/**
 * An abstract parent of data and index nodes for an indexed
 * search tree.  Nodes only hold data with Comparable keys.
 *
 * @param <K> The kind of key stored in this node.
 *
 * @author Zach Tomaszewski
 * @version Dec 7, 2006
 */
abstract class Node<K extends Comparable<K>> implements Comparable<Node<K>> {

  /**
   * Returns the smallest key in this Node (if a data node)
   * or its subtree (if an index node).
   */
  abstract public K getMinKey();

  /**
   * Sorts nodes based on their smallest keys.
   *
   * @see java.lang.Comparable
   */
  public int compareTo(Node<K> node) {
    if (node == null) {  //nulls will come after valid nodes
      return -1;
    }else {
      return this.getMinKey().compareTo(node.getMinKey());
    }
  }
}//end Node



/**
 * Nodes that serve as leaves in an indexed search tree.
 * Each node holds KeyedValue data elements; such elements
 * are sorted by key within the node.
 */
class DataNode<K extends Comparable<K>> extends Node<K> {

  /** The number of data elements held be each data node */
  public static final int NODE_SIZE = 2;

  /** Holds the data elements in this node */
  protected KeyedValue<K,?>[] data =
           (KeyedValue<K,?>[]) new KeyedValue[NODE_SIZE]; //XXX: warning, but ok


  /**
   * Constructs a new data node that contains the given
   * two items in sorted order.
   */
  public DataNode(KeyedValue<K,?> first, KeyedValue<K,?> second) {
//==CODE REMOVED==
  }

  /**
   * Returns the minimum key value stored in this DataNode.
   *
   * @return Smallest key in node, or null if node is empty.
   */
  public K getMinKey() {
//==CODE REMOVED==
    return null;
  }

  /**
   * Returns a string representation of this node.
   */
  public String toString() {
    return "data node=(" + data[0] + ", " + data[1] + ")";
  }

}//end DataNode



/**
 * Nodes that serve as internal nodes in an indexed search tree.
 * Each node holds pointers to children nodes (either DataNode or
 * other IndexNodes) and the mininum key values found in each of those
 * subtrees. The number of key values stored is one less than the number
 * of pointers stored.
 */
class IndexNode<K extends Comparable<K>> extends Node<K>{

  /** the number of pointers held by this node */
  public static final int NODE_SIZE = 3;

  protected Node<K>[] pointers = new Node[NODE_SIZE];  //XXX: warning x2, but ok
  protected Comparable<K>[] minKeys = new Comparable[NODE_SIZE - 1];

  /**
   * Constructs a new IndexNode with pointers to the given nodes.
   * Stores the child nodes in sorted order based on the value of
   * their smallest key.  Also stores the minimum key found in each child,
   * except for the first child.
   */
  public IndexNode(Node<K> one, Node<K> two, Node<K> three) {
//==CODE REMOVED==
  }

  /**
   * Returns the minimum key value stored in this IndexNode's children.
   *
   * @return Smallest key in tree, or null if this node is empty.
   */
  public K getMinKey() {
//==CODE REMOVED==
    return null;
  }

  /**
   * Returns a string representation of this node, displaying
   * only the min keys of its subtrees.
   */
  public String toString() {
    return "index node keys=(" + minKeys[0] + ", " + minKeys[1] + ")";
  }

}//end IndexNode



/**
 * A simple data-storage object that associates a key with a value.
 *
 * @param <K> The type of the key object
 * @param <V> The type of the value object
 */
class KeyedValue<K extends Comparable<K>, V>
                implements Comparable<KeyedValue<K, ?>> {

  private K key;
  private V value;

  /**
   * Constructs a new key-value pair.
   */
  public KeyedValue(K key, V value) {
    this.key = key;
    this.value = value;
  }

  /**
   * Returns this KeyedValue's key object.
   */
  public K getKey() {
    return this.key;
  }

  /**
   * Return this KeyedValue's value object.
   */
  public V getValue() {
    return this.value;
  }

  /**
   * Replaces this KeyedValue's value with newVal.
   */
  public void setValue(V newVal) {
    this.value = newVal;
  }

  /**
   * Compares this KeyedValue to the given KeyedValue based
   * on a comparison of their keys.
   * <p>
   * Supports <code>kv</code> being null;
   * nulls come after all legitimate values.
   */
  public int compareTo(KeyedValue<K,?> kv) {
    if (kv == null) {
      return -1;
    }else {
      return this.getKey().compareTo(kv.getKey());
    }
  }

  /**
   * Returns a string representation of this object as
   * "[key, value]", where key and value are replaced by their
   * toString representation.
   */
  public String toString() {
    //XXX: perhaps should just be "key"?
    return "[" + this.key + ", " + this.value + "]";
  }
}//end KeyedValue