package org.simantics.scl.compiler.internal.elaboration.utils;


/**
 * An implementation of Tarjan's algorithms for finding
 * the strongly connected components of a directed graph.
 * 
 * @author Hannu Niemistö
 */
public abstract class StronglyConnectedComponents {

    private int[] id;
    private int[] lowId;
    private boolean[] inStack;
    private int[] stack;
    private int stackPos = 0;
    private int currentId = 0;	 

    /**
     * Creates new instance of the algorithm for
     * finding strongly connected components. 
     * Size is the number of vertices of the graph.
     */
    public StronglyConnectedComponents(int size) {
        id = new int[size];
        lowId = new int[size];
        inStack = new boolean[size];
        stack = new int[size];
        for(int i=0;i<id.length;++i)
            id[i] = -1;
    }

    /**
     * Finds the components.
     */
    public void findComponents() {
        for(int i=0;i<id.length;++i)
            if(id[i] < 0)
                visit(i);
    }

    private void visit(int v) {
        int vId = currentId++;
        id[v] = vId;
        int tempLowId = vId;	

        int initialStackPos = stackPos;
        stack[stackPos++] = v;
        inStack[v] = true;

        for(int u : findDependencies(v)) {
            int uId = id[u];
            if(uId < 0) {
                visit(u);
                tempLowId = Math.min(tempLowId, lowId[u]);
            }
            else if(inStack[u])
                tempLowId = Math.min(tempLowId, uId);
        }

        lowId[v] = tempLowId;		
        if(vId == tempLowId) {
            int[] component = new int[stackPos-initialStackPos];
            while(stackPos > initialStackPos) {
                int e = stack[--stackPos];
                component[stackPos - initialStackPos] = e;
                inStack[e] = false;
            }
            reportComponent(component);
        }
    }

    /**
     * Returns dependencies of the vertex u.
     */
    protected abstract int[] findDependencies(int u);

    /**
     * Reports one strongly connected component of
     * the graph. The components are reported in the
     * order of dependency.
     */
    protected abstract void reportComponent(int[] component);

}