import edu.neu.ccs.demeterf.lib.List;
import java.io.FileInputStream;
import gen.*;
import java.util.Hashtable;
import java.util.Map.Entry;

public class TopoSort{
    static void p(String s){ System.out.println(s); }
    public static void main(String[] args) throws Exception{
        if(args.length == 0){
            p(" ** no input file given!\n");
            return;
        }
        Test t = Test.parse(new FileInputStream(args[0]));
        Graph<String,String> g = t.getG();
        p("Graph:\n"+t);
        p("Nodes: "+g.nodes());
        p(" Topo: "+iterative(g)+"\n");
    }

    static <N,L> List<Node<N>> iterative(Graph<N,L> g){
        final Hashtable<Node<N>,Integer> counts = inDegrees(g);
        final Hashtable<Node<N>,Adj<N,L>> adjs = adjHash(g);
        List<Node<N>> T = List.create();
        List<Node<N>> S = g.nodes().filter(new List.Pred<Node<N>>(){
                public boolean huh(Node<N> n){ return !counts.containsKey(n); }
            });

        while(!S.isEmpty()){
            Node<N> n = S.top();
            T = T.push(n);
            S = S.pop();

            for(Edge e : adjs.get(n))
                if(updateCount(counts, e.getTarg(), -1) == 0)
                    S = S.push(e.getTarg());
        }
        return T.reverse();
    }
    
    static <N,L> Hashtable<Node<N>,Integer> inDegrees(Graph<N,L> g){
        Hashtable<Node<N>,Integer> counts = new Hashtable<Node<N>,Integer>();
        for(Adj<N,L> adj : g)
            for(Edge<N,L> e : adj)
                updateCount(counts, e.getTarg(), +1);
        return counts;
    }

    static <N> int updateCount(Hashtable<Node<N>,Integer> counts, Node<N> n, int diff){
        int c = 0;
        if(counts.containsKey(n))
            c = counts.get(n);
        counts.put(n, c+diff);
        return c+diff;
    }

    static <N,L> Hashtable<Node<N>,Adj<N,L>> adjHash(Graph<N,L> g){
        Hashtable<Node<N>,Adj<N,L>> adjs = new Hashtable<Node<N>,Adj<N,L>>();
        for(Adj<N,L> adj : g)
            adjs.put(adj.getNode(), adj);
        return adjs;
    }
}