package edu.princeton.cs.algs4.growingtree.framework;
/*
 * @(#)SearchBSTAnimation.java
 *
 * Last Modified: 9/15/01
 */

 import java.util.*;
 import java.lang.*;
 import java.awt.*;
 import java.awt.font.*;
 import java.awt.geom.*;
import java.text.*;


/** *
 	* The Animation object that defines the Searching in a BSTTree. <p>
 	*
	* The object restores all values changed in the given nodes, however, if the object
	* is never allowed to finish, the restoring of values becomes impossible. On any exception occuring
	* elsewhere, the object may not restore the conditions correctly. <p>
	*
	* @author  Corey Sanders
	* @version 1.3 9/15/01
 	*/

public class SearchBSTAnimation<P extends NodeProperties> extends AbstractAnimation {

	private static int X_MOVE_VALUE = 20;
	private static int Y_MOVE_VALUE = 5;


	/**
	 * Constant that defines the starting location.
	 */
	private final int START = 0;

	/**
	 * Constant the defines the final moving location.
	 */
	private int FINAL_MOVE;
	/**
	 * Constant the defines the end location.
	 */
	private int END;

	/**
	 * Color Scheme used for the animation on left, using one of the NodeSettings Schemes.
	 */
	private NodeSettings animationSchemeLeft;

	/**
	 * Color Scheme used for the animation on right, using one of the NodeSettings Schemes.
	 */
	private NodeSettings animationSchemeRight;

	/**
	 * Color Scheme used for the animator, using one of the NodeSettings Schemes.
	 */
	private NodeSettings animatorScheme;

	/**
	 * Color Scheme used for the key of the animator, using one of the KeySettings Schemes.
	 */
	private KeySettings keyAnimatorScheme;

	/**
	 * Private doubles used to hold the current and previous location steps.
	 */
	private double currentLocation = 0.0;
	private double previousLocation = 0.0;


	/**
	 * Refers to the list of AffineTransforms used to emphasize each given node.
	 */
	private AffineTransformList enlargeTransforms;

	/**
	 * Refers to the list of AffineTransforms used to emphasize each given node.
	 */
	private AffineTransformList keySearchTransforms;

	/**
	 * Refers to the linked list which will store the node of each step, used to draw the
	 * pass of each node.
	 */
	private LinkedList<GrowingTreeNode<P>> nodes;

	/**
	 * Holds the node that is doing the drawing.
	 */
	private KeyType keySearch;

	/**
	 * Counts the amount of comparisons made.
	 */
	private int comparisonCount = 0;

	/**
	 * Counts the initial insertion size of the tree.
	 */
	private int searchingSize = 0;

	/**
	 * Node made for the search through the tree.
	 */
	private GrowingTreeNode<P> keySearchNode;

	/**
	 * Boolean flag to signal a search discovery.
	 */
	private boolean searchHit = false;

	/**
	 * The current node being compared to for the search.
	 */
	private GrowingTreeNode<P> currentNode;

	/**
	 * The Default step conversion used in animation (300).
	 */
	 public final static int DEFAULT_CONVERSION = 300;


	/**
	 * The constructor which initiates the status and prepares the colorSchemes. The node
	 * which is animating must be passed.
	 *
	 * @param keySearch the object key being searched for with the tree.
	 * @param headNode the head of the tree being searched.
	 * @param AnimationSchemeLeft the <code>NodeSettings</code> associated with a color scheme according to NodeSettings for the left Animation.
	 * @param AnimationSchemeRight the <code>NodeSettings</code> associated with a color scheme according to NodeSettings for the right Animation.
	 * @param KeyAnimatorScheme the <code>KeySettings</code> associated with a color scheme according to KeySettings.
	 * @param startingCmd the Animation command that this should start.
	 * @param stepTime the time for each step of the Animation. Sets the initial value.
	 */
	public SearchBSTAnimation(KeyType keySearch, GrowingTreeHead<P> headNode, NodeSettings AnimationSchemeLeft, NodeSettings AnimationSchemeRight, NodeSettings AnimatorScheme, KeySettings KeyAnimatorScheme, String startingCmd, int stepTime) {
		super();

		// Set defaults if no color schemes exist
		if (AnimationSchemeLeft == null) {
			AnimationSchemeLeft = new NodeSettings();
		}

		if (AnimationSchemeRight == null) {
			AnimationSchemeRight = new NodeSettings();
		}
		if (AnimatorScheme == null) {
			AnimatorScheme = new NodeSettings();
		}

		if (KeyAnimatorScheme == null) {
			KeyAnimatorScheme = new KeySettings();
		}
		// init enlargeTransforms
		enlargeTransforms = new AffineTransformList();
		// init searchTransforms
		keySearchTransforms = new AffineTransformList();
		// init nodes
		nodes = new LinkedList<GrowingTreeNode<P>>();

		// Set Key search Node
		setKeySearchNode(new GrowingTreeNode<P>(GrowingTreeNode.ANIMATING_BST_TREE_TYPE));

		getKeySearchNode().setNode(keySearch, new DrawingKey(keySearch));
		getKeySearchNode().setHead(headNode);
		// Set searching insertion size.
		searchingSize = headNode.size();


		// Set Animation Schemes
		setAnimationSchemeLeft((NodeSettings)AnimationSchemeLeft.clone());
		setAnimationSchemeRight((NodeSettings)AnimationSchemeRight.clone());
		setAnimatorScheme((NodeSettings)AnimatorScheme.clone());
		setKeyAnimatorScheme((KeySettings)KeyAnimatorScheme.clone());



		// Set the drawing node.
		setKeySearch(keySearch);
		setStartingCommand(startingCmd);
		setStepTime(stepTime);

	}

	/**
	 * The constructor which initiates the status and sets the color schemes to null. All colors
	 * are set to default for this animation. The key which is being searched for must be
	 * passed.
	 *
	 * @param keySearch the object key being searched for with the tree.
	 * @param headNode the head of the tree being searched.
	 */
	public SearchBSTAnimation(KeyType keySearch, GrowingTreeHead<P> headNode) {
		this(keySearch, headNode, null, null, null , null , Animation.PLAY, DEFAULT_STEP);
	}


	/************************/
	/* Accessor methods     */
	/************************/
	/**
	 * Gets whether a search hit has been found.
	 *
	 * @return true if a search hit was found.
	 */
	 public boolean isSearchHit() {
		 return searchHit;
	 }



	/**
	 * Gets the comparable object being searched for.
	 *
	 * @return comparable object being searched for.
	 */
	 public KeyType getKeySearch() {
		 return keySearch;
	 }

	/**
	 * Gets the node currently being drawn during the Search.
	 *
	 * @return BSTTree of the key currently being search for.
	 */
	private GrowingTreeNode<P> getKeySearchNode() {
		return keySearchNode;
	}

	/**
	 * Gets the NodeSettings for the left animation scheme for the search.
	 *
	 * @return NodeSettings for the node after the animated node passes it to the left.
	 */
	public NodeSettings getAnimationSchemeLeft() {
		return animationSchemeLeft;
	}

	/**
	 * Gets the NodeSettings for the right animation scheme for the search.
	 *
	 * @return NodeSettings for the node after the animated node passes it to the right.
	 */
	public NodeSettings getAnimationSchemeRight() {
		return animationSchemeRight;
	}


	/**
	 * Gets the NodeSettings for the animator scheme for the search.
	 *
	 * @return NodeSettings for the node animating.
	 */
	public NodeSettings getAnimatorScheme() {
		return animatorScheme;
	}

	/**
	 *  Sets the KeySettings for the animator scheme key for the search.
	 *
	 * @return KeySettings for the key of the node animating.
	 */
	public KeySettings getKeyAnimatorScheme() {
		return keyAnimatorScheme;
	}

	/************************/
	/* Mutator methods     */
	/************************/


	/**
	 * Sets true if a search hit is found.
	 */
	 private void setSearchHit(boolean hit) {
		 searchHit = hit;
	 }

	/**
	 * Sets the comparable object being searched for.
	 *
	 * @param keySearch comparable object being searched for.
	 */
	 private void setKeySearch(KeyType key) {
		 keySearch = key;
	 }

	/**
	 * Gets the node currently being drawn during the Search.
	 *
	 * @return BSTTree of the key currently being search for.
	 */
	private void setKeySearchNode(GrowingTreeNode<P> node) {
		keySearchNode = node;
	}

	/**
	 * Sets the NodeSettings for the left animation scheme for the insertion. The settings affect
	 * the change the node makes after the inserted node passes it to the left.
	 *
	 * @param scheme NodeSettings for the node after the animated node passes it to the left.
	 */
	public void setAnimationSchemeLeft(NodeSettings scheme) {
		animationSchemeLeft = scheme;
	}



	/**
	 * Sets the NodeSettings for the right animation scheme for the insertion. The settings affect
	 * the change the node makes after the inserted node passes it to the right.
	 *
	 * @param scheme NodeSettings for the node after the animated node passes it to the right.
	 */
	public void setAnimationSchemeRight(NodeSettings scheme) {
		animationSchemeRight = scheme;
	}



	/**
	 * Sets the NodeSettings for the animator scheme for the insertion. The settings affect
	 * the change the node makes as it is animating during the insertion
	 *
	 * @param scheme NodeSettings for the node animating.
	 */
	public void setAnimatorScheme(NodeSettings scheme) {
		animatorScheme = scheme;
	}



	/**
	 * Sets the KeySettings for the animator scheme key for the insertion. The settings affect
	 * the change the key of the node makes as it is animating during the insertion
	 *
	 * @param scheme KeySettings for the key of the node animating.
	 */
	public void setKeyAnimatorScheme(KeySettings scheme) {
		keyAnimatorScheme = scheme;
	}

	/****************************/
	/* Insert Animation methods */
	/****************************/

	/**
	 * Add a step to the Search Animation. The step is added with only a BSTTree.When the step is performed, the search will transform
     * the node passed (Color Scheme only). The nodes are automatically added as listeners.
	 *
	 * @param node the color scheme is changed when the step is completed.
	 */
	public void add(GrowingTreeNode<P> node) {
		nodes.add(node);
		node.addAnimator(this);
		this.addAnimationListener(node);

	}



	/*********************/
	/* Animation methods */
	/*********************/


	/**
	 * Draws the animation of the next step, using the status of the animation (Animation.PLAY, Animation.PAUSE and so forth).
	 * After completing the drawing, the Animation sends an AnimationEvent to all its listeners, indicating
	 * any information that the listerners may wish to use.
	 *
	 * @param g2 the graphics to which the animation step should be drawn.
	 * @param startingStatus the status used as the starting command of animation, if needed.
	 */
	public void drawAnimation(Graphics2D g2, String startingStatus) {

		setStartingCommand(startingStatus);

		// BEGIN status
		if (getStatus().equals(Animation.BEGIN)) {
			currentLocation = 0;
			previousLocation = 0;

			if (nodes.isEmpty()) {
				setStatus(Animation.FINISH);
			}
			else {
				currentNode = (GrowingTreeNode<P>)nodes.getFirst();

				// Set transforms list
				AffineTransform currentTransform = currentNode.getCurrentTransform();
				AffineTransform enlargeTransform = (AffineTransform)currentTransform.clone();
				enlargeTransform.scale(1.05, 1.05);
				AffineTransform translateTransform = (AffineTransform)enlargeTransform.clone();


				// Make initial enlarge transforms list.
				enlargeTransforms.add(currentTransform);
				enlargeTransforms.add(enlargeTransform);
				enlargeTransforms.add(currentTransform);

				// Make initial keySearch transforms list.
				keySearchTransforms.add(AffineTransform.getScaleInstance(90.0, 70.0));
				keySearchTransforms.add((AffineTransform)enlargeTransforms.get(1));

				// Left
				if((currentNode.getKey()).compareTo(getKeySearch()) > 0) {
					translateTransform.translate(-X_MOVE_VALUE/enlargeTransform.getScaleX(), Y_MOVE_VALUE/(2*enlargeTransform.getScaleY()));
				}

				// Right
				if((currentNode.getKey()).compareTo(getKeySearch()) < 0) {
					translateTransform.translate(X_MOVE_VALUE/enlargeTransform.getScaleX(), Y_MOVE_VALUE/(2*enlargeTransform.getScaleY()));
				}

				keySearchTransforms.add(translateTransform);

				getKeySearchNode().setSettings(getAnimatorScheme());
				((DrawingKey)getKeySearchNode().getValue()).setSettings(getKeyAnimatorScheme());
				getKeySearchNode().setCurrentTransform(AffineTransform.getScaleInstance(90.0, 70.0));

				animationAction();

				// Original message
				messageAction(Animation.BEGIN + " Search for "+getKeySearch().toString());
				// set starting status
				setStatus(getStartingCommand());

				// Draw all nodes
				int size= nodes.size();
				for(int i=0; i<size; i++) {
					((GrowingTreeNode<P>)nodes.get(i)).drawNodeAndLink(g2);
				}

				FINAL_MOVE = nodes.size();
				END = FINAL_MOVE + 1;

				return;
			}

		}

		int size= nodes.size();
		// Draw all non animating nodes
		for(int i=0; i<size; i++) {
			if (nodes.get(i) == currentNode) {
				;
			}
			else {
				((GrowingTreeNode<P>)nodes.get(i)).drawNodeAndLink(g2);
			}
		}


		// Currently on a step and no changes have occured. Return to starting command
		if (getStatus().equals(Animation.STEP)) {
			setStatus(getStartingCommand());
		}

		// PLAY status
		if (getStatus().equals(Animation.PLAY)) {

			messageAction(Animation.PLAY);

			previousLocation = currentLocation;

			if(getStep()) { // Skip middle animation steps.
				currentLocation = Math.ceil(currentLocation) + getStepSize();
			}
			else { // Normal step
				currentLocation += getStepSize();
			}

			if (currentLocation < FINAL_MOVE) {
				// Finished a step in the Animation.
				if (Math.ceil(previousLocation) == Math.floor(currentLocation) && previousLocation != 0) {
					// Set Step status
					setStatus(Animation.STEP);

					// Left
					if((currentNode.getKey()).compareTo(getKeySearch()) > 0) {
						currentNode.saveLeftSettings();
						currentNode.getSettings().setNodeSettings(getAnimationSchemeLeft());
						currentNode.getSettings().setLeftSettings(getAnimationSchemeLeft());
						currentNode.drawNodeAndLeftLink();

						//messageAction("  ("+currentNode.getKey().toString()+" < " + getKeySearch().toString()+")");
						//messageAction("Search for "+getKeySearch().toString()+" proceeds left");

					}

					// Right
					if((currentNode.getKey()).compareTo(getKeySearch()) < 0) {
						currentNode.saveRightSettings();
						currentNode.getSettings().setNodeSettings(getAnimationSchemeRight());
						currentNode.getSettings().setRightSettings(getAnimationSchemeRight());
						currentNode.drawNodeAndRightLink();

						//messageAction("  ("+currentNode.getKey().toString()+" > " + getKeySearch().toString()+")");
						//messageAction("Search for "+getKeySearch().toString()+" proceeds left");

					}

					keySearchTransforms.set(0,(AffineTransform)keySearchTransforms.get(2));
					// incrememnt comparison count
					comparisonCount++;
					currentNode = ((GrowingTreeNode<P>)nodes.get((int)Math.floor(currentLocation)));

				}
				// Halfway through current animation
				else if (((currentLocation - Math.floor(currentLocation)) > .5) && ((previousLocation - Math.floor(currentLocation)) < .5)) {
					// In between two nodes.
					//messageAction("Comparison of "+getKeySearch().toString()+" & " + currentNode.getKey().toString()+":");
					if (currentNode.getKey().compareTo(getKeySearch()) == 0) {
						messageAction("Search Hit");
						setSearchHit(true);
					}
				}

				// Search found
				if (isSearchHit()) {
					// Set transforms
					AffineTransform currentTransform = currentNode.getCurrentTransform();
					AffineTransform enlargeTransform = (AffineTransform)currentTransform.clone();
					enlargeTransform.scale(1.05, 1.05);
					AffineTransform translateTransform = ((AffineTransform)enlargeTransform.clone());
					translateTransform.scale(1.4, 1.4);
					translateTransform.translate(-X_MOVE_VALUE/translateTransform.getScaleX(), Y_MOVE_VALUE/translateTransform.getScaleY());


					//AffineTransform enlargeTransformSearchHit = AffineTransform.getScaleInstance(g2.getClipBounds().getWidth() / 4.0, g2.getClipBounds().getHeight() / 4.0);

					// Set enlarge transforms
					enlargeTransforms.set(0,enlargeTransform);
					enlargeTransforms.set(1,enlargeTransform);
					enlargeTransforms.set(2,currentTransform);

					// Set key search transforms

					keySearchTransforms.set(1,(AffineTransform)enlargeTransforms.get(1));
					keySearchTransforms.set(2, translateTransform);

				}
				// Search not yet found
				else  {
					AffineTransform currentTransform = currentNode.getCurrentTransform();
					AffineTransform enlargeTransform = (AffineTransform)currentTransform.clone();
					enlargeTransform.scale(1.05, 1.05);
					AffineTransform translateTransform = (AffineTransform)enlargeTransform.clone();

					// Left
					if((currentNode.getKey()).compareTo(getKeySearch()) > 0) {
						translateTransform.translate(-X_MOVE_VALUE/enlargeTransform.getScaleX(), Y_MOVE_VALUE/enlargeTransform.getScaleY());
					}

					// Right
					if((currentNode.getKey()).compareTo(getKeySearch()) < 0) {
						translateTransform.translate(X_MOVE_VALUE/enlargeTransform.getScaleX(), Y_MOVE_VALUE/enlargeTransform.getScaleY());
					}


					enlargeTransforms.set(0,currentTransform);
					enlargeTransforms.set(1,enlargeTransform);
					enlargeTransforms.set(2,currentTransform);


					keySearchTransforms.set(1, (AffineTransform)enlargeTransforms.get(1));
					keySearchTransforms.set(2, translateTransform);

				}

				// Draw just the node without links.
				currentNode.drawNodeAndLink(g2, enlargeTransforms.getTransformStep((currentLocation - Math.floor(currentLocation)) * 2.0));
				getKeySearchNode().drawNode(g2, keySearchTransforms.getTransformStep((currentLocation - Math.floor(currentLocation)) * 2.0));


			}
			// End of animation
			else if (currentLocation < END) {
				getKeySearchNode().setCurrentTransform((AffineTransform)keySearchTransforms.get(2));
				// Found a node
				if (isSearchHit()) {
					//currentLocation += getStepSize();
					currentNode.drawNodeAndLink(g2);

					//AffineTransform enlargeTransform = AffineTransform.getScaleInstance(g2.getClipBounds().getWidth() / 4.0, g2.getClipBounds().getHeight() / 4.0);

					getKeySearchNode().drawNode(g2);

				}
				else {
					currentNode.drawNodeAndLink(g2);
					getKeySearchNode().drawNode(g2);

					drawCrossLines(g2, currentLocation);
				}

			}
			else {
				setStatus(Animation.FINISH);
			}

		}


		// REWIND status
		if (getStatus().equals(Animation.REWIND)) {

			messageAction(Animation.REWIND);

			messageAction("Cannot Rewind : Searching");
			setStatus(Animation.PAUSE);

			/*

			previousLocation = currentLocation;

			if(getStep()) { // Skip middle Animation Steps
				currentLocation = Math.floor(currentLocation) - getStepSize();
			}
			else { // Normal Step
				currentLocation -= getStepSize();
			}

			if (currentLocation < START) {
				// Set status to stop
				setStatus(Animation.PAUSE);
				currentLocation = 0;
			}
			else if (currentLocation < FINAL_MOVE) {

				currentLocation = previousLocation;



				// Finished a step in the Animation.
				if (Math.ceil(currentLocation) == Math.floor(previousLocation)) {
					currentNode = ((BSTTree)nodes.get((int)Math.floor(currentLocation)));

					// Set Step status
					setStatus(Animation.STEP);

					while (currentNode.isSettingsSaved()) {
						currentNode.restoreSettings();
					}
					currentNode.eraseNodeAndLink();
					currentNode.drawNodeAndLink();
					comparisonCount--;


				}
				// Halfway through animation
				else if (((currentLocation - Math.floor(currentLocation)) < .5) && ((previousLocation - Math.floor(currentLocation)) > .5)) {
					// In between two nodes.
					if (currentNode.getKey().compareTo(getKeySearch()) == 0) {
						setSearchHit(false);
					}
				}

				// Search found
				if (isSearchHit()) {
					messageAction("Cannot Rewind : Search Hit");
					setStatus(Animation.PAUSE);
					currentLocation = previousLocation;
				}
				// Search not yet found
				else  {
					AffineTransform currentTransform = currentNode.getCurrentTransform();
					AffineTransform enlargeTransform = (AffineTransform)currentTransform.clone();
					enlargeTransform.scale(1.05, 1.05);
					AffineTransform translateTransform = (AffineTransform)enlargeTransform.clone();

					// Left
					if((currentNode.getKey()).compareTo(getKeySearch()) > 0) {
						translateTransform.translate(-X_MOVE_VALUE/enlargeTransform.getScaleX(), Y_MOVE_VALUE/enlargeTransform.getScaleY());
					}

					// Right
					if((currentNode.getKey()).compareTo(getKeySearch()) < 0) {
						translateTransform.translate(X_MOVE_VALUE/enlargeTransform.getScaleX(), Y_MOVE_VALUE/enlargeTransform.getScaleY());
					}

					enlargeTransforms.set(0,currentTransform);
					enlargeTransforms.set(1,enlargeTransform);
					enlargeTransforms.set(2,currentTransform);


					keySearchTransforms.set(1, (AffineTransform)enlargeTransforms.get(1));
					keySearchTransforms.set(2, translateTransform);

					AffineTransform parentTransform = ((BSTTree)currentNode.getParentTree()).getCurrentTransform();
					AffineTransform parEnlargeTransform = (AffineTransform)parentTransform.clone();
					enlargeTransform.scale(1.05, 1.05);
					AffineTransform previousTransform = (AffineTransform)parEnlargeTransform.clone();

					// Left
					if(currentNode == ((BSTTree)currentNode.getParentTree()).getLeftTree()) {
						previousTransform.translate(-X_MOVE_VALUE/parEnlargeTransform.getScaleX(), Y_MOVE_VALUE/parEnlargeTransform.getScaleY());
					}
					else {
						previousTransform.translate(X_MOVE_VALUE/parEnlargeTransform.getScaleX(), Y_MOVE_VALUE/parEnlargeTransform.getScaleY());
					}

					keySearchTransforms.set(0, previousTransform);

				}

				// Draw just the node without links.
				currentNode.drawNodeAndLink(g2, enlargeTransforms.getTransformStep((currentLocation - Math.floor(currentLocation)) * 2.0));
				getKeySearchNode().drawNode(g2, keySearchTransforms.getTransformStep((currentLocation - Math.floor(currentLocation)) * 2.0));


			}
			else {
				if (isSearchHit()) {
					messageAction("Cannot Rewind : Search Hit");
					setStatus(Animation.PAUSE);
					currentLocation = previousLocation;
				}
				else {
					messageAction("Cannot Rewind : Search Miss");
					setStatus(Animation.PAUSE);
					currentLocation = previousLocation;
				}

			}*/

		}

		// PAUSE status
		if (getStatus().equals(Animation.PAUSE)) {
			messageAction(Animation.PAUSE);

			if (currentLocation < FINAL_MOVE) {
				// Draw just the node without links.
				currentNode.drawNodeAndLink(g2, enlargeTransforms.getTransformStep((currentLocation - Math.floor(currentLocation)) * 2.0));
				getKeySearchNode().drawNode(g2, keySearchTransforms.getTransformStep((currentLocation - Math.floor(currentLocation)) * 2.0));

			}
			else {
				// Search hit
				if (isSearchHit()) {
					currentNode.drawNodeAndLink(g2);

					AffineTransform enlargeTransform = AffineTransform.getScaleInstance(g2.getClipBounds().getWidth() / 2.0, g2.getClipBounds().getHeight() / 2.0);

					getKeySearchNode().drawNode(g2, enlargeTransform);
				}
				// Search miss
				else {

					currentNode.drawNodeAndLink(g2);

					getKeySearchNode().drawNode(g2);

					drawCrossLines(g2, currentLocation);
				}

			}



		}

		// STOP status
		if (getStatus().equals(Animation.STOP)) {
			messageAction(Animation.STOP);
			if (currentLocation < FINAL_MOVE) {

			}
			else {
				currentNode.drawNodeAndLink(g2);
			}
		}


		// FINISH status
		if (getStatus().equals(Animation.FINISH)) {

			NumberFormat nf = NumberFormat.getNumberInstance();
			nf.setMaximumFractionDigits(3);

			messageAction(Animation.FINISH);
			if (isSearchHit()) {
				messageAction("*--------Search of "+getKeySearch().toString()+"--------*\nKey Found\nComparisons: "+
								comparisonCount);
			}
			else {
				messageAction("*--------Search of "+getKeySearch().toString()+"--------*\nKey Not Found\nComparisons: "+
								comparisonCount);
			}
			animationAction();
			restore();
			return;
		}

		// Call listeners
		animationAction();

	}

	/**
	 * Restores the settings of all nodes encountered during the animation. Usually called at
	 * the end of the animation (Animation.FINISH) to restore all settings changed throughout
	 * the animation. This also restores the animator node.
	 */
	private void restore() {
		//int size = nodes.size();

		for(int i=0; i < nodes.size(); i++) {
			GrowingTreeNode<P> currentNode = ((GrowingTreeNode<P>)nodes.get(i));
			while (currentNode.isSettingsSaved()) {
				currentNode.restoreSettings();
			}

		}

	}


	/**
	 * Draws two crossed lines according to the current location within the graphics.
	 *
	 * @param g2 Graphics2D to which the line is drawn.
	 * @param location the double location of progress in the animation.
	 */
	private void drawCrossLines(Graphics2D g2, double currentLocation) {

		double distance = (currentLocation-FINAL_MOVE);

		BasicStroke line = new BasicStroke(5.0f);
		// Set graphics information
		g2.setComposite(getAnimationSchemeLeft().getNodeComposite());
		g2.setStroke(line);

		if (distance < .5) {

			// Makes the left dotted line
			Line2D.Double crossLeft = new Line2D.Double(
		    	(getKeySearchNode().getCurrentTransform().getTranslateX()) ,
		 		(getKeySearchNode().getCurrentTransform().getTranslateY()) ,
				((getKeySearchNode().getCurrentTransform().getTranslateX()) + (distance*2.0) * (getKeySearchNode().getCurrentTransform().getScaleX())) ,
				((getKeySearchNode().getCurrentTransform().getTranslateY()) + (distance*2.0) * (getKeySearchNode().getCurrentTransform().getScaleY()))
			);


			g2.setPaint(Color.red);
			g2.draw(crossLeft);
		}
		else {

			distance -= .5;

			// Makes the left dotted line
			Line2D.Double crossLeft = new Line2D.Double(
		    	(getKeySearchNode().getCurrentTransform().getTranslateX()) ,
		 		(getKeySearchNode().getCurrentTransform().getTranslateY()) ,
				((getKeySearchNode().getCurrentTransform().getTranslateX()) + (getKeySearchNode().getCurrentTransform().getScaleX())) ,
				((getKeySearchNode().getCurrentTransform().getTranslateY()) + (getKeySearchNode().getCurrentTransform().getScaleY()))
			);


			g2.setPaint(Color.red);
			g2.draw(crossLeft);

			// Makes the right dotted line
			Line2D.Double crossRight = new Line2D.Double(
				((getKeySearchNode().getCurrentTransform().getTranslateX()) + (getKeySearchNode().getCurrentTransform().getScaleX())) ,
				(getKeySearchNode().getCurrentTransform().getTranslateY()) ,
				((getKeySearchNode().getCurrentTransform().getTranslateX()) + (1 - distance * 2.0) * (getKeySearchNode().getCurrentTransform().getScaleX())) ,
				((getKeySearchNode().getCurrentTransform().getTranslateY()) + (distance * 2.0) * (getKeySearchNode().getCurrentTransform().getScaleY()))
			);

			g2.setPaint(Color.red);
			g2.draw(crossRight);
		}
	}


	/**
	 * Calls all of the listeners of the current Animation and passed information regarding the
	 * progress and status of the current Animation. Additionally, the id of the type of animation is
	 * passed. Within, the <code>animationEventPerformed</code> method is called.
	 *
	 * @param cmd String Animation command passed instead of the current Status.
	 * @param description String description for messages.
	 */
	protected void animationAction(String cmd, String description) {
		super.animationAction(AnimationEvent.SEARCH_BST_ANIMATION, cmd, description, currentLocation / (double)nodes.size());
	}




}