/**
 * An abstract parent of data and index nodes for an indexed
 * search tree.  Nodes hold KeyedValues with Comparable keys.
 *
 * @author Zach Tomaszewski
 * @version Dec 7, 2006
 */
abstract class Node implements Comparable {

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

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

  /** 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[] data = new KeyedValue[NODE_SIZE];


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

  /**
   * Returns the minimum key value stored in this DataNode.
   *
   * @return Smallest key in node, or null if node is empty.
   */
  public Comparable 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 extends Node {

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

  protected Node[] pointers = new Node[NODE_SIZE];  //XXX: warning x2, but ok
  protected Comparable[] 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 one, Node two, Node 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 Comparable 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.
 * Keys should be Comparable.
 */
class KeyedValue implements Comparable {

  private Comparable key;
  private Object value;

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

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

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

  /**
   * Replaces this KeyedValue's value with newVal.
   */
  public void setValue(Object 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(Object kv) {
    if (kv == null) {
      return -1;
    }else {
      return this.getKey().compareTo(((KeyedValue) 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