--- jsr166/src/main/java/util/TreeMap.java 2006/03/19 18:03:54 1.27
+++ jsr166/src/main/java/util/TreeMap.java 2006/05/09 16:35:40 1.36
@@ -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
@@ -95,7 +95,7 @@ public class TreeMap
*
* @serial
*/
- private Comparator super K> comparator = null;
+ private final Comparator super K> comparator;
private transient Entry root = null;
@@ -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
@@ -125,6 +122,7 @@ public class TreeMap
* ClassCastException.
*/
public TreeMap() {
+ comparator = null;
}
/**
@@ -160,6 +158,7 @@ public class TreeMap
* @throws NullPointerException if the specified map is null
*/
public TreeMap(Map extends K, ? extends V> m) {
+ comparator = null;
putAll(m);
}
@@ -224,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;
}
/**
@@ -335,10 +316,12 @@ public class TreeMap
* and this map uses natural ordering, or its comparator
* does not permit null keys
*/
- private Entry getEntry(Object key) {
+ final Entry getEntry(Object key) {
// Offload comparator-based version for sake of performance
if (comparator != null)
return getEntryUsingComparator(key);
+ if (key == null)
+ throw new NullPointerException();
Comparable super K> k = (Comparable super K>) key;
Entry p = root;
while (p != null) {
@@ -359,18 +342,20 @@ public class TreeMap
* that are less dependent on comparator performance, but is
* worthwhile here.)
*/
- private Entry getEntryUsingComparator(Object key) {
+ 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;
}
@@ -381,12 +366,9 @@ public class TreeMap
* key; if no such entry exists (i.e., the greatest key in the Tree is less
* than the specified key), returns null.
*/
- private Entry getCeilingEntry(K key) {
+ final Entry getCeilingEntry(K key) {
Entry p = root;
- if (p==null)
- return null;
-
- while (true) {
+ while (p != null) {
int cmp = compare(key, p.key);
if (cmp < 0) {
if (p.left != null)
@@ -408,6 +390,7 @@ public class TreeMap
} else
return p;
}
+ return null;
}
/**
@@ -415,12 +398,9 @@ public class TreeMap
* exists, returns the entry for the greatest key less than the specified
* key; if no such entry exists, returns null.
*/
- private Entry getFloorEntry(K key) {
+ final Entry getFloorEntry(K key) {
Entry p = root;
- if (p==null)
- return null;
-
- while (true) {
+ while (p != null) {
int cmp = compare(key, p.key);
if (cmp > 0) {
if (p.right != null)
@@ -443,6 +423,7 @@ public class TreeMap
return p;
}
+ return null;
}
/**
@@ -451,12 +432,9 @@ public class TreeMap
* key greater than the specified key; if no such entry exists
* returns null.
*/
- private Entry getHigherEntry(K key) {
+ final Entry getHigherEntry(K key) {
Entry p = root;
- if (p==null)
- return null;
-
- while (true) {
+ while (p != null) {
int cmp = compare(key, p.key);
if (cmp < 0) {
if (p.left != null)
@@ -477,6 +455,7 @@ public class TreeMap
}
}
}
+ return null;
}
/**
@@ -484,12 +463,9 @@ public class TreeMap
* no such entry exists (i.e., the least key in the Tree is greater than
* the specified key), returns null.
*/
- private Entry getLowerEntry(K key) {
+ final Entry getLowerEntry(K key) {
Entry p = root;
- if (p==null)
- return null;
-
- while (true) {
+ while (p != null) {
int cmp = compare(key, p.key);
if (cmp > 0) {
if (p.right != null)
@@ -510,16 +486,7 @@ public class TreeMap
}
}
}
- }
-
- /**
- * Returns the key corresponding to the specified Entry.
- * @throws NoSuchElementException if the Entry is null
- */
- private static K key(Entry e) {
- if (e==null)
- throw new NoSuchElementException();
- return e.key;
+ return null;
}
/**
@@ -542,43 +509,57 @@ public class TreeMap
*/
public V put(K key, V value) {
Entry t = root;
-
if (t == null) {
- // TBD
-// if (key == null) {
-// if (comparator == null)
-// throw new NullPointerException();
-// comparator.compare(key, key);
-// }
- incrementSize();
+ // 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;
}
-
- while (true) {
- int cmp = compare(key, t.key);
- if (cmp == 0) {
- return t.setValue(value);
- } else if (cmp < 0) {
- if (t.left != 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();
- t.left = new Entry(key, value, t);
- fixAfterInsertion(t.left);
- return null;
- }
- } else { // cmp > 0
- if (t.right != null) {
+ else if (cmp > 0)
t = t.right;
- } else {
- incrementSize();
- t.right = new Entry(key, value, t);
- fixAfterInsertion(t.right);
- return null;
- }
- }
+ else
+ return t.setValue(value);
+ } while (t != 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 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++;
+ return null;
}
/**
@@ -634,8 +615,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 {
@@ -653,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());
}
/**
@@ -670,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;
}
@@ -682,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;
}
@@ -697,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));
}
/**
@@ -709,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));
}
/**
@@ -721,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));
}
/**
@@ -733,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));
}
/**
@@ -745,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));
}
/**
@@ -757,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));
}
/**
@@ -769,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));
}
/**
@@ -781,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
@@ -792,9 +761,9 @@ public class TreeMap
* the first time this view is requested. Views are stateless, so
* 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 EntrySet entrySet = null;
+ private transient KeySet navigableKeySet = null;
+ private transient NavigableMap descendingMap = null;
/**
* Returns a {@link Set} view of the keys contained in this map.
@@ -811,32 +780,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() {
+ KeySet 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();
}
/**
@@ -859,6 +818,115 @@ public class TreeMap
return (vs != null) ? vs : (values = new Values());
}
+ /**
+ * Returns a {@link Set} view of the mappings contained in this map.
+ * The set's iterator returns the entries in ascending key order.
+ * The set is backed by the map, so changes to the map are
+ * reflected in the set, and vice-versa. If the map is modified
+ * while an iteration over the set is in progress (except through
+ * the iterator's own remove operation, or through the
+ * setValue operation on a map entry returned by the
+ * iterator) the results of the iteration are undefined. The set
+ * supports element removal, which removes the corresponding
+ * mapping from the map, via the Iterator.remove,
+ * Set.remove, removeAll, retainAll and
+ * clear operations. It does not support the
+ * add or addAll operations.
+ */
+ public Set> entrySet() {
+ EntrySet es = entrySet;
+ return (es != null) ? es : (entrySet = new EntrySet());
+ }
+
+ /**
+ * @since 1.6
+ */
+ public NavigableMap descendingMap() {
+ NavigableMap km = descendingMap;
+ return (km != null) ? km :
+ (descendingMap = new DescendingSubMap(this,
+ true, null, true,
+ true, null, true));
+ }
+
+ /**
+ * @throws ClassCastException {@inheritDoc}
+ * @throws NullPointerException if fromKey or toKey is
+ * null and this map uses natural ordering, or its comparator
+ * does not permit null keys
+ * @throws IllegalArgumentException {@inheritDoc}
+ * @since 1.6
+ */
+ public NavigableMap subMap(K fromKey, boolean fromInclusive,
+ K toKey, boolean toInclusive) {
+ return new AscendingSubMap(this,
+ false, fromKey, fromInclusive,
+ false, toKey, toInclusive);
+ }
+
+ /**
+ * @throws ClassCastException {@inheritDoc}
+ * @throws NullPointerException if toKey is null
+ * and this map uses natural ordering, or its comparator
+ * does not permit null keys
+ * @throws IllegalArgumentException {@inheritDoc}
+ * @since 1.6
+ */
+ public NavigableMap headMap(K toKey, boolean inclusive) {
+ return new AscendingSubMap(this,
+ true, null, true,
+ false, toKey, inclusive);
+ }
+
+ /**
+ * @throws ClassCastException {@inheritDoc}
+ * @throws NullPointerException if fromKey is null
+ * and this map uses natural ordering, or its comparator
+ * does not permit null keys
+ * @throws IllegalArgumentException {@inheritDoc}
+ * @since 1.6
+ */
+ public NavigableMap tailMap(K fromKey, boolean inclusive) {
+ return new AscendingSubMap(this,
+ false, fromKey, inclusive,
+ true, null, true);
+ }
+
+ /**
+ * @throws ClassCastException {@inheritDoc}
+ * @throws NullPointerException if fromKey or toKey is
+ * null and this map uses natural ordering, or its comparator
+ * does not permit null keys
+ * @throws IllegalArgumentException {@inheritDoc}
+ */
+ public SortedMap subMap(K fromKey, K toKey) {
+ return subMap(fromKey, true, toKey, false);
+ }
+
+ /**
+ * @throws ClassCastException {@inheritDoc}
+ * @throws NullPointerException if toKey is null
+ * and this map uses natural ordering, or its comparator
+ * does not permit null keys
+ * @throws IllegalArgumentException {@inheritDoc}
+ */
+ public SortedMap headMap(K toKey) {
+ return headMap(toKey, false);
+ }
+
+ /**
+ * @throws ClassCastException {@inheritDoc}
+ * @throws NullPointerException if fromKey is null
+ * and this map uses natural ordering, or its comparator
+ * does not permit null keys
+ * @throws IllegalArgumentException {@inheritDoc}
+ */
+ public SortedMap tailMap(K fromKey) {
+ return tailMap(fromKey, true);
+ }
+
+ // View class support
+
class Values extends AbstractCollection {
public Iterator iterator() {
return new ValueIterator(getFirstEntry());
@@ -869,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) {
@@ -890,26 +955,6 @@ public class TreeMap
}
}
- /**
- * Returns a {@link Set} view of the mappings contained in this map.
- * The set's iterator returns the entries in ascending key order.
- * The set is backed by the map, so changes to the map are
- * reflected in the set, and vice-versa. If the map is modified
- * while an iteration over the set is in progress (except through
- * the iterator's own remove operation, or through the
- * setValue operation on a map entry returned by the
- * iterator) the results of the iteration are undefined. The set
- * supports element removal, which removes the corresponding
- * mapping from the map, via the Iterator.remove,
- * Set.remove, removeAll, retainAll and
- * clear operations. It does not support the
- * add or addAll operations.
- */
- public Set> entrySet() {
- Set> es = entrySet;
- return (es != null) ? es : (entrySet = new EntrySet());
- }
-
class EntrySet extends AbstractSet> {
public Iterator> iterator() {
return new EntryIterator(getFirstEntry());
@@ -946,324 +991,513 @@ public class TreeMap
}
}
- /**
- * @since 1.6
+ /*
+ * 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.
*/
- public Set> descendingEntrySet() {
- Set> es = descendingEntrySet;
- return (es != null) ? es : (descendingEntrySet = new DescendingEntrySet());
+
+ Iterator keyIterator() {
+ return new KeyIterator(getFirstEntry());
}
- class DescendingEntrySet extends EntrySet {
- public Iterator> iterator() {
- return new DescendingEntryIterator(getLastEntry());
+ 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 Iterator descendingIterator() {
+ if (m instanceof TreeMap)
+ return ((TreeMap)m).descendingKeyIterator();
+ else
+ return (Iterator)(((TreeMap.NavigableSubMap)m).descendingKeyIterator());
+ }
+
+ 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 super E> 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 subSet(E fromElement, boolean fromInclusive,
+ E toElement, boolean toInclusive) {
+ return new TreeSet(m.subMap(fromElement, fromInclusive,
+ toElement, toInclusive));
+ }
+ public NavigableSet headSet(E toElement, boolean inclusive) {
+ return new TreeSet(m.headMap(toElement, inclusive));
+ }
+ public NavigableSet tailSet(E fromElement, boolean inclusive) {
+ return new TreeSet(m.tailMap(fromElement, inclusive));
+ }
+ public SortedSet subSet(E fromElement, E toElement) {
+ return subSet(fromElement, true, toElement, false);
+ }
+ public SortedSet headSet(E toElement) {
+ return headSet(toElement, false);
+ }
+ public SortedSet tailSet(E fromElement) {
+ return tailSet(fromElement, true);
+ }
+ public NavigableSet descendingSet() {
+ return new TreeSet(m.descendingMap());
}
}
/**
- * @since 1.6
+ * Base class for TreeMap Iterators
*/
- public Set descendingKeySet() {
- Set ks = descendingKeySet;
- return (ks != null) ? ks : (descendingKeySet = new DescendingKeySet());
+ abstract class PrivateEntryIterator implements Iterator {
+ Entry next;
+ Entry lastReturned;
+ int expectedModCount;
+
+ PrivateEntryIterator(Entry first) {
+ expectedModCount = modCount;
+ lastReturned = null;
+ next = first;
+ }
+
+ public final boolean hasNext() {
+ return next != null;
+ }
+
+ final Entry nextEntry() {
+ Entry e = lastReturned = next;
+ if (e == null)
+ throw new NoSuchElementException();
+ if (modCount != expectedModCount)
+ throw new ConcurrentModificationException();
+ next = successor(e);
+ return e;
+ }
+
+ final Entry prevEntry() {
+ Entry e = lastReturned= next;
+ if (e == null)
+ throw new NoSuchElementException();
+ if (modCount != expectedModCount)
+ throw new ConcurrentModificationException();
+ next = predecessor(e);
+ return e;
+ }
+
+ public void remove() {
+ if (lastReturned == null)
+ throw new IllegalStateException();
+ if (modCount != expectedModCount)
+ throw new ConcurrentModificationException();
+ if (lastReturned.left != null && lastReturned.right != null)
+ next = lastReturned;
+ deleteEntry(lastReturned);
+ expectedModCount++;
+ lastReturned = null;
+ }
}
- class DescendingKeySet extends KeySet {
- public Iterator iterator() {
- return new DescendingKeyIterator(getLastEntry());
+ final class EntryIterator extends PrivateEntryIterator> {
+ EntryIterator(Entry first) {
+ super(first);
+ }
+ public Map.Entry next() {
+ return nextEntry();
}
}
- /**
- * @throws ClassCastException {@inheritDoc}
- * @throws NullPointerException if fromKey or toKey is
- * 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);
+ final class ValueIterator extends PrivateEntryIterator {
+ ValueIterator(Entry first) {
+ super(first);
+ }
+ public V next() {
+ return nextEntry().value;
+ }
+ }
+
+ final class KeyIterator extends PrivateEntryIterator {
+ KeyIterator(Entry first) {
+ super(first);
+ }
+ public K next() {
+ return nextEntry().key;
+ }
}
+ final class DescendingKeyIterator extends PrivateEntryIterator {
+ DescendingKeyIterator(Entry first) {
+ super(first);
+ }
+ public K next() {
+ return prevEntry().key;
+ }
+ }
+
+ // Little utilities
+
/**
- * @throws ClassCastException {@inheritDoc}
- * @throws NullPointerException if toKey is null
- * and this map uses natural ordering, or its comparator
- * does not permit null keys
- * @throws IllegalArgumentException {@inheritDoc}
- * @since 1.6
+ * Compares two keys using the correct comparison method for this TreeMap.
*/
- public NavigableMap navigableHeadMap(K toKey) {
- return new SubMap(toKey, true);
+ final int compare(Object k1, Object k2) {
+ return comparator==null ? ((Comparable super K>)k1).compareTo((K)k2)
+ : comparator.compare((K)k1, (K)k2);
}
/**
- * @throws ClassCastException {@inheritDoc}
- * @throws NullPointerException if fromKey is null
- * and this map uses natural ordering, or its comparator
- * does not permit null keys
- * @throws IllegalArgumentException {@inheritDoc}
- * @since 1.6
+ * Test two values for equality. Differs from o1.equals(o2) only in
+ * that it copes with null o1 properly.
*/
- public NavigableMap navigableTailMap(K fromKey) {
- return new SubMap(fromKey, false);
+ final static boolean valEquals(Object o1, Object o2) {
+ return (o1==null ? o2==null : o1.equals(o2));
}
/**
- * 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
- * does not permit null keys
- * @throws IllegalArgumentException {@inheritDoc}
+ * Return SimpleImmutableEntry for entry, or null if null
*/
- public SortedMap subMap(K fromKey, K toKey) {
- return new SubMap(fromKey, toKey);
+ static Map.Entry exportEntry(TreeMap.Entry e) {
+ return e == null? null :
+ new AbstractMap.SimpleImmutableEntry(e);
}
/**
- * 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
- * does not permit null keys
- * @throws IllegalArgumentException {@inheritDoc}
+ * Return key for entry, or null if null
*/
- public SortedMap headMap(K toKey) {
- return new SubMap(toKey, true);
+ static K keyOrNull(TreeMap.Entry e) {
+ return e == null? null : e.key;
}
/**
- * 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
- * does not permit null keys
- * @throws IllegalArgumentException {@inheritDoc}
+ * Returns the key corresponding to the specified Entry.
+ * @throws NoSuchElementException if the Entry is null
*/
- public SortedMap tailMap(K fromKey) {
- return new SubMap(fromKey, false);
+ static K key(Entry e) {
+ if (e==null)
+ throw new NoSuchElementException();
+ return e.key;
}
- private class SubMap
- extends AbstractMap
- implements NavigableMap, java.io.Serializable {
- private static final long serialVersionUID = -6520786458950516097L;
+ // SubMaps
+
+ /**
+ * @serial include
+ */
+ static abstract class NavigableSubMap extends AbstractMap
+ implements NavigableMap, java.io.Serializable {
/**
- * fromKey is significant only if fromStart is false. Similarly,
- * toKey is significant only if toStart is false.
+ * The backing map.
*/
- private boolean fromStart = false, toEnd = false;
- private K fromKey, toKey;
+ final TreeMap m;
- SubMap(K fromKey, K toKey) {
- if (compare(fromKey, toKey) > 0)
- throw new IllegalArgumentException("fromKey > toKey");
- this.fromKey = fromKey;
- this.toKey = toKey;
- }
-
- SubMap(K key, boolean headMap) {
- compare(key, key); // Type-check key
-
- if (headMap) {
- fromStart = true;
- toKey = key;
+ /**
+ * 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 boolean loInclusive, hiInclusive;
+
+ NavigableSubMap(TreeMap m,
+ 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 {
- toEnd = true;
- fromKey = key;
+ if (!fromStart) // type check
+ m.compare(lo, lo);
+ if (!toEnd)
+ m.compare(hi, hi);
}
- }
- SubMap(boolean fromStart, K fromKey, boolean toEnd, K toKey) {
+ this.m = m;
this.fromStart = fromStart;
- this.fromKey= fromKey;
+ this.lo = lo;
+ this.loInclusive = loInclusive;
this.toEnd = toEnd;
- this.toKey = toKey;
+ this.hi = hi;
+ 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 !tooLow(key) && !tooHigh(key);
+ }
+
+ final boolean inClosedRange(Object key) {
+ return (fromStart || m.compare(key, lo) >= 0)
+ && (toEnd || m.compare(hi, key) >= 0);
+ }
+
+ final boolean inRange(Object key, boolean inclusive) {
+ return inclusive ? inRange(key) : inClosedRange(key);
+ }
+
+ /*
+ * Absolute versions of relation operations.
+ * Subclasses map to these using like-named "sub"
+ * versions that invert senses for descending maps
+ */
+
+ final TreeMap.Entry absLowest() {
+ TreeMap.Entry e =
+ (fromStart ? m.getFirstEntry() :
+ (loInclusive ? m.getCeilingEntry(lo) :
+ m.getHigherEntry(lo)));
+ return (e == null || tooHigh(e.key)) ? null : e;
+ }
+
+ final TreeMap.Entry absHighest() {
+ TreeMap.Entry e =
+ (toEnd ? m.getLastEntry() :
+ (hiInclusive ? m.getFloorEntry(hi) :
+ m.getLowerEntry(hi)));
+ return (e == null || tooLow(e.key)) ? null : e;
+ }
+
+ 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;
+ }
+
+ 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;
+ }
+
+ 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;
}
+ 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) && TreeMap.this.containsKey(key);
+ public int size() {
+ return (fromStart && toEnd) ? m.size() : entrySet().size();
}
- public V get(Object key) {
- if (!inRange(key))
- return null;
- return TreeMap.this.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 TreeMap.this.put(key, value);
+ return m.put(key, value);
}
- public V remove(Object key) {
- if (!inRange(key))
- return null;
- return TreeMap.this.remove(key);
+ public final V get(Object key) {
+ return !inRange(key)? null : m.get(key);
}
- public Comparator super K> comparator() {
- return comparator;
+ public final V remove(Object key) {
+ return !inRange(key)? null : m.remove(key);
}
- 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 final Map.Entry ceilingEntry(K key) {
+ return exportEntry(subCeiling(key));
}
- 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 final K ceilingKey(K key) {
+ return keyOrNull(subCeiling(key));
}
- public Map.Entry firstEntry() {
- TreeMap.Entry e = fromStart ?
- getFirstEntry() : getCeilingEntry(fromKey);
- if (e == null || (!toEnd && compare(e.key, toKey) >= 0))
- return null;
- return e;
+ public final Map.Entry higherEntry(K key) {
+ return exportEntry(subHigher(key));
}
- 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 final K higherKey(K key) {
+ return keyOrNull(subHigher(key));
}
- 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 final Map.Entry floorEntry(K key) {
+ return exportEntry(subFloor(key));
}
- public Map.Entry pollLastEntry() {
- TreeMap.Entry e = toEnd ?
- getLastEntry() : getLowerEntry(toKey);
- if (e == null || (!fromStart && compare(e.key, fromKey) < 0))
- return null;
- Map.Entry result = new AbstractMap.SimpleImmutableEntry(e);
- deleteEntry(e);
- return result;
+ public final K floorKey(K key) {
+ return keyOrNull(subFloor(key));
}
- 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))
- return null;
- return e;
+ public final Map.Entry lowerEntry(K key) {
+ return exportEntry(subLower(key));
}
- public Map.Entry ceilingEntry(K key) {
- TreeMap.Entry e = subceiling(key);
- return e == null? null : new AbstractMap.SimpleImmutableEntry(e);
+ public final K lowerKey(K key) {
+ return keyOrNull(subLower(key));
}
- public K ceilingKey(K key) {
- TreeMap.Entry e = subceiling(key);
- return e == null? null : e.key;
+ public final K firstKey() {
+ return key(subLowest());
}
-
- 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 final K lastKey() {
+ return key(subHighest());
}
- public Map.Entry higherEntry(K key) {
- TreeMap.Entry e = subhigher(key);
- return e == null? null : new AbstractMap.SimpleImmutableEntry(e);
+ public final Map.Entry firstEntry() {
+ return exportEntry(subLowest());
}
- public K higherKey(K key) {
- TreeMap.Entry e = subhigher(key);
- return e == null? null : e.key;
+ public final Map.Entry lastEntry() {
+ return exportEntry(subHighest());
}
- private TreeMap.Entry