/*

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

 *

 * <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);