if (node.right != nil)      {        node = node.right;        while (node.left != nil)          node = node.left;        return node;      }    Node parent = node.parent;    // Exploit fact that nil.right == nil and node is non-nil.    while (node == parent.right)      {        node = parent;        parent = parent.parent;      }    return parent;  }  /**   * Serializes this object to the given stream.   *   * @param s the stream to write to   * @throws IOException if the underlying stream fails   * @serialData the <i>size</i> (int), followed by key (Object) and value   *             (Object) pairs in sorted order   */  private void writeObject(ObjectOutputStream s) throws IOException  {    s.defaultWriteObject();    Node node = firstNode();    s.writeInt(size);    while (node != nil)      {        s.writeObject(node.key);        s.writeObject(node.value);        node = successor(node);      }  }  /**   * Iterate over HashMap's entries. This implementation is parameterized   * to give a sequential view of keys, values, or entries.   *   * @author Eric Blake <ebb9@email.byu.edu>   */  private final class TreeIterator implements Iterator  {    /**     * The type of this Iterator: {@link #KEYS}, {@link #VALUES},     * or {@link #ENTRIES}.     */    private final int type;    /** The number of modifications to the backing Map that we know about. */    private int knownMod = modCount;    /** The last Entry returned by a next() call. */    private Node last;    /** The next entry that should be returned by next(). */    private Node next;    /**     * The last node visible to this iterator. This is used when iterating     * on a SubMap.     */    private final Node max;    /**     * Construct a new TreeIterator with the supplied type.     * @param type {@link #KEYS}, {@link #VALUES}, or {@link #ENTRIES}     */    TreeIterator(int type)    {      // FIXME gcj cannot handle this. Bug java/4695      // this(type, firstNode(), nil);      this.type = type;      this.next = firstNode();      this.max = nil;    }    /**     * Construct a new TreeIterator with the supplied type. Iteration will     * be from "first" (inclusive) to "max" (exclusive).     *     * @param type {@link #KEYS}, {@link #VALUES}, or {@link #ENTRIES}     * @param first where to start iteration, nil for empty iterator     * @param max the cutoff for iteration, nil for all remaining nodes     */    TreeIterator(int type, Node first, Node max)    {      this.type = type;      this.next = first;      this.max = max;    }    /**     * Returns true if the Iterator has more elements.     * @return true if there are more elements     * @throws ConcurrentModificationException if the TreeMap was modified     */    public boolean hasNext()    {      if (knownMod != modCount)        throw new ConcurrentModificationException();      return next != max;    }    /**     * Returns the next element in the Iterator's sequential view.     * @return the next element     * @throws ConcurrentModificationException if the TreeMap was modified     * @throws NoSuchElementException if there is none     */    public Object next()    {      if (knownMod != modCount)        throw new ConcurrentModificationException();      if (next == max)        throw new NoSuchElementException();      last = next;      next = successor(last);      if (type == VALUES)        return last.value;      else if (type == KEYS)        return last.key;      return last;    }    /**     * Removes from the backing TreeMap the last element which was fetched     * with the <code>next()</code> method.     * @throws ConcurrentModificationException if the TreeMap was modified     * @throws IllegalStateException if called when there is no last element     */    public void remove()    {      if (last == null)        throw new IllegalStateException();      if (knownMod != modCount)        throw new ConcurrentModificationException();      removeNode(last);      last = null;      knownMod++;    }  } // class TreeIterator  /**   * Implementation of {@link #subMap(Object, Object)} and other map   * ranges. This class provides a view of a portion of the original backing   * map, and throws {@link IllegalArgumentException} for attempts to   * access beyond that range.   *   * @author Eric Blake <ebb9@email.byu.edu>   */  private final class SubMap extends AbstractMap implements SortedMap  {    /**     * The lower range of this view, inclusive, or nil for unbounded.     * Package visible for use by nested classes.     */    final Object minKey;    /**     * The upper range of this view, exclusive, or nil for unbounded.     * Package visible for use by nested classes.     */    final Object maxKey;    /**     * The cache for {@link #entrySet()}.     */    private Set entries;    /**     * Create a SubMap representing the elements between minKey (inclusive)     * and maxKey (exclusive). If minKey is nil, SubMap has no lower bound     * (headMap). If maxKey is nil, the SubMap has no upper bound (tailMap).     *     * @param minKey the lower bound     * @param maxKey the upper bound     * @throws IllegalArgumentException if minKey &gt; maxKey     */    SubMap(Object minKey, Object maxKey)    {      if (minKey != nil && maxKey != nil && compare(minKey, maxKey) > 0)        throw new IllegalArgumentException("fromKey > toKey");      this.minKey = minKey;      this.maxKey = maxKey;    }    /**     * Check if "key" is in within the range bounds for this SubMap. The     * lower ("from") SubMap range is inclusive, and the upper ("to") bound     * is exclusive. Package visible for use by nested classes.     *     * @param key the key to check     * @return true if the key is in range     */    final boolean keyInRange(Object key)    {      return ((minKey == nil || compare(key, minKey) >= 0)              && (maxKey == nil || compare(key, maxKey) < 0));    }    public void clear()    {      Node next = lowestGreaterThan(minKey, true);      Node max = lowestGreaterThan(maxKey, false);      while (next != max)        {          Node current = next;          next = successor(current);          removeNode(current);        }    }    public Comparator comparator()    {      return comparator;    }    public boolean containsKey(Object key)    {      return keyInRange(key) && TreeMap.this.containsKey(key);    }    public boolean containsValue(Object value)    {      Node node = lowestGreaterThan(minKey, true);      Node max = lowestGreaterThan(maxKey, false);      while (node != max)        {          if (equals(value, node.getValue()))            return true;          node = successor(node);        }      return false;    }    public Set entrySet()    {      if (entries == null)        // Create an AbstractSet with custom implementations of those methods        // that can be overriden easily and efficiently.        entries = new AbstractSet()        {          public int size()          {            return SubMap.this.size();          }          public Iterator iterator()          {            Node first = lowestGreaterThan(minKey, true);            Node max = lowestGreaterThan(maxKey, false);            return new TreeIterator(ENTRIES, first, max);          }          public void clear()          {            SubMap.this.clear();          }          public boolean contains(Object o)          {            if (! (o instanceof Map.Entry))              return false;            Map.Entry me = (Map.Entry) o;            Object key = me.getKey();            if (! keyInRange(key))              return false;            Node n = getNode(key);            return n != nil && AbstractSet.equals(me.getValue(), n.value);          }          public boolean remove(Object o)          {            if (! (o instanceof Map.Entry))              return false;            Map.Entry me = (Map.Entry) o;            Object key = me.getKey();            if (! keyInRange(key))              return false;            Node n = getNode(key);            if (n != nil && AbstractSet.equals(me.getValue(), n.value))              {                removeNode(n);                return true;              }            return false;          }        };      return entries;    }    public Object firstKey()    {      Node node = lowestGreaterThan(minKey, true);      if (node == nil || ! keyInRange(node.key))        throw new NoSuchElementException();      return node.key;    }    public Object get(Object key)    {      if (keyInRange(key))        return TreeMap.this.get(key);      return null;    }    public SortedMap headMap(Object toKey)    {      if (! keyInRange(toKey))        throw new IllegalArgumentException("key outside range");      return new SubMap(minKey, toKey);    }    public Set keySet()    {      if (this.keys == null)        // Create an AbstractSet with custom implementations of those methods        // that can be overriden easily and efficiently.        this.keys = new AbstractSet()        {          public int size()          {            return SubMap.this.size();          }          public Iterator iterator()          {            Node first = lowestGreaterThan(minKey, true);            Node max = lowestGreaterThan(maxKey, false);            return new TreeIterator(KEYS, first, max);          }          public void clear()          {            SubMap.this.clear();          }          public boolean contains(Object o)          {            if (! keyInRange(o))              return false;            return getNode(o) != nil;          }          public boolean remove(Object o)          {            if (! keyInRange(o))              return false;            Node n = getNode(o);            if (n != nil)              {                removeNode(n);                return true;              }            return false;          }        };      return this.keys;    }    public Object lastKey()    {      Node node = highestLessThan(maxKey);      if (node == nil || ! keyInRange(node.key))        throw new NoSuchElementException();      return node.key;    }    public Object put(Object key, Object value)    {      if (! keyInRange(key))        throw new IllegalArgumentException("Key outside range");      return TreeMap.this.put(key, value);    }    public Object remove(Object key)    {      if (keyInRange(key))        return TreeMap.this.remove(key);      return null;    }    public int size()    {      Node node = lowestGreaterThan(minKey, true);      Node max = lowestGreaterThan(maxKey, false);      int count = 0;      while (node != max)        {          count++;          node = successor(node);        }      return count;    }    public SortedMap subMap(Object fromKey, Object toKey)    {      if (! keyInRange(fromKey) || ! keyInRange(toKey))        throw new IllegalArgumentException("key outside range");      return new SubMap(fromKey, toKey);    }    public SortedMap tailMap(Object fromKey)    {      if (! keyInRange(fromKey))        throw new IllegalArgumentException("key outside range");      return new SubMap(fromKey, maxKey);    }    public Collection values()    {      if (this.values == null)        // Create an AbstractCollection with custom implementations of those        // methods that can be overriden easily and efficiently.        this.values = new AbstractCollection()        {          public int size()          {            return SubMap.this.size();          }          public Iterator iterator()          {            Node first = lowestGreaterThan(minKey, true);            Node max = lowestGreaterThan(maxKey, false);            return new TreeIterator(VALUES, first, max);          }          public void clear()          {            SubMap.this.clear();          }        };      return this.values;    }  } // class SubMap  } // class TreeMap