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

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

    private static  class SAPResult {
        private int ancestor;
        private int length;
        public SAPResult(int a, int l) {
            ancestor = a;
            length = l;
        }
        public int length() { return length; }
        public int ancestor() { return ancestor; }
    };

    private Digraph g;

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

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

    // 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)
    {
        return ancestorAndLength(v, w).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)
    {
        return ancestorAndLength(v, w).length();
    }

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

    private SAPResult ancestorAndLength(int v, int w)
    {
        if ((Math.max(v, w) >= g.V()) || (Math.min(v, w) < 0))
            throw new IndexOutOfBoundsException("out of index");

        // the smallest index shall have the smallest components count
        int a, b;
        if (v < w) {
            a = v;
            b = w;
        } else {
            a = w;
            b = v;
        }

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

        if (a == b) {
            sol = a;
            len = 0;
        } else {

            ResizingArrayQueue<Integer> c = new ResizingArrayQueue<Integer>();
            SpecializedBFS aBFS = new SpecializedBFS(g, a, c);
            SpecializedBFS bBFS = new SpecializedBFS(g, b, null);

            for (int x : c) {
                if (!bBFS.hasPathTo(x)) continue;
                int l = aBFS.distTo(x) + bBFS.distTo(x);
                if (len > l) {
                    len = l;
                    sol = x;
                }
            }
        }

        if (sol == -1) len = -1;

        return new SAPResult(sol, len);
    }

    private SAPResult ancestorAndLength(Iterable<Integer> vv, Iterable<Integer> ww)
    {
        for (int v : vv) {
            if (v < 0 || v >= g.V())
                throw new IndexOutOfBoundsException("out of index");
        }
        for (int w : ww) {
            if (w < 0 || w >= g.V())
                throw new IndexOutOfBoundsException("out of index");
        }

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

        ResizingArrayQueue<Integer> c = new ResizingArrayQueue<Integer>();
        SpecializedBFS aBFS = new SpecializedBFS(g, vv, c);
        SpecializedBFS bBFS = new SpecializedBFS(g, ww, null);

        for (int x : c) {
            if (!bBFS.hasPathTo(x)) continue;
            int l = aBFS.distTo(x) + bBFS.distTo(x);
            if (len > l) {
                len = l;
                sol = x;
            }
        }

        if (sol == -1) len = -1;

        SAPResult res = new SAPResult(sol, len);

        return res;
    }

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