--- jsr166/src/main/java/util/TreeMap.java 2004/12/28 12:14:07 1.1
+++ jsr166/src/main/java/util/TreeMap.java 2006/05/10 02:31:44 1.38
@@ -1,26 +1,24 @@
/*
* %W% %E%
*
- * Copyright 2004 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;
-
+package java.util;
/**
- * Red-Black tree based implementation of the NavigableMap interface.
- * This class guarantees that the map will be in ascending key order, sorted
- * according to the natural order for the key's class (see
- * Comparable), or by the comparator provided at creation time,
- * depending on which constructor is used.
+ * A Red-Black tree based {@link NavigableMap} implementation.
+ * The map is sorted according to the {@linkplain Comparable natural
+ * ordering} of its keys, or by a {@link Comparator} provided at map
+ * creation time, depending on which constructor is used.
*
- * This implementation provides guaranteed log(n) time cost for the
+ *
This implementation provides guaranteed log(n) time cost for the
* containsKey, get, put and remove
* operations. Algorithms are adaptations of those in Cormen, Leiserson, and
- * Rivest's Introduction to Algorithms.
+ * Rivest's Introduction to Algorithms.
*
- * Note that the ordering maintained by a sorted map (whether or not an
+ *
Note that the ordering maintained by a sorted map (whether or not an
* explicit comparator is provided) must be consistent with equals if
* this sorted map is to correctly implement the Map interface. (See
* Comparable or Comparator for a precise definition of
@@ -30,30 +28,30 @@ package java.util;
* method, so two keys that are deemed equal by this method are, from the
* standpoint of the sorted map, equal. The behavior of a sorted map
* is well-defined even if its ordering is inconsistent with equals; it
- * just fails to obey the general contract of the Map interface.
+ * 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 all of this class's "collection view methods" are
+ * The iterators returned by the iterator method of the collections
+ * returned by all of this class's "collection view methods" are
* fail-fast: if the map is structurally modified at any time after the
* iterator is created, in any way except through the iterator's own
- * remove or add methods, the iterator throws a
- * ConcurrentModificationException. Thus, in the face of concurrent
+ * remove method, the iterator will throw a {@link
+ * ConcurrentModificationException}. Thus, in the face of concurrent
* modification, the iterator fails quickly and cleanly, rather than risking
- * arbitrary, non-deterministic behavior at an undetermined time in the
- * future.
+ * arbitrary, non-deterministic behavior at an undetermined time in the future.
*
*
Note that the fail-fast behavior of an iterator cannot be guaranteed
* as it is, generally speaking, impossible to make any hard guarantees in the
@@ -61,7 +59,7 @@ package java.util;
* throw ConcurrentModificationException on a best-effort basis.
* Therefore, it would be wrong to write a program that depended on this
* exception for its correctness: the fail-fast behavior of iterators
- * should be used only to detect bugs.
+ * should be used only to detect bugs.
*
*
All Map.Entry pairs returned by methods in this class
* and its views represent snapshots of mappings at the time they were
@@ -70,9 +68,12 @@ package java.util;
* associated map using put.)
*
*
This class is a member of the
- *
+ *
* Java Collections Framework.
*
+ * @param the type of keys maintained by this map
+ * @param the type of mapped values
+ *
* @author Josh Bloch and Doug Lea
* @version %I%, %G%
* @see Map
@@ -81,7 +82,6 @@ package java.util;
* @see Comparable
* @see Comparator
* @see Collection
- * @see Collections#synchronizedMap(Map)
* @since 1.2
*/
@@ -90,12 +90,12 @@ public class TreeMap
implements NavigableMap, Cloneable, java.io.Serializable
{
/**
- * The Comparator used to maintain order in this TreeMap, or
- * null if this TreeMap uses its elements natural ordering.
+ * The comparator used to maintain order in this tree map, or
+ * null if it uses the natural ordering of its keys.
*
* @serial
*/
- private Comparator comparator = null;
+ private final Comparator comparator;
private transient Entry root = null;
@@ -109,68 +109,67 @@ public class TreeMap
*/
private transient int modCount = 0;
- private void incrementSize() { modCount++; size++; }
- private void decrementSize() { modCount++; size--; }
-
/**
- * Constructs a new, empty map, sorted according to the keys' natural
- * order. All keys inserted into the map must implement the
- * Comparable interface. Furthermore, all such keys must be
- * mutually comparable: k1.compareTo(k2) must not throw a
- * ClassCastException for any elements k1 and k2 in the
- * map. If the user attempts to put a key into the map that violates this
- * constraint (for example, the user attempts to put a string key into a
- * map whose keys are integers), the put(Object key, Object
- * value) call will throw a ClassCastException.
- *
- * @see Comparable
+ * Constructs a new, empty tree map, using the natural ordering of its
+ * keys. All keys inserted into the map must implement the {@link
+ * Comparable} interface. Furthermore, all such keys must be
+ * mutually comparable: k1.compareTo(k2) must not throw
+ * a ClassCastException for any keys k1 and
+ * k2 in the map. If the user attempts to put a key into the
+ * map that violates this constraint (for example, the user attempts to
+ * put a string key into a map whose keys are integers), the
+ * put(Object key, Object value) call will throw a
+ * ClassCastException.
*/
public TreeMap() {
+ comparator = null;
}
/**
- * Constructs a new, empty map, sorted according to the given comparator.
- * All keys inserted into the map must be mutually comparable by
- * the given comparator: comparator.compare(k1, k2) must not
- * throw a ClassCastException for any keys k1 and
- * k2 in the map. If the user attempts to put a key into the
- * map that violates this constraint, the put(Object key, Object
- * value) call will throw a ClassCastException.
+ * Constructs a new, empty tree map, ordered according to the given
+ * comparator. All keys inserted into the map must be mutually
+ * comparable by the given comparator: comparator.compare(k1,
+ * k2) must not throw a ClassCastException for any keys
+ * k1 and k2 in the map. If the user attempts to put
+ * a key into the map that violates this constraint, the put(Object
+ * key, Object value) call will throw a
+ * ClassCastException.
*
- * @param c the comparator that will be used to sort this map. A
- * null value indicates that the keys' natural
- * ordering should be used.
- */
- public TreeMap(Comparator c) {
- this.comparator = c;
+ * @param comparator the comparator that will be used to order this map.
+ * If null, the {@linkplain Comparable natural
+ * ordering} of the keys will be used.
+ */
+ public TreeMap(Comparator comparator) {
+ this.comparator = comparator;
}
/**
- * Constructs a new map containing the same mappings as the given map,
- * sorted according to the keys' natural order. All keys inserted
- * into the new map must implement the Comparable interface.
- * Furthermore, all such keys must be mutually comparable:
- * k1.compareTo(k2) must not throw a ClassCastException
- * for any elements k1 and k2 in the map. This method
- * runs in n*log(n) time.
- *
- * @param m the map whose mappings are to be placed in this map.
- * @throws ClassCastException the keys in t are not Comparable, or
- * are not mutually comparable.
- * @throws NullPointerException if the specified map is null.
+ * Constructs a new tree map containing the same mappings as the given
+ * map, ordered according to the natural ordering of its keys.
+ * All keys inserted into the new map must implement the {@link
+ * Comparable} interface. Furthermore, all such keys must be
+ * mutually comparable: k1.compareTo(k2) must not throw
+ * a ClassCastException for any keys k1 and
+ * k2 in the map. This method runs in n*log(n) time.
+ *
+ * @param m the map whose mappings are to be placed in this map
+ * @throws ClassCastException if the keys in m are not {@link Comparable},
+ * or are not mutually comparable
+ * @throws NullPointerException if the specified map is null
*/
public TreeMap(Map m) {
+ comparator = null;
putAll(m);
}
/**
- * Constructs a new map containing the same mappings as the given
- * SortedMap, sorted according to the same ordering. This method
- * runs in linear time.
+ * Constructs a new tree map containing the same mappings and
+ * using the same ordering as the specified sorted map. This
+ * method runs in linear time.
*
* @param m the sorted map whose mappings are to be placed in this map,
- * and whose comparator is to be used to sort this map.
- * @throws NullPointerException if the specified sorted map is null.
+ * and whose comparator is to be used to sort this map
+ * @throws NullPointerException if the specified map is null
*/
public TreeMap(SortedMap m) {
comparator = m.comparator();
@@ -187,7 +186,7 @@ public class TreeMap
/**
* Returns the number of key-value mappings in this map.
*
- * @return the number of key-value mappings in this map.
+ * @return the number of key-value mappings in this map
*/
public int size() {
return size;
@@ -197,15 +196,14 @@ public class TreeMap
* Returns true if this map contains a mapping for the specified
* key.
*
- * @param key key whose presence in this map is to be tested.
- *
+ * @param key key whose presence in this map is to be tested
* @return true if this map contains a mapping for the
- * specified key.
- * @throws ClassCastException if the key cannot be compared with the keys
- * currently in the map.
- * @throws NullPointerException key is null and this map uses
- * natural ordering, or its comparator does not tolerate
- * null keys.
+ * specified key
+ * @throws ClassCastException if the specified key cannot be compared
+ * with the keys currently in the map
+ * @throws NullPointerException if the specified key is null
+ * and this map uses natural ordering, or its comparator
+ * does not permit null keys
*/
public boolean containsKey(Object key) {
return getEntry(key) != null;
@@ -216,106 +214,77 @@ 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 will probably require time linear in the Map size for most
- * implementations of Map.
+ * 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;
- * false otherwise.
+ * @param value value whose presence in this map is to be tested
+ * @return true if a mapping to value exists;
+ * false otherwise
* @since 1.2
*/
public boolean containsValue(Object value) {
- return (root==null ? false :
- (value==null ? valueSearchNull(root)
- : valueSearchNonNull(root, value)));
- }
-
- private boolean valueSearchNull(Entry n) {
- if (n.value == null)
- return true;
-
- // Check left and right subtrees for value
- return (n.left != null && valueSearchNull(n.left)) ||
- (n.right != null && valueSearchNull(n.right));
- }
-
- private boolean valueSearchNonNull(Entry n, Object value) {
- // Check this node for the value
- if (value.equals(n.value))
- return true;
-
- // Check left and right subtrees for value
- return (n.left != null && valueSearchNonNull(n.left, value)) ||
- (n.right != null && valueSearchNonNull(n.right, value));
+ for (Entry e = getFirstEntry(); e != null; e = successor(e))
+ if (valEquals(value, e.value))
+ return true;
+ return false;
}
/**
- * Returns the value to which this map maps the specified key. Returns
- * null if the map contains no mapping for this 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 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.
- * @throws ClassCastException key cannot be compared with the keys
- * currently in the map.
- * @throws NullPointerException key is null and this map uses
- * natural ordering, or its comparator does not tolerate
- * null keys.
+ * Returns the value to which the specified key is mapped,
+ * or {@code null} if this map contains no mapping for the key.
*
- * @see #containsKey(Object)
+ * 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
+ * and this map uses natural ordering, or its comparator
+ * does not permit null keys
*/
public V get(Object key) {
Entry p = getEntry(key);
return (p==null ? null : p.value);
}
- /**
- * Returns the comparator used to order this map, or null if this
- * map uses its keys' natural order.
- *
- * @return the comparator associated with this sorted map, or
- * null if it uses its keys' natural sort method.
- */
public Comparator comparator() {
return comparator;
}
/**
- * Returns the first (lowest) key currently in this sorted map.
- *
- * @return the first (lowest) key currently in this sorted map.
- * @throws NoSuchElementException Map is empty.
+ * @throws NoSuchElementException {@inheritDoc}
*/
public K firstKey() {
return key(getFirstEntry());
}
/**
- * Returns the last (highest) key currently in this sorted map.
- *
- * @return the last (highest) key currently in this sorted map.
- * @throws NoSuchElementException Map is empty.
+ * @throws NoSuchElementException {@inheritDoc}
*/
public K lastKey() {
return key(getLastEntry());
}
/**
- * Copies all of the mappings from the specified map to this map. These
- * mappings replace any mappings that this map had for any of the keys
- * currently in the specified map.
- *
- * @param map mappings to be stored in this map.
- * @throws ClassCastException class of a key or value in the specified
- * map prevents it from being stored in this map.
- *
- * @throws NullPointerException if the given map is null or
- * this map does not permit null keys and a
- * key in the specified map is null.
+ * Copies all of the mappings from the specified map to this map.
+ * These mappings replace any mappings that this map had for any
+ * of the keys currently in the specified map.
+ *
+ * @param map mappings to be stored in this map
+ * @throws ClassCastException if the class of a key or value in
+ * the specified map prevents it from being stored in this map
+ * @throws NullPointerException if the specified map is null or
+ * the specified map contains a null key and this map does not
+ * permit null keys
*/
public void putAll(Map map) {
int mapSize = map.size();
@@ -340,18 +309,20 @@ public class TreeMap
* does not contain an entry for the key.
*
* @return this map's entry for the given key, or null if the map
- * does not contain an entry for the key.
- * @throws ClassCastException if the key cannot be compared with the keys
- * currently in the map.
- * @throws NullPointerException key is null and this map uses
- * natural order, or its comparator does not tolerate *
- * null keys.
+ * does not contain an entry for the key
+ * @throws ClassCastException if the specified key cannot be compared
+ * with the keys currently in the map
+ * @throws NullPointerException if the specified key is null
+ * 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);
- Comparable k = (Comparable) key;
+ if (key == null)
+ throw new NullPointerException();
+ Comparable k = (Comparable) key;
Entry p = root;
while (p != null) {
int cmp = k.compareTo(p.key);
@@ -371,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 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;
}
@@ -393,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)
@@ -420,6 +390,7 @@ public class TreeMap
} else
return p;
}
+ return null;
}
/**
@@ -427,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)
@@ -455,6 +423,7 @@ public class TreeMap
return p;
}
+ return null;
}
/**
@@ -463,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)
@@ -489,6 +455,7 @@ public class TreeMap
}
}
}
+ return null;
}
/**
@@ -496,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)
@@ -522,85 +486,95 @@ public class TreeMap
}
}
}
- }
-
- /**
- * Returns the key corresponding to the specified Entry. Throw
- * NoSuchElementException if the Entry is null.
- */
- private static K key(Entry e) {
- if (e==null)
- throw new NoSuchElementException();
- return e.key;
+ return null;
}
/**
* 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.
- * @param value value to be associated with the specified key.
+ * @param key key with which the specified value is to be associated
+ * @param value value to be associated with the specified key
*
- * @return previous value associated with specified key, or null
- * if there was no mapping for key. A null return can
- * also indicate that the map previously associated null
- * with the specified key.
- * @throws ClassCastException key cannot be compared with the keys
- * currently in the map.
- * @throws NullPointerException key is null and this map uses
- * natural order, or its comparator does not tolerate
- * null keys.
+ * @return the previous value associated with key, or
+ * null if there was no mapping for key.
+ * (A null return can also indicate that the map
+ * previously associated null with key.)
+ * @throws ClassCastException if the specified key cannot be compared
+ * with the keys currently in the map
+ * @throws NullPointerException if the specified key is null
+ * and this map uses natural ordering, or its comparator
+ * does not permit null keys
*/
public V put(K key, V value) {
Entry t = root;
-
if (t == null) {
- 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 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 k = (Comparable) key;
+ do {
+ parent = t;
+ cmp = k.compareTo(t.key);
+ if (cmp < 0)
+ t = t.left;
+ else if (cmp > 0)
+ t = t.right;
+ else
+ return t.setValue(value);
+ } while (t != null);
+ }
+ Entry e = new Entry(key, value, parent);
+ if (cmp < 0)
+ parent.left = e;
+ else
+ parent.right = e;
+ fixAfterInsertion(e);
+ size++;
+ modCount++;
+ return null;
}
/**
* Removes the mapping for this key from this TreeMap if present.
*
* @param key key for which mapping should be removed
- * @return previous value associated with specified key, or null
- * if there was no mapping for key. A null return can
- * also indicate that the map previously associated
- * null with the specified key.
- *
- * @throws ClassCastException key cannot be compared with the keys
- * currently in the map.
- * @throws NullPointerException key is null and this map uses
- * natural order, or its comparator does not tolerate
- * null keys.
+ * @return the previous value associated with key, or
+ * null if there was no mapping for key.
+ * (A null return can also indicate that the map
+ * previously associated null with key.)
+ * @throws ClassCastException if the specified key cannot be compared
+ * with the keys currently in the map
+ * @throws NullPointerException if the specified key is null
+ * and this map uses natural ordering, or its comparator
+ * does not permit null keys
*/
public V remove(Object key) {
Entry p = getEntry(key);
@@ -613,7 +587,8 @@ public class TreeMap
}
/**
- * Removes all mappings from this TreeMap.
+ * Removes all of the mappings from this map.
+ * The map will be empty after this call returns.
*/
public void clear() {
modCount++;
@@ -625,7 +600,7 @@ public class TreeMap
* Returns a shallow copy of this TreeMap instance. (The keys and
* values themselves are not cloned.)
*
- * @return a shallow copy of this Map.
+ * @return a shallow copy of this map
*/
public Object clone() {
TreeMap clone = null;
@@ -640,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 {
@@ -656,213 +631,127 @@ public class TreeMap
// NavigableMap API methods
/**
- * Returns a key-value mapping associated with the least
- * key in this map, or null if the map is empty.
- *
- * @return an Entry with least key, or null
- * if the map is empty.
+ * @since 1.6
*/
public Map.Entry firstEntry() {
- Entry e = getFirstEntry();
- return (e == null)? null : new SnapshotEntry(e);
+ return exportEntry(getFirstEntry());
}
/**
- * Returns a key-value mapping associated with the greatest
- * key in this map, or null if the map is empty.
- * The returned entry does not support
- * the Entry.setValue method.
- *
- * @return an Entry with greatest key, or null
- * if the map is empty.
+ * @since 1.6
*/
public Map.Entry lastEntry() {
- Entry e = getLastEntry();
- return (e == null)? null : new SnapshotEntry(e);
+ return exportEntry(getLastEntry());
}
/**
- * Removes and returns a key-value mapping associated with
- * the least key in this map, or null if the map is empty.
- *
- * @return the removed first entry of this map, or null
- * if the map is empty.
+ * @since 1.6
*/
public Map.Entry pollFirstEntry() {
Entry p = getFirstEntry();
- if (p == null)
- return null;
- Map.Entry result = new SnapshotEntry(p);
- deleteEntry(p);
+ Map.Entry result = exportEntry(p);
+ if (p != null)
+ deleteEntry(p);
return result;
}
/**
- * Removes and returns a key-value mapping associated with
- * the greatest key in this map, or null if the map is empty.
- *
- * @return the removed last entry of this map, or null
- * if the map is empty.
+ * @since 1.6
*/
public Map.Entry pollLastEntry() {
Entry p = getLastEntry();
- if (p == null)
- return null;
- Map.Entry result = new SnapshotEntry(p);
- deleteEntry(p);
+ Map.Entry result = exportEntry(p);
+ if (p != null)
+ deleteEntry(p);
return result;
}
/**
- * Returns a key-value mapping associated with the least key
- * greater than or equal to the given key, or null if
- * there is no such entry.
- *
- * @param key the key.
- * @return an Entry associated with ceiling of given key, or
- * null if there is no such Entry.
- * @throws ClassCastException if key cannot be compared with the
- * keys currently in the map.
- * @throws NullPointerException key is null and this map uses
- * natural order, or its comparator does not tolerate
- * null keys.
+ * @throws ClassCastException {@inheritDoc}
+ * @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);
- return (e == null)? null : new SnapshotEntry(e);
+ public Map.Entry lowerEntry(K key) {
+ return exportEntry(getLowerEntry(key));
}
-
/**
- * Returns least key greater than or equal to the given key, or
- * null if there is no such key.
- *
- * @param key the key.
- * @return the ceiling key, or null
- * if there is no such key.
- * @throws ClassCastException if key cannot be compared with the keys
- * currently in the map.
- * @throws NullPointerException key is null and this map uses
- * natural order, or its comparator does not tolerate
- * null keys.
+ * @throws ClassCastException {@inheritDoc}
+ * @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);
- return (e == null)? null : e.key;
+ public K lowerKey(K key) {
+ return keyOrNull(getLowerEntry(key));
}
-
-
/**
- * Returns a key-value mapping associated with the greatest key
- * less than or equal to the given key, or null if there
- * is no such entry.
- *
- * @param key the key.
- * @return an Entry associated with floor of given key, or null
- * if there is no such Entry.
- * @throws ClassCastException if key cannot be compared with the keys
- * currently in the map.
- * @throws NullPointerException key is null and this map uses
- * natural order, or its comparator does not tolerate
- * null keys.
+ * @throws ClassCastException {@inheritDoc}
+ * @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);
- return (e == null)? null : new SnapshotEntry(e);
+ return exportEntry(getFloorEntry(key));
}
/**
- * Returns the greatest key
- * less than or equal to the given key, or null if there
- * is no such key.
- *
- * @param key the key.
- * @return the floor of given key, or null if there is no
- * such key.
- * @throws ClassCastException if key cannot be compared with the keys
- * currently in the map.
- * @throws NullPointerException key is null and this map uses
- * natural order, or its comparator does not tolerate
- * null keys.
+ * @throws ClassCastException {@inheritDoc}
+ * @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);
- return (e == null)? null : e.key;
+ return keyOrNull(getFloorEntry(key));
}
/**
- * Returns a key-value mapping associated with the least key
- * strictly greater than the given key, or null if there
- * is no such entry.
- *
- * @param key the key.
- * @return an Entry with least key greater than the given key, or
- * null if there is no such Entry.
- * @throws ClassCastException if key cannot be compared with the keys
- * currently in the map.
- * @throws NullPointerException key is null and this map uses
- * natural order, or its comparator does not tolerate
- * null keys.
+ * @throws ClassCastException {@inheritDoc}
+ * @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);
- return (e == null)? null : new SnapshotEntry(e);
+ public Map.Entry ceilingEntry(K key) {
+ return exportEntry(getCeilingEntry(key));
}
/**
- * Returns the least key strictly greater than the given key, or
- * null if there is no such key.
- *
- * @param key the key.
- * @return the least key greater than the given key, or
- * null if there is no such key.
- * @throws ClassCastException if key cannot be compared with the keys
- * currently in the map.
- * @throws NullPointerException key is null and this map uses
- * natural order, or its comparator does not tolerate
- * null keys.
+ * @throws ClassCastException {@inheritDoc}
+ * @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);
- return (e == null)? null : e.key;
+ public K ceilingKey(K key) {
+ return keyOrNull(getCeilingEntry(key));
}
/**
- * Returns a key-value mapping associated with the greatest
- * key strictly less than the given key, or null if there is no
- * such entry.
- *
- * @param key the key.
- * @return an Entry with greatest key less than the given
- * key, or null if there is no such Entry.
- * @throws ClassCastException if key cannot be compared with the keys
- * currently in the map.
- * @throws NullPointerException key is null and this map uses
- * natural order, or its comparator does not tolerate
- * null keys.
+ * @throws ClassCastException {@inheritDoc}
+ * @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);
- return (e == null)? null : new SnapshotEntry(e);
+ public Map.Entry higherEntry(K key) {
+ return exportEntry(getHigherEntry(key));
}
/**
- * Returns the greatest key strictly less than the given key, or
- * null if there is no such key.
- *
- * @param key the key.
- * @return the greatest key less than the given
- * key, or null if there is no such key.
- * @throws ClassCastException if key cannot be compared with the keys
- * currently in the map.
- * @throws NullPointerException key is null and this map uses
- * natural order, or its comparator does not tolerate
- * null keys.
+ * @throws ClassCastException {@inheritDoc}
+ * @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);
- return (e == null)? null : e.key;
+ public K higherKey(K key) {
+ return keyOrNull(getHigherEntry(key));
}
// Views
@@ -872,88 +761,185 @@ 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;
-
- transient Set keySet = null; // XXX remove when integrated
- transient Collection values = null; // XXX remove when integrated
-
- /**
- * Returns a Set view of the keys contained in this map. The set's
- * iterator will return the keys in ascending order. The set is backed by
- * this TreeMap instance, so changes to this map are reflected in
- * the Set, and vice-versa. 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.
- *
- * @return a set view of the keys contained in this TreeMap.
+ 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.
+ * The set's iterator returns the keys in ascending 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), 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 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;
- }
-
- public void clear() {
- TreeMap.this.clear();
- }
+ /**
+ * @since 1.6
+ */
+ public NavigableSet navigableKeySet() {
+ KeySet nks = navigableKeySet;
+ return (nks != null) ? nks : (navigableKeySet = new KeySet(this));
}
/**
- * Returns a collection view of the values contained in this map. The
- * collection's iterator will return the values in the order that their
- * corresponding keys appear in the tree. The collection is backed by
- * this TreeMap instance, so changes to this map are reflected in
- * the collection, and vice-versa. The collection supports element
- * removal, which removes the corresponding mapping from the map through
- * the Iterator.remove, Collection.remove,
- * removeAll, retainAll, and clear operations.
- * It does not support the add or addAll operations.
- *
- * @return a collection view of the values contained in this map.
+ * @since 1.6
+ */
+ public NavigableSet descendingKeySet() {
+ return descendingMap().navigableKeySet();
+ }
+
+ /**
+ * Returns a {@link Collection} view of the values contained in this map.
+ * The collection's iterator returns the values in ascending order
+ * of the corresponding keys.
+ * The collection is backed by the map, so changes to the map are
+ * reflected in the collection, and vice-versa. If the map is
+ * modified while an iteration over the collection is in progress
+ * (except through the iterator's own remove operation),
+ * the results of the iteration are undefined. The collection
+ * supports element removal, which removes the corresponding
+ * mapping from the map, via the Iterator.remove,
+ * Collection.remove, removeAll,
+ * retainAll and clear operations. It does not
+ * support the add or addAll operations.
*/
public Collection values() {
Collection vs = values;
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());
}
-
+
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;
+ return TreeMap.this.containsValue(o);
}
-
+
public boolean remove(Object o) {
for (Entry e = getFirstEntry(); e != null; e = successor(e)) {
if (valEquals(e.getValue(), o)) {
@@ -963,36 +949,17 @@ public class TreeMap
}
return false;
}
-
+
public void clear() {
TreeMap.this.clear();
}
}
- /**
- * Returns a set view of the mappings contained in this map. The set's
- * iterator returns the mappings in ascending key order. Each element in
- * the returned set is a Map.Entry. The set is backed by this
- * map, so changes to this map are reflected in the set, and vice-versa.
- * The set supports element removal, which removes the corresponding
- * mapping from the TreeMap, through the Iterator.remove,
- * Set.remove, removeAll, retainAll and
- * clear operations. It does not support the add or
- * addAll operations.
- *
- * @return a set view of the mappings contained in this map.
- * @see Map.Entry
- */
- public Set> entrySet() {
- Set> es = entrySet;
- 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;
@@ -1001,7 +968,7 @@ public class TreeMap
Entry p = getEntry(entry.getKey());
return p != null && valEquals(p.getValue(), value);
}
-
+
public boolean remove(Object o) {
if (!(o instanceof Map.Entry))
return false;
@@ -1014,400 +981,524 @@ public class TreeMap
}
return false;
}
-
+
public int size() {
return TreeMap.this.size();
}
-
+
public void clear() {
TreeMap.this.clear();
}
}
- /**
- * Returns a set view of the mappings contained in this map. The
- * set's iterator returns the mappings in descrending key order.
- * Each element in the returned set is a Map.Entry. The
- * set is backed by this map, so changes to this map are reflected
- * in the set, and vice-versa. The set supports element removal,
- * which removes the corresponding mapping from the TreeMap,
- * through the Iterator.remove, Set.remove,
- * removeAll, retainAll and clear
- * operations. It does not support the add or
- * addAll operations.
- *
- * @return a set view of the mappings contained in this map, in
- * descending key order
- * @see Map.Entry
- */
- public Set> descendingEntrySet() {
- Set> es = descendingEntrySet;
- return (es != null) ? es : (descendingEntrySet = new DescendingEntrySet());
+ /*
+ * 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());
}
- 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 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());
}
}
/**
- * Returns a Set view of the keys contained in this map. The
- * set's iterator will return the keys in descending order. The
- * map is backed by this TreeMap instance, so changes to
- * this map are reflected in the Set, and vice-versa. 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.
- *
- * @return a set view of the keys contained in this TreeMap.
+ * Base class for TreeMap Iterators
*/
- public Set descendingKeySet() {
- Set ks = descendingKeySet;
- return (ks != null) ? ks : (descendingKeySet = new DescendingKeySet());
- }
-
- class DescendingKeySet extends KeySet {
- public Iterator iterator() {
- return new DescendingKeyIterator(getLastEntry());
+ 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();
+ // deleted entries are replaced by their successors
+ if (lastReturned.left != null && lastReturned.right != null)
+ next = lastReturned;
+ deleteEntry(lastReturned);
+ expectedModCount = modCount;
+ lastReturned = null;
+ }
+ }
+
+ final class EntryIterator extends PrivateEntryIterator> {
+ EntryIterator(Entry first) {
+ super(first);
+ }
+ public Map.Entry next() {
+ return nextEntry();
+ }
+ }
+
+ 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
+
/**
- * Returns a view of the portion of this map whose keys range from
- * fromKey, inclusive, to toKey, exclusive. (If
- * fromKey and toKey are equal, the returned sorted map
- * is empty.) The returned sorted map is backed by this map, so changes
- * in the returned sorted map are reflected in this map, and vice-versa.
- * The returned sorted map supports all optional map operations.
- *
- * The sorted map returned by this method will throw an
- * IllegalArgumentException if the user attempts to insert a key
- * less than fromKey or greater than or equal to
- * toKey.
- *
- * Note: this method always returns a half-open range (which
- * includes its low endpoint but not its high endpoint). If you need a
- * closed range (which includes both endpoints), and the key type
- * allows for calculation of the successor a given key, merely request the
- * subrange from lowEndpoint to successor(highEndpoint).
- * For example, suppose that m is a sorted map whose keys are
- * strings. The following idiom obtains a view containing all of the
- * key-value mappings in m whose keys are between low
- * and high, inclusive:
- *
NavigableMap sub = m.submap(low, high+"\0");
- * A similar technique can be used to generate an open range (which
- * contains neither endpoint). The following idiom obtains a view
- * containing all of the key-value mappings in m whose keys are
- * between low and high, exclusive:
- * NavigableMap sub = m.subMap(low+"\0", high);
- *
- * @param fromKey low endpoint (inclusive) of the subMap.
- * @param toKey high endpoint (exclusive) of the subMap.
- *
- * @return a view of the portion of this map whose keys range from
- * fromKey, inclusive, to toKey, exclusive.
- *
- * @throws ClassCastException if fromKey and toKey
- * cannot be compared to one another using this map's comparator
- * (or, if the map has no comparator, using natural ordering).
- * @throws IllegalArgumentException if fromKey is greater than
- * toKey.
- * @throws NullPointerException if fromKey or toKey is
- * null and this map uses natural order, or its
- * comparator does not tolerate null keys.
+ * Compares two keys using the correct comparison method for this TreeMap.
*/
- public NavigableMap subMap(K fromKey, K toKey) {
- return new SubMap(fromKey, toKey);
+ final int compare(Object k1, Object k2) {
+ return comparator==null ? ((Comparable)k1).compareTo((K)k2)
+ : comparator.compare((K)k1, (K)k2);
}
/**
- * Returns a view of the portion of this map whose keys are strictly less
- * than toKey. The returned sorted map is backed by this map, so
- * changes in the returned sorted map are reflected in this map, and
- * vice-versa. The returned sorted map supports all optional map
- * operations.
- *
- * The sorted map returned by this method will throw an
- * IllegalArgumentException if the user attempts to insert a key
- * greater than or equal to toKey.
- *
- * Note: this method always returns a view that does not contain its
- * (high) endpoint. If you need a view that does contain this endpoint,
- * and the key type allows for calculation of the successor a given key,
- * merely request a headMap bounded by successor(highEndpoint).
- * For example, suppose that suppose that m is a sorted map whose
- * keys are strings. The following idiom obtains a view containing all of
- * the key-value mappings in m whose keys are less than or equal
- * to high:
- *
- * NavigableMap head = m.headMap(high+"\0");
- *
- *
- * @param toKey high endpoint (exclusive) of the headMap.
- * @return a view of the portion of this map whose keys are strictly
- * less than toKey.
- *
- * @throws ClassCastException if toKey is not compatible
- * with this map's comparator (or, if the map has no comparator,
- * if toKey does not implement Comparable).
- * @throws IllegalArgumentException if this map is itself a subMap,
- * headMap, or tailMap, and toKey is not within the
- * specified range of the subMap, headMap, or tailMap.
- * @throws NullPointerException if toKey is null and
- * this map uses natural order, or its comparator does not
- * tolerate null keys.
- */
- public NavigableMap headMap(K toKey) {
- return new SubMap(toKey, true);
- }
-
- /**
- * Returns a view of the portion of this map whose keys are greater than
- * or equal to fromKey. The returned sorted map is backed by
- * this map, so changes in the returned sorted map are reflected in this
- * map, and vice-versa. The returned sorted map supports all optional map
- * operations.
- *
- * The sorted map returned by this method will throw an
- * IllegalArgumentException if the user attempts to insert a key
- * less than fromKey.
- *
- * Note: this method always returns a view that contains its (low)
- * endpoint. If you need a view that does not contain this endpoint, and
- * the element type allows for calculation of the successor a given value,
- * merely request a tailMap bounded by successor(lowEndpoint).
- * For example, suppose that m is a sorted map whose keys
- * are strings. The following idiom obtains a view containing
- * all of the key-value mappings in m whose keys are strictly
- * greater than low:
- * NavigableMap tail = m.tailMap(low+"\0");
- *
- *
- * @param fromKey low endpoint (inclusive) of the tailMap.
- * @return a view of the portion of this map whose keys are greater
- * than or equal to fromKey.
- * @throws ClassCastException if fromKey is not compatible
- * with this map's comparator (or, if the map has no comparator,
- * if fromKey does not implement Comparable).
- * @throws IllegalArgumentException if this map is itself a subMap,
- * headMap, or tailMap, and fromKey is not within the
- * specified range of the subMap, headMap, or tailMap.
- * @throws NullPointerException if fromKey is null and
- * this map uses natural order, or its comparator does not
- * tolerate null keys.
- */
- public NavigableMap tailMap(K fromKey) {
- return new SubMap(fromKey, false);
- }
-
- private class SubMap
- extends AbstractMap
- implements NavigableMap, java.io.Serializable {
- private static final long serialVersionUID = -6520786458950516097L;
+ * 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 {
/**
- * 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;
-
- SubMap(K fromKey, K toKey) {
- if (compare(fromKey, toKey) > 0)
- throw new IllegalArgumentException("fromKey > toKey");
- this.fromKey = fromKey;
- this.toKey = toKey;
- }
+ final TreeMap m;
- 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((K) key) && TreeMap.this.containsKey(key);
+ public int size() {
+ return (fromStart && toEnd) ? m.size() : entrySet().size();
}
- public V get(Object key) {
- if (!inRange((K) 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((K) key))
- return null;
- return TreeMap.this.remove(key);
+ public final V get(Object key) {
+ return !inRange(key)? null : m.get(key);
}
- public Comparator 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 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 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 ceilingEntry(K key) {
+ return exportEntry(subCeiling(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 ceilingKey(K key) {
+ return keyOrNull(subCeiling(key));
}
- public Map.Entry pollFirstEntry() {
- TreeMap.Entry e = fromStart ?
- getFirstEntry() : getCeilingEntry(fromKey);
- if (e == null || (!fromStart && compare(e.key, fromKey) < 0))
- return null;
- Map.Entry result = new SnapshotEntry(e);
- deleteEntry(e);
- return result;
+ public final Map.Entry higherEntry(K key) {
+ return exportEntry(subHigher(key));
}
- public Map.Entry pollLastEntry() {
- TreeMap.Entry e = toEnd ?
- getLastEntry() : getLowerEntry(toKey);
- if (e == null || (!toEnd && compare(e.key, toKey) >= 0))
- return null;
- Map.Entry result = new SnapshotEntry(e);
- deleteEntry(e);
- return result;
+ public final K higherKey(K key) {
+ return keyOrNull(subHigher(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 floorEntry(K key) {
+ return exportEntry(subFloor(key));
}
- public Map.Entry ceilingEntry(K key) {
- TreeMap.Entry e = subceiling(key);
- return e == null? null : new SnapshotEntry(e);
+ public final K floorKey(K key) {
+ return keyOrNull(subFloor(key));
}
- public K ceilingKey(K key) {
- TreeMap.Entry e = subceiling(key);
- return e == null? null : e.key;
+ public final Map.Entry lowerEntry(K key) {
+ return exportEntry(subLower(key));
}
+ public final K lowerKey(K key) {
+ return keyOrNull(subLower(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 final K firstKey() {
+ return key(subLowest());
}
- public Map.Entry higherEntry(K key) {
- TreeMap.Entry e = subhigher(key);
- return e == null? null : new SnapshotEntry(e);
+ public final K lastKey() {
+ return key(subHighest());
}
- public K higherKey(K key) {
- TreeMap.Entry e = subhigher(key);
- return e == null? null : e.key;
+ public final Map.Entry firstEntry() {
+ return exportEntry(subLowest());
}
- 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 final Map.Entry lastEntry() {
+ return exportEntry(subHighest());
}
- public Map.Entry floorEntry(K key) {
- TreeMap.Entry e = subfloor(key);
- return e == null? null : new SnapshotEntry(e);
+ public final Map.Entry pollFirstEntry() {
+ TreeMap.Entry e = subLowest();
+ Map.Entry result = exportEntry(e);
+ if (e != null)
+ m.deleteEntry(e);
+ return result;
}
- public K floorKey(K key) {
- TreeMap.Entry e = subfloor(key);
- return e == null? null : e.key;
+ public final Map.Entry pollLastEntry() {
+ TreeMap.Entry e = subHighest();
+ Map.Entry result = exportEntry(e);
+ if (e != null)
+ m.deleteEntry(e);
+ return result;
}
- 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;
+ // Views
+ transient NavigableMap descendingMapView = null;
+ transient EntrySetView entrySetView = null;
+ transient KeySet