--- jsr166/src/main/java/util/TreeMap.java 2006/04/20 21:49:36 1.30 +++ jsr166/src/main/java/util/TreeMap.java 2007/01/30 03:54:29 1.42 @@ -1,7 +1,7 @@ /* * %W% %E% * - * Copyright 2006 Sun Microsystems, Inc. All rights reserved. + * Copyright 2007 Sun Microsystems, Inc. All rights reserved. * SUN PROPRIETARY/CONFIDENTIAL. Use is subject to license terms. */ @@ -68,7 +68,7 @@ package java.util; * associated map using put.) * *

This class is a member of the - * + * * Java Collections Framework. * * @param the type of keys maintained by this map @@ -95,7 +95,7 @@ public class TreeMap * * @serial */ - private Comparator comparator = null; + private final Comparator comparator; private transient Entry root = null; @@ -109,9 +109,6 @@ public class TreeMap */ private transient int modCount = 0; - private void incrementSize() { modCount++; size++; } - private void decrementSize() { modCount++; size--; } - /** * Constructs a new, empty tree map, using the natural ordering of its * keys. All keys inserted into the map must implement the {@link @@ -125,6 +122,7 @@ public class TreeMap * ClassCastException. */ public TreeMap() { + comparator = null; } /** @@ -160,6 +158,7 @@ public class TreeMap * @throws NullPointerException if the specified map is null */ public TreeMap(Map m) { + comparator = null; putAll(m); } @@ -224,28 +223,10 @@ public class TreeMap * @since 1.2 */ public boolean containsValue(Object value) { - return (root==null ? false : - (value==null ? valueSearchNull(root) - : valueSearchNonNull(root, value))); - } - - private boolean valueSearchNull(Entry n) { - if (n.value == null) - return true; - - // Check left and right subtrees for value - return (n.left != null && valueSearchNull(n.left)) || - (n.right != null && valueSearchNull(n.right)); - } - - private boolean valueSearchNonNull(Entry n, Object value) { - // Check this node for the value - if (value.equals(n.value)) - return true; - - // Check left and right subtrees for value - return (n.left != null && valueSearchNonNull(n.left, value)) || - (n.right != null && valueSearchNonNull(n.right, value)); + for (Entry e = getFirstEntry(); e != null; e = successor(e)) + if (valEquals(value, e.value)) + return true; + return false; } /** @@ -364,15 +345,17 @@ public class TreeMap final Entry getEntryUsingComparator(Object key) { K k = (K) key; Comparator cpr = comparator; - Entry p = root; - while (p != null) { - int cmp = cpr.compare(k, p.key); - if (cmp < 0) - p = p.left; - else if (cmp > 0) - p = p.right; - else - return p; + if (cpr != null) { + Entry p = root; + while (p != null) { + int cmp = cpr.compare(k, p.key); + if (cmp < 0) + p = p.left; + else if (cmp > 0) + p = p.right; + else + return p; + } } return null; } @@ -385,10 +368,7 @@ public class TreeMap */ final Entry getCeilingEntry(K key) { Entry p = root; - if (p==null) - return null; - - while (true) { + while (p != null) { int cmp = compare(key, p.key); if (cmp < 0) { if (p.left != null) @@ -410,6 +390,7 @@ public class TreeMap } else return p; } + return null; } /** @@ -419,10 +400,7 @@ public class TreeMap */ final Entry getFloorEntry(K key) { Entry p = root; - if (p==null) - return null; - - while (true) { + while (p != null) { int cmp = compare(key, p.key); if (cmp > 0) { if (p.right != null) @@ -445,6 +423,7 @@ public class TreeMap return p; } + return null; } /** @@ -455,10 +434,7 @@ public class TreeMap */ final Entry getHigherEntry(K key) { Entry p = root; - if (p==null) - return null; - - while (true) { + while (p != null) { int cmp = compare(key, p.key); if (cmp < 0) { if (p.left != null) @@ -479,6 +455,7 @@ public class TreeMap } } } + return null; } /** @@ -488,10 +465,7 @@ public class TreeMap */ final Entry getLowerEntry(K key) { Entry p = root; - if (p==null) - return null; - - while (true) { + while (p != null) { int cmp = compare(key, p.key); if (cmp > 0) { if (p.right != null) @@ -512,16 +486,7 @@ public class TreeMap } } } - } - - /** - * Returns the key corresponding to the specified Entry. - * @throws NoSuchElementException if the Entry is null - */ - static K key(Entry e) { - if (e==null) - throw new NoSuchElementException(); - return e.key; + return null; } /** @@ -544,43 +509,57 @@ public class TreeMap */ public V put(K key, V value) { Entry t = root; - if (t == null) { - // TBD - // if (key == null) { - // if (comparator == null) - // throw new NullPointerException(); - // comparator.compare(key, key); - // } - incrementSize(); + // TBD: + // 5045147: (coll) Adding null to an empty TreeSet should + // throw NullPointerException + // + // compare(key, key); // type check root = new Entry(key, value, null); + size = 1; + modCount++; return null; } - - while (true) { - int cmp = compare(key, t.key); - if (cmp == 0) { - return t.setValue(value); - } else if (cmp < 0) { - if (t.left != null) { + int cmp; + Entry parent; + // split comparator and comparable paths + Comparator cpr = comparator; + if (cpr != null) { + do { + parent = t; + cmp = cpr.compare(key, t.key); + if (cmp < 0) t = t.left; - } else { - incrementSize(); - t.left = new Entry(key, value, t); - fixAfterInsertion(t.left); - return null; - } - } else { // cmp > 0 - if (t.right != null) { + else if (cmp > 0) t = t.right; - } else { - incrementSize(); - t.right = new Entry(key, value, t); - fixAfterInsertion(t.right); - return null; - } - } + else + return t.setValue(value); + } while (t != null); + } + else { + if (key == null) + throw new NullPointerException(); + Comparable k = (Comparable) key; + do { + parent = t; + cmp = k.compareTo(t.key); + if (cmp < 0) + t = t.left; + else if (cmp > 0) + t = t.right; + else + return t.setValue(value); + } while (t != null); } + Entry e = new Entry(key, value, parent); + if (cmp < 0) + parent.left = e; + else + parent.right = e; + fixAfterInsertion(e); + size++; + modCount++; + return null; } /** @@ -655,16 +634,14 @@ public class TreeMap * @since 1.6 */ public Map.Entry firstEntry() { - Entry e = getFirstEntry(); - return (e == null)? null : new AbstractMap.SimpleImmutableEntry(e); + return exportEntry(getFirstEntry()); } /** * @since 1.6 */ public Map.Entry lastEntry() { - Entry e = getLastEntry(); - return (e == null)? null : new AbstractMap.SimpleImmutableEntry(e); + return exportEntry(getLastEntry()); } /** @@ -672,10 +649,9 @@ public class TreeMap */ public Map.Entry pollFirstEntry() { Entry p = getFirstEntry(); - if (p == null) - return null; - Map.Entry result = new AbstractMap.SimpleImmutableEntry(p); - deleteEntry(p); + Map.Entry result = exportEntry(p); + if (p != null) + deleteEntry(p); return result; } @@ -684,10 +660,9 @@ public class TreeMap */ public Map.Entry pollLastEntry() { Entry p = getLastEntry(); - if (p == null) - return null; - Map.Entry result = new AbstractMap.SimpleImmutableEntry(p); - deleteEntry(p); + Map.Entry result = exportEntry(p); + if (p != null) + deleteEntry(p); return result; } @@ -699,8 +674,7 @@ public class TreeMap * @since 1.6 */ public Map.Entry lowerEntry(K key) { - Entry e = getLowerEntry(key); - return (e == null)? null : new AbstractMap.SimpleImmutableEntry(e); + return exportEntry(getLowerEntry(key)); } /** @@ -711,8 +685,7 @@ public class TreeMap * @since 1.6 */ public K lowerKey(K key) { - Entry e = getLowerEntry(key); - return (e == null)? null : e.key; + return keyOrNull(getLowerEntry(key)); } /** @@ -723,8 +696,7 @@ public class TreeMap * @since 1.6 */ public Map.Entry floorEntry(K key) { - Entry e = getFloorEntry(key); - return (e == null)? null : new AbstractMap.SimpleImmutableEntry(e); + return exportEntry(getFloorEntry(key)); } /** @@ -735,8 +707,7 @@ public class TreeMap * @since 1.6 */ public K floorKey(K key) { - Entry e = getFloorEntry(key); - return (e == null)? null : e.key; + return keyOrNull(getFloorEntry(key)); } /** @@ -747,8 +718,7 @@ public class TreeMap * @since 1.6 */ public Map.Entry ceilingEntry(K key) { - Entry e = getCeilingEntry(key); - return (e == null)? null : new AbstractMap.SimpleImmutableEntry(e); + return exportEntry(getCeilingEntry(key)); } /** @@ -759,8 +729,7 @@ public class TreeMap * @since 1.6 */ public K ceilingKey(K key) { - Entry e = getCeilingEntry(key); - return (e == null)? null : e.key; + return keyOrNull(getCeilingEntry(key)); } /** @@ -771,8 +740,7 @@ public class TreeMap * @since 1.6 */ public Map.Entry higherEntry(K key) { - Entry e = getHigherEntry(key); - return (e == null)? null : new AbstractMap.SimpleImmutableEntry(e); + return exportEntry(getHigherEntry(key)); } /** @@ -783,8 +751,7 @@ public class TreeMap * @since 1.6 */ public K higherKey(K key) { - Entry e = getHigherEntry(key); - return (e == null)? null : e.key; + return keyOrNull(getHigherEntry(key)); } // Views @@ -878,8 +845,8 @@ public class TreeMap NavigableMap km = descendingMap; return (km != null) ? km : (descendingMap = new DescendingSubMap(this, - true, null, 0, - true, null, 0)); + true, null, true, + true, null, true)); } /** @@ -893,8 +860,8 @@ public class TreeMap public NavigableMap subMap(K fromKey, boolean fromInclusive, K toKey, boolean toInclusive) { return new AscendingSubMap(this, - false, fromKey, excluded(fromInclusive), - false, toKey, excluded(toInclusive)); + false, fromKey, fromInclusive, + false, toKey, toInclusive); } /** @@ -907,8 +874,8 @@ public class TreeMap */ public NavigableMap headMap(K toKey, boolean inclusive) { return new AscendingSubMap(this, - true, null, 0, - false, toKey, excluded(inclusive)); + true, null, true, + false, toKey, inclusive); } /** @@ -921,16 +888,8 @@ public class TreeMap */ public NavigableMap tailMap(K fromKey, boolean inclusive) { return new AscendingSubMap(this, - false, fromKey, excluded(inclusive), - true, null, 0); - } - - /** - * Translates a boolean "inclusive" value to the correct int value - * for the loExcluded or hiExcluded field. - */ - static int excluded(boolean inclusive) { - return inclusive ? 0 : 1; + false, fromKey, inclusive, + true, null, true); } /** @@ -978,10 +937,7 @@ public class TreeMap } public boolean contains(Object o) { - for (Entry e = getFirstEntry(); e != null; e = successor(e)) - if (valEquals(e.getValue(), o)) - return true; - return false; + return TreeMap.this.containsValue(o); } public boolean remove(Object o) { @@ -1093,13 +1049,10 @@ public class TreeMap m.remove(o); return size() != oldSize; } - public NavigableSet subSet(E fromElement, - boolean fromInclusive, - E toElement, - boolean toInclusive) { - return new TreeSet - (m.subMap(fromElement, fromInclusive, - toElement, toInclusive)); + public NavigableSet subSet(E fromElement, boolean fromInclusive, + E toElement, boolean toInclusive) { + return new TreeSet(m.subMap(fromElement, fromInclusive, + toElement, toInclusive)); } public NavigableSet headSet(E toElement, boolean inclusive) { return new TreeSet(m.headMap(toElement, inclusive)); @@ -1125,11 +1078,13 @@ public class TreeMap * Base class for TreeMap Iterators */ abstract class PrivateEntryIterator implements Iterator { - int expectedModCount = TreeMap.this.modCount; - Entry lastReturned = null; Entry next; + Entry lastReturned; + int expectedModCount; PrivateEntryIterator(Entry first) { + expectedModCount = modCount; + lastReturned = null; next = first; } @@ -1138,23 +1093,23 @@ public class TreeMap } final Entry nextEntry() { - if (next == null) + Entry e = lastReturned = next; + if (e == null) throw new NoSuchElementException(); if (modCount != expectedModCount) throw new ConcurrentModificationException(); - lastReturned = next; - next = successor(next); - return lastReturned; + next = successor(e); + return e; } final Entry prevEntry() { - if (next == null) + Entry e = lastReturned= next; + if (e == null) throw new NoSuchElementException(); if (modCount != expectedModCount) throw new ConcurrentModificationException(); - lastReturned = next; - next = predecessor(next); - return lastReturned; + next = predecessor(e); + return e; } public void remove() { @@ -1162,10 +1117,11 @@ public class TreeMap throw new IllegalStateException(); if (modCount != expectedModCount) throw new ConcurrentModificationException(); + // deleted entries are replaced by their successors if (lastReturned.left != null && lastReturned.right != null) next = lastReturned; deleteEntry(lastReturned); - expectedModCount++; + expectedModCount = modCount; lastReturned = null; } } @@ -1206,65 +1162,124 @@ public class TreeMap } } - // SubMaps + // Little utilities - static abstract class NavigableSubMap extends AbstractMap - implements NavigableMap, java.io.Serializable { + /** + * Compares two keys using the correct comparison method for this TreeMap. + */ + final int compare(Object k1, Object k2) { + return comparator==null ? ((Comparable)k1).compareTo((K)k2) + : comparator.compare((K)k1, (K)k2); + } - /* - * The backing map. - */ - final TreeMap m; + /** + * Test two values for equality. Differs from o1.equals(o2) only in + * that it copes with null o1 properly. + */ + final static boolean valEquals(Object o1, Object o2) { + return (o1==null ? o2==null : o1.equals(o2)); + } - /** True if low point is from start of backing map */ - boolean fromStart; + /** + * Return SimpleImmutableEntry for entry, or null if null + */ + static Map.Entry exportEntry(TreeMap.Entry e) { + return e == null? null : + new AbstractMap.SimpleImmutableEntry(e); + } - /** - * The low endpoint of this submap in absolute terms, or null - * if fromStart. - */ - K lo; + /** + * Return key for entry, or null if null + */ + static K keyOrNull(TreeMap.Entry e) { + return e == null? null : e.key; + } + + /** + * Returns the key corresponding to the specified Entry. + * @throws NoSuchElementException if the Entry is null + */ + static K key(Entry e) { + if (e==null) + throw new NoSuchElementException(); + return e.key; + } - /** - * Zero if the low endpoint is excluded from this submap, one if - * it's included. This field is unused if fromStart. - */ - int loExcluded; - /** True if high point is to End of backing map */ - boolean toEnd; + // SubMaps + + /** + * Dummy value serving as unmatchable fence key for unbounded + * SubMapIterators + */ + private static final Object UNBOUNDED = new Object(); + /** + * @serial include + */ + static abstract class NavigableSubMap extends AbstractMap + implements NavigableMap, java.io.Serializable { /** - * The high endpoint of this submap in absolute terms, or null - * if toEnd. + * The backing map. */ - K hi; + final TreeMap m; /** - * Zero if the high endpoint is excluded from this submap, one if - * it's included. This field is unused if toEnd. + * Endpoints are represented as triples (fromStart, lo, + * loInclusive) and (toEnd, hi, hiInclusive). If fromStart is + * true, then the low (absolute) bound is the start of the + * backing map, and the other values are ignored. Otherwise, + * if loInclusive is true, lo is the inclusive bound, else lo + * is the exclusive bound. Similarly for the upper bound. */ - int hiExcluded; + final K lo, hi; + final boolean fromStart, toEnd; + final boolean loInclusive, hiInclusive; NavigableSubMap(TreeMap m, - boolean fromStart, K lo, int loExcluded, - boolean toEnd, K hi, int hiExcluded) { - if (!fromStart && !toEnd && m.compare(lo, hi) > 0) - throw new IllegalArgumentException("fromKey > toKey"); + boolean fromStart, K lo, boolean loInclusive, + boolean toEnd, K hi, boolean hiInclusive) { + if (!fromStart && !toEnd) { + if (m.compare(lo, hi) > 0) + throw new IllegalArgumentException("fromKey > toKey"); + } else { + if (!fromStart) // type check + m.compare(lo, lo); + if (!toEnd) + m.compare(hi, hi); + } + this.m = m; this.fromStart = fromStart; this.lo = lo; - this.loExcluded = loExcluded; + this.loInclusive = loInclusive; this.toEnd = toEnd; this.hi = hi; - this.hiExcluded = hiExcluded; + this.hiInclusive = hiInclusive; } // internal utilities + final boolean tooLow(Object key) { + if (!fromStart) { + int c = m.compare(key, lo); + if (c < 0 || (c == 0 && !loInclusive)) + return true; + } + return false; + } + + final boolean tooHigh(Object key) { + if (!toEnd) { + int c = m.compare(key, hi); + if (c > 0 || (c == 0 && !hiInclusive)) + return true; + } + return false; + } + final boolean inRange(Object key) { - return (fromStart || m.compare(key, lo) >= loExcluded) - && (toEnd || m.compare(hi, key) >= hiExcluded); + return !tooLow(key) && !tooHigh(key); } final boolean inClosedRange(Object key) { @@ -1276,149 +1291,176 @@ public class TreeMap return inclusive ? inRange(key) : inClosedRange(key); } - final boolean tooLow(K key) { - return !fromStart && m.compare(key, lo) < loExcluded; - } - - final boolean tooHigh(K key) { - return !toEnd && m.compare(hi, key) < hiExcluded; - } - + /* + * Absolute versions of relation operations. + * Subclasses map to these using like-named "sub" + * versions that invert senses for descending maps + */ - /** Returns the lowest entry in this submap (absolute ordering) */ - final TreeMap.Entry loEntry() { - TreeMap.Entry result = + final TreeMap.Entry absLowest() { + TreeMap.Entry e = (fromStart ? m.getFirstEntry() : - (loExcluded == 0 ? m.getCeilingEntry(lo) : - m.getHigherEntry(lo))); - return (result == null || tooHigh(result.key)) ? null : result; + (loInclusive ? m.getCeilingEntry(lo) : + m.getHigherEntry(lo))); + return (e == null || tooHigh(e.key)) ? null : e; } - /** Returns the highest key in this submap (absolute ordering) */ - final TreeMap.Entry hiEntry() { - TreeMap.Entry result = + final TreeMap.Entry absHighest() { + TreeMap.Entry e = (toEnd ? m.getLastEntry() : - (hiExcluded == 0 ? m.getFloorEntry(hi) : - m.getLowerEntry(hi))); - return (result == null || tooLow(result.key)) ? null : result; + (hiInclusive ? m.getFloorEntry(hi) : + m.getLowerEntry(hi))); + return (e == null || tooLow(e.key)) ? null : e; } - /** Polls the lowest entry in this submap (absolute ordering) */ - final Map.Entry pollLoEntry() { - TreeMap.Entry e = loEntry(); - if (e == null) - return null; - Map.Entry result = new AbstractMap.SimpleImmutableEntry(e); - m.deleteEntry(e); - return result; + final TreeMap.Entry absCeiling(K key) { + if (tooLow(key)) + return absLowest(); + TreeMap.Entry e = m.getCeilingEntry(key); + return (e == null || tooHigh(e.key)) ? null : e; } - /** Polls the highest key in this submap (absolute ordering) */ - final Map.Entry pollHiEntry() { - TreeMap.Entry e = hiEntry(); - if (e == null) - return null; - Map.Entry result = new AbstractMap.SimpleImmutableEntry(e); - m.deleteEntry(e); - return result; + final TreeMap.Entry absHigher(K key) { + if (tooLow(key)) + return absLowest(); + TreeMap.Entry e = m.getHigherEntry(key); + return (e == null || tooHigh(e.key)) ? null : e; } - /** - * Return the absolute high fence for ascending traversal - */ - final TreeMap.Entry hiFence() { - if (toEnd) - return null; - else if (hiExcluded == 0) - return m.getHigherEntry(hi); - else - return m.getCeilingEntry(hi); + final TreeMap.Entry absFloor(K key) { + if (tooHigh(key)) + return absHighest(); + TreeMap.Entry e = m.getFloorEntry(key); + return (e == null || tooLow(e.key)) ? null : e; } - /** - * Return the absolute low fence for descending traversal - */ - final TreeMap.Entry loFence() { - if (fromStart) - return null; - else if (loExcluded == 0) - return m.getLowerEntry(lo); - else - return m.getFloorEntry(lo); + final TreeMap.Entry absLower(K key) { + if (tooHigh(key)) + return absHighest(); + TreeMap.Entry e = m.getLowerEntry(key); + return (e == null || tooLow(e.key)) ? null : e; } + /** Returns the absolute high fence for ascending traversal */ + final TreeMap.Entry absHighFence() { + return (toEnd ? null : (hiInclusive ? + m.getHigherEntry(hi) : + m.getCeilingEntry(hi))); + } + + /** Return the absolute low fence for descending traversal */ + final TreeMap.Entry absLowFence() { + return (fromStart ? null : (loInclusive ? + m.getLowerEntry(lo) : + m.getFloorEntry(lo))); + } + + // Abstract methods defined in ascending vs descending classes + // These relay to the appropriate absolute versions + + abstract TreeMap.Entry subLowest(); + abstract TreeMap.Entry subHighest(); + abstract TreeMap.Entry subCeiling(K key); + abstract TreeMap.Entry subHigher(K key); + abstract TreeMap.Entry subFloor(K key); + abstract TreeMap.Entry subLower(K key); + + /** Returns ascending iterator from the perspective of this submap */ + abstract Iterator keyIterator(); + + /** Returns descending iterator from the perspective of this submap */ + abstract Iterator descendingKeyIterator(); + + // public methods public boolean isEmpty() { - return entrySet().isEmpty(); + return (fromStart && toEnd) ? m.isEmpty() : entrySet().isEmpty(); } - public boolean containsKey(Object key) { - return inRange(key) && m.containsKey(key); + public int size() { + return (fromStart && toEnd) ? m.size() : entrySet().size(); } - public V get(Object key) { - if (!inRange(key)) - return null; - return m.get(key); + public final boolean containsKey(Object key) { + return inRange(key) && m.containsKey(key); } - public V put(K key, V value) { + public final V put(K key, V value) { if (!inRange(key)) throw new IllegalArgumentException("key out of range"); return m.put(key, value); } - public V remove(Object key) { - if (!inRange(key)) - return null; - return m.remove(key); + public final V get(Object key) { + return !inRange(key)? null : m.get(key); } - public Map.Entry ceilingEntry(K key) { - TreeMap.Entry e = subCeiling(key); - return e == null? null : new AbstractMap.SimpleImmutableEntry(e); + public final V remove(Object key) { + return !inRange(key)? null : m.remove(key); } - public K ceilingKey(K key) { - TreeMap.Entry e = subCeiling(key); - return e == null? null : e.key; + public final Map.Entry ceilingEntry(K key) { + return exportEntry(subCeiling(key)); } - public Map.Entry higherEntry(K key) { - TreeMap.Entry e = subHigher(key); - return e == null? null : new AbstractMap.SimpleImmutableEntry(e); + public final K ceilingKey(K key) { + return keyOrNull(subCeiling(key)); } - public K higherKey(K key) { - TreeMap.Entry e = subHigher(key); - return e == null? null : e.key; + public final Map.Entry higherEntry(K key) { + return exportEntry(subHigher(key)); } - public Map.Entry floorEntry(K key) { - TreeMap.Entry e = subFloor(key); - return e == null? null : new AbstractMap.SimpleImmutableEntry(e); + public final K higherKey(K key) { + return keyOrNull(subHigher(key)); } - public K floorKey(K key) { - TreeMap.Entry e = subFloor(key); - return e == null? null : e.key; + public final Map.Entry floorEntry(K key) { + return exportEntry(subFloor(key)); } - public Map.Entry lowerEntry(K key) { - TreeMap.Entry e = subLower(key); - return e == null? null : new AbstractMap.SimpleImmutableEntry(e); + public final K floorKey(K key) { + return keyOrNull(subFloor(key)); } - public K lowerKey(K key) { - TreeMap.Entry e = subLower(key); - return e == null? null : e.key; + public final Map.Entry lowerEntry(K key) { + return exportEntry(subLower(key)); } - abstract Iterator keyIterator(); - abstract Iterator descendingKeyIterator(); + public final K lowerKey(K key) { + return keyOrNull(subLower(key)); + } - public NavigableSet descendingKeySet() { - return descendingMap().navigableKeySet(); + public final K firstKey() { + return key(subLowest()); + } + + public final K lastKey() { + return key(subHighest()); + } + + public final Map.Entry firstEntry() { + return exportEntry(subLowest()); + } + + public final Map.Entry lastEntry() { + return exportEntry(subHighest()); + } + + public final Map.Entry pollFirstEntry() { + TreeMap.Entry e = subLowest(); + Map.Entry result = exportEntry(e); + if (e != null) + m.deleteEntry(e); + return result; + } + + public final Map.Entry pollLastEntry() { + TreeMap.Entry e = subHighest(); + Map.Entry result = exportEntry(e); + if (e != null) + m.deleteEntry(e); + return result; } // Views @@ -1426,6 +1468,34 @@ public class TreeMap transient EntrySetView entrySetView = null; transient KeySet navigableKeySetView = null; + public final NavigableSet navigableKeySet() { + KeySet nksv = navigableKeySetView; + return (nksv != null) ? nksv : + (navigableKeySetView = new TreeMap.KeySet(this)); + } + + public final Set keySet() { + return navigableKeySet(); + } + + public NavigableSet descendingKeySet() { + return descendingMap().navigableKeySet(); + } + + public final SortedMap subMap(K fromKey, K toKey) { + return subMap(fromKey, true, toKey, false); + } + + public final SortedMap headMap(K toKey) { + return headMap(toKey, false); + } + + public final SortedMap tailMap(K fromKey) { + return tailMap(fromKey, true); + } + + // View classes + abstract class EntrySetView extends AbstractSet> { private transient int size = -1, sizeModCount; @@ -1445,7 +1515,7 @@ public class TreeMap } public boolean isEmpty() { - TreeMap.Entry n = loEntry(); + TreeMap.Entry n = absLowest(); return n == null || tooHigh(n.key); } @@ -1477,184 +1547,136 @@ public class TreeMap } } - public NavigableSet navigableKeySet() { - KeySet nksv = navigableKeySetView; - return (nksv != null) ? nksv : - (navigableKeySetView = new TreeMap.KeySet(this)); - } - - public Set keySet() { - return navigableKeySet(); - } - - public SortedMap subMap(K fromKey, K toKey) { - return subMap(fromKey, true, toKey, false); - } - - public SortedMap headMap(K toKey) { - return headMap(toKey, false); - } - - public SortedMap tailMap(K fromKey) { - return tailMap(fromKey, true); - } - - - // The following four definitions are correct only for - // ascending submaps. They are overridden in DescendingSubMap. - // They are defined in the base class because the definitions - // in DescendingSubMap rely on those for AscendingSubMap. - - /** - * Returns the entry corresponding to the ceiling of the specified - * key from the perspective of this submap, or null if the submap - * contains no such entry. - */ - TreeMap.Entry subCeiling(K key) { - if (tooLow(key)) - return loEntry(); - TreeMap.Entry e = m.getCeilingEntry(key); - return (e == null || tooHigh(e.key)) ? null : e; - } - - /** - * Returns the entry corresponding to the higher of the specified - * key from the perspective of this submap, or null if the submap - * contains no such entry. - */ - TreeMap.Entry subHigher(K key) { - if (tooLow(key)) - return loEntry(); - TreeMap.Entry e = m.getHigherEntry(key); - return (e == null || tooHigh(e.key)) ? null : e; - } - - /** - * Returns the entry corresponding to the floor of the specified - * key from the perspective of this submap, or null if the submap - * contains no such entry. - */ - TreeMap.Entry subFloor(K key) { - if (tooHigh(key)) - return hiEntry(); - TreeMap.Entry e = m.getFloorEntry(key); - return (e == null || tooLow(e.key)) ? null : e; - } - - /** - * Returns the entry corresponding to the lower of the specified - * key from the perspective of this submap, or null if the submap - * contains no such entry. - */ - TreeMap.Entry subLower(K key) { - if (tooHigh(key)) - return hiEntry(); - TreeMap.Entry e = m.getLowerEntry(key); - return (e == null || tooLow(e.key)) ? null : e; - } - /** * Iterators for SubMaps */ abstract class SubMapIterator implements Iterator { - int expectedModCount = m.modCount; - TreeMap.Entry lastReturned = null; + TreeMap.Entry lastReturned; TreeMap.Entry next; - final K firstExcludedKey; + final Object fenceKey; + int expectedModCount; SubMapIterator(TreeMap.Entry first, - TreeMap.Entry firstExcluded) { + TreeMap.Entry fence) { + expectedModCount = m.modCount; + lastReturned = null; next = first; - firstExcludedKey = (firstExcluded == null ? null - : firstExcluded.key); + fenceKey = fence == null ? UNBOUNDED : fence.key; } public final boolean hasNext() { - return next != null && next.key != firstExcludedKey; + return next != null && next.key != fenceKey; } final TreeMap.Entry nextEntry() { - if (next == null || next.key == firstExcludedKey) + TreeMap.Entry e = lastReturned = next; + if (e == null || e.key == fenceKey) throw new NoSuchElementException(); if (m.modCount != expectedModCount) throw new ConcurrentModificationException(); - lastReturned = next; - next = m.successor(next); - return lastReturned; + next = successor(e); + return e; } final TreeMap.Entry prevEntry() { - if (next == null || next.key == firstExcludedKey) + TreeMap.Entry e = lastReturned = next; + if (e == null || e.key == fenceKey) throw new NoSuchElementException(); if (m.modCount != expectedModCount) throw new ConcurrentModificationException(); - lastReturned = next; - next = m.predecessor(next); - return lastReturned; + next = predecessor(e); + return e; } - public void remove() { + final void removeAscending() { if (lastReturned == null) throw new IllegalStateException(); if (m.modCount != expectedModCount) throw new ConcurrentModificationException(); + // deleted entries are replaced by their successors if (lastReturned.left != null && lastReturned.right != null) next = lastReturned; m.deleteEntry(lastReturned); - expectedModCount++; lastReturned = null; + expectedModCount = m.modCount; + } + + final void removeDescending() { + if (lastReturned == null) + throw new IllegalStateException(); + if (m.modCount != expectedModCount) + throw new ConcurrentModificationException(); + m.deleteEntry(lastReturned); + lastReturned = null; + expectedModCount = m.modCount; } + } final class SubMapEntryIterator extends SubMapIterator> { SubMapEntryIterator(TreeMap.Entry first, - TreeMap.Entry firstExcluded) { - super(first, firstExcluded); + TreeMap.Entry fence) { + super(first, fence); } public Map.Entry next() { return nextEntry(); } + public void remove() { + removeAscending(); + } } final class SubMapKeyIterator extends SubMapIterator { SubMapKeyIterator(TreeMap.Entry first, - TreeMap.Entry firstExcluded) { - super(first, firstExcluded); + TreeMap.Entry fence) { + super(first, fence); } public K next() { return nextEntry().key; } + public void remove() { + removeAscending(); + } } final class DescendingSubMapEntryIterator extends SubMapIterator> { DescendingSubMapEntryIterator(TreeMap.Entry last, - TreeMap.Entry lastExcluded) { - super(last, lastExcluded); + TreeMap.Entry fence) { + super(last, fence); } public Map.Entry next() { return prevEntry(); } + public void remove() { + removeDescending(); + } } final class DescendingSubMapKeyIterator extends SubMapIterator { DescendingSubMapKeyIterator(TreeMap.Entry last, - TreeMap.Entry lastExcluded) { - super(last, lastExcluded); + TreeMap.Entry fence) { + super(last, fence); } public K next() { return prevEntry().key; } + public void remove() { + removeDescending(); + } } } - static class AscendingSubMap extends NavigableSubMap { + /** + * @serial include + */ + static final class AscendingSubMap extends NavigableSubMap { private static final long serialVersionUID = 912986545866124060L; AscendingSubMap(TreeMap m, - boolean fromStart, K lo, int loExcluded, - boolean toEnd, K hi, int hiExcluded) { - super(m, fromStart, lo, loExcluded, toEnd, hi, hiExcluded); + boolean fromStart, K lo, boolean loInclusive, + boolean toEnd, K hi, boolean hiInclusive) { + super(m, fromStart, lo, loInclusive, toEnd, hi, hiInclusive); } public Comparator comparator() { @@ -1662,43 +1684,52 @@ public class TreeMap } public NavigableMap subMap(K fromKey, boolean fromInclusive, - K toKey, boolean toInclusive) { + K toKey, boolean toInclusive) { if (!inRange(fromKey, fromInclusive)) throw new IllegalArgumentException("fromKey out of range"); if (!inRange(toKey, toInclusive)) throw new IllegalArgumentException("toKey out of range"); return new AscendingSubMap(m, - false, fromKey, excluded(fromInclusive), - false, toKey, excluded(toInclusive)); + false, fromKey, fromInclusive, + false, toKey, toInclusive); } public NavigableMap headMap(K toKey, boolean inclusive) { - if (!inClosedRange(toKey)) + if (!inRange(toKey, inclusive)) throw new IllegalArgumentException("toKey out of range"); return new AscendingSubMap(m, - fromStart, lo, loExcluded, - false, toKey, excluded(inclusive)); + fromStart, lo, loInclusive, + false, toKey, inclusive); } public NavigableMap tailMap(K fromKey, boolean inclusive){ if (!inRange(fromKey, inclusive)) throw new IllegalArgumentException("fromKey out of range"); return new AscendingSubMap(m, - false, fromKey, excluded(inclusive), - toEnd, hi, hiExcluded); + false, fromKey, inclusive, + toEnd, hi, hiInclusive); + } + + public NavigableMap descendingMap() { + NavigableMap mv = descendingMapView; + return (mv != null) ? mv : + (descendingMapView = + new DescendingSubMap(m, + fromStart, lo, loInclusive, + toEnd, hi, hiInclusive)); } Iterator keyIterator() { - return new SubMapKeyIterator(loEntry(), hiFence()); + return new SubMapKeyIterator(absLowest(), absHighFence()); } Iterator descendingKeyIterator() { - return new DescendingSubMapKeyIterator(hiEntry(), loFence()); + return new DescendingSubMapKeyIterator(absHighest(), absLowFence()); } - class AscendingEntrySetView extends NavigableSubMap.EntrySetView { + final class AscendingEntrySetView extends EntrySetView { public Iterator> iterator() { - return new SubMapEntryIterator(loEntry(), hiFence()); + return new SubMapEntryIterator(absLowest(), absHighFence()); } } @@ -1707,46 +1738,23 @@ public class TreeMap return (es != null) ? es : new AscendingEntrySetView(); } - public K firstKey() { - return key(loEntry()); - } - - public K lastKey() { - return key(hiEntry()); - } - - public Map.Entry firstEntry() { - return loEntry(); - } - - public Map.Entry lastEntry() { - return hiEntry(); - } - - public Map.Entry pollFirstEntry() { - return pollLoEntry(); - } - - public Map.Entry pollLastEntry() { - return pollHiEntry(); - } - - public NavigableMap descendingMap() { - NavigableMap mv = descendingMapView; - return (mv != null) ? mv : - (descendingMapView = - new DescendingSubMap(m, - fromStart, lo, loExcluded, - toEnd, hi, hiExcluded)); - } + TreeMap.Entry subLowest() { return absLowest(); } + TreeMap.Entry subHighest() { return absHighest(); } + TreeMap.Entry subCeiling(K key) { return absCeiling(key); } + TreeMap.Entry subHigher(K key) { return absHigher(key); } + TreeMap.Entry subFloor(K key) { return absFloor(key); } + TreeMap.Entry subLower(K key) { return absLower(key); } } - static class DescendingSubMap extends NavigableSubMap { + /** + * @serial include + */ + static final class DescendingSubMap extends NavigableSubMap { private static final long serialVersionUID = 912986545866120460L; DescendingSubMap(TreeMap m, - boolean fromStart, K lo, int loExcluded, - boolean toEnd, K hi, int hiExcluded) { - super(m, fromStart, lo, loExcluded, toEnd, hi, hiExcluded); + boolean fromStart, K lo, boolean loInclusive, + boolean toEnd, K hi, boolean hiInclusive) { + super(m, fromStart, lo, loInclusive, toEnd, hi, hiInclusive); } private final Comparator reverseComparator = @@ -1757,73 +1765,30 @@ public class TreeMap } public NavigableMap subMap(K fromKey, boolean fromInclusive, - K toKey, boolean toInclusive) { + K toKey, boolean toInclusive) { if (!inRange(fromKey, fromInclusive)) throw new IllegalArgumentException("fromKey out of range"); if (!inRange(toKey, toInclusive)) throw new IllegalArgumentException("toKey out of range"); return new DescendingSubMap(m, - false, toKey, excluded(toInclusive), - false, fromKey, excluded(fromInclusive)); + false, toKey, toInclusive, + false, fromKey, fromInclusive); } public NavigableMap headMap(K toKey, boolean inclusive) { if (!inRange(toKey, inclusive)) throw new IllegalArgumentException("toKey out of range"); return new DescendingSubMap(m, - false, toKey, excluded(inclusive), - toEnd, hi, hiExcluded); + false, toKey, inclusive, + toEnd, hi, hiInclusive); } public NavigableMap tailMap(K fromKey, boolean inclusive){ if (!inRange(fromKey, inclusive)) throw new IllegalArgumentException("fromKey out of range"); return new DescendingSubMap(m, - fromStart, lo, loExcluded, - false, fromKey, excluded(inclusive)); - } - - Iterator keyIterator() { - return new DescendingSubMapKeyIterator(hiEntry(), loFence()); - } - - Iterator descendingKeyIterator() { - return new SubMapKeyIterator(loEntry(), hiFence()); - } - - class DescendingEntrySetView extends NavigableSubMap.EntrySetView { - public Iterator> iterator() { - return new DescendingSubMapEntryIterator(hiEntry(), loFence()); - } - } - - public Set> entrySet() { - EntrySetView es = entrySetView; - return (es != null) ? es : new DescendingEntrySetView(); - } - - public K firstKey() { - return key(hiEntry()); - } - - public K lastKey() { - return key(loEntry()); - } - - public Map.Entry firstEntry() { - return hiEntry(); - } - - public Map.Entry lastEntry() { - return loEntry(); - } - - public Map.Entry pollFirstEntry() { - return pollHiEntry(); - } - - public Map.Entry pollLastEntry() { - return pollLoEntry(); + fromStart, lo, loInclusive, + false, fromKey, inclusive); } public NavigableMap descendingMap() { @@ -1831,41 +1796,35 @@ public class TreeMap return (mv != null) ? mv : (descendingMapView = new AscendingSubMap(m, - fromStart, lo, loExcluded, - toEnd, hi, hiExcluded)); + fromStart, lo, loInclusive, + toEnd, hi, hiInclusive)); } - @Override TreeMap.Entry subCeiling(K key) { - return super.subFloor(key); + Iterator keyIterator() { + return new DescendingSubMapKeyIterator(absHighest(), absLowFence()); } - @Override TreeMap.Entry subHigher(K key) { - return super.subLower(key); + Iterator descendingKeyIterator() { + return new SubMapKeyIterator(absLowest(), absHighFence()); } - @Override TreeMap.Entry subFloor(K key) { - return super.subCeiling(key); + final class DescendingEntrySetView extends EntrySetView { + public Iterator> iterator() { + return new DescendingSubMapEntryIterator(absHighest(), absLowFence()); + } } - @Override TreeMap.Entry subLower(K key) { - return super.subHigher(key); + public Set> entrySet() { + EntrySetView es = entrySetView; + return (es != null) ? es : new DescendingEntrySetView(); } - } - /** - * Compares two keys using the correct comparison method for this TreeMap. - */ - final 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 - * that it copes with null o1 properly. - */ - final static boolean valEquals(Object o1, Object o2) { - return (o1==null ? o2==null : o1.equals(o2)); + TreeMap.Entry subLowest() { return absHighest(); } + TreeMap.Entry subHighest() { return absLowest(); } + TreeMap.Entry subCeiling(K key) { return absFloor(key); } + TreeMap.Entry subHigher(K key) { return absLower(key); } + TreeMap.Entry subFloor(K key) { return absCeiling(key); } + TreeMap.Entry subLower(K key) { return absHigher(key); } } /** @@ -1874,6 +1833,8 @@ public class TreeMap * support NavigableMap. It translates an old-version SubMap into * a new-version AscendingSubMap. This class is never otherwise * used. + * + * @serial include */ private class SubMap extends AbstractMap implements SortedMap, java.io.Serializable { @@ -1882,8 +1843,8 @@ public class TreeMap private K fromKey, toKey; private Object readResolve() { return new AscendingSubMap(TreeMap.this, - fromStart, fromKey, 0, - toEnd, toKey, 1); + fromStart, fromKey, true, + toEnd, toKey, false); } public Set> entrySet() { throw new InternalError(); } public K lastKey() { throw new InternalError(); } @@ -1895,6 +1856,8 @@ public class TreeMap } + // Red-black mechanics + private static final boolean RED = false; private static final boolean BLACK = true; @@ -1955,7 +1918,7 @@ public class TreeMap public boolean equals(Object o) { if (!(o instanceof Map.Entry)) return false; - Map.Entry e = (Map.Entry)o; + Map.Entry e = (Map.Entry)o; return valEquals(key,e.getKey()) && valEquals(value,e.getValue()); } @@ -1998,7 +1961,7 @@ public class TreeMap /** * Returns the successor of the specified Entry, or null if no such. */ - final Entry successor(Entry t) { + static TreeMap.Entry successor(Entry t) { if (t == null) return null; else if (t.right != null) { @@ -2020,7 +1983,7 @@ public class TreeMap /** * Returns the predecessor of the specified Entry, or null if no such. */ - final Entry predecessor(Entry t) { + static Entry predecessor(Entry t) { if (t == null) return null; else if (t.left != null) { @@ -2070,40 +2033,43 @@ public class TreeMap return (p == null) ? null: p.right; } - /** From CLR **/ + /** From CLR */ private void rotateLeft(Entry p) { - Entry r = p.right; - p.right = r.left; - if (r.left != null) - r.left.parent = p; - r.parent = p.parent; - if (p.parent == null) - root = r; - else if (p.parent.left == p) - p.parent.left = r; - else - p.parent.right = r; - r.left = p; - p.parent = r; + if (p != null) { + Entry r = p.right; + p.right = r.left; + if (r.left != null) + r.left.parent = p; + r.parent = p.parent; + if (p.parent == null) + root = r; + else if (p.parent.left == p) + p.parent.left = r; + else + p.parent.right = r; + r.left = p; + p.parent = r; + } } - /** From CLR **/ + /** From CLR */ private void rotateRight(Entry p) { - Entry l = p.left; - p.left = l.right; - if (l.right != null) l.right.parent = p; - l.parent = p.parent; - if (p.parent == null) - root = l; - else if (p.parent.right == p) - p.parent.right = l; - else p.parent.left = l; - l.right = p; - p.parent = l; + if (p != null) { + Entry l = p.left; + p.left = l.right; + if (l.right != null) l.right.parent = p; + l.parent = p.parent; + if (p.parent == null) + root = l; + else if (p.parent.right == p) + p.parent.right = l; + else p.parent.left = l; + l.right = p; + p.parent = l; + } } - - /** From CLR **/ + /** From CLR */ private void fixAfterInsertion(Entry x) { x.color = RED; @@ -2122,8 +2088,7 @@ public class TreeMap } setColor(parentOf(x), BLACK); setColor(parentOf(parentOf(x)), RED); - if (parentOf(parentOf(x)) != null) - rotateRight(parentOf(parentOf(x))); + rotateRight(parentOf(parentOf(x))); } } else { Entry y = leftOf(parentOf(parentOf(x))); @@ -2137,10 +2102,9 @@ public class TreeMap x = parentOf(x); rotateRight(x); } - setColor(parentOf(x), BLACK); + setColor(parentOf(x), BLACK); setColor(parentOf(parentOf(x)), RED); - if (parentOf(parentOf(x)) != null) - rotateLeft(parentOf(parentOf(x))); + rotateLeft(parentOf(parentOf(x))); } } } @@ -2150,9 +2114,9 @@ public class TreeMap /** * Delete node p, and then rebalance the tree. */ - private void deleteEntry(Entry p) { - decrementSize(); + modCount++; + size--; // If strictly internal, copy successor's element to p and then make p // point to successor. @@ -2198,7 +2162,7 @@ public class TreeMap } } - /** From CLR **/ + /** From CLR */ private void fixAfterDeletion(Entry x) { while (x != root && colorOf(x) == BLACK) { if (x == leftOf(parentOf(x))) { @@ -2213,7 +2177,7 @@ public class TreeMap if (colorOf(leftOf(sib)) == BLACK && colorOf(rightOf(sib)) == BLACK) { - setColor(sib, RED); + setColor(sib, RED); x = parentOf(x); } else { if (colorOf(rightOf(sib)) == BLACK) { @@ -2240,7 +2204,7 @@ public class TreeMap if (colorOf(rightOf(sib)) == BLACK && colorOf(leftOf(sib)) == BLACK) { - setColor(sib, RED); + setColor(sib, RED); x = parentOf(x); } else { if (colorOf(leftOf(sib)) == BLACK) { @@ -2306,13 +2270,13 @@ public class TreeMap buildFromSorted(size, null, s, null); } - /** Intended to be called only from TreeSet.readObject **/ + /** Intended to be called only from TreeSet.readObject */ void readTreeSet(int size, java.io.ObjectInputStream s, V defaultVal) throws java.io.IOException, ClassNotFoundException { buildFromSorted(size, null, s, defaultVal); } - /** Intended to be called only from TreeSet.addAll **/ + /** Intended to be called only from TreeSet.addAll */ void addAllForTreeSet(SortedSet set, V defaultVal) { try { buildFromSorted(set.size(), set.iterator(), null, defaultVal); @@ -2395,7 +2359,7 @@ public class TreeMap if (hi < lo) return null; - int mid = (lo + hi) / 2; + int mid = (lo + hi) >>> 1; Entry left = null; if (lo < mid)