import BinaryTree;
import Comparator;

/**
 * A generic implementation of binary search trees.  Created for
 * Exam 3 in CSC152 99S.  I've chosen not to indicate that this
 * implements Dictionary for simplicity's sake.
 *
 * A binary search tree is a binary tree in which all the
 * descendants are less than then value stored in a node, and
 * all the right descendants are greater-than or equal to the
 * value stored in the node.
 *
 * Note that binary search trees are restricted binary trees,
 * so we don't want them to extend binary tree.  Rather, we keep
 * a binary tree as one of the fields.  Since we need to be able
 * to determine ordering, we also store a comparator.
 *
 * @author Samuel A. Rebelsky
 * @version 1.0 of April 1999
 */
public class BinarySearchTree {

  // +--------+--------------------------------------------------
  // | Fields |
  // +--------+

  /**
   * The underlying binary tree.  We don't subclass
   * BinaryTree (or one of its implementations), because
   * we don't want clients to do anything but add and
   * lookup elements.
   */
  protected BinaryTree tree;

  /**
   * The comparator used to determine ordering.
   */
  protected Comparator compare;


  // +--------------+--------------------------------------------
  // | Constructors |
  // +--------------+

  /**
   * Build a new binary search tree, using an underlying
   * binary tree and comparator.
   */
  public BinarySearchTree(BinaryTree tree, Comparator compare) {
    this.tree = tree;
    this.compare = compare;
  } // BinarySearchTree(BinaryTree, Comparator)


  // +-----------+-----------------------------------------------
  // | Accessors |
  // +-----------+

  /**
   * Find an equal element in the tree, returning that element.
   * Pre: The tree and element to look up are initialized.
   * Pre: The tree is in the standard order.
   * Pre: The element and all values in the tree can be
   *   can be compared using the comparator.
   * Post: If there are equal elements in the tree, one such
   *   element is returned.
   * Post: If there are no equal elements in the tree, returns null.
   * Post: The tree is unaffected.
   */
  public Object lookup(Object elt) {
    // STUB
    return null;
  } // lookup(Object)

  // +-----------+-----------------------------------------------
  // | Modifiers |
  // +-----------+

  /**
   * Delete *one copy* of an object from a binary search tree.
   * Pre: The tree and element to delete are initialized.
   * Pre: The tree is in the standard order.
   * Pre: The element and all values in the tree can be
   *   compared using the comparator.
   * Post: If there are equal elements in the tree, there is one
   *   fewer equal element.
   * Post: No other elements are removed.
   * Post: The tree remains in standard order.
   */
  public void delete() {
    // STUB
  } // delete()

  /**
   * Insert an element in a binary search tree.
   * Pre: The tree is initialized.
   * Pre: The tree is in the standard order (smaller elements
   *   to the left, larger to the right).
   * Pre: The element and all values in the tree can be 
   *   compared using the comparator.
   * Post: The element is inserted at the proper place.
   */
  public void insert(Object newElt) {
    // Special case: The tree is empty, so put at the root.
    if (tree.size() == 0)
      tree.setRoot(newElt);
    // Normal case: Find the location and put it there.
    else
      insert(newElt, tree.rootCursor());
  } // insert(Object)

  // +---------+-------------------------------------------------
  // | Helpers |
  // +---------+

  /**
   * Insert an element in the portion of a subtree below
   * a cursor.
   * Pre: The cursor is on the tree.
   * Pre: The tree is nonempty.
   * Pre: The subtree is in the specified order (smaller elements
   *   to the left, larger elements to the right).
   * Pre: The element and all the values in the subtree can be
   *   compared using the comparator.
   * Post: The element is inserted at the proper location.
   */
  protected void insert(Object newElt, BinaryTreeCursor cursor) {
    // Smaller things belong to the left.
    if (compare.lessThan(newElt, cursor.getValue())) {
      // Is there something to the left?  If so, insert
      // in the left subtree.
      if (cursor.hasLeftChild())
        insert(newElt, cursor.getLeftChild());
      // If there isn't something to the left, put the smaller
      // element there.
      else
        cursor.setLeft(newElt);
    } // if smaller
    // Larger things belong to the right.
    else {
      // Is there something to the right?  If so, insert
      // in the right subtree.
      if (cursor.hasRightChild()) 
        insert(newElt, cursor.getRightChild());
      // If there isn't something to the right, put the new
      // larger (or equal) thing there.
      else
        cursor.setRight(newElt);
    } // larger or equal
  } // insert(Object, BinaryTreeCursor)

} // class BinarySearchTree