/*

* Copyright (c) 1997, 2011, Oracle and/or its affiliates. All rights reserved.

* ORACLE PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*/

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.

*

* <p>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 <em>Introduction to Algorithms</em>.

*

* <p>Note that the ordering maintained by a tree map, like any sorted map, and

* whether or not an explicit comparator is provided, must be <em>consistent

* with {@code equals}</em> if this sorted map is to correctly implement the

* {@code Map} interface. (See {@code Comparable} or {@code Comparator} for a

* precise definition of <em>consistent with equals</em>.) 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 <em>is</em> well-defined even if its ordering is

* inconsistent with {@code equals}; it just fails to obey the general contract

* of the {@code Map} interface.

*

* <p><strong>Note that this implementation is not synchronized.</strong>

* If multiple threads access a map concurrently, and at least one of the

* threads modifies the map structurally, it <em>must</em> 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: <pre>

* SortedMap m = Collections.synchronizedSortedMap(new TreeMap(...));</pre>

*

* <p>The iterators returned by the {@code iterator} method of the collections

* returned by all of this class's "collection view methods" are

* <em>fail-fast</em>: 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.

*

* <p>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: <em>the fail-fast behavior of iterators

* should be used only to detect bugs.</em>

*

* <p>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 <strong>not</strong> support the {@code Entry.setValue}

* method. (Note however that it is possible to change mappings in the

* associated map using {@code put}.)

*

* <p>This class is a member of the

* <a href="{@docRoot}/../technotes/guides/collections/index.html">

* Java Collections Framework</a>.

*

* @param <K> the type of keys maintained by this map

* @param <V> 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<K,V>

extends AbstractMap<K,V>

implements NavigableMap<K,V>, 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<? super K> comparator;

private transient Entry<K,V> 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

* <em>mutually comparable</em>: {@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 <em>mutually

* comparable</em> 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<? super K> comparator) {

this.comparator = comparator;

}

/**

* Constructs a new tree map containing the same mappings as the given

* map, ordered according to the <em>natural ordering</em> of its keys.

* All keys inserted into the new map must implement the {@link

* Comparable} interface. Furthermore, all such keys must be

* <em>mutually comparable</em>: {@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<? extends K, ? extends V> 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<K, ? extends V> 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<K,V> 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.

*

* <p>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.)

*

* <p>A return value of {@code null} does not <em>necessarily</em>

* 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<K,V> p = getEntry(key);

return (p==null ? null : p.value);

}

public Comparator<? super K> 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<? extends K, ? extends V> 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<K,V> getEntry(Object key) {

// Offload comparator-based version for sake of performance

if (comparator != null)

return getEntryUsingComparator(key);

if (key == null)

throw new NullPointerException();

Comparable<? super K> k = (Comparable<? super K>) key;

Entry<K,V> 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<K,V> getEntryUsingComparator(Object key) {

K k = (K) key;

Comparator<? super K> cpr = comparator;

if (cpr != null) {

Entry<K,V> 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<K,V> getCeilingEntry(K key) {

Entry<K,V> 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<K,V> parent = p.parent;

Entry<K,V> 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<K,V> getFloorEntry(K key) {

Entry<K,V> 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<K,V> parent = p.parent;

Entry<K,V> 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<K,V> getHigherEntry(K key) {

Entry<K,V> 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<K,V> parent = p.parent;

Entry<K,V> 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<K,V> getLowerEntry(K key) {

Entry<K,V> 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<K,V> parent = p.parent;

Entry<K,V> 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<K,V> 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<K,V> parent;

// split comparator and comparable paths

Comparator<? super K> 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<? super K> k = (Comparable<? super K>) 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<K,V> 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<K,V> 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<K,V> clone = null;

try {

clone = (TreeMap<K,V>) 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<K,V> firstEntry() {

return exportEntry(getFirstEntry());

}

/**

* @since 1.6

*/

public Map.Entry<K,V> lastEntry() {

return exportEntry(getLastEntry());

}

/**

* @since 1.6

*/

public Map.Entry<K,V> pollFirstEntry() {

Entry<K,V> p = getFirstEntry();

Map.Entry<K,V> result = exportEntry(p);

if (p != null)

deleteEntry(p);

return result;

}

/**

* @since 1.6

*/

public Map.Entry<K,V> pollLastEntry() {

Entry<K,V> p = getLastEntry();

Map.Entry<K,V> 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<K,V> 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<K,V> 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<K,V> 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<K,V> 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<K> navigableKeySet = null;

private transient NavigableMap<K,V> 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<K> keySet() {

return navigableKeySet();

}

/**

* @since 1.6

*/

public NavigableSet<K> navigableKeySet() {

KeySet<K> nks = navigableKeySet;

return (nks != null) ? nks : (navigableKeySet = new KeySet(this));

}

/**

* @since 1.6

*/

public NavigableSet<K> 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<V> values() {

Collection<V> 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<Map.Entry<K,V>> entrySet() {

EntrySet es = entrySet;

return (es != null) ? es : (entrySet = new EntrySet());

}

/**

* @since 1.6

*/

public NavigableMap<K, V> descendingMap() {

NavigableMap<K, V> 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<K,V> 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<K,V> 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<K,V> 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<K,V> 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<K,V> 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<K,V> tailMap(K fromKey) {

return tailMap(fromKey, true);

}

// View class support

class Values extends AbstractCollection<V> {

public Iterator<V> 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<K,V> 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<Map.Entry<K,V>> {

public Iterator<Map.Entry<K,V>> iterator() {

return new EntryIterator(getFirstEntry());

}

public boolean contains(Object o) {

if (!(o instanceof Map.Entry))

return false;

Map.Entry<K,V> entry = (Map.Entry<K,V>) o;

V value = entry.getValue();

Entry<K,V> 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<K,V> entry = (Map.Entry<K,V>) o;

V value = entry.getValue();

Entry<K,V> p = getEntry(entry.getKey());

if (p != null && valEquals(p.getValue(), value)) {

deleteEntry(p);

return true;

}

return false;

}

public int size() {