/****************************************************************
 * SearchApplet.java
 *
 * Applet that runs a search algorithm on a specified tree.
 */

import java.applet.Applet;
import java.awt.*;
import java.util.StringTokenizer;
import java.util.Vector;

/**
 * This applet runs a search algorithm on a tree, taking
 * user input to determine what to search for within the tree and
 * producing a visual representation of the search's progress through
 * the tree.
 * Uses some of the ideas demonstrated in the sort demo included
 * with Sun's JDK 1.1. 
 * 
 * To use this applet, you would add a tag like the following into your
 * HTML:
 * <pre>
 * &lt;applet code="SearchApplet.class" width=400 height=350&gt; 
 * &lt;PARAM name=alg value="BreadthFirstSearch"&gt; 
 * &lt;/applet&gt;
 * </pre>
 *
 * If you are using the Depth-Limited algorithm, which takes a depth
 * limit, you could also add another PARAM tag to specify that limit:
 * <pre>
 * &lt;PARAM name=depth value="3"&gt;
 * </pre>
 *
 * To-do list of improvements
 * <UL>
 * <LI>Allow the user to enter a block of text to be used as the tree
 *	instead of having it hardwired in.
 * <LI>Along the lines of the first one, have a randomly-generated
 *	"numeric" tree used. 
 * <LI>Allow the user to input the branching factor of the tree, or 
 *	perhaps just make this an optional parameter of the applet.
 * </UL>
 *
 * @author Naomi Novik
 */
public class SearchApplet extends Applet implements Runnable
{
    /* Following are workarounds for font size calculations, as Netscape
     * reports unappealing font height/ascents on varying platforms. */
    static final int FIXED_FONT_HEIGHT = 10; 
    static final int FIXED_FONT_ASCENT = 3;
    
    static final String treeString = "This is a string used to build a tree of strings for the search algorithms to work on";
    /** 
     * Thread to run the search algorithm. */
    Thread       	kicker;
    
    /** 
     * @see WalTreeCanvas */
    WalTreeCanvas	treeCanvas;

    /**
     * @see WNode */
    WNode       	root;
    
    /**
     * Store the nodes of the tree in order for easier insertion
     * of new nodes.
     */
    Vector		treeNodes;
    
    /**
     * Branching factor of the tree.
     */
    int			branchFactor;
    
    /**
     * @see SearchAlgorithm */
    SearchAlgorithm	algorithm;
    String		algName;

    /* User input widgets */
    Panel		inputPanel;
    Button		btn_clear;
    Button		btn_start;
    TextField		textToFind;
    String		searchString;
    
    /* Status bar */
    public TextField	statusBar;

    // Some basic info about the applet.
    public String getAppletInfo() {
	return "SearchApplet v. 0.1.\nWritten by Naomi Novik.";
    }
	
    // Information about the supported parameters
    public String[][] getParameterInfo() {return info;}
	
    private String[][] info = {
	{"alg", "string", "name of search algorithm to use"},
	{"depth", "integer", "maximum depth to search to in the tree"}
    };

    /**
     * Initialize the applet.
     */
    public void init ()
    {
	String str;

	searchString = null; // initially
	branchFactor = 2; // default

	/* Get the algorithm to use from the PARAM tag in HTML. */
	String algParam = getParameter("alg");
	if (algParam == null) {
	    algParam = "BreadthFirst";
	}
	algName = algParam + "Algorithm";
	
	/* Set up the tree display */
	setLayout(new BorderLayout());
	add("Center", treeCanvas = new WalTreeCanvas());
	statusBar = new TextField(40);
	statusBar.setEditable(false);
	statusBar.setText("SearchApplet initializing...");
	add("South",statusBar);
	
	/* Set distance between node and child. */
	treeCanvas.setParentDistance(5);

	/* Add the user input widgets. */
	inputPanel = new Panel();
	inputPanel.add(new Label("Search String: "));
	inputPanel.add(textToFind = new TextField(10));
	inputPanel.add(btn_clear = new Button("Clear"));
	inputPanel.add(btn_start = new Button("Start Search"));
	add("North", inputPanel);

	/* Initialize the tree. */
	root = null;
	buildTree(); // We want to construct a tree to search in.
	
	statusBar.setText("SearchApplet ready: " + algName);
    }
    
    /**
     * Handle events that occur in the applet as a result of user action.
     */
    public boolean handleEvent(Event e) {
	if(e.id == Event.ACTION_EVENT && e.target == btn_clear) {
	    clearSearch();
	} else if (e.id == Event.ACTION_EVENT && e.target == btn_start) {
	    // set the value of the searchString
	    setSearchString(textToFind.getText());
	    
	    // Throw an error or print a warning here if the searchString is
	    // null.
	    if (searchString == null) {
	    	statusBar.setText("No search string entered!");
	    } else {
		statusBar.setText("Starting search.");
		startSearch();
	    }
	} else {
	    return false;
	}
	return true;
    }


    /**
     * Set the value of the searchString.
     */
    void setSearchString(String s) {
    	if (s == "") {return;}
    	searchString = s;
    }


    /**
     * Stop the applet. Kill any algorithm that is still
     * searching.
     */
    public synchronized void stop() {
	if (kicker != null) {
            try {
		kicker.stop();
            } catch (IllegalThreadStateException e) {
                // ignore this exception
            }
	    kicker = null;
	}
	if (algorithm != null){
            try {
		algorithm.stop();
            } catch (IllegalThreadStateException e) {
                // ignore this exception
            }
	}
    }


    /**
     * Start a search of the tree by starting off a new Thread. The
     * Thread will then call the run() procedure below. This shouldn't
     * get called if the searchString variable is null!
     * It needs to be synchronized with the stop() method because they 
     * both manipulate the common kicker variable.
     */
    private synchronized void startSearch() {
	if (kicker == null || !kicker.isAlive()) {
	    repaint();
	    kicker = new Thread(this);
	    kicker.start();
	}
    }



    /**
     * Main event loop. This will be called by the Thread forked
     * off in startSearch.
     * We need to set the search algorithm to be used, using the 
     * name specified in the applet's params.
     */
    public void run () {
    	Integer d;
    	WNode n = null;
    	
	try {
	    if (algorithm == null) {
		algorithm = (SearchAlgorithm)Class.forName(algName).newInstance();
		algorithm.setCaller(this);
		// Get the depth limit to search to from the PARAM tag in HTML.
		// If present and not null, call setDepth() procedure of 
		// searchAlgorithm.
		String dstring = getParameter("depth");
		if (dstring != null) {
		    try {
			d = new Integer(getParameter("depth"));
		    	algorithm.setDepth(d.intValue());
		    } catch (NumberFormatException nfe) {
		    	// Ignore the error; it'll just use the default.
		    } 
		}		    
	    }
	    algorithm.init();
	    // Pass the tree and the string to find along to the search alg.
	    n = algorithm.search(root, searchString);
	    // Print out results
	    treeCanvas.repaint();
	    if (n != null) {
	    	int nd = n.getNodeDepth();
	    	statusBar.setText("Search string found at depth " + nd);
	    } else {
	    	statusBar.setText("Search failed.");
	    }
	//} catch (ArrayIndexOutOfBoundsException oob) {
	   // n = null;
	   // statusBar.setText("Search failed.");
	} catch(Exception e) {
	    statusBar.setText("Error in search: " + e.toString());
	}
	
    }


    /**
     * Pause a while, to make the search progress visually clearer.
     * @see SearchAlgorithm
     */
    public void pause() {
	if (kicker != null) {
	    treeCanvas.repaint();
	}
	try {
	    Thread.sleep(1000);
	} catch (InterruptedException e) {
	    statusBar.setText("Exception caught in pause: " + e.toString());
	}
    }

    /**
     * Construct a tree to search in, based on the treeString variable,
     * by tokenizing that variable and adding each token from the string
     * to the tree. We clear the tree first before building it.
     */
    private void buildTree() {
    	clearTree();
    	treeNodes = new Vector();
    	StringTokenizer treeTokenizer = new StringTokenizer(treeString);
    	String tok;
    	while (treeTokenizer.hasMoreElements()) {
    	    tok = treeTokenizer.nextToken();
    	    addString(tok);
    	}
    }

    /**
     * Clear the tree completely. 
     */
    public void clearTree() {
	root = null;
	treeCanvas.setTree(null);

	treeCanvas.repaint();
    }


    /**
     * Add the specified string to the displayed tree.
     */
    public void addString(String s) {

	if(s.equals("")) {
	    return;
	}

	if(root == null) {
	    root = treeCanvas.makeNode(s, null, null, null);
	    treeNodes.addElement(root);
	} else {
	    WNode n = treeCanvas.makeNode(s, null, null, null);
	    insertNode(n);
	    treeNodes.addElement(n);
	}

	treeCanvas.setTree(root);
	treeCanvas.repaint();
    }

    /**
     * Insert the specified node into the tree at the next available
     * spot (depends on branchFactor).
     */
    public void insertNode(WNode n) {
	WNode t;
	Vector allChildren;
	int childCount;
	
	for (int i = 0; i < treeNodes.size(); i++) {
	    t = (WNode) treeNodes.elementAt(i);
	    allChildren = t.expand();
	    childCount = allChildren.size();
	    if (childCount < branchFactor) {
	    	// n becomes child of t
	    	n.parent = t;
	    	n.sibling = t.child;
	    	t.child = n;
	    	return;
	    }
	}
    }

    /**
     * Clear the search information while still preserving the tree.
     */
    public void clearSearch() {
	clearSearch(root);
	treeCanvas.repaint();
	statusBar.setText("SearchApplet ready: " + algName);
    }
    
    /**
     * Iterate through the tree, calling the 'leave()' member
     * function on each node to clear the visited information.
     *
     * @see WNode#leave
     */
    private void clearSearch(WNode t) {
    	WNode n;
    	
    	if (t==null) {return;}
    	t.leave();
    	n = t.child;
    	
    	while (n != null) {
    	    clearSearch(n);
    	    n = n.sibling;
    	}
    }

};