/**
 * Binary search trees.
 */
public class NewBST
{
  // +--------+--------------------------------------------------
  // | Fields |
  // +--------+

  /**
   * The root of the tree.
   */
  NewBSTNode root;
  
  /**
   * The comparator used to decide where things go.
   */
  GComparator compare;


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

  /**
   * Create a new binary search tree that uses compare to compare
   * elements.
   */
  public NewBST(GComparator compare) {
    this.compare = compare;
    this.root = null;
  } // NewBST(GComparator)


  // +------------------+----------------------------------------
  // | Exported Methods |
  // +------------------+

  /**
   * Add a new element to the tree.
   */
  public void add(Object newElement) {
    this.root = add(newElement, this.root);
  } // add(Object newElement)

  /**
   * Delete an element from the tree.
   */
  public void delete(Object deleteMe) {
    this.root = delete(deleteMe, this.root);
  } // delete(Object)

  /**
   * Dump the tree to the screen.
   */
  public void dump() {
    dump(this.root, "");
  } // dump()


  // +----------------------+------------------------------------
  // | Local Helper Methods |
  // +----------------------+

  /**
   * Add an element at the subtree rooted at hereWeAre.  Return
   * the modified subtree.
   */
  NewBSTNode add(Object newElement, NewBSTNode hereWeAre) {
    if (hereWeAre == null) {
      hereWeAre = new NewBSTNode(newElement);
    }
    else if (compare.mayPrecede(newElement, hereWeAre.contents)) {
      hereWeAre.left = add(newElement, hereWeAre.left);
    }
    else {
      hereWeAre.right = add(newElement, hereWeAre.right);
    }
    hereWeAre.updateHeight();
    return hereWeAre;
  } // add(Object)

  /**
   * Delete an element from the subtree rooted at hereWeAre.  Return
   * the modified subree.
   */
  NewBSTNode delete(Object deleteMe, NewBSTNode hereWeAre) 
  {
    // Deletion strategy: Find the rightmost node in the left subtree,
    // delete it, and put the value here.
    // Base case: Not found, ran off of the tree.
    if (hereWeAre == null) {
      return null;
    }
    // Base case: Found!
    else if (this.same(deleteMe, hereWeAre.contents)) {
      // Special case: No left subtree.  Return the right subtree.
      if (hereWeAre.left == null) return hereWeAre.right;
      // Normal case: Left subtree.  Do funky stuff.
      hereWeAre.left = getAndDeleteRightmost(hereWeAre.left, hereWeAre);
    }
    // Recursive case: Should be in left subtree.
    else if (this.compare.mayPrecede(deleteMe, hereWeAre.contents)) {
      hereWeAre.left = delete(deleteMe, hereWeAre.left);
    }
    // Recursive case: Should be in right subtree.
    else {
      hereWeAre.right = delete(deleteMe, hereWeAre.right);
    }

    // A little bit of clean up and we're done.
    hereWeAre.updateHeight();
    return hereWeAre;
  } // delete(Object, NewBSTNode)

  /**
   * Dump the subtree rooted at subroot.  Indent that subtree by indent.
   */
  void dump(NewBSTNode subroot, String indent) {
    if (subroot != null) {
      System.out.println(indent + subroot.contents 
                         + " [height " + subroot.height +"]");
      dump(subroot.left, indent + "L ");
      dump(subroot.right, indent + "R ");
    }
  } // dump(NewBSTNode, String)

  /**
   * Find the rightmost value in the tree rooted at hereWeAre.
   * Shove that in putItHere, delete the corresponding node,
   * and return the modified tree.
   */
  NewBSTNode getAndDeleteRightmost(NewBSTNode hereWeAre, NewBSTNode putItHere)
  {
    // If hereWeAre is null, it turns out there was no rightmost
    // child.  Simply return null.
    if (null == hereWeAre)
      return null;
    // If hereWeAre has no right children, it is the rightmost node,
    // so shove its contents in putItHere and return its left child
    else if (null == hereWeAre.right) {
      putItHere.contents = hereWeAre.contents;
      return hereWeAre.left;
    }
    else {
      hereWeAre.right = getAndDeleteRightmost(hereWeAre.right, putItHere);
      hereWeAre.updateHeight();
      return hereWeAre;
    }
  } // getAndDeleteRightmost(NewBSTNode, NewBSTNode)

  /**
   * Determine if two elements are the same using the comparator.
   * Assume that if x may precede y and y may precede x, then
   * x is the same as y.
   */
  boolean same(Object alpha, Object beta) {
    return compare.mayPrecede(alpha, beta) 
           && compare.mayPrecede(beta, alpha);
  } // same(Object, Object)

} // class NewBST