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

 import java.util.*;
 import java.awt.*;
import java.awt.geom.*;


/** *
 	* 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.
	*
	* @author  Corey Sanders
	* @version 1.3 9/15/01
 	*/
public class TraverseBSTAnimation<P extends NodeProperties> extends AbstractAnimation {



	/**
	 * 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 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;

	/**
	 * Private int to hold the last step of the traversal.
	 */
	private int lastStep;


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

	/**
	 * 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;


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



	/**
	 * The constructor which initiates the status and prepares the colorSchemes. The node
	 * which is animating must be passed.
	 * @param AnimatorScheme the <code>NodeSettings</code> associated with a color scheme for a passed node.
	 * @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 TraverseBSTAnimation(NodeSettings AnimatorScheme, KeySettings KeyAnimatorScheme, String startingCmd, int stepTime) {
		super();

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

		if (KeyAnimatorScheme == null) {
			KeyAnimatorScheme = new KeySettings();
		}
		// init enlargeTransforms
		enlargeTransforms = new AffineTransformList();

		// init nodes
		nodes = new LinkedList<GrowingTreeNode<P>>();


		// Set Animation Schemes
		setAnimatorScheme((NodeSettings)AnimatorScheme.clone());
		setKeyAnimatorScheme((KeySettings)KeyAnimatorScheme.clone());

		// Set the drawing node.
		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.
	 */
	public TraverseBSTAnimation() {
		this(null , null ,Animation.PLAY, DEFAULT_STEP);
	}


	/************************/
	/* Accessor methods     */
	/************************/


	/**
	 * 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 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 Traversal Animation.  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 = nodes.getFirst();

				// Set transforms list
				AffineTransform currentTransform = currentNode.getCurrentTransform();
				AffineTransform enlargeScreenTransform = AffineTransform.getScaleInstance(g2.getClipBounds().getWidth() / 8.0, g2.getClipBounds().getHeight() / 8.0);


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

				animationAction();

				// Original message
				messageAction(Animation.BEGIN + " traversal.");
				// set starting status
				setStatus(getStartingCommand());

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

				FINAL_MOVE = nodes.size() * 2;
				END = FINAL_MOVE + 2;

				messageAction(currentNode.getKey().toString()+" visited.");

				return;
			}

		}

		// 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 (((currentLocation) >= (lastStep+2)) && previousLocation != 0) {
					// Set Step status
					setStatus(Animation.STEP);

					//animator scheme exists
					currentNode.saveSettings();
					currentNode.setNodeSettings(getAnimatorScheme());

					((DrawingKey)currentNode.getValue()).saveSettings();
					((DrawingKey)currentNode.getValue()).setKeySettings(getKeyAnimatorScheme());

					currentNode = (nodes.get((int)(Math.floor(currentLocation) / 2.0)) );
					lastStep += 2;

					messageAction(currentNode.getKey().toString()+" visited.");

				}

				// Set transforms list
				AffineTransform currentTransform = currentNode.getCurrentTransform();
				AffineTransform enlargeScreenTransform = AffineTransform.getScaleInstance(g2.getClipBounds().getWidth() / 8.0, g2.getClipBounds().getHeight() / 8.0);

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



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

				// Draw just the node without links.
				currentNode.drawNodeAndLink(g2, enlargeTransforms.getTransformStep(currentLocation - lastStep));

			}
			// End of animation
			else if (currentLocation < END) {

				if (previousLocation < FINAL_MOVE) {
					//animator scheme exists
					currentNode.saveSettings();
					currentNode.setNodeSettings(getAnimatorScheme());

					((DrawingKey)currentNode.getValue()).saveSettings();
					((DrawingKey)currentNode.getValue()).setKeySettings(getKeyAnimatorScheme());

				}

				if (currentLocation >= (FINAL_MOVE + 1)) {
					restore();
				}

				currentLocation += (getStepSize());

				int size= nodes.size();
				// Draw all non animating nodes
				for(int i=0; i<size; i++) {
					AffineTransform originalTransform = nodes.get(i).getCurrentTransform();
					AffineTransform enlargeFinishTransform = (AffineTransform)originalTransform.clone();
					enlargeFinishTransform.scale(1.1, 1.1);

					// Set enlarge transforms list.
					enlargeTransforms.set(0,originalTransform);
					enlargeTransforms.set(1,enlargeFinishTransform);
					enlargeTransforms.set(2,originalTransform);

					nodes.get(i).drawNodeAndLink(g2, enlargeTransforms.getTransformStep(currentLocation - FINAL_MOVE) );

				}
			}
			else {
				setStatus(Animation.FINISH);
			}
		}


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

			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 = START;
			}

			if (currentLocation < FINAL_MOVE) {
				if (previousLocation >= FINAL_MOVE) {
					messageAction("Cannot Rewind : Traversal Complete");
					setStatus(Animation.PAUSE);
					currentLocation = previousLocation;
				}


				// Finished a step in the Animation.
				if ((currentLocation) < (lastStep)) {
					// Set Step status
					setStatus(Animation.STEP);

					currentNode = ((GrowingTreeNode<P>)nodes.get((int)(Math.ceil(currentLocation) / 2.0) - 1) );
					lastStep -= 2;

					//animator scheme exists
					while (currentNode.isSettingsSaved()) {
						currentNode.restoreSettings();
					}

					while (((DrawableKey)currentNode.getValue()).isSettingsSaved()) {
						((DrawableKey)currentNode.getValue()).restoreSettings();
					}

				}

				// Set transforms list
				AffineTransform currentTransform = currentNode.getCurrentTransform();
				AffineTransform enlargeScreenTransform = AffineTransform.getScaleInstance(g2.getClipBounds().getWidth() / 8.0, g2.getClipBounds().getHeight() / 8.0);

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



				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);
					}
				}

				// Draw just the node without links.
				currentNode.drawNodeAndLink(g2, enlargeTransforms.getTransformStep(currentLocation - lastStep));

			}
			// End of animation
			else if (currentLocation < END) {

				int size= nodes.size();
				// Draw all non animating nodes
				for(int i=0; i<size; i++) {
					AffineTransform originalTransform = (((GrowingTreeNode<P>)nodes.get(i)).getCurrentTransform());
					AffineTransform enlargeFinishTransform = (AffineTransform)originalTransform.clone();
					enlargeFinishTransform.scale(1.1, 1.1);

					// Set enlarge transforms list.
					enlargeTransforms.set(0,originalTransform);
					enlargeTransforms.set(1,enlargeFinishTransform);
					enlargeTransforms.set(2,originalTransform);

					((GrowingTreeNode<P>)nodes.get(i)).drawNodeAndLink(g2, enlargeTransforms.getTransformStep(currentLocation - FINAL_MOVE) );

				}
			}


		}

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

			if (currentLocation < FINAL_MOVE) {
				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);
					}
				}

				// Draw just the node without links.
				currentNode.drawNodeAndLink(g2, enlargeTransforms.getTransformStep(currentLocation - lastStep));


			}
			// End of animation
			else {

				int size= nodes.size();
				// Draw all non animating nodes
				for(int i=0; i<size; i++) {
					AffineTransform originalTransform = (((GrowingTreeNode<P>)nodes.get(i)).getCurrentTransform());
					AffineTransform enlargeFinishTransform = (AffineTransform)originalTransform.clone();
					enlargeFinishTransform.scale(2.5, 2.5);

					// Set enlarge transforms list.
					enlargeTransforms.set(0,originalTransform);
					enlargeTransforms.set(1,enlargeFinishTransform);
					enlargeTransforms.set(2,originalTransform);

					((GrowingTreeNode<P>)nodes.get(i)).drawNodeAndLink(g2, enlargeTransforms.getTransformStep(currentLocation - FINAL_MOVE) );

				}
			}




		}

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

			if (currentLocation < FINAL_MOVE) {
				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);
					}
				}
			}
			// End of animation
			else {

				int size= nodes.size();
				// Draw all non animating nodes
				for(int i=0; i<size; i++) {
					AffineTransform originalTransform = (((GrowingTreeNode<P>)nodes.get(i)).getCurrentTransform());
					AffineTransform enlargeFinishTransform = (AffineTransform)originalTransform.clone();
					enlargeFinishTransform.scale(2.5, 2.5);

					// Set enlarge transforms list.
					enlargeTransforms.set(0,originalTransform);
					enlargeTransforms.set(1,enlargeFinishTransform);
					enlargeTransforms.set(2,originalTransform);

					((GrowingTreeNode<P>)nodes.get(i)).drawNodeAndLink(g2, enlargeTransforms.getTransformStep(currentLocation - FINAL_MOVE) );

				}
			}


		}


		// FINISH status
		if (getStatus().equals(Animation.FINISH)) {
			restore();
			messageAction(Animation.FINISH);
			messageAction("*--------Traversal of Tree--------*");

			animationAction();
			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();
			}

			while (((DrawableKey)currentNode.getValue()).isSettingsSaved()) {
				((DrawableKey)currentNode.getValue()).restoreSettings();
			}
		}

	}


	/**
	 * 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.TRAVERSE_BST_ANIMATION, cmd, description, currentLocation / (double)nodes.size());
	}




}