--- jsr166/src/main/java/util/TreeMap.java 2006/04/21 13:42:57 1.31 +++ jsr166/src/main/java/util/TreeMap.java 2007/05/21 20:23:38 1.44 @@ -1,8 +1,26 @@ /* - * %W% %E% + * Copyright 1997-2007 Sun Microsystems, Inc. All Rights Reserved. + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. * - * Copyright 2006 Sun Microsystems, Inc. All rights reserved. - * SUN PROPRIETARY/CONFIDENTIAL. Use is subject to license terms. + * This code is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License version 2 only, as + * published by the Free Software Foundation. Sun designates this + * particular file as subject to the "Classpath" exception as provided + * by Sun in the LICENSE file that accompanied this code. + * + * This code is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License + * version 2 for more details (a copy is included in the LICENSE file that + * accompanied this code). + * + * You should have received a copy of the GNU General Public License version + * 2 along with this work; if not, write to the Free Software Foundation, + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. + * + * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara, + * CA 95054 USA or visit www.sun.com if you need additional information or + * have any questions. */ package java.util; @@ -68,7 +86,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 @@ -109,9 +127,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 @@ -226,28 +241,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; } /** @@ -361,20 +358,22 @@ public class TreeMap * Version of getEntry using comparator. Split off from getEntry * for performance. (This is not worth doing for most methods, * that are less dependent on comparator performance, but is - * worthwhile for get and put.) + * worthwhile here.) */ 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; } @@ -509,16 +508,6 @@ 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; - } - - /** * Associates the specified value with the specified key in this map. * If the map previously contained a mapping for the key, the old * value is replaced. @@ -537,73 +526,57 @@ public class TreeMap * does not permit null keys */ public V put(K key, V value) { - // Offload comparator-based version for sake of performance - if (comparator != null) - return putUsingComparator(key, value); - if (key == null) - throw new NullPointerException(); - Comparable k = (Comparable) key; - Entry t = root; - while (t != null) { - int cmp = k.compareTo(t.key); - if (cmp == 0) { - return t.setValue(value); - } else if (cmp < 0) { - if (t.left != null) { + if (t == null) { + // 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; + } + 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(); - fixAfterInsertion(t.left = new Entry(key, value, t)); - return null; - } - } else { // cmp > 0 - if (t.right != null) { + else if (cmp > 0) t = t.right; - } else { - incrementSize(); - fixAfterInsertion(t.right = new Entry(key, value, t)); - return null; - } - } + else + return t.setValue(value); + } while (t != null); } - incrementSize(); - root = new Entry(key, value, null); - return null; - } - - /** - * Version of put using comparator. Split off from put for - * performance. - */ - final V putUsingComparator(K key, V value) { - Comparator cpr = comparator; - Entry t = root; - while (t != null) { - int cmp = cpr.compare(key, t.key); - if (cmp == 0) { - return t.setValue(value); - } else if (cmp < 0) { - if (t.left != 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 { - incrementSize(); - fixAfterInsertion(t.left = new Entry(key, value, t)); - return null; - } - } else { // cmp > 0 - if (t.right != null) { + else if (cmp > 0) t = t.right; - } else { - incrementSize(); - fixAfterInsertion(t.right = new Entry(key, value, t)); - return null; - } - } + else + return t.setValue(value); + } while (t != null); } - cpr.compare(key, key); // type check - incrementSize(); - root = new Entry(key, value, null); + Entry e = new Entry(key, value, parent); + if (cmp < 0) + parent.left = e; + else + parent.right = e; + fixAfterInsertion(e); + size++; + modCount++; return null; } @@ -679,16 +652,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()); } /** @@ -696,10 +667,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; } @@ -708,10 +678,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; } @@ -723,8 +692,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)); } /** @@ -735,8 +703,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)); } /** @@ -747,8 +714,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)); } /** @@ -759,8 +725,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)); } /** @@ -771,8 +736,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)); } /** @@ -783,8 +747,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)); } /** @@ -795,8 +758,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)); } /** @@ -807,8 +769,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 @@ -902,8 +863,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)); } /** @@ -917,8 +878,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); } /** @@ -931,8 +892,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); } /** @@ -945,16 +906,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); } /** @@ -1002,10 +955,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) { @@ -1118,7 +1068,7 @@ public class TreeMap return size() != oldSize; } public NavigableSet subSet(E fromElement, boolean fromInclusive, - E toElement, boolean toInclusive) { + E toElement, boolean toInclusive) { return new TreeSet(m.subMap(fromElement, fromInclusive, toElement, toInclusive)); } @@ -1161,22 +1111,24 @@ public class TreeMap } final Entry nextEntry() { - Entry e = lastReturned = next; + Entry e = next; if (e == null) throw new NoSuchElementException(); if (modCount != expectedModCount) throw new ConcurrentModificationException(); next = successor(e); + lastReturned = e; return e; } final Entry prevEntry() { - Entry e = lastReturned= next; + Entry e = next; if (e == null) throw new NoSuchElementException(); if (modCount != expectedModCount) throw new ConcurrentModificationException(); next = predecessor(e); + lastReturned = e; return e; } @@ -1185,10 +1137,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; } } @@ -1229,55 +1182,124 @@ public class TreeMap } } + // Little utilities + + /** + * 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)); + } + + /** + * Return SimpleImmutableEntry for entry, or null if null + */ + static Map.Entry exportEntry(TreeMap.Entry e) { + return e == null? null : + new AbstractMap.SimpleImmutableEntry(e); + } + + /** + * Return key for entry, or null if null + */ + static K keyOrNull(TreeMap.Entry e) { + return e == null? null : e.key; + } + + /** + * Returns the key corresponding to the specified Entry. + * @throws NoSuchElementException if the Entry is null + */ + static K key(Entry e) { + if (e==null) + throw new NoSuchElementException(); + return e.key; + } + + // SubMaps + /** + * 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 backing map. */ final TreeMap m; - /* - * Endpoints are represented as triples (fromStart, lo, loExcluded) - * and (toEnd, hi, hiExcluded). If fromStart is true, then - * the low (absolute) bound is the start of the backing map, and the - * other values are ignored. Otherwise, if loExcluded is - * zero, lo is the inclusive bound, else loExcluded is one, - * and lo is the exclusive bound. Similarly for the upper bound. + /** + * Endpoints are represented as triples (fromStart, lo, + * loInclusive) and (toEnd, hi, hiInclusive). If fromStart is + * true, then the low (absolute) bound is the start of the + * backing map, and the other values are ignored. Otherwise, + * if loInclusive is true, lo is the inclusive bound, else lo + * is the exclusive bound. Similarly for the upper bound. */ - final K lo, hi; final boolean fromStart, toEnd; - final int loExcluded, hiExcluded; + final boolean loInclusive, hiInclusive; NavigableSubMap(TreeMap m, - boolean fromStart, K lo, int loExcluded, - boolean toEnd, K hi, int hiExcluded) { + 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); } - else if (!fromStart) // type check - m.compare(lo, lo); - else 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) { @@ -1289,148 +1311,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 @@ -1438,6 +1488,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; @@ -1457,7 +1535,7 @@ public class TreeMap } public boolean isEmpty() { - TreeMap.Entry n = loEntry(); + TreeMap.Entry n = absLowest(); return n == null || tooHigh(n.key); } @@ -1489,88 +1567,13 @@ 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 { TreeMap.Entry lastReturned; TreeMap.Entry next; - final K fenceKey; + final Object fenceKey; int expectedModCount; SubMapIterator(TreeMap.Entry first, @@ -1578,7 +1581,7 @@ public class TreeMap expectedModCount = m.modCount; lastReturned = null; next = first; - fenceKey = fence == null ? null : fence.key; + fenceKey = fence == null ? UNBOUNDED : fence.key; } public final boolean hasNext() { @@ -1586,36 +1589,50 @@ public class TreeMap } final TreeMap.Entry nextEntry() { - TreeMap.Entry e = lastReturned = next; + TreeMap.Entry e = next; if (e == null || e.key == fenceKey) throw new NoSuchElementException(); if (m.modCount != expectedModCount) throw new ConcurrentModificationException(); next = successor(e); + lastReturned = e; return e; } final TreeMap.Entry prevEntry() { - TreeMap.Entry e = lastReturned = next; + TreeMap.Entry e = next; if (e == null || e.key == fenceKey) throw new NoSuchElementException(); if (m.modCount != expectedModCount) throw new ConcurrentModificationException(); next = predecessor(e); + lastReturned = 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> { @@ -1626,6 +1643,9 @@ public class TreeMap public Map.Entry next() { return nextEntry(); } + public void remove() { + removeAscending(); + } } final class SubMapKeyIterator extends SubMapIterator { @@ -1636,37 +1656,49 @@ public class TreeMap 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() { @@ -1674,43 +1706,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()); } } @@ -1719,46 +1760,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 = @@ -1769,73 +1787,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() { @@ -1843,41 +1818,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); } } /** @@ -1886,6 +1855,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 { @@ -1894,8 +1865,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(); } @@ -1907,6 +1878,8 @@ public class TreeMap } + // Red-black mechanics + private static final boolean RED = false; private static final boolean BLACK = true; @@ -1967,7 +1940,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()); } @@ -2082,40 +2055,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; @@ -2134,8 +2110,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))); @@ -2151,8 +2126,7 @@ public class TreeMap } setColor(parentOf(x), BLACK); setColor(parentOf(parentOf(x)), RED); - if (parentOf(parentOf(x)) != null) - rotateLeft(parentOf(parentOf(x))); + rotateLeft(parentOf(parentOf(x))); } } } @@ -2162,9 +2136,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. @@ -2210,7 +2184,7 @@ public class TreeMap } } - /** From CLR **/ + /** From CLR */ private void fixAfterDeletion(Entry x) { while (x != root && colorOf(x) == BLACK) { if (x == leftOf(parentOf(x))) { @@ -2318,13 +2292,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); @@ -2407,7 +2381,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)