Collections drop from Classpath:

2001-12-15  Bryce McKinlay  <bryce@waitaki.otago.ac.nz>

	* java/util/BitSet.java (and): Fix off-by-one bug, don't skip part of
	the bitset.
	(andNot): Likewise.
	(xor): Likewise.

2001-12-15  Bryce McKinlay  <bryce@waitaki.otago.ac.nz>

	* java/util/LinkedList.java (LinkedListItr.add): Don't skip the next
	entry.

2001-12-15  Eric Blake  <ebb9@email.byu.edu>

	* java/util/TreeMap.java (removeNode): Fix bug in node removal.

2001-12-15  Bryce McKinlay  <bryce@waitaki.otago.ac.nz>

	* java/util/AbstractCollection.java (containsAll): Use size of the
	correct collection for loop bound.
	* java/util/AbstractList.java (iterator.next): Increment pos after
	calling get on backing list.
	(listIterator.next): Likewise.
	* java/util/LinkedList.java (addLastEntry): Don't increment size before
	checking for size == 0.
	(addFirstEntry): Rearrange to match addLastEntry.
	(add): Do not increment size before inserting the new entry.

	* java/util/AbstractCollection.java (addAll): Use size of the
	correct collection for loop bound.

2001-12-15  Bryce McKinlay  <bryce@waitaki.otago.ac.nz>

	* java/util/AbstractSet.java (removeAll): Fix scoping thinko.
	* java/util/HashMap.java (putAllInternal): Set size here.
	* java/util/Hashtable.java (putAllInternal): New method. Copy contents
	of a map efficiently without calling put() or putAll().
	(Hashtable (map)): Use putAllInternal.
	(clone): Likewise.

2001-12-15  Eric Blake  <ebb9@email.byu.edu>

	* java/util/Collections.java:
	* java/util/Vector.java:
	* java/util/WeakHashMap.java: Fix spelling errors.

2001-12-15  Eric Blake  <ebb9@email.byu.edu>

	* java/util/AbstractCollection.java (removeAllInternal),
	(retainAllInternal): Add hooks for use by ArrayList.
	* java/util/AbstractList.java: Minor code updates. Fix some
	scoping.
	* java/util/AbstractMap.java: ditto
	* java/util/ArrayList.java (readObject, writeObject): ditto
	(removeAllInternal, retainAllInternal): Optimize.
	* java/util/Arrays.java: ditto
	* java/util/Collections.java: ditto. Change order of parameters
	to equals(Object, Object) to match specs.
	* java/util/Dictionary.java: Improve javadoc.
	(Dictionary): Add explicit constructor.
	* java/util/HashMap.java: Improve javadoc. Rearrange methods to
	follow order in JDK. Cleanups related to recent code migration to
	AbstractMap. Fix some scoping.
	(entrySet): Cache the result.
	(modCount): Ensure that this is updated correctly.
	* java/util/HashSet.java: Improve javadoc. Fix some scoping.
	(init): Add hooks for LinkedHashSet.
	(map): Use "" instead of Boolean.TRUE in backing map. Use
	package-private API where possible for less overhead.
	(readObject, writeObject): Fix serialization.
	* java/util/Hashtable.java: Improve javadoc. Fix some scoping.
	(entrySet, keySet, values): Cache the result.
	(modCount): Ensure that this is updated correctly.
	(contains, remove): Fix NullPointer checking to match specs.
	(class Enumeration): Make more like HashIterator.
	* java/util/IdentityHashMap.java: Minor code updates.
	(modCount): Ensure that this is updated correctly.
	(readObject, writeObject): Fix serialization.
	* java/util/LinkedHashMap.java: Minor code updates. Cleanups
	related to recent code migration to AbstractMap.
	* java/util/LinkedHashSet.java: New file.
	* java/util/LinkedList.java:
	(readObject, writeObject): Fix serialization.
	* java/util/Makefile.am: List recently added files.
	* java/util/Stack.java: Minor code updates.
	* java/util/TreeMap.java: Improve javadoc. Overhaul the class to
	be more efficient. Fix some scoping. Rearrange the methods.
	(nil): Ensure that this can be thread-safe, and make it a static
	final. Initialize it to be more useful as a sentinal node.
	(Node): Specify color in constructor.
	(deleteFixup, insertFixup): Improve comments and algorithm.
	(fabricateTree): Redesign with less overhead.
	(lowestGreaterThan): Add parameter first to make SubMap easier.
	(removeNode): Patch hole where nil was being modified. Choose
	predecessor instead of successor so in-place swap works.
	(class VerifyResult, verifyTree, verifySub, verifyError): Remove
	this dead code after verifying the class works.
	(class SubMap): Rewrite several algorithms to avoid problems with
	comparing nil.
	* java/util/TreeSet.java: Improve javadoc. Fix some scoping.
	(clone): Fix ClassCastException when cloning subSet().
	(readObject, writeObject): Fix serialization.
	* java/util/WeakHashMap.java: Improve javadoc. Fix some scoping.
	(NULL_KEY): Make it compare as null, for ease elsewhere.
	(Class WeakEntry): Rename from Entry, to avoid shadowing
	Map.Entry. Add missing toString.
	(modCount): Ensure that this is updated correctly.
	(clear, containsValue, keySet, putAll, values, WeakHashMap(Map)):
	Add missing methods and constructor.

2001-12-15  Eric Blake  <ebb9@email.byu.edu>

	* java/util/ArrayList.java (checkBoundExclusive),
	(checkBoundInclusive): Rename from range??clusive, to match
	AbstractList.
	* java/util/LinkedList.java (checkBoundsExclusive),
	(checkBoundsInclusive): ditto
	* java/util/Vector.java (checkBoundExclusive),
	(checkBoundInclusive): Move bounds checking into common methods.

2001-12-15  Eric Blake  <ebb9@email.byu.edu>

	* java/util/AbstractList.java:
	(modCount): Make sure it is updated in all needed places.
	* java/util/ArrayList.java: Improve javadoc. Implements
	RandomAccess. Add serialVersionUID. Reorder methods.
	(modCount): Make sure it is updated in all needed places.
	(rangeExclusive, rangeInclusive): Add common methods for bounds
	check.
	(isEmpty): Add missing method.
	* java/util/Collections.java: (class SynchronizedList): Make
	package visible.
	* java/util/ConcurrentModificationException.java: Improve
	javadoc.
	* java/util/EmptyStackException.java: Improve javadoc.
	* java/util/LinkedList.java: Improve javadoc.
	(modCount): Make sure it is updated in all needed places.
	(rangeExclusive, rangeInclusive): Add common methods for bounds
	check.
	* java/util/NoSuchElementException.java: Improve javadoc.
	* java/util/Stack.java: Improve javadoc. Fix synchronization
	issues.
	(modCount): Make sure it is updated in all needed places.
	* java/util/Vector.java: Improve javadoc. Fix synchronization
	issues. Implements RandomAccess. Reorder methods.
	(modCount): Make sure it is updated in all needed places.
	(setSize): Fix according to specifications: this does not dictate
	the backing array size.
	(removeAll, retainAll): Faster implementations.

2001-12-15  Eric Blake  <ebb9@email.byu.edu>

	* java/util/BitSet.java: Improve javadoc.
	(cardinality(), clear(), clear(int, int), flip(int)),
	(flip(int, int), get(int, int), intersects(BitSet), isEmpty()),
	(nextClearBit(int), nextSetBit(int), set(int, boolean)),
	(set(int, int), set(int, int, boolean)): Add new JDK 1.4 methods.
	(clone): Fix so subclasses clone correctly.

2001-12-15  Eric Blake  <ebb9@email.byu.edu>

	* java/util/AbstractCollection.java: Improve javadoc.
	(AbstractCollection()): Make constructor protected.
	(equals(Object, Object), hashCode(Object)): Add utility methods.
	* java/util/AbstractList.java: Improve javadoc.
	(AbstractList()): Make constructor protected.
	(indexOf(Object)): Call listIterator(), not listIterator(int).
	(iterator()): Follow Sun's requirement to not use listIterator(0).
	(listIterator(int)): Make AbstractListItr anonymous.
	(subList(int, int)): Add support for RandomAccess.
	(SubList.add(int, Object), SubList.remove(Object)): Fix bug with
	modCount tracking.
	(SubList.addAll(Collection)): Add missing method.
	(SubList.listIterator(int)): Fix bugs in indexing, modCount
	tracking.
	(class RandomAccessSubList): Add new class.
	* java/util/AbstractMap.java: Improve javadoc.
	(keys, values, KEYS, VALUES, ENTRIES): Consolidate common map
	fields.
	(AbstractMap()): Make constructor protected.
	(equals(Object, Object), hashCode(Object)): Add utility methods.
	(equals(Object)): Change algorithm to
	entrySet().equals(m.entrySet()), as documented by Sun.
	(keySet(), values()): Cache the collections.
	* java/util/AbstractSequentialList.java: Improve javadoc.
	(AbstractSequentialList()): Make constructor protected.
	* java/util/AbstractSet.java: Improve javadoc.
	(AbstractSet()): Make constructor protected.
	(removeAll(Collection)): Add missing method.
	* java/util/Arrays.java: Improve javadoc, rearrange method orders.
	(defaultComparator): Remove, in favor of
	Collections.compare(Object, Object, Comparator).
	(binarySearch, equals, sort): Fix natural order comparison of
	floats and doubles. Also improve Object comparison - when
	comparator is null, use natural order.
	(fill, sort): Add missing checks for IllegalArgumentException.
	(sort, qsort): Fix sorting bugs, rework the code for more
	legibility.
	(mergeSort): Inline into sort(Object[], int, int, Comparator).
	(class ArrayList): Rename from ListImpl, and make compatible with
	JDK serialization. Add methods which more efficiently override
	those of AbstractList.
	* java/util/Collections: Improve javadoc.
	(isSequential(List)): Add and use a method for deciding between
	RandomAccess and sequential algorithms on lists.
	(class Empty*, class Synchronized*, class Unmodifiable*): Make
	compliant with JDK serializability.
	(class Singleton*, class CopiesList, class RevereseComparator),
	(class UnmodifiableMap.UnmodifiableEntrySet),
	(class *RandomAccessList): New classes for serial compatibility.
	(class Empty*, class Singleton*, class CopiesList): Add methods
	which more efficiently override those of Abstract*.
	(search): Inline into binarySearch(List, Object, Comparator).
	(binarySearch): Make sequential search only do log(n) comparisons,
	instead of n.
	(copy(List, List)): Do bounds checking before starting.
	(indexOfSubList, lastIndexOfSubList, list, replaceAll, rotate),
	(swap):	Add new JDK 1.4 methods.
	(binarySearch, max, min, sort): Allow null comparator to represent
	natural ordering.
	(reverse(List)): Avoid unnecessary swap.
	(shuffle(List, Random)): Do shuffle in-place for RandomAccess
	lists.
	(SingletonList.get): Fix logic bug.
	(SingletonMap.entrySet): Make the entry immutable, and cache the
	returned set.
	(SynchronizedCollection, SynchronizedMap, UnmodifiableCollection),
	(UnmodifiableMap): Detect null pointer in construction.
	(SynchronizedMap, UnmodifiableMap): Cache collection views.
	* java/util/BasicMapEntry: Improve javadoc.

From-SVN: r48035

1 files changed, 1329 insertions, 1020 deletions

diff --git a/libjava/java/util/TreeMap.java b/libjava/java/util/TreeMap.java
index 59d6079..83386d6 100644
--- a/libjava/java/util/TreeMap.java
+++ b/libjava/java/util/TreeMap.java
@@ -38,80 +38,166 @@ import java.io.IOException;
  * interface.  Elements in the Map will be sorted by either a user-provided
  * Comparator object, or by the natural ordering of the keys.
  *
- * The algorithms are adopted from Corman, Leiserson,
- * and Rivest's <i>Introduction to Algorithms.</i>  In other words,
- * I cribbed from the same pseudocode as Sun.  <em>Any similarity
- * between my code and Sun's (if there is any -- I have never looked
- * at Sun's) is a result of this fact.</em>
- *
- * TreeMap guarantees O(log n) insertion and deletion of elements.  That 
- * being said, there is a large enough constant coefficient in front of 
- * that "log n" (overhead involved in keeping the tree 
- * balanced), that TreeMap may not be the best choice for small
- * collections.
+ * The algorithms are adopted from Corman, Leiserson, and Rivest's
+ * <i>Introduction to Algorithms.</i>  TreeMap guarantees O(log n)
+ * insertion and deletion of elements.  That being said, there is a large
+ * enough constant coefficient in front of that "log n" (overhead involved
+ * in keeping the tree balanced), that TreeMap may not be the best choice
+ * for small collections. If something is already sorted, you may want to
+ * just use a LinkedHashMap to maintain the order while providing O(1) access.
  *
  * TreeMap is a part of the JDK1.2 Collections API.  Null keys are allowed
- * only if a Comparator is used which can deal with them.  Null values are 
- * always allowed.
+ * only if a Comparator is used which can deal with them; natural ordering
+ * cannot cope with null.  Null values are always allowed. Note that the
+ * ordering must be <i>consistent with equals</i> to correctly implement
+ * the Map interface. If this condition is violated, the map is still
+ * well-behaved, but you may have suprising results when comparing it to
+ * other maps.<p>
+ *
+ * This implementation is not synchronized. If you need to share this between
+ * multiple threads, do something like:<br>
+ * <code>SortedMap m
+ *       = Collections.synchronizedSortedMap(new TreeMap(...));</code><p>
+ *
+ * The iterators are <i>fail-fast</i>, meaning that any structural
+ * modification, except for <code>remove()</code> called on the iterator
+ * itself, cause the iterator to throw a
+ * <code>ConcurrentModificationException</code> rather than exhibit
+ * non-deterministic behavior.
  *
- * @author           Jon Zeppieri
- * @author	     Bryce McKinlay
+ * @author Jon Zeppieri
+ * @author Bryce McKinlay
+ * @author Eric Blake <ebb9@email.byu.edu>
+ * @see Map
+ * @see HashMap
+ * @see Hashtable
+ * @see LinkedHashMap
+ * @see Comparable
+ * @see Comparator
+ * @see Collection
+ * @see Collections#synchronizedSortedMap(SortedMap)
+ * @since 1.2
+ * @status updated to 1.4
  */
 public class TreeMap extends AbstractMap
   implements SortedMap, Cloneable, Serializable
 {
-  private static final int RED = -1,
-                           BLACK = 1;
+  // Implementation note:
+  // A red-black tree is a binary search tree with the additional properties
+  // that all paths to a leaf node visit the same number of black nodes,
+  // and no red node has red children. To avoid some null-pointer checks,
+  // we use the special node nil which is always black, has no relatives,
+  // and has key and value of null (but is not equal to a mapping of null).
 
-  /** Sentinal node, used to avoid null checks for corner cases and make the
-      delete rebalance code simpler. Note that this must not be static, due 
-      to thread-safety concerns. */
-  transient Node nil = new Node(null, null);
+  /**
+   * Compatible with JDK 1.2.
+   */
+  private static final long serialVersionUID = 919286545866124006L;
 
-  /** The root node of this TreeMap */
-  transient Node root = nil;
+  /**
+   * Color status of a node. Package visible for use by nested classes.
+   */
+  static final int RED = -1,
+                   BLACK = 1;
 
-  /** The size of this TreeMap */
-  transient int size = 0;
+  /**
+   * Sentinal node, used to avoid null checks for corner cases and make the
+   * delete rebalance code simpler. The rebalance code must never assign
+   * the parent, left, or right of nil, but may safely reassign the color
+   * to be black. This object must never be used as a key in a TreeMap, or
+   * it will break bounds checking of a SubMap.
+   */
+  static final Node nil = new Node(null, null, BLACK);
+  static
+    {
+      // Nil is self-referential, so we must initialize it after creation.
+      nil.parent = nil;
+      nil.left = nil;
+      nil.right = nil;
+    }
 
-  /** Number of modifications */
-  transient int modCount = 0;
+  /**
+   * The root node of this TreeMap.
+   */
+  private transient Node root = nil;
+
+  /**
+   * The size of this TreeMap. Package visible for use by nested classes.
+   */
+  transient int size;
+
+  /**
+   * The cache for {@link #entrySet()}.
+   */
+  private transient Set entries;
 
-  /** This TreeMap's comparator, if any. */
-  Comparator comparator = null;
+  /**
+   * Counts the number of modifications this TreeMap has undergone, used
+   * by Iterators to know when to throw ConcurrentModificationExceptions.
+   * Package visible for use by nested classes.
+   */
+  transient int modCount;
 
-  static final long serialVersionUID = 919286545866124006L;
+  /**
+   * This TreeMap's comparator, or null for natural ordering.
+   * Package visible for use by nested classes.
+   * @serial the comparator ordering this tree, or null
+   */
+  final Comparator comparator;
 
-  private static class Node extends BasicMapEntry implements Map.Entry
+  /**
+   * Class to represent an entry in the tree. Holds a single key-value pair,
+   * plus pointers to parent and child nodes.
+   *
+   * @author Eric Blake <ebb9@email.byu.edu>
+   */
+  private static final class Node extends BasicMapEntry
   {
+    // All fields package visible for use by nested classes.
+    /** The color of this node. */
     int color;
-    Node left;
-    Node right;
-    Node parent;
 
-    Node(Object key, Object value)
+    /** The left child node. */
+    Node left = nil;
+    /** The right child node. */
+    Node right = nil;
+    /** The parent node. */
+    Node parent = nil;
+
+    /**
+     * Simple constructor.
+     * @param key the key
+     * @param value the value
+     */
+    Node(Object key, Object value, int color)
     {
       super(key, value);
-      this.color = BLACK;
+      this.color = color;
     }
   }
 
   /**
-   * Instantiate a new TreeMap with no elements, using the keys'
-   * natural ordering to sort.
+   * Instantiate a new TreeMap with no elements, using the keys' natural
+   * ordering to sort. All entries in the map must have a key which implements
+   * Comparable, and which are <i>mutually comparable</i>, otherwise map
+   * operations may throw a {@link ClassCastException}. Attempts to use
+   * a null key will throw a {@link NullPointerException}.
    *
-   * @see java.lang.Comparable
+   * @see Comparable
    */
   public TreeMap()
   {
+    this((Comparator) null);
   }
 
   /**
-   * Instantiate a new TreeMap with no elements, using the provided
-   * comparator to sort.
+   * Instantiate a new TreeMap with no elements, using the provided comparator
+   * to sort. All entries in the map must have keys which are mutually
+   * comparable by the Comparator, otherwise map operations may throw a
+   * {@link ClassCastException}.
    *
-   * @param        oComparator        a Comparator object, used to sort 
-   *                                  the keys of this SortedMap
+   * @param comparator the sort order for the keys of this map, or null
+   *        for the natural order
    */
   public TreeMap(Comparator c)
   {
@@ -119,62 +205,70 @@ public class TreeMap extends AbstractMap
   }
 
   /**
-   * Instantiate a new TreeMap, initializing it with all of the
-   * elements in the provided Map.  The elements will be sorted 
-   * using the natural ordering of the keys.
-   *
-   * @param              map         a Map, whose keys will be put into
-   *                                  this TreeMap
+   * Instantiate a new TreeMap, initializing it with all of the elements in
+   * the provided Map.  The elements will be sorted using the natural
+   * ordering of the keys. This algorithm runs in n*log(n) time. All entries
+   * in the map must have keys which implement Comparable and are mutually
+   * comparable, otherwise map operations may throw a
+   * {@link ClassCastException}.
    *
-   * @throws             ClassCastException     if the keys in the provided
-   *                                            Map do not implement 
-   *                                            Comparable
-   *
-   * @see                java.lang.Comparable
+   * @param map a Map, whose entries will be put into this TreeMap
+   * @throws ClassCastException if the keys in the provided Map are not
+   *         comparable
+   * @throws NullPointerException if map is null
+   * @see Comparable
    */
   public TreeMap(Map map)
   {
+    this((Comparator) null);
     putAll(map);
   }
 
-  /** 
-   * Instantiate a new TreeMap, initializing it with all of the
-   * elements in the provided SortedMap.  The elements will be sorted 
-   * using the same method as in the provided SortedMap.
+  /**
+   * Instantiate a new TreeMap, initializing it with all of the elements in
+   * the provided SortedMap.  The elements will be sorted using the same
+   * comparator as in the provided SortedMap. This runs in linear time.
+   *
+   * @param sm a SortedMap, whose entries will be put into this TreeMap
+   * @throws NullPointerException if sm is null
    */
   public TreeMap(SortedMap sm)
   {
     this(sm.comparator());
-
-    int sm_size = sm.size();
+    int pos = sm.size();
     Iterator itr = sm.entrySet().iterator();
 
-    fabricateTree(sm_size);
+    fabricateTree(pos);
     Node node = firstNode();
-    
-    for (int i = 0; i < sm_size; i++)
+
+    while (--pos >= 0)
       {
-	Map.Entry me = (Map.Entry) itr.next();
-	node.key = me.getKey();
-	node.value = me.getValue();	
-	node = successor(node);
+        Map.Entry me = (Map.Entry) itr.next();
+        node.key = me.getKey();
+        node.value = me.getValue();
+        node = successor(node);
       }
   }
 
-  public int size()
-  {
-    return size;
-  }
-
+  /**
+   * Clears the Map so it has no keys. This is O(1).
+   */
   public void clear()
   {
-    modCount++;
-    root = nil;
-    // nil node could have a residual parent reference, clear it for GC.
-    nil.parent = null;
-    size = 0;
+    if (size > 0)
+      {
+        modCount++;
+        root = nil;
+        size = 0;
+      }
   }
 
+  /**
+   * Returns a shallow clone of this TreeMap. The Map itself is cloned,
+   * but its contents are not.
+   *
+   * @return the clone
+   */
   public Object clone()
   {
     TreeMap copy = null;
@@ -185,547 +279,684 @@ public class TreeMap extends AbstractMap
     catch (CloneNotSupportedException x)
       {
       }
-    // Each instance must have a unique sentinal.
-    copy.nil = new Node(null, null);
+    copy.entries = null;
     copy.fabricateTree(size);
 
     Node node = firstNode();
     Node cnode = copy.firstNode();
-    
+
     while (node != nil)
       {
         cnode.key = node.key;
-	cnode.value = node.value;
-	node = successor(node);
-	cnode = copy.successor(cnode);
+        cnode.value = node.value;
+        node = successor(node);
+        cnode = copy.successor(cnode);
       }
     return copy;
   }
-  
+
+  /**
+   * Return the comparator used to sort this map, or null if it is by
+   * natural order.
+   *
+   * @return the map's comparator
+   */
   public Comparator comparator()
   {
     return comparator;
   }
 
+  /**
+   * Returns true if the map contains a mapping for the given key.
+   *
+   * @param key the key to look for
+   * @return true if the key has a mapping
+   * @throws ClassCastException if key is not comparable to map elements
+   * @throws NullPointerException if key is null and the comparator is not
+   *         tolerant of nulls
+   */
   public boolean containsKey(Object key)
   {
     return getNode(key) != nil;
   }
 
+  /**
+   * Returns true if the map contains at least one mapping to the given value.
+   * This requires linear time.
+   *
+   * @param value the value to look for
+   * @return true if the value appears in a mapping
+   */
   public boolean containsValue(Object value)
   {
     Node node = firstNode();
-    Object currentVal;
-
     while (node != nil)
       {
-	currentVal = node.getValue();
-
-        if (value == null ? currentVal == null : value.equals (currentVal))
-	  return true;
-
-	node = successor(node);
+        if (equals(value, node.value))
+          return true;
+        node = successor(node);
       }
     return false;
   }
 
+  /**
+   * Returns a "set view" of this TreeMap's entries. 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.<p>
+   *
+   * Note that the iterators for all three views, from keySet(), entrySet(),
+   * and values(), traverse the TreeMap in sorted sequence.
+   *
+   * @return a set view of the entries
+   * @see #keySet()
+   * @see #values()
+   * @see Map.Entry
+   */
   public Set entrySet()
   {
-    // Create an AbstractSet with custom implementations of those methods that 
-    // can be overriden easily and efficiently.
-    return new AbstractSet()
-    {
-      public int size()
+    if (entries == null)
+      // Create an AbstractSet with custom implementations of those methods
+      // that can be overriden easily and efficiently.
+      entries = new AbstractSet()
       {
-        return size;
-      }
-      
-      public Iterator iterator()
-      {
-        return new TreeIterator(TreeIterator.ENTRIES);
-      }
-            
-      public void clear()
-      {
-        TreeMap.this.clear();
-      }
+        public int size()
+        {
+          return size;
+        }
 
-      public boolean contains(Object o)
-      {
-        if (!(o instanceof Map.Entry))
-	  return false;
-	Map.Entry me = (Map.Entry) o;
-	Node n = getNode(me.getKey());
-	return (n != nil && me.getValue().equals(n.value));
-      }
-      
-      public boolean remove(Object o)
-      {
-        if (!(o instanceof Map.Entry))
-	  return false;
-	Map.Entry me = (Map.Entry) o;
-	Node n = getNode(me.getKey());
-	if (n != nil && me.getValue().equals(n.value))
-	  {
-	    removeNode(n);
-	    return true;
-	  }
-	return false;
+        public Iterator iterator()
+        {
+          return new TreeIterator(ENTRIES);
+        }
+
+        public void clear()
+        {
+          TreeMap.this.clear();
+        }
+
+        public boolean contains(Object o)
+        {
+          if (! (o instanceof Map.Entry))
+            return false;
+          Map.Entry me = (Map.Entry) o;
+          Node n = getNode(me.getKey());
+          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;
+          Node n = getNode(me.getKey());
+          if (n != nil && AbstractSet.equals(me.getValue(), n.value))
+            {
+              removeNode(n);
+              return true;
+            }
+          return false;
+        }
+      };
+    return entries;
   }
 
+  /**
+   * Returns the first (lowest) key in the map.
+   *
+   * @return the first key
+   * @throws NoSuchElementException if the map is empty
+   */
   public Object firstKey()
   {
     if (root == nil)
-      throw new NoSuchElementException("empty");
-    return firstNode().getKey();
-  }
-  
-  private Node firstNode()
-  {
-    if (root == nil)
-      return nil;
-    Node node = root;
-    while (node.left != nil)
-      node = node.left;
-    return node;
+      throw new NoSuchElementException();
+    return firstNode().key;
   }
 
-  public Object lastKey()
-  {
-    if (root == nil)
-      throw new NoSuchElementException("empty");
-    return lastNode().getKey();
-  }
-  
-  private Node lastNode()
-  {
-    if (root == nil)
-      return nil;
-    Node node = root;
-    while (node.right != nil)
-      node = node.right;
-    return node;  
-  }
-  
+  /**
+   * Return the value in this TreeMap associated with the supplied key,
+   * or <code>null</code> if the key maps to nothing.  NOTE: Since the value
+   * could also be null, you must use containsKey to see if this key
+   * actually maps to something.
+   *
+   * @param key the key for which to fetch an associated value
+   * @return what the key maps to, if present
+   * @throws ClassCastException if key is not comparable to elements in the map
+   * @throws NullPointerException if key is null but the comparator does not
+   *         tolerate nulls
+   * @see #put(Object, Object)
+   * @see #containsKey(Object)
+   */
   public Object get(Object key)
   {
+    // Exploit fact that nil.value == null.
     return getNode(key).value;
   }
-  
-  /** Return the TreeMap.Node associated with KEY, or the nil node if no such
-      node exists in the tree. */
-  private Node getNode(Object key)
-  {
-    int comparison;
-    Node current = root;
 
-    while (current != nil)
-      {
-        comparison = compare(key, current.key);
-	if (comparison > 0)
-	  current = current.right;
-	else if (comparison < 0)
-	  current = current.left;
-	else
-	  return current;
-      }
-    return current; 
+  /**
+   * 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()
   {
-    // Create an AbstractSet with custom implementations of those methods that 
-    // can be overriden easily and efficiently.
-    return new AbstractSet()
-    {
-      public int size()
+    if (keys == null)
+      // Create an AbstractSet with custom implementations of those methods
+      // that can be overriden easily and efficiently.
+      keys = new AbstractSet()
       {
-        return size;
-      }
-      
-      public Iterator iterator()
-      {
-        return new TreeIterator(TreeIterator.KEYS);
-      }
+        public int size()
+        {
+          return size;
+        }
 
-      public void clear()
-      {
-        TreeMap.this.clear();
-      }
+        public Iterator iterator()
+        {
+          return new TreeIterator(KEYS);
+        }
 
-      public boolean contains(Object o)
-      {
-        return TreeMap.this.containsKey(o);
-      }
-      
-      public boolean remove(Object key)
-      {
-        Node n = getNode(key);
-	if (n == nil)
-	  return false;
-        TreeMap.this.removeNode(n);
-	return true;
-      }
-    };
+        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)
   {
-    modCount++;
     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.
-	    Object r = current.value;
-	    current.value = value;
-	    return r;
-	  }
+        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);
-    n.color = RED;
+    Node n = new Node(key, value, RED);
     n.parent = parent;
-    n.left = nil;
-    n.right = nil;
-    
+
     // Insert node in tree.
+    modCount++;
     size++;
     if (parent == nil)
       {
-        // Special case: inserting into an empty tree.
-	root = n;
-	n.color = BLACK;
-	return null;
+        // Special case inserting into an empty tree.
+        root = n;
+        return null;
       }
-    else if (comparison > 0)
+    if (comparison > 0)
       parent.right = n;
     else
-      parent.left = n;   
-    
+      parent.left = n;
+
     // Rebalance after insert.
     insertFixup(n);
-    //verifyTree();
     return null;
   }
 
-  /** Maintain red-black balance after inserting a new node. */
-  private void insertFixup(Node n)
-  {
-    // Only need to rebalance when parent is a RED node, and while at least
-    // 2 levels deep into the tree (ie: node has a grandparent).
-    while (n != root && n.parent.parent != nil && n.parent.color == RED)
-      {
-	if (n.parent == n.parent.parent.left)
-	  {
-            Node uncle = n.parent.parent.right;
-            if (uncle != nil && uncle.color == RED) 
-	      {
-        	n.parent.color = BLACK;
-        	uncle.color = BLACK;
-        	n.parent.parent.color = RED;
-        	n = n.parent.parent;
-              }
-	    else // Uncle is BLACK.
-	      {                
-                if (n == n.parent.right)
-		  {
-                    // Make n a left child.
-                    n = n.parent;
-                    rotateLeft(n);
-                  }
-
-                // Recolor and rotate.
-                n.parent.color = BLACK;
-                n.parent.parent.color = RED;
-                rotateRight(n.parent.parent);
-              }
-	  }
-	else
-	  {
-	    // Mirror image of above code.
-	    Node uncle = n.parent.parent.left;
-            if (uncle != nil && uncle.color == RED)
-	      {
-                n.parent.color = BLACK;
-                uncle.color = BLACK;
-                n.parent.parent.color = RED;
-                n = n.parent.parent;
-              }
-	    else
-	      {
-                if (n == n.parent.left)
-		  {
-                    n = n.parent;
-                    rotateRight(n);
-                  }
-                n.parent.color = BLACK;
-                n.parent.parent.color = RED;
-                rotateLeft(n.parent.parent);
-	      }
-	  }
-      }
-    root.color = BLACK;
-  }
-
+  /**
+   * 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 msize = m.size();
-    Map.Entry e;
-
-    for (int i = 0; i < msize; i++)
+    int pos = m.size();
+    while (--pos >= 0)
       {
-	e = (Map.Entry) itr.next();
-	put(e.getKey(), e.getValue());
+        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)
-      {
-        removeNode(n);
-	return n.value;
-      }
-    return null;
+    if (n == nil)
+      return null;
+    removeNode(n);
+    return n.value;
   }
-  
-  // Remove node from tree. This will increment modCount and decrement size. 
-  // Node must exist in the tree.
-  private void removeNode(Node node) // z
+
+  /**
+   * Returns the number of key-value mappings currently in this Map.
+   *
+   * @return the size
+   */
+  public int size()
   {
-    Node splice; // y
-    Node child;  // x
-    
-    modCount++;
-    size--;
+    return size;
+  }
 
-    // Find splice, the node at the position to actually remove from the tree. 
-    if (node.left == nil || node.right == nil)
-      {
-	// Node to be deleted has 0 or 1 children.
-        splice = node;
-	if (node.left == nil)
-	  child = node.right;
-	else
-	  child = node.left;
-      }
-    else
-      {
-	// Node has 2 children. Splice is node's successor, and will be 
-	// swapped with node since we can't remove node directly.
-        splice = node.right;
-        while (splice.left != nil)
-	  splice = splice.left;
-	child = splice.right;
-      }
+  /**
+   * 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);
+  }
 
-    // Unlink splice from the tree.
-    Node parent = splice.parent;
-    child.parent = parent;
-    if (parent != nil)
+  /**
+   * 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()
       {
-	if (splice == parent.left)
-          parent.left = child;
-	else
-          parent.right = child;
-      }
-    else
-      root = child;
+        public int size()
+        {
+          return size;
+        }
 
-    // Keep track of splice's color in case it gets changed in the swap.
-    int spliceColor = splice.color;
+        public Iterator iterator()
+        {
+          return new TreeIterator(VALUES);
+        }
 
-/*
-    if (splice != node)
-      {
-        node.key = splice.key;
-	node.value = splice.value;
-      }
-*/
-    if (splice != node)
-      {
-        // Swap SPLICE for NODE. Some implementations optimize here by simply
-	// swapping the values, but we can't do that: if an iterator was
-	// referencing a node in its "next" field, and that node got swapped, 
-	// things would get confused.
-	if (node == root)
-	  {
-	    root = splice;
-	  }
-	else
-	  {
-	    if (node.parent.left == node)
-	      node.parent.left = splice;
-	    else
-	      node.parent.right = splice;
-          }
-	splice.parent = node.parent;
-	splice.left = node.left;
-	splice.right = node.right;
-	splice.left.parent = splice;
-	splice.right.parent = splice;
-	splice.color = node.color;
-      }
+        public void clear()
+        {
+          TreeMap.this.clear();
+        }
+      };
+    return values;
+  }
 
-    if (spliceColor == BLACK)
-      deleteFixup (child);
-    
-    //verifyTree();      
+  /**
+   * 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. */
-  private void deleteFixup (Node node)
+  /**
+   * 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)
   {
-    // A black node has been removed, so we need to rebalance to avoid 
+    // 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. 
+    // node is red, we can simply recolor it black and all is well.
     while (node != root && node.color == BLACK)
       {
-        if (node == node.parent.left)
-	  {
-	    // Rebalance left side.
-	    Node sibling = node.parent.right;
-	    if (sibling.color == RED)
-	      {
+        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;
-                node.parent.color = RED;
-                rotateLeft(node.parent);
-                sibling = node.parent.right;
-	      }
+                parent.color = RED;
+                rotateLeft(parent);
+                sibling = parent.right;
+              }
 
-	    if (sibling.left.color == BLACK && sibling.right.color == BLACK)
+            if (sibling.left.color == BLACK && sibling.right.color == BLACK)
               {
-	        // Case 2: Sibling has no red children.
-		sibling.color = RED;
-		// Black height has been decreased, so move up the tree and 
-		// repeat.
-		node = node.parent;
+                // 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.
-		    sibling.left.color = BLACK;
-		    sibling.color = RED;
+            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 = node.parent.right;
-		  }		  
-		
-		// Case 4: Sibling has red right child.
-		sibling.color = sibling.parent.color;
-		sibling.parent.color = BLACK;
-		sibling.right.color = BLACK;
-                rotateLeft(node.parent);
+                    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 = node.parent.left;
-	    if (sibling.color == RED)
-	      {
+              }
+          }
+        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;
-                node.parent.color = RED;
-                rotateRight(node.parent);
-                sibling = node.parent.left;
-	      }
+                parent.color = RED;
+                rotateRight(parent);
+                sibling = parent.left;
+              }
 
-	    if (sibling.left.color == BLACK && sibling.right.color == BLACK)
+            if (sibling.right.color == BLACK && sibling.left.color == BLACK)
               {
-		sibling.color = RED;
-		node = node.parent;
+                // 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)
-		  {
-		    sibling.right.color = BLACK;
-		    sibling.color = RED;
+            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 = node.parent.left;
-		  }		  
-		
-		sibling.color = sibling.parent.color;
-		sibling.parent.color = BLACK;
-		sibling.left.color = BLACK;
-                rotateRight(node.parent);
-                node = root;
-	      }
-	  }
+                    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;
   }
 
-  public SortedMap subMap(Object fromKey, Object toKey)
+  /**
+   * 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 (compare(fromKey, toKey) <= 0)
-      return new SubMap(fromKey, toKey);
-    else
-      throw new IllegalArgumentException("fromKey > toKey");
-  }
+    if (count == 0)
+      return;
 
-  public SortedMap headMap(Object toKey)
-  {
-    return new SubMap(nil, toKey);
-  }
+    // 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.
 
-  public SortedMap tailMap(Object fromKey)
-  {
-    return new SubMap(fromKey, nil);
-  }
+    // Make the root node.
+    root = new Node(null, null, BLACK);
+    size = count;
+    Node row = root;
+    int rowsize;
 
-  /** Returns a "collection view" (or "bag view") of this TreeMap's values. */
-  public Collection values()
-  {
-    // We don't bother overriding many of the optional methods, as doing so
-    // wouldn't provide any significant performance advantage.
-    return new AbstractCollection()
-    {
-      public int size()
+    // 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.
+    int overflow = count - rowsize;
+    Node parent = row;
+    int i;
+    for (i = 0; i < overflow; i += 2)
+      {
+        Node left = new Node(null, null, RED);
+        Node right = new Node(null, null, RED);
+        left.parent = parent;
+        right.parent = parent;
+        parent.left = left;
+        Node next = parent.right;
+        parent.right = right;
+        parent = next;
+      }
+    // Add a lone left node if necessary.
+    if (i - overflow == 0)
       {
-        return size;
+        Node left = new Node(null, null, RED);
+        left.parent = parent;
+        parent.left = left;
+        parent = parent.right;
+        left.parent.right = nil;
       }
-      
-      public Iterator iterator()
+    // Unlink the remaining nodes of the previous row.
+    while (parent != nil)
       {
-        return new TreeIterator(TreeIterator.VALUES);
+        Node next = parent.right;
+        parent.right = nil;
+        parent = next;
       }
-      
-      public void clear()
+  }
+
+  /**
+   * Returns the first sorted node in the map, or nil if empty. Package
+   * visible for use by nested classes.
+   *
+   * @return the first node
+   */
+  final Node firstNode()
+  {
+    // Exploit fact that nil.left == nil.
+    Node node = root;
+    while (node.left != nil)
+      node = node.left;
+    return node;
+  }
+
+  /**
+   * Return the TreeMap.Node associated with key, or the nil node if no such
+   * node exists in the tree. Package visible for use by nested classes.
+   *
+   * @param key the key to search for
+   * @return the node where the key is found, or nil
+   */
+  final Node getNode(Object key)
+  {
+    Node current = root;
+    while (current != nil)
       {
-        TreeMap.this.clear();
+        int comparison = compare(key, current.key);
+        if (comparison > 0)
+          current = current.right;
+        else if (comparison < 0)
+          current = current.left;
+        else
+          return current;
       }
-    };
+    return current;
   }
 
-  // Find the "highest" node which is < key. If key is nil, return last node.
-  // Note that highestLessThan is exclusive (it won't return a key which is
-  // equal to "key"), while lowestGreaterThan is inclusive, in order to be 
-  // consistent with the semantics of subMap().
-  private Node highestLessThan(Object key)
+  /**
+   * Find the "highest" node which is &lt; key. If key is nil, return last
+   * node. Package visible for use by nested classes.
+   *
+   * @param key the upper bound, exclusive
+   * @return the previous node
+   */
+  final Node highestLessThan(Object key)
   {
     if (key == nil)
       return lastNode();
-  
+
     Node last = nil;
     Node current = root;
     int comparison = 0;
@@ -734,24 +965,118 @@ public class TreeMap extends AbstractMap
       {
         last = current;
         comparison = compare(key, current.key);
-	if (comparison > 0)
-	  current = current.right;
-	else if (comparison < 0)
-	  current = current.left;
-	else /* Exact match. */
-	  return predecessor(last);
+        if (comparison > 0)
+          current = current.right;
+        else if (comparison < 0)
+          current = current.left;
+        else // Exact match.
+          return predecessor(last);
       }
-    if (comparison <= 0)
-      return predecessor(last);
-    else
-      return last;
+    return comparison <= 0 ? predecessor(last) : last;
+  }
+
+  /**
+   * Maintain red-black balance after inserting a new node.
+   *
+   * @param n the newly inserted node
+   */
+  private void insertFixup(Node n)
+  {
+    // Only need to rebalance when parent is a RED node, and while at least
+    // 2 levels deep into the tree (ie: node has a grandparent). Remember
+    // that nil.color == BLACK.
+    while (n.parent.color == RED && n.parent.parent != nil)
+      {
+        if (n.parent == n.parent.parent.left)
+          {
+            Node uncle = n.parent.parent.right;
+            // Uncle may be nil, in which case it is BLACK.
+            if (uncle.color == RED)
+              {
+                // Case 1. Uncle is RED: Change colors of parent, uncle,
+                // and grandparent, and move n to grandparent.
+                n.parent.color = BLACK;
+                uncle.color = BLACK;
+                uncle.parent.color = RED;
+                n = uncle.parent;
+              }
+            else
+              {
+                if (n == n.parent.right)
+                  {
+                    // Case 2. Uncle is BLACK and x is right child.
+                    // Move n to parent, and rotate n left.
+                    n = n.parent;
+                    rotateLeft(n);
+                  }
+                // Case 3. Uncle is BLACK and x is left child.
+                // Recolor parent, grandparent, and rotate grandparent right.
+                n.parent.color = BLACK;
+                n.parent.parent.color = RED;
+                rotateRight(n.parent.parent);
+              }
+          }
+        else
+          {
+            // Mirror image of above code.
+            Node uncle = n.parent.parent.left;
+            // Uncle may be nil, in which case it is BLACK.
+            if (uncle.color == RED)
+              {
+                // Case 1. Uncle is RED: Change colors of parent, uncle,
+                // and grandparent, and move n to grandparent.
+                n.parent.color = BLACK;
+                uncle.color = BLACK;
+                uncle.parent.color = RED;
+                n = uncle.parent;
+              }
+            else
+              {
+                if (n == n.parent.left)
+                {
+                    // Case 2. Uncle is BLACK and x is left child.
+                    // Move n to parent, and rotate n right.
+                    n = n.parent;
+                    rotateRight(n);
+                  }
+                // Case 3. Uncle is BLACK and x is right child.
+                // Recolor parent, grandparent, and rotate grandparent left.
+                n.parent.color = BLACK;
+                n.parent.parent.color = RED;
+                rotateLeft(n.parent.parent);
+              }
+          }
+      }
+    root.color = BLACK;
   }
 
-  // Find the "lowest" node which is >= key. If key is nil, return first node.
-  private Node lowestGreaterThan(Object key)
+  /**
+   * Returns the last sorted node in the map, or nil if empty.
+   *
+   * @return the last node
+   */
+  private Node lastNode()
+  {
+    // Exploit fact that nil.right == nil.
+    Node node = root;
+    while (node.right != nil)
+      node = node.right;
+    return node;
+  }
+
+  /**
+   * Find the "lowest" node which is &gt;= key. If key is nil, return either
+   * nil or the first node, depending on the parameter first.
+   * Package visible for use by nested classes.
+   *
+   * @param key the lower bound, inclusive
+   * @param first true to return the first element instead of nil for nil key
+   * @return the next node
+   */
+  final Node lowestGreaterThan(Object key, boolean first)
   {
     if (key == nil)
-      return firstNode();
+      return first ? firstNode() : nil;
 
     Node last = nil;
     Node current = root;
@@ -761,95 +1086,176 @@ public class TreeMap extends AbstractMap
       {
         last = current;
         comparison = compare(key, current.key);
-	if (comparison > 0)
-	  current = current.right;
-	else if (comparison < 0)
-	  current = current.left;
-	else
-	  return current;
+        if (comparison > 0)
+          current = current.right;
+        else if (comparison < 0)
+          current = current.left;
+        else
+          return current;
       }
-    if (comparison > 0)
-      return successor(last);
-    else
-      return last;
-  }  
+    return comparison > 0 ? successor(last) : last;
+  }
 
-  private void writeObject(ObjectOutputStream out) throws IOException
+  /**
+   * Return the node preceding the given one, or nil if there isn't one.
+   *
+   * @param node the current node, not nil
+   * @return the prior node in sorted order
+   */
+  private Node predecessor(Node node)
   {
-    out.defaultWriteObject();
+    if (node.left != nil)
+      {
+        node = node.left;
+        while (node.right != nil)
+          node = node.right;
+        return node;
+      }
 
-    Node node = firstNode();
-    out.writeInt(size);
-    
-    while (node != nil)
+    Node parent = node.parent;
+    // Exploit fact that nil.left == nil and node is non-nil.
+    while (node == parent.left)
       {
-        out.writeObject(node.key);
-	out.writeObject(node.value);
-	node = successor(node);
+        node = parent;
+        parent = node.parent;
       }
+    return parent;
   }
 
-  private void readObject(ObjectInputStream in)
+  /**
+   * Construct a tree from sorted keys in linear time. Package visible for
+   * use by TreeSet.
+   *
+   * @param s the stream to read from
+   * @param count the number of keys to read
+   * @param readValue true to read values, false to insert "" as the value
+   * @throws ClassNotFoundException if the underlying stream fails
+   * @throws IOException if the underlying stream fails
+   * @see #readObject(ObjectInputStream)
+   * @see TreeSet#readObject(ObjectInputStream)
+   */
+  final void putFromObjStream(ObjectInputStream s, int count,
+                              boolean readValues)
     throws IOException, ClassNotFoundException
   {
-    in.defaultReadObject();
-    int size = in.readInt();
-    putFromObjStream(in, size, true);
-  }
+    fabricateTree(count);
+    Node node = firstNode();
 
-  private int compare(Object o1, Object o2)
-  {
-    if (comparator == null)
-      return ((Comparable) o1).compareTo(o2);
-    else
-      return comparator.compare(o1, o2);
+    while (--count >= 0)
+      {
+        node.key = s.readObject();
+        node.value = readValues ? s.readObject() : "";
+        node = successor(node);
+      }
   }
 
-  /* Return the node following Node, or nil if there isn't one. */
-  private Node successor(Node node)
+  /**
+   * Construct a tree from sorted keys in linear time, with values of "".
+   * Package visible for use by TreeSet.
+   *
+   * @param keys the iterator over the sorted keys
+   * @param count the number of nodes to insert
+   * @see TreeSet#TreeSet(SortedSet)
+   */
+  final void putKeysLinear(Iterator keys, int count)
   {
-    if (node.right != nil)
-      {
-        node = node.right;
-	while (node.left != nil)
-	  node = node.left;
-	return node;
-      }
+    fabricateTree(count);
+    Node node = firstNode();
 
-    Node parent = node.parent;
-    while (parent != nil && node == parent.right)
+    while (--count >= 0)
       {
-	node = parent;
-	parent = parent.parent;
+        node.key = keys.next();
+        node.value = "";
+        node = successor(node);
       }
-    return parent;
   }
 
-  /* Return the node preceeding Node, or nil if there isn't one. */
-  private Node predecessor(Node node)
+  /**
+   * Deserializes this object from the given stream.
+   *
+   * @param s the stream to read from
+   * @throws ClassNotFoundException if the underlying stream fails
+   * @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 readObject(ObjectInputStream s)
+    throws IOException, ClassNotFoundException
   {
-    if (node.left != nil)
+    s.defaultReadObject();
+    int size = s.readInt();
+    putFromObjStream(s, size, true);
+  }
+
+  /**
+   * Remove node from tree. This will increment modCount and decrement size.
+   * Node must exist in the tree. Package visible for use by nested classes.
+   *
+   * @param node the node to remove
+   */
+  final void removeNode(Node node)
+  {
+    Node splice;
+    Node child;
+
+    modCount++;
+    size--;
+
+    // Find splice, the node at the position to actually remove from the tree.
+    if (node.left == nil)
       {
-        node = node.left;
-	while (node.right != nil)
-	  node = node.right;
-	return node;
+        // Node to be deleted has 0 or 1 children.
+        splice = node;
+        child = node.right;
       }
-      
-    Node parent = node.parent;
-    while (parent != nil && node == parent.left)
+    else if (node.right == nil)
       {
-	node = parent;
-	parent = parent.parent;
+        // Node to be deleted has 1 child.
+        splice = node;
+        child = node.left;
       }
-    return parent;
+    else
+      {
+        // Node has 2 children. Splice is node's predecessor, and we swap
+        // its contents into node.
+        splice = node.left;
+        while (splice.right != nil)
+          splice = splice.right;
+        child = splice.left;
+        node.key = splice.key;
+        node.value = splice.value;
+      }
+
+    // Unlink splice from the tree.
+    Node parent = splice.parent;
+    if (child != nil)
+      child.parent = parent;
+    if (parent == nil)
+      {
+        // Special case for 0 or 1 node remaining.
+        root = child;
+        return;
+      }
+    if (splice == parent.left)
+      parent.left = child;
+    else
+      parent.right = child;
+
+    if (splice.color == BLACK)
+      deleteFixup(child, parent);
   }
 
-  /** Rotate node n to the left. */
+  /**
+   * Rotate node n to the left.
+   *
+   * @param node the node to rotate
+   */
   private void rotateLeft(Node node)
   {
     Node child = node.right;
-    
+    // if (node == nil || child == nil)
+    //   throw new InternalError();
+
     // Establish node.right link.
     node.right = child.left;
     if (child.left != nil)
@@ -860,331 +1266,146 @@ public class TreeMap extends AbstractMap
     if (node.parent != nil)
       {
         if (node == node.parent.left)
-	  node.parent.left = child;
-	else
-	  node.parent.right = child;
+          node.parent.left = child;
+        else
+          node.parent.right = child;
       }
     else
       root = child;
 
     // Link n and child.
     child.left = node;
-    if (node != nil)
-      node.parent = child;
+    node.parent = child;
   }
 
-  /** Rotate node n to the right. */
+  /**
+   * Rotate node n to the right.
+   *
+   * @param node the node to rotate
+   */
   private void rotateRight(Node node)
   {
     Node child = node.left;
-    
+    // if (node == nil || child == nil)
+    //   throw new InternalError();
+
     // Establish node.left link.
     node.left = child.right;
     if (child.right != nil)
       child.right.parent = node;
-      
+
     // Establish child->parent link.
     child.parent = node.parent;
     if (node.parent != nil)
       {
         if (node == node.parent.right)
-	  node.parent.right = child;
-	else
-	  node.parent.left = child;
+          node.parent.right = child;
+        else
+          node.parent.left = child;
       }
     else
       root = child;
-    
+
     // Link n and child.
     child.right = node;
-    if (node != nil)
-      node.parent = child;
-  }
-  
-  /* Construct a tree from sorted keys in linear time. This is used to
-     implement TreeSet's SortedSet constructor. */
-  void putKeysLinear(Iterator keys, int count)
-  {
-    fabricateTree(count);    
-    Node node = firstNode();
-    
-    for (int i = 0; i < count; i++)
-      {
-	node.key = keys.next();
-	node.value = Boolean.TRUE;
-	node = successor(node);
-      }
-  }
-  
-  /* As above, but load keys from an ObjectInputStream. Used by readObject()
-     methods. If "readValues" is set, entry values will also be read from the 
-     stream. If not, only keys will be read. */
-  void putFromObjStream(ObjectInputStream in, int count, boolean readValues) 
-    throws IOException, ClassNotFoundException
-  {
-    fabricateTree(count);    
-    Node node = firstNode();
-    
-    for (int i = 0; i < count; i++)
-      {
-	node.key = in.readObject();
-	if (readValues)
-	  node.value = in.readObject();
-	else
-	  node.value = Boolean.TRUE;	  
-	node = successor(node);
-      }
-  }
-     
-  /* Construct a perfectly balanced tree consisting of n "blank" nodes. 
-     This permits a tree to be generated from pre-sorted input in linear 
-     time. */
-  private void fabricateTree(int count)
-  {
-    if (count == 0)
-      return;
-    // Calculate the (maximum) depth of the perfectly balanced tree.
-    double ddepth = (Math.log (count + 1) / Math.log (2));
-    int maxdepth = (int) Math.ceil (ddepth);
-    
-    // The number of nodes which can fit in a perfectly-balanced tree of 
-    // height "depth - 1".
-    int max = (int) Math.pow (2, maxdepth - 1) - 1;
-    
-    // Number of nodes which spill over into the deepest row of the tree.
-    int overflow = (int) count - max;
-    
-    size = count;
-    // Make the root node.
-    root = new Node(null, null);
-    root.parent = nil;
-    root.left = nil;
-    root.right = nil;
-    
-    Node row = root;
-    for (int depth = 2; depth <= maxdepth; depth++)  // each row
-      {	
-	// Number of nodes at this depth
-	int rowcap = (int) Math.pow (2, depth - 1);
-	Node parent = row;
-	Node last = null;
-	
-	// Actual number of nodes to create in this row
-	int rowsize;
-	if (depth == maxdepth)
-	  rowsize = overflow;
-	else
-	  rowsize = rowcap;
-	
-	// The bottom most row of nodes is coloured red, as is every second row 
-	// going up, except the root node (row 1). I'm not sure if this is the 
-	// optimal configuration for the tree, but it seems logical enough.
-	// We just need to honour the black-height and red-parent rules here.
-	boolean colorRowRed = (depth % 2 == maxdepth % 2);
-	
-	int i;
-	for (i = 1; i <= rowsize; i++)  // each node in row
-	  {
-	    Node node = new Node(null, null);
-	    node.parent = parent;
-	    if (i % 2 == 1)
-	      parent.left = node;
-	    else
-	      {
-		Node nextparent = parent.right;
-		parent.right = node;
-		parent = nextparent;
-	      }
-
-	    // We use the "right" link to maintain a chain of nodes in 
-	    // each row until the parent->child links are established.
-	    if (last != null)
-	      last.right = node;
-	    last = node;
-	    
-	    if (colorRowRed)
-	      node.color = RED;
-	    
-	    if (i == 1)
-	      row = node;
-	  }
-
-        // Set nil child pointers on leaf nodes.
-	if (depth == maxdepth)
-	  {
-	    // leaf nodes at maxdepth-1.
-	    if (parent != null)
-	      {
-		if (i % 2 == 0)
-		  {
-	            // Current "parent" has "left" set already.
-		    Node next = parent.right;
-		    parent.right = nil;
-		    parent = next;
-		  }		  		  
-		while (parent != null)
-		  {
-		    parent.left = nil;
-		    Node next = parent.right;
-		    parent.right = nil;
-		    parent = next;
-		  }
-	      }
-	    // leaf nodes at maxdepth.
-	    Node node = row;
-	    Node next;
-	    while (node != null)
-	      {
-	        node.left = nil;
-		next = node.right;
-		node.right = nil;
-		node = next;
-	      }
-	  }
-      }
-  }
-  
-  private class VerifyResult
-  {
-    int count; // Total number of nodes.
-    int black; // Black height/depth.
-    int maxdepth; // Maximum depth of branch.
+    node.parent = child;
   }
 
-  /* Check that red-black properties are consistent for the tree. */
-  private void verifyTree()
-  {
-    if (root == nil)
-      {
-        System.err.println ("Verify: empty tree");
-	if (size != 0)
-	  verifyError (this, "no root node but size=" + size);
-	return;
-      }
-    VerifyResult vr = verifySub (root);
-    if (vr.count != size)
-      {
-	verifyError (this, "Tree size not consistent with actual nodes counted. "
-                     + "counted " + vr.count + ", size=" + size);
-        System.exit(1);
-      }
-    System.err.println ("Verify: " + vr.count + " nodes, black height=" + vr.black
-                        + ", maxdepth=" + vr.maxdepth);
-  }
-  
-  /* Recursive call to check that rbtree rules hold. Returns total node count
-     and black height of the given branch. */
-  private VerifyResult verifySub(Node n)
+  /**
+   * Return the node following the given one, or nil if there isn't one.
+   * Package visible for use by nested classes.
+   *
+   * @param node the current node, not nil
+   * @return the next node in sorted order
+   */
+  final Node successor(Node node)
   {
-    VerifyResult vr1 = null;
-    VerifyResult vr2 = null;
-    
-    if (n.left == nil && n.right == nil)
-      {
-        // leaf node
-	VerifyResult r = new VerifyResult();
-	r.black = (n.color == BLACK ? 1 : 0);
-	r.count = 1;
-	r.maxdepth = 1;
-	return r;
-      }
-    
-    if (n.left != nil)
+    if (node.right != nil)
       {
-        if (n.left.parent != n)
-	  verifyError(n.left, "Node's parent link does not point to " + n);
-	
-	if (n.color == RED && n.left.color == RED)
-	  verifyError(n, "Red node has red left child");
-	
-	vr1 = verifySub (n.left);
-	if (n.right == nil)
-	  {
-	    if (n.color == BLACK)
-	      vr1.black++;
-	    vr1.count++;
-	    vr1.maxdepth++;
-	    return vr1;
-	  }
+        node = node.right;
+        while (node.left != nil)
+          node = node.left;
+        return node;
       }
 
-    if (n.right != nil)
+    Node parent = node.parent;
+    // Exploit fact that nil.right == nil and node is non-nil.
+    while (node == parent.right)
       {
-        if (n.right.parent != n)
-	  verifyError(n.right, "Node's parent link does not point to " + n);
-
-	if (n.color == RED && n.right.color == RED)
-	  verifyError(n, "Red node has red right child");
-
-	vr2 = verifySub (n.right);
-	if (n.left == nil)
-	  {
-	    if (n.color == BLACK)
-	      vr2.black++;
-	    vr2.count++;
-	    vr2.maxdepth++;
-	    return vr2;
-	  }
+        node = parent;
+        parent = parent.parent;
       }
-    
-    if (vr1.black != vr2.black)
-      verifyError (n, "Black heights: " + vr1.black + "," + vr2.black + " don't match.");
-    vr1.count += vr2.count + 1;
-    vr1.maxdepth = Math.max(vr1.maxdepth, vr2.maxdepth) + 1;
-    if (n.color == BLACK)
-      vr1.black++;
-    return vr1;
+    return parent;
   }
-  
-  private void verifyError (Object obj, String msg)
+
+  /**
+   * 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
   {
-    System.err.print ("Verify error: ");
-    try
-      {
-        System.err.print (obj);
-      }
-    catch (Exception x)
+    s.defaultWriteObject();
+
+    Node node = firstNode();
+    s.writeInt(size);
+    while (node != nil)
       {
-        System.err.print ("(error printing obj): " + x);
+        s.writeObject(node.key);
+        s.writeObject(node.value);
+        node = successor(node);
       }
-    System.err.println();
-    System.err.println (msg);
-    Thread.dumpStack();
-    System.exit(1);
   }
 
   /**
-   * Iterate over HashMap's entries.
-   * This implementation is parameterized to give a sequential view of
-   * keys, values, or entries.
-   */   
-  class TreeIterator implements Iterator
+   * 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
   {
-    static final int ENTRIES = 0,
-                     KEYS = 1,
-                     VALUES = 2;  
-  
-    // the type of this Iterator: KEYS, VALUES, or ENTRIES.
-    int type;
-    // the number of modifications to the backing Map that we know about.
-    int knownMod = TreeMap.this.modCount;
-    // The last Entry returned by a next() call.
-    Node last;
-    // The next entry that should be returned by next().
-    Node next;
-    // The last node visible to this iterator. This is used when iterating
-    // on a SubMap.
-    Node max;
-
-    /* Create Iterator with the supplied type: KEYS, VALUES, or ENTRIES */
+    /**
+     * 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 an interator for a SubMap. Iteration will begin at node
-       "first", and stop when "max" is reached. */    
+
+    /**
+     * 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;
@@ -1192,263 +1413,351 @@ public class TreeMap extends AbstractMap
       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 != TreeMap.this.modCount)
-	throw new ConcurrentModificationException();
-      return (next != nil);
+      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 (next == nil)
-	throw new NoSuchElementException();
-      if (knownMod != TreeMap.this.modCount)
-	throw new ConcurrentModificationException();
-      Node n = next;
-
-      // Check limit in case we are iterating through a submap.
-      if (n != max)
-	next = successor(n);
-      else
-        next = nil;
-      
-      last = n;
-      
+      if (knownMod != modCount)
+        throw new ConcurrentModificationException();
+      if (next == max)
+        throw new NoSuchElementException();
+      last = next;
+      next = successor(last);
+
       if (type == VALUES)
-        return n.value;
+        return last.value;
       else if (type == KEYS)
-        return n.key;
-      return n;
+        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 (knownMod != modCount)
+        throw new ConcurrentModificationException();
       if (last == null)
-	throw new IllegalStateException();
-      if (knownMod != TreeMap.this.modCount)
-	throw new ConcurrentModificationException();
-/*
-      Object key = null;
-      if (next != nil)
-        key = next.key;
-*/
-      TreeMap.this.removeNode(last);
-      knownMod++;
-/*
-      if (key != null)
-        next = getNode(key);
-*/	
+        throw new IllegalStateException();
+
+      removeNode(last);
       last = null;
+      knownMod++;
     }
-  }
+  } // class TreeIterator
 
-  class SubMap extends AbstractMap implements SortedMap
+  /**
+   * 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
   {
-    Object minKey;
-    Object maxKey;
-
-    /* Create a SubMap representing the elements between minKey and maxKey
-       (inclusive). If minKey is nil, SubMap has no lower bound (headMap).
-       If maxKey is nil, the SubMap has no upper bound (tailMap). */
+    /**
+     * 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 current;
-      Node next = lowestGreaterThan(minKey);
-      Node max = highestLessThan(maxKey);
-      
-      if (compare(next.key, max.key) > 0)
-        // Nothing to delete.
-	return;
-        
-      do
+      Node next = lowestGreaterThan(minKey, true);
+      Node max = lowestGreaterThan(maxKey, false);
+      while (next != max)
         {
-	  current = next;
-	  next = successor(current);
-	  remove(current);
-	}
-      while (current != max);
+          Node current = next;
+          next = successor(current);
+          removeNode(current);
+        }
     }
-    
-    /* 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. */
-    private boolean keyInRange(Object key)
+
+    public Comparator comparator()
     {
-      return ((minKey == nil || compare(key, minKey) >= 0)
-	      && (maxKey == nil || compare(key, maxKey) < 0));
+      return comparator;
     }
 
     public boolean containsKey(Object key)
     {
-      return (keyInRange(key) && TreeMap.this.containsKey(key));
+      return keyInRange(key) && TreeMap.this.containsKey(key);
     }
 
     public boolean containsValue(Object value)
     {
-      Node node = lowestGreaterThan(minKey);
-      Node max = highestLessThan(maxKey);
-      Object currentVal;
-
-      if (node == nil || max == nil || compare(node.key, max.key) > 0)
-        // Nothing to search.
-	return false;
-
-      while (true)
-	{
-	  currentVal = node.getValue();
-          if (value == null ? currentVal == null : value.equals (currentVal))
-	    return true;
-	  if (node == max)
-	    return false;
-	  node = successor(node);
-	}
+      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 get(Object key)
+    public Object firstKey()
     {
-      if (keyInRange(key))
-	return TreeMap.this.get(key);
-      return null;
+      Node node = lowestGreaterThan(minKey, true);
+      if (node == nil || ! keyInRange(node.key))
+        throw new NoSuchElementException();
+      return node.key;
     }
 
-    public Object put(Object key, Object value)
+    public Object get(Object key)
     {
       if (keyInRange(key))
-	return TreeMap.this.put(key, value);
-      else
-	throw new IllegalArgumentException("Key outside range");
+        return TreeMap.this.get(key);
+      return null;
     }
 
-    public Object remove(Object key)
+    public SortedMap headMap(Object toKey)
     {
-      if (keyInRange(key))
-	return TreeMap.this.remove(key);
-      else
-        return null;
+      if (! keyInRange(toKey))
+        throw new IllegalArgumentException("key outside range");
+      return new SubMap(minKey, toKey);
     }
 
-    public int size()
+    public Set keySet()
     {
-      Node node = lowestGreaterThan(minKey);
-      Node max = highestLessThan(maxKey);
+      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();
+          }
 
-      if (node == nil || max == nil || compare(node.key, max.key) > 0)
-	return 0;  // Empty.
+          public Iterator iterator()
+          {
+            Node first = lowestGreaterThan(minKey, true);
+            Node max = lowestGreaterThan(maxKey, false);
+            return new TreeIterator(KEYS, first, max);
+          }
 
-      int count = 1;
-      while (node != max)
-        {
-	  count++;
-	  node = successor(node);
-	}
+          public void clear()
+          {
+            SubMap.this.clear();
+          }
 
-      return count;
+          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 Set entrySet()
+    public Object lastKey()
     {
-      // Create an AbstractSet with custom implementations of those methods that 
-      // can be overriden easily and efficiently.
-      return new AbstractSet()
-      {
-	public int size()
-	{
-          return SubMap.this.size();
-	}
-
-	public Iterator iterator()
-	{
-	  Node first = lowestGreaterThan(minKey);
-	  Node max = highestLessThan(maxKey);
-          return new TreeIterator(TreeIterator.ENTRIES, first, max);
-	}
-
-	public void clear()
-	{
-          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 && me.getValue().equals(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 && me.getValue().equals(n.value))
-	    {
-	      removeNode(n);
-	      return true;
-	    }
-	  return false;
-	}
-      };    
+      Node node = highestLessThan(maxKey);
+      if (node == nil || ! keyInRange(node.key))
+        throw new NoSuchElementException();
+      return node.key;
     }
 
-    public Comparator comparator()
+    public Object put(Object key, Object value)
     {
-      return comparator;
+      if (! keyInRange(key))
+        throw new IllegalArgumentException("Key outside range");
+      return TreeMap.this.put(key, value);
     }
 
-    public Object firstKey()
+    public Object remove(Object key)
     {
-      Node node = lowestGreaterThan(minKey);
-      if (node == nil || !keyInRange(node.key))
-        throw new NoSuchElementException ("empty");
-      return node.key;
+      if (keyInRange(key))
+        return TreeMap.this.remove(key);
+      return null;
     }
 
-    public Object lastKey()
+    public int size()
     {
-      Node node = highestLessThan(maxKey);
-      if (node == nil || !keyInRange(node.key))
-        throw new NoSuchElementException ("empty");
-      return node.key;
+      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))
+      if (! keyInRange(fromKey) || ! keyInRange(toKey))
         throw new IllegalArgumentException("key outside range");
-
-      return TreeMap.this.subMap(fromKey, toKey);
+      return new SubMap(fromKey, toKey);
     }
 
-    public SortedMap headMap(Object toKey)
+    public SortedMap tailMap(Object fromKey)
     {
-      if (!keyInRange(toKey))
+      if (! keyInRange(fromKey))
         throw new IllegalArgumentException("key outside range");
-
-      return TreeMap.this.subMap(minKey, toKey);
+      return new SubMap(fromKey, maxKey);
     }
 
-    public SortedMap tailMap(Object fromKey)
+    public Collection values()
     {
-      if (!keyInRange(fromKey))
-        throw new IllegalArgumentException("key outside range");
+      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();
+          }
 
-      return TreeMap.this.subMap(fromKey, maxKey);
+          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.keys;
     }
-  }
-}
+  } // class SubMap  
+} // class TreeMap