diff -r 000000000000 -r 724f3e1ea53e emul/compact/src/main/java/java/util/TreeMap.java
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/emul/compact/src/main/java/java/util/TreeMap.java Sat Sep 07 13:51:24 2013 +0200
@@ -0,0 +1,2442 @@
+/*
+ * Copyright (c) 1997, 2011, Oracle and/or its affiliates. All rights reserved.
+ * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
+ *
+ * This code is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License version 2 only, as
+ * published by the Free Software Foundation. Oracle designates this
+ * particular file as subject to the "Classpath" exception as provided
+ * by Oracle in the LICENSE file that accompanied this code.
+ *
+ * This code is distributed in the hope that it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
+ * version 2 for more details (a copy is included in the LICENSE file that
+ * accompanied this code).
+ *
+ * You should have received a copy of the GNU General Public License version
+ * 2 along with this work; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
+ *
+ * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
+ * or visit www.oracle.com if you need additional information or have any
+ * questions.
+ */
+
+package java.util;
+
+/**
+ * A Red-Black tree based {@link NavigableMap} implementation.
+ * The map is sorted according to the {@linkplain Comparable natural
+ * ordering} of its keys, or by a {@link Comparator} provided at map
+ * creation time, depending on which constructor is used.
+ *
+ * This implementation provides guaranteed log(n) time cost for the
+ * {@code containsKey}, {@code get}, {@code put} and {@code remove}
+ * operations. Algorithms are adaptations of those in Cormen, Leiserson, and
+ * Rivest's Introduction to Algorithms.
+ *
+ *
Note that the ordering maintained by a tree map, like any sorted map, and
+ * whether or not an explicit comparator is provided, must be consistent
+ * with {@code equals} if this sorted map is to correctly implement the
+ * {@code Map} interface. (See {@code Comparable} or {@code Comparator} for a
+ * precise definition of consistent with equals.) This is so because
+ * the {@code Map} interface is defined in terms of the {@code equals}
+ * operation, but a sorted map performs all key comparisons using its {@code
+ * compareTo} (or {@code compare}) method, so two keys that are deemed equal by
+ * this method are, from the standpoint of the sorted map, equal. The behavior
+ * of a sorted map is well-defined even if its ordering is
+ * inconsistent with {@code equals}; it just fails to obey the general contract
+ * of the {@code Map} interface.
+ *
+ *
Note that this implementation is not synchronized.
+ * If multiple threads access a map concurrently, and at least one of the
+ * threads modifies the map structurally, it must be synchronized
+ * externally. (A structural modification is any operation that adds or
+ * deletes one or more mappings; merely changing the value associated
+ * with an existing key is not a structural modification.) This is
+ * typically accomplished by synchronizing on some object that naturally
+ * encapsulates the map.
+ * If no such object exists, the map should be "wrapped" using the
+ * {@link Collections#synchronizedSortedMap Collections.synchronizedSortedMap}
+ * method. This is best done at creation time, to prevent accidental
+ * unsynchronized access to the map:
+ * SortedMap m = Collections.synchronizedSortedMap(new TreeMap(...));
+ *
+ * The iterators returned by the {@code iterator} method of the collections
+ * returned by all of this class's "collection view methods" are
+ * fail-fast: if the map is structurally modified at any time after
+ * the iterator is created, in any way except through the iterator's own
+ * {@code remove} method, the iterator will throw a {@link
+ * ConcurrentModificationException}. Thus, in the face of concurrent
+ * modification, the iterator fails quickly and cleanly, rather than risking
+ * arbitrary, non-deterministic behavior at an undetermined time in the future.
+ *
+ *
Note that the fail-fast behavior of an iterator cannot be guaranteed
+ * as it is, generally speaking, impossible to make any hard guarantees in the
+ * presence of unsynchronized concurrent modification. Fail-fast iterators
+ * throw {@code ConcurrentModificationException} on a best-effort basis.
+ * Therefore, it would be wrong to write a program that depended on this
+ * exception for its correctness: the fail-fast behavior of iterators
+ * should be used only to detect bugs.
+ *
+ *
All {@code Map.Entry} pairs returned by methods in this class
+ * and its views represent snapshots of mappings at the time they were
+ * produced. They do not support the {@code Entry.setValue}
+ * method. (Note however that it is possible to change mappings in the
+ * associated map using {@code put}.)
+ *
+ *
This class is a member of the
+ *
+ * Java Collections Framework.
+ *
+ * @param the type of keys maintained by this map
+ * @param the type of mapped values
+ *
+ * @author Josh Bloch and Doug Lea
+ * @see Map
+ * @see HashMap
+ * @see Hashtable
+ * @see Comparable
+ * @see Comparator
+ * @see Collection
+ * @since 1.2
+ */
+
+public class TreeMap
+ extends AbstractMap
+ implements NavigableMap, Cloneable, java.io.Serializable
+{
+ /**
+ * The comparator used to maintain order in this tree map, or
+ * null if it uses the natural ordering of its keys.
+ *
+ * @serial
+ */
+ private final Comparator comparator;
+
+ private transient Entry root = null;
+
+ /**
+ * The number of entries in the tree
+ */
+ private transient int size = 0;
+
+ /**
+ * The number of structural modifications to the tree.
+ */
+ private transient int modCount = 0;
+
+ /**
+ * Constructs a new, empty tree map, using the natural ordering of its
+ * keys. All keys inserted into the map must implement the {@link
+ * Comparable} interface. Furthermore, all such keys must be
+ * mutually comparable: {@code k1.compareTo(k2)} must not throw
+ * a {@code ClassCastException} for any keys {@code k1} and
+ * {@code k2} in the map. If the user attempts to put a key into the
+ * map that violates this constraint (for example, the user attempts to
+ * put a string key into a map whose keys are integers), the
+ * {@code put(Object key, Object value)} call will throw a
+ * {@code ClassCastException}.
+ */
+ public TreeMap() {
+ comparator = null;
+ }
+
+ /**
+ * Constructs a new, empty tree map, ordered according to the given
+ * comparator. All keys inserted into the map must be mutually
+ * comparable by the given comparator: {@code comparator.compare(k1,
+ * k2)} must not throw a {@code ClassCastException} for any keys
+ * {@code k1} and {@code k2} in the map. If the user attempts to put
+ * a key into the map that violates this constraint, the {@code put(Object
+ * key, Object value)} call will throw a
+ * {@code ClassCastException}.
+ *
+ * @param comparator the comparator that will be used to order this map.
+ * If {@code null}, the {@linkplain Comparable natural
+ * ordering} of the keys will be used.
+ */
+ public TreeMap(Comparator comparator) {
+ this.comparator = comparator;
+ }
+
+ /**
+ * Constructs a new tree map containing the same mappings as the given
+ * map, ordered according to the natural ordering of its keys.
+ * All keys inserted into the new map must implement the {@link
+ * Comparable} interface. Furthermore, all such keys must be
+ * mutually comparable: {@code k1.compareTo(k2)} must not throw
+ * a {@code ClassCastException} for any keys {@code k1} and
+ * {@code k2} in the map. This method runs in n*log(n) time.
+ *
+ * @param m the map whose mappings are to be placed in this map
+ * @throws ClassCastException if the keys in m are not {@link Comparable},
+ * or are not mutually comparable
+ * @throws NullPointerException if the specified map is null
+ */
+ public TreeMap(Map m) {
+ comparator = null;
+ putAll(m);
+ }
+
+ /**
+ * Constructs a new tree map containing the same mappings and
+ * using the same ordering as the specified sorted map. This
+ * method runs in linear time.
+ *
+ * @param m the sorted map whose mappings are to be placed in this map,
+ * and whose comparator is to be used to sort this map
+ * @throws NullPointerException if the specified map is null
+ */
+ public TreeMap(SortedMap m) {
+ comparator = m.comparator();
+ try {
+ buildFromSorted(m.size(), m.entrySet().iterator(), null, null);
+ } catch (java.io.IOException cannotHappen) {
+ } catch (ClassNotFoundException cannotHappen) {
+ }
+ }
+
+
+ // Query Operations
+
+ /**
+ * Returns the number of key-value mappings in this map.
+ *
+ * @return the number of key-value mappings in this map
+ */
+ public int size() {
+ return size;
+ }
+
+ /**
+ * Returns {@code true} if this map contains a mapping for the specified
+ * key.
+ *
+ * @param key key whose presence in this map is to be tested
+ * @return {@code true} if this map contains a mapping for the
+ * specified 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
+ * and this map uses natural ordering, or its comparator
+ * does not permit null keys
+ */
+ public boolean containsKey(Object key) {
+ return getEntry(key) != null;
+ }
+
+ /**
+ * Returns {@code true} if this map maps one or more keys to the
+ * specified value. More formally, returns {@code true} if and only if
+ * this map contains at least one mapping to a value {@code v} such
+ * that {@code (value==null ? v==null : value.equals(v))}. This
+ * operation will probably require time linear in the map size for
+ * most implementations.
+ *
+ * @param value value whose presence in this map is to be tested
+ * @return {@code true} if a mapping to {@code value} exists;
+ * {@code false} otherwise
+ * @since 1.2
+ */
+ public boolean containsValue(Object value) {
+ for (Entry e = getFirstEntry(); e != null; e = successor(e))
+ if (valEquals(value, e.value))
+ return true;
+ return false;
+ }
+
+ /**
+ * 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.
+ *
+ * @throws ClassCastException if the specified key cannot be compared
+ * with the keys currently in the map
+ * @throws NullPointerException if the specified key is null
+ * and this map uses natural ordering, or its comparator
+ * does not permit null keys
+ */
+ public V get(Object key) {
+ Entry p = getEntry(key);
+ return (p==null ? null : p.value);
+ }
+
+ public Comparator comparator() {
+ return comparator;
+ }
+
+ /**
+ * @throws NoSuchElementException {@inheritDoc}
+ */
+ public K firstKey() {
+ return key(getFirstEntry());
+ }
+
+ /**
+ * @throws NoSuchElementException {@inheritDoc}
+ */
+ public K lastKey() {
+ return key(getLastEntry());
+ }
+
+ /**
+ * Copies all of the mappings from the specified map to this map.
+ * These mappings replace any mappings that this map had for any
+ * of the keys currently in the specified map.
+ *
+ * @param map mappings to be stored in this map
+ * @throws ClassCastException if the class of a key or value in
+ * the specified map prevents it from being stored in this map
+ * @throws NullPointerException if the specified map is null or
+ * the specified map contains a null key and this map does not
+ * permit null keys
+ */
+ public void putAll(Map map) {
+ int mapSize = map.size();
+ if (size==0 && mapSize!=0 && map instanceof SortedMap) {
+ Comparator c = ((SortedMap)map).comparator();
+ if (c == comparator || (c != null && c.equals(comparator))) {
+ ++modCount;
+ try {
+ buildFromSorted(mapSize, map.entrySet().iterator(),
+ null, null);
+ } catch (java.io.IOException cannotHappen) {
+ } catch (ClassNotFoundException cannotHappen) {
+ }
+ return;
+ }
+ }
+ super.putAll(map);
+ }
+
+ /**
+ * Returns this map's entry for the given key, or {@code null} if the map
+ * does not contain an entry for the key.
+ *
+ * @return this map's entry for the given key, or {@code null} if the map
+ * does not contain an entry 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
+ * and this map uses natural ordering, or its comparator
+ * does not permit null keys
+ */
+ 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) {
+ int cmp = k.compareTo(p.key);
+ if (cmp < 0)
+ p = p.left;
+ else if (cmp > 0)
+ p = p.right;
+ else
+ return p;
+ }
+ return null;
+ }
+
+ /**
+ * 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.)
+ */
+ final Entry getEntryUsingComparator(Object key) {
+ K k = (K) key;
+ Comparator cpr = comparator;
+ 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;
+ }
+
+ /**
+ * Gets the entry corresponding to the specified key; if no such entry
+ * exists, returns the entry for the least key greater than the specified
+ * key; if no such entry exists (i.e., the greatest key in the Tree is less
+ * than the specified key), returns {@code null}.
+ */
+ final Entry getCeilingEntry(K key) {
+ Entry p = root;
+ while (p != null) {
+ int cmp = compare(key, p.key);
+ if (cmp < 0) {
+ if (p.left != null)
+ p = p.left;
+ else
+ return p;
+ } else if (cmp > 0) {
+ if (p.right != null) {
+ p = p.right;
+ } else {
+ Entry parent = p.parent;
+ Entry ch = p;
+ while (parent != null && ch == parent.right) {
+ ch = parent;
+ parent = parent.parent;
+ }
+ return parent;
+ }
+ } else
+ return p;
+ }
+ return null;
+ }
+
+ /**
+ * Gets the entry corresponding to the specified key; if no such entry
+ * exists, returns the entry for the greatest key less than the specified
+ * key; if no such entry exists, returns {@code null}.
+ */
+ final Entry getFloorEntry(K key) {
+ Entry p = root;
+ while (p != null) {
+ int cmp = compare(key, p.key);
+ if (cmp > 0) {
+ if (p.right != null)
+ p = p.right;
+ else
+ return p;
+ } else if (cmp < 0) {
+ if (p.left != null) {
+ p = p.left;
+ } else {
+ Entry parent = p.parent;
+ Entry ch = p;
+ while (parent != null && ch == parent.left) {
+ ch = parent;
+ parent = parent.parent;
+ }
+ return parent;
+ }
+ } else
+ return p;
+
+ }
+ return null;
+ }
+
+ /**
+ * Gets the entry for the least key greater than the specified
+ * key; if no such entry exists, returns the entry for the least
+ * key greater than the specified key; if no such entry exists
+ * returns {@code null}.
+ */
+ final Entry getHigherEntry(K key) {
+ Entry p = root;
+ while (p != null) {
+ int cmp = compare(key, p.key);
+ if (cmp < 0) {
+ if (p.left != null)
+ p = p.left;
+ else
+ return p;
+ } else {
+ if (p.right != null) {
+ p = p.right;
+ } else {
+ Entry parent = p.parent;
+ Entry ch = p;
+ while (parent != null && ch == parent.right) {
+ ch = parent;
+ parent = parent.parent;
+ }
+ return parent;
+ }
+ }
+ }
+ return null;
+ }
+
+ /**
+ * Returns the entry for the greatest key less than the specified key; if
+ * no such entry exists (i.e., the least key in the Tree is greater than
+ * the specified key), returns {@code null}.
+ */
+ final Entry getLowerEntry(K key) {
+ Entry p = root;
+ while (p != null) {
+ int cmp = compare(key, p.key);
+ if (cmp > 0) {
+ if (p.right != null)
+ p = p.right;
+ else
+ return p;
+ } else {
+ if (p.left != null) {
+ p = p.left;
+ } else {
+ Entry parent = p.parent;
+ Entry ch = p;
+ while (parent != null && ch == parent.left) {
+ ch = parent;
+ parent = parent.parent;
+ }
+ return parent;
+ }
+ }
+ }
+ return null;
+ }
+
+ /**
+ * Associates the specified value with the specified key in this map.
+ * If the map previously contained a mapping for the key, the old
+ * value is replaced.
+ *
+ * @param key key with which the specified value is to be associated
+ * @param value value to be associated with the specified key
+ *
+ * @return the previous value associated with {@code key}, or
+ * {@code null} if there was no mapping for {@code key}.
+ * (A {@code null} return can also indicate that the map
+ * previously associated {@code null} with {@code 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
+ * and this map uses natural ordering, or its comparator
+ * does not permit null keys
+ */
+ public V put(K key, V value) {
+ Entry t = root;
+ if (t == null) {
+ compare(key, key); // type (and possibly null) check
+
+ root = new Entry<>(key, value, null);
+ size = 1;
+ modCount++;
+ return null;
+ }
+ int cmp;
+ Entry parent;
+ // split comparator and comparable paths
+ Comparator cpr = comparator;
+ if (cpr != null) {
+ do {
+ parent = t;
+ cmp = cpr.compare(key, t.key);
+ if (cmp < 0)
+ t = t.left;
+ else if (cmp > 0)
+ t = t.right;
+ 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;
+ }
+
+ /**
+ * Removes the mapping for this key from this TreeMap if present.
+ *
+ * @param key key for which mapping should be removed
+ * @return the previous value associated with {@code key}, or
+ * {@code null} if there was no mapping for {@code key}.
+ * (A {@code null} return can also indicate that the map
+ * previously associated {@code null} with {@code 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
+ * and this map uses natural ordering, or its comparator
+ * does not permit null keys
+ */
+ public V remove(Object key) {
+ Entry p = getEntry(key);
+ if (p == null)
+ return null;
+
+ V oldValue = p.value;
+ deleteEntry(p);
+ return oldValue;
+ }
+
+ /**
+ * Removes all of the mappings from this map.
+ * The map will be empty after this call returns.
+ */
+ public void clear() {
+ modCount++;
+ size = 0;
+ root = null;
+ }
+
+ /**
+ * Returns a shallow copy of this {@code TreeMap} instance. (The keys and
+ * values themselves are not cloned.)
+ *
+ * @return a shallow copy of this map
+ */
+ public Object clone() {
+ TreeMap clone = null;
+ try {
+ clone = (TreeMap) super.clone();
+ } catch (CloneNotSupportedException e) {
+ throw new InternalError();
+ }
+
+ // Put clone into "virgin" state (except for comparator)
+ clone.root = null;
+ clone.size = 0;
+ clone.modCount = 0;
+ clone.entrySet = null;
+ clone.navigableKeySet = null;
+ clone.descendingMap = null;
+
+ // Initialize clone with our mappings
+ try {
+ clone.buildFromSorted(size, entrySet().iterator(), null, null);
+ } catch (java.io.IOException cannotHappen) {
+ } catch (ClassNotFoundException cannotHappen) {
+ }
+
+ return clone;
+ }
+
+ // NavigableMap API methods
+
+ /**
+ * @since 1.6
+ */
+ public Map.Entry firstEntry() {
+ return exportEntry(getFirstEntry());
+ }
+
+ /**
+ * @since 1.6
+ */
+ public Map.Entry lastEntry() {
+ return exportEntry(getLastEntry());
+ }
+
+ /**
+ * @since 1.6
+ */
+ public Map.Entry pollFirstEntry() {
+ Entry p = getFirstEntry();
+ Map.Entry result = exportEntry(p);
+ if (p != null)
+ deleteEntry(p);
+ return result;
+ }
+
+ /**
+ * @since 1.6
+ */
+ public Map.Entry pollLastEntry() {
+ Entry p = getLastEntry();
+ Map.Entry result = exportEntry(p);
+ if (p != null)
+ deleteEntry(p);
+ return result;
+ }
+
+ /**
+ * @throws ClassCastException {@inheritDoc}
+ * @throws NullPointerException if the specified key is null
+ * and this map uses natural ordering, or its comparator
+ * does not permit null keys
+ * @since 1.6
+ */
+ public Map.Entry lowerEntry(K key) {
+ return exportEntry(getLowerEntry(key));
+ }
+
+ /**
+ * @throws ClassCastException {@inheritDoc}
+ * @throws NullPointerException if the specified key is null
+ * and this map uses natural ordering, or its comparator
+ * does not permit null keys
+ * @since 1.6
+ */
+ public K lowerKey(K key) {
+ return keyOrNull(getLowerEntry(key));
+ }
+
+ /**
+ * @throws ClassCastException {@inheritDoc}
+ * @throws NullPointerException if the specified key is null
+ * and this map uses natural ordering, or its comparator
+ * does not permit null keys
+ * @since 1.6
+ */
+ public Map.Entry floorEntry(K key) {
+ return exportEntry(getFloorEntry(key));
+ }
+
+ /**
+ * @throws ClassCastException {@inheritDoc}
+ * @throws NullPointerException if the specified key is null
+ * and this map uses natural ordering, or its comparator
+ * does not permit null keys
+ * @since 1.6
+ */
+ public K floorKey(K key) {
+ return keyOrNull(getFloorEntry(key));
+ }
+
+ /**
+ * @throws ClassCastException {@inheritDoc}
+ * @throws NullPointerException if the specified key is null
+ * and this map uses natural ordering, or its comparator
+ * does not permit null keys
+ * @since 1.6
+ */
+ public Map.Entry ceilingEntry(K key) {
+ return exportEntry(getCeilingEntry(key));
+ }
+
+ /**
+ * @throws ClassCastException {@inheritDoc}
+ * @throws NullPointerException if the specified key is null
+ * and this map uses natural ordering, or its comparator
+ * does not permit null keys
+ * @since 1.6
+ */
+ public K ceilingKey(K key) {
+ return keyOrNull(getCeilingEntry(key));
+ }
+
+ /**
+ * @throws ClassCastException {@inheritDoc}
+ * @throws NullPointerException if the specified key is null
+ * and this map uses natural ordering, or its comparator
+ * does not permit null keys
+ * @since 1.6
+ */
+ public Map.Entry higherEntry(K key) {
+ return exportEntry(getHigherEntry(key));
+ }
+
+ /**
+ * @throws ClassCastException {@inheritDoc}
+ * @throws NullPointerException if the specified key is null
+ * and this map uses natural ordering, or its comparator
+ * does not permit null keys
+ * @since 1.6
+ */
+ public K higherKey(K key) {
+ return keyOrNull(getHigherEntry(key));
+ }
+
+ // Views
+
+ /**
+ * Fields initialized to contain an instance of the entry set view
+ * the first time this view is requested. Views are stateless, so
+ * there's no reason to create more than one.
+ */
+ 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.
+ * The set's iterator returns the keys in ascending 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 {@code remove} operation), the results of
+ * the iteration are undefined. The set supports element removal,
+ * which removes the corresponding mapping from the map, via the
+ * {@code Iterator.remove}, {@code Set.remove},
+ * {@code removeAll}, {@code retainAll}, and {@code clear}
+ * operations. It does not support the {@code add} or {@code addAll}
+ * operations.
+ */
+ public Set keySet() {
+ return navigableKeySet();
+ }
+
+ /**
+ * @since 1.6
+ */
+ public NavigableSet navigableKeySet() {
+ KeySet nks = navigableKeySet;
+ return (nks != null) ? nks : (navigableKeySet = new KeySet(this));
+ }
+
+ /**
+ * @since 1.6
+ */
+ public NavigableSet descendingKeySet() {
+ return descendingMap().navigableKeySet();
+ }
+
+ /**
+ * Returns a {@link Collection} view of the values contained in this map.
+ * The collection's iterator returns the values in ascending order
+ * of the corresponding keys.
+ * The collection is backed by the map, so changes to the map are
+ * reflected in the collection, and vice-versa. If the map is
+ * modified while an iteration over the collection is in progress
+ * (except through the iterator's own {@code remove} operation),
+ * the results of the iteration are undefined. The collection
+ * supports element removal, which removes the corresponding
+ * mapping from the map, via the {@code Iterator.remove},
+ * {@code Collection.remove}, {@code removeAll},
+ * {@code retainAll} and {@code clear} operations. It does not
+ * support the {@code add} or {@code addAll} operations.
+ */
+ public Collection values() {
+ Collection vs = values;
+ 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 {@code remove} operation, or through the
+ * {@code 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 {@code Iterator.remove},
+ * {@code Set.remove}, {@code removeAll}, {@code retainAll} and
+ * {@code clear} operations. It does not support the
+ * {@code add} or {@code 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 {@code fromKey} or {@code 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 {@code 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 {@code 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 {@code fromKey} or {@code 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 {@code 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 {@code 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());
+ }
+
+ public int size() {
+ return TreeMap.this.size();
+ }
+
+ public boolean contains(Object o) {
+ return TreeMap.this.containsValue(o);
+ }
+
+ public boolean remove(Object o) {
+ for (Entry e = getFirstEntry(); e != null; e = successor(e)) {
+ if (valEquals(e.getValue(), o)) {
+ deleteEntry(e);
+ return true;
+ }
+ }
+ return false;
+ }
+
+ public void clear() {
+ TreeMap.this.clear();
+ }
+ }
+
+ class EntrySet extends AbstractSet> {
+ public Iterator> iterator() {
+ return new EntryIterator(getFirstEntry());
+ }
+
+ public boolean contains(Object o) {
+ if (!(o instanceof Map.Entry))
+ return false;
+ Map.Entry entry = (Map.Entry) o;
+ V value = entry.getValue();
+ Entry p = getEntry(entry.getKey());
+ return p != null && valEquals(p.getValue(), value);
+ }
+
+ public boolean remove(Object o) {
+ if (!(o instanceof Map.Entry))
+ return false;
+ Map.Entry entry = (Map.Entry) o;
+ V value = entry.getValue();
+ Entry p = getEntry(entry.getKey());
+ if (p != null && valEquals(p.getValue(), value)) {
+ deleteEntry(p);
+ return true;
+ }
+ return false;
+ }
+
+ public int size() {
+ return TreeMap.this.size();
+ }
+
+ public void clear() {
+ TreeMap.this.clear();
+ }
+ }
+
+ /*
+ * 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.
+ */
+
+ Iterator keyIterator() {
+ return new KeyIterator(getFirstEntry());
+ }
+
+ Iterator descendingKeyIterator() {
+ 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());
+ }
+
+ 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 KeySet<>(m.subMap(fromElement, fromInclusive,
+ toElement, toInclusive));
+ }
+ public NavigableSet headSet(E toElement, boolean inclusive) {
+ return new KeySet<>(m.headMap(toElement, inclusive));
+ }
+ public NavigableSet tailSet(E fromElement, boolean inclusive) {
+ return new KeySet<>(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 KeySet(m.descendingMap());
+ }
+ }
+
+ /**
+ * Base class for TreeMap Iterators
+ */
+ 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 = next;
+ if (e == null)
+ throw new NoSuchElementException();
+ if (modCount != expectedModCount)
+ throw new ConcurrentModificationException();
+ next = successor(e);
+ lastReturned = e;
+ return e;
+ }
+
+ final Entry prevEntry() {
+ Entry e = next;
+ if (e == null)
+ throw new NoSuchElementException();
+ if (modCount != expectedModCount)
+ throw new ConcurrentModificationException();
+ next = predecessor(e);
+ lastReturned = e;
+ return e;
+ }
+
+ public void remove() {
+ if (lastReturned == null)
+ throw new IllegalStateException();
+ if (modCount != expectedModCount)
+ throw new ConcurrentModificationException();
+ // deleted entries are replaced by their successors
+ if (lastReturned.left != null && lastReturned.right != null)
+ next = lastReturned;
+ deleteEntry(lastReturned);
+ expectedModCount = modCount;
+ lastReturned = null;
+ }
+ }
+
+ final class EntryIterator extends PrivateEntryIterator> {
+ EntryIterator(Entry first) {
+ super(first);
+ }
+ public Map.Entry next() {
+ return nextEntry();
+ }
+ }
+
+ 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
+
+ /**
+ * Compares two keys using the correct comparison method for this TreeMap.
+ */
+ final int compare(Object k1, Object k2) {
+ return comparator==null ? ((Comparable)k1).compareTo((K)k2)
+ : comparator.compare((K)k1, (K)k2);
+ }
+
+ /**
+ * Test two values for equality. Differs from o1.equals(o2) only in
+ * that it copes with {@code null} o1 properly.
+ */
+ static final boolean valEquals(Object o1, Object o2) {
+ return (o1==null ? o2==null : o1.equals(o2));
+ }
+
+ /**
+ * Return SimpleImmutableEntry for entry, or null if null
+ */
+ static Map.Entry exportEntry(TreeMap.Entry e) {
+ return (e == null) ? null :
+ new AbstractMap.SimpleImmutableEntry<>(e);
+ }
+
+ /**
+ * Return key for entry, or null if null
+ */
+ static K keyOrNull(TreeMap.Entry e) {
+ return (e == null) ? null : e.key;
+ }
+
+ /**
+ * Returns the key corresponding to the specified Entry.
+ * @throws NoSuchElementException if the Entry is null
+ */
+ static K key(Entry e) {
+ if (e==null)
+ throw new NoSuchElementException();
+ return e.key;
+ }
+
+
+ // SubMaps
+
+ /**
+ * Dummy value serving as unmatchable fence key for unbounded
+ * SubMapIterators
+ */
+ private static final Object UNBOUNDED = new Object();
+
+ /**
+ * @serial include
+ */
+ abstract static class NavigableSubMap extends AbstractMap
+ implements NavigableMap, java.io.Serializable {
+ /**
+ * The backing map.
+ */
+ final TreeMap m;
+
+ /**
+ * 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 {
+ if (!fromStart) // type check
+ m.compare(lo, lo);
+ if (!toEnd)
+ m.compare(hi, hi);
+ }
+
+ this.m = m;
+ this.fromStart = fromStart;
+ this.lo = lo;
+ this.loInclusive = loInclusive;
+ this.toEnd = toEnd;
+ 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 (fromStart && toEnd) ? m.isEmpty() : entrySet().isEmpty();
+ }
+
+ public int size() {
+ return (fromStart && toEnd) ? m.size() : entrySet().size();
+ }
+
+ public final boolean containsKey(Object key) {
+ return inRange(key) && m.containsKey(key);
+ }
+
+ public final V put(K key, V value) {
+ if (!inRange(key))
+ throw new IllegalArgumentException("key out of range");
+ return m.put(key, value);
+ }
+
+ public final V get(Object key) {
+ return !inRange(key) ? null : m.get(key);
+ }
+
+ public final V remove(Object key) {
+ return !inRange(key) ? null : m.remove(key);
+ }
+
+ public final Map.Entry ceilingEntry(K key) {
+ return exportEntry(subCeiling(key));
+ }
+
+ public final K ceilingKey(K key) {
+ return keyOrNull(subCeiling(key));
+ }
+
+ public final Map.Entry higherEntry(K key) {
+ return exportEntry(subHigher(key));
+ }
+
+ public final K higherKey(K key) {
+ return keyOrNull(subHigher(key));
+ }
+
+ public final Map.Entry floorEntry(K key) {
+ return exportEntry(subFloor(key));
+ }
+
+ public final K floorKey(K key) {
+ return keyOrNull(subFloor(key));
+ }
+
+ public final Map.Entry lowerEntry(K key) {
+ return exportEntry(subLower(key));
+ }
+
+ public final K lowerKey(K key) {
+ return keyOrNull(subLower(key));
+ }
+
+ public final K firstKey() {
+ return key(subLowest());
+ }
+
+ public final K lastKey() {
+ return key(subHighest());
+ }
+
+ public final Map.Entry firstEntry() {
+ return exportEntry(subLowest());
+ }
+
+ public final Map.Entry lastEntry() {
+ return exportEntry(subHighest());
+ }
+
+ public final Map.Entry pollFirstEntry() {
+ TreeMap.Entry e = subLowest();
+ Map.Entry result = exportEntry(e);
+ if (e != null)
+ m.deleteEntry(e);
+ return result;
+ }
+
+ public final Map.Entry pollLastEntry() {
+ TreeMap.Entry e = subHighest();
+ Map.Entry result = exportEntry(e);
+ if (e != null)
+ m.deleteEntry(e);
+ return result;
+ }
+
+ // Views
+ 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));
+ }
+
+ public final Set keySet() {
+ return navigableKeySet();
+ }
+
+ public NavigableSet descendingKeySet() {
+ return descendingMap().navigableKeySet();
+ }
+
+ public final SortedMap subMap(K fromKey, K toKey) {
+ return subMap(fromKey, true, toKey, false);
+ }
+
+ public final SortedMap headMap(K toKey) {
+ return headMap(toKey, false);
+ }
+
+ public final SortedMap tailMap(K fromKey) {
+ return tailMap(fromKey, true);
+ }
+
+ // View classes
+
+ abstract class EntrySetView extends AbstractSet> {
+ private transient int size = -1, sizeModCount;
+
+ public int size() {
+ if (fromStart && toEnd)
+ return m.size();
+ if (size == -1 || sizeModCount != m.modCount) {
+ sizeModCount = m.modCount;
+ size = 0;
+ Iterator i = iterator();
+ while (i.hasNext()) {
+ size++;
+ i.next();
+ }
+ }
+ return size;
+ }
+
+ public boolean isEmpty() {
+ TreeMap.Entry n = absLowest();
+ return n == null || tooHigh(n.key);
+ }
+
+ public boolean contains(Object o) {
+ if (!(o instanceof Map.Entry))
+ return false;
+ Map.Entry entry = (Map.Entry) o;
+ K key = entry.getKey();
+ if (!inRange(key))
+ return false;
+ TreeMap.Entry node = m.getEntry(key);
+ return node != null &&
+ valEquals(node.getValue(), entry.getValue());
+ }
+
+ public boolean remove(Object o) {
+ if (!(o instanceof Map.Entry))
+ return false;
+ Map.Entry entry = (Map.Entry) o;
+ K key = entry.getKey();
+ if (!inRange(key))
+ return false;
+ TreeMap.Entry node = m.getEntry(key);
+ if (node!=null && valEquals(node.getValue(),
+ entry.getValue())) {
+ m.deleteEntry(node);
+ return true;
+ }
+ return false;
+ }
+ }
+
+ /**
+ * Iterators for SubMaps
+ */
+ abstract class SubMapIterator implements Iterator {
+ TreeMap.Entry lastReturned;
+ TreeMap.Entry next;
+ final Object fenceKey;
+ int expectedModCount;
+
+ SubMapIterator(TreeMap.Entry first,
+ TreeMap.Entry fence) {
+ expectedModCount = m.modCount;
+ lastReturned = null;
+ next = first;
+ fenceKey = fence == null ? UNBOUNDED : fence.key;
+ }
+
+ public final boolean hasNext() {
+ return next != null && next.key != fenceKey;
+ }
+
+ final TreeMap.Entry nextEntry() {
+ TreeMap.Entry e = next;
+ if (e == null || e.key == fenceKey)
+ throw new NoSuchElementException();
+ if (m.modCount != expectedModCount)
+ throw new ConcurrentModificationException();
+ next = successor(e);
+ lastReturned = e;
+ return e;
+ }
+
+ final TreeMap.Entry prevEntry() {
+ TreeMap.Entry e = next;
+ if (e == null || e.key == fenceKey)
+ throw new NoSuchElementException();
+ if (m.modCount != expectedModCount)
+ throw new ConcurrentModificationException();
+ next = predecessor(e);
+ lastReturned = e;
+ return e;
+ }
+
+ final void removeAscending() {
+ if (lastReturned == null)
+ throw new IllegalStateException();
+ if (m.modCount != expectedModCount)
+ throw new ConcurrentModificationException();
+ // deleted entries are replaced by their successors
+ if (lastReturned.left != null && lastReturned.right != null)
+ next = lastReturned;
+ m.deleteEntry(lastReturned);
+ lastReturned = null;
+ expectedModCount = m.modCount;
+ }
+
+ final void removeDescending() {
+ if (lastReturned == null)
+ throw new IllegalStateException();
+ if (m.modCount != expectedModCount)
+ throw new ConcurrentModificationException();
+ m.deleteEntry(lastReturned);
+ lastReturned = null;
+ expectedModCount = m.modCount;
+ }
+
+ }
+
+ final class SubMapEntryIterator extends SubMapIterator> {
+ SubMapEntryIterator(TreeMap.Entry first,
+ TreeMap.Entry fence) {
+ super(first, fence);
+ }
+ public Map.Entry next() {
+ return nextEntry();
+ }
+ public void remove() {
+ removeAscending();
+ }
+ }
+
+ final class SubMapKeyIterator extends SubMapIterator {
+ SubMapKeyIterator(TreeMap.Entry first,
+ TreeMap.Entry fence) {
+ super(first, fence);
+ }
+ public K next() {
+ return nextEntry().key;
+ }
+ public void remove() {
+ removeAscending();
+ }
+ }
+
+ final class DescendingSubMapEntryIterator extends SubMapIterator> {
+ DescendingSubMapEntryIterator(TreeMap.Entry last,
+ TreeMap.Entry fence) {
+ super(last, fence);
+ }
+
+ public Map.Entry next() {
+ return prevEntry();
+ }
+ public void remove() {
+ removeDescending();
+ }
+ }
+
+ final class DescendingSubMapKeyIterator extends SubMapIterator {
+ DescendingSubMapKeyIterator(TreeMap.Entry last,
+ TreeMap.Entry fence) {
+ super(last, fence);
+ }
+ public K next() {
+ return prevEntry().key;
+ }
+ public void remove() {
+ removeDescending();
+ }
+ }
+ }
+
+ /**
+ * @serial include
+ */
+ static final class AscendingSubMap extends NavigableSubMap {
+ private static final long serialVersionUID = 912986545866124060L;
+
+ AscendingSubMap(TreeMap m,
+ boolean fromStart, K lo, boolean loInclusive,
+ boolean toEnd, K hi, boolean hiInclusive) {
+ super(m, fromStart, lo, loInclusive, toEnd, hi, hiInclusive);
+ }
+
+ public Comparator comparator() {
+ return m.comparator();
+ }
+
+ 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 NavigableMap headMap(K toKey, boolean inclusive) {
+ if (!inRange(toKey, inclusive))
+ throw new IllegalArgumentException("toKey out of range");
+ return new AscendingSubMap(m,
+ fromStart, lo, loInclusive,
+ false, toKey, inclusive);
+ }
+
+ public NavigableMap tailMap(K fromKey, boolean inclusive) {
+ if (!inRange(fromKey, inclusive))
+ throw new IllegalArgumentException("fromKey out of range");
+ return new AscendingSubMap(m,
+ false, fromKey, inclusive,
+ toEnd, hi, hiInclusive);
+ }
+
+ public NavigableMap descendingMap() {
+ NavigableMap mv = descendingMapView;
+ return (mv != null) ? mv :
+ (descendingMapView =
+ new DescendingSubMap(m,
+ fromStart, lo, loInclusive,
+ toEnd, hi, hiInclusive));
+ }
+
+ Iterator keyIterator() {
+ return new SubMapKeyIterator(absLowest(), absHighFence());
+ }
+
+ Iterator descendingKeyIterator() {
+ return new DescendingSubMapKeyIterator(absHighest(), absLowFence());
+ }
+
+ final class AscendingEntrySetView extends EntrySetView {
+ public Iterator> iterator() {
+ return new SubMapEntryIterator(absLowest(), absHighFence());
+ }
+ }
+
+ 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); }
+ }
+
+ /**
+ * @serial include
+ */
+ 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);
+ }
+
+ private final Comparator reverseComparator =
+ Collections.reverseOrder(m.comparator);
+
+ public Comparator comparator() {
+ return reverseComparator;
+ }
+
+ 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);
+ }
+
+ 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 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));
+ }
+
+ Iterator keyIterator() {
+ return new DescendingSubMapKeyIterator(absHighest(), absLowFence());
+ }
+
+ Iterator descendingKeyIterator() {
+ return new SubMapKeyIterator(absLowest(), absHighFence());
+ }
+
+ final class DescendingEntrySetView extends EntrySetView {
+ public Iterator> iterator() {
+ return new DescendingSubMapEntryIterator(absHighest(), absLowFence());
+ }
+ }
+
+ 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); }
+ }
+
+ /**
+ * 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 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(); }
+ }
+
+
+ // Red-black mechanics
+
+ private static final boolean RED = false;
+ private static final boolean BLACK = true;
+
+ /**
+ * Node in the Tree. Doubles as a means to pass key-value pairs back to
+ * user (see Map.Entry).
+ */
+
+ static final class Entry implements Map.Entry {
+ K key;
+ V value;
+ Entry left = null;
+ Entry right = null;
+ Entry parent;
+ boolean color = BLACK;
+
+ /**
+ * Make a new cell with given key, value, and parent, and with
+ * {@code null} child links, and BLACK color.
+ */
+ Entry(K key, V value, Entry parent) {
+ this.key = key;
+ this.value = value;
+ this.parent = parent;
+ }
+
+ /**
+ * Returns the key.
+ *
+ * @return the key
+ */
+ public K getKey() {
+ return key;
+ }
+
+ /**
+ * Returns the value associated with the key.
+ *
+ * @return the value associated with the key
+ */
+ public V getValue() {
+ return value;
+ }
+
+ /**
+ * Replaces the value currently associated with the key with the given
+ * value.
+ *
+ * @return the value associated with the key before this method was
+ * called
+ */
+ public V setValue(V value) {
+ V oldValue = this.value;
+ this.value = value;
+ return oldValue;
+ }
+
+ public boolean equals(Object o) {
+ if (!(o instanceof Map.Entry))
+ return false;
+ Map.Entry e = (Map.Entry)o;
+
+ return valEquals(key,e.getKey()) && valEquals(value,e.getValue());
+ }
+
+ public int hashCode() {
+ int keyHash = (key==null ? 0 : key.hashCode());
+ int valueHash = (value==null ? 0 : value.hashCode());
+ return keyHash ^ valueHash;
+ }
+
+ public String toString() {
+ return key + "=" + value;
+ }
+ }
+
+ /**
+ * Returns the first Entry in the TreeMap (according to the TreeMap's
+ * key-sort function). Returns null if the TreeMap is empty.
+ */
+ final Entry getFirstEntry() {
+ Entry