/**
 * IterativeDeepeningSearchAlgorithm
 * Expands on the generic SearchAlgorithm to search for a specified
 * string within a tree.
 */

import java.util.Vector;

/**
 * Extends the DepthLimitedSearchAlgorithm class to use the Iterative Deepening 
 * search algorithm, which performs depth-limited search repeatedly, increasing
 * the depth limit each time, until the tree is empty or the desired node is
 * found.
 */
public class IterativeDeepeningSearchAlgorithm extends DepthLimitedSearchAlgorithm {

    /**
     * Override search method from SearchAlgorithm class.
     */
    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;
	}
	
	
	// Increase the depth until we find the target or exceed the
	// maximum depth of the tree.
	int maxDepth = root.getTreeDepth();
	for (int i=0; i <= maxDepth ; i++) {
	    enqueue(root);
	    setDepth(i);
	    clearSearch();
	    n = searchQueue();
	    if (n != null) {
	    	return n;
	    }
	}
	
	return n;
	
    }

}