// ---------------
// BFSPSearch.java
// ---------------

import java.util.Arrays;
import java.util.PriorityQueue;

final class Entry implements Comparable<Entry> {
    private int v;
    private int w;

    public Entry (int vertex, int weight) {
        v = vertex;
        w = weight;}

    public int compareTo (Entry that) { // const
        return w - that.w;}

    public int vertex () { // const
        return v;}

    public int weight () { // const
        return w;}}

final class BFSPSearch {
    /**
     * O(e)            in space
     * O(v log(e) + e) in time
     */
    public static boolean eval (Entry[][] g, int u, int v, GraphVisitor gv) {
        final int[]                a   = new int[g.length];
        final PriorityQueue<Entry> pqe = new PriorityQueue<Entry>();
        Arrays.fill(a, Integer.MAX_VALUE);
        a[u] = 0;
        pqe.add(new Entry(u, 0));
        gv.visit(u, u);
        while (!pqe.isEmpty()) {
            final int t = pqe.remove().vertex();
            if (t == v)
                return true;
            for (Entry e : g[t]) {
                final int w = e.vertex();
                final int x = a[t] + e.weight();
                if (x < a[w]) {
                    a[w] = x;
                    pqe.add(new Entry(w, a[w]));
                    gv.visit(t, w);}}}
        return false;}}

final class BFSPSearchTest {
    public static void main (String[] args) {
        System.out.println("BFSPSearch.java");

        final Entry[][] g = {
            {new Entry(1, 4), new Entry(2,  2), new Entry(4, 15)}, // 0
            {new Entry(3, 1), new Entry(4, 10)},                   // 1
            {new Entry(3, 5)},                                     // 2
            {new Entry(4, 3), new Entry(5,  0)},                   // 3
            {},                                                    // 4
            {new Entry(3, 2), new Entry(7,  4)},                   // 5
            {new Entry(7, 4)},                                     // 6
            {}};                                                   // 7

        {
        final GraphEdgeVisitor gev = new GraphEdgeVisitor(g.length);
        assert BFSPSearch.eval(g, 0, 4, gev) == true;
        assert Arrays.equals(gev.pred(), new int[]{0,  0,  0,  1,  3,  3, -1,  5});
        assert gev.path(0, 4).equals(Arrays.asList(0, 1, 3, 4));
        }

        {
        final GraphEdgeVisitor gev = new GraphEdgeVisitor(g.length);
        assert BFSPSearch.eval(g, 0, 6, gev) == false;
        }

        System.out.println("Done.");}}