/*
 * @(#)DeleteRedBlackAnimation.java
 *
 * Last Modified: 9/15/01
 */

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

/** *
 	* The Animation object that defines the Deletion of a node in a DeleteRedBlackAnimation. Two constructors exist,
 	* one setting the animator and line paints, the other using defaults. The animation builds RotationBSTAnimations
 	* as it goes, keeping only one currently animating and allowing rewinding only to the previous
 	* rotation. <p>
	*
	* @author  Corey Sanders
	* @version 1.3 9/15/01
 	*/

public class DeleteRedBlackAnimation extends DeleteBSTAnimation {

	/**
	 * The list of links that need to be changed to red at the next possible location.
	 */
	LinkedList redChangeLinks = new LinkedList();

	/**
	 * The list of links that need to be changed to black at the next possible location.
	 */
	LinkedList blackChangeLinks = new LinkedList();

	/**
	 * Refers to the current Rotation being drawn.
	 */
	 RotationBSTAnimation currentRotation = null;

	/**
	 * Holds the node that is replacing.
	 */
	private RedBlackTree childNode;

	/**
	 * Refers to the current <code>SelectionBSTAnimation</code> being drawn.
	 */
	 protected SelectionBSTAnimation currentSelection;


	/**
	 * Current RedBlackTree node. This is the current node being checked for cases.
	 */
	private RedBlackTree currentNode;

	/**
	 * Current RedBlackTree sibling. This is the child of the parent of the current node being checked.
	 */
	private RedBlackTree currentNodeSibling;

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

	/**
	 * Constant that defines the fading of the erasing node.
	 */
	protected final int FADE_NODE = 1;

	/**
	 * Defines the partitioning through the tree.
	 */
	protected int SELECTION_TREE = 2;

	/**
	 * Defines the partitioning through the tree.
	 */
	protected int FADE_NODE_REPLACE = 3;

	/**
	 * Defines the partitioning through the tree.
	 */
	protected int REPLACE_NODE = 4;

	/**
	 * The location for the rotations to begin.
	 */
	 private double WAITING_FIX_UP = 4.1;

	/**
	 * Defines the final move through the tree.
	 */
	protected int FIX_UP = 5;

	/**
	 * Defines the final move through the tree.
	 */
	protected int FINAL_MOVE = 6;

	/**
	 * Defines the final move through the tree.
	 */
	protected int END = 7;

	/**
	 * The location for the rotations to check.
	 */
	 private int rotationCheck;


	/**
	 * The location for beginning of red-black deletion.
	 */
	 protected static final int BEGIN_FIXUP = 0;

	/**
	 * The location for case one in red-black deletion.
	 */
	 protected static final int CASE_ONE = 1;

	 /**
	 * The location for case two in red-black deletion.
	 */
	 protected static final int CASE_TWO = 2;

	 /**
	 * The location for case three in red-black deletion.
	 */
	 protected static final int CASE_THREE = 3;

	/**
	 * The location for case four in red-black deletion.
	 */
	 protected static final int CASE_FOUR = 4;

	/**
	 * The location for the end of red-black deletion.
	 */
	 protected static final int END_FIXUP = 5;




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

	/**
	 * Gets the node being deleted during the replacing.
	 *
	 * @return RedBlackTree of the child node.
	 */
	public RedBlackTree getChildNode() {
		return childNode;
	}


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

	/**
	 * Sets the node being deleted during the Deletion.
	 *
	 * @param BSTTree of the node being deleted.
	 */
	public void setChildNode(RedBlackTree node) {
		childNode = node;
	}

	/**
	 * The constructor which initiates the status and prepares the line paints. The node
	 * which is being deleted must be passed.
	 *
	 * @param erasingNode the BSTTree which is being deleted.
	 * @param RightLinePaint the paint for the right line when drawing the deletion.
	 * @param LeftLinePaint the paint for the left line when drawing the deletion
	 * @param startingCmd the Animation command that this should start.
	 * @param stepTime the time for each step of the Animation. Sets the initial value.
	 */
	public DeleteRedBlackAnimation(BSTTree erasingNode, PaintSettings RightLinePaint, PaintSettings LeftLinePaint, String startingCmd, int stepTime) {

		// Call to AbstractAnimation
		super(erasingNode, RightLinePaint, LeftLinePaint, startingCmd,stepTime );

	}



	/**
	 * The constructor which initiates the status and sets the line paints to null.
	 *
	 * @param erasingNode the BSTTree which is deleted during the deletion.
	 */
	public DeleteRedBlackAnimation(BSTTree erasingNode) {
		this(erasingNode, null, null, Animation.PLAY, DEFAULT_STEP);
	}


	/***********************/
	/* Creation Methods    */
	/***********************/

	/**
	 * Creates the moving nodes corresponding to the final moving of the nodes.
	 */
	protected void createFinalMovingNodes() {
		// Intialize
		finalMovingNodes = new MovingBSTTreeAnimation();

		// Head node
		RedBlackTree headNode = (RedBlackTree)getErasingNode().getHead().getChild();

		// If there is a grandchild.
		MovingRedBlackTree headMovingNode = new MovingRedBlackTree(headNode);

		if (headNode != getErasingNode() && headNode.isAnimateDrawing() ) {
			// If there is a grandchild.
			headMovingNode = new MovingRedBlackTree(headNode);

			// Add grandchild to descendant animation
			finalMovingNodes.add(headMovingNode, headNode);

			headMovingNode.setMovePosition(MovingBSTTree.FOLLOW_NODE);

			// Set listeners
			finalMovingNodes.addAnimationListener(headNode);
			(headNode).addAnimator(finalMovingNodes);
		}
		// Add all children
		addNode((RedBlackTree)headNode.getLeftTree(), finalMovingNodes, MovingBSTTree.FOLLOW_NODE, headMovingNode);
		addNode((RedBlackTree)headNode.getRightTree(), finalMovingNodes, MovingBSTTree.FOLLOW_NODE, headMovingNode);

	}

	/**
	 * Adds all children nodes to the animator list, setting the Moving node as its parent. The move position
	 * defines the moving of the new node.
	 *
	 * @param node the node which the MovingBSTTree made imitates.
	 * @param animator the MovingBSTTreeAnimation to which the new MovingBSTTree node is added.
	 * @param movePostion the moving position of the new MovingBSTTree.
	 * @param parent <code>MovingBSTTree</code> parent for the node, specifically for following the node.
	 */
	protected void addNode(RedBlackTree node, MovingBSTTreeAnimation animator, int movePosition, MovingRedBlackTree parent) {
		if (node.isEmpty())
			return;

		// Create new MovingBSTTree
		MovingRedBlackTree movingNode = new MovingRedBlackTree(node, parent);


		if (node != getErasingNode() && node.isAnimateDrawing()) {


			// Sets the move position
			movingNode.setMovePosition(movePosition);

			// Adds the animator to the MovingBSTTreeAnimation
			animator.add(movingNode, node);

			// Adds the listener to the animation and the animation to the node.
			animator.addAnimationListener(node);
			node.addAnimator(animator);
		}

		// Recursively goes through children
		addNode((RedBlackTree)node.getLeftTree(), animator, MovingBSTTree.FOLLOW_NODE, movingNode);
		addNode((RedBlackTree)node.getRightTree(), animator, MovingBSTTree.FOLLOW_NODE, movingNode);


	}

	/*********************/
	/* 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.
	 * <b> BSTTreeHead calls: </b>
	 * <ul>
	 * <li><code>removeTreeType</code> - to do the final deletion in the actual code (after partitioning has occured)</li>
	 * </ul>
	 * <b> Other Animation Objects used: </b>
	 * <ul>
	 * <li>PartitionBSTAnimation</li>
	 * <li>MovingBSTTreeAnimation</li>
	 * </ul>
	 *
	 *
	 * @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);

		// Starting Finish status (set prior to call)
		if (getStatus().equals(Animation.FINISH)) {

			if (getReplacingNode() != null) {
				// Set alpha for fade
				float currentAlpha = 1;

				// Erasing node with alpha
				getReplacingNode().getSettings().setNodeComposite(AlphaComposite.getInstance(AlphaComposite.SRC_OVER, currentAlpha));
				getReplacingNode().getSettings().setLeftLinkComposite(AlphaComposite.getInstance(AlphaComposite.SRC_OVER, currentAlpha));
				getReplacingNode().getSettings().setRightLinkComposite(AlphaComposite.getInstance(AlphaComposite.SRC_OVER, currentAlpha));
				((DrawableKey)getReplacingNode().getValue()).getSettings().setKeyComposite(AlphaComposite.getInstance(AlphaComposite.SRC_OVER, currentAlpha));
			}

			// The fading out of the node.
			if (currentLocation < FADE_NODE_REPLACE) {

				if (currentLocation == SELECTION_TREE) {
					// Set play status
					currentSelection.setStatus(Animation.FINISH);

					// Draw rotation animation
					currentSelection.drawAnimation(g2, Animation.FINISH);
				}
				if (currentLocation > SELECTION_TREE && currentLocation < FADE_NODE_REPLACE) {
					AnimationEvent animationEvent = new AnimationEvent(this, AnimationEvent.DELETE_RED_BLACK_ANIMATION, Animation.FINISH);

					// Remove listener
					((RedBlackTree)getReplacingNode()).animationEventPerformed(animationEvent);
					this.removeAnimationListener(getReplacingNode());
				}

				((RedBlackTreeHead)getErasingNode().getHead()).remove(getErasingNode());
				return;
			}


			// The final move of the node
			if (currentLocation < REPLACE_NODE) {


				AnimationEvent animationEvent = new AnimationEvent(this, AnimationEvent.DELETE_RED_BLACK_ANIMATION, Animation.FINISH);

				// Remove listener
				((RedBlackTree)getReplacingNode()).animationEventPerformed(animationEvent);
				this.removeAnimationListener(getReplacingNode());

				// Set status of moving animation
				finalMovingNodes.setStatus(Animation.FINISH);
				// Draw animation
				finalMovingNodes.drawAnimation(g2, Animation.FINISH);

				// REDRAW Message
				messageAction(Animation.REDRAW);

				currentLocation = WAITING_FIX_UP;
				currentRotation = null;
				rotationCheck = BEGIN_FIXUP;
				currentNode = getChildNode();



			}
			if (currentLocation < FIX_UP && currentLocation >= WAITING_FIX_UP) {
				currentLocation = FIX_UP;
			}

			if (currentLocation >= FIX_UP && currentLocation < END) {
				if (currentRotation == null) {
					makeCurrentRotation();

				}// End of null currentRotation
				else {
					// Set play status
					currentRotation.setStatus(Animation.FINISH);

					// Draw rotation animation
					currentRotation.drawAnimation(g2, Animation.FINISH);

					setBlackChangeLinks();
					setRedChangeLinks();

					messageAction(Animation.REDRAW);
					currentRotation.removeAnimationListener(this);
					currentRotation = null;

					makeCurrentRotation();
				}

			} // End of FIX_UP

		}


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

			// Set listeners
			getErasingNode().addAnimator(this);
			this.addAnimationListener(getErasingNode());

			// Redraw
			messageAction(Animation.REDRAW);

			animationAction();

			// Original message
			messageAction(Animation.BEGIN + " Deletion of "+getErasingNode().getKey().toString());

			// set starting status
			setStatus(getStartingCommand());

			// Draw to animating graphic
			getErasingNode().drawNodeAndLink(g2);


			return;

		}

		// DRAW Dotted Line
		drawDottedLine(g2, currentLocation);


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


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

			messageAction(Animation.PLAY);

			// Only Increment if fading or final move
			if ((currentLocation <= FADE_NODE) || (currentLocation >  SELECTION_TREE  && currentLocation < FIX_UP)) {
				previousLocation = currentLocation;

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


			// The fading out of the node.
			if (currentLocation < FADE_NODE) {

				// Set alpha for fade
				float currentAlpha = (float)((double)FADE_NODE - currentLocation);

				// Erasing node with alpha
				getErasingNode().getSettings().setNodeComposite(AlphaComposite.getInstance(AlphaComposite.SRC_OVER, currentAlpha));
				getErasingNode().getSettings().setLeftLinkComposite(AlphaComposite.getInstance(AlphaComposite.SRC_OVER, currentAlpha));
				getErasingNode().getSettings().setRightLinkComposite(AlphaComposite.getInstance(AlphaComposite.SRC_OVER, currentAlpha));
				((DrawableKey)getErasingNode().getValue()).getSettings().setKeyComposite(AlphaComposite.getInstance(AlphaComposite.SRC_OVER, currentAlpha));

				// Draw to animating graphic
				getErasingNode().drawNodeAndLink(g2);

			}
			// Finish with fading
			else if ((currentLocation >= FADE_NODE) && (previousLocation <= FADE_NODE)) {

				previousLocation = currentLocation;
				// Step
				setStatus(Animation.STEP);

				// Empty right tree
				if (getErasingNode().getRightTree().isEmpty()) {
					// Empty Left tree
					if (getErasingNode().getLeftTree().isEmpty()) {
						// Do actual deletion in tree (Setting the correct final location).
						// Tree finishes cleared.
						getErasingNode().getHead().removeTreeType(getErasingNode());
						if (getErasingNode().getHead().isTreeEmpty()) {
							messageAction("Resulting Tree is Empty");
						}
						setReplacingNode(null);
						setStatus(Animation.FINISH);
					}
					// Non-Empty Left Tree
					else {
						// Step
						setStatus(Animation.STEP);

						// Set replacing node as left tree
						setReplacingNode((BSTTree)getErasingNode().getLeftTree());

						// Set listeners
						getReplacingNode().addAnimator(this);
						this.addAnimationListener(getReplacingNode());


						if (!getReplacingNode().getLeftTree().isEmpty()) {
							setChildNode((RedBlackTree)getReplacingNode().getLeftTree());
						}
						else {
							setChildNode((RedBlackTree)getReplacingNode().getRightTree());
						}

						// Redraw
						messageAction(Animation.REDRAW);

						// Draw to animating graphic
						getReplacingNode().drawNodeAndLink(g2);

						currentLocation = SELECTION_TREE + getStepSize();

						messageAction("No right Tree : Replace with Left tree");

					}

				}
				// Non-Empty Right Tree
				else {

					// Partition element
					currentLocation = SELECTION_TREE;

					messageAction("Select the smallest node of right subtree");

					currentSelection = (SelectionBSTAnimation)((BSTTreeHead)getErasingNode().getHead()).makeSelectionAnimation((BSTTree)getErasingNode().getRightTree(), 0);

					currentSelection.addAnimationListener(this);

					currentSelection.drawAnimation(g2, Animation.PLAY);

					// Do not allow the erased node draw during the Partition
					getErasingNode().setAnimateDrawing(false);
				}
			}

			// The partition of the tree
			else if (currentLocation == SELECTION_TREE) {
				// Set values for animation
				currentSelection.setStepTime(getStepTime());
				currentSelection.setStep(getStep());

				// Set play status
				currentSelection.setStatus(Animation.PLAY);

				// Draw rotation animation
				currentSelection.drawAnimation(g2, Animation.PLAY);

				if (currentSelection.getStatus().equals(Animation.FINISH)) {
					setReplacingNode((RedBlackTree)getErasingNode().getHead().selectTreeType((BSTTree)getErasingNode().getRightTree(), 0));
				 	// Step
					setStatus(Animation.STEP);

					if (!getReplacingNode().getLeftTree().isEmpty()) {
						setChildNode((RedBlackTree)getReplacingNode().getLeftTree());
					}
					else {
						setChildNode((RedBlackTree)getReplacingNode().getRightTree());
					}

					// Original message
					messageAction(Animation.BEGIN + " Removal of "+getReplacingNode().getKey().toString());

					// Set listeners
					getReplacingNode().addAnimator(this);
					this.addAnimationListener(getReplacingNode());

					// Redraw
					messageAction(Animation.REDRAW);

					// Draw to animating graphic
					getReplacingNode().drawNodeAndLink(g2);

					currentLocation += getStepSize();
				}
			}
			else if (currentLocation < FADE_NODE_REPLACE) {

				// Set alpha for fade
				float currentAlpha = (float)((double)FADE_NODE_REPLACE - currentLocation);

				// Erasing node with alpha
				getReplacingNode().getSettings().setNodeComposite(AlphaComposite.getInstance(AlphaComposite.SRC_OVER, currentAlpha));
				getReplacingNode().getSettings().setLeftLinkComposite(AlphaComposite.getInstance(AlphaComposite.SRC_OVER, currentAlpha));
				getReplacingNode().getSettings().setRightLinkComposite(AlphaComposite.getInstance(AlphaComposite.SRC_OVER, currentAlpha));
				((DrawableKey)getReplacingNode().getValue()).getSettings().setKeyComposite(AlphaComposite.getInstance(AlphaComposite.SRC_OVER, currentAlpha));

				// Draw to animating graphic
				getReplacingNode().drawNodeAndLink(g2);

			}

			// The final move of the node
			else if (currentLocation < REPLACE_NODE) {

				if (previousLocation <= FADE_NODE_REPLACE) {
					// Step
					setStatus(Animation.STEP);

					// Do not allow the erased node draw during the Partition
					getReplacingNode().setAnimateDrawing(false);

					// Create final moving nodes starting at previous location.
					createFinalMovingNodes();

					// Do actual deletion in tree (Setting the correct final location).
					getErasingNode().getHead().removeTreeType(getErasingNode());

					// REDRAW Message
					messageAction(Animation.REDRAW);

					// Beginning final moving Nodes
					finalMovingNodes.drawAnimation(g2, Animation.PLAY);

					messageAction("Replace erased node with node " + getReplacingNode().getKey().toString());

				}
				else {

					// Set alpha for fade
					float currentAlpha = (float)(1.0 - ((double)REPLACE_NODE - currentLocation));

					// Erasing node with alpha
					getReplacingNode().getSettings().setNodeComposite(AlphaComposite.getInstance(AlphaComposite.SRC_OVER, currentAlpha));
					getReplacingNode().getSettings().setLeftLinkComposite(AlphaComposite.getInstance(AlphaComposite.SRC_OVER, currentAlpha));
					getReplacingNode().getSettings().setRightLinkComposite(AlphaComposite.getInstance(AlphaComposite.SRC_OVER, currentAlpha));
					((DrawableKey)getReplacingNode().getValue()).getSettings().setKeyComposite(AlphaComposite.getInstance(AlphaComposite.SRC_OVER, currentAlpha));

					// Draw to animating graphic
					getReplacingNode().drawNodeAndLink(g2);

					// Set play status
					finalMovingNodes.setStatus(Animation.PLAY);

					// Set values for animation
					finalMovingNodes.setStepTime(getStepTime());
					finalMovingNodes.setStep(getStep());

					// Draw animation
					finalMovingNodes.drawAnimation(g2, Animation.PLAY);
				}
			}

			// Finish with fading
			else if ((currentLocation >= REPLACE_NODE) && (previousLocation <= REPLACE_NODE)) {

				previousLocation = currentLocation;

				// Set alpha for fade
				float currentAlpha = 1;

				// Erasing node with alpha
				getReplacingNode().getSettings().setNodeComposite(AlphaComposite.getInstance(AlphaComposite.SRC_OVER, currentAlpha));
				getReplacingNode().getSettings().setLeftLinkComposite(AlphaComposite.getInstance(AlphaComposite.SRC_OVER, currentAlpha));
				getReplacingNode().getSettings().setRightLinkComposite(AlphaComposite.getInstance(AlphaComposite.SRC_OVER, currentAlpha));
				((DrawableKey)getReplacingNode().getValue()).getSettings().setKeyComposite(AlphaComposite.getInstance(AlphaComposite.SRC_OVER, currentAlpha));

				// Draw to animating graphic
				getReplacingNode().drawNodeAndLink(g2);

				// Do not allow the erased node draw during the Partition
				getReplacingNode().setAnimateDrawing(true);


				AnimationEvent animationEvent = new AnimationEvent(this, AnimationEvent.DELETE_RED_BLACK_ANIMATION, Animation.FINISH);

				// Remove listener
				((RedBlackTree)getReplacingNode()).animationEventPerformed(animationEvent);
				this.removeAnimationListener(getReplacingNode());


				// Set values for animation
				finalMovingNodes.setStepTime(getStepTime());
				finalMovingNodes.setStep(getStep());

				// Set play status
				finalMovingNodes.setStatus(Animation.PLAY);
				// Draw animation
				finalMovingNodes.drawAnimation(g2, Animation.PLAY);
				// Set status of moving animation
				finalMovingNodes.setStatus(Animation.FINISH);
				// Draw animation
				finalMovingNodes.drawAnimation(g2, Animation.FINISH);

				// REDRAW Message
				messageAction(Animation.REDRAW);

				currentLocation = WAITING_FIX_UP;
				currentRotation = null;
				rotationCheck = BEGIN_FIXUP;
				currentNode = getChildNode();
			}
			else if (currentLocation < FIX_UP && currentLocation >= WAITING_FIX_UP) {
			}

			else if (currentLocation >= FIX_UP && currentLocation < END) {

				if (currentRotation == null) {
					makeCurrentRotation();

					if (currentRotation != null) {
						// Draw rotation animation
						currentRotation.addAnimationListener(this);

						messageAction(Animation.REDRAW);

						currentRotation.drawAnimation(g2, Animation.PLAY);
					}



				}// End of null currentRotation
				else {
					// Set values for animation
					currentRotation.setStepTime(getStepTime());
					currentRotation.setStep(getStep());

					// Set play status
					currentRotation.setStatus(Animation.PLAY);

					// Draw rotation animation
					currentRotation.drawAnimation(g2, Animation.PLAY);

					if (currentRotation.getStatus().equals(Animation.FINISH)) {

						setBlackChangeLinks();
						setRedChangeLinks();

						messageAction(Animation.REDRAW);

						currentLocation = WAITING_FIX_UP;

						// Draw rotation animation
						currentRotation.drawAnimation(g2, Animation.FINISH);

						currentRotation.removeAnimationListener(this);
						currentRotation = null;
					}
				}

			} // End of FIX_UP
			else if (currentLocation == END){
				setStatus(Animation.FINISH);
			}

		}

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

			messageAction(Animation.REWIND);

			// Only Increment if fading or final move
			if ((currentLocation <= FADE_NODE) || (currentLocation >  SELECTION_TREE  && currentLocation < FIX_UP)) {
				previousLocation = currentLocation;

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

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


			// The fading out of the node.
			if (currentLocation < FADE_NODE) {

				// Set alpha for fade
				float currentAlpha = (float)((double)FADE_NODE - currentLocation);

				// Erasing node with alpha
				getErasingNode().getSettings().setNodeComposite(AlphaComposite.getInstance(AlphaComposite.SRC_OVER, currentAlpha));
				getErasingNode().getSettings().setLeftLinkComposite(AlphaComposite.getInstance(AlphaComposite.SRC_OVER, currentAlpha));
				getErasingNode().getSettings().setRightLinkComposite(AlphaComposite.getInstance(AlphaComposite.SRC_OVER, currentAlpha));
				((DrawableKey)getErasingNode().getValue()).getSettings().setKeyComposite(AlphaComposite.getInstance(AlphaComposite.SRC_OVER, currentAlpha));

				// Draw to animating graphic
				getErasingNode().drawNodeAndLink(g2);

			}

			// The partition of the tree
			else if (currentLocation <= SELECTION_TREE) {

				// Previously replacing node
				if (previousLocation > SELECTION_TREE) {
					currentLocation = SELECTION_TREE + getStepSize();
					messageAction("Cannot Rewind : Beginning of Splice");
					// Pause status
					setStatus(Animation.PAUSE);
					return;
				}

				// Set values for animation
				currentSelection.setStepTime(getStepTime());
				currentSelection.setStep(getStep());

				// Set play status
				currentSelection.setStatus(Animation.REWIND);

				// Draw rotation animation
				currentSelection.drawAnimation(g2, Animation.REWIND);

				if (currentSelection.getStatus().equals(Animation.PAUSE)) {
					messageAction("Cannot Rewind : Beginning of Selection");
					// Pause status
					setStatus(Animation.PAUSE);
				}
			}
			else if (currentLocation < FADE_NODE_REPLACE) {
				if (previousLocation >= FADE_NODE_REPLACE) {
					currentLocation = FADE_NODE_REPLACE + getStepSize();
					previousLocation = currentLocation;
					messageAction("Cannot Rewind : Beginning of Replacement");
					// Pause status
					setStatus(Animation.PAUSE);

					// Draw to animating graphic
					getReplacingNode().drawNodeAndLink(g2);

					// Set play status
					finalMovingNodes.setStatus(Animation.PAUSE);

					// Draw animation
					finalMovingNodes.drawAnimation(g2, Animation.PAUSE);

					return;
				}

				// Set alpha for fade
				float currentAlpha = (float)((double)FADE_NODE_REPLACE - currentLocation);

				// Erasing node with alpha
				getReplacingNode().getSettings().setNodeComposite(AlphaComposite.getInstance(AlphaComposite.SRC_OVER, currentAlpha));
				getReplacingNode().getSettings().setLeftLinkComposite(AlphaComposite.getInstance(AlphaComposite.SRC_OVER, currentAlpha));
				getReplacingNode().getSettings().setRightLinkComposite(AlphaComposite.getInstance(AlphaComposite.SRC_OVER, currentAlpha));
				((DrawableKey)getReplacingNode().getValue()).getSettings().setKeyComposite(AlphaComposite.getInstance(AlphaComposite.SRC_OVER, currentAlpha));

				// Draw to animating graphic
				getReplacingNode().drawNodeAndLink(g2);

			}
			// The final move of the node
			else if (currentLocation < REPLACE_NODE) {

				// Set alpha for fade
				float currentAlpha = (float)(1.0 - ((double)REPLACE_NODE - currentLocation));

				// Erasing node with alpha
				getReplacingNode().getSettings().setNodeComposite(AlphaComposite.getInstance(AlphaComposite.SRC_OVER, currentAlpha));
				getReplacingNode().getSettings().setLeftLinkComposite(AlphaComposite.getInstance(AlphaComposite.SRC_OVER, currentAlpha));
				getReplacingNode().getSettings().setRightLinkComposite(AlphaComposite.getInstance(AlphaComposite.SRC_OVER, currentAlpha));
				((DrawableKey)getReplacingNode().getValue()).getSettings().setKeyComposite(AlphaComposite.getInstance(AlphaComposite.SRC_OVER, currentAlpha));

				// Draw to animating graphic
				getReplacingNode().drawNodeAndLink(g2);

				// Set play status
				finalMovingNodes.setStatus(Animation.REWIND);

				// Set values for animation
				finalMovingNodes.setStepTime(getStepTime());
				finalMovingNodes.setStep(getStep());

				// Draw animation
				finalMovingNodes.drawAnimation(g2, Animation.REWIND);
			}
			else if (currentLocation < FIX_UP && currentLocation >= WAITING_FIX_UP) {
				messageAction("Cannot Rewind : Beginning of Fixing");
				currentLocation = previousLocation;
				// Pause status
				setStatus(Animation.PAUSE);
			}

			else if (currentLocation >= FIX_UP && currentLocation < END) {
				// Set values for animation
				currentRotation.setStepTime(getStepTime());
				currentRotation.setStep(getStep());

				// Set rewind status
				currentRotation.setStatus(Animation.REWIND);

				// Draw rotation animation
				currentRotation.drawAnimation(g2, Animation.REWIND);

				if (currentRotation.getStatus().equals(Animation.PAUSE)) {

					messageAction("Cannot Rewind : Beginning of Rotation");
					// Pause status
					setStatus(Animation.PAUSE);
				}

			}

		}

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

			messageAction(Animation.PAUSE);

			// The fading out of the node.
			if (currentLocation < FADE_NODE) {

				// Draw to animating graphic
				getErasingNode().drawNodeAndLink(g2);

			}

			// The partition of the tree
			else if (currentLocation <= SELECTION_TREE) {

				// Set play status
				currentSelection.setStatus(Animation.PAUSE);

				// Draw rotation animation
				currentSelection.drawAnimation(g2, Animation.PAUSE);

			}
			else if (currentLocation < FADE_NODE_REPLACE) {

				// Draw to animating graphic
				getReplacingNode().drawNodeAndLink(g2);

			}
			// The final move of the node
			else if (currentLocation < REPLACE_NODE) {

				// Draw to animating graphic
				getReplacingNode().drawNodeAndLink(g2);

				// Set play status
				finalMovingNodes.setStatus(Animation.PAUSE);

				// Draw animation
				finalMovingNodes.drawAnimation(g2, Animation.PAUSE);
			}
			else if (currentLocation < FIX_UP && currentLocation >= WAITING_FIX_UP) {

			}
			else if (currentLocation >= FIX_UP && currentLocation < END) {
				// Set rewind status
				currentRotation.setStatus(Animation.PAUSE);

				// Draw rotation animation
				currentRotation.drawAnimation(g2, Animation.PAUSE);
			}

		}

		// STOP status
		if (getStatus().equals(Animation.STOP)) {
			messageAction(Animation.STOP);
			// The fading out of the node.
			// The fading out of the node.
			if (currentLocation < FADE_NODE) {


			}

			// The partition of the tree
			else if (currentLocation <= SELECTION_TREE) {

				// Set play status
				currentSelection.setStatus(Animation.STOP);

				// Draw rotation animation
				currentSelection.drawAnimation(g2, Animation.STOP);

			}
			else if (currentLocation < FADE_NODE_REPLACE) {


			}
			// The final move of the node
			else if (currentLocation < REPLACE_NODE) {

				// Set play status
				finalMovingNodes.setStatus(Animation.STOP);

				// Draw animation
				finalMovingNodes.drawAnimation(g2, Animation.STOP);
			}
			else if (currentLocation < FIX_UP && currentLocation >= WAITING_FIX_UP) {

			}
			else if (currentLocation >= FIX_UP && currentLocation < END) {
				// Set rewind status
				currentRotation.setStatus(Animation.STOP);

				// Draw rotation animation
				currentRotation.drawAnimation(g2, Animation.STOP);
			}

			return;
		}


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

			messageAction(Animation.FINISH);

			if (getReplacingNode() == null) {
				messageAction("*--------Deletion of "+getErasingNode().getKey().toString()+"--------*\n"+
							"No Replacement for Node");
			}
			else {
				messageAction("*--------Deletion of "+getErasingNode().getKey().toString()+"--------*\n"+
								"Node replaced by: "+getReplacingNode().getKey().toString());

			}

		}

		// Call listeners
		animationAction();

	}


	/**
	 * Fixes the redChangeLinks by settings all the nodes links within the list to red. Then
	 * the nodes are removed from the list, always leaving it clear after this call.
	 */
	 public void setRedChangeLinks() {
		ListIterator list = redChangeLinks.listIterator(0);
		while (list.hasNext()) {
			RedBlackTree currentNode = (RedBlackTree)list.next();
			if (!currentNode.isEmpty()) {

				// Reverses the link
				currentNode.setRedLink(true);
			}
		}

		redChangeLinks.clear();
	}

	/**
	 * Fixes the blackChangeLinks by settings all the nodes links within the list to black. Then
	 * the nodes are removed from the list, always leaving it clear after this call.
	 */
	 public void setBlackChangeLinks() {
		ListIterator list = blackChangeLinks.listIterator(0);
		while (list.hasNext()) {
			RedBlackTree currentNode = (RedBlackTree)list.next();

			if (!currentNode.isEmpty()) {

			// Reverses the link
			currentNode.setRedLink(false);
			}
		}

		blackChangeLinks.clear();
	}

	/**
	 * Constructs the current Rotation according to the current tree, and the defined rotationCheck.
	 * This method follows the rules set by the deletion of a node in a red-black tree. Consequently,
	 * this method is one of the important methods in extending <code>DeleteBSTAnimation</code>.
	 *
	 */
	protected void makeCurrentRotation() {

		if (rotationCheck != END_FIXUP) {
			while ((currentNode.getParentTree() != currentNode.getHead()) && (!currentNode.isRedLink())) {
				if (rotationCheck == BEGIN_FIXUP) {
					rotationCheck = CASE_ONE;
				}

				if (currentNode == ((RedBlackTree)currentNode.getParentTree()).getLeftTree()) {

					currentNodeSibling = (RedBlackTree)((RedBlackTree)currentNode.getParentTree()).getRightTree();

					if (rotationCheck == CASE_ONE) {
						rotationCheck = CASE_TWO;

						// CASE ONE
						if (currentNodeSibling.isRedLink()) {

							messageAction("Case one on left:");

							if (currentNodeSibling.getKey() == null || currentNodeSibling.getKey() == null ) {
								messageAction("Sibling ("+currentNodeSibling.getKey().toString()+") of "+currentNode.getKey().toString()+" is red,");
							}
							blackChangeLinks.add(currentNodeSibling);
							redChangeLinks.add(((RedBlackTree)currentNode.getParentTree()));

							currentRotation = (RotationBSTAnimation)((RedBlackTreeHead)currentNode.getHead()).makeRotationAnimation(currentNodeSibling);

							if (currentRotation == null) {
								((RedBlackTreeHead)currentNode.getHead()).rotateUpTreeType(currentNodeSibling);

								setBlackChangeLinks();
								setRedChangeLinks();

								messageAction(Animation.REDRAW);
								currentNodeSibling = (RedBlackTree)((RedBlackTree)currentNode.getParentTree()).getRightTree();

							}
							else {
								break;
							}
						}
					}

					if (rotationCheck == CASE_TWO) {
						// CASE TWO
						if (currentNodeSibling.isEmpty()) {
							rotationCheck = END_FIXUP;
							break;
						}

						if ( (!((RedBlackTree)currentNodeSibling.getLeftTree()).isRedLink()) && (!((RedBlackTree)currentNodeSibling.getRightTree()).isRedLink()) ){

							messageAction("Case two on left:");

							if (!currentNodeSibling.isEmpty()) {
								messageAction("Sibling ("+currentNodeSibling.getKey().toString()+"). Both of its children are black.");
							}

							rotationCheck = BEGIN_FIXUP;

							currentNodeSibling.setRedLink(true);

							messageAction(Animation.REDRAW);

							currentNode = (RedBlackTree)currentNode.getParentTree();

							currentLocation = WAITING_FIX_UP;
						}
						else {
							rotationCheck = CASE_THREE;
						}
					}

					if (rotationCheck == CASE_THREE) {
						rotationCheck = CASE_FOUR;

						if (!((RedBlackTree)currentNodeSibling.getRightTree()).isRedLink()) {

							messageAction("Case three on left:");

							if (!currentNodeSibling.isEmpty()) {
								messageAction("Sibling ("+currentNodeSibling.getKey().toString()+"). Left Child is red and right child is black.");
							}

							blackChangeLinks.add(((RedBlackTree)currentNodeSibling.getLeftTree()));
							redChangeLinks.add(currentNodeSibling);

							currentRotation = (RotationBSTAnimation)((RedBlackTreeHead)currentNode.getHead()).makeRotationAnimation((RedBlackTree)currentNodeSibling.getLeftTree());

							if (currentRotation == null) {
								((RedBlackTreeHead)currentNode.getHead()).rotateUpTreeType((RedBlackTree)currentNodeSibling.getLeftTree());

								setBlackChangeLinks();
								setRedChangeLinks();

								messageAction(Animation.REDRAW);
								currentNodeSibling = (RedBlackTree)((RedBlackTree)currentNode.getParentTree()).getRightTree();

							}
							else {
								break;
							}

						}
					}
					if (rotationCheck == CASE_FOUR)  {

						messageAction("Case four on left:");

						if (!currentNodeSibling.isEmpty()) {
							messageAction("Sibling ("+currentNodeSibling.getKey().toString()+"). Right Child is red and left child is black.");
						}

						blackChangeLinks.add((RedBlackTree)currentNode.getParentTree());
						blackChangeLinks.add((RedBlackTree)currentNodeSibling.getRightTree());

						if (((RedBlackTree)currentNode.getParentTree()).isRedLink()) {
							redChangeLinks.add(currentNodeSibling);
						}
						else {
							blackChangeLinks.add(currentNodeSibling);
						}

						currentRotation = (RotationBSTAnimation)((RedBlackTreeHead)currentNode.getHead()).makeRotationAnimation(currentNodeSibling);

						if (currentRotation == null) {
							((RedBlackTreeHead)currentNode.getHead()).rotateUpTreeType(currentNodeSibling);

							setBlackChangeLinks();
							setRedChangeLinks();

							messageAction(Animation.REDRAW);
						}

						rotationCheck = END_FIXUP;

						break;
					}
				}
				// Right Tree
				else {
					currentNodeSibling = (RedBlackTree)((RedBlackTree)currentNode.getParentTree()).getLeftTree();

					if (rotationCheck == CASE_ONE) {
						rotationCheck = CASE_TWO;

						// CASE ONE
						if (currentNodeSibling.isRedLink()) {

							messageAction("Case one on right:");

							if (currentNodeSibling.getKey() == null || currentNodeSibling.getKey() == null ) {
								messageAction("Sibling ("+currentNodeSibling.getKey().toString()+") of "+currentNode.getKey().toString()+" is red,");
							}


							blackChangeLinks.add(currentNodeSibling);
							redChangeLinks.add(((RedBlackTree)currentNode.getParentTree()));

							currentRotation = (RotationBSTAnimation)(RotationBSTAnimation)((RedBlackTreeHead)currentNode.getHead()).makeRotationAnimation(currentNodeSibling);

							if (currentRotation == null) {
								((RedBlackTreeHead)currentNode.getHead()).rotateUpTreeType(currentNodeSibling);

								setBlackChangeLinks();
								setRedChangeLinks();

								messageAction(Animation.REDRAW);
								currentNodeSibling = (RedBlackTree)((RedBlackTree)currentNode.getParentTree()).getLeftTree();

							}
							else {
								break;
							}
						}
					}

					if (rotationCheck == CASE_TWO) {

						if (currentNodeSibling.isEmpty()) {
							rotationCheck = END_FIXUP;
							break;
						}

						if ( !((RedBlackTree)currentNodeSibling.getRightTree()).isRedLink() && !((RedBlackTree)currentNodeSibling.getLeftTree()).isRedLink() ) {

							messageAction("Case two on right:");

							if (!currentNodeSibling.isEmpty()) {
								messageAction("Sibling ("+currentNodeSibling.getKey().toString()+"). Both of its children are black.");
							}

							rotationCheck = BEGIN_FIXUP;

							currentNodeSibling.setRedLink(true);

							messageAction(Animation.REDRAW);

							currentNode = (RedBlackTree)currentNode.getParentTree();

							currentLocation = WAITING_FIX_UP;
						}
						else {
							rotationCheck = CASE_THREE;
						}
					}
					if (rotationCheck == CASE_THREE) {
						rotationCheck = CASE_FOUR;

						if (!((RedBlackTree)currentNodeSibling.getLeftTree()).isRedLink()) {

							messageAction("Case three on right:");

							if (!currentNodeSibling.isEmpty()) {
								messageAction("Sibling ("+currentNodeSibling.getKey().toString()+"). Right Child is red and left child is black.");
							}

							blackChangeLinks.add(((RedBlackTree)currentNodeSibling.getRightTree()));
							redChangeLinks.add(currentNodeSibling);

							currentRotation = (RotationBSTAnimation)(RotationBSTAnimation)((RedBlackTreeHead)currentNode.getHead()).makeRotationAnimation((RedBlackTree)currentNodeSibling.getRightTree());

							if (currentRotation == null) {
								setBlackChangeLinks();
								setRedChangeLinks();

								((RedBlackTreeHead)currentNode.getHead()).rotateUpTreeType((RedBlackTree)currentNodeSibling.getLeftTree());
								messageAction(Animation.REDRAW);
								currentNodeSibling = (RedBlackTree)((RedBlackTree)currentNode.getParentTree()).getLeftTree();
							}
							else {
								break;
							}

						}
					}

					if (rotationCheck == CASE_FOUR)  {

						messageAction("Case four on right:");

						if (!currentNodeSibling.isEmpty()) {
							messageAction("Sibling ("+currentNodeSibling.getKey().toString()+"). Left Child is red and right child is black.");
						}

						blackChangeLinks.add((RedBlackTree)currentNode.getParentTree());
						blackChangeLinks.add((RedBlackTree)currentNodeSibling.getLeftTree());

						if (((RedBlackTree)currentNode.getParentTree()).isRedLink()) {
							redChangeLinks.add(currentNodeSibling);
						}
						else {
							blackChangeLinks.add(currentNodeSibling);
						}

						currentRotation = (RotationBSTAnimation)(RotationBSTAnimation)((RedBlackTreeHead)currentNode.getHead()).makeRotationAnimation(currentNodeSibling);

						if (currentRotation == null) {
							setBlackChangeLinks();
							setRedChangeLinks();

							((RedBlackTreeHead)currentNode.getHead()).rotateUpTreeType(currentNodeSibling);
							messageAction(Animation.REDRAW);
						}

						rotationCheck = END_FIXUP;

						break;
					}
				}// End of Right Side
			}// End of WHILE loop

			if (currentRotation == null) {
				setBlackChangeLinks();
				setRedChangeLinks();
				if (currentNode.getKey() != null) {
					messageAction("Set Current Node ("+currentNode.getKey().toString()+") as black");
				}

				currentNode.setRedLink(false);
				messageAction(Animation.REDRAW);
				currentLocation = END;
			}
		}// End of FIXUP
		else if (rotationCheck == END_FIXUP) {
			setBlackChangeLinks();
			setRedChangeLinks();
			if (currentNode.getKey() != null) {
				messageAction("Set Current Node ("+currentNode.getKey().toString()+") as black");
			}
			currentNode.setRedLink(false);
			messageAction(Animation.REDRAW);
			currentLocation = END;
		}
	}



	/**
	 * Draws a dotted line 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.
	 */
	protected void drawDottedLine( Graphics2D g2, double location) {

		if (location >= WAITING_FIX_UP) {
			return;
		}

		// Makes the left dotted line
		Line2D.Double dottedLeft = new Line2D.Double( (getErasingNode().getCurrentTransform().getTranslateX() + getErasingNode().getCurrentTransform().getScaleX()/2.0 - 1) , (getErasingNode().getCurrentTransform().getTranslateY() + getErasingNode().getCurrentTransform().getScaleY()/2.0) , (getErasingNode().getCurrentTransform().getTranslateX() + getErasingNode().getCurrentTransform().getScaleX()/2.0 - 1) , (g2.getClipBounds().getY() + g2.getClipBounds().getHeight()));
		// Makes the right dotted line
		Line2D.Double dottedRight = new Line2D.Double( (getErasingNode().getCurrentTransform().getTranslateX() + getErasingNode().getCurrentTransform().getScaleX()/2.0+ 1) , (getErasingNode().getCurrentTransform().getTranslateY() + getErasingNode().getCurrentTransform().getScaleY()/2.0) , (getErasingNode().getCurrentTransform().getTranslateX() + getErasingNode().getCurrentTransform().getScaleX()/2.0 + 1) , (g2.getClipBounds().getY() + g2.getClipBounds().getHeight()));

		// Sets break distance
		float dash[] = {10.0f};
	    BasicStroke dashed = new BasicStroke(2.0f,
	                                          BasicStroke.CAP_BUTT,
	                                          BasicStroke.JOIN_MITER,
	                                          10.0f, dash, 0.0f);

		// Draw dotted line.
		if (location <= FADE_NODE) { // Fading in
			g2.setComposite(AlphaComposite.getInstance(AlphaComposite.SRC_OVER, (float)location));
		}
		else if (location >= FADE_NODE_REPLACE) {
			g2.setComposite(AlphaComposite.getInstance(AlphaComposite.SRC_OVER, (float)(1.0 - (location - (Math.floor(location)))) ));
		}
		else {// Full Composite
			g2.setComposite(AlphaComposite.getInstance(AlphaComposite.SRC_OVER, 1.0F));
		}



		// Set graphics information

		g2.setStroke(dashed);
		g2.setPaint(getLeftLinePaintSettings().getPaint());

		g2.draw(dottedLeft);
		g2.setPaint(getRightLinePaintSettings().getPaint());
		g2.draw(dottedRight);
	}



	/**
	 * 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.DELETE_RED_BLACK_ANIMATION, cmd, description, currentLocation / END);
	}

}