// BreadthFirstSearch.java
//
// Copyright Mark Watson, 1998.  Open Source and Open Content.
//

import java.util.Vector;

public class BreadthFirstSearch extends SearchApplet {

    public void init() {

	// Define a test network before calling the super class 'init':
	addNode("0", 0.0f, 0.0f);
	addNode("1", 1.0f, 1.0f);
	addNode("2", 5.0f, 2.0f);
	addNode("3", 2.0f, 5.0f);
	addNode("4", 7.0f, 5.0f);
	addNode("5", 8.0f, 8.0f);
	addNode("6", 10.0f, 5.0f);
	addNode("7", 8.0f, 2.0f);
	addNode("8", 12.0f, 8.0f);
	addNode("9", 13.0f, 5.0f);

	addLink(0,1);
	addLink(1,2);
	addLink(2,3);
	addLink(2,4);
	addLink(4,5);
	addLink(4,6);
	addLink(6,8);
	addLink(8,9);
	addLink(2,7);
	addLink(7,9);

	// Now that we have defined the network to search, we
	// can now call the super class init:
	super.init();
    }

    /** findPath - abstract method in super class */
    // Breadth first search  algorithm from "Algorithms"
    // (Cormen, Leiserson, Rivest) page 460:
    public int [] findPath(int node_1, int node_2) { // return an array of node indices
	System.out.println("Entered BreadthFirstSearch.findPath(" +
			   node_1 + ", " + node_2 + ")");
	if (node_1 == node_2)  {
	    repaintPath(null, 0);
	    return null;
	}
	// data structures for depth first search:
	boolean [] visitedFlag = new boolean[numNodes];
	float [] distanceToNode = new float[numNodes];
	int [] predecessor = new int[numNodes];
	Queue queue = new Queue(numNodes + 2);

	// data structures for graphical display (only):
	int [] display_path = new int[2 * numNodes + 1];
	int num_display_path = 0;

	for (int i=0; i<numNodes; i++) {
	    visitedFlag[i] = false;
	    distanceToNode[i] = 10000000.0f;
	    predecessor[i] = -1;
	}

	visitedFlag[node_1] = true;
	distanceToNode[node_1] = 0.0f;
	queue.enqueue(node_1);
outer:	while (queue.isEmpty() == false) {
	    int head = queue.head();
	    int [] connected = connected_nodes(head);
	    if (connected != null) {
		for (int i=0; i<connected.length; i++) {
		    if (visitedFlag[connected[i]] == false) {
			distanceToNode[connected[i]] = distanceToNode[head] + 1.0f;
			predecessor[connected[i]] = head;
			queue.enqueue(connected[i]);
			display_path[num_display_path++] = head;
			display_path[num_display_path++] = connected[i];
			repaintPath(display_path, num_display_path);
			if (connected[i] == node_2) break outer; // we are done
		    }
		}
		visitedFlag[head] = true;
		queue.dequeue(); // ignore return value
	    }
	}
	// now calculate the shortest path from the predecessor array:
	int [] ret = new int[numNodes + 1];
	int count = 0;
	ret[count++] = node_2;
	for (int i=0; i<numNodes; i++) {
	    ret[count] = predecessor[ret[count - 1]];
	    count++;
	    if (ret[count - 1] == node_1)  break;  // back to starting node
	}
	num_display_path = 0;
	int [] ret2 = new int[count];
	for (int i=0; i<count; i++) {
	    ret2[i] = ret[count - 1 - i];
	    if (i > 0) { // re-calculate the plot display points:
		display_path[num_display_path++] = ret2[i-1];
		display_path[num_display_path++] = ret2[i];
	    }
	}
	// now re-calculate the display path points:
	repaintPath(display_path, num_display_path);
	return ret2;   
    }

    // Queue algorithm from "Algorithms" (Cormen, Leiserson, Rivest) page 202:
    protected class Queue {
	public Queue(int num) {
	    queue = new int[num];
	    head = tail = 0;
	    len = num;
	}
	public Queue() {
	    this(400);
	}
	private int [] queue;
	int tail, head, len;
	public void enqueue(int n) {
	    queue[tail] = n;
	    if (tail >= (len - 1)) {
		tail = 0;
	    } else {
		tail++;
	    }
	}
	public int dequeue() {
	    int ret = queue[head];
	    if (head >= (len - 1)) {
		head = 0;
	    } else {
		head++;
	    }
	    return ret;
	}
	public boolean isEmpty() {
	    return head == (tail + 1);
	}
	public int head() {
	    return queue[head];
	}	
    }

    protected int [] connected_nodes(int node) {
	int [] ret = new int[SearchApplet.MAX];
	int num = 0;

	for (int n=0; n<numNodes; n++) {
	    boolean connected = false;
	    // See if there is a link between node 'node' and 'n':
	    for (int i=0; i<numLinks; i++) {
		if (link_1[i] == node) {
		    if (link_2[i] == n) {
			connected = true;
			break;
		    }
		}
		if (link_2[i] == node) {
		    if (link_1[i] == n) {
			connected = true;
			break;
		    }
		}
	    }
	    if (connected) {
		ret[num++] = n;
	    }
	}
	if (num == 0)  return null;
	int [] ret2 = new int[num];
	for (int i=0; i<num; i++) {
	    ret2[i] = ret[i];
	}
	return ret2;
    }
		
    private int [] path = new int[SearchApplet.MAX];
    private int num_path = 0;

    private int [] copy_path(int [] path, int num_to_copy) {
	int [] ret = new int[SearchApplet.MAX];
	for (int i=0; i<num_to_copy; i++) {
	    ret[i] = path[i];
	}
	return ret;
    }


}