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

import java.util.Vector;

/**
 * Extends the DepthFirstSearchAlgorithm class to use the Depth-Limited 
 * search algorithm, which performs depth-first search but stops at
 * a specified depth before going any further.
 */
public class DepthLimitedSearchAlgorithm extends DepthFirstSearchAlgorithm {
        
    /**
     * Override searchQueue (from the SearchAlgorithm class) to return 
     * when a specific depth is reached.
     */
    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 if (top.getNodeDepth() == depth) {
     	    // Keep searching without adding children to the queue.
     	    return searchQueue();
    	} 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();
    	}
    }
 

}