/*
 * SearchAlgorithm.java
 */

import java.util.Vector;

/**
 * A generic search algorithm, implementing the basic methods needed
 * for a search. The three main methods that need to be overridden in
 * order to make a specific search algorithm are search(), searchQueue(),
 * and enqueue().
 * <P>
 * @author Naomi Novik
 */
public class SearchAlgorithm {
    /**
     * The search applet.
     */
    private SearchApplet caller;

    /**
     * When true stop searching.
     */
    protected boolean stopRequested = false;
    
    /**
     * Vector containing the queue of nodes to search.
     */
    protected Vector nodeQueue;
    
    /**
     * What to look for.
     */
    protected String searchString;

    /**
     * Maximum depth in the tree to search until, used in depth-limited
     * and iterative-deepening search algorithms.
     */
    protected int depth = 10;
    
    /**
     * Constructor.
     */
    public SearchAlgorithm() {
    	super();
    }
    	

    /**
     * Set the caller.
     */
    public void setCaller(SearchApplet c) {
	caller = c;
    }

    /**
     * Set depth.
     */
    public void setDepth(int d) {
    	this.depth = d;
    	caller.statusBar.setText("Depth limit set to: " + d);

    }
    
    
    /**
     * Clear the search.
     */
    protected void clearSearch() {
    	caller.clearSearch();
    }

    /**
     * Stop searching.
     */
    public void stop() {
	stopRequested = true;
    }

    /**
     * Initialize
     */
    public void init() {
	stopRequested = false;
    }

    /**
     * Pop off the top value of nodeQueue.
     */
    protected WNode pop() {
    	WNode top = null;    	
    	if (nodeQueue.size() <=0) {return top;}    	
	top = (WNode) this.nodeQueue.elementAt(0);	// Top of the queue
	nodeQueue.removeElementAt(0);	
	return top;
    }
    
    /**
     * Peek at the top value of nodeQueue.
     */
    protected WNode peek() {
    	WNode top = null;
   	if (nodeQueue.size() <=0) {return top;}
    	top = (WNode) this.nodeQueue.elementAt(0);
    	return top;
    }

    /**
     * Pause for a while.
     */
    protected void pause() throws Exception {
	if (stopRequested) {
	    throw new Exception("Search Algorithm");
	}
	caller.pause();
    }

    /**
     * This method will be called to search through a tree.
     */
    public WNode search(WNode root, String searchString) throws Exception {
        WNode n = null;
	nodeQueue = new Vector();

	if (searchString == null || searchString.equals("")) {
	    throw new Exception("No search string specified.");
    	} else if (root == null) {
    	    return n;
	} else {
	    this.searchString = searchString;
	    enqueue(root);
	}
	
	n = searchQueue();
	return n;
    }
    
    /**
     * Recursively called to search through the queue of nodes.
     * Return the node if searchString found.
     */
    protected WNode searchQueue() throws Exception {
	Vector newNodes;
	WNode top;
        
        pause();
        
        top = pop();
        
    	if (top == null) {return top;}
        
        top.visit();
	
	if (searchString.equals(top.toString())) {
     	    return top;
    	} else {
    	    /* Keep searching; add the children of this node to the queue. */
    	    newNodes = top.expand();
    	    for (int i=0; i < newNodes.size(); i++) {
    	    	enqueue((WNode) newNodes.elementAt(i));
    	    }
    	    return searchQueue();
    	}
    }
    
    /**
     * This method will be called to enqueue a new node.
     * Should be overridden by child classes.
     */
    protected void enqueue(WNode newNode) { }
    
}