--- jsr166/src/main/java/util/TreeMap.java 2006/04/23 20:59:49 1.34
+++ jsr166/src/main/java/util/TreeMap.java 2007/05/21 20:23:38 1.44
@@ -1,8 +1,26 @@
/*
- * %W% %E%
+ * Copyright 1997-2007 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,7 +86,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
@@ -510,7 +528,11 @@ public class TreeMap
public V put(K key, V value) {
Entry t = root;
if (t == null) {
- compare(key, key); // type check
+ // 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++;
@@ -1046,7 +1068,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));
}
@@ -1089,22 +1111,24 @@ public class TreeMap
}
final Entry nextEntry() {
- Entry e = lastReturned = next;
+ 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;
}
@@ -1113,10 +1137,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;
}
}
@@ -1203,14 +1228,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
@@ -1218,7 +1252,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;
@@ -1343,7 +1376,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();
@@ -1540,7 +1573,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,
@@ -1548,7 +1581,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() {
@@ -1556,36 +1589,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> {
@@ -1596,6 +1643,9 @@ public class TreeMap
public Map.Entry next() {
return nextEntry();
}
+ public void remove() {
+ removeAscending();
+ }
}
final class SubMapKeyIterator extends SubMapIterator {
@@ -1606,6 +1656,9 @@ public class TreeMap
public K next() {
return nextEntry().key;
}
+ public void remove() {
+ removeAscending();
+ }
}
final class DescendingSubMapEntryIterator extends SubMapIterator> {
@@ -1617,6 +1670,9 @@ public class TreeMap
public Map.Entry next() {
return prevEntry();
}
+ public void remove() {
+ removeDescending();
+ }
}
final class DescendingSubMapKeyIterator extends SubMapIterator {
@@ -1627,15 +1683,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);
}
@@ -1644,7 +1706,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))
@@ -1655,7 +1717,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,
@@ -1706,11 +1768,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);
}
@@ -1722,7 +1787,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))
@@ -1790,6 +1855,8 @@ 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 {
@@ -1873,7 +1940,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());
}
@@ -2314,7 +2381,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)