--- jsr166/src/main/java/util/TreeMap.java	2006/04/22 16:38:01	1.32
+++ jsr166/src/main/java/util/TreeMap.java	2006/04/23 20:59:49	1.34
@@ -109,9 +109,6 @@ public class TreeMap<K,V>
      */
     private transient int modCount = 0;
 
-    private void incrementSize()   { modCount++; size++; }
-    private void decrementSize()   { modCount++; size--; }
-
     /**
      * Constructs a new, empty tree map, using the natural ordering of its
      * keys.  All keys inserted into the map must implement the {@link
@@ -226,28 +223,10 @@ public class TreeMap<K,V>
      * @since 1.2
      */
     public boolean containsValue(Object value) {
-        return (root==null ? false :
-                (value==null ? valueSearchNull(root)
-                 : valueSearchNonNull(root, value)));
-    }
-
-    private boolean valueSearchNull(Entry n) {
-        if (n.value == null)
-            return true;
-
-        // Check left and right subtrees for value
-        return (n.left  != null && valueSearchNull(n.left)) ||
-            (n.right != null && valueSearchNull(n.right));
-    }
-
-    private boolean valueSearchNonNull(Entry n, Object value) {
-        // Check this node for the value
-        if (value.equals(n.value))
-            return true;
-
-        // Check left and right subtrees for value
-        return (n.left  != null && valueSearchNonNull(n.left, value)) ||
-            (n.right != null && valueSearchNonNull(n.right, value));
+        for (Entry<K,V> e = getFirstEntry(); e != null; e = successor(e))
+            if (valEquals(value, e.value))
+                return true;
+        return false;
     }
 
     /**
@@ -361,20 +340,22 @@ public class TreeMap<K,V>
      * Version of getEntry using comparator. Split off from getEntry
      * for performance. (This is not worth doing for most methods,
      * that are less dependent on comparator performance, but is
-     * worthwhile for get and put.)
+     * worthwhile here.)
      */
     final Entry<K,V> getEntryUsingComparator(Object key) {
 	K k = (K) key;
         Comparator<? super K> cpr = comparator;
-        Entry<K,V> p = root;
-        while (p != null) {
-            int cmp = cpr.compare(k, p.key);
-            if (cmp < 0)
-                p = p.left;
-            else if (cmp > 0)
-                p = p.right;
-            else
-                return p;
+        if (cpr != null) {
+            Entry<K,V> p = root;
+            while (p != null) {
+                int cmp = cpr.compare(k, p.key);
+                if (cmp < 0)
+                    p = p.left;
+                else if (cmp > 0)
+                    p = p.right;
+                else
+                    return p;
+            }
         }
         return null;
     }
@@ -509,16 +490,6 @@ public class TreeMap<K,V>
     }
 
     /**
-     * Returns the key corresponding to the specified Entry.
-     * @throws NoSuchElementException if the Entry is null
-     */
-    static <K> K key(Entry<K,?> e) {
-        if (e==null)
-            throw new NoSuchElementException();
-        return e.key;
-    }
-
-    /**
      * Associates the specified value with the specified key in this map.
      * If the map previously contained a mapping for the key, the old
      * value is replaced.
@@ -537,73 +508,53 @@ public class TreeMap<K,V>
      *         does not permit null keys
      */
     public V put(K key, V value) {
-        // Offload comparator-based version for sake of performance
-        if (comparator != null)
-            return putUsingComparator(key, value);
-        if (key == null)
-            throw new NullPointerException();
-	Comparable<? super K> k = (Comparable<? super K>) key;
-
         Entry<K,V> t = root;
-        while (t != null) {
-            int cmp = k.compareTo(t.key);
-            if (cmp == 0) {
-                return t.setValue(value);
-            } else if (cmp < 0) {
-                if (t.left != null) {
+        if (t == null) {
+            compare(key, key); // type check
+            root = new Entry<K,V>(key, value, null);
+            size = 1;
+            modCount++;
+            return null;
+        }
+        int cmp;
+        Entry<K,V> parent;
+        // split comparator and comparable paths
+        Comparator<? super K> cpr = comparator;
+        if (cpr != null) {
+            do {
+                parent = t;
+                cmp = cpr.compare(key, t.key);
+                if (cmp < 0)
                     t = t.left;
-                } else {
-                    incrementSize();
-                    fixAfterInsertion(t.left = new Entry<K,V>(key, value, t));
-                    return null;
-                }
-            } else { // cmp > 0
-                if (t.right != null) {
+                else if (cmp > 0)
                     t = t.right;
-                } else {
-                    incrementSize();
-                    fixAfterInsertion(t.right = new Entry<K,V>(key, value, t));
-                    return null;
-                }
-            }
+                else
+                    return t.setValue(value);
+            } while (t != null);
         }
-        incrementSize();
-        root = new Entry<K,V>(key, value, null);
-        return null;
-    }
-
-    /**
-     * Version of put using comparator. Split off from put for
-     * performance.
-     */
-    final V putUsingComparator(K key, V value) {
-        Comparator<? super K> cpr = comparator;
-        Entry<K,V> t = root;
-        while (t != null) {
-            int cmp = cpr.compare(key, t.key);
-            if (cmp == 0) {
-                return t.setValue(value);
-            } else if (cmp < 0) {
-                if (t.left != null) {
+        else {
+            if (key == null)
+                throw new NullPointerException();
+            Comparable<? super K> k = (Comparable<? super K>) key;
+            do {
+                parent = t;
+                cmp = k.compareTo(t.key);
+                if (cmp < 0)
                     t = t.left;
-                } else {
-                    incrementSize();
-                    fixAfterInsertion(t.left = new Entry<K,V>(key, value, t));
-                    return null;
-                }
-            } else { // cmp > 0
-                if (t.right != null) {
+                else if (cmp > 0)
                     t = t.right;
-                } else {
-                    incrementSize();
-                    fixAfterInsertion(t.right = new Entry<K,V>(key, value, t));
-                    return null;
-                }
-            }
+                else
+                    return t.setValue(value);
+            } while (t != null);
         }
-        cpr.compare(key, key); // type check
-        incrementSize();
-        root = new Entry<K,V>(key, value, null);
+        Entry<K,V> e = new Entry<K,V>(key, value, parent);
+        if (cmp < 0)
+            parent.left = e;
+        else
+            parent.right = e;
+        fixAfterInsertion(e);
+        size++;
+        modCount++;
         return null;
     }
 
@@ -679,16 +630,14 @@ public class TreeMap<K,V>
      * @since 1.6
      */
     public Map.Entry<K,V> firstEntry() {
-        Entry<K,V> e = getFirstEntry();
-        return (e == null)? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
+        return exportEntry(getFirstEntry());
     }
 
     /**
      * @since 1.6
      */
     public Map.Entry<K,V> lastEntry() {
-        Entry<K,V> e = getLastEntry();
-        return (e == null)? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
+        return exportEntry(getLastEntry());
     }
 
     /**
@@ -696,10 +645,9 @@ public class TreeMap<K,V>
      */
     public Map.Entry<K,V> pollFirstEntry() {
         Entry<K,V> p = getFirstEntry();
-        if (p == null)
-            return null;
-        Map.Entry<K,V> result = new AbstractMap.SimpleImmutableEntry<K,V>(p);
-        deleteEntry(p);
+        Map.Entry<K,V> result = exportEntry(p);
+        if (p != null)
+            deleteEntry(p);
         return result;
     }
 
@@ -708,10 +656,9 @@ public class TreeMap<K,V>
      */
     public Map.Entry<K,V> pollLastEntry() {
         Entry<K,V> p = getLastEntry();
-        if (p == null)
-            return null;
-        Map.Entry<K,V> result = new AbstractMap.SimpleImmutableEntry<K,V>(p);
-        deleteEntry(p);
+        Map.Entry<K,V> result = exportEntry(p);
+        if (p != null)
+            deleteEntry(p);
         return result;
     }
 
@@ -723,8 +670,7 @@ public class TreeMap<K,V>
      * @since 1.6
      */
     public Map.Entry<K,V> lowerEntry(K key) {
-        Entry<K,V> e =  getLowerEntry(key);
-        return (e == null)? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
+        return exportEntry(getLowerEntry(key));
     }
 
     /**
@@ -735,8 +681,7 @@ public class TreeMap<K,V>
      * @since 1.6
      */
     public K lowerKey(K key) {
-        Entry<K,V> e =  getLowerEntry(key);
-        return (e == null)? null : e.key;
+        return keyOrNull(getLowerEntry(key));
     }
 
     /**
@@ -747,8 +692,7 @@ public class TreeMap<K,V>
      * @since 1.6
      */
     public Map.Entry<K,V> floorEntry(K key) {
-        Entry<K,V> e = getFloorEntry(key);
-        return (e == null)? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
+        return exportEntry(getFloorEntry(key));
     }
 
     /**
@@ -759,8 +703,7 @@ public class TreeMap<K,V>
      * @since 1.6
      */
     public K floorKey(K key) {
-        Entry<K,V> e = getFloorEntry(key);
-        return (e == null)? null : e.key;
+        return keyOrNull(getFloorEntry(key));
     }
 
     /**
@@ -771,8 +714,7 @@ public class TreeMap<K,V>
      * @since 1.6
      */
     public Map.Entry<K,V> ceilingEntry(K key) {
-        Entry<K,V> e = getCeilingEntry(key);
-        return (e == null)? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
+        return exportEntry(getCeilingEntry(key));
     }
 
     /**
@@ -783,8 +725,7 @@ public class TreeMap<K,V>
      * @since 1.6
      */
     public K ceilingKey(K key) {
-        Entry<K,V> e = getCeilingEntry(key);
-        return (e == null)? null : e.key;
+        return keyOrNull(getCeilingEntry(key));
     }
 
     /**
@@ -795,8 +736,7 @@ public class TreeMap<K,V>
      * @since 1.6
      */
     public Map.Entry<K,V> higherEntry(K key) {
-        Entry<K,V> e = getHigherEntry(key);
-        return (e == null)? null : new AbstractMap.SimpleImmutableEntry<K,V>(e);
+        return exportEntry(getHigherEntry(key));
     }
 
     /**
@@ -807,8 +747,7 @@ public class TreeMap<K,V>
      * @since 1.6
      */
     public K higherKey(K key) {
-        Entry<K,V> e = getHigherEntry(key);
-        return (e == null)? null : e.key;
+        return keyOrNull(getHigherEntry(key));
     }
 
     // Views
@@ -994,10 +933,7 @@ public class TreeMap<K,V>
         }
 
         public boolean contains(Object o) {
-            for (Entry<K,V> e = getFirstEntry(); e != null; e = successor(e))
-                if (valEquals(e.getValue(), o))
-                    return true;
-            return false;
+            return TreeMap.this.containsValue(o);
         }
 
         public boolean remove(Object o) {
@@ -1221,6 +1157,50 @@ public class TreeMap<K,V>
         }
     }
 
+    // Little utilities
+
+    /**
+     * Compares two keys using the correct comparison method for this TreeMap.
+     */
+    final int compare(Object k1, Object k2) {
+        return comparator==null ? ((Comparable<? super K>)k1).compareTo((K)k2)
+            : comparator.compare((K)k1, (K)k2);
+    }
+
+    /**
+     * Test two values for equality.  Differs from o1.equals(o2) only in
+     * that it copes with <tt>null</tt> o1 properly.
+     */
+    final static boolean valEquals(Object o1, Object o2) {
+        return (o1==null ? o2==null : o1.equals(o2));
+    }
+
+    /**
+     * Return SimpleImmutableEntry for entry, or null if null
+     */
+    static <K,V> Map.Entry<K,V> exportEntry(TreeMap.Entry<K,V> e) {
+        return e == null? null :
+            new AbstractMap.SimpleImmutableEntry<K,V>(e);
+    }
+
+    /**
+     * Return key for entry, or null if null
+     */
+    static <K,V> K keyOrNull(TreeMap.Entry<K,V> e) {
+        return e == null? null : e.key;
+    }
+
+    /**
+     * Returns the key corresponding to the specified Entry.
+     * @throws NoSuchElementException if the Entry is null
+     */
+    static <K> K key(Entry<K,?> e) {
+        if (e==null)
+            throw new NoSuchElementException();
+        return e.key;
+    }
+
+
     // SubMaps
 
     static abstract class NavigableSubMap<K,V> extends AbstractMap<K,V>
@@ -1298,21 +1278,6 @@ public class TreeMap<K,V>
             return inclusive ? inRange(key) : inClosedRange(key);
         }
 
-        /**
-         * Return SimpleImmutableEntry for entry, or null if null
-         */
-        static <K,V> Map.Entry<K,V> exportEntry(TreeMap.Entry<K,V> e) {
-            return e == null? null : 
-                new AbstractMap.SimpleImmutableEntry<K,V>(e);
-        }
-
-        /**
-         * Return key for entry, or null if null
-         */
-        static <K,V> K exportKey(TreeMap.Entry<K,V> e) {
-            return e == null? null : e.key;
-        }
-
         /*
          * Absolute versions of relation operations.
          * Subclasses map to these using like-named "sub"
@@ -1334,7 +1299,7 @@ public class TreeMap<K,V>
                                  m.getLowerEntry(hi)));
             return (e == null || tooLow(e.key)) ? null : e;
         }
-        
+
         final TreeMap.Entry<K,V> absCeiling(K key) {
             if (tooLow(key))
                 return absLowest();
@@ -1365,7 +1330,7 @@ public class TreeMap<K,V>
 
         /** Returns the absolute high fence for ascending traversal */
         final TreeMap.Entry<K,V> absHighFence() {
-            return (toEnd ? null : (hiInclusive ? 
+            return (toEnd ? null : (hiInclusive ?
                                     m.getHigherEntry(hi) :
                                     m.getCeilingEntry(hi)));
         }
@@ -1426,7 +1391,7 @@ public class TreeMap<K,V>
         }
 
         public final K ceilingKey(K key) {
-            return exportKey(subCeiling(key));
+            return keyOrNull(subCeiling(key));
         }
 
         public final Map.Entry<K,V> higherEntry(K key) {
@@ -1434,7 +1399,7 @@ public class TreeMap<K,V>
         }
 
         public final K higherKey(K key) {
-            return exportKey(subHigher(key));
+            return keyOrNull(subHigher(key));
         }
 
         public final Map.Entry<K,V> floorEntry(K key) {
@@ -1442,7 +1407,7 @@ public class TreeMap<K,V>
         }
 
         public final K floorKey(K key) {
-            return exportKey(subFloor(key));
+            return keyOrNull(subFloor(key));
         }
 
         public final Map.Entry<K,V> lowerEntry(K key) {
@@ -1450,7 +1415,7 @@ public class TreeMap<K,V>
         }
 
         public final K lowerKey(K key) {
-            return exportKey(subLower(key));
+            return keyOrNull(subLower(key));
         }
 
         public final K firstKey() {
@@ -1820,22 +1785,6 @@ public class TreeMap<K,V>
     }
 
     /**
-     * Compares two keys using the correct comparison method for this TreeMap.
-     */
-    final int compare(Object k1, Object k2) {
-        return comparator==null ? ((Comparable<? super K>)k1).compareTo((K)k2)
-            : comparator.compare((K)k1, (K)k2);
-    }
-
-    /**
-     * Test two values for equality.  Differs from o1.equals(o2) only in
-     * that it copes with <tt>null</tt> o1 properly.
-     */
-    final static boolean valEquals(Object o1, Object o2) {
-        return (o1==null ? o2==null : o1.equals(o2));
-    }
-
-    /**
      * This class exists solely for the sake of serialization
      * compatibility with previous releases of TreeMap that did not
      * support NavigableMap.  It translates an old-version SubMap into
@@ -1862,6 +1811,8 @@ public class TreeMap<K,V>
     }
 
 
+    // Red-black mechanics
+
     private static final boolean RED   = false;
     private static final boolean BLACK = true;
 
@@ -2037,40 +1988,43 @@ public class TreeMap<K,V>
         return (p == null) ? null: p.right;
     }
 
-    /** From CLR **/
+    /** From CLR */
     private void rotateLeft(Entry<K,V> p) {
-        Entry<K,V> r = p.right;
-        p.right = r.left;
-        if (r.left != null)
-            r.left.parent = p;
-        r.parent = p.parent;
-        if (p.parent == null)
-            root = r;
-        else if (p.parent.left == p)
-            p.parent.left = r;
-        else
-            p.parent.right = r;
-        r.left = p;
-        p.parent = r;
+        if (p != null) {
+            Entry<K,V> r = p.right;
+            p.right = r.left;
+            if (r.left != null)
+                r.left.parent = p;
+            r.parent = p.parent;
+            if (p.parent == null)
+                root = r;
+            else if (p.parent.left == p)
+                p.parent.left = r;
+            else
+                p.parent.right = r;
+            r.left = p;
+            p.parent = r;
+        }
     }
 
-    /** From CLR **/
+    /** From CLR */
     private void rotateRight(Entry<K,V> p) {
-        Entry<K,V> l = p.left;
-        p.left = l.right;
-        if (l.right != null) l.right.parent = p;
-        l.parent = p.parent;
-        if (p.parent == null)
-            root = l;
-        else if (p.parent.right == p)
-            p.parent.right = l;
-        else p.parent.left = l;
-        l.right = p;
-        p.parent = l;
+        if (p != null) {
+            Entry<K,V> l = p.left;
+            p.left = l.right;
+            if (l.right != null) l.right.parent = p;
+            l.parent = p.parent;
+            if (p.parent == null)
+                root = l;
+            else if (p.parent.right == p)
+                p.parent.right = l;
+            else p.parent.left = l;
+            l.right = p;
+            p.parent = l;
+        }
     }
 
-
-    /** From CLR **/
+    /** From CLR */
     private void fixAfterInsertion(Entry<K,V> x) {
         x.color = RED;
 
@@ -2089,8 +2043,7 @@ public class TreeMap<K,V>
                     }
                     setColor(parentOf(x), BLACK);
                     setColor(parentOf(parentOf(x)), RED);
-                    if (parentOf(parentOf(x)) != null)
-                        rotateRight(parentOf(parentOf(x)));
+                    rotateRight(parentOf(parentOf(x)));
                 }
             } else {
                 Entry<K,V> y = leftOf(parentOf(parentOf(x)));
@@ -2106,8 +2059,7 @@ public class TreeMap<K,V>
                     }
                     setColor(parentOf(x), BLACK);
                     setColor(parentOf(parentOf(x)), RED);
-                    if (parentOf(parentOf(x)) != null)
-                        rotateLeft(parentOf(parentOf(x)));
+                    rotateLeft(parentOf(parentOf(x)));
                 }
             }
         }
@@ -2117,9 +2069,9 @@ public class TreeMap<K,V>
     /**
      * Delete node p, and then rebalance the tree.
      */
-
     private void deleteEntry(Entry<K,V> p) {
-        decrementSize();
+        modCount++;
+        size--;
 
         // If strictly internal, copy successor's element to p and then make p
         // point to successor.
@@ -2165,7 +2117,7 @@ public class TreeMap<K,V>
         }
     }
 
-    /** From CLR **/
+    /** From CLR */
     private void fixAfterDeletion(Entry<K,V> x) {
         while (x != root && colorOf(x) == BLACK) {
             if (x == leftOf(parentOf(x))) {
@@ -2273,13 +2225,13 @@ public class TreeMap<K,V>
         buildFromSorted(size, null, s, null);
     }
 
-    /** Intended to be called only from TreeSet.readObject **/
+    /** Intended to be called only from TreeSet.readObject */
     void readTreeSet(int size, java.io.ObjectInputStream s, V defaultVal)
         throws java.io.IOException, ClassNotFoundException {
         buildFromSorted(size, null, s, defaultVal);
     }
 
-    /** Intended to be called only from TreeSet.addAll **/
+    /** Intended to be called only from TreeSet.addAll */
     void addAllForTreeSet(SortedSet<? extends K> set, V defaultVal) {
 	try {
 	    buildFromSorted(set.size(), set.iterator(), null, defaultVal);