--- jsr166/src/main/java/util/TreeMap.java 2006/04/22 23:02:25 1.33
+++ jsr166/src/main/java/util/TreeMap.java 2010/09/01 07:48:47 1.49
@@ -1,8 +1,26 @@
/*
- * %W% %E%
+ * Copyright 1997-2008 Sun Microsystems, Inc. All Rights Reserved.
+ * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
*
- * Copyright 2006 Sun Microsystems, Inc. All rights reserved.
- * SUN PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
+ * This code is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License version 2 only, as
+ * published by the Free Software Foundation. Sun designates this
+ * particular file as subject to the "Classpath" exception as provided
+ * by Sun in the LICENSE file that accompanied this code.
+ *
+ * This code is distributed in the hope that it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
+ * version 2 for more details (a copy is included in the LICENSE file that
+ * accompanied this code).
+ *
+ * You should have received a copy of the GNU General Public License version
+ * 2 along with this work; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
+ *
+ * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
+ * CA 95054 USA or visit www.sun.com if you need additional information or
+ * have any questions.
*/
package java.util;
@@ -68,14 +86,13 @@ 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
* @param the type of mapped values
*
* @author Josh Bloch and Doug Lea
- * @version %I%, %G%
* @see Map
* @see HashMap
* @see Hashtable
@@ -219,32 +236,14 @@ public class TreeMap
*
* @param value value whose presence in this map is to be tested
* @return true if a mapping to value exists;
- * false otherwise
+ * false otherwise
* @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;
}
/**
@@ -309,14 +308,14 @@ public class TreeMap
if (size==0 && mapSize!=0 && map instanceof SortedMap) {
Comparator c = ((SortedMap)map).comparator();
if (c == comparator || (c != null && c.equals(comparator))) {
- ++modCount;
- try {
- buildFromSorted(mapSize, map.entrySet().iterator(),
- null, null);
- } catch (java.io.IOException cannotHappen) {
- } catch (ClassNotFoundException cannotHappen) {
- }
- return;
+ ++modCount;
+ try {
+ buildFromSorted(mapSize, map.entrySet().iterator(),
+ null, null);
+ } catch (java.io.IOException cannotHappen) {
+ } catch (ClassNotFoundException cannotHappen) {
+ }
+ return;
}
}
super.putAll(map);
@@ -340,7 +339,7 @@ public class TreeMap
return getEntryUsingComparator(key);
if (key == null)
throw new NullPointerException();
- Comparable k = (Comparable) key;
+ Comparable k = (Comparable) key;
Entry p = root;
while (p != null) {
int cmp = k.compareTo(p.key);
@@ -358,20 +357,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;
+ 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;
}
@@ -524,73 +525,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;
- int cmp = 0;
- Entry parent = null;
Entry t = root;
- while (t != null) {
- parent = t;
- cmp = k.compareTo(t.key);
- if (cmp < 0)
- t = t.left;
- else if (cmp > 0)
- t = t.right;
- else
- return t.setValue(value);
- }
- Entry e = new Entry((K)k, value, parent);
- size++;
- modCount++;
- if (parent != null) {
- if (cmp < 0)
- parent.left = e;
- else
- parent.right = e;
- fixAfterInsertion(e);
+ 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;
}
- else
- root = e;
- return null;
- }
-
- /**
- * Version of put using comparator. Split off from put for
- * performance.
- */
- final V putUsingComparator(K key, V value) {
+ int cmp;
+ Entry parent;
+ // split comparator and comparable paths
Comparator cpr = comparator;
- int cmp = 0;
- Entry parent = null;
- Entry t = root;
- if (t == null)
- cpr.compare(key, key); // type check
- while (t != null) {
- parent = t;
- cmp = cpr.compare(key, t.key);
- if (cmp < 0)
- t = t.left;
- else if (cmp > 0)
- t = t.right;
- else
- return t.setValue(value);
+ if (cpr != null) {
+ do {
+ parent = t;
+ cmp = cpr.compare(key, t.key);
+ if (cmp < 0)
+ t = t.left;
+ else if (cmp > 0)
+ t = t.right;
+ else
+ return t.setValue(value);
+ } while (t != 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 if (cmp > 0)
+ t = t.right;
+ else
+ return t.setValue(value);
+ } while (t != null);
}
Entry e = new Entry(key, value, parent);
+ if (cmp < 0)
+ parent.left = e;
+ else
+ parent.right = e;
+ fixAfterInsertion(e);
size++;
modCount++;
- if (parent != null) {
- if (cmp < 0)
- parent.left = e;
- else
- parent.right = e;
- fixAfterInsertion(e);
- }
- else
- root = e;
return null;
}
@@ -969,10 +954,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) {
@@ -1039,7 +1021,7 @@ public class TreeMap
}
Iterator descendingKeyIterator() {
- return new DescendingKeyIterator(getFirstEntry());
+ return new DescendingKeyIterator(getLastEntry());
}
static final class KeySet extends AbstractSet implements NavigableSet {
@@ -1085,15 +1067,15 @@ public class TreeMap
return size() != oldSize;
}
public NavigableSet subSet(E fromElement, boolean fromInclusive,
- E toElement, boolean toInclusive) {
- return new TreeSet(m.subMap(fromElement, fromInclusive,
- toElement, toInclusive));
+ E toElement, boolean toInclusive) {
+ return new KeySet(m.subMap(fromElement, fromInclusive,
+ toElement, toInclusive));
}
public NavigableSet headSet(E toElement, boolean inclusive) {
- return new TreeSet(m.headMap(toElement, inclusive));
+ return new KeySet(m.headMap(toElement, inclusive));
}
public NavigableSet tailSet(E fromElement, boolean inclusive) {
- return new TreeSet(m.tailMap(fromElement, inclusive));
+ return new KeySet(m.tailMap(fromElement, inclusive));
}
public SortedSet subSet(E fromElement, E toElement) {
return subSet(fromElement, true, toElement, false);
@@ -1105,7 +1087,7 @@ public class TreeMap
return tailSet(fromElement, true);
}
public NavigableSet descendingSet() {
- return new TreeSet(m.descendingMap());
+ return new KeySet(m.descendingMap());
}
}
@@ -1127,23 +1109,25 @@ public class TreeMap
return next != null;
}
- final Entry nextEntry() {
- Entry e = lastReturned = next;
+ final Entry nextEntry() {
+ Entry e = next;
if (e == null)
throw new NoSuchElementException();
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
next = successor(e);
+ lastReturned = e;
return e;
}
final Entry prevEntry() {
- Entry e = lastReturned= next;
+ Entry e = next;
if (e == null)
throw new NoSuchElementException();
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
next = predecessor(e);
+ lastReturned = e;
return e;
}
@@ -1152,10 +1136,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;
}
}
@@ -1242,14 +1227,23 @@ public class TreeMap
// 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
@@ -1257,7 +1251,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;
@@ -1324,7 +1317,7 @@ public class TreeMap
*/
final TreeMap.Entry absLowest() {
- TreeMap.Entry e =
+ TreeMap.Entry e =
(fromStart ? m.getFirstEntry() :
(loInclusive ? m.getCeilingEntry(lo) :
m.getHigherEntry(lo)));
@@ -1332,7 +1325,7 @@ public class TreeMap
}
final TreeMap.Entry absHighest() {
- TreeMap.Entry e =
+ TreeMap.Entry e =
(toEnd ? m.getLastEntry() :
(hiInclusive ? m.getFloorEntry(hi) :
m.getLowerEntry(hi)));
@@ -1342,28 +1335,28 @@ public class TreeMap
final TreeMap.Entry absCeiling(K key) {
if (tooLow(key))
return absLowest();
- TreeMap.Entry e = m.getCeilingEntry(key);
+ TreeMap.Entry e = m.getCeilingEntry(key);
return (e == null || tooHigh(e.key)) ? null : e;
}
final TreeMap.Entry absHigher(K key) {
if (tooLow(key))
return absLowest();
- TreeMap.Entry e = m.getHigherEntry(key);
+ TreeMap.Entry e = m.getHigherEntry(key);
return (e == null || tooHigh(e.key)) ? null : e;
}
final TreeMap.Entry absFloor(K key) {
if (tooHigh(key))
return absHighest();
- TreeMap.Entry e = m.getFloorEntry(key);
+ TreeMap.Entry e = m.getFloorEntry(key);
return (e == null || tooLow(e.key)) ? null : e;
}
final TreeMap.Entry absLower(K key) {
if (tooHigh(key))
return absHighest();
- TreeMap.Entry e = m.getLowerEntry(key);
+ TreeMap.Entry e = m.getLowerEntry(key);
return (e == null || tooLow(e.key)) ? null : e;
}
@@ -1382,7 +1375,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();
@@ -1474,7 +1467,7 @@ public class TreeMap
}
public final Map.Entry pollFirstEntry() {
- TreeMap.Entry e = subLowest();
+ TreeMap.Entry e = subLowest();
Map.Entry result = exportEntry(e);
if (e != null)
m.deleteEntry(e);
@@ -1482,7 +1475,7 @@ public class TreeMap
}
public final Map.Entry pollLastEntry() {
- TreeMap.Entry e = subHighest();
+ TreeMap.Entry e = subHighest();
Map.Entry result = exportEntry(e);
if (e != null)
m.deleteEntry(e);
@@ -1579,7 +1572,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,
@@ -1587,7 +1580,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() {
@@ -1595,36 +1588,50 @@ public class TreeMap
}
final TreeMap.Entry nextEntry() {
- TreeMap.Entry e = lastReturned = next;
+ TreeMap.Entry e = next;
if (e == null || e.key == fenceKey)
throw new NoSuchElementException();
if (m.modCount != expectedModCount)
throw new ConcurrentModificationException();
next = successor(e);
+ lastReturned = e;
return e;
}
final TreeMap.Entry prevEntry() {
- TreeMap.Entry e = lastReturned = next;
+ TreeMap.Entry e = next;
if (e == null || e.key == fenceKey)
throw new NoSuchElementException();
if (m.modCount != expectedModCount)
throw new ConcurrentModificationException();
next = predecessor(e);
+ lastReturned = e;
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> {
@@ -1635,6 +1642,9 @@ public class TreeMap
public Map.Entry next() {
return nextEntry();
}
+ public void remove() {
+ removeAscending();
+ }
}
final class SubMapKeyIterator extends SubMapIterator {
@@ -1645,6 +1655,9 @@ public class TreeMap
public K next() {
return nextEntry().key;
}
+ public void remove() {
+ removeAscending();
+ }
}
final class DescendingSubMapEntryIterator extends SubMapIterator> {
@@ -1656,6 +1669,9 @@ public class TreeMap
public Map.Entry next() {
return prevEntry();
}
+ public void remove() {
+ removeDescending();
+ }
}
final class DescendingSubMapKeyIterator extends SubMapIterator {
@@ -1666,15 +1682,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);
}
@@ -1683,7 +1705,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))
@@ -1694,7 +1716,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,
@@ -1745,11 +1767,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);
}
@@ -1761,7 +1786,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))
@@ -1829,9 +1854,11 @@ public class TreeMap
* 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 {
+ implements SortedMap, java.io.Serializable {
private static final long serialVersionUID = -6520786458950516097L;
private boolean fromStart = false, toEnd = false;
private K fromKey, toKey;
@@ -1861,7 +1888,7 @@ public class TreeMap
*/
static final class Entry implements Map.Entry {
- K key;
+ K key;
V value;
Entry left = null;
Entry right = null;
@@ -1912,7 +1939,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());
}
@@ -2016,7 +2043,7 @@ public class TreeMap
private static void setColor(Entry p, boolean c) {
if (p != null)
- p.color = c;
+ p.color = c;
}
private static Entry leftOf(Entry p) {
@@ -2029,37 +2056,40 @@ public class TreeMap
/** 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 */
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 */
private void fixAfterInsertion(Entry x) {
x.color = RED;
@@ -2079,8 +2109,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)));
@@ -2096,8 +2125,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)));
}
}
}
@@ -2107,7 +2135,6 @@ public class TreeMap
/**
* Delete node p, and then rebalance the tree.
*/
-
private void deleteEntry(Entry p) {
modCount++;
size--;
@@ -2115,7 +2142,7 @@ public class TreeMap
// If strictly internal, copy successor's element to p and then make p
// point to successor.
if (p.left != null && p.right != null) {
- Entry s = successor (p);
+ Entry s = successor(p);
p.key = s.key;
p.value = s.value;
p = s;
@@ -2272,11 +2299,11 @@ public class TreeMap
/** Intended to be called only from TreeSet.addAll */
void addAllForTreeSet(SortedSet set, V defaultVal) {
- try {
- buildFromSorted(set.size(), set.iterator(), null, defaultVal);
- } catch (java.io.IOException cannotHappen) {
- } catch (ClassNotFoundException cannotHappen) {
- }
+ try {
+ buildFromSorted(set.size(), set.iterator(), null, defaultVal);
+ } catch (java.io.IOException cannotHappen) {
+ } catch (ClassNotFoundException cannotHappen) {
+ }
}
@@ -2311,12 +2338,12 @@ public class TreeMap
* This cannot occur if str is null.
*/
private void buildFromSorted(int size, Iterator it,
- java.io.ObjectInputStream str,
- V defaultVal)
+ java.io.ObjectInputStream str,
+ V defaultVal)
throws java.io.IOException, ClassNotFoundException {
this.size = size;
root = buildFromSorted(0, 0, size-1, computeRedLevel(size),
- it, str, defaultVal);
+ it, str, defaultVal);
}
/**
@@ -2334,10 +2361,10 @@ public class TreeMap
* Must be equal to computeRedLevel for tree of this size.
*/
private final Entry buildFromSorted(int level, int lo, int hi,
- int redLevel,
- Iterator it,
- java.io.ObjectInputStream str,
- V defaultVal)
+ int redLevel,
+ Iterator it,
+ java.io.ObjectInputStream str,
+ V defaultVal)
throws java.io.IOException, ClassNotFoundException {
/*
* Strategy: The root is the middlemost element. To get to it, we
@@ -2353,12 +2380,12 @@ public class TreeMap
if (hi < lo) return null;
- int mid = (lo + hi) / 2;
+ int mid = (lo + hi) >>> 1;
Entry left = null;
if (lo < mid)
left = buildFromSorted(level+1, lo, mid - 1, redLevel,
- it, str, defaultVal);
+ it, str, defaultVal);
// extract key and/or value from iterator or stream
K key;
@@ -2390,7 +2417,7 @@ public class TreeMap
if (mid < hi) {
Entry right = buildFromSorted(level+1, mid+1, hi, redLevel,
- it, str, defaultVal);
+ it, str, defaultVal);
middle.right = right;
right.parent = middle;
}