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

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


/** * This class provides the head structure for a <code>RedBlackTree</code>. It implements the
  	* interface for TreeHead and implements all important methods necessary for maintaining a
  	* Red-Black 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 RedBlackTreeHead extends BSTTreeHead {


	/*************************************************************************/
	/* BSTTreeHead constructor, methods, and variables, regardless of type.  */
	/*************************************************************************/


	/**
	 * String representing information regarding the type of tree.
	 */
	public static final String TREE_INFORMATION =
	"A red-black BST is a binary search tree in which each node is marked to be either red\n"+
	"or black, with the additional restriction that no two red nodes appear consecutively on\n"+
	"any path from an external link to the root (Sedgewick, 558).\n\n"+
	"A balanced red-black BST is a red-black BST in which all paths from external links to\n"+
	"the root have the same number of black nodes (Sedgewick, 558).\n\n"+
	"Search Hits and Search Misses require about 1.002 lg N comparisons,\n"+
	"on the average, in a tree built from N random keys.\n\n"+
	"Search Hits and Search Misses can require 2 lg N + 2 comparisons in the worst case.\n";


	/**
	  * Constructs a new, null RedBlackTree, sorted according to the keys' natural
	  * order.
	  *
	  * <p><b>Default type is BST_TREE_TYPE.</b>
     */
     public RedBlackTreeHead() {
		 this(0);
 	 }

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

	/**
	 * Makes a new tree message. The method calls <code>messageAction</code> with the information
	 * necessary for the tree status. The information presented include :
	 * <ul>
	 *<li>Tree Type</li>
	 *<li>Tree Size</li>
	 *<li>Tree Level</li>
	 *</ul>
	 */
	public void TreeStatusMessage() {
		String treeStatusMsg = "Type = Red-Black "+getTreeTypeString()+"\n  Size = "+size()+
				      			"\n  Level = "+getTreeLevel();
		messageAction(treeStatusMsg, this);
	}


	/**
 	 ******************************************************************************
	 * BST_TREE_TYPE Static methods for determining best/average/worst case times *
	 ******************************************************************************
	 */


	  /**
	   * Returns the average Search hit time, according to n, the amount of elements in the tree.
	   *
	   * @param n the size of the tree for which the average search hit is needed.
	   *
	   * @return double the is the average search hit.
	   */
	   public double averageSearchHit(int n) {
		   return (Math.log((double)n) * 1.002);
	   }

	  /**
	   * Returns the average Search miss time, according to n, the amount of elements in the tree.
	   *
	   * @param n the size of the tree for which the average search hit is needed.
	   *
	   * @return double the is the average search hit.
	   */
	   public double averageSearchMiss(int n) {
		   return (Math.log((double)n) * 1.002);
	   }



	  /**
	   * Returns the worst case Search hit time, according to n, the amount of elements in the tree.
	   *
	   * @param n the size of the tree for which the worst case search hit is needed.
	   *
	   * @return double the is the worst case search hit.
	   */
	   public double worstCaseSearchHit(int n) {
		   return (Math.log((double)n) * 2 + 2);;
	   }

	  /**
	   * Returns the worst case Search miss time, according to n, the amount of elements in the tree.
	   *
	   * @param n the size of the tree for which the worst case search hit is needed.
	   *
	   * @return double the is the worst case search hit.
	   */
	   public double worstCaseSearchMiss(int n) {
		   return (Math.log((double)n) * 2 + 2);;
	   }

	  /**
	   * Returns the average Insertion time, according to n, the amount of elements in the tree.
	   *
	   * @param n the size of the tree for which the average search hit is needed.
	   *
	   * @return double the is the average search hit.
	   */
	   public double averageInsertion(int n) {
		   return (Math.log((double)n) * 1.002);
	   }

	  /**
	   * Returns the worst case Insertion time, according to n, the amount of elements in the tree.
	   *
	   * @param n the size of the tree for which the worst case search hit is needed.
	   *
	   * @return double the is the worst case search hit.
	   */
	   public double worstCaseInsertion(int n) {
		  return (Math.log((double)n) * 2 + 2);;
	   }


	/**
	 **********************************
	 * Waiting Action Method          *
	 **********************************
	 */

	/**
	 * Acts according to the String action passed. The method generally accompanies
	 * a <code>WaitingActionList</code> which keeps the list of actions, and calls the method when
	 * instructed to call the next action.
	 *
	 * @param action String action representing the next action for the BSTTreeHead.
	 * @param elements elemetns to which the action could be occuring, depending on the type of action.
	 */
	public void waitingAction(String action, Object element) {
		if (action.equals(TreeHead.INSERT_NODE)) {
			insertAnimatingType((RedBlackTree)element);
		}
		else {
			super.waitingAction(action, element);
		}
	}

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


	/**
 	 ************************************************************************
	 * BST_TREE_TYPE Original Methods(Overiden in ANIMATING_BST_TREE_TYPE   *
	 ************************************************************************
	 */


	/**
	 * Sets the child of the TreeHead and sets its red link to false.
	 *
	 * @param child <code>Tree</code>, beginning the <code>Tree</code> nodes.
	 */
	public void setChild(Tree child) {
		super.setChild(child);
	}

	/**
	 * Makes and places the node into the tree. The node is returned for further manipulation.
	 *
	 * @param keyInsert	comparable object which is added to the tree.
	 * @param valueInsert Object that accompanies keyInsert in the node.
	 *
	 * @return BSTTree that was recently inserted into the tree.
	 *
	 * @throws    ClassCastException key cannot be compared with the keys
	 *		  currently in the map.
	 */
	protected BSTTree makeNodeTreeType(Comparable keyInsert, Object valueInsert) {

		// Get node from node factory.
		RedBlackTree newTree = new RedBlackTree(getTreeType());
		newTree.setHead(this);

		// Set the null leaves.
		newTree.setLeaf();

		((BSTTree)newTree.getRightTree()).setHead(this);
		((BSTTree)newTree.getLeftTree()).setHead(this);


		// Set the values of the node.
		newTree.setNode(keyInsert, valueInsert);

		return newTree;
	}




	/*-----------------------------------------------------------------------*/
    /*-------------------------------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 <code>NodeSettings</code> for the entire tree from the head down.
	 * These settings are used for drawing the node and the links of each given tree.
	 *
	 * @param s <code>NodeSettings</code> for use in drawing the entire tree.
	 * @param k <code>KeySettings</code> for use in drawing the keys of the entire tree.
	 */
	public void setTreeSettings(NodeSettings s, KeySettings k, PaintSettings redLinkPaint, Stroke redLinkStroke) {

		if (!isDrawingBSTTree())
			return;

		setDrawingNodeSettings(s);
		setDrawingKeySettings(k);
		setRedLinkPaint(redLinkPaint);
		setRedLinkStroke(redLinkStroke);

		if (!isTreeEmpty()) {
			((RedBlackTree)getChild()).setTreeSettings(s, k, redLinkPaint, redLinkStroke);
		}

	}


	/*-----------------------------------------------------------------------*/
    /*---------------------------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 Overiding methods *
	 *********************************************
	 */

	/**
	 * Insert the comaparable node to the tree using its <i> natural ordering </i>.
	 *
	 * <p><b> Call to <code>insertDrawingType</code> </b>
	 *
	 * @param node BSTTree node to be inserted into the tree
	 * @throws    ClassCastException key cannot be compared with the keys
	 *		  currently in the map.
	 */
	protected void insertAnimatingType(BSTTree node) throws ClassCastException {


		if ((!isAnimatingBSTTree()) || (isTreeEmpty())) {
			((RedBlackTree)node).setRedLink(true);
			insertDrawingType(node);
			return;
		}


		// If Animation is occuring, add ROTATE_UP to the waitingList.
		if (isTreeAnimating()) {
			getWaitingList().add(AnimatingTreeHead.INSERT_NODE, node);
			return;
		}


		Animation insertAnimator = makeInsertAnimation(node);

		// Add animation and recieve listening events.
		this.addTreeAnimator(insertAnimator);
		insertAnimator.addAnimationListener(this);

		// Add animation to the inserting node.
		node.addAnimator(insertAnimator);
		insertAnimator.addAnimationListener(node);


		// Super call
		insertDrawingType(node);

		// Add the final location, after the tree is built.
		((InsertRedBlackAnimation)insertAnimator).add(node);

	}


	/**
 	 ****************************************************
	 * ANIMATING_BST_TREE_TYPE Constructing Animations  *
	 ****************************************************
	 */


	/**
	 * Makes an insert Animation using the given node. The Animation adds no listeners, making
	 * the client have to add the listeners.
	 *
	 * @param insertNode BSTTree node that the insert Animation is built for.
	 * @return Animation that represents the insertAnimation.
	 */
	public Animation makeInsertAnimation(BSTTree insertNode) {

		if (!isAnimatingBSTTree()) {
			return null;
		}

		// Head node (backup test).
		if (insertNode == this)
			return null;

		// Construct animation for Insert.
		InsertRedBlackAnimation newAnimator = new InsertRedBlackAnimation(insertNode,getInsertNodeLeftSettings(),getInsertNodeRightSettings(),getInsertAnimatorNodeSettings(), getInsertAnimatorKeySettings(), getTreeStatus(), getTreeAnimationStepSize());

		// Starting Animation.
		AffineTransform a = AffineTransform.getScaleInstance(getScreenBounds().getWidth() * .35, getScreenBounds().getHeight() * .35);


		// Add initial animation.
		newAnimator.add(a);

		// Recursive call to insert the tree, starting at the head level.
		((RedBlackTree)getChild()).makeInsertAnimation(insertNode, newAnimator);

		return newAnimator;

	}



	/**
	 * Makes a delete Animation using the given node. The Animation adds no listeners, making
	 * the client have to add the listeners.
	 *
	 * @param node BSTTree node that the deletion Animation is built from.
	 * @return Animation that represents the deleteAnimation.
	 */
	public Animation makeDeletionAnimation(BSTTree node) {

		if (!isAnimatingBSTTree()) {
			return null;
		}

		// If this is the node to be deleted (precautionary check).
		if (node == this)
			return null;

		// New deletion animation.
		DeleteRedBlackAnimation newAnimator = new DeleteRedBlackAnimation(node, getDeleteLeftLinePaintSettings(), getDeleteRightLinePaintSettings(), getTreeStatus(), getTreeAnimationStepSize());

		return newAnimator;
	}

}