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

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


/** *
 	* The Animation object that defines the Insertion into a BSTTree. Two constructors exist,
 	* one setting the animator and animation color Schemes. The addition of nodes that the Animation
 	* must pass include both the AffineTransform and then BSTTree or either separately. <p>
	*
	* @author  Corey Sanders
	* @version 2.2 9/15/01
 	*/

public class InsertBSTAnimation<P extends NodeProperties> extends AbstractAnimation {

	/**
	 * Previous and next node indeces
	 */
	 protected int previousNodeIndex = 0;
	 protected int nextNodeIndex = 0;

	/**
	 * 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 draw the animation.
	 */
	private AffineTransformList movements = new AffineTransformList();

	/**
	 * 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>> nodeMovements = new LinkedList<GrowingTreeNode<P>>();

	/**
	 * Holds the node that is doing the drawing.
	 */
	private GrowingTreeNode<P> insertNode;

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

	/**
	 * Counts the initial insertion size of the tree.
	 */
	protected int insertionSize = 0;
	

	/**
	 * The constructor which initiates the status and prepares the colorSchemes. The node
	 * which is animating must be passed. The first step added is the identity step.
	 *
	 * @param node the BSTTree which is animated during the animation.
	 * @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 AnimatorScheme the <code>NodeSettings</code> associated with a color scheme according to NodeSettings.
	 * @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 InsertBSTAnimation(GrowingTreeNode<P> node, 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();
		}


		// Add identity
		movements.add(new AffineTransform());
		// Add null first node
		nodeMovements.add(null);

		// Set insertion size.
		insertionSize = node.getHead().size();



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

		// Set the drawing node.
		setInsertNode(node);
		setStartingCommand(startingCmd);
		setStepTime(stepTime);
	}

	/**
	 * The constructor which initiates the status and sets the colorSchemes to null. No colors
	 * will be change using this animation. The node
	 * which is animating must be passed. The first step added is the identity step.
	 *
	 * @param node the BSTTree which is animated during the animation.
	 */
	public InsertBSTAnimation(GrowingTreeNode<P> node) {
		this(node, null, null, null , null , Animation.PLAY, DEFAULT_STEP);
	}


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

	/**
	 * Gets the current location of the Insertion.
	 *
	 * @return double of the current location  of the ndoe currently being inserted and animated.
	 */
	protected double getCurrentLocation() {
		return currentLocation;
	}


	/**
	 * Gets the previous location of the Insertion.
	 *
	 * @return double of the previous location  of the ndoe currently being inserted and animated.
	 */
	protected double getPreviousLocation() {
		return previousLocation;
	}

	/**
	 * Gets the nodes of the Insertion.
	 *
	 * @return LinkedList of the nodes.
	 */
	protected LinkedList<GrowingTreeNode<P>> getNodeMovements() {
		return nodeMovements;
	}

	/**
	 * Gets the affine transform movements of the Insertion.
	 *
	 * @return AffineTransformList of  the affine transform movements.
	 */
	protected AffineTransformList getMovements() {
		return movements;
	}

	/**
	 * Gets the node currently being drawn during the Insertion.
	 *
	 * @return BSTTree of the ndoe currently being inserted and animated.
	 */
	protected GrowingTreeNode<P> getInsertNode() {
		return insertNode;
	}

	/**
	 * Gets the NodeSettings for the left animation scheme for the insertion.
	 *
	 * @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 insertion.
	 *
	 * @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 insertion.
	 *
	 * @return NodeSettings for the node animating.
	 */
	public NodeSettings getAnimatorScheme() {
		return animatorScheme;
	}

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

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


	/**
	 * Sets the current location of the Insertion.
	 *
	 * @return currentLocation double of the current location  of the ndoe currently being inserted and animated.
	 */
	protected void setCurrentLocation(double currentLocation) {
		this.currentLocation = currentLocation;
	}


	/**
	 * Sets the previous location of the Insertion.
	 *
	 * @param previousLocation double of the previous location  of the ndoe currently being inserted and animated.
	 */
	protected void setPreviousLocation(double previousLocation) {
		this.previousLocation = previousLocation;
	}

	/**
	 * Sets the node currently being drawn during the Insertion.
	 *
	 * @param GrowingTreeNode of the node currently being inserted and animated.
	 */
	protected void setInsertNode(GrowingTreeNode<P> node) {
		insertNode = 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 InsertAnimation. The step is added with only an AffineTransform,
	 * which is used to draw that step in the Animation. No node will be affected, even
	 * if the transform comes from a node.
	 *
	 * @param a AffineTransform to be drawn in the following step.
	 */
	public void add(AffineTransform a) {
		this.add(a, null);
	}

	/**
	 * Add a step to the InsertAnimation. The step is added with an AffineTransform and a BSTTree
	 * node. Consequently, when the step is performed, the node will transform to the given AffineTransform,
	 * and the node passed will be modified (Color Scheme only).
	 *
	 * @param a AffineTransform to be drawn in the following step.
	 * @param node the color scheme is changed when the step is completed.
	 */
	public void add(AffineTransform a, GrowingTreeNode<P> node) {
		movements.add(a);
		nodeMovements.add(node);
	}

	/**
	 * Add a step to the InsertAnimation. The step is added with only a BSTTree which is used to determine
	 * the AffineTransform for the current step.W hen the step is performed, the node will transform to the passed node's AffineTransform,
	 * and the node passed will be modified (Color Scheme only).
	 *
	 * @param node the color scheme is changed when the step is completed.
	 */
	public void add(GrowingTreeNode<P> node) {
		this.add(node.getCurrentTransform(), 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;

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

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


			animationAction();

			messageAction(Animation.BEGIN + " Insertion of "+insertNode.getKey().toString());
			
			// set starting status
			setStatus(getStartingCommand());

			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();
			}
			// Set node positions.
			nextNodeIndex = (int)Math.ceil(currentLocation);
			previousNodeIndex = (int)Math.floor(currentLocation);

			// Completed Animation
			if (currentLocation >= (movements.size()-1)) {
				setStatus(Animation.FINISH);
				drawAnimation(g2, getStartingCommand());
				return;
			}

			// Finished a step in the Animation.
			if (Math.ceil(previousLocation) == Math.floor(currentLocation) && previousLocation != 0) {

				setStatus(Animation.STEP);


				GrowingTreeNode<P> previousNode = ((GrowingTreeNode<P>)nodeMovements.get(previousNodeIndex));
				GrowingTreeNode<P> nextNode = ((GrowingTreeNode<P>)nodeMovements.get(nextNodeIndex));

				// In between two nodes.
				if ((previousNode != null) && nextNode != null) {
					//messageAction("Comparison of "+insertNode.getKey().toString()+" & " + previousNode.getKey().toString()+":");

					// Left
					if(previousNode.getLeftNodeInternal() == nextNode) {
						previousNode.saveLeftSettings();
						previousNode.getSettings().setNodeSettings(getAnimationSchemeLeft());
						previousNode.getSettings().setLeftSettings(getAnimationSchemeLeft());
						previousNode.drawNodeAndLeftLink();
						//messageAction("  ("+insertNode.getKey().toString()+" < " + previousNode.getKey().toString()+")");
						//messageAction(insertNode.getKey().toString()+" proceeds to the left");

					}

					// Right
					if(previousNode.getRightNodeInternal() == nextNode) {
						previousNode.saveRightSettings();
						previousNode.getSettings().setNodeSettings(getAnimationSchemeLeft());
						previousNode.getSettings().setRightSettings(getAnimationSchemeRight());
						previousNode.drawNodeAndRightLink();
						//messageAction("  ("+insertNode.getKey().toString()+" > " + previousNode.getKey().toString()+")");
						//messageAction(insertNode.getKey().toString()+" proceeds to the right");
					}

					comparisonCount++;
				}
			}
		}

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

			nextNodeIndex = (int)Math.ceil(currentLocation);
			previousNodeIndex = (int)Math.floor(currentLocation);

			// Beginning of Animation
			if (currentLocation <= 0) {
				setStatus(Animation.PAUSE);
				currentLocation = 0;
				animationAction();
				return;
			}

			// Finished a step in the Animation.
			if (Math.floor(previousLocation) == Math.ceil(currentLocation)) {

				setStatus(Animation.STEP);

				// Node after nextNode.
				GrowingTreeNode<P> nextFollowingNode = ((GrowingTreeNode<P>)nodeMovements.get(nextNodeIndex+1));
				// Next node.
				GrowingTreeNode<P> nextNode = ((GrowingTreeNode<P>)nodeMovements.get(nextNodeIndex));

				// The next two nodes exist
				if ((nextNode != null) && (nextFollowingNode != null)) {
					// Left
					if(nextNode.getLeftNodeInternal() == nextFollowingNode) {
						nextNode.restoreLeftSettings();
					}
					// Right
					if(nextNode.getRightNodeInternal() == nextFollowingNode) {
						nextNode.restoreRightSettings();
					}
					nextNode.eraseNodeAndLink();
					nextNode.drawNodeAndLink();
					comparisonCount--;
				}
			}
		}

		// PAUSE status
		if (getStatus().equals(Animation.PAUSE)) {
			nextNodeIndex = (int)Math.ceil(currentLocation);
			previousNodeIndex = (int)Math.floor(currentLocation);
			messageAction(Animation.PAUSE);

		}

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


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

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

			messageAction(Animation.FINISH);
			messageAction("*--------Insertion of "+insertNode.getKey().toString()+"--------*\n Comparisons: "+
								comparisonCount);

			animationAction();
			restore();
			insertNode.getHead().popTreeProperties();

			return;
		}


		// Set movements
		movements.set(previousNodeIndex, resetPosition(previousNodeIndex));
		movements.set(nextNodeIndex, resetPosition(nextNodeIndex));

		// Draw just the node without links.
		insertNode.drawNode(g2, movements.getTransformStep(currentLocation));

		// 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.
	 */
	protected void restore() {

 		for(int i=0; (i+1) < nodeMovements.size(); i++) {
        	if((nodeMovements.get(i) != null)) {
            	GrowingTreeNode<P> thisNode = ((GrowingTreeNode<P>)nodeMovements.get(i));
            	GrowingTreeNode<P> nextNode = ((GrowingTreeNode<P>)nodeMovements.get(i+1));

				if (thisNode.isSettingsSaved()) {

					if(thisNode.getLeftNodeInternal() == nextNode) {
						thisNode.restoreLeftSettings();
						thisNode.drawNodeAndLeftLink();
					}
					if(thisNode.getRightNodeInternal() == nextNode) {
						thisNode.restoreRightSettings();
						thisNode.drawNodeAndRightLink();
					}
				}
				if (((DrawableKey)thisNode.getValue()).isSettingsSaved()) {
					((DrawableKey)thisNode.getValue()).restoreSettings();
				}

			}
		}


		GrowingTreeNode<P> thisNode = (GrowingTreeNode<P>)nodeMovements.getLast();

		if (thisNode.isSettingsSaved()) {
			thisNode.restoreSettings();
		}
		if  (((DrawableKey)thisNode.getValue()).isSettingsSaved()) {
			((DrawableKey)thisNode.getValue()).restoreSettings();
		}
	}


	/**
	 * Returns the AffineTransform after resetting the transform based upon the node's position.
	 * The node Index calls the node list to get the node for that index. If no node is present,
	 * then the AffineTransform previously declared for the nodeIndex is returned. Otherwise, the
	 * AffineTransform associated with the node is returned.
	 *
	 * @param nodeIndex index for the resetting AffineTransform.
	 * @return AffineTransform for the nodeIndex.
	 */
	protected AffineTransform resetPosition(int nodeIndex) {
		if (nodeMovements.get(nodeIndex) == null)
			return (AffineTransform)movements.get(nodeIndex);
		else
			return ((GrowingTreeNode<P>)nodeMovements.get(nodeIndex)).getCurrentTransform();
	}


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

}