--- jsr166/src/main/java/util/TreeMap.java 2005/07/18 01:14:34 1.23 +++ jsr166/src/main/java/util/TreeMap.java 2006/04/22 16:38:01 1.32 @@ -1,12 +1,11 @@ /* * %W% %E% * - * Copyright 2005 Sun Microsystems, Inc. All rights reserved. + * Copyright 2006 Sun Microsystems, Inc. All rights reserved. * SUN PROPRIETARY/CONFIDENTIAL. Use is subject to license terms. */ package java.util; -import java.util.*; // for javadoc (till 6280605 is fixed) /** * A Red-Black tree based {@link NavigableMap} implementation. @@ -96,7 +95,7 @@ public class TreeMap * * @serial */ - private Comparator comparator = null; + private final Comparator comparator; private transient Entry root = null; @@ -126,6 +125,7 @@ public class TreeMap * ClassCastException. */ public TreeMap() { + comparator = null; } /** @@ -161,6 +161,7 @@ public class TreeMap * @throws NullPointerException if the specified map is null */ public TreeMap(Map m) { + comparator = null; putAll(m); } @@ -227,7 +228,7 @@ public class TreeMap public boolean containsValue(Object value) { return (root==null ? false : (value==null ? valueSearchNull(root) - : valueSearchNonNull(root, value))); + : valueSearchNonNull(root, value))); } private boolean valueSearchNull(Entry n) { @@ -236,7 +237,7 @@ public class TreeMap // Check left and right subtrees for value return (n.left != null && valueSearchNull(n.left)) || - (n.right != null && valueSearchNull(n.right)); + (n.right != null && valueSearchNull(n.right)); } private boolean valueSearchNonNull(Entry n, Object value) { @@ -246,20 +247,25 @@ public class TreeMap // Check left and right subtrees for value return (n.left != null && valueSearchNonNull(n.left, value)) || - (n.right != null && valueSearchNonNull(n.right, value)); + (n.right != null && valueSearchNonNull(n.right, value)); } /** - * Returns the value to which this map maps the specified key, or - * null if the map contains no mapping for the key. A return - * value of null does not necessarily indicate that the - * map contains no mapping for the key; it's also possible that the map - * explicitly maps the key to null. The {@link #containsKey - * containsKey} operation may be used to distinguish these two cases. + * Returns the value to which the specified key is mapped, + * or {@code null} if this map contains no mapping for the key. + * + *

More formally, if this map contains a mapping from a key + * {@code k} to a value {@code v} such that {@code key} compares + * equal to {@code k} according to the map's ordering, then this + * method returns {@code v}; otherwise it returns {@code null}. + * (There can be at most one such mapping.) + * + *

A return value of {@code null} does not necessarily + * indicate that the map contains no mapping for the key; it's also + * possible that the map explicitly maps the key to {@code null}. + * The {@link #containsKey containsKey} operation may be used to + * distinguish these two cases. * - * @param key key whose associated value is to be returned - * @return the value to which this map maps the specified key, or - * null if the map contains no mapping for the key * @throws ClassCastException if the specified key cannot be compared * with the keys currently in the map * @throws NullPointerException if the specified key is null @@ -331,10 +337,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) { @@ -353,9 +361,9 @@ 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 here.) + * worthwhile for get and put.) */ - private Entry getEntryUsingComparator(Object key) { + final Entry getEntryUsingComparator(Object key) { K k = (K) key; Comparator cpr = comparator; Entry p = root; @@ -377,12 +385,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) @@ -404,6 +409,7 @@ public class TreeMap } else return p; } + return null; } /** @@ -411,12 +417,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) @@ -439,6 +442,7 @@ public class TreeMap return p; } + return null; } /** @@ -447,12 +451,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) @@ -473,6 +474,7 @@ public class TreeMap } } } + return null; } /** @@ -480,12 +482,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) @@ -506,13 +505,14 @@ public class TreeMap } } } + return null; } /** * Returns the key corresponding to the specified Entry. * @throws NoSuchElementException if the Entry is null */ - private static K key(Entry e) { + static K key(Entry e) { if (e==null) throw new NoSuchElementException(); return e.key; @@ -537,22 +537,50 @@ public class TreeMap * does not permit null keys */ public V put(K key, V value) { - Entry t = root; + // 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; - if (t == null) { - // TBD -// if (key == null) { -// if (comparator == null) -// throw new NullPointerException(); -// comparator.compare(key, key); -// } - incrementSize(); - root = new Entry(key, value, null); - return null; + 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) { + t = t.left; + } else { + incrementSize(); + fixAfterInsertion(t.left = new Entry(key, value, t)); + return null; + } + } else { // cmp > 0 + if (t.right != null) { + t = t.right; + } else { + incrementSize(); + fixAfterInsertion(t.right = new Entry(key, value, t)); + return null; + } + } } + incrementSize(); + root = new Entry(key, value, null); + return null; + } - while (true) { - int cmp = compare(key, t.key); + /** + * 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) { @@ -560,8 +588,7 @@ public class TreeMap t = t.left; } else { incrementSize(); - t.left = new Entry(key, value, t); - fixAfterInsertion(t.left); + fixAfterInsertion(t.left = new Entry(key, value, t)); return null; } } else { // cmp > 0 @@ -569,12 +596,15 @@ public class TreeMap t = t.right; } else { incrementSize(); - t.right = new Entry(key, value, t); - fixAfterInsertion(t.right); + fixAfterInsertion(t.right = new Entry(key, value, t)); return null; } } } + cpr.compare(key, key); // type check + incrementSize(); + root = new Entry(key, value, null); + return null; } /** @@ -630,8 +660,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 { @@ -788,9 +818,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. @@ -807,32 +837,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(); } /** @@ -855,6 +875,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()); @@ -886,26 +1015,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()); @@ -942,324 +1051,482 @@ 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()); - } - class DescendingEntrySet extends EntrySet { - public Iterator> iterator() { - return new DescendingEntryIterator(getLastEntry()); - } + Iterator keyIterator() { + return new KeyIterator(getFirstEntry()); } - /** - * @since 1.6 - */ - public Set descendingKeySet() { - Set ks = descendingKeySet; - return (ks != null) ? ks : (descendingKeySet = new DescendingKeySet()); + Iterator descendingKeyIterator() { + return new DescendingKeyIterator(getFirstEntry()); } - class DescendingKeySet extends KeySet { - public Iterator iterator() { - return new DescendingKeyIterator(getLastEntry()); + 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()); } - } - /** - * @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); + 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()); + } } /** - * @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 + * Base class for TreeMap Iterators */ - public NavigableMap navigableHeadMap(K toKey) { - return new SubMap(toKey, true); + 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; + } } - /** - * @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 navigableTailMap(K fromKey) { - return new SubMap(fromKey, false); + final class EntryIterator extends PrivateEntryIterator> { + EntryIterator(Entry first) { + super(first); + } + public Map.Entry next() { + return nextEntry(); + } } - /** - * 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} - */ - public SortedMap subMap(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; + } } - /** - * 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} - */ - public SortedMap headMap(K toKey) { - return new SubMap(toKey, true); + final class KeyIterator extends PrivateEntryIterator { + KeyIterator(Entry first) { + super(first); + } + public K next() { + return nextEntry().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} - */ - public SortedMap tailMap(K fromKey) { - return new SubMap(fromKey, false); + final class DescendingKeyIterator extends PrivateEntryIterator { + DescendingKeyIterator(Entry first) { + super(first); + } + public K next() { + return prevEntry().key; + } } - private class SubMap - extends AbstractMap - implements NavigableMap, java.io.Serializable { - private static final long serialVersionUID = -6520786458950516097L; + // SubMaps - /** - * fromKey is significant only if fromStart is false. Similarly, - * toKey is significant only if toStart is false. + static abstract class NavigableSubMap extends AbstractMap + implements NavigableMap, java.io.Serializable { + /* + * 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; - } + /* + * 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. + */ - SubMap(K key, boolean headMap) { - compare(key, key); // Type-check key - - if (headMap) { - fromStart = true; - toKey = key; + 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); + } + + /** + * 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 exportKey(TreeMap.Entry e) { + return e == null? null : e.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 exportKey(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 exportKey(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 exportKey(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 exportKey(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++; @@ -1270,7 +1537,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) { @@ -1280,9 +1548,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) { @@ -1292,271 +1560,308 @@ 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 final boolean hasNext() { + return next != null && next.key != fenceKey; + } - public boolean hasNext() { return i.hasNext(); } - public K next() { return i.next().getKey(); } - public void remove() { i.remove(); } - }; + 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 int size() { - return SubMap.this.size(); + 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 boolean contains(Object k) { - return SubMap.this.containsKey(k); + 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 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); + final class SubMapEntryIterator extends SubMapIterator> { + SubMapEntryIterator(TreeMap.Entry first, + TreeMap.Entry fence) { + super(first, fence); + } + public Map.Entry next() { + return nextEntry(); + } } - public NavigableMap navigableHeadMap(K toKey) { - if (!inRange2(toKey)) - throw new IllegalArgumentException("toKey out of range"); - return new SubMap(fromStart, fromKey, false, toKey); + final class SubMapKeyIterator extends SubMapIterator { + SubMapKeyIterator(TreeMap.Entry first, + TreeMap.Entry fence) { + super(first, fence); + } + public K next() { + return nextEntry().key; + } } - public NavigableMap navigableTailMap(K fromKey) { - if (!inRange2(fromKey)) - throw new IllegalArgumentException("fromKey out of range"); - return new SubMap(false, fromKey, toEnd, toKey); - } + final class DescendingSubMapEntryIterator extends SubMapIterator> { + DescendingSubMapEntryIterator(TreeMap.Entry last, + TreeMap.Entry fence) { + super(last, fence); + } - public SortedMap subMap(K fromKey, K toKey) { - return navigableSubMap(fromKey, toKey); + public Map.Entry next() { + return prevEntry(); + } } - public SortedMap headMap(K toKey) { - return navigableHeadMap(toKey); + final class DescendingSubMapKeyIterator extends SubMapIterator { + DescendingSubMapKeyIterator(TreeMap.Entry last, + TreeMap.Entry fence) { + super(last, fence); + } + public K next() { + return prevEntry().key; + } } + } - public SortedMap tailMap(K fromKey) { - return navigableTailMap(fromKey); - } + static final class AscendingSubMap extends NavigableSubMap { + private static final long serialVersionUID = 912986545866124060L; - private boolean inRange(Object key) { - return (fromStart || compare(key, fromKey) >= 0) && - (toEnd || compare(key, toKey) < 0); + AscendingSubMap(TreeMap m, + boolean fromStart, K lo, boolean loInclusive, + boolean toEnd, K hi, boolean hiInclusive) { + super(m, fromStart, lo, loInclusive, toEnd, hi, hiInclusive); } - // 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); + public Comparator comparator() { + return m.comparator(); } - } - /** - * TreeMap Iterator. - */ - abstract class PrivateEntryIterator implements Iterator { - int expectedModCount = TreeMap.this.modCount; - Entry lastReturned = null; - Entry next; - - PrivateEntryIterator(Entry first) { - next = first; + 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 boolean hasNext() { - return next != 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); } - Entry nextEntry() { - if (next == null) - throw new NoSuchElementException(); - if (modCount != expectedModCount) - throw new ConcurrentModificationException(); - lastReturned = next; - next = successor(next); - return lastReturned; + 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); } - 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 descendingMap() { + NavigableMap mv = descendingMapView; + return (mv != null) ? mv : + (descendingMapView = + new DescendingSubMap(m, + fromStart, lo, loInclusive, + toEnd, hi, hiInclusive)); } - } - class EntryIterator extends PrivateEntryIterator> { - EntryIterator(Entry first) { - super(first); + Iterator keyIterator() { + return new SubMapKeyIterator(absLowest(), absHighFence()); } - public Map.Entry next() { - return nextEntry(); - } - } - class KeyIterator extends PrivateEntryIterator { - KeyIterator(Entry first) { - super(first); - } - public K next() { - return nextEntry().key; + Iterator descendingKeyIterator() { + return new DescendingSubMapKeyIterator(absHighest(), absLowFence()); } - } - class ValueIterator extends PrivateEntryIterator { - ValueIterator(Entry first) { - super(first); + final class AscendingEntrySetView extends EntrySetView { + public Iterator> iterator() { + return new SubMapEntryIterator(absLowest(), absHighFence()); + } } - public V next() { - return nextEntry().value; + + public Set> entrySet() { + EntrySetView es = entrySetView; + return (es != null) ? es : new AscendingEntrySetView(); } - } - class SubMapEntryIterator extends PrivateEntryIterator> { - private final K firstExcludedKey; + 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); } + } - SubMapEntryIterator(Entry first, Entry firstExcluded) { - super(first); - firstExcludedKey = (firstExcluded == null - ? null - : firstExcluded.key); + 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); } - public boolean hasNext() { - return next != null && next.key != firstExcludedKey; - } + private final Comparator reverseComparator = + Collections.reverseOrder(m.comparator); - public Map.Entry next() { - if (next == null || next.key == firstExcludedKey) - throw new NoSuchElementException(); - return nextEntry(); + public Comparator comparator() { + return reverseComparator; } - } - /** - * Base for Descending Iterators. - */ - abstract class DescendingPrivateEntryIterator extends PrivateEntryIterator { - DescendingPrivateEntryIterator(Entry first) { - super(first); + 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); } - Entry nextEntry() { - if (next == null) - throw new NoSuchElementException(); - if (modCount != expectedModCount) - throw new ConcurrentModificationException(); - lastReturned = next; - next = predecessor(next); - return lastReturned; + 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); } - } - class DescendingEntryIterator extends DescendingPrivateEntryIterator> { - DescendingEntryIterator(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 DescendingSubMap(m, + fromStart, lo, loInclusive, + false, fromKey, inclusive); } - } - class DescendingKeyIterator extends DescendingPrivateEntryIterator { - DescendingKeyIterator(Entry first) { - super(first); - } - public K next() { - return nextEntry().key; + 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. */ - private int compare(Object k1, Object k2) { + final int compare(Object k1, Object k2) { return comparator==null ? ((Comparable)k1).compareTo((K)k2) - : comparator.compare((K)k1, (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. */ - private static boolean valEquals(Object o1, Object o2) { + final static boolean valEquals(Object o1, Object o2) { return (o1==null ? o2==null : o1.equals(o2)); } + /** + * 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. + */ + 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(); } + } + + private static final boolean RED = false; private static final boolean BLACK = true; @@ -1565,7 +1870,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; @@ -1637,7 +1942,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) @@ -1649,7 +1954,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) @@ -1660,7 +1965,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) { @@ -1682,7 +1987,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) { @@ -1799,7 +2104,7 @@ 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))); @@ -1875,7 +2180,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) { @@ -1902,7 +2207,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) { @@ -1953,8 +2258,6 @@ public class TreeMap } } - - /** * Reconstitute the TreeMap instance from a stream (i.e., * deserialize it). @@ -2016,20 +2319,18 @@ public class TreeMap * @throws ClassNotFoundException propagated from readObject. * This cannot occur if str is null. */ - private - void buildFromSorted(int size, Iterator it, - java.io.ObjectInputStream str, - V defaultVal) + private void buildFromSorted(int size, Iterator it, + java.io.ObjectInputStream str, + V defaultVal) throws java.io.IOException, ClassNotFoundException { this.size = size; - root = - buildFromSorted(0, 0, size-1, computeRedLevel(size), - it, str, defaultVal); + root = buildFromSorted(0, 0, size-1, computeRedLevel(size), + it, str, defaultVal); } /** * Recursive "helper method" that does the real work of the - * of the previous method. Identically named parameters have + * previous method. Identically named parameters have * identical definitions. Additional parameters are documented below. * It is assumed that the comparator and size fields of the TreeMap are * already set prior to calling this method. (It ignores both fields.)