/**   * Returns a view of this Map including all entries with keys less than   * <code>toKey</code>. The returned map is backed by the original, so changes   * in one appear in the other. The submap will throw an   * {@link IllegalArgumentException} for any attempt to access or add an   * element beyond the specified cutoff. The returned map does not include   * the endpoint; if you want inclusion, pass the successor element.   *   * @param toKey the (exclusive) cutoff point   * @return a view of the map less than the cutoff   * @throws ClassCastException if <code>toKey</code> is not compatible with   *         the comparator (or is not Comparable, for natural ordering)   * @throws NullPointerException if toKey is null, but the comparator does not   *         tolerate null elements   */  public SortedMap headMap(Object toKey)  {    return new SubMap(nil, toKey);  }  /**   * Returns a "set view" of this TreeMap's keys. The set is backed by the   * TreeMap, so changes in one show up in the other.  The set supports   * element removal, but not element addition.   *   * @return a set view of the keys   * @see #values()   * @see #entrySet()   */  public Set keySet()  {    if (keys == null)      // Create an AbstractSet with custom implementations of those methods      // that can be overriden easily and efficiently.      keys = new AbstractSet()      {        public int size()        {          return size;        }        public Iterator iterator()        {          return new TreeIterator(KEYS);        }        public void clear()        {          TreeMap.this.clear();        }        public boolean contains(Object o)        {          return containsKey(o);        }        public boolean remove(Object key)        {          Node n = getNode(key);          if (n == nil)            return false;          removeNode(n);          return true;        }      };    return keys;  }  /**   * Returns the last (highest) key in the map.   *   * @return the last key   * @throws NoSuchElementException if the map is empty   */  public Object lastKey()  {    if (root == nil)      throw new NoSuchElementException("empty");    return lastNode().key;  }  /**   * Puts the supplied value into the Map, mapped by the supplied key.   * The value may be retrieved by any object which <code>equals()</code>   * this key. NOTE: Since the prior value could also be null, you must   * first use containsKey if you want to see if you are replacing the   * key's mapping.   *   * @param key the key used to locate the value   * @param value the value to be stored in the HashMap   * @return the prior mapping of the key, or null if there was none   * @throws ClassCastException if key is not comparable to current map keys   * @throws NullPointerException if key is null, but the comparator does   *         not tolerate nulls   * @see #get(Object)   * @see Object#equals(Object)   */  public Object put(Object key, Object value)  {    Node current = root;    Node parent = nil;    int comparison = 0;    // Find new node's parent.    while (current != nil)      {        parent = current;        comparison = compare(key, current.key);        if (comparison > 0)          current = current.right;        else if (comparison < 0)          current = current.left;        else // Key already in tree.          return current.setValue(value);      }    // Set up new node.    Node n = new Node(key, value, RED);    n.parent = parent;    // Insert node in tree.    modCount++;    size++;    if (parent == nil)      {        // Special case inserting into an empty tree.        root = n;        return null;      }    if (comparison > 0)      parent.right = n;    else      parent.left = n;    // Rebalance after insert.    insertFixup(n);    return null;  }  /**   * Copies all elements of the given map into this hashtable.  If this table   * already has a mapping for a key, the new mapping replaces the current   * one.   *   * @param m the map to be hashed into this   * @throws ClassCastException if a key in m is not comparable with keys   *         in the map   * @throws NullPointerException if a key in m is null, and the comparator   *         does not tolerate nulls   */  public void putAll(Map m)  {    Iterator itr = m.entrySet().iterator();    int pos = m.size();    while (--pos >= 0)      {        Map.Entry e = (Map.Entry) itr.next();        put(e.getKey(), e.getValue());      }  }  /**   * Removes from the TreeMap and returns the value which is mapped by the   * supplied key. If the key maps to nothing, then the TreeMap remains   * unchanged, and <code>null</code> is returned. NOTE: Since the value   * could also be null, you must use containsKey to see if you are   * actually removing a mapping.   *   * @param key the key used to locate the value to remove   * @return whatever the key mapped to, if present   * @throws ClassCastException if key is not comparable to current map keys   * @throws NullPointerException if key is null, but the comparator does   *         not tolerate nulls   */  public Object remove(Object key)  {    Node n = getNode(key);    if (n == nil)      return null;    // Note: removeNode can alter the contents of n, so save value now.    Object result = n.value;    removeNode(n);    return result;  }  /**   * Returns the number of key-value mappings currently in this Map.   *   * @return the size   */  public int size()  {    return size;  }  /**   * Returns a view of this Map including all entries with keys greater or   * equal to <code>fromKey</code> and less than <code>toKey</code> (a   * half-open interval). The returned map is backed by the original, so   * changes in one appear in the other. The submap will throw an   * {@link IllegalArgumentException} for any attempt to access or add an   * element beyond the specified cutoffs. The returned map includes the low   * endpoint but not the high; if you want to reverse this behavior on   * either end, pass in the successor element.   *   * @param fromKey the (inclusive) low cutoff point   * @param toKey the (exclusive) high cutoff point   * @return a view of the map between the cutoffs   * @throws ClassCastException if either cutoff is not compatible with   *         the comparator (or is not Comparable, for natural ordering)   * @throws NullPointerException if fromKey or toKey is null, but the   *         comparator does not tolerate null elements   * @throws IllegalArgumentException if fromKey is greater than toKey   */  public SortedMap subMap(Object fromKey, Object toKey)  {    return new SubMap(fromKey, toKey);  }  /**   * Returns a view of this Map including all entries with keys greater or   * equal to <code>fromKey</code>. The returned map is backed by the   * original, so changes in one appear in the other. The submap will throw an   * {@link IllegalArgumentException} for any attempt to access or add an   * element beyond the specified cutoff. The returned map includes the   * endpoint; if you want to exclude it, pass in the successor element.   *   * @param fromKey the (inclusive) low cutoff point   * @return a view of the map above the cutoff   * @throws ClassCastException if <code>fromKey</code> is not compatible with   *         the comparator (or is not Comparable, for natural ordering)   * @throws NullPointerException if fromKey is null, but the comparator   *         does not tolerate null elements   */  public SortedMap tailMap(Object fromKey)  {    return new SubMap(fromKey, nil);  }  /**   * Returns a "collection view" (or "bag view") of this TreeMap's values.   * The collection is backed by the TreeMap, so changes in one show up   * in the other.  The collection supports element removal, but not element   * addition.   *   * @return a bag view of the values   * @see #keySet()   * @see #entrySet()   */  public Collection values()  {    if (values == null)      // We don't bother overriding many of the optional methods, as doing so      // wouldn't provide any significant performance advantage.      values = new AbstractCollection()      {        public int size()        {          return size;        }        public Iterator iterator()        {          return new TreeIterator(VALUES);        }        public void clear()        {          TreeMap.this.clear();        }      };    return values;  }  /**   * Compares two elements by the set comparator, or by natural ordering.   * Package visible for use by nested classes.   *   * @param o1 the first object   * @param o2 the second object   * @throws ClassCastException if o1 and o2 are not mutually comparable,   *         or are not Comparable with natural ordering   * @throws NullPointerException if o1 or o2 is null with natural ordering   */  final int compare(Object o1, Object o2)  {    return (comparator == null            ? ((Comparable) o1).compareTo(o2)            : comparator.compare(o1, o2));  }  /**   * Maintain red-black balance after deleting a node.   *   * @param node the child of the node just deleted, possibly nil   * @param parent the parent of the node just deleted, never nil   */  private void deleteFixup(Node node, Node parent)  {    // if (parent == nil)    //   throw new InternalError();    // If a black node has been removed, we need to rebalance to avoid    // violating the "same number of black nodes on any path" rule. If    // node is red, we can simply recolor it black and all is well.    while (node != root && node.color == BLACK)      {        if (node == parent.left)          {            // Rebalance left side.            Node sibling = parent.right;            // if (sibling == nil)            //   throw new InternalError();            if (sibling.color == RED)              {                // Case 1: Sibling is red.                // Recolor sibling and parent, and rotate parent left.                sibling.color = BLACK;                parent.color = RED;                rotateLeft(parent);                sibling = parent.right;              }            if (sibling.left.color == BLACK && sibling.right.color == BLACK)              {                // Case 2: Sibling has no red children.                // Recolor sibling, and move to parent.                sibling.color = RED;                node = parent;                parent = parent.parent;              }            else              {                if (sibling.right.color == BLACK)                  {                    // Case 3: Sibling has red left child.                    // Recolor sibling and left child, rotate sibling right.                    sibling.left.color = BLACK;                    sibling.color = RED;                    rotateRight(sibling);                    sibling = parent.right;                  }                // Case 4: Sibling has red right child. Recolor sibling,                // right child, and parent, and rotate parent left.                sibling.color = parent.color;                parent.color = BLACK;                sibling.right.color = BLACK;                rotateLeft(parent);                node = root; // Finished.              }          }        else          {            // Symmetric "mirror" of left-side case.            Node sibling = parent.left;            // if (sibling == nil)            //   throw new InternalError();            if (sibling.color == RED)              {                // Case 1: Sibling is red.                // Recolor sibling and parent, and rotate parent right.                sibling.color = BLACK;                parent.color = RED;                rotateRight(parent);                sibling = parent.left;              }            if (sibling.right.color == BLACK && sibling.left.color == BLACK)              {                // Case 2: Sibling has no red children.                // Recolor sibling, and move to parent.                sibling.color = RED;                node = parent;                parent = parent.parent;              }            else              {                if (sibling.left.color == BLACK)                  {                    // Case 3: Sibling has red right child.                    // Recolor sibling and right child, rotate sibling left.                    sibling.right.color = BLACK;                    sibling.color = RED;                    rotateLeft(sibling);                    sibling = parent.left;                  }                // Case 4: Sibling has red left child. Recolor sibling,                // left child, and parent, and rotate parent right.                sibling.color = parent.color;                parent.color = BLACK;                sibling.left.color = BLACK;                rotateRight(parent);                node = root; // Finished.              }          }      }    node.color = BLACK;  }  /**   * Construct a perfectly balanced tree consisting of n "blank" nodes. This   * permits a tree to be generated from pre-sorted input in linear time.   *   * @param count the number of blank nodes, non-negative   */  private void fabricateTree(final int count)  {    if (count == 0)      return;    // We color every row of nodes black, except for the overflow nodes.    // I believe that this is the optimal arrangement. We construct the tree    // in place by temporarily linking each node to the next node in the row,    // then updating those links to the children when working on the next row.    // Make the root node.    root = new Node(null, null, BLACK);    size = count;    Node row = root;    int rowsize;    // Fill each row that is completely full of nodes.    for (rowsize = 2; rowsize + rowsize <= count; rowsize <<= 1)      {        Node parent = row;        Node last = null;        for (int i = 0; i < rowsize; i += 2)          {            Node left = new Node(null, null, BLACK);            Node right = new Node(null, null, BLACK);            left.parent = parent;            left.right = right;            right.parent = parent;            parent.left = left;            Node next = parent.right;            parent.right = right;            parent = next;            if (last != null)              last.right = left;            last = right;          }        row = row.left;      }    // Now do the partial final row in red.