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

  /**
   * The root of the tree.
   */
  BSTNode 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 BST(GComparator compare) {
    this.compare = compare;
    this.root = null;
  } // BST(GComparator)


  // +---------+-------------------------------------------------
  // | 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)

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

  /**
   * Delete an element from the subtree rooted at hereWeAre.  Return
   * the modified subree.
   */
  BSTNode delete(Object deleteMe, BSTNode hereWeAre) 
  {
/*
   Deletion strategy: 
     Shove the right subtree at the rightmost point 
     in the left subtree.
   Observation:
     This strategy will probably lead to unbalanced trees.
     But hey, maybe we'll be lucky.
 */
    // 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 one: No left subtree.  Return the right subtree.
      if (hereWeAre.left == null) return hereWeAre.right;
      // Special case two: No right subtree.  Return the left subtree.
      if (hereWeAre.right == null) return hereWeAre.left;
      // Special case three: No subtrees. Handled by special cases above.
      // Default case: Two subtrees
      putAtRight(hereWeAre.left, hereWeAre.right);
      return hereWeAre.left;
    }
    // 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);
    }
    return hereWeAre;
  } // delete(Object, BSTNode)

  /**
   * Add addMe to the rightmost position in hereWeAre.  Return
   * the modified tree.
   */
  void putAtRight(BSTNode hereWeAre, BSTNode addMe)
  {
     while (hereWeAre.right != null)
       hereWeAre = hereWeAre.right;
     hereWeAre.right = addMe;
/*
     // Base case: We've run out of tree.  
     if (hereWeAre == null) return addMe;
     // Normal case
     hereWeAre.right = putAtRight(hereWeAre.right, addMe);
     return hereWeAre;
 */
  } // putAtRight(BSTNode, BSTNode)

  /**
   * Find the rightmost value in the tree rooted at hereWeAre.
   * Shove that in putItHere, delete the corresponding node,
   * and return the modified tree.
   */
  BSTNode grabAndDeleteRightMost(BSTNode hereWeAre, BSTNode putItHere)
  {
    // If hereWeAre is null, it turns out there was no rightmost
    // child.  Simply return null.
    if (hereWeAre == null)
      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 (hereWeAre.right == null) {
      putItHere.contents = hereWeAre.contents;
      return hereWeAre.left;
    }
    else {
      hereWeAre.right = grabAndDeleteRightMost(hereWeAre.right, putItHere);
      return hereWeAre;
    }
  } // grabAndDeleteRightMost(BSTNode, BSTNode)

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

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

  void dump(BSTNode subroot, String indent) {
    if (subroot != null) {
      System.out.println(indent + subroot.contents);
      dump(subroot.left, indent + "L ");
      dump(subroot.right, indent + "R ");
    }
  } // dump(BSTNode, String)
} // class BST