// -------------
// BFSearch.java
// -------------

import java.util.Arrays;
import java.util.Collections;
import java.util.LinkedList;
import java.util.Queue;

final class BFSearch {
    /**
     * O(v)     in space
     * O(v + e) in time
     */
    public static boolean eval (int[][] g, int u, int v) {
        final boolean[]      b  = new boolean[g.length];
        final Queue<Integer> qi = new LinkedList<Integer>();
        b[u] = true;
        qi.add(u);
        while (!qi.isEmpty()) {
            final int t = qi.remove();
            if (t == v)
                return true;
            for (int w : g[t])
                if (!b[w]) {
                    b[w] = true;
                    qi.add(w);}}
        return false;}

    /**
     * O(v)     in space
     * O(v + e) in time
     */
    public static boolean eval (int[][] g, int u, int v, GraphVisitor gv) {
        final boolean[]      b  = new boolean[g.length];
        final Queue<Integer> qi = new LinkedList<Integer>();
        b[u] = true;
        qi.add(u);
        gv.visit(u, u);
        while (!qi.isEmpty()) {
            final int t = qi.remove();
            if (t == v)
                return true;
            for (int w : g[t])
                if (!b[w]) {
                    b[w] = true;
                    qi.add(w);
                    gv.visit(t, w);}}
        return false;}}

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

        final int[][] g = { // Fig. 14.30, Pg. 500
            {1, 3},         // 0
            {3, 4},         // 1
            {0, 3, 5},      // 2
            {4, 5, 6},      // 3
            {6},            // 4
            {},             // 5
            {5}};           // 6

        assert BFSearch.eval(g, 0, 0) == true;
        assert BFSearch.eval(g, 0, 1) == true;
        assert BFSearch.eval(g, 0, 2) == false;
        assert BFSearch.eval(g, 0, 3) == true;
        assert BFSearch.eval(g, 0, 4) == true;
        assert BFSearch.eval(g, 0, 5) == true;
        assert BFSearch.eval(g, 0, 6) == true;

        assert BFSearch.eval(g, 3, 0) == false;
        assert BFSearch.eval(g, 3, 1) == false;
        assert BFSearch.eval(g, 3, 2) == false;
        assert BFSearch.eval(g, 3, 3) == true;
        assert BFSearch.eval(g, 3, 4) == true;
        assert BFSearch.eval(g, 3, 5) == true;
        assert BFSearch.eval(g, 3, 6) == true;

        assert BFSearch.eval(g, 6, 0) == false;
        assert BFSearch.eval(g, 6, 1) == false;
        assert BFSearch.eval(g, 6, 2) == false;
        assert BFSearch.eval(g, 6, 3) == false;
        assert BFSearch.eval(g, 6, 4) == false;
        assert BFSearch.eval(g, 6, 5) == true;
        assert BFSearch.eval(g, 6, 6) == true;

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

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

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