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

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


/** * The class provides the base structure of a <code>RedBlackTree</code>, a node of a Red-Black tree.
    * It uses the elements <i>natural ordering</i>. It uses everything defined within the <code>AbstractTree</code>
    * <p>The BSTTree cannot be the head of the tree, it is only the nodes. It defines recursive methods
    * which aren't defined in the head node and it does not define the methods for the head node.
	*
	* <p><hr>The Red-Black tree is a natural extension of a Binary Search Tree, because it is in fact
	* a specialized Binary Search Tree.
    * <p><b>Note that this implementation is not synchronized.</b> If multiple
 	* threads access this tree concurrently, and at least one of the threads modifies
 	* the tree structurally, it <i>must</i> be synchronized externally.
 	* @author  Corey Sanders
	* @version 3.4 9/15/01
 	*/
public class RedBlackTree extends BSTTree {


	/*************************************************************************/
	/* BSTTree constructor, methods, and variables for all types of BSTTrees */
	/*************************************************************************/


	 /**
	  * Constructs a new, empty RedBlackTree.
	  *
	  * <p><b>Default type is BST_TREE_TYPE.</b>
     */
     public RedBlackTree() {
		 this(0);
 	 }

 	 /**
 	  * Constructs a new, empty RedBlackTree according to the type passed.
 	  *
 	  *@param treeType type of tree that should be implemented.
 	  */
 	  public RedBlackTree(int treeType) {
		  super(treeType);

	  }

	/**
	* Copies the fields of this <code>RedBlackTree</code> into the <code>RedBlackTree</code> copy.
	* The only additional information is the red bit.
	*
	* @param copy the <code>BSTTree</code> that takes the fields of the <code>BSTTree</code>.
	*/
	protected void copyBSTTree(BSTTree copy) {
		((RedBlackTree)copy).setRedLink(isRedLink());

		super.copyBSTTree(copy);
	}


	/*-----------------------------------------------------------------------*/
    /*-------------------------------BST_TREE_TYPE---------------------------*/
	/*-----------------------------------START-------------------------------*/
	/*-----------------------------------------------------------------------*/


	/*************************************************************************/
	/* BST_TREE_TYPE : Methods and Variables specific to the BST_TREE_TYPE.  */
	/* These methods are universally used, regardless of the type of BST.    */
	/*************************************************************************/


	/**
	 * Bit to determine whether the link to the node is red or black.
	 * This bit will be modified numerous times throughout insertion.
	 */
	private boolean redLink = false;


	/**
 	 **********************************
	 * BST_TREE_TYPE Accesssor methods*
	 **********************************
	 */

	/**
	 * Gets the red link for the node.
	 *
	 * @return true if the link to the current node is red.
	 */
	public boolean isRedLink() {
		return redLink;
	}


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

	/**
	 * Sets the red link for the node.
	 *
	 * @param redLink true if the link to the current node is red.
	 */
	public void setRedLink(boolean redLink) {
		this.redLink = redLink;
	}


	/**
     * Sets the values of a new Node left and right tress, to refer to null trees. Both the left and right trees are
     * instantiated and their values are set to the default null values.
	 */
	protected void setLeaf() {
		setLeftTree(new RedBlackTree(getTreeType()));
		setRightTree(new RedBlackTree(getTreeType()));
		getLeftTree().setParentTree(this);
		getRightTree().setParentTree(this);
		((RedBlackTree)getLeftTree()).setRedLink(false);
		((RedBlackTree)getRightTree()).setRedLink(false);

	}


	/**
 	 **********************************
	 * BST_TREE_TYPE Tree Methods	  *
	 **********************************
	 */


	/**
     * Inserts the given object into the tree, using recursive calls and is called from the Head node. This method is recursive until it
     * finds a subtree that is null and sets the node.
     *
     * <p> Before Recursive calls (on the way down) 4-nodes are split up. Then the node is
     * recursively inserted and on returning calls (on the way back up), Red-Black link integrity
     * is maintained.
     *
     * @param newTree the tree to be inserted, with key and value already set.
     *
     * @param currentLevel keeps track of the recursive call, and sets the new level if it changes.
     *
     * @throws    ClassCastException key cannot be compared with the keys
	 *		  currently in the tree.
     */
	protected void insert(BSTTree newTree, int currentLevel) throws ClassCastException {

		if (!((RedBlackTreeHead)getHead()).isTreeAnimating()) {

			// Set insertion color link.
			if (currentLevel == 0) {
				((RedBlackTree)newTree).setRedLink(true);
			}


			// Fixes 4-nodes
			if (((RedBlackTree)getLeftTree()).isRedLink() && ((RedBlackTree)getRightTree()).isRedLink()) {
				setRedLink(true);
				((RedBlackTree)getLeftTree()).setRedLink(false);
				((RedBlackTree)getRightTree()).setRedLink(false);
			}
		}

		super.insert(newTree, currentLevel);

		if (!((RedBlackTreeHead)getHead()).isTreeAnimating()) {
			insertRedBlackTree((RedBlackTree)newTree);
		}

	}


	/**
     * Inserts the given object into the tree, using recursive calls and is called from the Head node. This method is recursive until it
     * finds a subtree that is null and sets the node.
     *
     * <p> Before Recursive calls (on the way down) 4-nodes are split up. Then the node is
     * recursively inserted and on returning calls (on the way back up), Red-Black link integrity
     * is maintained.
     *
     * @param newTree the tree to be inserted, with key and value already set.
     *
     * @param currentLevel keeps track of the recursive call, and sets the new level if it changes.
     *
     * @throws    ClassCastException key cannot be compared with the keys
	 *		  currently in the tree.
     */
	protected void insertRedBlackTree(RedBlackTree newTree) throws ClassCastException {

		// Keeps Red-Link integrity
		if ((newTree.getKey()).compareTo(getKey()) < 0) { // Go to the left
  			if (this != getHead().getChild()) {
				// Two consequetive red links.
				if ((isRedLink()) && (((RedBlackTree)getLeftTree()).isRedLink())) {
					// Same Direction
					if (this != ((RedBlackTree)getParentTree()).getLeftTree()) {
 						((RedBlackTreeHead)getHead()).rotateUp((RedBlackTree)getLeftTree());
					}
				}
			}

			if (!getLeftTree().isEmpty()) {
				if ((((RedBlackTree)getLeftTree()).isRedLink()) && (((RedBlackTree)getLeftTree().getLeftTree()).isRedLink()) ) {
					// Reference to rotated up parent.
					RedBlackTree newParent = (RedBlackTree)getLeftTree();
					((RedBlackTreeHead)getHead()).rotateUp((RedBlackTree)getLeftTree());
					newParent.setRedLink(false);
					((RedBlackTree)newParent.getRightTree()).setRedLink(true);
				}
			}
		}
		else {
			if (this != getHead().getChild()) {
				// Two consequetive red links.
				if ((isRedLink()) && (((RedBlackTree)getRightTree()).isRedLink())) {
					// Same Direction
					if (this != ((RedBlackTree)getParentTree()).getRightTree()) {
						((RedBlackTreeHead)getHead()).rotateUp((RedBlackTree)getRightTree());
					}
				}
			}

			if (!getRightTree().isEmpty()) {
				if ((((RedBlackTree)getRightTree()).isRedLink()) && (((RedBlackTree)getRightTree().getRightTree()).isRedLink()) ) {
					// Reference to rotated up parent.
					RedBlackTree newParent = (RedBlackTree)getRightTree();
					((RedBlackTreeHead)getHead()).rotateUp((RedBlackTree)getRightTree());
					newParent.setRedLink(false);
					((RedBlackTree)newParent.getLeftTree()).setRedLink(true);
				}
			}
		}
	}

	/**
	 * Finds the replacing node for a deletion. It simply searches down to the bottom of the tree
	 * Looking for the smallest element from the initial call.
	 *
	 * @return RedBlackTree that should be the smallest node.
	 */
	protected RedBlackTree findReplacingNode() {
		if (getLeftTree().isEmpty()) {
			return this;
		}
		else {
			return ((RedBlackTree)getLeftTree()).findReplacingNode();
		}
	}


	/**
     * Removes the BSTTree from the tree. The call bypasses the <code>BSTTree</code> by
     * partitioning the right subTree and replacing itself with the smallest of the right tree.
     */
	protected void remove() {
		BSTTree currentParent = (BSTTree)getParentTree();

		boolean left;

		if (this ==  currentParent.getLeftTree()) {
			left = true;
		}
		else {
			left = false;
		}

		BSTTree replacedNode;
		BSTTree childNode;

		if (getRightTree().isEmpty() || getLeftTree().isEmpty()) {
			replacedNode = this;
		}
		else {
			replacedNode = ((RedBlackTree)getRightTree()).findReplacingNode();
		}

		if (!replacedNode.getLeftTree().isEmpty()) {
			childNode = (BSTTree)replacedNode.getLeftTree();
		}
		else {
			childNode = (BSTTree)replacedNode.getRightTree();
		}

		childNode.setParentTree((BSTTree)replacedNode.getParentTree());


		if (replacedNode == ((BSTTree)replacedNode.getParentTree()).getLeftTree()) {
			((BSTTree)replacedNode.getParentTree()).setLeftTree(childNode);
		}
		else {
			((BSTTree)replacedNode.getParentTree()).setRightTree(childNode);
		}

		if (replacedNode != this) {
			// Actually copying.
			replacedNode.setParentTree(currentParent);
			if (left) {
				currentParent.setLeftTree(replacedNode);
			}
			else {
				currentParent.setRightTree(replacedNode);
			}

			replacedNode.setRightTree(this.getRightTree());
			((RedBlackTree)replacedNode.getRightTree()).setParentTree(replacedNode);

			replacedNode.setLeftTree(this.getLeftTree());
			((RedBlackTree)replacedNode.getLeftTree()).setParentTree(replacedNode);

			((RedBlackTree)replacedNode).setRedLink(this.isRedLink());

		}


		if (!((RedBlackTree)replacedNode).isRedLink() && !((RedBlackTreeHead)getHead()).isTreeAnimating()) {
			((RedBlackTree)childNode).fixUpRedBlackLinks();
		}

	}



	/**
	 * Fixes down to the bottom of the node passed, the red-black links. The pass down separates
	 * any 4-nodes and the way back up rotates if necessary.
	 */
	 protected void fixUpRedBlackLinks() {
		RedBlackTree currentNode = this;
		RedBlackTree currentNodeSibling;


		while ((currentNode.getParentTree() != getHead()) && (!currentNode.isRedLink())) {
			if (currentNode == ((RedBlackTree)currentNode.getParentTree()).getLeftTree()) {
				currentNodeSibling = (RedBlackTree)((RedBlackTree)currentNode.getParentTree()).getRightTree();
				if (currentNodeSibling.isRedLink()) {
					currentNodeSibling.setRedLink(false);
					((RedBlackTree)currentNode.getParentTree()).setRedLink(true);

					((RedBlackTreeHead)getHead()).rotateUp(currentNodeSibling);

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

				}
				if (currentNodeSibling.isEmpty()) {
					break;
				}
				if ( (!((RedBlackTree)currentNodeSibling.getLeftTree()).isRedLink()) && (!((RedBlackTree)currentNodeSibling.getRightTree()).isRedLink()) ){
					currentNodeSibling.setRedLink(true);
					currentNode = (RedBlackTree)currentNode.getParentTree();
				}
				else {
					if (!((RedBlackTree)currentNodeSibling.getRightTree()).isRedLink()) {
						((RedBlackTree)currentNodeSibling.getLeftTree()).setRedLink(false);
						currentNodeSibling.setRedLink(true);

						((RedBlackTreeHead)getHead()).rotateUp((RedBlackTree)currentNodeSibling.getLeftTree());

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

					currentNodeSibling.setRedLink(((RedBlackTree)currentNode.getParentTree()).isRedLink());
					((RedBlackTree)currentNode.getParentTree()).setRedLink(false);
					((RedBlackTree)currentNodeSibling.getRightTree()).setRedLink(false);

					((RedBlackTreeHead)getHead()).rotateUp(currentNodeSibling);

					break;
				}
			}
			else {
				currentNodeSibling = (RedBlackTree)((RedBlackTree)currentNode.getParentTree()).getLeftTree();
				if (currentNodeSibling.isRedLink()) {
					currentNodeSibling.setRedLink(false);
					((RedBlackTree)currentNode.getParentTree()).setRedLink(true);

					((RedBlackTreeHead)getHead()).rotateUp(currentNodeSibling);
					currentNodeSibling = (RedBlackTree)((RedBlackTree)currentNode.getParentTree()).getLeftTree();

				}

				if (currentNodeSibling.isEmpty()) {
					break;
				}
				if ( !((RedBlackTree)currentNodeSibling.getRightTree()).isRedLink() && !((RedBlackTree)currentNodeSibling.getLeftTree()).isRedLink() ){
					currentNodeSibling.setRedLink(true);
					currentNode = (RedBlackTree)currentNode.getParentTree();
				}
				else {
					if (!((RedBlackTree)currentNodeSibling.getLeftTree()).isRedLink()) {
						((RedBlackTree)currentNodeSibling.getRightTree()).setRedLink(false);
						currentNodeSibling.setRedLink(true);

						((RedBlackTreeHead)getHead()).rotateUp((RedBlackTree)currentNodeSibling.getRightTree());

						currentNodeSibling = (RedBlackTree)((RedBlackTree)currentNode.getParentTree()).getLeftTree();
					}

					currentNodeSibling.setRedLink(((RedBlackTree)currentNode.getParentTree()).isRedLink());
					((RedBlackTree)currentNode.getParentTree()).setRedLink(false);
					((RedBlackTree)currentNodeSibling.getLeftTree()).setRedLink(false);

					((RedBlackTreeHead)getHead()).rotateUp(currentNodeSibling);

					break;
				}
			}
		}

		currentNode.setRedLink(false);


	}








	/*-----------------------------------------------------------------------*/
    /*-------------------------------BST_TREE_TYPE---------------------------*/
	/*------------------------------------END--------------------------------*/
	/*-----------------------------------------------------------------------*/




    /*/////////////////////////////////////\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/
    /*\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\//////////////////////////////////*/




	/*-----------------------------------------------------------------------*/
    /*----------------------------DRAWING_BST_TREE_TYPE----------------------*/
	/*-----------------------------------START-------------------------------*/
	/*-----------------------------------------------------------------------*/



	/*************************************************************************/
	/* DRAWING_BST_TREE_TYPE : Methods and Variables specific to the         */
	/* DRAWING_BST_TREE_TYPE.  These methods are specificaly used for drawing*/
	/* to a Graphics2D. Therefore, do not use this type unless that is your  */
	/* purpose.        														 */
	/*************************************************************************/

	/**
	 * The current redLinkPaint (Red Default...heh heh OBVIOUSLY)
	 */
	private PaintSettings redLinkPaint = PaintSettings.getScheme(PaintSettings.RED);

	/**
	 * The current redLinkStroke (BasicStroke(2.0F) Default)
	 */
	private Stroke redLinkStroke = new BasicStroke(2.0F);


	/**
 	 *******************************************
	 * DRAWING_BST_TREE_TYPE Accesssor methods *
	 *******************************************
	 */

	/**
	 * Gets the red link paint for the current <code>RedBlackTree</code>.
	 *
	 * @return the paint for the red links of the drawing node.
	 */
	public PaintSettings getRedLinkPaint() {
		return redLinkPaint;
	}

	/**
	 * Gets the red link stroke for the current <code>RedBlackTree</code>.
	 *
	 * @return the stroke for the red links of the drawing node.
	 */
	public Stroke getRedLinkStroke() {
		return redLinkStroke;
	}

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

	/**
	 * Sets the red link paint for the current <code>RedBlackTree</code>.
	 *
	 * @param redLinkPaint the paint for the red links of the drawing node.
	 */
	public void setRedLinkPaint(PaintSettings redLinkPaint) {
		this.redLinkPaint = redLinkPaint;
	}


	/**
	 * Gets the red link stroke for the current <code>RedBlackTree</code>.
	 *
	 * @return the stroke for the red links of the drawing node.
	 */
	public void setRedLinkStroke(Stroke redLinkStroke) {
		this.redLinkStroke = redLinkStroke;
	}

	/**
	 * Sets the settings of the entire tree. This represents a recursive call through the tree,
	 * setting the tree's NodeSettings and then calling both children.
	 *
	 * @param s NodeSettings being set for the entire tree.
	 */
	protected void setTreeSettings(NodeSettings s, KeySettings k, PaintSettings redLinkPaint, Stroke redLinkStroke) {

		if (!isDrawingBSTTree())
			return;

		if(isEmpty())
			return;

		setSettings(s);
		((DrawableKey)getValue()).setSettings(k);
		setRedLinkPaint(redLinkPaint);
		setRedLinkStroke(redLinkStroke);


		((RedBlackTree)getLeftTree()).setTreeSettings(s, k, redLinkPaint, redLinkStroke);
		((RedBlackTree)getRightTree()).setTreeSettings(s, k, redLinkPaint, redLinkStroke);
	}

	/**
 	 *****************************************************************
	 * DRAWING_BST_TREE_TYPE Drawing methods (DrawingTree Interface) *
	 *****************************************************************
	 */

	/**
	 * Draws just the right link according to the NodeSettings currently set.
	 *
	 * @param g2 graphics to which the node and links are drawn.
	 * @param sectionHeight the height of the tree' section, to draw the correct lengths for the links.
	 * @param a transfrom to draw the node and links.
	 * @param drawingLevel the level in the tree to which the node is currently being drawn.
	 * @param powerLevel the power to which the links extend, depending on how many links are present.
	 * @param bottomLinks the boolean to declare whether the bottom links should be drawn.
	 */
	 protected void drawRightLink(Graphics2D g2, double sectionHeight, AffineTransform a, double drawingLevel, double powerLevel, boolean bottomLinks) {

		Rectangle2D bounds = g2.getClipBounds();

		// Right line
		Line2D.Double right = new Line2D.Double( (a.getTranslateX() + (3*a.getScaleX())/4.0) , (a.getTranslateY() + a.getScaleY()/2.0) , (a.getTranslateX() + a.getScaleX()/2.0 + bounds.getWidth()/powerLevel) , (sectionHeight * drawingLevel));

		// Set graphics information
		if (!(getRightTree().isEmpty()) && ((RedBlackTree)getRightTree()).isRedLink()) {
			g2.setStroke(getRedLinkStroke());
			g2.setPaint(getRedLinkPaint().getPaint());
		}
		else {
			g2.setStroke(getSettings().getRightLinkStroke());
			g2.setPaint(getSettings().getRightLinkPaint());
		}


		g2.setComposite(getSettings().getRightLinkComposite());
		g2.draw(right);

	}

	/**
	 * Draws just the left link according to the NodeSettings currently set.
	 *
	 * @param g2 graphics to which the node and links are drawn.
	 * @param sectionHeight the height of the tree' section, to draw the correct lengths for the links.
	 * @param a transfrom to draw the node and links.
	 * @param drawingLevel the level in the tree to which the node is currently being drawn.
	 * @param powerLevel the power to which the links extend, depending on how many links are present.
	 * @param bottomLinks the boolean to declare whether the bottom links should be drawn.
	 */
	  protected void drawLeftLink(Graphics2D g2, double sectionHeight, AffineTransform a, double drawingLevel, double powerLevel, boolean bottomLinks) {

		Rectangle2D bounds = g2.getClipBounds();

		// Draw the left and right links
		Line2D.Double left = new Line2D.Double( (a.getTranslateX() + a.getScaleX()/4.0) , (a.getTranslateY() + a.getScaleY()/2.0) , (a.getTranslateX() + a.getScaleX()/2.0 - bounds.getWidth()/powerLevel) , (sectionHeight * drawingLevel));

		// Set graphics information
		if (!(getLeftTree().isEmpty()) && ((RedBlackTree)getLeftTree()).isRedLink()) {
			g2.setStroke(getRedLinkStroke());
			g2.setPaint(getRedLinkPaint().getPaint());
		}
		else {
			g2.setStroke(getSettings().getRightLinkStroke());
			g2.setPaint(getSettings().getRightLinkPaint());
		}


		g2.setComposite(getSettings().getRightLinkComposite());
		g2.draw(left);
	}


	/*-----------------------------------------------------------------------*/
    /*----------------------------DRAWING_BST_TREE_TYPE----------------------*/
	/*------------------------------------END--------------------------------*/
	/*-----------------------------------------------------------------------*/




    /*/////////////////////////////////////\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/
    /*\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\//////////////////////////////////*/




	/*-----------------------------------------------------------------------*/
    /*---------------------------ANIMATING_BST_TREE_TYPE---------------------*/
	/*-----------------------------------START-------------------------------*/
	/*-----------------------------------------------------------------------*/



	/*************************************************************************/
	/* ANIMATING_BST_TREE_TYPE : Methods and Variables specific to the       */
	/* ANIMATING_BST_TREE_TYPE.  These methods are specificaly used for      */
	/* animaitng to a Graphics2D. Therefore, do not use this type unless     */
	/* that is your purpose.  												 */
	/*************************************************************************/


	/**
 	 *********************************************
	 * ANIMATING_BST_TREE_TYPE Accesssor methods *
	 *********************************************
	 */

	/**********************************/
	/* Recursive Constructing methods */
	/**********************************/

	/**
	 * Insert the <code>BSTTree</code> down from the current node. This is a recursive call,
	 * defined in <code>BSTTree</code>. It is overiden in this class to build the animation
	 * of the insertion. The reason this animation is overiden and not simply added in the AnimatingBSTTreeHead,
	 * is to allow multiple insertions to occur at once. Therefore, insertion never goes through
	 * <code>WaitingActionList</code>.
     *
     * @param node the node being inserted into the tree.
     * @param newAnimator the InsertBSTAnimation to which the nodes are being added.
     *
     * @throws    ClassCastException key cannot be compared with the keys
	 *		  currently in the tree.
     */
	protected void makeInsertAnimation(BSTTree insertNode, InsertRedBlackAnimation newAnimator) throws ClassCastException {


		if (!isAnimatingBSTTree()) {
			return;
		}

		if (isEmpty()) {
			return;
		}


		// Add the animator to the Insertion animation.
		newAnimator.add(this);

		if ((insertNode.getKey()).compareTo(getKey()) < 0) { // Go to the left
			((RedBlackTree)getLeftTree()).makeInsertAnimation(insertNode, newAnimator);
		}
		else { // Go to the right
			((RedBlackTree)getRightTree()).makeInsertAnimation(insertNode, newAnimator);
		}

	}


}