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

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


/** *
 	* The Animation object that defines a selection within 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.4 9/15/01
 	*/

public class SelectionBSTAnimation<P extends NodeProperties> extends AbstractAnimation {


	public static final float ENLARGE_SIZE = 1.4F;

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

	/**
	 * Defines the final node location.
	 */
	private int FINAL_NODE;
	/**
	 * Defines the end location.
	 */
	protected 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.
	 */
	protected 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 linked list which will store the node of each step, used to draw the
	 * pass of each node.
	 */
	protected LinkedList<GrowingTreeNode<P>> nodes;

	/**
	 * Holds the node that is doing the drawing.
	 */
	private int elementCount;

	/**
	 * Holds the original element count.
	 */
	private int originalElementCount;

	/**
	 * Current Animating Node.
	 */
	private GrowingTreeNode<P> currentNode;

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


	/**
	 * 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 elementCount the integer count of the kth element being partitioned.
	 * @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 SelectionBSTAnimation(int elementCount, 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();
		}

		enlargeTransforms = new AffineTransformList();
		nodes = new LinkedList<GrowingTreeNode<P>>();


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


		// 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.
	 *
	 * @param elementCount the integer count of the kth element being partitioned.
	 */
	public SelectionBSTAnimation(int elementCount) {
		this(elementCount, null, null, null , null , Animation.PLAY, DEFAULT_STEP);
	}


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


	/**
	 * Gets the element count (kth element being partition).
	 *
	 * @return elementCount count of kth element being partitioned.
	 */
	 public int getElementCount() {
		 return elementCount;
	 }

	/**
	 * 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 the element count (kth element being partition).
	 *
	 * @param elementCount count of kth element being partitioned.
	 */
	 public void setElementCount(int elementCount) {
		 this.elementCount = elementCount;
	 }

	/**
	 * 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).
	 *
	 * @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;

			// Empty nodes, set to finish.
			if (nodes.isEmpty()) {
				setStatus(Animation.FINISH);
			}
			else {
				// Set current node
				currentNode = (GrowingTreeNode<P>)nodes.getFirst();
				// Set originalElementCount
				originalElementCount = getElementCount();

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

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

				animationAction();

				messageAction(Animation.BEGIN + " Selection for "+getElementCount()+"th smallest from "+currentNode.getKey().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);
				}

				// Set location flags
				FINAL_NODE = nodes.size();
				END = FINAL_NODE+1;

				return;
			}

		}

		if (!getStatus().equals(Animation.FINISH)) {
			
			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.
				if (currentLocation == 0) {
					currentLocation += getStepSize();
					previousLocation = currentLocation;
				}
				currentLocation = Math.ceil(currentLocation) + getStepSize();

			}
			else { // Normal step
				currentLocation += getStepSize();
			}
			// Still selecting
			if (currentLocation < FINAL_NODE) {
				// Finished a step in the Animation.
				if (Math.ceil(previousLocation) == Math.floor(currentLocation) && previousLocation != 0) {
					// Set Step status
					setStatus(Animation.STEP);

					GrowingTreeNode<P> nextNode = ((GrowingTreeNode<P>)nodes.get((int)Math.floor(currentLocation)));

					messageAction("Size of "+currentNode.getKey().toString()+" left tree : " + currentNode.getLeftNodeInternal().size());

					// Left
					if(currentNode.getLeftNodeInternal() == nextNode ) {
						currentNode.saveLeftSettings();
						currentNode.getSettings().setNodeSettings(getAnimationSchemeLeft());
						currentNode.getSettings().setLeftSettings(getAnimationSchemeLeft());
						//currentNode.drawNodeAndLeftLink();
						messageAction("    ("+getElementCount()+" < "+currentNode.getLeftNodeInternal().size()+" ) ");
						messageAction("Selection for "+getElementCount()+"th element proceeds left");
					}

					// Right
					if(currentNode.getRightNodeInternal() == nextNode ) {
						currentNode.saveRightSettings();
						currentNode.getSettings().setNodeSettings(getAnimationSchemeRight());
						currentNode.getSettings().setRightSettings(getAnimationSchemeRight());
						//currentNode.drawNodeAndRightLink();
						messageAction("   ("+getElementCount()+" > "+currentNode.getLeftNodeInternal().size()+" ) ");
						messageAction("Selection for "+getElementCount()+"th element proceeds right");
						setElementCount(getElementCount() - currentNode.getLeftNodeInternal().size() - 1);
					}
					// Next node set
					currentNode = nextNode;

					//messageAction("Selection continues with "+currentNode.getKey().toString()+",\n looking for its "+getElementCount()+"th element ");

				}

				// The beginning node of the selection, if the selection is not of that node.
				if (currentNode == nodes.getFirst() && (nodes.size() > 1)) {
					AffineTransform currentTransform = currentNode.getCurrentTransform();
					AffineTransform enlargeFirstNode = (AffineTransform)currentTransform.clone();
					enlargeFirstNode.scale(ENLARGE_SIZE, ENLARGE_SIZE);

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

					currentNode.drawNodeAndLink(g2);
					currentNode.drawNode(g2, enlargeTransforms.getTransformStep((currentLocation - Math.floor(currentLocation)) * 2.0));
				}
				// If the selection is at the final node
				else if (currentNode == nodes.getLast()) {
					AffineTransform currentTransform = currentNode.getCurrentTransform();
					AffineTransform enlargeLastNode = (AffineTransform)currentTransform.clone();
					enlargeLastNode.scale(ENLARGE_SIZE, ENLARGE_SIZE);

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

					currentNode.drawNodeAndLink(g2);
					currentNode.drawNode(g2, enlargeTransforms.getTransformStep((currentLocation - Math.floor(currentLocation)) * 2.0));

				}
				// In the middle of the selection
				else {
					AffineTransform currentTransform = currentNode.getCurrentTransform();
					AffineTransform enlargeTransform = (AffineTransform)currentTransform.clone();
					enlargeTransform.scale(ENLARGE_SIZE, ENLARGE_SIZE);

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

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

				}

			}
			// Final animation
			else if (currentLocation < END) {
				// Draw the node
				currentNode.drawNodeAndLink(g2);
				// Save
				currentNode.saveSettings();
				((DrawableKey)currentNode.getValue()).saveSettings();
				// Set setttings
				currentNode.setNodeSettings(getAnimatorScheme());
				((DrawableKey)currentNode.getValue()).setKeySettings(getKeyAnimatorScheme());
				// Draw the node large
				AffineTransform currentTransform = currentNode.getCurrentTransform();
				AffineTransform enlargeLastNode = (AffineTransform)currentTransform.clone();
				enlargeLastNode.scale(ENLARGE_SIZE, ENLARGE_SIZE);

				currentNode.drawNode(g2, enlargeLastNode);
				// Restore
				currentNode.restoreSettings();
				((DrawableKey)currentNode.getValue()).restoreSettings();

			}
			// Finally, FINISH
			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 = 0;
			}
			if (currentLocation < FINAL_NODE) {

				if (previousLocation >= END) {
					currentNode.restoreSettings();
					((DrawableKey)currentNode.getValue()).restoreSettings();
				}

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

					GrowingTreeNode<P> nextNode = ((GrowingTreeNode<P>)nodes.get((int)Math.floor(currentLocation)));
					// Restore settings
					while (nextNode.isSettingsSaved()) {
						nextNode.restoreSettings();
					}
					//nextNode.eraseNodeAndLink();
					//nextNode.drawNodeAndLink();

					if(nextNode.getRightNodeInternal() == currentNode ) {
						setElementCount(getElementCount() + nextNode.getLeftNodeInternal().size() + 1);
					}

					currentNode = nextNode;
				}
				// The beginning node of the selection, if the selection is not of that node.
				if (currentNode == nodes.getFirst()) {
					AffineTransform currentTransform = currentNode.getCurrentTransform();
					AffineTransform enlargeFirstNode = (AffineTransform)currentTransform.clone();
					enlargeFirstNode.scale(ENLARGE_SIZE, ENLARGE_SIZE);

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

					currentNode.drawNodeAndLink(g2);
					currentNode.drawNode(g2, enlargeTransforms.getTransformStep((currentLocation - Math.floor(currentLocation)) * 2.0));
				}
				// If the selection is at the final node
				else if (currentNode == nodes.getLast()) {
					AffineTransform currentTransform = currentNode.getCurrentTransform();
					AffineTransform enlargeLastNode = (AffineTransform)currentTransform.clone();
					enlargeLastNode.scale(ENLARGE_SIZE, ENLARGE_SIZE);

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

					currentNode.drawNodeAndLink(g2);
					currentNode.drawNode(g2, enlargeTransforms.getTransformStep((currentLocation - Math.floor(currentLocation)) * 2.0));

				}
				// In the middle of the selection
				else {
					AffineTransform currentTransform = currentNode.getCurrentTransform();
					AffineTransform enlargeTransform = (AffineTransform)currentTransform.clone();
					enlargeTransform.scale(ENLARGE_SIZE, ENLARGE_SIZE);

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

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

				}

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

			}
			else {
				AffineTransform currentTransform = currentNode.getCurrentTransform();
				AffineTransform enlargeTransform = (AffineTransform)currentTransform.clone();
				enlargeTransform.scale(ENLARGE_SIZE, ENLARGE_SIZE);

				currentNode.drawNode(g2, enlargeTransform);
			}


		}

		// PAUSE status
		if (getStatus().equals(Animation.PAUSE)) {
			messageAction(Animation.PAUSE);
			// Draw node where it is.
			currentNode.drawNodeAndLink(g2);
		}

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

		}


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

			messageAction("*----Selection Element Found----*\n"+originalElementCount+"th element of "+((GrowingTreeNode<P>)nodes.getFirst()).getKey().toString()+"\nElement found at "+currentNode.getKey().toString());

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

	}




}