--- jsr166/src/main/java/util/TreeMap.java 2004/12/31 13:00:33 1.2 +++ jsr166/src/main/java/util/TreeMap.java 2005/05/02 16:35:52 1.11 @@ -1,17 +1,17 @@ /* * %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; /** * 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 + * according to the natural order for the keys' class (see * Comparable), or by the comparator provided at creation time, * depending on which constructor is used.

* @@ -61,7 +61,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 @@ -203,7 +203,7 @@ public class TreeMap * 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 + * @throws NullPointerException if key is null and this map uses * natural ordering, or its comparator does not tolerate * null keys. */ @@ -260,9 +260,9 @@ public class TreeMap * @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 + * @throws ClassCastException if key cannot be compared with the keys * currently in the map. - * @throws NullPointerException key is null and this map uses + * @throws NullPointerException if key is null and this map uses * natural ordering, or its comparator does not tolerate * null keys. * @@ -343,7 +343,7 @@ public class TreeMap * 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 + * @throws NullPointerException if key is null and this map uses * natural order, or its comparator does not tolerate * * null keys. */ @@ -542,13 +542,13 @@ public class TreeMap * @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 + * @return the 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 + * @throws ClassCastException if key cannot be compared with the keys * currently in the map. - * @throws NullPointerException key is null and this map uses + * @throws NullPointerException if key is null and this map uses * natural order, or its comparator does not tolerate * null keys. */ @@ -559,7 +559,7 @@ public class TreeMap incrementSize(); root = new Entry(key, value, null); return null; - } + } while (true) { int cmp = compare(key, t.key); @@ -591,14 +591,14 @@ 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 + * @return the 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 + * @throws ClassCastException if key cannot be compared with the keys * currently in the map. - * @throws NullPointerException key is null and this map uses + * @throws NullPointerException if key is null and this map uses * natural order, or its comparator does not tolerate * null keys. */ @@ -658,8 +658,8 @@ public class TreeMap /** * 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 + * + * @return an Entry with least key, or null * if the map is empty. */ public Map.Entry firstEntry() { @@ -670,9 +670,7 @@ public class TreeMap /** * 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. */ @@ -684,13 +682,13 @@ public class TreeMap /** * 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); deleteEntry(p); @@ -700,13 +698,13 @@ public class TreeMap /** * 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); deleteEntry(p); @@ -716,14 +714,14 @@ public class TreeMap /** * 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. - * + * 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 + * @throws NullPointerException if key is null and this map uses * natural order, or its comparator does not tolerate * null keys. */ @@ -736,13 +734,13 @@ public class TreeMap /** * 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 + * @throws NullPointerException if key is null and this map uses * natural order, or its comparator does not tolerate * null keys. */ @@ -756,14 +754,14 @@ public class TreeMap /** * 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. - * + * 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 + * @throws NullPointerException if key is null and this map uses * natural order, or its comparator does not tolerate * null keys. */ @@ -776,13 +774,13 @@ public class TreeMap * 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 + * @throws NullPointerException if key is null and this map uses * natural order, or its comparator does not tolerate * null keys. */ @@ -794,14 +792,14 @@ 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. - * + * 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 + * @throws NullPointerException if key is null and this map uses * natural order, or its comparator does not tolerate * null keys. */ @@ -813,13 +811,13 @@ public class TreeMap /** * 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 + * @throws NullPointerException if key is null and this map uses * natural order, or its comparator does not tolerate * null keys. */ @@ -831,14 +829,14 @@ public class TreeMap /** * Returns a key-value mapping associated with the greatest * key strictly less than the given key, or null if there is no - * such entry. - * + * 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 + * @throws NullPointerException if key is null and this map uses * natural order, or its comparator does not tolerate * null keys. */ @@ -850,13 +848,13 @@ public class TreeMap /** * 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 + * @throws NullPointerException if key is null and this map uses * natural order, or its comparator does not tolerate * null keys. */ @@ -874,10 +872,7 @@ 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 @@ -900,21 +895,21 @@ 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(); } @@ -942,18 +937,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,7 +958,7 @@ public class TreeMap } return false; } - + public void clear() { TreeMap.this.clear(); } @@ -992,7 +987,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 +996,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,11 +1009,11 @@ public class TreeMap } return false; } - + public int size() { return TreeMap.this.size(); } - + public void clear() { TreeMap.this.clear(); } @@ -1026,7 +1021,7 @@ public class TreeMap /** * Returns a set view of the mappings contained in this map. The - * set's iterator returns the mappings in descrending key order. + * 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, @@ -1036,7 +1031,7 @@ public class TreeMap * operations. It does not support the add or * addAll operations. * - * @return a set view of the mappings contained in this map, in + * @return a set view of the mappings contained in this map, in * descending key order * @see Map.Entry */ @@ -1078,12 +1073,13 @@ 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 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.

+ * 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 sorted map returned by this method will throw an + * 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.

@@ -1091,18 +1087,18 @@ public class TreeMap * 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 + * 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 sorted map whose keys are + * 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.submap(low, high+"\0");
+ * 
  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.subMap(low+"\0", high);
+ * 
  NavigableMap sub = m.navigableSubMap(low+"\0", high);
* * @param fromKey low endpoint (inclusive) of the subMap. * @param toKey high endpoint (exclusive) of the subMap. @@ -1119,31 +1115,32 @@ public class TreeMap * null and this map uses natural order, or its * comparator does not tolerate null keys. */ - public NavigableMap subMap(K fromKey, K toKey) { + 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 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 + * 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 sorted map returned by this method will throw an + * 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 a given key, + * 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 sorted map whose + * 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");
+     *     NavigableMap head = m.navigableHeadMap(high+"\0");
      *
* * @param toKey high endpoint (exclusive) of the headMap. @@ -1160,30 +1157,30 @@ public class TreeMap * this map uses natural order, or its comparator does not * tolerate null keys. */ - public NavigableMap headMap(K toKey) { + 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 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 + * 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 sorted map returned by this method will throw an + * 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 a given value, + * 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 sorted map whose keys + * 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");
+     *     NavigableMap tail = m.navigableTailMap(low+"\0");
      *
* * @param fromKey low endpoint (inclusive) of the tailMap. @@ -1199,7 +1196,73 @@ public class TreeMap * this map uses natural order, or its comparator does not * tolerate null keys. */ - public NavigableMap tailMap(K fromKey) { + 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. + * @throws NullPointerException if fromKey or toKey is + * null and this map uses natural order, or its + * comparator does not tolerate null keys. + */ + 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. + * + * @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 SortedMap headMap(K toKey) { + return new SubMap(toKey, true); + } + + /** + * Equivalent to 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. + */ + public SortedMap tailMap(K fromKey) { return new SubMap(fromKey, false); } @@ -1242,7 +1305,7 @@ public class TreeMap } public boolean isEmpty() { - return entrySet.isEmpty(); + return entrySet().isEmpty(); } public boolean containsKey(Object key) { @@ -1275,7 +1338,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; } @@ -1283,12 +1346,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; @@ -1296,7 +1359,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; @@ -1304,9 +1367,9 @@ 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); deleteEntry(e); @@ -1314,9 +1377,9 @@ public class TreeMap } 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); deleteEntry(e); @@ -1396,10 +1459,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> { @@ -1456,7 +1520,7 @@ public class TreeMap } private transient Set> descendingEntrySetView = null; - private transient Set descendingKeySetView = null; + private transient Set descendingKeySetView = null; public Set> descendingEntrySet() { Set> es = descendingEntrySetView; @@ -1480,24 +1544,24 @@ 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 subMap(K fromKey, K toKey) { + public NavigableMap navigableSubMap(K fromKey, K toKey) { if (!inRange2(fromKey)) throw new IllegalArgumentException("fromKey out of range"); if (!inRange2(toKey)) @@ -1505,18 +1569,31 @@ public class TreeMap return new SubMap(fromKey, toKey); } - public NavigableMap headMap(K toKey) { + public NavigableMap navigableHeadMap(K toKey) { if (!inRange2(toKey)) throw new IllegalArgumentException("toKey out of range"); return new SubMap(fromStart, fromKey, false, toKey); } - public NavigableMap tailMap(K fromKey) { + public NavigableMap navigableTailMap(K fromKey) { if (!inRange2(fromKey)) throw new IllegalArgumentException("fromKey out of range"); return new SubMap(false, fromKey, toEnd, toKey); } + + public SortedMap subMap(K fromKey, K toKey) { + return navigableSubMap(fromKey, toKey); + } + + public SortedMap headMap(K toKey) { + return navigableHeadMap(toKey); + } + + public SortedMap tailMap(K fromKey) { + return navigableTailMap(fromKey); + } + private boolean inRange(K key) { return (fromStart || compare(key, fromKey) >= 0) && (toEnd || compare(key, toKey) < 0); @@ -2083,8 +2160,9 @@ public class TreeMap // Write out size (number of Mappings) s.writeInt(size); + Set> es = entrySet(); // Write out keys and values (alternating) - for (Iterator> i = entrySet().iterator(); i.hasNext(); ) { + for (Iterator> i = es.iterator(); i.hasNext(); ) { Map.Entry e = i.next(); s.writeObject(e.getKey()); s.writeObject(e.getValue());