--- jsr166/src/main/java/util/TreeMap.java 2005/03/22 01:30:10 1.4 +++ jsr166/src/main/java/util/TreeMap.java 2005/06/24 00:26:57 1.21 @@ -1,26 +1,25 @@ /* * %W% %E% * - * Copyright 2004 Sun Microsystems, Inc. All rights reserved. + * Copyright 2005 Sun Microsystems, Inc. All rights reserved. * SUN PROPRIETARY/CONFIDENTIAL. Use is subject to license terms. */ -package java.util; - +package java.util; +import java.util.*; // for javadoc (till 6280605 is fixed) /** - * 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,9 +29,9 @@ 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 + *

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 @@ -44,16 +43,16 @@ package java.util; * time, to prevent accidental unsynchronized access to the map: * 

  *     Map m = Collections.synchronizedMap(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 +60,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 @@ -73,6 +72,9 @@ package java.util; * * 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 @@ -90,8 +92,8 @@ 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 */ @@ -113,64 +115,64 @@ public class TreeMap 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() { } /** - * 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. - * - * @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; + * 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 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) { 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 +189,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 +199,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 if 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,12 +217,12 @@ 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) { @@ -250,72 +251,56 @@ public class TreeMap } /** - * Returns the value to which this map maps the specified key. Returns - * null if the map contains no mapping for this key. A return + * Returns the value to which this map maps the specified key, or + * null if the map contains no mapping for the key. A return * value of null does not necessarily indicate that the * map contains no mapping for the key; it's also possible that the map - * explicitly maps the key to null. The containsKey - * operation may be used to distinguish these two cases. + * explicitly maps the key to null. The {@link #containsKey + * containsKey} operation may be used to distinguish these two cases. * - * @param key key whose associated value is to be returned. + * @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 if key cannot be compared with the keys - * currently in the map. - * @throws NullPointerException if key is null and this map uses - * natural ordering, or its comparator does not tolerate - * null keys. - * - * @see #containsKey(Object) + * null if the map contains no mapping 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 */ 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 +325,18 @@ 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 if 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) { // Offload comparator-based version for sake of performance if (comparator != null) return getEntryUsingComparator(key); - Comparable k = (Comparable) key; + Comparable k = (Comparable) key; Entry p = root; while (p != null) { int cmp = k.compareTo(p.key); @@ -525,8 +510,8 @@ public class TreeMap } /** - * Returns the key corresponding to the specified Entry. Throw - * NoSuchElementException if the Entry is null. + * Returns the key corresponding to the specified Entry. + * @throws NoSuchElementException if the Entry is null */ private static K key(Entry e) { if (e==null) @@ -536,30 +521,35 @@ public class TreeMap /** * Associates the specified value with the specified key in this map. - * If the map previously contained a mapping for this key, the old + * If the map previously contained a mapping for the key, the old * value is replaced. * - * @param key key with which the specified value is to be associated. - * @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 if key cannot be compared with the keys - * currently in the map. - * @throws NullPointerException if 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) { + if (key == null) { + if (comparator == null) + throw new NullPointerException(); + comparator.compare(key, key); + } incrementSize(); root = new Entry(key, value, null); return null; - } + } while (true) { int cmp = compare(key, t.key); @@ -591,16 +581,15 @@ public class TreeMap * 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 if key cannot be compared with the keys - * currently in the map. - * @throws NullPointerException if 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 +602,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 +615,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; @@ -655,136 +645,72 @@ 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. - */ public Map.Entry firstEntry() { Entry e = getFirstEntry(); - return (e == null)? null : new AbstractMap.SimpleImmutableEntry(e); + return (e == null)? null : new AbstractMap.SimpleImmutableEntry(e); } - /** - * 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. - */ public Map.Entry lastEntry() { Entry e = getLastEntry(); - return (e == null)? null : new AbstractMap.SimpleImmutableEntry(e); + return (e == null)? null : new AbstractMap.SimpleImmutableEntry(e); } - /** - * 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. - */ public Map.Entry pollFirstEntry() { Entry p = getFirstEntry(); - if (p == null) + if (p == null) return null; - Map.Entry result = new AbstractMap.SimpleImmutableEntry(p); + Map.Entry result = new AbstractMap.SimpleImmutableEntry(p); 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. - */ public Map.Entry pollLastEntry() { Entry p = getLastEntry(); - if (p == null) + if (p == null) return null; - Map.Entry result = new AbstractMap.SimpleImmutableEntry(p); + Map.Entry result = new AbstractMap.SimpleImmutableEntry(p); 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 if 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 */ - public Map.Entry ceilingEntry(K key) { - Entry e = getCeilingEntry(key); - return (e == null)? null : new AbstractMap.SimpleImmutableEntry(e); + public Map.Entry lowerEntry(K key) { + Entry e = getLowerEntry(key); + return (e == null)? null : new AbstractMap.SimpleImmutableEntry(e); } - /** - * 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 if 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 */ - public K ceilingKey(K key) { - Entry e = getCeilingEntry(key); + public K lowerKey(K key) { + Entry e = getLowerEntry(key); return (e == null)? null : e.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 if 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 */ public Map.Entry floorEntry(K key) { Entry e = getFloorEntry(key); - return (e == null)? null : new AbstractMap.SimpleImmutableEntry(e); + return (e == null)? null : new AbstractMap.SimpleImmutableEntry(e); } /** - * 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 if 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 */ public K floorKey(K key) { Entry e = getFloorEntry(key); @@ -792,76 +718,46 @@ public class TreeMap } /** - * 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 if 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 */ - public Map.Entry higherEntry(K key) { - Entry e = getHigherEntry(key); - return (e == null)? null : new AbstractMap.SimpleImmutableEntry(e); + public Map.Entry ceilingEntry(K key) { + Entry e = getCeilingEntry(key); + return (e == null)? null : new AbstractMap.SimpleImmutableEntry(e); } /** - * 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 if 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 */ - public K higherKey(K key) { - Entry e = getHigherEntry(key); + public K ceilingKey(K key) { + Entry e = getCeilingEntry(key); return (e == null)? null : e.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 if 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 */ - public Map.Entry lowerEntry(K key) { - Entry e = getLowerEntry(key); - return (e == null)? null : new AbstractMap.SimpleImmutableEntry(e); + public Map.Entry higherEntry(K key) { + Entry e = getHigherEntry(key); + return (e == null)? null : new AbstractMap.SimpleImmutableEntry(e); } /** - * 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 if 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 */ - public K lowerKey(K key) { - Entry e = getLowerEntry(key); + public K higherKey(K key) { + Entry e = getHigherEntry(key); return (e == null)? null : e.key; } @@ -874,22 +770,21 @@ public class TreeMap */ 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 + private transient Set descendingKeySet = null; /** - * 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. + * 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; @@ -900,38 +795,40 @@ public class TreeMap 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(); } } /** - * 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. + * 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; @@ -942,18 +839,18 @@ public class TreeMap public Iterator iterator() { return new ValueIterator(getFirstEntry()); } - + public int size() { return TreeMap.this.size(); } - + public boolean contains(Object o) { for (Entry e = getFirstEntry(); e != null; e = successor(e)) if (valEquals(e.getValue(), o)) return true; return false; } - + public boolean remove(Object o) { for (Entry e = getFirstEntry(); e != null; e = successor(e)) { if (valEquals(e.getValue(), o)) { @@ -963,25 +860,26 @@ 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, + * 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. - * - * @return a set view of the mappings contained in this map. - * @see Map.Entry + * clear operations. It does not support the + * add or addAll operations. */ public Set> entrySet() { Set> es = entrySet; @@ -992,7 +890,7 @@ public class TreeMap public Iterator> iterator() { return new EntryIterator(getFirstEntry()); } - + public boolean contains(Object o) { if (!(o instanceof Map.Entry)) return false; @@ -1001,7 +899,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,32 +912,16 @@ 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 descending 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()); @@ -1051,19 +933,6 @@ public class TreeMap } } - /** - * 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. - */ public Set descendingKeySet() { Set ks = descendingKeySet; return (ks != null) ? ks : (descendingKeySet = new DescendingKeySet()); @@ -1076,196 +945,81 @@ public class TreeMap } /** - * 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 - * navigable map is empty.) The returned navigable map is backed - * by this map, so changes in the returned navigable map are - * reflected in this map, and vice-versa. The returned navigable - * map supports all optional map operations.

- * - * The navigable 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 of a given key, merely request the - * subrange from lowEndpoint to successor(highEndpoint). - * For example, suppose that m is a navigable 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.navigableSubMap(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.navigableSubMap(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 ClassCastException {@inheritDoc} * @throws NullPointerException if fromKey or toKey is - * null and this map uses natural order, or its - * comparator does not tolerate null keys. + * null and this map uses natural ordering, or its comparator + * does not permit null keys + * @throws IllegalArgumentException {@inheritDoc} */ public NavigableMap navigableSubMap(K fromKey, K toKey) { return new SubMap(fromKey, toKey); } - /** - * Returns a view of the portion of this map whose keys are strictly less - * than toKey. The returned navigable map is backed by this map, so - * changes in the returned navigable map are reflected in this map, and - * vice-versa. The returned navigable map supports all optional map - * operations.

- * - * The navigable 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 of a given key, - * merely request a headMap bounded by successor(highEndpoint). - * For example, suppose that suppose that m is a navigable 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. + * @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 NavigableMap navigableHeadMap(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 navigable map is backed by - * this map, so changes in the returned navigable map are reflected in this - * map, and vice-versa. The returned navigable map supports all optional map - * operations.

- * - * The navigable 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 of a given value, - * merely request a tailMap bounded by successor(lowEndpoint). - * For example, suppose that m is a navigable 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. + * @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 NavigableMap navigableTailMap(K fromKey) { return new SubMap(fromKey, false); } /** - * Equivalent to navigableSubMap but with a return - * type conforming to the SortedMap interface. - * @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. + * 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 order, or its - * comparator does not tolerate null keys. + * 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 new SubMap(fromKey, toKey); } - /** - * Equivalent to navigableHeadMap but with a return - * type conforming to the SortedMap interface. + * Equivalent to {@link #navigableHeadMap} but with a return type + * conforming to the SortedMap interface. + * + *

{@inheritDoc} * - * @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. + * @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 new SubMap(toKey, true); } /** - * Equivalent to navigableTailMap but with a return - * type conforming to the SortedMap interface. + * Equivalent to {@link #navigableTailMap} but with a return type + * conforming to the SortedMap interface. * - * @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. + *

{@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} */ public SortedMap tailMap(K fromKey) { return new SubMap(fromKey, false); @@ -1310,15 +1064,15 @@ public class TreeMap } public boolean isEmpty() { - return entrySet.isEmpty(); + return entrySet().isEmpty(); } public boolean containsKey(Object key) { - return inRange((K) key) && TreeMap.this.containsKey(key); + return inRange(key) && TreeMap.this.containsKey(key); } public V get(Object key) { - if (!inRange((K) key)) + if (!inRange(key)) return null; return TreeMap.this.get(key); } @@ -1330,7 +1084,7 @@ public class TreeMap } public V remove(Object key) { - if (!inRange((K) key)) + if (!inRange(key)) return null; return TreeMap.this.remove(key); } @@ -1343,7 +1097,7 @@ public class TreeMap TreeMap.Entry e = fromStart ? getFirstEntry() : getCeilingEntry(fromKey); K first = key(e); if (!toEnd && compare(first, toKey) >= 0) - throw(new NoSuchElementException()); + throw new NoSuchElementException(); return first; } @@ -1351,12 +1105,12 @@ public class TreeMap TreeMap.Entry e = toEnd ? getLastEntry() : getLowerEntry(toKey); K last = key(e); if (!fromStart && compare(last, fromKey) < 0) - throw(new NoSuchElementException()); + throw new NoSuchElementException(); return last; } public Map.Entry firstEntry() { - TreeMap.Entry e = fromStart ? + TreeMap.Entry e = fromStart ? getFirstEntry() : getCeilingEntry(fromKey); if (e == null || (!toEnd && compare(e.key, toKey) >= 0)) return null; @@ -1364,7 +1118,7 @@ public class TreeMap } public Map.Entry lastEntry() { - TreeMap.Entry e = toEnd ? + TreeMap.Entry e = toEnd ? getLastEntry() : getLowerEntry(toKey); if (e == null || (!fromStart && compare(e.key, fromKey) < 0)) return null; @@ -1372,21 +1126,21 @@ public class TreeMap } public Map.Entry pollFirstEntry() { - TreeMap.Entry e = fromStart ? + TreeMap.Entry e = fromStart ? getFirstEntry() : getCeilingEntry(fromKey); - if (e == null || (!fromStart && compare(e.key, fromKey) < 0)) + if (e == null || (!toEnd && compare(e.key, toKey) >= 0)) return null; - Map.Entry result = new AbstractMap.SimpleImmutableEntry(e); + Map.Entry result = new AbstractMap.SimpleImmutableEntry(e); deleteEntry(e); return result; } public Map.Entry pollLastEntry() { - TreeMap.Entry e = toEnd ? + TreeMap.Entry e = toEnd ? getLastEntry() : getLowerEntry(toKey); - if (e == null || (!toEnd && compare(e.key, toKey) >= 0)) + if (e == null || (!fromStart && compare(e.key, fromKey) < 0)) return null; - Map.Entry result = new AbstractMap.SimpleImmutableEntry(e); + Map.Entry result = new AbstractMap.SimpleImmutableEntry(e); deleteEntry(e); return result; } @@ -1401,7 +1155,7 @@ public class TreeMap public Map.Entry ceilingEntry(K key) { TreeMap.Entry e = subceiling(key); - return e == null? null : new AbstractMap.SimpleImmutableEntry(e); + return e == null? null : new AbstractMap.SimpleImmutableEntry(e); } public K ceilingKey(K key) { @@ -1420,7 +1174,7 @@ public class TreeMap public Map.Entry higherEntry(K key) { TreeMap.Entry e = subhigher(key); - return e == null? null : new AbstractMap.SimpleImmutableEntry(e); + return e == null? null : new AbstractMap.SimpleImmutableEntry(e); } public K higherKey(K key) { @@ -1438,7 +1192,7 @@ public class TreeMap public Map.Entry floorEntry(K key) { TreeMap.Entry e = subfloor(key); - return e == null? null : new AbstractMap.SimpleImmutableEntry(e); + return e == null? null : new AbstractMap.SimpleImmutableEntry(e); } public K floorKey(K key) { @@ -1456,7 +1210,7 @@ public class TreeMap public Map.Entry lowerEntry(K key) { TreeMap.Entry e = sublower(key); - return e == null? null : new AbstractMap.SimpleImmutableEntry(e); + return e == null? null : new AbstractMap.SimpleImmutableEntry(e); } public K lowerKey(K key) { @@ -1464,10 +1218,11 @@ public class TreeMap return e == null? null : e.key; } - private transient Set> entrySet = new EntrySetView(); + private transient Set> entrySet = null; public Set> entrySet() { - return entrySet; + Set> es = entrySet; + return (es != null)? es : (entrySet = new EntrySetView()); } private class EntrySetView extends AbstractSet> { @@ -1524,16 +1279,18 @@ public class TreeMap } private transient Set> descendingEntrySetView = null; - private transient Set descendingKeySetView = null; + private transient Set descendingKeySetView = null; public Set> descendingEntrySet() { Set> es = descendingEntrySetView; - return (es != null) ? es : (descendingEntrySetView = new DescendingEntrySetView()); + return (es != null) ? es : + (descendingEntrySetView = new DescendingEntrySetView()); } public Set descendingKeySet() { Set ks = descendingKeySetView; - return (ks != null) ? ks : (descendingKeySetView = new DescendingKeySetView()); + return (ks != null) ? ks : + (descendingKeySetView = new DescendingKeySetView()); } private class DescendingEntrySetView extends EntrySetView { @@ -1548,23 +1305,22 @@ public class TreeMap public Iterator iterator() { return new Iterator() { private Iterator> i = descendingEntrySet().iterator(); - + public boolean hasNext() { return i.hasNext(); } public K next() { return i.next().getKey(); } public void remove() { i.remove(); } }; } - + public int size() { return SubMap.this.size(); } - + public boolean contains(Object k) { return SubMap.this.containsKey(k); } } - public NavigableMap navigableSubMap(K fromKey, K toKey) { if (!inRange2(fromKey)) throw new IllegalArgumentException("fromKey out of range"); @@ -1585,7 +1341,6 @@ public class TreeMap return new SubMap(false, fromKey, toEnd, toKey); } - public SortedMap subMap(K fromKey, K toKey) { return navigableSubMap(fromKey, toKey); } @@ -1598,13 +1353,13 @@ public class TreeMap return navigableTailMap(fromKey); } - private boolean inRange(K key) { + private boolean inRange(Object key) { return (fromStart || compare(key, fromKey) >= 0) && (toEnd || compare(key, toKey) < 0); } // This form allows the high endpoint (as well as all legit keys) - private boolean inRange2(K key) { + private boolean inRange2(Object key) { return (fromStart || compare(key, fromKey) >= 0) && (toEnd || compare(key, toKey) <= 0); } @@ -1626,7 +1381,7 @@ public class TreeMap return next != null; } - Entry nextEntry() { + Entry nextEntry() { if (next == null) throw new NoSuchElementException(); if (modCount != expectedModCount) @@ -1653,7 +1408,6 @@ public class TreeMap EntryIterator(Entry first) { super(first); } - public Map.Entry next() { return nextEntry(); } @@ -1698,7 +1452,6 @@ public class TreeMap } } - /** * Base for Descending Iterators. */ @@ -1759,17 +1512,16 @@ public class TreeMap } - /** * Compares two keys using the correct comparison method for this TreeMap. */ - private int compare(K k1, K k2) { - return (comparator==null ? ((Comparable)k1).compareTo(k2) - : comparator.compare((K)k1, (K)k2)); + private int compare(Object k1, Object k2) { + return comparator==null ? ((Comparable)k1).compareTo((K)k2) + : comparator.compare((K)k1, (K)k2); } /** - * Test two values for equality. Differs from o1.equals(o2) only in + * Test two values for equality. Differs from o1.equals(o2) only in * that it copes with null o1 properly. */ private static boolean valEquals(Object o1, Object o2) { @@ -1805,7 +1557,7 @@ public class TreeMap /** * Returns the key. * - * @return the key. + * @return the key */ public K getKey() { return key; @@ -1814,7 +1566,7 @@ public class TreeMap /** * Returns the value associated with the key. * - * @return the value associated with the key. + * @return the value associated with the key */ public V getValue() { return value; @@ -1825,7 +1577,7 @@ public class TreeMap * value. * * @return the value associated with the key before this method was - * called. + * called */ public V setValue(V value) { V oldValue = this.value; @@ -2196,7 +1948,7 @@ public class TreeMap } /** Intended to be called only from TreeSet.addAll **/ - void addAllForTreeSet(SortedSet> set, V defaultVal) { + void addAllForTreeSet(SortedSet set, V defaultVal) { try { buildFromSorted(set.size(), set.iterator(), null, defaultVal); } catch (java.io.IOException cannotHappen) { @@ -2221,7 +1973,7 @@ public class TreeMap * to calling this method. * * @param size the number of keys (or key-value pairs) to be read from - * the iterator or stream. + * the iterator or stream * @param it If non-null, new entries are created from entries * or keys read from this iterator. * @param str If non-null, new entries are created from keys and @@ -2256,7 +2008,7 @@ public class TreeMap * @param level the current level of tree. Initial call should be 0. * @param lo the first element index of this subtree. Initial should be 0. * @param hi the last element index of this subtree. Initial should be - * size-1. + * size-1. * @param redLevel the level at which nodes should be red. * Must be equal to computeRedLevel for tree of this size. */ @@ -2340,5 +2092,4 @@ public class TreeMap level++; return level; } - }