/*
 * @(#)BSTTree.java
 *
 * Last Modified: 8/06/02
 */

 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>BSTTree</code>, a node of the Binary Search 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 BSTTree defines methods necessary for a BSTTree, a DrawingBSTTree, and an AnimatingBSTTree.
	* The type is set when the node is constructed but can be changed in the middle. If a method is
	* called for a type that is higher is level than the type of the tree, the method will be ignored.
	*
    * <p> <i>A <b>Binary Search Tree</b> is a binary tree that has a key associated with each
    * of its internal nodes, with the additional property that the key in any node is larger than
    * (or eqaul to) that keys in all nodes in that node's left subtree and smaller than (or equal to)
    * the keys in all nodes in the node's right subtree. </i> (Sedgewick, 502, <i>Algorithms in C</i>)
    *
    * <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 BSTTree implements Tree, DrawingTree, AnimationListener, AnimatingTree  {


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

	/**
	 * Tree type defining only a BSTTree. The Drawing and Animating methods will not be available.
	 */
	public final static int BST_TREE_TYPE = 0;

	/**
	 * Tree type defining a DrawingBSTTree. The Animating methods will not be available.
	 */
	public final static int DRAWING_BST_TREE_TYPE = 1;

	/**
	 * Tree type defining AnimatingBSTTree. All methods will be available and all animations will occur.
	 */
	public final static int ANIMATING_BST_TREE_TYPE = 2;

	/**
	 * Stores the type of tree the BSTTree is.
	 */
	 private int treeType;


	 /**
	  * Constructs a new, empty BSTTree, sorted according to the keys' natural
	  * order.  All keys inserted into the tree must implement the
	  * <tt>Comparable</tt> interface.  Furthermore, all such keys must be
	  * <i>mutually comparable</i>: <tt>k1.compareTo(k2)</tt> must not throw a
	  * ClassCastException for any elements <tt>k1</tt> and <tt>k2</tt> in the
	  * tree.  If the user attempts to put a key into the tree that violates this
	  * constraint (for example, the user attempts to put a string key into a
	  * map whose keys are integers), the <tt>add(Comparable key, Object
	  * value)</tt> call will throw a <tt>ClassCastException</tt>.
	  *
	  * <p><b>Default type is BST_TREE_TYPE.</b>
     */
     public BSTTree() {
		 this(0);
 	 }

 	 /**
 	  * Constructs a new, empty BSTTree according to the type passed. The options for the
 	  * types are BST_TREE_TYPE, DRAWING_BST_TREE_TYPE, and ANIMATING_BST_TREE_TYPE. The
 	  * types are defined as follows:
 	  * <ul>
 	  * <li><b>BST_TREE_TYPE</b>: Only implements the basic methods of a Binary Search Tree.
 	  * A lot of the expensive (huge overhead) information necessary for drawing and animating
 	  * are left not instantiated to save time. This basic type is simply for BST usage.</li>
 	  * <li><b>DRAWING_BST_TREE_TYPE</b>: Implements the methods necessary to draw the BST onto
 	  * the screen. This includes a lot of overhead data that is necessary for rendering the tree. </li>
 	  * <li><b>ANIMATING_BST_TREE_TYPE</b>: This implements the rest of the methods necessary to
 	  * animate the tree. The overhead is small for the animating methods, but for every method
 	  * possible, the animation occurs. Therefore, to stop animation, the node must be set to just
 	  * DRAWING_BST_TREE_TYPE and then the method will ignore the animation.</li></ul>
 	  *
 	  *@param treeType type of tree that should be implemented.
 	  */
 	  public BSTTree(int treeType) {
		  setTreeType(treeType);

	  }

	  /**
	   * Checks the tree type and determines the appropriate construction necessary.
	   * Generally called every time the tree type changes.
	   */
	   private void checkConstructors() {
		  if (getTreeType() >= BST_TREE_TYPE) {
			  constructBSTTree();
		  }
		  if (getTreeType() >= DRAWING_BST_TREE_TYPE) {
			  constructDrawingBSTTree();
		  }
		  if (getTreeType() >= ANIMATING_BST_TREE_TYPE) {
			  constructAnimatingBSTTree();
		  }
	  }

	  /**
	   * Sets the tree type for the BSTTree.
	   *
	   * @param treeType setting for the tree.
	   */
	   public void setTreeType(int treeType) {
		   this.treeType = treeType;

		   checkConstructors();
	   }

	  /**
	   * Gets the tree type for the BSTTree.
	   *
	   * @return tree type for the tree.
	   */
	   public int getTreeType() {
	 		return treeType;
	   }

	  /**
	   * Fixes the tree type for the entire BSTTree.
	   *
	   * @param treeType setting for the tree.
	   */
	   protected void fixTreeType(int treeType) {
	 		setTreeType(treeType);

	 		if (isEmpty())
	 			return;

	 		((BSTTree)getLeftTree()).fixTreeType(treeType);
	 		((BSTTree)getRightTree()).fixTreeType(treeType);
	   }

	  /**
	   * Gets the tree type String for the BSTTree.
	   *
	   * @return tree type String for the tree.
	   */
	   public String getTreeTypeString() {
	 		return "BST Tree";
	   }


	/**
	 * Returns true if the BSTTree is of type DrawingBSTTree or higher type.
	 *
	 * @return true if is is DRAWING_BST_TREE_TYPE.
	 */
	protected boolean isDrawingBSTTree() {
		return (treeType >= DRAWING_BST_TREE_TYPE);
	}

	/**
	 * Returns true if the BSTTree is of type AnimatingBSTTree.
	 *
	 * @return true if is is DRAWING_BST_TREE_TYPE.
	 */
	protected boolean isAnimatingBSTTree() {
		return (treeType >= ANIMATING_BST_TREE_TYPE);
	}

	/**
	* Copies the fields of this <code>BSTTree</code> into the <code>BSTTree</code> copy.
	* It simply copies it field by field, for usage when changes are made to the head node.<p>
	* If the tree type is Drawing or Animating, the method copies the fields accordingly.
	*
	* @param copy the <code>BSTTree</code> that takes the fields of the <code>BSTTree</code>.
	*/
	protected void copyBSTTree(BSTTree copy) {
		copy.key = key;
		copy.value = value;
		copy.left = left;
		if (left != null)
			left.parent = copy;
		copy.right = right;
		if (right != null)
			right.parent = copy;
		copy.parent = parent;
		copy.level = level;
		copy.size = size;

		if (isDrawingBSTTree()) {
			copy.setSettings((NodeSettings)(this.getSettings().clone()));
			((DrawableKey)copy.getValue()).setSettings((KeySettings)((DrawableKey)this.getValue()).getSettings().clone());
		}



	}


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


	/**
	 * The number of entries in the BSTTree.
	 */
	 private int size;

	 /**
	  * The amount of levels to the bottom of the tree.
	  */
	 private int level;

	 /**
	  * The left and right branches of the given tree.
	  */
	 private BSTTree left;
	 private BSTTree right;

	/**
	 * The key object in this current node.
	 */
	 private Comparable key;

	/**
	 * The key object in this current node.
	 */
	 private Object value;

	/**
	 * The count of the node in the inorder list.
	 */
	 private int inorder_count;

	 /**
	  * Parent link
	  */
	  private BSTTree parent;

	 /**
	  * Parent link
	  */
	  private BSTTreeHead head;

	/**
	 * Constructor for the BST_TREE_TYPE. This constructs and sets all values to defaults
	 * for the BST_TREE_TYPE.
	 */
	 public void constructBSTTree() {
		 if (getHead() == null && getParentTree() == null) {
		 	setSize(0);
		 	setLevel(0);
		 	setLeftTree(null);
		 	setRightTree(null);
		 	setNode(null, null);
		 	setParentTree(null);
		 	setHead(null);
		}
	 }


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

	/**
	 * Gets the head for the node. The head node is used in numerous operations and is
	 * the reference for the tree.
	 *
	 * @return BSTTreeHead that represents the head for this node, indicating the tree.
	 */
	public BSTTreeHead getHead() {
		return head;
	}

	/**
	 * Returns the number of nodes in the current Tree and below.
	 *
	 * @return the number of nodes in the current Tree and below.
	 */
	public int size() {
		return size;
    }

	/**
	 * Returns true if the current <code>BSTTree</code> is empty.
	 *
	 * @return the boolean true if the <code>BSTTree</code> is empty.
	 */
	public boolean isEmpty() {
		return (key == null);
	}


	/**
	 * Returns the value of the current <code>BSTTree</code>.
	 *
	 * @return the value of the current <code>BSTTree</code>.
	 */
	public Object getValue() {
		return value;
    }

	/**
	 * Returns the key of the current <code>BSTTree</code>.
	 *
	 * @return the key of the current <code>BSTTree</code>.
	 */
	public Comparable getKey() {
		return key;
    }


	/**
     * Gets the the level of the current <code>BSTTree</code>.
     * The level is the integer count of how far down the tree is to the current node.
     *
     * @return integer count of the level of the current <code>BSTTree</code>.
     */
	public int getLevel() {
		return level;
	}

	/**
	 * Returns the inorder count of the current node.
	 *
	 * @return the inorder count of the node.
	 */
	public int getInorderCount() {
		return inorder_count;
    }

	/**
     * Returns the left <code>BSTTree</code> of the current tree. Used to traverse down
     * the binary tree.
	 *
	 * @return <code>BSTTree</code> that is the left subtree of the current <code>BSTTree</code>,
	 * null of no such tree exists.
	 */
	public BSTTree getLeftTree() {
		return left;
	}

	/**
     * Returns the right <code>BSTTree</code> of the current tree. Used to traverse down
     * the binary tree.
	 *
	 * @return <code>BSTTree</code> that is the right subtree of the current <code>BSTTree</code>,
	 * null of no such tree exists.
	 */
	public BSTTree getRightTree() {
		return right;
	}


	/**
     * Returns the children of the current <code>Tree</code>.
	 *
	 * @return <code>Tree</code> array that is the children and null if the tree is an exterior node.
	 */
	public Tree[] getChildren() {
		BSTTree[] treeList = new BSTTree[2];
		treeList[0] = getLeftTree();
		treeList[1] = getRightTree();
		return treeList;
	}



	/**
     * Returns the parent of the current tree. Used to traverse up
     * the binary tree.
	 *
	 * @return Tree that is the parent of the current tree and null if the tree is the head.
	 */
	public Tree getParentTree() {
		return parent;
	}

	/**
     * Determines if the current node is within a BSTTree. It quickly checks if its parent
     * points to it, and if its two children point up to it. A quick check that does not go through
     * the entire tree.
	 *
	 * @return true if the node is within a BSTTree.
	 */
	public boolean inTree() {
		if (getLeftTree() == null || getRightTree() == null || ((BSTTree)getParentTree()) == null)
			return false;


		return
		 (
				(this.getLeftTree().getParentTree() == this)
		 	&& 	(this.getRightTree().getParentTree() == this)
		 	&& 	(( ((BSTTree)this.getParentTree()).getRightTree() == this)
		 		|| ( ((BSTTree)this.getParentTree()).getLeftTree() == this))
		 );
	}


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


	/**
	 * Sets the head for the node. The head node is used in numerous operations and is
	 * the reference for the tree. It is a protected class for changing the node results in
	 * changes to all operations (including <code>getLevel</code>).
	 *
	 * @param head TreeHead for the current node.
	 */
	protected void setHead(BSTTreeHead head) {
		this.head = head;
	}



	/**
	 * Sets the left tree for the node. The left and right tree are used in many operations.
	 * It is a protected class for changing the left results in
	 * changes to some operations.
	 *
	 * @param left BSTTree that sets the left link for the current node.
	 */
	protected void setLeftTree(BSTTree left) {
		this.left = left;
	}

	/**
	 * Sets the right tree for the node. The left and right tree are used in many operations.
	 * It is a protected class for changing the right results in
	 * changes to some operations.
	 *
	 * @param right BSTTree that sets the right link for the current node.
	 */
	protected void setRightTree(BSTTree right) {
		this.right = right;
	}

	/**
	 * Sets the parent tree for the node. The parent tree are used in many operations.
	 * It is a protected class for changing the parent results in
	 * changes to some operations.
	 *
	 * @param parent BSTTree that sets the parent link for the current node.
	 */
	protected void setParentTree(BSTTree parent) {
		this.parent = parent;
	}

	/**
     * Sets the the level of the current <code>BSTTree</code>.
     * The level sets the integer count of how far down the tree is.
     *
     * @param level the level set for the node.
     */
	protected void setLevel(int level) {
		this.level = level;
	}

	/**
     * Sets the the size of the current <code>BSTTree</code>.
     * The size represents the nodes below and including the current node.
     *
     * @param size integer setting the size of the node, which is the count of the nodes below
     * and including the current node.
     */
	protected void setSize(int size) {
		this.size = size;
	}

	/**
	 * Sets the inorder count of the current node.
     *
     * @param the inorder count for the node.
	 */
	protected void setInorderCount(int inorder_count) {
		this.inorder_count = inorder_count;
    }

	/**
     * Sets the key and value of the <code>BSTTree</code>. This is prtoected for usage by
     * extended classes but not for public access.
     *
     * @param keyInsert comparable object to be inserted as the key of the <code>BSTTree</code>.
     *
     * @param valueInsert object to be inserted as the value of the <code>BSTTree</code>.
     */
	protected void setNode(Comparable keyInsert, Object valueInsert) {
		key = keyInsert;
		value = valueInsert;
	}

	/**
     * Fixes the level of the node. Given the currentLevel of the BSTtree, the level of each successive BSTtree (both left
     * and right) are fixed until the leaf nodes are reached. The method call is recursive.
     *
     * @param currentLevel currentLevel of the <code>BSTTree</code>
     *
	*/
	protected void fixLevel(int currentLevel) {
		if (isEmpty()) {
			return;
		}

		this.level = currentLevel;

		left.fixLevel(currentLevel+1);
		right.fixLevel(currentLevel+1);

		if (currentLevel > getHead().getTreeLevel()) {
			getHead().setTreeLevel(currentLevel);
		}

		return;

	}

	/**
     * Fixes the size of the node. The method call is recursive.
     *
     *
     * @return integer of the size fixed, which is passed up through the BSTTree, recursively.
     */
	protected int fixSize() {
		if (isEmpty()) {
			return 0;
		}

		setSize(left.fixSize() + right.fixSize() + 1);

		return size();
	}


	/**
     * 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 BSTTree(getTreeType()));
		setRightTree(new BSTTree(getTreeType()));
		getLeftTree().setParentTree(this);
		getRightTree().setParentTree(this);
	}

	/**
 	 **********************************
	 * 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.
     *
     * @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 {
		currentLevel++; // Increments the level.

		if ((newTree.getKey()).compareTo(getKey()) < 0) { // Go to the left
			if(getLeftTree().isEmpty()) { // Leaf of tree
				setLeftTree(newTree); // Set tree.
				getLeftTree().setParentTree(this); // Set parent.
				getLeftTree().setLevel(currentLevel+1); // Increase level

				if (getLeftTree().getLevel() > getHead().getTreeLevel())
					getHead().setTreeLevel(getLeftTree().getLevel());

				getLeftTree().setSize(1); // Set initial size
			}
			else
				getLeftTree().insert(newTree, currentLevel);


		}
		else { // Go to the right
			if(getRightTree().isEmpty()) { // Leaf of tree
				setRightTree(newTree); // Set tree.
				getRightTree().setParentTree(this); // Set parent.
				getRightTree().setLevel(currentLevel+1); // Increase level

				if (getRightTree().getLevel() > getHead().getTreeLevel())
					getHead().setTreeLevel(getRightTree().getLevel());

				getRightTree().setSize(1); // Set initial size
			}
			else
				getRightTree().insert(newTree, currentLevel);

		}


		// Set the size as one plus the left and sizes.
		setSize(getLeftTree().size() + getRightTree().size() + 1);

		return;

	}




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

		// Gets the smallest of the right tree.
		BSTTree temp = join(getLeftTree(), getRightTree());

		// Replaces links
		if (this == currentParent.getLeftTree()) {
			currentParent.setLeftTree(temp);
		}
		else {
			currentParent.setRightTree(temp);
		}

		temp.setParentTree(currentParent);

		if (temp.isEmpty())
			return;

		// fixes the size
		temp.setSize(temp.getLeftTree().size() + temp.getRightTree().size() + 1);

	}


	/**
     * Finds a node within a tree using the comparable keyFind. Null is returned if the
     * key is not within the tree and the node is returned otherwise. The method is a recursive
     * call.
     *
     * @param keyFind the key which the method is attempting to find.
     * @return Tree which contains the keyFind as a key or the last examined tree if the keyFind is not present
     * in the entire tree.
     */
	protected Tree search(Comparable keyFind) throws ClassCastException {

		if(isEmpty()) {
			return getParentTree();
		}
		// Go left
		if (keyFind.compareTo(getKey()) < 0) {
			return getLeftTree().search(keyFind);
		}
		// Go right
		if (keyFind.compareTo(getKey()) > 0) {
			return getRightTree().search(keyFind);
		}
		else { // Equal (Match)
			return this;
		}
	}


   /**
	* Selects for the <code>Tree</code> in the entire tree.
	*
	* @param keySelect integer key selecting the count item.
	* @return Tree the <code>Tree</code> found or null.
	*/
	protected Tree select(int keySelect) {

		if(isEmpty()) {
			return null;
		}

		if (getLeftTree().size() > keySelect) {
			return getLeftTree().select(keySelect);
		}
		else if (getLeftTree().size() < keySelect) {
			return getRightTree().select(keySelect - getLeftTree().size() - 1);
		}

		return this;
	}

	/**
	* Partitions the <code>Tree</code> at the given keySelect and rotates the keySelectth node
	* to this node's position. A recursive call generally called from the head
	*
	* @param keySelect integer key selecting the count item.
	* @param levelCount integer counting the levels down the partition is going.
	*
	* @return BSTTree that is the reference to the newly partitioned tree.
	*/
	protected BSTTree partition(int keySelect, int levelCount) {

		BSTTree newNode;

		if (getLeftTree().size() > keySelect) {
			// Recursive call
			return getLeftTree().partition(keySelect, levelCount + 1);

		}
		else if (getLeftTree().size()  < keySelect) {
			return getRightTree().partition(keySelect - getLeftTree().size() - 1, levelCount + 1);
		}

		// Rotate Up the amount of levels the partition went down.
		((BSTTreeHead)getHead()).rotateUp(this, levelCount);

		return this;
	}


   /**
	* Rotate the tree to the right. It simply changes around references to BSTTrees.
	*
	* @return BSTTree that is the reference to the newly rotated tree.
	*/
	protected BSTTree rotateRight() {

		BSTTree temp = (BSTTree)getLeftTree();
		setLeftTree((BSTTree)temp.getRightTree());
		getLeftTree().setParentTree(this);
		temp.setRightTree(this);

		setParentTree(temp);

		temp.setParentTree(null);


		// Fix sizes
		setSize(getLeftTree().size() + getRightTree().size() + 1);
		temp.setSize(temp.getLeftTree().size() + temp.getRightTree().size() + 1);

		return temp;

	}


	/**
	* Rotate the tree to the left. It simply changes around references to BSTTrees.
	*
	* @return BSTTree that is the reference to the newly rotated tree.
	*/
	protected BSTTree rotateLeft() {
		BSTTree temp = (BSTTree)getRightTree();
		setRightTree((BSTTree)temp.getLeftTree());
		getRightTree().setParentTree(this);
		temp.setLeftTree(this);

		setParentTree(temp);

		temp.setParentTree(null);

		// Fix sizes
		setSize(getLeftTree().size() + getRightTree().size() + 1);
		temp.setSize(temp.getLeftTree().size() + temp.getRightTree().size() + 1);

		return temp;
	}




   /**
	* Joins two subtrees together as one tree. It takes the greater subtree and
	* partitions the smallest element to the root. Then it makes that new head
	* element's left subtree the smaller subtree.
	*
	* @param treeJoinOne one subtree to be joined.
	* @param treeJoinTwo second subtree to be joined.
	*
	* @return BSTTree object which is the new reference to the joined tree.
	*/

	protected static BSTTree join(BSTTree treeJoinOne, BSTTree treeJoinTwo) {


		// Empty trees
		if (treeJoinTwo.isEmpty()) {
			return treeJoinOne;
		}

		if (treeJoinOne.isEmpty()) {
			return treeJoinTwo;
		}

		BSTTree returnTree;

		// Tree one is less than tree two
		if (treeJoinOne.getKey().compareTo(treeJoinTwo.getKey()) < 0) {

			treeJoinOne.setParentTree(treeJoinTwo.partition(0, 0));
			((BSTTree)treeJoinOne.getParentTree()).setLeftTree(treeJoinOne);

			((BSTTree)treeJoinOne.getParentTree()).setSize(((BSTTree)treeJoinOne.getParentTree()).getLeftTree().size() + ((BSTTree)treeJoinOne.getParentTree()).getRightTree().size() + 1);

			return ((BSTTree)treeJoinOne.getParentTree());
		}
		else {


			treeJoinTwo.setParentTree(treeJoinOne.partition(0, 0));
			((BSTTree)treeJoinTwo.getParentTree()).setLeftTree(treeJoinTwo);

			((BSTTree)treeJoinTwo.getParentTree()).setSize(((BSTTree)treeJoinTwo.getParentTree()).getLeftTree().size() + ((BSTTree)treeJoinTwo.getParentTree()).getRightTree().size() + 1);


			return (BSTTree)treeJoinTwo.getParentTree();
		}

	}


	/**
	 **********************************
	 * Traversal Methods              *
	 **********************************
	 */

	/**
	 * Makes an array in preorder using recursive calls and the count. The BSTTree
	 * is traversed in preorder, adding the BSTTree objects in turn to the array.
	 *
	 * @param treeArray the array that has the BSTTree objects.
     */
	protected void makePreorderTree(LinkedList treeList) {
		if (isEmpty())
			return;

		// Push onto stack
		treeList.add(this);

		((BSTTree)getLeftTree()).makePreorderTree(treeList);
		((BSTTree)getRightTree()).makePreorderTree(treeList);

	}

	/**
	 * Makes an array in inorder using recursive calls and the count. The BSTTree
	 * is traversed in inorder, adding the BSTTree objects in turn to the array.
	 *
	 * @param treeArray the array that has the BSTTree objects.
     */
	protected void makeInorderTree(LinkedList treeList) {
		if (isEmpty())
			return;

		((BSTTree)getLeftTree()).makeInorderTree(treeList);

		// Push onto stack
		treeList.add(this);

		((BSTTree)getRightTree()).makeInorderTree(treeList);

	}



	/**
	 * Makes an array in postorder using recursive calls and the count. The BSTTree
	 * is traversed in postorder, adding the BSTTree objects in turn to the array.
	 *
	 * @param treeArray the array that has the BSTTree objects.
     */
	protected void makePostorderTree(LinkedList treeList) {
		if (isEmpty())
			return;


		((BSTTree)getLeftTree()).makePostorderTree(treeList);
		((BSTTree)getRightTree()).makePostorderTree(treeList);

		// Push onto stack
		treeList.add(this);

	}




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


	/**
	 * Bounds defining the screen in which the <code>DrawingTree</code> exists.
	 */
	private Rectangle2D screenBounds;

	/**
	 * Origin shape, defining the shape of the node at the origin and size 1.
	 */
	private Shape nodeOriginShape;

	/**
	 * Origin shape, defining the shape of the bounding box of the key contained within the nodeOriginShape.
	 */
	private Shape keyOriginRectangle;

	/**
	 * The current Shape of the <code>DrawingTree</code>, last drawn as this specific shape.
	 */
	private Shape currentShape;

	/**
	 * The current <code>AffineTransform</code> of the <code>DrawingTree</code>, representing the
	 * most current Transformation to draw the nodeOriginShape and keyOriginRectangle.
	 */
	private AffineTransform currentTransform;

	/**
	 * The previous <code>AffineTransform</code> of the <code>DrawingTree</code>.
	 */
	private AffineTransform previousTransform;

	/**
	 * The double drawing level for the current <code>DrawingTree</code>.
	 */
	private double drawingLevel;

	/**
	 * The current power of 2 representing, 2^drawinLevel.
	 */
	private double currentPower2;

	/**
	 * The current drawing settings of the node.
	 */
	private NodeSettings currentSettings = null;

	/**
	 * The previous drawing settings of the node.
	 */
	private NodeSettings previousSettings = null;

	/**
	 * The count for how many total saves the current Node has been called (to save the NodeSettings).
	 */
	private int countSaves = 0;

	/**
	 * The count for how many left saves the current Node has been called (<code>saveLeftSettings</code>).
	 */
	private int countLeftSaves = 0;

	/**
	 * The count for how many right saves the current Node has been called (<code>saveRightSettings</code>).
	 */
	private int countRightSaves = 0;

	/**
	 * Graphics2D for drawing the node on the previous graphics defined.
	 */
	 private Graphics2D graphics;




	/**
	 * Constructor for the DRAWING_BST_TREE_TYPE. This constructs and sets all values to defaults
	 * for the DRAWING_BST_TREE_TYPE.
	 */
	 public void constructDrawingBSTTree() {
		 if (currentSettings == null) {
		 	currentSettings = new NodeSettings();
		 	previousSettings = null;
		 	countSaves = 0;
		 	countLeftSaves = 0;
		 	countRightSaves = 0;
		 	currentTransform = null;
		 	previousTransform = null;
		 	newNodeShape();
		}
	 }



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

	/**
	 * Gets the drawing level for the current <code>DrawingTree</code>. This is a necessary method for allowing
	 * intermidiary drawing between two levels, because the param is a double, not an integer.
	 *
	 * @return the double level for the drawing node.
	 */
	public double getDrawingLevel() {
		return drawingLevel;
	}

	/**
	 * Gets the height of the section for the <code>DrawingTree</code>. The section height is generally
	 * used to determine link length and node height when drawing the tree.
	 *
	 * @return double height of the drawing section for the node.
	 */
	public double getSectionHeight() {
		return getHead().getTreeSectionHeight();

	}

	/**
	 * Gets the bounds of the screen to which the tree is drawing. The bounds generally is simply
	 * the rectangle enclosing the Graphics2D passed.
	 *
	 * @return the rectangle representing the bounds of the screen.
	 */
	public Rectangle2D getScreenBounds() {
		return screenBounds;
	}

	/**
	 * Gets the current power of 2 to which the tree was last drawn. The power is
	 * stored in this way to allow quick access and avoiding power methods.
	 *
	 * @return double power of 2 last used in drawing the tree (2^drawingLevel).
	 */
	public double getCurrentPower2() {
		return currentPower2;
	}

	/**
	 * Gets the <code>NodeSettings</code> of the tree.
	 * These settings are used for drawing the node and the links of the given tree.
	 *
	 * @return <code>NodeSettings</code> for use in drawing the tree.
	 */
	public NodeSettings getSettings() {
		return currentSettings;
	}

	/**
	 * Returns true if the settings are currently saved for the DrawingTree.
	 *
	 * @return true if the <code>NodeSettings</code> are saved.
	 */
	public boolean isSettingsSaved() {
		// Saved if previousSettings is not null.
		return (previousSettings != null);
	}

	/**
	 * Gets the shape of the node at the origin and size 1, for usage in
	 * transforming and drawing.
	 *
	 * @return <code>Shape</code> of the node at the origin and size 1.
	 */
	protected Shape getNodeOriginShape() {
		return nodeOriginShape;
	}

	/**
	 * Gets the shape of the key within the node shape at the origin and size 1,
	 * for usage in transforming and drawing.
	 *
	 * @return <code>Shape</code> of the key.
	 */
	protected Shape getKeyOriginRectangle() {
		return keyOriginRectangle;
	}

	/**
	 * Gets the shape of the node previously drawn or transformed.
	 *
	 * @return <code>Shape</code> of the node previously drawn.
	 */
	protected Shape getCurrentShape() {
		return currentShape;
	}

	/**
	 * Gets the <code>AffineTransform</code> defined within the tree. The current transform
	 * is used when calling <code>draw</code> without the <code>AffineTransform</code> value.
	 *
	 * @return transform set for the current drawing of the tree.
	 */
	public AffineTransform getCurrentTransform() {
		return currentTransform;
	}

	/**
	 * Gets the <code>AffineTransform</code> previously defined within the tree. The previous transform
	 * is used when calling <code>restoreTransform</code> and is automatically
	 * updates with each call of <code>setCurrentTransform</code>.
	 *
	 * @return transform previously set for the drawing of the tree.
	 */
	protected AffineTransform getPreviousTransform() {
		return previousTransform;
	}

	/**
	 * Gets the graphics previously defined within the tree. The graphics are defined in
	 * <code>makeTree</code> or by the client using <code>setCurrentGraphics</code>.
	 *
	 * @return Graphics2D which was the previously defined graphics.
	 */
	 public Graphics2D getCurrentGraphics() {
		 return graphics;
	 }

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

	/**
	 * Sets the drawing level for the current <code>DrawingTree</code>. This is a necessary method for allowing
	 * intermidiary drawing between two levels, because the param is a double, not an integer.
	 *
	 * @param level the double level for the drawing node.
	 */
	protected void setDrawingLevel(double level) {

		if (!isDrawingBSTTree())
			return;

		drawingLevel = level;
	}

	/**
	 * Sets the bounds of the screen to which the tree is drawing. Generally, these bounds
	 * are set using <code>getClipBounds</code> on the Graphics2D passed, however, the bounds
	 * can be set in any way.
	 *
	 * @param bounds the rectangle representing the bounds of the screen.
	 */
	public void setScreenBounds(Rectangle2D bounds) {

		if (!isDrawingBSTTree())
			return;


		screenBounds = bounds;
	}


	/**
	 * Sets the graphics defined within the tree.
	 *
	 * @param g2 Graphics2D which are the defined graphics for the tree.
	 */
	 public void setCurrentGraphics(Graphics2D g2) {
		 graphics = g2;
	 }



	/**
	 * Sets the current power of 2. The power is
	 * stored in this way to allow quick access and avoiding power methods.
	 *
	 * @return p2 power of 2 for drawing the tree (generally 2^drawingLevel).
	 */
	protected void setCurrentPower2(double p2) {

		if (!isDrawingBSTTree())
			return;

		currentPower2 = p2;
	}


	/**
	 * 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) {

		if (!isDrawingBSTTree())
			return;

		if(isEmpty())
			return;

		setSettings(s);
		((DrawableKey)getValue()).setSettings(k);


		getLeftTree().setTreeSettings(s, k);
		getRightTree().setTreeSettings(s, k);
	}

	/**
	 * Sets the settings of the node for the <code>BSTTree</code>. No settings are saved
	 * and the previous settings are not modified.
	 *
	 * @param s <code>NodeSettings</code> set for the entire tree.
	 */
	public void setNodeSettings(NodeSettings s) {
		currentSettings = (NodeSettings)s.clone();
	}


	/**
	 * Sets the <code>NodeSettings</code> of the <code>DrawingTree</code>.
	 * These settings are used for drawing the node and the links of the given tree.
	 * <p> If the settings are saved, the <b>previous</b> settings are modified to the <code>NodeSettings</code>,
	 * leaving the current settings unmodified. To modify the current settings, use <code>setNodeSettings</code>.
	 *
	 * If the settings are not saved, the previous settings are made null and the currentSettings are set.
	 *
	 * @param s <code>NodeSettings</code> for use in drawing the tree.
	 */
	public void setSettings(NodeSettings s) {

		NodeSettings newSettings = (NodeSettings)s.clone();

		if (!isDrawingBSTTree())
			return;

		// No previous saved settings
		if (!isSettingsSaved()) {
			// null previous settings
			previousSettings = null;
			currentSettings = newSettings;

			// Reset saves
			countSaves = 0;
			countLeftSaves = 0;
			countRightSaves = 0;
		}
		else {
			// Set previous settings as s, because currently the settings are saved.
			previousSettings = newSettings;
		}
	}


	/**
	 * Sets the <code>AffineTransform</code> defined within the tree. The set transform
	 * is used when calling <code>draw</code> without the <code>AffineTransform</code> value.
	 *
	 * @param a transform set for the current drawing of the tree.
	 */
	protected void setCurrentTransform(AffineTransform a) {

		if (!isDrawingBSTTree())
			return;

		previousTransform = currentTransform;
		currentTransform = a;
	}

	/**
	 * Restores the <code>AffineTransform</code> defined previously within the tree.
	 * The previous transform is always the last transform defined and is automatically
	 * updated each time <code>setCurrentTransform</code> is called.
	 */
	public void restoreTransform() {

		if (!isDrawingBSTTree())
			return;

		currentTransform = previousTransform;
	}



	/**
 	 *****************************************************
	 * DRAWING_BST_TREE_TYPE NodeSettings Saving methods *
	 *****************************************************
	 */


	/**
	 * Saves the settings for the tree, incrementing the count of saves by one and setting the
	 * previous settings accordingly.
	 */
	public void saveSettings() {

		if (!isDrawingBSTTree())
			return;

		countSaves++;
		if (previousSettings == null) {
			previousSettings = (NodeSettings)currentSettings.clone();
		}
	}

	/**
	 * Saves the settings for the tree, incrementing the count of left Saves and total saves by one and setting the
	 * previous settings accordingly.
	 */
	public void saveLeftSettings() {

		if (!isDrawingBSTTree())
			return;

		countLeftSaves++;
		saveSettings();
	}

	/**
	 * Saves the settings for the tree, incrementing the count of right Saves and total saves by one and setting the
	 * previous settings accordingly.
	 */
	public void saveRightSettings() {

		if (!isDrawingBSTTree())
			return;

		countRightSaves++;
		saveSettings();
	}

	/**
	 * Restores the settings for the tree, decrementing the count of left Saves and total saves by one.
	 * If the left settings have been restored completely, than the NodeSettings for the tree are set accordingly.
	 */
	public void restoreLeftSettings() {

		if (!isDrawingBSTTree())
			return;

		countLeftSaves--;

		if (countLeftSaves <= 0) { // Completely Restored
			currentSettings.setLeftSettings(previousSettings);
			countLeftSaves = 0;
		}
		restoreSettings();
	}

	/**
	 * Restores the settings for the tree, decrementing the count of right Saves and total saves by one.
	 * If the right settings have been restored completely, than the NodeSettings for the tree are set accordingly.
	 */
	public void restoreRightSettings() {

		if (!isDrawingBSTTree())
			return;

		countRightSaves--;

		if (countRightSaves <= 0) { // Completely Restored
			currentSettings.setRightSettings(previousSettings);
			countRightSaves = 0;
		}
		restoreSettings();
	}

	/**
	 * Restores the settings for the tree, decrementing the count of saves by one.
	 * If the settings have been restored completely, than the NodeSettings for the tree
	 * are set accordingly.
	 */
	public void restoreSettings() {

		if (!isDrawingBSTTree())
			return;

		countSaves--;
		if (countSaves <= 0) { // Completely Restored
			currentSettings = previousSettings;
			previousSettings = null;
			countSaves = 0;
			countRightSaves = 0;
			countLeftSaves = 0;
		}

	}


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


	/**
	 * Makes a new shape for the node and key. This method must be called to develop the nodeOriginShape and keyOriginRectangle, which
	 * is not modified or changed after the initial call. Basically, this instantiates the important
	 * data for the tree.
	 */
	private void newNodeShape() {
		// Bounds of the nodeShape.
		Rectangle2D nodeShapeBounds = getSettings().getNodeShape().getBounds2D();

		// Make the scale and translate transforms.
		AffineTransform scaleTransform = AffineTransform.getScaleInstance(1/nodeShapeBounds.getWidth() , 1/nodeShapeBounds.getHeight());
		AffineTransform translateTransform = AffineTransform.getTranslateInstance(-nodeShapeBounds.getX(), -nodeShapeBounds.getY());

		scaleTransform.concatenate(translateTransform);

		// Make the nodeOriginShape
		nodeOriginShape = scaleTransform.createTransformedShape(getSettings().getNodeShape());

		// Create Shape for key inside node.
		keyOriginRectangle = getSettings().getNodeShape().getInscribedRectangle();

		keyOriginRectangle = (scaleTransform.createTransformedShape(keyOriginRectangle)).getBounds2D();

	}

	/**
	 * Makes the tree recursively using the two parameters. The tree is made by setting the values using the
	 * following methods: <br>
	 * <ul>
	 * <li><code>setCurrentTransform</code></li>
	 * <li><code>setLevel</code></li>
	 * <li><code>setDrawingLevel</code></li>
	 * <li><code>setCurrentPower2</code></li>
	 * <li><code>setScreenBounds</code>(using head bounds)</li>
	 * </ul><p>
	 * The method calls the method for the left and right children, using properly modified
	 * <code>AffineTransform</code> and level.
	 *
	 * @param a <code>AffineTransform</code> for the current tree.
	 * @param currentLevel the current level for the tree.
	 */
	protected void makeTree(AffineTransform a, int currentLevel) {

		if (isEmpty())
			return;

		// Set the current values.
		setCurrentTransform(a);
		setLevel(currentLevel);
		setDrawingLevel((double)currentLevel);
		setCurrentPower2(Math.pow(2.0, currentLevel+1));
		// Bounds of the graphics
		setScreenBounds(getHead().getScreenBounds());


		// Make the left and right transforms.
		AffineTransform leftTransform = (AffineTransform)getCurrentTransform().clone();
		AffineTransform rightTransform = (AffineTransform)getCurrentTransform().clone();

		if ( ((BSTTreeHead)getHead()).getDisplay() == BSTTreeHead.SECTIONAL_DISPLAY) {
			a.translate(((getScreenBounds().getWidth() / getHead().size())*getInorderCount())/getCurrentTransform().getScaleX(), 0);
			// Set the current values.
			setCurrentTransform(a);

			leftTransform.translate(0, ( getHead().getSectionHeight()/getCurrentTransform().getScaleY()));
			rightTransform.translate(0, (getHead().getSectionHeight()/getCurrentTransform().getScaleY()));
		}
		else {

			leftTransform.translate(((-getScreenBounds().getWidth()/getCurrentPower2())/getCurrentTransform().getScaleX()), ( getHead().getSectionHeight()/getCurrentTransform().getScaleY()));
			rightTransform.translate(((getScreenBounds().getWidth()/getCurrentPower2())/getCurrentTransform().getScaleX()), (getHead().getSectionHeight()/getCurrentTransform().getScaleY()));
		}

		// Call the left and right tress.
		getLeftTree().makeTree(leftTransform, currentLevel+1);
		getRightTree().makeTree(rightTransform, currentLevel+1);

	}

	/**
	 * Draws the tree recursively, on to the Graphics2D. The current transform, drawing level,
	 * power, and screen bounds must all be set before the recursive method is called.
	 *
	 * @param g2 the Graphics2D to which the tree is drawn.
	 */
	protected void drawTree(Graphics2D g2) {
		if (isEmpty())
			return;

		setCurrentGraphics(g2);

		if (!isNodeAnimating()) {
			drawNodeAndLink(g2);
		}

		getLeftTree().drawTree(g2);
		getRightTree().drawTree(g2);
	}


	/**
	 * Draws the node of the tree using the previously defined graphics. The drawing uses
	 * the previously defined <code>AffineTransform</code>.
	 *
	 */
	public void drawNode() {
		NodeSettings temp = (NodeSettings)getSettings().clone();

		getSettings().setScheme(NodeSettings.ERASE, Color.black);

		drawNode(getCurrentGraphics());

		setNodeSettings(temp);

		drawNode(getCurrentGraphics());
	}


	/**
	 * Draws the node of the tree to the given Graphics2D. The drawing uses
	 * the previously defined <code>AffineTransform</code>.
	 *
	 * @param g2 graphics to which the node is drawn.
	 */
	public void drawNode(Graphics2D g2) {
		drawNode(g2, getCurrentTransform());
	}



	/**
	 * Draws the node of the tree to the given Graphics2D, using the <code>AffineTransform</code>.
	 * The drawing uses the <code>AffineTransform</code> to determine the exact way to draw the
	 * node.
	 *
	 * @param g2 graphics to which the node is drawn.
	 * @param a transform to draw the node.
	 */
	public void drawNode(Graphics2D g2, AffineTransform a) {

		currentShape = a.createTransformedShape(getNodeOriginShape());

		// Set graphics information
		g2.setComposite(getSettings().getNodeComposite());

		g2.setPaint(getSettings().getNodeFillPaint());
		g2.fill(currentShape);

		g2.setStroke(getSettings().getNodeOutlineStroke());
		g2.setPaint(getSettings().getNodeOutlinePaint());
		g2.draw(currentShape);

		// Get keyShape.
		Shape keyShape = a.createTransformedShape(getKeyOriginRectangle());

		// Bounding Box
		Rectangle2D keyBoundingBox = keyShape.getBounds2D();

		AffineTransform scaleTransform = AffineTransform.getScaleInstance(keyBoundingBox.getWidth() , keyBoundingBox.getHeight());
		AffineTransform translateTransform = AffineTransform.getTranslateInstance(keyBoundingBox.getX(), keyBoundingBox.getY());

		translateTransform.concatenate(scaleTransform);

		// Draws the key.
		((DrawableKey)getValue()).drawKey(g2, translateTransform);

	}


	/**
	 * Draws the node and left link of the tree using the previously defined graphics.
	 * The drawing uses the previously defined <code>AffineTransform</code>,
	 * section height, drawing level, and power level.
	 */
	public void drawNodeAndLeftLink() {

		boolean bottomLinks;

		if (getHead() != null) {
			bottomLinks = (((BSTTreeHead)getHead()).getDisplay() == BSTTreeHead.BINARY_DISPLAY);
		}
		else {
			bottomLinks = true;
		}

		// Redraw
		drawLeftLink(getCurrentGraphics(), getHead().getSectionHeight(), getCurrentTransform(), (double)getLevel(), getCurrentPower2(), bottomLinks);

		// Draw the node
		drawNode(getCurrentGraphics(), getCurrentTransform());
	}

	/**
	 * Draws the node and right link of the tree using the previously defined graphics.
	 * The drawing uses the previously defined <code>AffineTransform</code>,
	 * section height, drawing level, and power level.
	 */
	public void drawNodeAndRightLink() {


		boolean bottomLinks;

		if (getHead() != null) {
			bottomLinks = (((BSTTreeHead)getHead()).getDisplay() == BSTTreeHead.BINARY_DISPLAY);
		}
		else {
			bottomLinks = true;
		}

		// Redraw
		drawRightLink(getCurrentGraphics(), getHead().getSectionHeight(), getCurrentTransform(), (double)getLevel(), getCurrentPower2(), bottomLinks);

		// Draw the node
		drawNode(getCurrentGraphics(), getCurrentTransform());
	}

	/**
	 * Erases the previous drawing of the nodeAndLinkm, simply drawing.
	 */
	 public void eraseNodeAndLink() {
		// Copy the settings
		NodeSettings temp = (NodeSettings)getSettings();

		// Erase setting
		setNodeSettings(NodeSettings.getScheme(NodeSettings.ERASE, getHead().getBackgroundColor()));

		drawNodeAndLink(getCurrentGraphics());

		// Reset settings
		setNodeSettings(temp);
	}

	/**
	 * Draws the node and link of the tree using the previously defined graphics..
	 * The drawing uses the previously defined <code>AffineTransform</code>,
	 * section height, drawing level, and power level.
	 */
	public void drawNodeAndLink() {
		// Redraw
		drawNodeAndLink(getCurrentGraphics());

	}

	/**
	 * Draws the node and link of the tree to the given Graphics2D.
	 * The drawing generally uses the previously defined <code>AffineTransform</code>,
	 * section height, drawing level, and power level.
	 *
	 * @param g2 graphics to which the node is drawn.
	 */
	public void drawNodeAndLink(Graphics2D g2) {

		boolean bottomLinks;

		if (getHead() != null) {
			bottomLinks = (((BSTTreeHead)getHead()).getDisplay() == BSTTreeHead.BINARY_DISPLAY);
		}
		else {
			bottomLinks = true;
		}

		drawNodeAndLink(g2, getHead().getSectionHeight(), getCurrentTransform(), (double)getLevel(), getCurrentPower2(),bottomLinks);
	}

	/**
	 * Draws the node and link of the tree to the given Graphics2D.
	 * The drawing generally uses the previously defined <code>AffineTransform</code>,
	 * section height, drawing level, and power level.
	 *
	 * @param g2 graphics to which the node is drawn.
	 * @param bottomLinks the boolean to declare whether the bottom links should be drawn.
	 */
	public void drawNodeAndLink(Graphics2D g2, boolean bottomLinks) {

		drawNodeAndLink(g2, getHead().getSectionHeight(), getCurrentTransform(), (double)getLevel(), getCurrentPower2(),bottomLinks);
	}

	/**
	 * Draws the node and link of the tree to the given Graphics2D. Using the Transform, the node
	 * is affect, while the links use the previously defined transform to draw. Consequently, the
	 * node made shift and enlarge while keeping the links constant.
	 *
	 * @param g2 graphics to which the node and links are drawn.
 	 * @param a transfrom to draw the node and links.
 	 */
	public void drawNodeAndLink(Graphics2D g2, AffineTransform a) {


		boolean bottomLinks;

		if (getHead() != null) {
			bottomLinks = (((BSTTreeHead)getHead()).getDisplay() == BSTTreeHead.BINARY_DISPLAY);
		}
		else {
			bottomLinks = true;
		}


		drawNodeAndLink(g2, a, bottomLinks);
	}

	/**
	 * Draws the node and link of the tree to the given Graphics2D. Using the Transform, the node
	 * is affect, while the links use the previously defined transform to draw. Consequently, the
	 * node made shift and enlarge while keeping the links constant.
	 *
	 * @param g2 graphics to which the node and links are drawn.
 	 * @param a transfrom to draw the node and links.
 	 * @param bottomLinks the boolean to declare whether the bottom links should be drawn.
 	 */
	public void drawNodeAndLink(Graphics2D g2, AffineTransform a, boolean bottomLinks) {

		drawRightLink(g2, getHead().getSectionHeight(), getCurrentTransform(), (double)getLevel(), getCurrentPower2(), bottomLinks);
		drawLeftLink(g2, getHead().getSectionHeight(), getCurrentTransform(), (double)getLevel(), getCurrentPower2(), bottomLinks);

		// Draw the node
		drawNode(g2, a);
	}

	/**
	 * Draws the node and link of the tree to the given Graphics2D.
	 * The drawing generally uses the <code>AffineTransform</code>, section height,
	 * drawing level, and power level to render the node and its links.
	 *
	 * @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.
	 */
	public void drawNodeAndLink(Graphics2D g2, double sectionHeight, AffineTransform a, double drawingLevel, double powerLevel) {

		boolean bottomLinks;

		if (getHead() != null) {
			bottomLinks = (((BSTTreeHead)getHead()).getDisplay() == BSTTreeHead.BINARY_DISPLAY);
		}
		else {
			bottomLinks = true;
		}

		drawNodeAndLink(g2, sectionHeight, a, drawingLevel, powerLevel,bottomLinks);
	}


	/**
	 * Draws the node and link of the tree to the given Graphics2D.
	 * The drawing generally uses the <code>AffineTransform</code>, section height,
	 * drawing level, and power level to render the node and its links.
	 *
	 * @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.
	 */
	public void drawNodeAndLink(Graphics2D g2, double sectionHeight, AffineTransform a, double drawingLevel, double powerLevel, boolean bottomLinks) {

		Rectangle2D bounds = g2.getClipBounds();


		drawRightLink(g2, sectionHeight, a, drawingLevel, powerLevel, bottomLinks);
		drawLeftLink(g2, sectionHeight, a, drawingLevel, powerLevel, bottomLinks);

		// Draw the node
		drawNode(g2, a);
	}


	/**
	 * 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();
		BSTTree rightTree = getRightTree();
		Line2D.Double right;

		if (rightTree != null) {
			if (!(rightTree.isEmpty())) {
				double horizontal = rightTree.getCurrentTransform().getTranslateX() + rightTree.getCurrentTransform().getScaleX()/2.0;
				double vertical = rightTree.getCurrentTransform().getTranslateY();

				// Right line
			    right = new Line2D.Double((a.getTranslateX() + (3*a.getScaleX())/4.0) , (a.getTranslateY() + 3*a.getScaleY()/4.0) , horizontal , vertical);


				g2.setComposite(getSettings().getRightLinkComposite());
				g2.setStroke(getSettings().getRightLinkStroke());
				g2.setPaint(getSettings().getRightLinkPaint());

				g2.draw(right);

				return;
			}

		}


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

			g2.setComposite(getSettings().getRightLinkComposite());
			g2.setStroke(getSettings().getRightLinkStroke());
			g2.setPaint(getSettings().getRightLinkPaint());

			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();
		BSTTree leftTree = getLeftTree();
		// Draw the left and right links
		Line2D.Double left;

		if (leftTree != null) {
			if (!(leftTree.isEmpty())) {
				double horizontal = leftTree.getCurrentTransform().getTranslateX() + leftTree.getCurrentTransform().getScaleX()/2.0;
				double vertical = leftTree.getCurrentTransform().getTranslateY();

				// Right line
			    left = new Line2D.Double( (a.getTranslateX() + a.getScaleX()/4.0) , (a.getTranslateY() + 3*a.getScaleY()/4.0) , horizontal, vertical);


				// Set graphics information
				g2.setComposite(getSettings().getLeftLinkComposite());
				g2.setStroke(getSettings().getLeftLinkStroke());
				g2.setPaint(getSettings().getLeftLinkPaint());

				g2.draw(left);

				return;
			}
		}
		if (bottomLinks) {
			// left line
			left = new Line2D.Double( (a.getTranslateX() + a.getScaleX()/4.0) , (a.getTranslateY() + 3*a.getScaleY()/4.0) , (a.getTranslateX() + a.getScaleX()/2.0 - bounds.getWidth()/powerLevel) , (sectionHeight * drawingLevel));

			// Set graphics information
			g2.setComposite(getSettings().getLeftLinkComposite());
			g2.setStroke(getSettings().getLeftLinkStroke());
			g2.setPaint(getSettings().getLeftLinkPaint());

			g2.draw(left);

		}

	}


	/**
	 * Finds the node represented by the x-y coordinates given. The (x,y) location represents a location
	 * within the Graphics2D to which the node appears. The recursive method progresses through the entire tree
	 * looking for the proper node.
	 *
	 * @param x x-coordinate to find the node.
	 * @param y y-coordinate to find the node.
	 *
	 * @return DrawingTree representing the x-y coordinates passed or null if no node is found.
	 */
	protected DrawingTree findNode(double x, double y) {
		if (isEmpty())
			return null;

		if (isNodeAnimating())
			return null;

		if (getCurrentTransform() == null ||  getHead() == null )
			return null;

		// If y < (1.6)(section height) of this current node, than the node is returned.
		if( y <= (getCurrentTransform().getTranslateY() + getHead().getSectionHeight() / 1.6) ){
			return this;
		}
		else {

			// If x is less than half this width, the method is called for the left.
			if (x >= getCurrentTransform().getTranslateX() + getCurrentTransform().getScaleX()/2.0)
				return getRightTree().findNode(x, y);
			else
			// Otherwise the method is called for the right.
				return getLeftTree().findNode(x, y);
		}
	}


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



	/**
	 * The list of animators of the current node.
	 */
	private LinkedList animators;

	/**
	 * The boolean flag whether when called form within an Animation, it should draw.
	 */
	 private boolean animateDrawing;

	/**
	 * Constructor for the ANIMATING_BST_TREE_TYPE. This constructs and sets all values to defaults
	 * for the ANIMATING_BST_TREE_TYPE.
	 */
	 public void constructAnimatingBSTTree() {
		if (animators == null) {
		 	animators = new LinkedList();
		}
		animateDrawing = true;
	 }


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

	/**
	 * Returns true if the node is animating. It simply determines if the list of animators is empty.
	 *
	 * @return true if the node is currently animating.
	 */
	public boolean isNodeAnimating() {
		if (animators == null)
			return false;
		else
			return (!animators.isEmpty());
	}

	/**
	 * Gets the first <code>Animation</code> of the node.
	 *
	 * @return Animation which is the first Animation of the node.
	 */
	public Animation getAnimator() {
		if (!isAnimatingBSTTree())
			return null;


		if (animators.isEmpty()) {
			return null;
		}
		return (Animation)animators.getFirst();
	}

	/**
	 * Sets the boolean flag whether  the node should draw if called from an animation.
	 * Only special cases is the flag set to false (Deletion Animations).
	 *
	 * @param animateDrawing boolean flag to draw if animating.
	 */
	 public void setAnimateDrawing(boolean animateDrawing) {
		 this.animateDrawing = animateDrawing;
	 }

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

	/**
	 * Adds an animation to the current node. This method does not add the node to listen for
	 * AnimationEvents. That must be performed by the user.
	 *
	 * @param a the <code>Animation</code> being added to the node.
	 */
	public void addAnimator(Animation a) {
		if (!isAnimatingBSTTree()) {
			return;
		}

		animators.add(a);
	}


	/**
	 * Gets the boolean flag whether the node should draw if called from an animation.
	 * Only special cases is the flag set to false (Deletion Animations).
	 *
	 * @return boolean flag to draw if animating.
	 */
	 public boolean isAnimateDrawing() {
		 return animateDrawing;
	 }

	/**********************************/
	/* 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, InsertBSTAnimation newAnimator) throws ClassCastException {


		if (!isAnimatingBSTTree()) {
			return;
		}

		if (isEmpty()) {
			return;
		}


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

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

	}

	/**
	 * Constructs the <code>searchBSTAnimation</code> down from the current node.
	 * This is a recursive call through the tree. No Listeners are affected by this call.
	 *
     * @param keySearch the key being searched for.
     *
     * @param newAnimator the SerachBSTAnimation to which the nodes are being added.
     *
     * @throws    ClassCastException key cannot be compared with the keys
	 *		  currently in the tree.
     */
	protected void makeSearchAnimation(Comparable keySearch, SearchBSTAnimation newAnimator) throws ClassCastException {


		if (!isAnimatingBSTTree()) {
			return;
		}

		if (isEmpty()) {
			return;
		}

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

		if (keySearch.compareTo(getKey()) < 0) { // Go to the left
			getLeftTree().makeSearchAnimation(keySearch, newAnimator);
		}
		else if (keySearch.compareTo(getKey()) > 0)  { // Go to the right
			getRightTree().makeSearchAnimation(keySearch, newAnimator);
		}
		// If equal, stop. (SEARCH HIT)
	}


	/**
	 * Constructs the <code>partitionBSTAnimation</code> down from the current node.
	 * This is a recursive call through the tree. No Listeners are affected by this call.
	 *
     * @param elementCount the integer (kth small element) searching for that partition
     *
     * @param newAnimator the PartitionBSTAnimation to which the nodes are being added.
     *
     * @throws    ClassCastException key cannot be compared with the keys
	 *		  currently in the tree.
     */
	protected void makeSelectionAnimation(int elementCount, SelectionBSTAnimation newAnimator) throws ClassCastException {


		if (!isAnimatingBSTTree()) {
			return;
		}

		if (isEmpty()) {
			return;
		}

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

		if (getLeftTree().size() > elementCount) {
			getLeftTree().makeSelectionAnimation(elementCount, newAnimator);
		}
		if (getLeftTree().size() < elementCount) {
			getRightTree().makeSelectionAnimation(elementCount - getLeftTree().size() - 1, newAnimator);
		}

	}



	/**
 	 ********************************************************
	 * ANIMATING_BST_TREE_TYPE Implements Animation Listener*
	 ********************************************************
	 */

	/**
	 * Implements <code>AnimationListener</code> which requires the following method.
	 * The only status of animation it listens for is <code>Animation.FINISH</code>, to remove
	 * the animation from the animators list.
	 *
	 * @param e AnimationEvent that represents the information of the Animation.
	 */
	public void animationEventPerformed(AnimationEvent e) {

		if (!isAnimatingBSTTree()) {
			if (animators != null) {
				animators.clear();
			}
			return;
		}

		if (e.getStatus().equals(Animation.FINISH)) {
			animators.remove(e.getSource());
		}

	}

}