ByLevelHeuristic.java

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;
    }
}