--- jsr166/src/main/java/util/TreeMap.java 2006/04/22 16:38:01 1.32
+++ jsr166/src/main/java/util/TreeMap.java 2007/01/30 03:54:29 1.42
@@ -1,7 +1,7 @@
/*
* %W% %E%
*
- * Copyright 2006 Sun Microsystems, Inc. All rights reserved.
+ * Copyright 2007 Sun Microsystems, Inc. All rights reserved.
* SUN PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
*/
@@ -68,7 +68,7 @@ package java.util;
* associated map using put.)
*
* This class is a member of the
- *
+ *
* Java Collections Framework.
*
* @param the type of keys maintained by this map
@@ -109,9 +109,6 @@ public class TreeMap
*/
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
* @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 e = getFirstEntry(); e != null; e = successor(e))
+ if (valEquals(value, e.value))
+ return true;
+ return false;
}
/**
@@ -361,20 +340,22 @@ public class TreeMap
* 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 getEntryUsingComparator(Object key) {
K k = (K) key;
Comparator cpr = comparator;
- Entry 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 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
}
/**
- * Returns the key corresponding to the specified Entry.
- * @throws NoSuchElementException if the Entry is null
- */
- static K key(Entry 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,57 @@ public class TreeMap
* 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 k = (Comparable) key;
-
Entry 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) {
+ // TBD:
+ // 5045147: (coll) Adding null to an empty TreeSet should
+ // throw NullPointerException
+ //
+ // compare(key, key); // type check
+ root = new Entry(key, value, null);
+ size = 1;
+ modCount++;
+ return null;
+ }
+ int cmp;
+ Entry parent;
+ // split comparator and comparable paths
+ Comparator 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(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(key, value, t));
- return null;
- }
- }
+ else
+ return t.setValue(value);
+ } while (t != null);
}
- incrementSize();
- root = new Entry(key, value, null);
- return null;
- }
-
- /**
- * Version of put using comparator. Split off from put for
- * performance.
- */
- final V putUsingComparator(K key, V value) {
- Comparator cpr = comparator;
- Entry 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 k = (Comparable) key;
+ do {
+ parent = t;
+ cmp = k.compareTo(t.key);
+ if (cmp < 0)
t = t.left;
- } else {
- incrementSize();
- fixAfterInsertion(t.left = new Entry(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(key, value, t));
- return null;
- }
- }
+ else
+ return t.setValue(value);
+ } while (t != null);
}
- cpr.compare(key, key); // type check
- incrementSize();
- root = new Entry(key, value, null);
+ Entry e = new Entry(key, value, parent);
+ if (cmp < 0)
+ parent.left = e;
+ else
+ parent.right = e;
+ fixAfterInsertion(e);
+ size++;
+ modCount++;
return null;
}
@@ -679,16 +634,14 @@ public class TreeMap
* @since 1.6
*/
public Map.Entry firstEntry() {
- Entry e = getFirstEntry();
- return (e == null)? null : new AbstractMap.SimpleImmutableEntry(e);
+ return exportEntry(getFirstEntry());
}
/**
* @since 1.6
*/
public Map.Entry lastEntry() {
- Entry e = getLastEntry();
- return (e == null)? null : new AbstractMap.SimpleImmutableEntry(e);
+ return exportEntry(getLastEntry());
}
/**
@@ -696,10 +649,9 @@ public class TreeMap
*/
public Map.Entry pollFirstEntry() {
Entry p = getFirstEntry();
- if (p == null)
- return null;
- Map.Entry result = new AbstractMap.SimpleImmutableEntry(p);
- deleteEntry(p);
+ Map.Entry result = exportEntry(p);
+ if (p != null)
+ deleteEntry(p);
return result;
}
@@ -708,10 +660,9 @@ public class TreeMap
*/
public Map.Entry pollLastEntry() {
Entry p = getLastEntry();
- if (p == null)
- return null;
- Map.Entry result = new AbstractMap.SimpleImmutableEntry(p);
- deleteEntry(p);
+ Map.Entry result = exportEntry(p);
+ if (p != null)
+ deleteEntry(p);
return result;
}
@@ -723,8 +674,7 @@ public class TreeMap
* @since 1.6
*/
public Map.Entry lowerEntry(K key) {
- Entry e = getLowerEntry(key);
- return (e == null)? null : new AbstractMap.SimpleImmutableEntry(e);
+ return exportEntry(getLowerEntry(key));
}
/**
@@ -735,8 +685,7 @@ public class TreeMap
* @since 1.6
*/
public K lowerKey(K key) {
- Entry e = getLowerEntry(key);
- return (e == null)? null : e.key;
+ return keyOrNull(getLowerEntry(key));
}
/**
@@ -747,8 +696,7 @@ public class TreeMap
* @since 1.6
*/
public Map.Entry floorEntry(K key) {
- Entry e = getFloorEntry(key);
- return (e == null)? null : new AbstractMap.SimpleImmutableEntry(e);
+ return exportEntry(getFloorEntry(key));
}
/**
@@ -759,8 +707,7 @@ public class TreeMap
* @since 1.6
*/
public K floorKey(K key) {
- Entry e = getFloorEntry(key);
- return (e == null)? null : e.key;
+ return keyOrNull(getFloorEntry(key));
}
/**
@@ -771,8 +718,7 @@ public class TreeMap
* @since 1.6
*/
public Map.Entry ceilingEntry(K key) {
- Entry e = getCeilingEntry(key);
- return (e == null)? null : new AbstractMap.SimpleImmutableEntry(e);
+ return exportEntry(getCeilingEntry(key));
}
/**
@@ -783,8 +729,7 @@ public class TreeMap
* @since 1.6
*/
public K ceilingKey(K key) {
- Entry e = getCeilingEntry(key);
- return (e == null)? null : e.key;
+ return keyOrNull(getCeilingEntry(key));
}
/**
@@ -795,8 +740,7 @@ public class TreeMap
* @since 1.6
*/
public Map.Entry higherEntry(K key) {
- Entry e = getHigherEntry(key);
- return (e == null)? null : new AbstractMap.SimpleImmutableEntry(e);
+ return exportEntry(getHigherEntry(key));
}
/**
@@ -807,8 +751,7 @@ public class TreeMap
* @since 1.6
*/
public K higherKey(K key) {
- Entry e = getHigherEntry(key);
- return (e == null)? null : e.key;
+ return keyOrNull(getHigherEntry(key));
}
// Views
@@ -994,10 +937,7 @@ public class TreeMap
}
public boolean contains(Object o) {
- for (Entry 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) {
@@ -1110,7 +1050,7 @@ public class TreeMap
return size() != oldSize;
}
public NavigableSet subSet(E fromElement, boolean fromInclusive,
- E toElement, boolean toInclusive) {
+ E toElement, boolean toInclusive) {
return new TreeSet(m.subMap(fromElement, fromInclusive,
toElement, toInclusive));
}
@@ -1177,10 +1117,11 @@ public class TreeMap
throw new IllegalStateException();
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
+ // deleted entries are replaced by their successors
if (lastReturned.left != null && lastReturned.right != null)
next = lastReturned;
deleteEntry(lastReturned);
- expectedModCount++;
+ expectedModCount = modCount;
lastReturned = null;
}
}
@@ -1221,16 +1162,69 @@ public class TreeMap
}
}
+ // Little utilities
+
+ /**
+ * Compares two keys using the correct comparison method for this TreeMap.
+ */
+ final int compare(Object k1, Object k2) {
+ return comparator==null ? ((Comparable)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 null 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 Map.Entry exportEntry(TreeMap.Entry e) {
+ return e == null? null :
+ new AbstractMap.SimpleImmutableEntry(e);
+ }
+
+ /**
+ * Return key for entry, or null if null
+ */
+ static K keyOrNull(TreeMap.Entry e) {
+ return e == null? null : e.key;
+ }
+
+ /**
+ * Returns the key corresponding to the specified Entry.
+ * @throws NoSuchElementException if the Entry is null
+ */
+ static K key(Entry e) {
+ if (e==null)
+ throw new NoSuchElementException();
+ return e.key;
+ }
+
+
// SubMaps
+ /**
+ * Dummy value serving as unmatchable fence key for unbounded
+ * SubMapIterators
+ */
+ private static final Object UNBOUNDED = new Object();
+
+ /**
+ * @serial include
+ */
static abstract class NavigableSubMap extends AbstractMap
implements NavigableMap, java.io.Serializable {
- /*
+ /**
* The backing map.
*/
final TreeMap m;
- /*
+ /**
* Endpoints are represented as triples (fromStart, lo,
* loInclusive) and (toEnd, hi, hiInclusive). If fromStart is
* true, then the low (absolute) bound is the start of the
@@ -1238,7 +1232,6 @@ public class TreeMap
* if loInclusive is true, lo is the inclusive bound, else lo
* is the exclusive bound. Similarly for the upper bound.
*/
-
final K lo, hi;
final boolean fromStart, toEnd;
final boolean loInclusive, hiInclusive;
@@ -1298,21 +1291,6 @@ public class TreeMap
return inclusive ? inRange(key) : inClosedRange(key);
}
- /**
- * Return SimpleImmutableEntry for entry, or null if null
- */
- static Map.Entry exportEntry(TreeMap.Entry e) {
- return e == null? null :
- new AbstractMap.SimpleImmutableEntry(e);
- }
-
- /**
- * Return key for entry, or null if null
- */
- static K exportKey(TreeMap.Entry e) {
- return e == null? null : e.key;
- }
-
/*
* Absolute versions of relation operations.
* Subclasses map to these using like-named "sub"
@@ -1334,7 +1312,7 @@ public class TreeMap
m.getLowerEntry(hi)));
return (e == null || tooLow(e.key)) ? null : e;
}
-
+
final TreeMap.Entry absCeiling(K key) {
if (tooLow(key))
return absLowest();
@@ -1365,7 +1343,7 @@ public class TreeMap
/** Returns the absolute high fence for ascending traversal */
final TreeMap.Entry absHighFence() {
- return (toEnd ? null : (hiInclusive ?
+ return (toEnd ? null : (hiInclusive ?
m.getHigherEntry(hi) :
m.getCeilingEntry(hi)));
}
@@ -1378,7 +1356,7 @@ public class TreeMap
}
// Abstract methods defined in ascending vs descending classes
- // These relay to the appropriate absolute versions
+ // These relay to the appropriate absolute versions
abstract TreeMap.Entry subLowest();
abstract TreeMap.Entry subHighest();
@@ -1426,7 +1404,7 @@ public class TreeMap
}
public final K ceilingKey(K key) {
- return exportKey(subCeiling(key));
+ return keyOrNull(subCeiling(key));
}
public final Map.Entry higherEntry(K key) {
@@ -1434,7 +1412,7 @@ public class TreeMap
}
public final K higherKey(K key) {
- return exportKey(subHigher(key));
+ return keyOrNull(subHigher(key));
}
public final Map.Entry floorEntry(K key) {
@@ -1442,7 +1420,7 @@ public class TreeMap
}
public final K floorKey(K key) {
- return exportKey(subFloor(key));
+ return keyOrNull(subFloor(key));
}
public final Map.Entry lowerEntry(K key) {
@@ -1450,7 +1428,7 @@ public class TreeMap
}
public final K lowerKey(K key) {
- return exportKey(subLower(key));
+ return keyOrNull(subLower(key));
}
public final K firstKey() {
@@ -1575,7 +1553,7 @@ public class TreeMap
abstract class SubMapIterator implements Iterator {
TreeMap.Entry lastReturned;
TreeMap.Entry next;
- final K fenceKey;
+ final Object fenceKey;
int expectedModCount;
SubMapIterator(TreeMap.Entry first,
@@ -1583,7 +1561,7 @@ public class TreeMap
expectedModCount = m.modCount;
lastReturned = null;
next = first;
- fenceKey = fence == null ? null : fence.key;
+ fenceKey = fence == null ? UNBOUNDED : fence.key;
}
public final boolean hasNext() {
@@ -1610,17 +1588,29 @@ public class TreeMap
return e;
}
- public void remove() {
+ final void removeAscending() {
if (lastReturned == null)
throw new IllegalStateException();
if (m.modCount != expectedModCount)
throw new ConcurrentModificationException();
+ // deleted entries are replaced by their successors
if (lastReturned.left != null && lastReturned.right != null)
next = lastReturned;
m.deleteEntry(lastReturned);
- expectedModCount++;
lastReturned = null;
+ expectedModCount = m.modCount;
+ }
+
+ final void removeDescending() {
+ if (lastReturned == null)
+ throw new IllegalStateException();
+ if (m.modCount != expectedModCount)
+ throw new ConcurrentModificationException();
+ m.deleteEntry(lastReturned);
+ lastReturned = null;
+ expectedModCount = m.modCount;
}
+
}
final class SubMapEntryIterator extends SubMapIterator> {
@@ -1631,6 +1621,9 @@ public class TreeMap
public Map.Entry next() {
return nextEntry();
}
+ public void remove() {
+ removeAscending();
+ }
}
final class SubMapKeyIterator extends SubMapIterator {
@@ -1641,6 +1634,9 @@ public class TreeMap
public K next() {
return nextEntry().key;
}
+ public void remove() {
+ removeAscending();
+ }
}
final class DescendingSubMapEntryIterator extends SubMapIterator> {
@@ -1652,6 +1648,9 @@ public class TreeMap
public Map.Entry next() {
return prevEntry();
}
+ public void remove() {
+ removeDescending();
+ }
}
final class DescendingSubMapKeyIterator extends SubMapIterator {
@@ -1662,15 +1661,21 @@ public class TreeMap
public K next() {
return prevEntry().key;
}
+ public void remove() {
+ removeDescending();
+ }
}
}
+ /**
+ * @serial include
+ */
static final class AscendingSubMap extends NavigableSubMap {
private static final long serialVersionUID = 912986545866124060L;
AscendingSubMap(TreeMap m,
boolean fromStart, K lo, boolean loInclusive,
- boolean toEnd, K hi, boolean hiInclusive) {
+ boolean toEnd, K hi, boolean hiInclusive) {
super(m, fromStart, lo, loInclusive, toEnd, hi, hiInclusive);
}
@@ -1679,7 +1684,7 @@ public class TreeMap
}
public NavigableMap subMap(K fromKey, boolean fromInclusive,
- K toKey, boolean toInclusive) {
+ K toKey, boolean toInclusive) {
if (!inRange(fromKey, fromInclusive))
throw new IllegalArgumentException("fromKey out of range");
if (!inRange(toKey, toInclusive))
@@ -1690,7 +1695,7 @@ public class TreeMap
}
public NavigableMap headMap(K toKey, boolean inclusive) {
- if (!inClosedRange(toKey))
+ if (!inRange(toKey, inclusive))
throw new IllegalArgumentException("toKey out of range");
return new AscendingSubMap(m,
fromStart, lo, loInclusive,
@@ -1741,11 +1746,14 @@ public class TreeMap
TreeMap.Entry subLower(K key) { return absLower(key); }
}
+ /**
+ * @serial include
+ */
static final class DescendingSubMap extends NavigableSubMap {
private static final long serialVersionUID = 912986545866120460L;
DescendingSubMap(TreeMap m,
boolean fromStart, K lo, boolean loInclusive,
- boolean toEnd, K hi, boolean hiInclusive) {
+ boolean toEnd, K hi, boolean hiInclusive) {
super(m, fromStart, lo, loInclusive, toEnd, hi, hiInclusive);
}
@@ -1757,7 +1765,7 @@ public class TreeMap
}
public NavigableMap subMap(K fromKey, boolean fromInclusive,
- K toKey, boolean toInclusive) {
+ K toKey, boolean toInclusive) {
if (!inRange(fromKey, fromInclusive))
throw new IllegalArgumentException("fromKey out of range");
if (!inRange(toKey, toInclusive))
@@ -1820,27 +1828,13 @@ public class TreeMap
}
/**
- * Compares two keys using the correct comparison method for this TreeMap.
- */
- final int compare(Object k1, Object k2) {
- return comparator==null ? ((Comparable)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 null 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
* a new-version AscendingSubMap. This class is never otherwise
* used.
+ *
+ * @serial include
*/
private class SubMap extends AbstractMap
implements SortedMap, java.io.Serializable {
@@ -1862,6 +1856,8 @@ public class TreeMap
}
+ // Red-black mechanics
+
private static final boolean RED = false;
private static final boolean BLACK = true;
@@ -1922,7 +1918,7 @@ public class TreeMap
public boolean equals(Object o) {
if (!(o instanceof Map.Entry))
return false;
- Map.Entry e = (Map.Entry)o;
+ Map.Entry e = (Map.Entry)o;
return valEquals(key,e.getKey()) && valEquals(value,e.getValue());
}
@@ -2037,40 +2033,43 @@ public class TreeMap
return (p == null) ? null: p.right;
}
- /** From CLR **/
+ /** From CLR */
private void rotateLeft(Entry p) {
- Entry 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 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 p) {
- Entry 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 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 x) {
x.color = RED;
@@ -2089,8 +2088,7 @@ public class TreeMap
}
setColor(parentOf(x), BLACK);
setColor(parentOf(parentOf(x)), RED);
- if (parentOf(parentOf(x)) != null)
- rotateRight(parentOf(parentOf(x)));
+ rotateRight(parentOf(parentOf(x)));
}
} else {
Entry y = leftOf(parentOf(parentOf(x)));
@@ -2106,8 +2104,7 @@ public class TreeMap
}
setColor(parentOf(x), BLACK);
setColor(parentOf(parentOf(x)), RED);
- if (parentOf(parentOf(x)) != null)
- rotateLeft(parentOf(parentOf(x)));
+ rotateLeft(parentOf(parentOf(x)));
}
}
}
@@ -2117,9 +2114,9 @@ public class TreeMap
/**
* Delete node p, and then rebalance the tree.
*/
-
private void deleteEntry(Entry p) {
- decrementSize();
+ modCount++;
+ size--;
// If strictly internal, copy successor's element to p and then make p
// point to successor.
@@ -2165,7 +2162,7 @@ public class TreeMap
}
}
- /** From CLR **/
+ /** From CLR */
private void fixAfterDeletion(Entry x) {
while (x != root && colorOf(x) == BLACK) {
if (x == leftOf(parentOf(x))) {
@@ -2273,13 +2270,13 @@ public class TreeMap
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 set, V defaultVal) {
try {
buildFromSorted(set.size(), set.iterator(), null, defaultVal);
@@ -2362,7 +2359,7 @@ public class TreeMap
if (hi < lo) return null;
- int mid = (lo + hi) / 2;
+ int mid = (lo + hi) >>> 1;
Entry left = null;
if (lo < mid)