--- jsr166/src/main/java/util/TreeMap.java 2004/12/31 13:00:33 1.2 +++ jsr166/src/main/java/util/TreeMap.java 2005/03/31 15:23:10 1.7 @@ -11,7 +11,7 @@ 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. */ @@ -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. */ @@ -670,8 +670,6 @@ 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. @@ -723,7 +721,7 @@ public class TreeMap * 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. */ @@ -742,7 +740,7 @@ public class TreeMap * 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. */ @@ -763,7 +761,7 @@ public class TreeMap * 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. */ @@ -782,7 +780,7 @@ public class TreeMap * 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. */ @@ -801,7 +799,7 @@ public class TreeMap * 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. */ @@ -819,7 +817,7 @@ public class TreeMap * 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. */ @@ -838,7 +836,7 @@ public class TreeMap * 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. */ @@ -856,7 +854,7 @@ public class TreeMap * 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. */ @@ -1026,7 +1024,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, @@ -1078,12 +1076,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 +1090,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 +1118,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 +1160,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 +1199,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 +1308,7 @@ public class TreeMap } public boolean isEmpty() { - return entrySet.isEmpty(); + return entrySet().isEmpty(); } public boolean containsKey(Object key) { @@ -1306,7 +1372,7 @@ public class TreeMap public Map.Entry pollFirstEntry() { 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); @@ -1316,7 +1382,7 @@ public class TreeMap public Map.Entry pollLastEntry() { 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 +1462,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> { @@ -1497,7 +1564,7 @@ public class TreeMap } - 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 +1572,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 +2163,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());