/* vim: set expandtab tabstop=4 shiftwidth=4 : */

import java.util.Iterator;

public class SAP
{

    private final Digraph g;
    private final BFS vBFS;
    private final BFS wBFS;

    private class BFS implements Iterable<Integer>
    {
        private static final int MAXINT = Integer.MAX_VALUE;

        private boolean[] marked;
        private int[] distTo;
        private Queue<Integer> visited;
        private Queue<Integer> q;

        public BFS(int size)
        {
            marked = new boolean[size];
            distTo = new int[size];
            visited = new Queue<Integer>();
            q = new Queue<Integer>();
            for (int v = 0; v < size; v++) {
                // distTo[v] = -1;
                marked[v] = false;
            }
        }

        public void bfs(int s)
        {
            clear();

            marked[s] = true;
            distTo[s] = 0;

            q.enqueue(s);
            visited.enqueue(s);
            bfs();
        }

        public void bfs(Iterable<Integer> ss)
        {
            clear();

            for (int s : ss) {
                marked[s] = true;
                distTo[s] = 0;
                q.enqueue(s);
                visited.enqueue(s);
            }

            bfs();
        }

        public int distTo(int v)
        {
            return distTo[v];
        }

        public boolean hasPathTo(int v)
        {
            return marked[v];
        }

        public Iterator<Integer> iterator() {
            return visited.iterator();
        }

        public int visitedCount()
        {
            return visited.size();
        }

        private void clear()
        {
            while (!visited.isEmpty()) {
                marked[visited.dequeue()] = false;
            }
        }

        private void bfs()
        {
            while (!q.isEmpty()) {
                int v = q.dequeue();
                for (int w : g.adj(v)) {
                    if (!marked[w]) {
                        distTo[w] = distTo[v] + 1;
                        marked[w] = true;
                        q.enqueue(w);
                        visited.enqueue(w);
                    }
                }
            }
        }
    }

    // data type use space proportional to E + V
    // all methods take time at most proportional to E + V in the worst case

    // constructor takes a digraph (not necessarily a DAG)
    public SAP(Digraph G)
    {
        g = new Digraph(G);
        vBFS = new BFS(G.V());
        wBFS = new BFS(G.V());
    }

    // length of shortest ancestral path between v and w
    // -1 if no such path
    public int length(int v, int w)
    {
        check(v);
        check(w);

        vBFS.bfs(v);
        wBFS.bfs(w);

        return distance();
    }

    // a common ancestor of v and w that participates in a shortest ancestral path
    // -1 if no such path
    public int ancestor(int v, int w)
    {
        check(v);
        check(w);

        vBFS.bfs(v);
        wBFS.bfs(w);

        return ancestor();
    }

    // length of shortest ancestral path between any vertex in v and any vertex in w
    // -1 if no such path
    public int length(Iterable<Integer> v, Iterable<Integer> w)
    {
        check(v);
        check(w);

        vBFS.bfs(v);
        wBFS.bfs(w);

        return distance();
    }

    // a common ancestor that participates in shortest ancestral path
    // -1 if no such path
    public int ancestor(Iterable<Integer> v, Iterable<Integer> w)
    {
        check(v);
        check(w);

        vBFS.bfs(v);
        wBFS.bfs(w);

        return ancestor();
    }

    private int distance()
    {
        BFS aBFS, bBFS;
        if (vBFS.visitedCount() < wBFS.visitedCount()) {
            aBFS = vBFS;
            bBFS = wBFS;
        } else {
            aBFS = wBFS;
            bBFS = vBFS;
        }

        int len = Integer.MAX_VALUE;

        for (int x : aBFS) {
            if (bBFS.hasPathTo(x)) {
                int l = aBFS.distTo(x) + bBFS.distTo(x);
                if (l < len) {
                    len = l;
                }
            }
        }

        if (len == Integer.MAX_VALUE)
            return -1;
        return len;
    }

    private int ancestor()
    {
        BFS aBFS, bBFS;
        if (vBFS.visitedCount() < wBFS.visitedCount()) {
            aBFS = vBFS;
            bBFS = wBFS;
        } else {
            aBFS = wBFS;
            bBFS = vBFS;
        }

        int ancestor = -1;
        int len = Integer.MAX_VALUE;

        for (int x : aBFS) {
            if (bBFS.hasPathTo(x)) {
                int l = aBFS.distTo(x) + bBFS.distTo(x);
                if (l < len) {
                    len = l;
                    ancestor = x;
                }
            }
        }

        return ancestor;
    }

    private void check(int v)
    {
        if (v < 0 || v >= g.V())
            throw new IndexOutOfBoundsException("out of index");
    }

    private void check(Iterable<Integer> vs)
    {
        for (int v : vs) {
            check(v);
        }
    }

    // for unit testing of this class (such as the one below)
    public static void main(String[] args)
    {
        int length, ancestor;
        In in;
        Digraph G;
        SAP sap;

        in = new In("./data/digraph1.txt");
        G = new Digraph(in);
        sap = new SAP(G);

        length = sap.length(3, 11);
        ancestor = sap.ancestor(3, 11);
        StdOut.printf("length = %d, ancestor = %d\n", length, ancestor);

        length = sap.length(9, 12);
        ancestor = sap.ancestor(9, 12);
        StdOut.printf("length = %d, ancestor = %d\n", length, ancestor);

        length = sap.length(7, 2);
        ancestor = sap.ancestor(7, 2);
        StdOut.printf("length = %d, ancestor = %d\n", length, ancestor);

        length = sap.length(1, 6);
        ancestor = sap.ancestor(1, 6);
        StdOut.printf("length = %d, ancestor = %d\n", length, ancestor);

        Stopwatch w1 = new Stopwatch();
        for (int i = 1; i < 7; i++) {
            String g = "./data/digraph"+i+".txt";
            in = new In(g);
            G = new Digraph(in);
            sap = new SAP(G);
            for (int v = 0; v < G.V(); v++) {
                for (int w = 0; w < G.V(); w++) {
                    int a = sap.ancestor(v, w);
                    int l = sap.length(v, w);
                    // StdOut.printf("%s %d->%d : a:%d l:%d\n", g, v, w, a, l);
                }
            }
        }
        double a1 = w1.elapsedTime();
        StdOut.printf("all solved in : %g \n", a1);
    }
}