package Heuristics; import FaultTree.BasicEvent; import FaultTree.IntermediateEvent; import FaultTree.FaultTree; import java.util.*; import static java.lang.Math.max; public class ByLevelHeuristic implements Heuristic { Map<IntermediateEvent, Integer> levelsIE; Map<BasicEvent, Integer> order; @Override public Map<BasicEvent, Integer> getOrder(FaultTree tree) { order = new HashMap<>(); if (tree == null) { return order; } levelsIE = new HashMap<>(); int counter = 0; LinkedList<IntermediateEvent> listIE = new LinkedList<>(); LinkedList<BasicEvent> listBE = new LinkedList<>(); IntermediateEvent root = (IntermediateEvent)tree; levelsIE.put(root, 0); updateLists(listBE, listIE, root); while(listBE.size() > 0 || listIE.size() > 0){ LinkedList<IntermediateEvent> tempIE = new LinkedList<>(); for(BasicEvent event : listBE){ //if all parents of a child have level assigned => add child to final ordering //otherwise skip this child for now if(!order.containsKey(event) && isAllParentsSeen(event)){ order.put(event, counter++); } } listBE = new LinkedList<>(); for(IntermediateEvent event : listIE){ if(!levelsIE.containsKey(event) && isAllParentsSeen(event)){ int maxParentLevel = getMaxParentLevel(event); levelsIE.put(event, maxParentLevel+1); updateLists(listBE, tempIE, event); } } listIE = tempIE; } return order; } private void updateLists(LinkedList<BasicEvent> listBE, LinkedList<IntermediateEvent> listIE, IntermediateEvent event) { if(event.left instanceof BasicEvent){ listBE.add((BasicEvent) event.left); } else if(event.left instanceof IntermediateEvent){ listIE.add((IntermediateEvent) event.left); } if(event.right instanceof BasicEvent){ listBE.add((BasicEvent) event.right); } else if(event.right instanceof IntermediateEvent){ listIE.add((IntermediateEvent) event.right); } } private boolean isAllParentsSeen(FaultTree event){ for(IntermediateEvent parent : event.getParents()){ if (!levelsIE.containsKey(parent)){ return false; } } return true; } private int getMaxParentLevel(FaultTree event){ int maxLevel = 0; for(IntermediateEvent parent : event.getParents()){ maxLevel = max(maxLevel, levelsIE.get(parent)); } return maxLevel; } }