--- jsr166/src/main/java/util/TreeMap.java 2005/06/16 02:11:13 1.18
+++ jsr166/src/main/java/util/TreeMap.java 2006/04/19 15:07:14 1.28
@@ -1,12 +1,11 @@
/*
* %W% %E%
*
- * Copyright 2005 Sun Microsystems, Inc. All rights reserved.
+ * Copyright 2006 Sun Microsystems, Inc. All rights reserved.
* SUN PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
*/
package java.util;
-import java.util.*; // for javadoc
/**
* A Red-Black tree based {@link NavigableMap} implementation.
@@ -31,19 +30,19 @@ import java.util.*; // for javadoc
* is well-defined even if its ordering is inconsistent with equals; it
* just fails to obey the general contract of the Map interface.
*
- * Note that this implementation is not synchronized. If multiple
- * threads access a map concurrently, and at least one of the threads modifies
- * the map structurally, it must be synchronized externally. (A
- * structural modification is any operation that adds or deletes one or more
- * mappings; merely changing the value associated with an existing key is not
- * a structural modification.) This is typically accomplished by
- * synchronizing on some object that naturally encapsulates the map. If no
- * such object exists, the map should be "wrapped" using the
- * Collections.synchronizedMap method. This is best done at creation
- * time, to prevent accidental unsynchronized access to the map:
- *
- * Map m = Collections.synchronizedMap(new TreeMap(...));
- *
+ * Note that this implementation is not synchronized.
+ * If multiple threads access a map concurrently, and at least one of the
+ * threads modifies the map structurally, it must be synchronized
+ * externally. (A structural modification is any operation that adds or
+ * deletes one or more mappings; merely changing the value associated
+ * with an existing key is not a structural modification.) This is
+ * typically accomplished by synchronizing on some object that naturally
+ * encapsulates the map.
+ * If no such object exists, the map should be "wrapped" using the
+ * {@link Collections#synchronizedSortedMap Collections.synchronizedSortedMap}
+ * method. This is best done at creation time, to prevent accidental
+ * unsynchronized access to the map:
+ * SortedMap m = Collections.synchronizedSortedMap(new TreeMap(...));
*
* The iterators returned by the iterator method of the collections
* returned by all of this class's "collection view methods" are
@@ -83,7 +82,6 @@ import java.util.*; // for javadoc
* @see Comparable
* @see Comparator
* @see Collection
- * @see Collections#synchronizedMap(Map)
* @since 1.2
*/
@@ -111,6 +109,15 @@ public class TreeMap
*/
private transient int modCount = 0;
+ /**
+ * A sentinel to indicate that an endpoint of a submap is not bounded.
+ * It is used to generate head maps, tail maps, and descending views
+ * of the entire backing map. The sentinel must be serializable,
+ * requiring a little class to express.
+ */
+ private static class Unbounded implements java.io.Serializable {}
+ private static final Unbounded UNBOUNDED = new Unbounded();
+
private void incrementSize() { modCount++; size++; }
private void decrementSize() { modCount++; size--; }
@@ -217,7 +224,8 @@ public class TreeMap
* specified value. More formally, returns true if and only if
* this map contains at least one mapping to a value v such
* that (value==null ? v==null : value.equals(v)). This
- * operation requires time linear in the map size.
+ * operation will probably require time linear in the map size for
+ * most implementations.
*
* @param value value whose presence in this map is to be tested
* @return true if a mapping to value exists;
@@ -250,16 +258,21 @@ public class TreeMap
}
/**
- * Returns the value to which this map maps the specified key, or
- * null if the map contains no mapping for the key. A return
- * value of null does not necessarily indicate that the
- * map contains no mapping for the key; it's also possible that the map
- * explicitly maps the key to null. The {@link #containsKey}
- * operation may be used to distinguish these two cases.
- *
- * @param key key whose associated value is to be returned
- * @return the value to which this map maps the specified key, or
- * null if the map contains no mapping for the key
+ * Returns the value to which the specified key is mapped,
+ * or {@code null} if this map contains no mapping for the key.
+ *
+ * More formally, if this map contains a mapping from a key
+ * {@code k} to a value {@code v} such that {@code key} compares
+ * equal to {@code k} according to the map's ordering, then this
+ * method returns {@code v}; otherwise it returns {@code null}.
+ * (There can be at most one such mapping.)
+ *
+ *
A return value of {@code null} does not necessarily
+ * indicate that the map contains no mapping for the key; it's also
+ * possible that the map explicitly maps the key to {@code null}.
+ * The {@link #containsKey containsKey} operation may be used to
+ * distinguish these two cases.
+ *
* @throws ClassCastException if the specified key cannot be compared
* with the keys currently in the map
* @throws NullPointerException if the specified key is null
@@ -335,6 +348,8 @@ public class TreeMap
// Offload comparator-based version for sake of performance
if (comparator != null)
return getEntryUsingComparator(key);
+ if (key == null)
+ throw new NullPointerException();
Comparable k = (Comparable) key;
Entry p = root;
while (p != null) {
@@ -520,7 +535,7 @@ public class TreeMap
/**
* Associates the specified value with the specified key in this map.
- * If the map previously contained a mapping for this key, the old
+ * If the map previously contained a mapping for the key, the old
* value is replaced.
*
* @param key key with which the specified value is to be associated
@@ -540,11 +555,12 @@ public class TreeMap
Entry t = root;
if (t == null) {
- if (key == null) {
- if (comparator == null)
- throw new NullPointerException();
- comparator.compare(key, key);
- }
+ // TBD
+// if (key == null) {
+// if (comparator == null)
+// throw new NullPointerException();
+// comparator.compare(key, key);
+// }
incrementSize();
root = new Entry(key, value, null);
return null;
@@ -629,8 +645,8 @@ public class TreeMap
clone.size = 0;
clone.modCount = 0;
clone.entrySet = null;
- clone.descendingEntrySet = null;
- clone.descendingKeySet = null;
+ clone.navigableKeySet = null;
+ clone.descendingMap = null;
// Initialize clone with our mappings
try {
@@ -644,16 +660,25 @@ public class TreeMap
// NavigableMap API methods
+ /**
+ * @since 1.6
+ */
public Map.Entry firstEntry() {
Entry e = getFirstEntry();
return (e == null)? null : new AbstractMap.SimpleImmutableEntry(e);
}
+ /**
+ * @since 1.6
+ */
public Map.Entry lastEntry() {
Entry e = getLastEntry();
return (e == null)? null : new AbstractMap.SimpleImmutableEntry(e);
}
+ /**
+ * @since 1.6
+ */
public Map.Entry pollFirstEntry() {
Entry p = getFirstEntry();
if (p == null)
@@ -663,6 +688,9 @@ public class TreeMap
return result;
}
+ /**
+ * @since 1.6
+ */
public Map.Entry pollLastEntry() {
Entry p = getLastEntry();
if (p == null)
@@ -677,6 +705,7 @@ public class TreeMap
* @throws NullPointerException if the specified key is null
* and this map uses natural ordering, or its comparator
* does not permit null keys
+ * @since 1.6
*/
public Map.Entry lowerEntry(K key) {
Entry e = getLowerEntry(key);
@@ -688,6 +717,7 @@ public class TreeMap
* @throws NullPointerException if the specified key is null
* and this map uses natural ordering, or its comparator
* does not permit null keys
+ * @since 1.6
*/
public K lowerKey(K key) {
Entry e = getLowerEntry(key);
@@ -699,6 +729,7 @@ public class TreeMap
* @throws NullPointerException if the specified key is null
* and this map uses natural ordering, or its comparator
* does not permit null keys
+ * @since 1.6
*/
public Map.Entry floorEntry(K key) {
Entry e = getFloorEntry(key);
@@ -710,6 +741,7 @@ public class TreeMap
* @throws NullPointerException if the specified key is null
* and this map uses natural ordering, or its comparator
* does not permit null keys
+ * @since 1.6
*/
public K floorKey(K key) {
Entry e = getFloorEntry(key);
@@ -721,6 +753,7 @@ public class TreeMap
* @throws NullPointerException if the specified key is null
* and this map uses natural ordering, or its comparator
* does not permit null keys
+ * @since 1.6
*/
public Map.Entry ceilingEntry(K key) {
Entry e = getCeilingEntry(key);
@@ -732,6 +765,7 @@ public class TreeMap
* @throws NullPointerException if the specified key is null
* and this map uses natural ordering, or its comparator
* does not permit null keys
+ * @since 1.6
*/
public K ceilingKey(K key) {
Entry e = getCeilingEntry(key);
@@ -743,6 +777,7 @@ public class TreeMap
* @throws NullPointerException if the specified key is null
* and this map uses natural ordering, or its comparator
* does not permit null keys
+ * @since 1.6
*/
public Map.Entry higherEntry(K key) {
Entry e = getHigherEntry(key);
@@ -754,6 +789,7 @@ public class TreeMap
* @throws NullPointerException if the specified key is null
* and this map uses natural ordering, or its comparator
* does not permit null keys
+ * @since 1.6
*/
public K higherKey(K key) {
Entry e = getHigherEntry(key);
@@ -768,8 +804,8 @@ public class TreeMap
* there's no reason to create more than one.
*/
private transient Set> entrySet = null;
- private transient Set> descendingEntrySet = null;
- private transient Set descendingKeySet = null;
+ private transient KeySet navigableKeySet = null;
+ private transient NavigableMap descendingMap = null;
/**
* Returns a {@link Set} view of the keys contained in this map.
@@ -786,32 +822,22 @@ public class TreeMap
* operations.
*/
public Set keySet() {
- Set ks = keySet;
- return (ks != null) ? ks : (keySet = new KeySet());
+ return navigableKeySet();
}
- class KeySet extends AbstractSet {
- public Iterator iterator() {
- return new KeyIterator(getFirstEntry());
- }
-
- public int size() {
- return TreeMap.this.size();
- }
-
- public boolean contains(Object o) {
- return containsKey(o);
- }
-
- public boolean remove(Object o) {
- int oldSize = size;
- TreeMap.this.remove(o);
- return size != oldSize;
- }
+ /**
+ * @since 1.6
+ */
+ public NavigableSet navigableKeySet() {
+ NavigableSet nks = navigableKeySet;
+ return (nks != null) ? nks : (navigableKeySet = new KeySet(this));
+ }
- public void clear() {
- TreeMap.this.clear();
- }
+ /**
+ * @since 1.6
+ */
+ public NavigableSet descendingKeySet() {
+ return descendingMap().navigableKeySet();
}
/**
@@ -834,37 +860,6 @@ public class TreeMap
return (vs != null) ? vs : (values = new Values());
}
- class Values extends AbstractCollection {
- public Iterator iterator() {
- return new ValueIterator(getFirstEntry());
- }
-
- public int size() {
- return TreeMap.this.size();
- }
-
- public boolean contains(Object o) {
- for (Entry e = getFirstEntry(); e != null; e = successor(e))
- if (valEquals(e.getValue(), o))
- return true;
- return false;
- }
-
- public boolean remove(Object o) {
- for (Entry e = getFirstEntry(); e != null; e = successor(e)) {
- if (valEquals(e.getValue(), o)) {
- deleteEntry(e);
- return true;
- }
- }
- return false;
- }
-
- public void clear() {
- TreeMap.this.clear();
- }
- }
-
/**
* Returns a {@link Set} view of the mappings contained in this map.
* The set's iterator returns the entries in ascending key order.
@@ -885,62 +880,14 @@ public class TreeMap
return (es != null) ? es : (entrySet = new EntrySet());
}
- class EntrySet extends AbstractSet> {
- public Iterator> iterator() {
- return new EntryIterator(getFirstEntry());
- }
-
- public boolean contains(Object o) {
- if (!(o instanceof Map.Entry))
- return false;
- Map.Entry entry = (Map.Entry) o;
- V value = entry.getValue();
- Entry p = getEntry(entry.getKey());
- return p != null && valEquals(p.getValue(), value);
- }
-
- public boolean remove(Object o) {
- if (!(o instanceof Map.Entry))
- return false;
- Map.Entry entry = (Map.Entry) o;
- V value = entry.getValue();
- Entry p = getEntry(entry.getKey());
- if (p != null && valEquals(p.getValue(), value)) {
- deleteEntry(p);
- return true;
- }
- return false;
- }
-
- public int size() {
- return TreeMap.this.size();
- }
-
- public void clear() {
- TreeMap.this.clear();
- }
- }
-
- public Set> descendingEntrySet() {
- Set> es = descendingEntrySet;
- return (es != null) ? es : (descendingEntrySet = new DescendingEntrySet());
- }
-
- class DescendingEntrySet extends EntrySet {
- public Iterator> iterator() {
- return new DescendingEntryIterator(getLastEntry());
- }
- }
-
- public Set descendingKeySet() {
- Set ks = descendingKeySet;
- return (ks != null) ? ks : (descendingKeySet = new DescendingKeySet());
- }
-
- class DescendingKeySet extends KeySet {
- public Iterator iterator() {
- return new DescendingKeyIterator(getLastEntry());
- }
+ /**
+ * @since 1.6
+ */
+ public NavigableMap descendingMap() {
+ NavigableMap km = descendingMap;
+ return (km != null) ? km :
+ (descendingMap = new DescendingSubMap((K)UNBOUNDED, 0,
+ (K)UNBOUNDED, 0));
}
/**
@@ -949,9 +896,12 @@ public class TreeMap
* null and this map uses natural ordering, or its comparator
* does not permit null keys
* @throws IllegalArgumentException {@inheritDoc}
+ * @since 1.6
*/
- public NavigableMap navigableSubMap(K fromKey, K toKey) {
- return new SubMap(fromKey, toKey);
+ public NavigableMap navigableSubMap(K fromKey, boolean fromInclusive,
+ K toKey, boolean toInclusive) {
+ return new AscendingSubMap(fromKey, excluded(fromInclusive),
+ toKey, excluded(toInclusive));
}
/**
@@ -960,9 +910,10 @@ public class TreeMap
* and this map uses natural ordering, or its comparator
* does not permit null keys
* @throws IllegalArgumentException {@inheritDoc}
+ * @since 1.6
*/
- public NavigableMap navigableHeadMap(K toKey) {
- return new SubMap(toKey, true);
+ public NavigableMap navigableHeadMap(K toKey, boolean inclusive) {
+ return new AscendingSubMap((K)UNBOUNDED, 0, toKey, excluded(inclusive));
}
/**
@@ -971,17 +922,21 @@ public class TreeMap
* and this map uses natural ordering, or its comparator
* does not permit null keys
* @throws IllegalArgumentException {@inheritDoc}
+ * @since 1.6
*/
- public NavigableMap navigableTailMap(K fromKey) {
- return new SubMap(fromKey, false);
+ public NavigableMap navigableTailMap(K fromKey, boolean inclusive) {
+ return new AscendingSubMap(fromKey, excluded(inclusive), (K)UNBOUNDED, 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;
}
/**
- * Equivalent to {@link #navigableSubMap} but with a return type
- * conforming to the SortedMap interface.
- *
- * {@inheritDoc}
- *
* @throws ClassCastException {@inheritDoc}
* @throws NullPointerException if fromKey or toKey is
* null and this map uses natural ordering, or its comparator
@@ -989,15 +944,10 @@ public class TreeMap
* @throws IllegalArgumentException {@inheritDoc}
*/
public SortedMap subMap(K fromKey, K toKey) {
- return new SubMap(fromKey, toKey);
+ return navigableSubMap(fromKey, true, toKey, false);
}
/**
- * Equivalent to {@link #navigableHeadMap} but with a return type
- * conforming to the SortedMap interface.
- *
- * {@inheritDoc}
- *
* @throws ClassCastException {@inheritDoc}
* @throws NullPointerException if toKey is null
* and this map uses natural ordering, or its comparator
@@ -1005,15 +955,10 @@ public class TreeMap
* @throws IllegalArgumentException {@inheritDoc}
*/
public SortedMap headMap(K toKey) {
- return new SubMap(toKey, true);
+ return navigableHeadMap(toKey, false);
}
/**
- * Equivalent to {@link #navigableTailMap} but with a return type
- * conforming to the SortedMap interface.
- *
- * {@inheritDoc}
- *
* @throws ClassCastException {@inheritDoc}
* @throws NullPointerException if fromKey is null
* and this map uses natural ordering, or its comparator
@@ -1021,210 +966,283 @@ public class TreeMap
* @throws IllegalArgumentException {@inheritDoc}
*/
public SortedMap tailMap(K fromKey) {
- return new SubMap(fromKey, false);
+ return navigableTailMap(fromKey, true);
}
- private class SubMap
- extends AbstractMap
- implements NavigableMap, java.io.Serializable {
- private static final long serialVersionUID = -6520786458950516097L;
+ // View class support
- /**
- * fromKey is significant only if fromStart is false. Similarly,
- * toKey is significant only if toStart is false.
- */
- private boolean fromStart = false, toEnd = false;
- private K fromKey, toKey;
+ class Values extends AbstractCollection {
+ public Iterator iterator() {
+ return new ValueIterator(getFirstEntry());
+ }
- SubMap(K fromKey, K toKey) {
- if (compare(fromKey, toKey) > 0)
- throw new IllegalArgumentException("fromKey > toKey");
- this.fromKey = fromKey;
- this.toKey = toKey;
+ public int size() {
+ return TreeMap.this.size();
}
- SubMap(K key, boolean headMap) {
- compare(key, key); // Type-check key
+ public boolean contains(Object o) {
+ for (Entry e = getFirstEntry(); e != null; e = successor(e))
+ if (valEquals(e.getValue(), o))
+ return true;
+ return false;
+ }
- if (headMap) {
- fromStart = true;
- toKey = key;
- } else {
- toEnd = true;
- fromKey = key;
+ public boolean remove(Object o) {
+ for (Entry e = getFirstEntry(); e != null; e = successor(e)) {
+ if (valEquals(e.getValue(), o)) {
+ deleteEntry(e);
+ return true;
+ }
}
+ return false;
}
- SubMap(boolean fromStart, K fromKey, boolean toEnd, K toKey) {
- this.fromStart = fromStart;
- this.fromKey= fromKey;
- this.toEnd = toEnd;
- this.toKey = toKey;
+ public void clear() {
+ TreeMap.this.clear();
}
+ }
- public boolean isEmpty() {
- return entrySet().isEmpty();
+ class EntrySet extends AbstractSet> {
+ public Iterator> iterator() {
+ return new EntryIterator(getFirstEntry());
}
- public boolean containsKey(Object key) {
- return inRange(key) && TreeMap.this.containsKey(key);
+ public boolean contains(Object o) {
+ if (!(o instanceof Map.Entry))
+ return false;
+ Map.Entry entry = (Map.Entry) o;
+ V value = entry.getValue();
+ Entry p = getEntry(entry.getKey());
+ return p != null && valEquals(p.getValue(), value);
}
- public V get(Object key) {
- if (!inRange(key))
- return null;
- return TreeMap.this.get(key);
+ public boolean remove(Object o) {
+ if (!(o instanceof Map.Entry))
+ return false;
+ Map.Entry entry = (Map.Entry) o;
+ V value = entry.getValue();
+ Entry p = getEntry(entry.getKey());
+ if (p != null && valEquals(p.getValue(), value)) {
+ deleteEntry(p);
+ return true;
+ }
+ return false;
}
- public V put(K key, V value) {
- if (!inRange(key))
- throw new IllegalArgumentException("key out of range");
- return TreeMap.this.put(key, value);
+ public int size() {
+ return TreeMap.this.size();
}
- public V remove(Object key) {
- if (!inRange(key))
- return null;
- return TreeMap.this.remove(key);
+ public void clear() {
+ TreeMap.this.clear();
}
+ }
- public Comparator comparator() {
- return comparator;
+ /*
+ * Unlike Values and EntrySet, the KeySet class is static,
+ * delegating to a NavigableMap to allow use by SubMaps, which
+ * outweighs the ugliness of needing type-tests for the following
+ * Iterator methods that are defined appropriately in main versus
+ * submap classes.
+ */
+
+ Iterator keyIterator() {
+ return new KeyIterator(getFirstEntry());
+ }
+
+ Iterator descendingKeyIterator() {
+ return new DescendingKeyIterator(getFirstEntry());
+ }
+
+ static final class KeySet extends AbstractSet implements NavigableSet {
+ private final NavigableMap m;
+ KeySet(NavigableMap map) { m = map; }
+
+ public Iterator iterator() {
+ if (m instanceof TreeMap)
+ return ((TreeMap)m).keyIterator();
+ else
+ return (Iterator)(((TreeMap.NavigableSubMap)m).keyIterator());
}
- public K firstKey() {
- TreeMap.Entry e = fromStart ? getFirstEntry() : getCeilingEntry(fromKey);
- K first = key(e);
- if (!toEnd && compare(first, toKey) >= 0)
- throw new NoSuchElementException();
- return first;
+ public Iterator descendingIterator() {
+ if (m instanceof TreeMap)
+ return ((TreeMap)m).descendingKeyIterator();
+ else
+ return (Iterator)(((TreeMap.NavigableSubMap)m).descendingKeyIterator());
}
- public K lastKey() {
- TreeMap.Entry e = toEnd ? getLastEntry() : getLowerEntry(toKey);
- K last = key(e);
- if (!fromStart && compare(last, fromKey) < 0)
- throw new NoSuchElementException();
- return last;
+ public int size() { return m.size(); }
+ public boolean isEmpty() { return m.isEmpty(); }
+ public boolean contains(Object o) { return m.containsKey(o); }
+ public void clear() { m.clear(); }
+ public E lower(E e) { return m.lowerKey(e); }
+ public E floor(E e) { return m.floorKey(e); }
+ public E ceiling(E e) { return m.ceilingKey(e); }
+ public E higher(E e) { return m.higherKey(e); }
+ public E first() { return m.firstKey(); }
+ public E last() { return m.lastKey(); }
+ public Comparator comparator() { return m.comparator(); }
+ public E pollFirst() {
+ Map.Entry e = m.pollFirstEntry();
+ return e == null? null : e.getKey();
+ }
+ public E pollLast() {
+ Map.Entry e = m.pollLastEntry();
+ return e == null? null : e.getKey();
+ }
+ public boolean remove(Object o) {
+ int oldSize = size();
+ m.remove(o);
+ return size() != oldSize;
}
+ public NavigableSet navigableSubSet(E fromElement,
+ boolean fromInclusive,
+ E toElement,
+ boolean toInclusive) {
+ return new TreeSet
+ (m.navigableSubMap(fromElement, fromInclusive,
+ toElement, toInclusive));
+ }
+ public NavigableSet navigableHeadSet(E toElement, boolean inclusive) {
+ return new TreeSet(m.navigableHeadMap(toElement, inclusive));
+ }
+ public NavigableSet navigableTailSet(E fromElement, boolean inclusive) {
+ return new TreeSet(m.navigableTailMap(fromElement, inclusive));
+ }
+ public SortedSet subSet(E fromElement, E toElement) {
+ return navigableSubSet(fromElement, true, toElement, false);
+ }
+ public SortedSet headSet(E toElement) {
+ return navigableHeadSet(toElement, false);
+ }
+ public SortedSet tailSet(E fromElement) {
+ return navigableTailSet(fromElement, true);
+ }
+ public NavigableSet descendingSet() {
+ return new TreeSet(m.descendingMap());
+ }
+ }
- public Map.Entry firstEntry() {
- TreeMap.Entry e = fromStart ?
- getFirstEntry() : getCeilingEntry(fromKey);
- if (e == null || (!toEnd && compare(e.key, toKey) >= 0))
- return null;
- return e;
+ // SubMaps
+
+ abstract class NavigableSubMap extends AbstractMap
+ implements NavigableMap, java.io.Serializable {
+
+ /**
+ * The low endpoint of this submap in absolute terms. For ascending
+ * submaps this will be the "first" endpoint; for descending submaps,
+ * the last. If there is no bound, this field is set to UNBOUNDED.
+ */
+ K lo;
+
+ /**
+ * Zero if the low endpoint is excluded from this submap, one if
+ * it's included. This field is unused if lo is UNBOUNDED.
+ */
+ int loExcluded;
+
+ /**
+ * The high endpoint of this submap in absolute terms. For ascending
+ * submaps this will be the "last" endpoint; for descending submaps,
+ * the first. If there is no bound, this field is set to UNBOUNDED.
+ */
+ K hi;
+
+ /**
+ * Zero if the high endpoint is excluded from this submap, one if
+ * it's included. This field is unused if hi is UNBOUNDED.
+ */
+ int hiExcluded;
+
+ NavigableSubMap(K lo, int loExcluded, K hi, int hiExcluded) {
+ if (lo != UNBOUNDED && hi != UNBOUNDED && compare(lo, hi) > 0)
+ throw new IllegalArgumentException("fromKey > toKey");
+ this.lo = lo;
+ this.loExcluded = loExcluded;
+ this.hi = hi;
+ this.hiExcluded = hiExcluded;
}
- public Map.Entry lastEntry() {
- TreeMap.Entry e = toEnd ?
- getLastEntry() : getLowerEntry(toKey);
- if (e == null || (!fromStart && compare(e.key, fromKey) < 0))
- return null;
- return e;
+ public boolean isEmpty() {
+ return entrySet().isEmpty();
}
- public Map.Entry pollFirstEntry() {
- TreeMap.Entry e = fromStart ?
- getFirstEntry() : getCeilingEntry(fromKey);
- if (e == null || (!toEnd && compare(e.key, toKey) >= 0))
- return null;
- Map.Entry result = new AbstractMap.SimpleImmutableEntry(e);
- deleteEntry(e);
- return result;
+ public boolean containsKey(Object key) {
+ return inRange(key) && TreeMap.this.containsKey(key);
}
- public Map.Entry pollLastEntry() {
- TreeMap.Entry e = toEnd ?
- getLastEntry() : getLowerEntry(toKey);
- if (e == null || (!fromStart && compare(e.key, fromKey) < 0))
+ public V get(Object key) {
+ if (!inRange(key))
return null;
- Map.Entry result = new AbstractMap.SimpleImmutableEntry(e);
- deleteEntry(e);
- return result;
+ return TreeMap.this.get(key);
+ }
+
+ public V put(K key, V value) {
+ if (!inRange(key))
+ throw new IllegalArgumentException("key out of range");
+ return TreeMap.this.put(key, value);
}
- private TreeMap.Entry subceiling(K key) {
- TreeMap.Entry e = (!fromStart && compare(key, fromKey) < 0)?
- getCeilingEntry(fromKey) : getCeilingEntry(key);
- if (e == null || (!toEnd && compare(e.key, toKey) >= 0))
+ public V remove(Object key) {
+ if (!inRange(key))
return null;
- return e;
+ return TreeMap.this.remove(key);
}
public Map.Entry ceilingEntry(K key) {
- TreeMap.Entry e = subceiling(key);
+ TreeMap.Entry e = subCeiling(key);
return e == null? null : new AbstractMap.SimpleImmutableEntry(e);
}
public K ceilingKey(K key) {
- TreeMap.Entry e = subceiling(key);
+ TreeMap.Entry e = subCeiling(key);
return e == null? null : e.key;
}
-
- private TreeMap.Entry subhigher(K key) {
- TreeMap.Entry e = (!fromStart && compare(key, fromKey) < 0)?
- getCeilingEntry(fromKey) : getHigherEntry(key);
- if (e == null || (!toEnd && compare(e.key, toKey) >= 0))
- return null;
- return e;
- }
-
public Map.Entry higherEntry(K key) {
- TreeMap.Entry e = subhigher(key);
+ TreeMap.Entry e = subHigher(key);
return e == null? null : new AbstractMap.SimpleImmutableEntry(e);
}
public K higherKey(K key) {
- TreeMap.Entry e = subhigher(key);
+ TreeMap.Entry e = subHigher(key);
return e == null? null : e.key;
}
- private TreeMap.Entry subfloor(K key) {
- TreeMap.Entry e = (!toEnd && compare(key, toKey) >= 0)?
- getLowerEntry(toKey) : getFloorEntry(key);
- if (e == null || (!fromStart && compare(e.key, fromKey) < 0))
- return null;
- return e;
- }
-
public Map.Entry floorEntry(K key) {
- TreeMap.Entry e = subfloor(key);
+ TreeMap.Entry e = subFloor(key);
return e == null? null : new AbstractMap.SimpleImmutableEntry(e);
}
public K floorKey(K key) {
- TreeMap.Entry e = subfloor(key);
+ TreeMap.Entry e = subFloor(key);
return e == null? null : e.key;
}
- private TreeMap.Entry sublower(K key) {
- TreeMap.Entry e = (!toEnd && compare(key, toKey) >= 0)?
- getLowerEntry(toKey) : getLowerEntry(key);
- if (e == null || (!fromStart && compare(e.key, fromKey) < 0))
- return null;
- return e;
- }
-
public Map.Entry lowerEntry(K key) {
- TreeMap.Entry e = sublower(key);
+ TreeMap.Entry e = subLower(key);
return e == null? null : new AbstractMap.SimpleImmutableEntry(e);
}
public K lowerKey(K key) {
- TreeMap.Entry e = sublower(key);
+ TreeMap.Entry e = subLower(key);
return e == null? null : e.key;
}
- private transient Set> entrySet = null;
+ abstract Iterator keyIterator();
+ abstract Iterator descendingKeyIterator();
- public Set> entrySet() {
- Set> es = entrySet;
- return (es != null)? es : (entrySet = new EntrySetView());
+ public NavigableSet descendingKeySet() {
+ return descendingMap().navigableKeySet();
}
- private class EntrySetView extends AbstractSet> {
+ // Views
+ transient NavigableMap descendingMapView = null;
+ transient Set> entrySetView = null;
+ private transient NavigableSet navigableKeySetView = null;
+
+ abstract class EntrySetView extends AbstractSet> {
private transient int size = -1, sizeModCount;
public int size() {
@@ -1269,99 +1287,381 @@ public class TreeMap
}
return false;
}
+ }
- public Iterator> iterator() {
- return new SubMapEntryIterator(
- (fromStart ? getFirstEntry() : getCeilingEntry(fromKey)),
- (toEnd ? null : getCeilingEntry(toKey)));
- }
+ public NavigableSet navigableKeySet() {
+ NavigableSet nksv = navigableKeySetView;
+ return (nksv != null) ? nksv :
+ (navigableKeySetView = new TreeMap.KeySet(this));
}
- private transient Set> descendingEntrySetView = null;
- private transient Set descendingKeySetView = null;
+ public Set keySet() {
+ return navigableKeySet();
+ }
- public Set> descendingEntrySet() {
- Set> es = descendingEntrySetView;
- return (es != null) ? es :
- (descendingEntrySetView = new DescendingEntrySetView());
- }
-
- public Set descendingKeySet() {
- Set ks = descendingKeySetView;
- return (ks != null) ? ks :
- (descendingKeySetView = new DescendingKeySetView());
- }
-
- private class DescendingEntrySetView extends EntrySetView {
- public Iterator> iterator() {
- return new DescendingSubMapEntryIterator
- ((toEnd ? getLastEntry() : getLowerEntry(toKey)),
- (fromStart ? null : getLowerEntry(fromKey)));
- }
+ public SortedMap subMap(K fromKey, K toKey) {
+ return navigableSubMap(fromKey, true, toKey, false);
}
- private class DescendingKeySetView extends AbstractSet {
- public Iterator iterator() {
- return new Iterator() {
- private Iterator> i = descendingEntrySet().iterator();
-
- public boolean hasNext() { return i.hasNext(); }
- public K next() { return i.next().getKey(); }
- public void remove() { i.remove(); }
- };
- }
+ public SortedMap headMap(K toKey) {
+ return navigableHeadMap(toKey, false);
+ }
- public int size() {
- return SubMap.this.size();
- }
+ public SortedMap tailMap(K fromKey) {
+ return navigableTailMap(fromKey, true);
+ }
- public boolean contains(Object k) {
- return SubMap.this.containsKey(k);
- }
+ /** Returns the lowest entry in this submap (absolute ordering) */
+ TreeMap.Entry loEntry() {
+ TreeMap.Entry result =
+ ((lo == UNBOUNDED) ? getFirstEntry() :
+ (loExcluded == 0) ? getCeilingEntry(lo) : getHigherEntry(lo));
+ return (result == null || tooHigh(result.key)) ? null : result;
+ }
+
+ /** Returns the highest key in this submap (absolute ordering) */
+ TreeMap.Entry hiEntry() {
+ TreeMap.Entry result =
+ ((hi == UNBOUNDED) ? getLastEntry() :
+ (hiExcluded == 0) ? getFloorEntry(hi) : getLowerEntry(hi));
+ return (result == null || tooLow(result.key)) ? null : result;
+ }
+
+ /** Polls the lowest entry in this submap (absolute ordering) */
+ Map.Entry pollLoEntry() {
+ TreeMap.Entry e =
+ ((lo == UNBOUNDED) ? getFirstEntry() :
+ (loExcluded == 0) ? getCeilingEntry(lo) : getHigherEntry(lo));
+ if (e == null || tooHigh(e.key))
+ return null;
+ Map.Entry result = new AbstractMap.SimpleImmutableEntry(e);
+ deleteEntry(e);
+ return result;
}
- public NavigableMap navigableSubMap(K fromKey, K toKey) {
- if (!inRange2(fromKey))
+ /** Polls the highest key in this submap (absolute ordering) */
+ Map.Entry pollHiEntry() {
+ TreeMap.Entry e =
+ ((hi == UNBOUNDED) ? getLastEntry() :
+ (hiExcluded == 0) ? getFloorEntry(hi) : getLowerEntry(hi));
+ if (e == null || tooLow(e.key))
+ return null;
+ Map.Entry result = new AbstractMap.SimpleImmutableEntry(e);
+ deleteEntry(e);
+ return result;
+ }
+
+ // 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 = 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 = 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 = 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 = getLowerEntry(key);
+ return (e == null || tooLow(e.key)) ? null : e;
+ }
+
+ boolean inRange(Object key) {
+ return (lo == UNBOUNDED || compare(key, lo) >= loExcluded)
+ && (hi == UNBOUNDED || compare(hi, key) >= hiExcluded);
+ }
+
+ boolean inClosedRange(Object key) {
+ return (lo == UNBOUNDED || compare(key, lo) >= 0)
+ && (hi == UNBOUNDED || compare(hi, key) >= 0);
+ }
+
+ boolean inRange(Object key, boolean inclusive) {
+ return inclusive ? inRange(key) : inClosedRange(key);
+ }
+
+ boolean tooLow(K key) {
+ return lo != UNBOUNDED && compare(key, lo) < loExcluded;
+ }
+
+ boolean tooHigh(K key) {
+ return hi != UNBOUNDED && compare(hi, key) < hiExcluded;
+ }
+ }
+
+ class AscendingSubMap extends NavigableSubMap {
+ private static final long serialVersionUID = 912986545866124060L;
+
+ AscendingSubMap(K lo, int loExcluded, K hi, int hiExcluded) {
+ super(lo, loExcluded, hi, hiExcluded);
+ }
+
+ public Comparator comparator() {
+ return comparator;
+ }
+
+ public NavigableMap navigableSubMap(
+ K fromKey, boolean fromInclusive, K toKey, boolean toInclusive) {
+ if (!inRange(fromKey, fromInclusive))
throw new IllegalArgumentException("fromKey out of range");
- if (!inRange2(toKey))
+ if (!inRange(toKey, toInclusive))
throw new IllegalArgumentException("toKey out of range");
- return new SubMap(fromKey, toKey);
+ return new AscendingSubMap(fromKey, excluded(fromInclusive),
+ toKey, excluded(toInclusive));
}
- public NavigableMap navigableHeadMap(K toKey) {
- if (!inRange2(toKey))
+ public NavigableMap navigableHeadMap(K toKey, boolean inclusive) {
+ if (!inClosedRange(toKey))
throw new IllegalArgumentException("toKey out of range");
- return new SubMap(fromStart, fromKey, false, toKey);
+ return new AscendingSubMap(lo, loExcluded,
+ toKey, excluded(inclusive));
}
- public NavigableMap navigableTailMap(K fromKey) {
- if (!inRange2(fromKey))
+ public NavigableMap navigableTailMap(K fromKey, boolean inclusive){
+ if (!inRange(fromKey, inclusive))
throw new IllegalArgumentException("fromKey out of range");
- return new SubMap(false, fromKey, toEnd, toKey);
+ return new AscendingSubMap(fromKey, excluded(inclusive),
+ hi, hiExcluded);
}
- public SortedMap subMap(K fromKey, K toKey) {
- return navigableSubMap(fromKey, toKey);
+ Iterator keyIterator() {
+ return new SubMapKeyIterator
+ (loEntry(),
+ hi == UNBOUNDED ? null :
+ hiExcluded == 1 ? getCeilingEntry(hi) :
+ getHigherEntry(hi));
+ }
+
+ Iterator descendingKeyIterator() {
+ return new DescendingSubMapKeyIterator
+ (hiEntry(),
+ lo == UNBOUNDED ? null :
+ loExcluded == 1 ? getFloorEntry(lo) :
+ getLowerEntry(lo));
}
- public SortedMap headMap(K toKey) {
- return navigableHeadMap(toKey);
+ public Set> entrySet() {
+ Set> es = entrySetView;
+ if (es != null)
+ return es;
+ return entrySetView = new NavigableSubMap.EntrySetView() {
+ public Iterator> iterator() {
+ return new SubMapEntryIterator(loEntry(),
+ hi == UNBOUNDED ? null :
+ hiExcluded == 1 ? getCeilingEntry(hi) :
+ getHigherEntry(hi));
+ }
+ };
}
- public SortedMap tailMap(K fromKey) {
- return navigableTailMap(fromKey);
+ 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