/*
 * @(#)BalancedBSTTree.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>BalancedBSTTree</code>. Therefore,
	* it overides all important methods necessary for maintaining a
  	* Balanced BST.
	*
	* <p><hr>The Balance defines methods necessary for a BSTTreeHead, a DrawingBSTTreeHead, and an AnimatingBSTTreeHead.
	* The type is set when the node is constructed but can be changed in the middle using methods found in BSTTree. 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><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.5 9/15/01
 	*/
public class BalancedBSTTree extends BSTTree {


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


	/**
	  * Constructs a new, null BalancedBSTTreeHead, sorted according to the keys' natural
	  * order and insertion occurs automatically to the root.
	  *
	  * <p><b>Default type is BST_TREE_TYPE.</b>
      */
     public BalancedBSTTree() {
		 this(0);
 	 }

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

	/**
     * 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>Randomly (according to the probability set in the head) balances each node after passing
     * in an insertion.
     *
     * @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 {
		// Super recursive call
		super.insert(newTree, currentLevel);

		if (!isEmpty()) {
			if (Math.abs(getLeftTree().size() - getRightTree().size()) >= ((BalancedBSTTreeHead)getHead()).getBalanceDifference()) {
				if (((BalancedBSTTreeHead)getHead()).getWaitingList().isEmpty()) {
					((BalancedBSTTreeHead)getHead()).balance(this);
				}
				else {
					((BalancedBSTTreeHead)getHead()).getWaitingList().addFirst(AnimatingTreeHead.BALANCE_NODE, this);
				}
			}
		}

	}

	/**
     * 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 {
		// Super recursive call
		Tree node = super.search(keyFind);

		if (!isEmpty()) {
			if (Math.abs(getLeftTree().size() - getRightTree().size()) >= ((BalancedBSTTreeHead)getHead()).getBalanceDifference()) {
				if (((BalancedBSTTreeHead)getHead()).getWaitingList().isEmpty()) {
					((BalancedBSTTreeHead)getHead()).balance(this);
				}
				else {
					((BalancedBSTTreeHead)getHead()).getWaitingList().addFirst(AnimatingTreeHead.BALANCE_NODE, this);
				}
			}
		}

		return node;

	}

}