--- jsr166/src/main/java/util/TreeMap.java 2006/03/19 18:03:54 1.27 +++ jsr166/src/main/java/util/TreeMap.java 2006/05/09 16:35:40 1.36 @@ -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; } /** @@ -335,10 +316,12 @@ public class TreeMap * and this map uses natural ordering, or its comparator * does not permit null keys */ - private Entry getEntry(Object key) { + final Entry getEntry(Object key) { // Offload comparator-based version for sake of performance if (comparator != null) return getEntryUsingComparator(key); + if (key == null) + throw new NullPointerException(); Comparable k = (Comparable) key; Entry p = root; while (p != null) { @@ -359,18 +342,20 @@ public class TreeMap * that are less dependent on comparator performance, but is * worthwhile here.) */ - private Entry getEntryUsingComparator(Object key) { + 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; } @@ -381,12 +366,9 @@ public class TreeMap * key; if no such entry exists (i.e., the greatest key in the Tree is less * than the specified key), returns null. */ - private Entry getCeilingEntry(K key) { + 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) @@ -408,6 +390,7 @@ public class TreeMap } else return p; } + return null; } /** @@ -415,12 +398,9 @@ public class TreeMap * exists, returns the entry for the greatest key less than the specified * key; if no such entry exists, returns null. */ - private Entry getFloorEntry(K key) { + 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) @@ -443,6 +423,7 @@ public class TreeMap return p; } + return null; } /** @@ -451,12 +432,9 @@ public class TreeMap * key greater than the specified key; if no such entry exists * returns null. */ - private Entry getHigherEntry(K key) { + 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) @@ -477,6 +455,7 @@ public class TreeMap } } } + return null; } /** @@ -484,12 +463,9 @@ public class TreeMap * no such entry exists (i.e., the least key in the Tree is greater than * the specified key), returns null. */ - private Entry getLowerEntry(K key) { + 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) @@ -510,16 +486,7 @@ public class TreeMap } } } - } - - /** - * Returns the key corresponding to the specified Entry. - * @throws NoSuchElementException if the Entry is null - */ - private static K key(Entry e) { - if (e==null) - throw new NoSuchElementException(); - return e.key; + return null; } /** @@ -542,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; } /** @@ -634,8 +615,8 @@ public class TreeMap clone.size = 0; clone.modCount = 0; clone.entrySet = null; - clone.descendingEntrySet = null; - clone.descendingKeySet = null; + clone.navigableKeySet = null; + clone.descendingMap = null; // Initialize clone with our mappings try { @@ -653,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()); } /** @@ -670,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; } @@ -682,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; } @@ -697,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)); } /** @@ -709,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)); } /** @@ -721,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)); } /** @@ -733,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)); } /** @@ -745,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)); } /** @@ -757,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)); } /** @@ -769,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)); } /** @@ -781,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 @@ -792,9 +761,9 @@ public class TreeMap * the first time this view is requested. Views are stateless, so * there's no reason to create more than one. */ - private transient Set> entrySet = null; - private transient Set> descendingEntrySet = null; - private transient Set descendingKeySet = null; + private transient EntrySet entrySet = null; + private transient KeySet navigableKeySet = null; + private transient NavigableMap descendingMap = null; /** * Returns a {@link Set} view of the keys contained in this map. @@ -811,32 +780,22 @@ public class TreeMap * operations. */ public Set keySet() { - Set ks = keySet; - return (ks != null) ? ks : (keySet = new KeySet()); + return navigableKeySet(); } - class KeySet extends AbstractSet { - public Iterator iterator() { - return new KeyIterator(getFirstEntry()); - } - - public int size() { - return TreeMap.this.size(); - } - - public boolean contains(Object o) { - return containsKey(o); - } - - public boolean remove(Object o) { - int oldSize = size; - TreeMap.this.remove(o); - return size != oldSize; - } + /** + * @since 1.6 + */ + public NavigableSet navigableKeySet() { + KeySet nks = navigableKeySet; + return (nks != null) ? nks : (navigableKeySet = new KeySet(this)); + } - public void clear() { - TreeMap.this.clear(); - } + /** + * @since 1.6 + */ + public NavigableSet descendingKeySet() { + return descendingMap().navigableKeySet(); } /** @@ -859,6 +818,115 @@ public class TreeMap return (vs != null) ? vs : (values = new Values()); } + /** + * Returns a {@link Set} view of the mappings contained in this map. + * The set's iterator returns the entries in ascending key order. + * The set is backed by the map, so changes to the map are + * reflected in the set, and vice-versa. If the map is modified + * while an iteration over the set is in progress (except through + * the iterator's own remove operation, or through the + * setValue operation on a map entry returned by the + * iterator) the results of the iteration are undefined. The set + * supports element removal, which removes the corresponding + * mapping from the map, via the Iterator.remove, + * Set.remove, removeAll, retainAll and + * clear operations. It does not support the + * add or addAll operations. + */ + public Set> entrySet() { + EntrySet es = entrySet; + return (es != null) ? es : (entrySet = new EntrySet()); + } + + /** + * @since 1.6 + */ + public NavigableMap descendingMap() { + NavigableMap km = descendingMap; + return (km != null) ? km : + (descendingMap = new DescendingSubMap(this, + true, null, true, + true, null, true)); + } + + /** + * @throws ClassCastException {@inheritDoc} + * @throws NullPointerException if fromKey or toKey is + * null and this map uses natural ordering, or its comparator + * does not permit null keys + * @throws IllegalArgumentException {@inheritDoc} + * @since 1.6 + */ + public NavigableMap subMap(K fromKey, boolean fromInclusive, + K toKey, boolean toInclusive) { + return new AscendingSubMap(this, + false, fromKey, fromInclusive, + false, toKey, toInclusive); + } + + /** + * @throws ClassCastException {@inheritDoc} + * @throws NullPointerException if toKey is null + * and this map uses natural ordering, or its comparator + * does not permit null keys + * @throws IllegalArgumentException {@inheritDoc} + * @since 1.6 + */ + public NavigableMap headMap(K toKey, boolean inclusive) { + return new AscendingSubMap(this, + true, null, true, + false, toKey, inclusive); + } + + /** + * @throws ClassCastException {@inheritDoc} + * @throws NullPointerException if fromKey is null + * and this map uses natural ordering, or its comparator + * does not permit null keys + * @throws IllegalArgumentException {@inheritDoc} + * @since 1.6 + */ + public NavigableMap tailMap(K fromKey, boolean inclusive) { + return new AscendingSubMap(this, + false, fromKey, inclusive, + true, null, true); + } + + /** + * @throws ClassCastException {@inheritDoc} + * @throws NullPointerException if fromKey or toKey is + * null and this map uses natural ordering, or its comparator + * does not permit null keys + * @throws IllegalArgumentException {@inheritDoc} + */ + public SortedMap subMap(K fromKey, K toKey) { + return subMap(fromKey, true, toKey, false); + } + + /** + * @throws ClassCastException {@inheritDoc} + * @throws NullPointerException if toKey is null + * and this map uses natural ordering, or its comparator + * does not permit null keys + * @throws IllegalArgumentException {@inheritDoc} + */ + public SortedMap headMap(K toKey) { + return headMap(toKey, false); + } + + /** + * @throws ClassCastException {@inheritDoc} + * @throws NullPointerException if fromKey is null + * and this map uses natural ordering, or its comparator + * does not permit null keys + * @throws IllegalArgumentException {@inheritDoc} + */ + public SortedMap tailMap(K fromKey) { + return tailMap(fromKey, true); + } + + // View class support + class Values extends AbstractCollection { public Iterator iterator() { return new ValueIterator(getFirstEntry()); @@ -869,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) { @@ -890,26 +955,6 @@ public class TreeMap } } - /** - * Returns a {@link Set} view of the mappings contained in this map. - * The set's iterator returns the entries in ascending key order. - * The set is backed by the map, so changes to the map are - * reflected in the set, and vice-versa. If the map is modified - * while an iteration over the set is in progress (except through - * the iterator's own remove operation, or through the - * setValue operation on a map entry returned by the - * iterator) the results of the iteration are undefined. The set - * supports element removal, which removes the corresponding - * mapping from the map, via the Iterator.remove, - * Set.remove, removeAll, retainAll and - * clear operations. It does not support the - * add or addAll operations. - */ - public Set> entrySet() { - Set> es = entrySet; - return (es != null) ? es : (entrySet = new EntrySet()); - } - class EntrySet extends AbstractSet> { public Iterator> iterator() { return new EntryIterator(getFirstEntry()); @@ -946,324 +991,513 @@ public class TreeMap } } - /** - * @since 1.6 + /* + * Unlike Values and EntrySet, the KeySet class is static, + * delegating to a NavigableMap to allow use by SubMaps, which + * outweighs the ugliness of needing type-tests for the following + * Iterator methods that are defined appropriately in main versus + * submap classes. */ - public Set> descendingEntrySet() { - Set> es = descendingEntrySet; - return (es != null) ? es : (descendingEntrySet = new DescendingEntrySet()); + + Iterator keyIterator() { + return new KeyIterator(getFirstEntry()); } - class DescendingEntrySet extends EntrySet { - public Iterator> iterator() { - return new DescendingEntryIterator(getLastEntry()); + Iterator descendingKeyIterator() { + return new DescendingKeyIterator(getFirstEntry()); + } + + static final class KeySet extends AbstractSet implements NavigableSet { + private final NavigableMap m; + KeySet(NavigableMap map) { m = map; } + + public Iterator iterator() { + if (m instanceof TreeMap) + return ((TreeMap)m).keyIterator(); + else + return (Iterator)(((TreeMap.NavigableSubMap)m).keyIterator()); + } + + public Iterator descendingIterator() { + if (m instanceof TreeMap) + return ((TreeMap)m).descendingKeyIterator(); + else + return (Iterator)(((TreeMap.NavigableSubMap)m).descendingKeyIterator()); + } + + public int size() { return m.size(); } + public boolean isEmpty() { return m.isEmpty(); } + public boolean contains(Object o) { return m.containsKey(o); } + public void clear() { m.clear(); } + public E lower(E e) { return m.lowerKey(e); } + public E floor(E e) { return m.floorKey(e); } + public E ceiling(E e) { return m.ceilingKey(e); } + public E higher(E e) { return m.higherKey(e); } + public E first() { return m.firstKey(); } + public E last() { return m.lastKey(); } + public Comparator comparator() { return m.comparator(); } + public E pollFirst() { + Map.Entry e = m.pollFirstEntry(); + return e == null? null : e.getKey(); + } + public E pollLast() { + Map.Entry e = m.pollLastEntry(); + return e == null? null : e.getKey(); + } + public boolean remove(Object o) { + int oldSize = size(); + 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 headSet(E toElement, boolean inclusive) { + return new TreeSet(m.headMap(toElement, inclusive)); + } + public NavigableSet tailSet(E fromElement, boolean inclusive) { + return new TreeSet(m.tailMap(fromElement, inclusive)); + } + public SortedSet subSet(E fromElement, E toElement) { + return subSet(fromElement, true, toElement, false); + } + public SortedSet headSet(E toElement) { + return headSet(toElement, false); + } + public SortedSet tailSet(E fromElement) { + return tailSet(fromElement, true); + } + public NavigableSet descendingSet() { + return new TreeSet(m.descendingMap()); } } /** - * @since 1.6 + * Base class for TreeMap Iterators */ - public Set descendingKeySet() { - Set ks = descendingKeySet; - return (ks != null) ? ks : (descendingKeySet = new DescendingKeySet()); + abstract class PrivateEntryIterator implements Iterator { + Entry next; + Entry lastReturned; + int expectedModCount; + + PrivateEntryIterator(Entry first) { + expectedModCount = modCount; + lastReturned = null; + next = first; + } + + public final boolean hasNext() { + return next != null; + } + + final Entry nextEntry() { + Entry e = lastReturned = next; + if (e == null) + throw new NoSuchElementException(); + if (modCount != expectedModCount) + throw new ConcurrentModificationException(); + next = successor(e); + return e; + } + + final Entry prevEntry() { + Entry e = lastReturned= next; + if (e == null) + throw new NoSuchElementException(); + if (modCount != expectedModCount) + throw new ConcurrentModificationException(); + next = predecessor(e); + return e; + } + + public void remove() { + if (lastReturned == null) + throw new IllegalStateException(); + if (modCount != expectedModCount) + throw new ConcurrentModificationException(); + if (lastReturned.left != null && lastReturned.right != null) + next = lastReturned; + deleteEntry(lastReturned); + expectedModCount++; + lastReturned = null; + } } - class DescendingKeySet extends KeySet { - public Iterator iterator() { - return new DescendingKeyIterator(getLastEntry()); + final class EntryIterator extends PrivateEntryIterator> { + EntryIterator(Entry first) { + super(first); + } + public Map.Entry next() { + return nextEntry(); } } - /** - * @throws ClassCastException {@inheritDoc} - * @throws NullPointerException if fromKey or toKey is - * null and this map uses natural ordering, or its comparator - * does not permit null keys - * @throws IllegalArgumentException {@inheritDoc} - * @since 1.6 - */ - public NavigableMap navigableSubMap(K fromKey, K toKey) { - return new SubMap(fromKey, toKey); + final class ValueIterator extends PrivateEntryIterator { + ValueIterator(Entry first) { + super(first); + } + public V next() { + return nextEntry().value; + } + } + + final class KeyIterator extends PrivateEntryIterator { + KeyIterator(Entry first) { + super(first); + } + public K next() { + return nextEntry().key; + } } + final class DescendingKeyIterator extends PrivateEntryIterator { + DescendingKeyIterator(Entry first) { + super(first); + } + public K next() { + return prevEntry().key; + } + } + + // Little utilities + /** - * @throws ClassCastException {@inheritDoc} - * @throws NullPointerException if toKey is null - * and this map uses natural ordering, or its comparator - * does not permit null keys - * @throws IllegalArgumentException {@inheritDoc} - * @since 1.6 + * Compares two keys using the correct comparison method for this TreeMap. */ - public NavigableMap navigableHeadMap(K toKey) { - return new SubMap(toKey, true); + final int compare(Object k1, Object k2) { + return comparator==null ? ((Comparable)k1).compareTo((K)k2) + : comparator.compare((K)k1, (K)k2); } /** - * @throws ClassCastException {@inheritDoc} - * @throws NullPointerException if fromKey is null - * and this map uses natural ordering, or its comparator - * does not permit null keys - * @throws IllegalArgumentException {@inheritDoc} - * @since 1.6 + * Test two values for equality. Differs from o1.equals(o2) only in + * that it copes with null o1 properly. */ - public NavigableMap navigableTailMap(K fromKey) { - return new SubMap(fromKey, false); + final static boolean valEquals(Object o1, Object o2) { + return (o1==null ? o2==null : o1.equals(o2)); } /** - * Equivalent to {@link #navigableSubMap} but with a return type - * conforming to the SortedMap interface. - * - *

{@inheritDoc} - * - * @throws ClassCastException {@inheritDoc} - * @throws NullPointerException if fromKey or toKey is - * null and this map uses natural ordering, or its comparator - * does not permit null keys - * @throws IllegalArgumentException {@inheritDoc} + * Return SimpleImmutableEntry for entry, or null if null */ - public SortedMap subMap(K fromKey, K toKey) { - return new SubMap(fromKey, toKey); + static Map.Entry exportEntry(TreeMap.Entry e) { + return e == null? null : + new AbstractMap.SimpleImmutableEntry(e); } /** - * Equivalent to {@link #navigableHeadMap} but with a return type - * conforming to the SortedMap interface. - * - *

{@inheritDoc} - * - * @throws ClassCastException {@inheritDoc} - * @throws NullPointerException if toKey is null - * and this map uses natural ordering, or its comparator - * does not permit null keys - * @throws IllegalArgumentException {@inheritDoc} + * Return key for entry, or null if null */ - public SortedMap headMap(K toKey) { - return new SubMap(toKey, true); + static K keyOrNull(TreeMap.Entry e) { + return e == null? null : e.key; } /** - * Equivalent to {@link #navigableTailMap} but with a return type - * conforming to the SortedMap interface. - * - *

{@inheritDoc} - * - * @throws ClassCastException {@inheritDoc} - * @throws NullPointerException if fromKey is null - * and this map uses natural ordering, or its comparator - * does not permit null keys - * @throws IllegalArgumentException {@inheritDoc} + * Returns the key corresponding to the specified Entry. + * @throws NoSuchElementException if the Entry is null */ - public SortedMap tailMap(K fromKey) { - return new SubMap(fromKey, false); + static K key(Entry e) { + if (e==null) + throw new NoSuchElementException(); + return e.key; } - private class SubMap - extends AbstractMap - implements NavigableMap, java.io.Serializable { - private static final long serialVersionUID = -6520786458950516097L; + // SubMaps + + /** + * @serial include + */ + static abstract class NavigableSubMap extends AbstractMap + implements NavigableMap, java.io.Serializable { /** - * fromKey is significant only if fromStart is false. Similarly, - * toKey is significant only if toStart is false. + * The backing map. */ - private boolean fromStart = false, toEnd = false; - private K fromKey, toKey; + final TreeMap m; - SubMap(K fromKey, K toKey) { - if (compare(fromKey, toKey) > 0) - throw new IllegalArgumentException("fromKey > toKey"); - this.fromKey = fromKey; - this.toKey = toKey; - } - - SubMap(K key, boolean headMap) { - compare(key, key); // Type-check key - - if (headMap) { - fromStart = true; - toKey = key; + /** + * 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 boolean loInclusive, hiInclusive; + + NavigableSubMap(TreeMap m, + 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 { - toEnd = true; - fromKey = key; + if (!fromStart) // type check + m.compare(lo, lo); + if (!toEnd) + m.compare(hi, hi); } - } - SubMap(boolean fromStart, K fromKey, boolean toEnd, K toKey) { + this.m = m; this.fromStart = fromStart; - this.fromKey= fromKey; + this.lo = lo; + this.loInclusive = loInclusive; this.toEnd = toEnd; - this.toKey = toKey; + this.hi = hi; + 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 !tooLow(key) && !tooHigh(key); + } + + final boolean inClosedRange(Object key) { + return (fromStart || m.compare(key, lo) >= 0) + && (toEnd || m.compare(hi, key) >= 0); + } + + final boolean inRange(Object key, boolean inclusive) { + return inclusive ? inRange(key) : inClosedRange(key); + } + + /* + * Absolute versions of relation operations. + * Subclasses map to these using like-named "sub" + * versions that invert senses for descending maps + */ + + final TreeMap.Entry absLowest() { + TreeMap.Entry e = + (fromStart ? m.getFirstEntry() : + (loInclusive ? m.getCeilingEntry(lo) : + m.getHigherEntry(lo))); + return (e == null || tooHigh(e.key)) ? null : e; + } + + final TreeMap.Entry absHighest() { + TreeMap.Entry e = + (toEnd ? m.getLastEntry() : + (hiInclusive ? m.getFloorEntry(hi) : + m.getLowerEntry(hi))); + return (e == null || tooLow(e.key)) ? null : e; + } + + 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; + } + + 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; + } + + 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; } + 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) && TreeMap.this.containsKey(key); + public int size() { + return (fromStart && toEnd) ? m.size() : entrySet().size(); } - public V get(Object key) { - if (!inRange(key)) - return null; - return TreeMap.this.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 TreeMap.this.put(key, value); + return m.put(key, value); } - public V remove(Object key) { - if (!inRange(key)) - return null; - return TreeMap.this.remove(key); + public final V get(Object key) { + return !inRange(key)? null : m.get(key); } - public Comparator comparator() { - return comparator; + public final V remove(Object key) { + return !inRange(key)? null : m.remove(key); } - public K firstKey() { - TreeMap.Entry e = fromStart ? getFirstEntry() : getCeilingEntry(fromKey); - K first = key(e); - if (!toEnd && compare(first, toKey) >= 0) - throw new NoSuchElementException(); - return first; + public final Map.Entry ceilingEntry(K key) { + return exportEntry(subCeiling(key)); } - public K lastKey() { - TreeMap.Entry e = toEnd ? getLastEntry() : getLowerEntry(toKey); - K last = key(e); - if (!fromStart && compare(last, fromKey) < 0) - throw new NoSuchElementException(); - return last; + public final K ceilingKey(K key) { + return keyOrNull(subCeiling(key)); } - public Map.Entry firstEntry() { - TreeMap.Entry e = fromStart ? - getFirstEntry() : getCeilingEntry(fromKey); - if (e == null || (!toEnd && compare(e.key, toKey) >= 0)) - return null; - return e; + public final Map.Entry higherEntry(K key) { + return exportEntry(subHigher(key)); } - public Map.Entry lastEntry() { - TreeMap.Entry e = toEnd ? - getLastEntry() : getLowerEntry(toKey); - if (e == null || (!fromStart && compare(e.key, fromKey) < 0)) - return null; - return e; + public final K higherKey(K key) { + return keyOrNull(subHigher(key)); } - public Map.Entry pollFirstEntry() { - TreeMap.Entry e = fromStart ? - getFirstEntry() : getCeilingEntry(fromKey); - if (e == null || (!toEnd && compare(e.key, toKey) >= 0)) - return null; - Map.Entry result = new AbstractMap.SimpleImmutableEntry(e); - deleteEntry(e); - return result; + public final Map.Entry floorEntry(K key) { + return exportEntry(subFloor(key)); } - public Map.Entry pollLastEntry() { - TreeMap.Entry e = toEnd ? - getLastEntry() : getLowerEntry(toKey); - if (e == null || (!fromStart && compare(e.key, fromKey) < 0)) - return null; - Map.Entry result = new AbstractMap.SimpleImmutableEntry(e); - deleteEntry(e); - return result; + public final K floorKey(K key) { + return keyOrNull(subFloor(key)); } - private TreeMap.Entry subceiling(K key) { - TreeMap.Entry e = (!fromStart && compare(key, fromKey) < 0)? - getCeilingEntry(fromKey) : getCeilingEntry(key); - if (e == null || (!toEnd && compare(e.key, toKey) >= 0)) - return null; - return e; + public final Map.Entry lowerEntry(K key) { + return exportEntry(subLower(key)); } - public Map.Entry ceilingEntry(K key) { - TreeMap.Entry e = subceiling(key); - return e == null? null : new AbstractMap.SimpleImmutableEntry(e); + public final K lowerKey(K key) { + return keyOrNull(subLower(key)); } - public K ceilingKey(K key) { - TreeMap.Entry e = subceiling(key); - return e == null? null : e.key; + public final K firstKey() { + return key(subLowest()); } - - private TreeMap.Entry subhigher(K key) { - TreeMap.Entry e = (!fromStart && compare(key, fromKey) < 0)? - getCeilingEntry(fromKey) : getHigherEntry(key); - if (e == null || (!toEnd && compare(e.key, toKey) >= 0)) - return null; - return e; + public final K lastKey() { + return key(subHighest()); } - public Map.Entry higherEntry(K key) { - TreeMap.Entry e = subhigher(key); - return e == null? null : new AbstractMap.SimpleImmutableEntry(e); + public final Map.Entry firstEntry() { + return exportEntry(subLowest()); } - public K higherKey(K key) { - TreeMap.Entry e = subhigher(key); - return e == null? null : e.key; + public final Map.Entry lastEntry() { + return exportEntry(subHighest()); } - private TreeMap.Entry subfloor(K key) { - TreeMap.Entry e = (!toEnd && compare(key, toKey) >= 0)? - getLowerEntry(toKey) : getFloorEntry(key); - if (e == null || (!fromStart && compare(e.key, fromKey) < 0)) - return null; - return e; + public final Map.Entry pollFirstEntry() { + TreeMap.Entry e = subLowest(); + Map.Entry result = exportEntry(e); + if (e != null) + m.deleteEntry(e); + return result; } - public Map.Entry floorEntry(K key) { - TreeMap.Entry e = subfloor(key); - return e == null? null : new AbstractMap.SimpleImmutableEntry(e); + public final Map.Entry pollLastEntry() { + TreeMap.Entry e = subHighest(); + Map.Entry result = exportEntry(e); + if (e != null) + m.deleteEntry(e); + return result; } - public K floorKey(K key) { - TreeMap.Entry e = subfloor(key); - return e == null? null : e.key; + // Views + transient NavigableMap descendingMapView = null; + transient EntrySetView entrySetView = null; + transient KeySet navigableKeySetView = null; + + public final NavigableSet navigableKeySet() { + KeySet nksv = navigableKeySetView; + return (nksv != null) ? nksv : + (navigableKeySetView = new TreeMap.KeySet(this)); } - private TreeMap.Entry sublower(K key) { - TreeMap.Entry e = (!toEnd && compare(key, toKey) >= 0)? - getLowerEntry(toKey) : getLowerEntry(key); - if (e == null || (!fromStart && compare(e.key, fromKey) < 0)) - return null; - return e; + public final Set keySet() { + return navigableKeySet(); } - public Map.Entry lowerEntry(K key) { - TreeMap.Entry e = sublower(key); - return e == null? null : new AbstractMap.SimpleImmutableEntry(e); + public NavigableSet descendingKeySet() { + return descendingMap().navigableKeySet(); } - public K lowerKey(K key) { - TreeMap.Entry e = sublower(key); - return e == null? null : e.key; + public final SortedMap subMap(K fromKey, K toKey) { + return subMap(fromKey, true, toKey, false); } - private transient Set> entrySet = null; + public final SortedMap headMap(K toKey) { + return headMap(toKey, false); + } - public Set> entrySet() { - Set> es = entrySet; - return (es != null)? es : (entrySet = new EntrySetView()); + public final SortedMap tailMap(K fromKey) { + return tailMap(fromKey, true); } - private class EntrySetView extends AbstractSet> { + // View classes + + abstract class EntrySetView extends AbstractSet> { private transient int size = -1, sizeModCount; public int size() { - if (size == -1 || sizeModCount != TreeMap.this.modCount) { - size = 0; sizeModCount = TreeMap.this.modCount; + if (fromStart && toEnd) + return m.size(); + if (size == -1 || sizeModCount != m.modCount) { + sizeModCount = m.modCount; + size = 0; Iterator i = iterator(); while (i.hasNext()) { size++; @@ -1274,7 +1508,8 @@ public class TreeMap } public boolean isEmpty() { - return !iterator().hasNext(); + TreeMap.Entry n = absLowest(); + return n == null || tooHigh(n.key); } public boolean contains(Object o) { @@ -1284,9 +1519,9 @@ public class TreeMap K key = entry.getKey(); if (!inRange(key)) return false; - TreeMap.Entry node = getEntry(key); + TreeMap.Entry node = m.getEntry(key); return node != null && - valEquals(node.getValue(), entry.getValue()); + valEquals(node.getValue(), entry.getValue()); } public boolean remove(Object o) { @@ -1296,270 +1531,301 @@ public class TreeMap K key = entry.getKey(); if (!inRange(key)) return false; - TreeMap.Entry node = getEntry(key); + TreeMap.Entry node = m.getEntry(key); if (node!=null && valEquals(node.getValue(),entry.getValue())){ - deleteEntry(node); + m.deleteEntry(node); return true; } return false; } - - public Iterator> iterator() { - return new SubMapEntryIterator( - (fromStart ? getFirstEntry() : getCeilingEntry(fromKey)), - (toEnd ? null : getCeilingEntry(toKey))); - } } - private transient Set> descendingEntrySetView = null; - private transient Set descendingKeySetView = null; - - public Set> descendingEntrySet() { - Set> es = descendingEntrySetView; - return (es != null) ? es : - (descendingEntrySetView = new DescendingEntrySetView()); - } - - public Set descendingKeySet() { - Set ks = descendingKeySetView; - return (ks != null) ? ks : - (descendingKeySetView = new DescendingKeySetView()); - } + /** + * Iterators for SubMaps + */ + abstract class SubMapIterator implements Iterator { + TreeMap.Entry lastReturned; + TreeMap.Entry next; + final K fenceKey; + int expectedModCount; - private class DescendingEntrySetView extends EntrySetView { - public Iterator> iterator() { - return new DescendingSubMapEntryIterator - ((toEnd ? getLastEntry() : getLowerEntry(toKey)), - (fromStart ? null : getLowerEntry(fromKey))); + SubMapIterator(TreeMap.Entry first, + TreeMap.Entry fence) { + expectedModCount = m.modCount; + lastReturned = null; + next = first; + fenceKey = fence == null ? null : fence.key; } - } - private class DescendingKeySetView extends AbstractSet { - public Iterator iterator() { - return new Iterator() { - private Iterator> i = descendingEntrySet().iterator(); - - public boolean hasNext() { return i.hasNext(); } - public K next() { return i.next().getKey(); } - public void remove() { i.remove(); } - }; + public final boolean hasNext() { + return next != null && next.key != fenceKey; } - public int size() { - return SubMap.this.size(); + final TreeMap.Entry nextEntry() { + TreeMap.Entry e = lastReturned = next; + if (e == null || e.key == fenceKey) + throw new NoSuchElementException(); + if (m.modCount != expectedModCount) + throw new ConcurrentModificationException(); + next = successor(e); + return e; } - public boolean contains(Object k) { - return SubMap.this.containsKey(k); + final TreeMap.Entry prevEntry() { + TreeMap.Entry e = lastReturned = next; + if (e == null || e.key == fenceKey) + throw new NoSuchElementException(); + if (m.modCount != expectedModCount) + throw new ConcurrentModificationException(); + next = predecessor(e); + return e; } - } - - public NavigableMap navigableSubMap(K fromKey, K toKey) { - if (!inRange2(fromKey)) - throw new IllegalArgumentException("fromKey out of range"); - if (!inRange2(toKey)) - throw new IllegalArgumentException("toKey out of range"); - return new SubMap(fromKey, 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 navigableTailMap(K fromKey) { - if (!inRange2(fromKey)) - throw new IllegalArgumentException("fromKey out of range"); - return new SubMap(false, fromKey, toEnd, toKey); + public void remove() { + if (lastReturned == null) + throw new IllegalStateException(); + if (m.modCount != expectedModCount) + throw new ConcurrentModificationException(); + if (lastReturned.left != null && lastReturned.right != null) + next = lastReturned; + m.deleteEntry(lastReturned); + expectedModCount++; + lastReturned = null; + } } - public SortedMap subMap(K fromKey, K toKey) { - return navigableSubMap(fromKey, toKey); + final class SubMapEntryIterator extends SubMapIterator> { + SubMapEntryIterator(TreeMap.Entry first, + TreeMap.Entry fence) { + super(first, fence); + } + public Map.Entry next() { + return nextEntry(); + } } - public SortedMap headMap(K toKey) { - return navigableHeadMap(toKey); + final class SubMapKeyIterator extends SubMapIterator { + SubMapKeyIterator(TreeMap.Entry first, + TreeMap.Entry fence) { + super(first, fence); + } + public K next() { + return nextEntry().key; + } } - public SortedMap tailMap(K fromKey) { - return navigableTailMap(fromKey); - } + final class DescendingSubMapEntryIterator extends SubMapIterator> { + DescendingSubMapEntryIterator(TreeMap.Entry last, + TreeMap.Entry fence) { + super(last, fence); + } - private boolean inRange(Object key) { - return (fromStart || compare(key, fromKey) >= 0) && - (toEnd || compare(key, toKey) < 0); + public Map.Entry next() { + return prevEntry(); + } } - // This form allows the high endpoint (as well as all legit keys) - private boolean inRange2(Object key) { - return (fromStart || compare(key, fromKey) >= 0) && - (toEnd || compare(key, toKey) <= 0); + final class DescendingSubMapKeyIterator extends SubMapIterator { + DescendingSubMapKeyIterator(TreeMap.Entry last, + TreeMap.Entry fence) { + super(last, fence); + } + public K next() { + return prevEntry().key; + } } } /** - * TreeMap Iterator. + * @serial include */ - abstract class PrivateEntryIterator implements Iterator { - int expectedModCount = TreeMap.this.modCount; - Entry lastReturned = null; - Entry next; + static final class AscendingSubMap extends NavigableSubMap { + private static final long serialVersionUID = 912986545866124060L; - PrivateEntryIterator(Entry first) { - next = first; + AscendingSubMap(TreeMap m, + boolean fromStart, K lo, boolean loInclusive, + boolean toEnd, K hi, boolean hiInclusive) { + super(m, fromStart, lo, loInclusive, toEnd, hi, hiInclusive); } - public boolean hasNext() { - return next != null; + public Comparator comparator() { + return m.comparator(); } - Entry nextEntry() { - if (next == null) - throw new NoSuchElementException(); - if (modCount != expectedModCount) - throw new ConcurrentModificationException(); - lastReturned = next; - next = successor(next); - return lastReturned; + public NavigableMap subMap(K fromKey, boolean fromInclusive, + 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, fromInclusive, + false, toKey, toInclusive); } - public void remove() { - if (lastReturned == null) - throw new IllegalStateException(); - if (modCount != expectedModCount) - throw new ConcurrentModificationException(); - if (lastReturned.left != null && lastReturned.right != null) - next = lastReturned; - deleteEntry(lastReturned); - expectedModCount++; - lastReturned = null; + public NavigableMap headMap(K toKey, boolean inclusive) { + if (!inClosedRange(toKey)) + throw new IllegalArgumentException("toKey out of range"); + return new AscendingSubMap(m, + fromStart, lo, loInclusive, + false, toKey, inclusive); } - } - class EntryIterator extends PrivateEntryIterator> { - EntryIterator(Entry first) { - super(first); - } - public Map.Entry next() { - return nextEntry(); + public NavigableMap tailMap(K fromKey, boolean inclusive){ + if (!inRange(fromKey, inclusive)) + throw new IllegalArgumentException("fromKey out of range"); + return new AscendingSubMap(m, + false, fromKey, inclusive, + toEnd, hi, hiInclusive); } - } - class KeyIterator extends PrivateEntryIterator { - KeyIterator(Entry first) { - super(first); - } - public K next() { - return nextEntry().key; + public NavigableMap descendingMap() { + NavigableMap mv = descendingMapView; + return (mv != null) ? mv : + (descendingMapView = + new DescendingSubMap(m, + fromStart, lo, loInclusive, + toEnd, hi, hiInclusive)); } - } - class ValueIterator extends PrivateEntryIterator { - ValueIterator(Entry first) { - super(first); + Iterator keyIterator() { + return new SubMapKeyIterator(absLowest(), absHighFence()); } - public V next() { - return nextEntry().value; - } - } - - class SubMapEntryIterator extends PrivateEntryIterator> { - private final K firstExcludedKey; - SubMapEntryIterator(Entry first, Entry firstExcluded) { - super(first); - firstExcludedKey = (firstExcluded == null - ? null - : firstExcluded.key); + Iterator descendingKeyIterator() { + return new DescendingSubMapKeyIterator(absHighest(), absLowFence()); } - public boolean hasNext() { - return next != null && next.key != firstExcludedKey; + final class AscendingEntrySetView extends EntrySetView { + public Iterator> iterator() { + return new SubMapEntryIterator(absLowest(), absHighFence()); + } } - public Map.Entry next() { - if (next == null || next.key == firstExcludedKey) - throw new NoSuchElementException(); - return nextEntry(); + public Set> entrySet() { + EntrySetView es = entrySetView; + return (es != null) ? es : new AscendingEntrySetView(); } + + 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); } } /** - * Base for Descending Iterators. + * @serial include */ - abstract class DescendingPrivateEntryIterator extends PrivateEntryIterator { - DescendingPrivateEntryIterator(Entry first) { - super(first); + static final class DescendingSubMap extends NavigableSubMap { + private static final long serialVersionUID = 912986545866120460L; + DescendingSubMap(TreeMap m, + boolean fromStart, K lo, boolean loInclusive, + boolean toEnd, K hi, boolean hiInclusive) { + super(m, fromStart, lo, loInclusive, toEnd, hi, hiInclusive); } - Entry nextEntry() { - if (next == null) - throw new NoSuchElementException(); - if (modCount != expectedModCount) - throw new ConcurrentModificationException(); - lastReturned = next; - next = predecessor(next); - return lastReturned; - } - } + private final Comparator reverseComparator = + Collections.reverseOrder(m.comparator); - class DescendingEntryIterator extends DescendingPrivateEntryIterator> { - DescendingEntryIterator(Entry first) { - super(first); + public Comparator comparator() { + return reverseComparator; } - public Map.Entry next() { - return nextEntry(); + + public NavigableMap subMap(K fromKey, boolean fromInclusive, + 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, toInclusive, + false, fromKey, fromInclusive); } - } - class DescendingKeyIterator extends DescendingPrivateEntryIterator { - DescendingKeyIterator(Entry first) { - super(first); + public NavigableMap headMap(K toKey, boolean inclusive) { + if (!inRange(toKey, inclusive)) + throw new IllegalArgumentException("toKey out of range"); + return new DescendingSubMap(m, + false, toKey, inclusive, + toEnd, hi, hiInclusive); } - public K next() { - return nextEntry().key; + + public NavigableMap tailMap(K fromKey, boolean inclusive){ + if (!inRange(fromKey, inclusive)) + throw new IllegalArgumentException("fromKey out of range"); + return new DescendingSubMap(m, + fromStart, lo, loInclusive, + false, fromKey, inclusive); } - } + public NavigableMap descendingMap() { + NavigableMap mv = descendingMapView; + return (mv != null) ? mv : + (descendingMapView = + new AscendingSubMap(m, + fromStart, lo, loInclusive, + toEnd, hi, hiInclusive)); + } - class DescendingSubMapEntryIterator extends DescendingPrivateEntryIterator> { - private final K lastExcludedKey; + Iterator keyIterator() { + return new DescendingSubMapKeyIterator(absHighest(), absLowFence()); + } - DescendingSubMapEntryIterator(Entry last, Entry lastExcluded) { - super(last); - lastExcludedKey = (lastExcluded == null - ? null - : lastExcluded.key); + Iterator descendingKeyIterator() { + return new SubMapKeyIterator(absLowest(), absHighFence()); } - public boolean hasNext() { - return next != null && next.key != lastExcludedKey; + final class DescendingEntrySetView extends EntrySetView { + public Iterator> iterator() { + return new DescendingSubMapEntryIterator(absHighest(), absLowFence()); + } } - public Map.Entry next() { - if (next == null || next.key == lastExcludedKey) - throw new NoSuchElementException(); - return nextEntry(); + public Set> entrySet() { + EntrySetView es = entrySetView; + return (es != null) ? es : new DescendingEntrySetView(); } + 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); } } /** - * Compares two keys using the correct comparison method for this TreeMap. + * This class exists solely for the sake of serialization + * compatibility with previous releases of TreeMap that did not + * support NavigableMap. It translates an old-version SubMap into + * a new-version AscendingSubMap. This class is never otherwise + * used. + * + * @serial include */ - private int compare(Object k1, Object k2) { - return comparator==null ? ((Comparable)k1).compareTo((K)k2) - : comparator.compare((K)k1, (K)k2); + private class SubMap extends AbstractMap + implements SortedMap, java.io.Serializable { + private static final long serialVersionUID = -6520786458950516097L; + private boolean fromStart = false, toEnd = false; + private K fromKey, toKey; + private Object readResolve() { + return new AscendingSubMap(TreeMap.this, + fromStart, fromKey, true, + toEnd, toKey, false); + } + public Set> entrySet() { throw new InternalError(); } + public K lastKey() { throw new InternalError(); } + public K firstKey() { throw new InternalError(); } + public SortedMap subMap(K fromKey, K toKey) { throw new InternalError(); } + public SortedMap headMap(K toKey) { throw new InternalError(); } + public SortedMap tailMap(K fromKey) { throw new InternalError(); } + public Comparator comparator() { throw new InternalError(); } } - /** - * Test two values for equality. Differs from o1.equals(o2) only in - * that it copes with null o1 properly. - */ - private static boolean valEquals(Object o1, Object o2) { - return (o1==null ? o2==null : o1.equals(o2)); - } + + // Red-black mechanics private static final boolean RED = false; private static final boolean BLACK = true; @@ -1569,7 +1835,7 @@ public class TreeMap * user (see Map.Entry). */ - static class Entry implements Map.Entry { + static final class Entry implements Map.Entry { K key; V value; Entry left = null; @@ -1621,7 +1887,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()); } @@ -1641,7 +1907,7 @@ public class TreeMap * Returns the first Entry in the TreeMap (according to the TreeMap's * key-sort function). Returns null if the TreeMap is empty. */ - private Entry getFirstEntry() { + final Entry getFirstEntry() { Entry p = root; if (p != null) while (p.left != null) @@ -1653,7 +1919,7 @@ public class TreeMap * Returns the last Entry in the TreeMap (according to the TreeMap's * key-sort function). Returns null if the TreeMap is empty. */ - private Entry getLastEntry() { + final Entry getLastEntry() { Entry p = root; if (p != null) while (p.right != null) @@ -1664,7 +1930,7 @@ public class TreeMap /** * Returns the successor of the specified Entry, or null if no such. */ - private Entry successor(Entry t) { + static TreeMap.Entry successor(Entry t) { if (t == null) return null; else if (t.right != null) { @@ -1686,7 +1952,7 @@ public class TreeMap /** * Returns the predecessor of the specified Entry, or null if no such. */ - private Entry predecessor(Entry t) { + static Entry predecessor(Entry t) { if (t == null) return null; else if (t.left != null) { @@ -1736,40 +2002,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; @@ -1788,8 +2057,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))); @@ -1803,10 +2071,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))); } } } @@ -1816,9 +2083,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. @@ -1864,7 +2131,7 @@ public class TreeMap } } - /** From CLR **/ + /** From CLR */ private void fixAfterDeletion(Entry x) { while (x != root && colorOf(x) == BLACK) { if (x == leftOf(parentOf(x))) { @@ -1879,7 +2146,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) { @@ -1906,7 +2173,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) { @@ -1957,8 +2224,6 @@ public class TreeMap } } - - /** * Reconstitute the TreeMap instance from a stream (i.e., * deserialize it). @@ -1974,13 +2239,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);