package username.dict;

import java.io.PrintWriter;

/**
 * An implementation of dictionaries using binary search trees.
 *
 * @author Samuel A. Rebelsky
 * @version 1.0 of April 2005
 */
public class BST<I extends Comparable, V>
  implements NewDict<I,V>
{
// +----------------------+------------------------------------
// | Implementation Notes |
// +----------------------+

/*
(1) A binary search tree is a binary tree in which the left
subtree contains indices less than the index stored in the root
and the right subtree contains values greater than the index
stored in the root.

(2) No duplicate indices are allowed.

(3) To support dictionary-type operations, we store both an
index and a value in each node.
*/

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

   /**
    * The node that serves as the root of the tree.
    */
   BSTNode<I,V> root;

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

  /**
   * Create a new binary search tree.
   */
  public BST()
  {
    this.root = null;
  } // BST()


// +--------------------+--------------------------------------
// | Dictionary Methods |
// +--------------------+

  public void put(I index, V value) {
    this.root = this.put(this.root, index, value);
  } // put(I, V)

  public V get(I index) {
    return this.get(this.root, index);
  } // get(I)

  public void dump(PrintWriter pen)
  {
    this.dump(this.root, pen, "");
  } // dump(PrintWriter)


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

  /**
   * Add something to the subtree rooted at n.  Return the
   * new subtree.
   */
  BSTNode<I,V> put(BSTNode<I,V> top, I index, V value)
  {
    // If we've reached the end of the tree, return a new node.
    if (top == null) {
      return new BSTNode<I,V>(index, value);
    }
    // Compare the top to the searched value.
    int relationship = index.compareTo(top.index);
    // Too small?  Look in the left
    if (relationship < 0) {
      top.left = this.put(top.left, index, value);
    }
    // Too large? Look in the right 
    else if (relationship > 0) {
      top.right = this.put(top.right, index,value);
    }
    // Otherwise, fix the node 
    else {
      top.value = value;
    }
    return top;
  } // put(BSTNode<I,V>, I, V)

  /**
   * Get the value in the node with index index.  Returns null
   * if there is no such index.
   */
  V get(BSTNode<I,V> top, I index)
  {
    // If we've reached the end of the tree, return null
    if (top == null)
      return null;
    // Compare the top to the searched value.
    int relationship = index.compareTo(top.index);
    // Too small?  Look in the left
    if (relationship < 0) {
      return get(top.left, index);
    }
    // Too large?  Look in the right
    else if (relationship > 0) {
      return get(top.right, index);
    }
    // Default: matched
    else {
      return top.value;
    } // else
  } // get(BSTNode<I,V>, index)

  /**
   * Dump the tree with a certain indendation
   */
  public void dump(BSTNode<I,V> top, PrintWriter pen, String indent)
  {
    // Sanity check
    if (top == null) return;
    // Dump away
    pen.println(indent + top.index + " => " + top.value);
    dump(top.left, pen, indent + " L ");
    dump(top.right, pen, indent + " R ");
  } // dump(BSTNode<i,V>, PrintWriter, String)

} // class BST