--- jsr166/src/main/java/util/TreeMap.java 2006/04/21 13:42:57 1.31
+++ jsr166/src/main/java/util/TreeMap.java 2006/05/09 18:17:08 1.37
@@ -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 super K> 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 super K> k = (Comparable super K>) 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 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(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 super K> 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 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(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
@@ -902,8 +845,8 @@ public class TreeMap
NavigableMap km = descendingMap;
return (km != null) ? km :
(descendingMap = new DescendingSubMap(this,
- true, null, 0,
- true, null, 0));
+ true, null, true,
+ true, null, true));
}
/**
@@ -917,8 +860,8 @@ public class TreeMap
public NavigableMap subMap(K fromKey, boolean fromInclusive,
K toKey, boolean toInclusive) {
return new AscendingSubMap(this,
- false, fromKey, excluded(fromInclusive),
- false, toKey, excluded(toInclusive));
+ false, fromKey, fromInclusive,
+ false, toKey, toInclusive);
}
/**
@@ -931,8 +874,8 @@ public class TreeMap
*/
public NavigableMap headMap(K toKey, boolean inclusive) {
return new AscendingSubMap(this,
- true, null, 0,
- false, toKey, excluded(inclusive));
+ true, null, true,
+ false, toKey, inclusive);
}
/**
@@ -945,16 +888,8 @@ public class TreeMap
*/
public NavigableMap tailMap(K fromKey, boolean inclusive) {
return new AscendingSubMap(this,
- false, fromKey, excluded(inclusive),
- true, null, 0);
- }
-
- /**
- * Translates a boolean "inclusive" value to the correct int value
- * for the loExcluded or hiExcluded field.
- */
- static int excluded(boolean inclusive) {
- return inclusive ? 0 : 1;
+ false, fromKey, inclusive,
+ true, null, true);
}
/**
@@ -1002,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) {
@@ -1118,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));
}
@@ -1185,6 +1117,7 @@ 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);
@@ -1229,55 +1162,118 @@ 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 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 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
+ /**
+ * @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, loExcluded)
- * and (toEnd, hi, hiExcluded). If fromStart is true, then
- * the low (absolute) bound is the start of the backing map, and the
- * other values are ignored. Otherwise, if loExcluded is
- * zero, lo is the inclusive bound, else loExcluded is one,
- * and lo is the exclusive bound. Similarly for the upper bound.
+ /**
+ * 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
+ * backing map, and the other values are ignored. Otherwise,
+ * 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 int loExcluded, hiExcluded;
+ final boolean loInclusive, hiInclusive;
NavigableSubMap(TreeMap m,
- boolean fromStart, K lo, int loExcluded,
- boolean toEnd, K hi, int hiExcluded) {
+ boolean fromStart, K lo, boolean loInclusive,
+ boolean toEnd, K hi, boolean hiInclusive) {
if (!fromStart && !toEnd) {
if (m.compare(lo, hi) > 0)
throw new IllegalArgumentException("fromKey > toKey");
+ } else {
+ if (!fromStart) // type check
+ m.compare(lo, lo);
+ if (!toEnd)
+ m.compare(hi, hi);
}
- else if (!fromStart) // type check
- m.compare(lo, lo);
- else if (!toEnd)
- m.compare(hi, hi);
this.m = m;
this.fromStart = fromStart;
this.lo = lo;
- this.loExcluded = loExcluded;
+ this.loInclusive = loInclusive;
this.toEnd = toEnd;
this.hi = hi;
- this.hiExcluded = hiExcluded;
+ this.hiInclusive = hiInclusive;
}
// internal utilities
+ final boolean tooLow(Object key) {
+ if (!fromStart) {
+ int c = m.compare(key, lo);
+ if (c < 0 || (c == 0 && !loInclusive))
+ return true;
+ }
+ return false;
+ }
+
+ final boolean tooHigh(Object key) {
+ if (!toEnd) {
+ int c = m.compare(key, hi);
+ if (c > 0 || (c == 0 && !hiInclusive))
+ return true;
+ }
+ return false;
+ }
+
final boolean inRange(Object key) {
- return (fromStart || m.compare(key, lo) >= loExcluded)
- && (toEnd || m.compare(hi, key) >= hiExcluded);
+ return !tooLow(key) && !tooHigh(key);
}
final boolean inClosedRange(Object key) {
@@ -1289,148 +1285,176 @@ public class TreeMap
return inclusive ? inRange(key) : inClosedRange(key);
}
- final boolean tooLow(K key) {
- return !fromStart && m.compare(key, lo) < loExcluded;
- }
-
- final boolean tooHigh(K key) {
- return !toEnd && m.compare(hi, key) < hiExcluded;
- }
+ /*
+ * Absolute versions of relation operations.
+ * Subclasses map to these using like-named "sub"
+ * versions that invert senses for descending maps
+ */
- /** Returns the lowest entry in this submap (absolute ordering) */
- final TreeMap.Entry loEntry() {
- TreeMap.Entry result =
+ final TreeMap.Entry absLowest() {
+ TreeMap.Entry e =
(fromStart ? m.getFirstEntry() :
- (loExcluded == 0 ? m.getCeilingEntry(lo) :
- m.getHigherEntry(lo)));
- return (result == null || tooHigh(result.key)) ? null : result;
+ (loInclusive ? m.getCeilingEntry(lo) :
+ m.getHigherEntry(lo)));
+ return (e == null || tooHigh(e.key)) ? null : e;
}
- /** Returns the highest key in this submap (absolute ordering) */
- final TreeMap.Entry hiEntry() {
- TreeMap.Entry result =
+ final TreeMap.Entry absHighest() {
+ TreeMap.Entry e =
(toEnd ? m.getLastEntry() :
- (hiExcluded == 0 ? m.getFloorEntry(hi) :
- m.getLowerEntry(hi)));
- return (result == null || tooLow(result.key)) ? null : result;
+ (hiInclusive ? m.getFloorEntry(hi) :
+ m.getLowerEntry(hi)));
+ return (e == null || tooLow(e.key)) ? null : e;
}
- /** Polls the lowest entry in this submap (absolute ordering) */
- final Map.Entry pollLoEntry() {
- TreeMap.Entry e = loEntry();
- if (e == null)
- return null;
- Map.Entry result = new AbstractMap.SimpleImmutableEntry(e);
- m.deleteEntry(e);
- return result;
+ final TreeMap.Entry absCeiling(K key) {
+ if (tooLow(key))
+ return absLowest();
+ TreeMap.Entry e = m.getCeilingEntry(key);
+ return (e == null || tooHigh(e.key)) ? null : e;
}
- /** Polls the highest key in this submap (absolute ordering) */
- final Map.Entry pollHiEntry() {
- TreeMap.Entry e = hiEntry();
- if (e == null)
- return null;
- Map.Entry result = new AbstractMap.SimpleImmutableEntry(e);
- m.deleteEntry(e);
- return result;
+ final TreeMap.Entry absHigher(K key) {
+ if (tooLow(key))
+ return absLowest();
+ TreeMap.Entry e = m.getHigherEntry(key);
+ return (e == null || tooHigh(e.key)) ? null : e;
}
- /**
- * Return the absolute high fence for ascending traversal
- */
- final TreeMap.Entry hiFence() {
- if (toEnd)
- return null;
- else if (hiExcluded == 0)
- return m.getHigherEntry(hi);
- else
- return m.getCeilingEntry(hi);
+ final TreeMap.Entry absFloor(K key) {
+ if (tooHigh(key))
+ return absHighest();
+ TreeMap.Entry e = m.getFloorEntry(key);
+ return (e == null || tooLow(e.key)) ? null : e;
}
- /**
- * Return the absolute low fence for descending traversal
- */
- final TreeMap.Entry loFence() {
- if (fromStart)
- return null;
- else if (loExcluded == 0)
- return m.getLowerEntry(lo);
- else
- return m.getFloorEntry(lo);
+ final TreeMap.Entry absLower(K key) {
+ if (tooHigh(key))
+ return absHighest();
+ TreeMap.Entry e = m.getLowerEntry(key);
+ return (e == null || tooLow(e.key)) ? null : e;
}
+ /** Returns the absolute high fence for ascending traversal */
+ final TreeMap.Entry absHighFence() {
+ return (toEnd ? null : (hiInclusive ?
+ m.getHigherEntry(hi) :
+ m.getCeilingEntry(hi)));
+ }
+
+ /** Return the absolute low fence for descending traversal */
+ final TreeMap.Entry absLowFence() {
+ return (fromStart ? null : (loInclusive ?
+ m.getLowerEntry(lo) :
+ m.getFloorEntry(lo)));
+ }
+
+ // Abstract methods defined in ascending vs descending classes
+ // These relay to the appropriate absolute versions
+
+ abstract TreeMap.Entry subLowest();
+ abstract TreeMap.Entry subHighest();
+ abstract TreeMap.Entry subCeiling(K key);
+ abstract TreeMap.Entry subHigher(K key);
+ abstract TreeMap.Entry subFloor(K key);
+ abstract TreeMap.Entry subLower(K key);
+
+ /** Returns ascending iterator from the perspective of this submap */
+ abstract Iterator keyIterator();
+
+ /** Returns descending iterator from the perspective of this submap */
+ abstract Iterator descendingKeyIterator();
+
+ // public methods
public boolean isEmpty() {
- return entrySet().isEmpty();
+ return (fromStart && toEnd) ? m.isEmpty() : entrySet().isEmpty();
}
- public boolean containsKey(Object key) {
- return inRange(key) && m.containsKey(key);
+ public int size() {
+ return (fromStart && toEnd) ? m.size() : entrySet().size();
}
- public V get(Object key) {
- if (!inRange(key))
- return null;
- return m.get(key);
+ public final boolean containsKey(Object key) {
+ return inRange(key) && m.containsKey(key);
}
- public V put(K key, V value) {
+ public final V put(K key, V value) {
if (!inRange(key))
throw new IllegalArgumentException("key out of range");
return m.put(key, value);
}
- public V remove(Object key) {
- if (!inRange(key))
- return null;
- return m.remove(key);
+ public final V get(Object key) {
+ return !inRange(key)? null : m.get(key);
}
- public Map.Entry ceilingEntry(K key) {
- TreeMap.Entry e = subCeiling(key);
- return e == null? null : new AbstractMap.SimpleImmutableEntry(e);
+ public final V remove(Object key) {
+ return !inRange(key)? null : m.remove(key);
}
- public K ceilingKey(K key) {
- TreeMap.Entry e = subCeiling(key);
- return e == null? null : e.key;
+ public final Map.Entry ceilingEntry(K key) {
+ return exportEntry(subCeiling(key));
}
- public Map.Entry higherEntry(K key) {
- TreeMap.Entry e = subHigher(key);
- return e == null? null : new AbstractMap.SimpleImmutableEntry(e);
+ public final K ceilingKey(K key) {
+ return keyOrNull(subCeiling(key));
}
- public K higherKey(K key) {
- TreeMap.Entry e = subHigher(key);
- return e == null? null : e.key;
+ public final Map.Entry higherEntry(K key) {
+ return exportEntry(subHigher(key));
}
- public Map.Entry floorEntry(K key) {
- TreeMap.Entry e = subFloor(key);
- return e == null? null : new AbstractMap.SimpleImmutableEntry(e);
+ public final K higherKey(K key) {
+ return keyOrNull(subHigher(key));
}
- public K floorKey(K key) {
- TreeMap.Entry e = subFloor(key);
- return e == null? null : e.key;
+ public final Map.Entry floorEntry(K key) {
+ return exportEntry(subFloor(key));
}
- public Map.Entry lowerEntry(K key) {
- TreeMap.Entry e = subLower(key);
- return e == null? null : new AbstractMap.SimpleImmutableEntry(e);
+ public final K floorKey(K key) {
+ return keyOrNull(subFloor(key));
}
- public K lowerKey(K key) {
- TreeMap.Entry e = subLower(key);
- return e == null? null : e.key;
+ public final Map.Entry lowerEntry(K key) {
+ return exportEntry(subLower(key));
}
- abstract Iterator keyIterator();
- abstract Iterator descendingKeyIterator();
+ public final K lowerKey(K key) {
+ return keyOrNull(subLower(key));
+ }
- public NavigableSet descendingKeySet() {
- return descendingMap().navigableKeySet();
+ public final K firstKey() {
+ return key(subLowest());
+ }
+
+ public final K lastKey() {
+ return key(subHighest());
+ }
+
+ public final Map.Entry firstEntry() {
+ return exportEntry(subLowest());
+ }
+
+ public final Map.Entry lastEntry() {
+ return exportEntry(subHighest());
+ }
+
+ public final Map.Entry pollFirstEntry() {
+ TreeMap.Entry e = subLowest();
+ Map.Entry result = exportEntry(e);
+ if (e != null)
+ m.deleteEntry(e);
+ return result;
+ }
+
+ public final Map.Entry pollLastEntry() {
+ TreeMap.Entry e = subHighest();
+ Map.Entry result = exportEntry(e);
+ if (e != null)
+ m.deleteEntry(e);
+ return result;
}
// Views
@@ -1438,6 +1462,34 @@ public class TreeMap
transient EntrySetView entrySetView = null;
transient KeySet navigableKeySetView = null;
+ public final NavigableSet navigableKeySet() {
+ KeySet nksv = navigableKeySetView;
+ return (nksv != null) ? nksv :
+ (navigableKeySetView = new TreeMap.KeySet(this));
+ }
+
+ public final Set keySet() {
+ return navigableKeySet();
+ }
+
+ public NavigableSet descendingKeySet() {
+ return descendingMap().navigableKeySet();
+ }
+
+ public final SortedMap subMap(K fromKey, K toKey) {
+ return subMap(fromKey, true, toKey, false);
+ }
+
+ public final SortedMap headMap(K toKey) {
+ return headMap(toKey, false);
+ }
+
+ public final SortedMap tailMap(K fromKey) {
+ return tailMap(fromKey, true);
+ }
+
+ // View classes
+
abstract class EntrySetView extends AbstractSet> {
private transient int size = -1, sizeModCount;
@@ -1457,7 +1509,7 @@ public class TreeMap
}
public boolean isEmpty() {
- TreeMap.Entry n = loEntry();
+ TreeMap.Entry n = absLowest();
return n == null || tooHigh(n.key);
}
@@ -1489,81 +1541,6 @@ public class TreeMap
}
}
- public NavigableSet navigableKeySet() {
- KeySet nksv = navigableKeySetView;
- return (nksv != null) ? nksv :
- (navigableKeySetView = new TreeMap.KeySet(this));
- }
-
- public Set keySet() {
- return navigableKeySet();
- }
-
- public SortedMap subMap(K fromKey, K toKey) {
- return subMap(fromKey, true, toKey, false);
- }
-
- public SortedMap headMap(K toKey) {
- return headMap(toKey, false);
- }
-
- public SortedMap tailMap(K fromKey) {
- return tailMap(fromKey, true);
- }
-
- // The following four definitions are correct only for
- // ascending submaps. They are overridden in DescendingSubMap.
- // They are defined in the base class because the definitions
- // in DescendingSubMap rely on those for AscendingSubMap.
-
- /**
- * Returns the entry corresponding to the ceiling of the specified
- * key from the perspective of this submap, or null if the submap
- * contains no such entry.
- */
- TreeMap.Entry subCeiling(K key) {
- if (tooLow(key))
- return loEntry();
- TreeMap.Entry e = m.getCeilingEntry(key);
- return (e == null || tooHigh(e.key)) ? null : e;
- }
-
- /**
- * Returns the entry corresponding to the higher of the specified
- * key from the perspective of this submap, or null if the submap
- * contains no such entry.
- */
- TreeMap.Entry subHigher(K key) {
- if (tooLow(key))
- return loEntry();
- TreeMap.Entry e = m.getHigherEntry(key);
- return (e == null || tooHigh(e.key)) ? null : e;
- }
-
- /**
- * Returns the entry corresponding to the floor of the specified
- * key from the perspective of this submap, or null if the submap
- * contains no such entry.
- */
- TreeMap.Entry subFloor(K key) {
- if (tooHigh(key))
- return hiEntry();
- TreeMap.Entry e = m.getFloorEntry(key);
- return (e == null || tooLow(e.key)) ? null : e;
- }
-
- /**
- * Returns the entry corresponding to the lower of the specified
- * key from the perspective of this submap, or null if the submap
- * contains no such entry.
- */
- TreeMap.Entry subLower(K key) {
- if (tooHigh(key))
- return hiEntry();
- TreeMap.Entry e = m.getLowerEntry(key);
- return (e == null || tooLow(e.key)) ? null : e;
- }
-
/**
* Iterators for SubMaps
*/
@@ -1605,17 +1582,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> {
@@ -1626,6 +1615,9 @@ public class TreeMap
public Map.Entry next() {
return nextEntry();
}
+ public void remove() {
+ removeAscending();
+ }
}
final class SubMapKeyIterator extends SubMapIterator {
@@ -1636,37 +1628,49 @@ public class TreeMap
public K next() {
return nextEntry().key;
}
+ public void remove() {
+ removeAscending();
+ }
}
final class DescendingSubMapEntryIterator extends SubMapIterator> {
DescendingSubMapEntryIterator(TreeMap.Entry last,
- TreeMap.Entry lastExcluded) {
- super(last, lastExcluded);
+ TreeMap.Entry fence) {
+ super(last, fence);
}
public Map.Entry next() {
return prevEntry();
}
+ public void remove() {
+ removeDescending();
+ }
}
final class DescendingSubMapKeyIterator extends SubMapIterator {
DescendingSubMapKeyIterator(TreeMap.Entry last,
- TreeMap.Entry lastExcluded) {
- super(last, lastExcluded);
+ TreeMap.Entry fence) {
+ super(last, fence);
}
public K next() {
return prevEntry().key;
}
+ public void remove() {
+ removeDescending();
+ }
}
}
- static class AscendingSubMap extends NavigableSubMap {
+ /**
+ * @serial include
+ */
+ static final class AscendingSubMap extends NavigableSubMap {
private static final long serialVersionUID = 912986545866124060L;
AscendingSubMap(TreeMap m,
- boolean fromStart, K lo, int loExcluded,
- boolean toEnd, K hi, int hiExcluded) {
- super(m, fromStart, lo, loExcluded, toEnd, hi, hiExcluded);
+ boolean fromStart, K lo, boolean loInclusive,
+ boolean toEnd, K hi, boolean hiInclusive) {
+ super(m, fromStart, lo, loInclusive, toEnd, hi, hiInclusive);
}
public Comparator super K> comparator() {
@@ -1674,43 +1678,52 @@ 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))
throw new IllegalArgumentException("toKey out of range");
return new AscendingSubMap(m,
- false, fromKey, excluded(fromInclusive),
- false, toKey, excluded(toInclusive));
+ false, fromKey, fromInclusive,
+ false, toKey, toInclusive);
}
public NavigableMap headMap(K toKey, boolean inclusive) {
if (!inClosedRange(toKey))
throw new IllegalArgumentException("toKey out of range");
return new AscendingSubMap(m,
- fromStart, lo, loExcluded,
- false, toKey, excluded(inclusive));
+ fromStart, lo, loInclusive,
+ false, toKey, inclusive);
}
public NavigableMap tailMap(K fromKey, boolean inclusive){
if (!inRange(fromKey, inclusive))
throw new IllegalArgumentException("fromKey out of range");
return new AscendingSubMap(m,
- false, fromKey, excluded(inclusive),
- toEnd, hi, hiExcluded);
+ false, fromKey, inclusive,
+ toEnd, hi, hiInclusive);
+ }
+
+ public NavigableMap descendingMap() {
+ NavigableMap mv = descendingMapView;
+ return (mv != null) ? mv :
+ (descendingMapView =
+ new DescendingSubMap(m,
+ fromStart, lo, loInclusive,
+ toEnd, hi, hiInclusive));
}
Iterator keyIterator() {
- return new SubMapKeyIterator(loEntry(), hiFence());
+ return new SubMapKeyIterator(absLowest(), absHighFence());
}
Iterator descendingKeyIterator() {
- return new DescendingSubMapKeyIterator(hiEntry(), loFence());
+ return new DescendingSubMapKeyIterator(absHighest(), absLowFence());
}
- class AscendingEntrySetView extends NavigableSubMap.EntrySetView {
+ final class AscendingEntrySetView extends EntrySetView {
public Iterator> iterator() {
- return new SubMapEntryIterator(loEntry(), hiFence());
+ return new SubMapEntryIterator(absLowest(), absHighFence());
}
}
@@ -1719,46 +1732,23 @@ public class TreeMap
return (es != null) ? es : new AscendingEntrySetView();
}
- public K firstKey() {
- return key(loEntry());
- }
-
- public K lastKey() {
- return key(hiEntry());
- }
-
- public Map.Entry firstEntry() {
- return loEntry();
- }
-
- public Map.Entry lastEntry() {
- return hiEntry();
- }
-
- public Map.Entry pollFirstEntry() {
- return pollLoEntry();
- }
-
- public Map.Entry pollLastEntry() {
- return pollHiEntry();
- }
-
- public NavigableMap descendingMap() {
- NavigableMap mv = descendingMapView;
- return (mv != null) ? mv :
- (descendingMapView =
- new DescendingSubMap(m,
- fromStart, lo, loExcluded,
- toEnd, hi, hiExcluded));
- }
+ TreeMap.Entry subLowest() { return absLowest(); }
+ TreeMap.Entry subHighest() { return absHighest(); }
+ TreeMap.Entry subCeiling(K key) { return absCeiling(key); }
+ TreeMap.Entry subHigher(K key) { return absHigher(key); }
+ TreeMap.Entry subFloor(K key) { return absFloor(key); }
+ TreeMap.Entry subLower(K key) { return absLower(key); }
}
- static class DescendingSubMap extends NavigableSubMap {
+ /**
+ * @serial include
+ */
+ static final class DescendingSubMap extends NavigableSubMap {
private static final long serialVersionUID = 912986545866120460L;
DescendingSubMap(TreeMap m,
- boolean fromStart, K lo, int loExcluded,
- boolean toEnd, K hi, int hiExcluded) {
- super(m, fromStart, lo, loExcluded, toEnd, hi, hiExcluded);
+ boolean fromStart, K lo, boolean loInclusive,
+ boolean toEnd, K hi, boolean hiInclusive) {
+ super(m, fromStart, lo, loInclusive, toEnd, hi, hiInclusive);
}
private final Comparator super K> reverseComparator =
@@ -1769,73 +1759,30 @@ 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))
throw new IllegalArgumentException("toKey out of range");
return new DescendingSubMap(m,
- false, toKey, excluded(toInclusive),
- false, fromKey, excluded(fromInclusive));
+ false, toKey, toInclusive,
+ false, fromKey, fromInclusive);
}
public NavigableMap headMap(K toKey, boolean inclusive) {
if (!inRange(toKey, inclusive))
throw new IllegalArgumentException("toKey out of range");
return new DescendingSubMap(m,
- false, toKey, excluded(inclusive),
- toEnd, hi, hiExcluded);
+ false, toKey, inclusive,
+ toEnd, hi, hiInclusive);
}
public NavigableMap tailMap(K fromKey, boolean inclusive){
if (!inRange(fromKey, inclusive))
throw new IllegalArgumentException("fromKey out of range");
return new DescendingSubMap(m,
- fromStart, lo, loExcluded,
- false, fromKey, excluded(inclusive));
- }
-
- Iterator keyIterator() {
- return new DescendingSubMapKeyIterator(hiEntry(), loFence());
- }
-
- Iterator descendingKeyIterator() {
- return new SubMapKeyIterator(loEntry(), hiFence());
- }
-
- class DescendingEntrySetView extends NavigableSubMap.EntrySetView {
- public Iterator> iterator() {
- return new DescendingSubMapEntryIterator(hiEntry(), loFence());
- }
- }
-
- public Set> entrySet() {
- EntrySetView es = entrySetView;
- return (es != null) ? es : new DescendingEntrySetView();
- }
-
- public K firstKey() {
- return key(hiEntry());
- }
-
- public K lastKey() {
- return key(loEntry());
- }
-
- public Map.Entry firstEntry() {
- return hiEntry();
- }
-
- public Map.Entry lastEntry() {
- return loEntry();
- }
-
- public Map.Entry pollFirstEntry() {
- return pollHiEntry();
- }
-
- public Map.Entry pollLastEntry() {
- return pollLoEntry();
+ fromStart, lo, loInclusive,
+ false, fromKey, inclusive);
}
public NavigableMap descendingMap() {
@@ -1843,41 +1790,35 @@ public class TreeMap
return (mv != null) ? mv :
(descendingMapView =
new AscendingSubMap(m,
- fromStart, lo, loExcluded,
- toEnd, hi, hiExcluded));
+ fromStart, lo, loInclusive,
+ toEnd, hi, hiInclusive));
}
- @Override TreeMap.Entry