/*

 * Copyright 1997-2008 Sun Microsystems, Inc.  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.  Sun designates this

 * particular file as subject to the "Classpath" exception as provided

 * by Sun 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 Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,

 * CA 95054 USA or visit www.sun.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

 * <tt>containsKey</tt>, <tt>get</tt>, <tt>put</tt> and <tt>remove</tt>

 * operations.  Algorithms are adaptations of those in Cormen, Leiserson, and

 * Rivest's <I>Introduction to Algorithms</I>.

 *

 * <p>Note that the ordering maintained by a sorted map (whether or not an

 * explicit comparator is provided) must be <i>consistent with equals</i> if

 * this sorted map is to correctly implement the <tt>Map</tt> interface.  (See

 * <tt>Comparable</tt> or <tt>Comparator</tt> for a precise definition of

 * <i>consistent with equals</i>.)  This is so because the <tt>Map</tt>

 * interface is defined in terms of the equals operation, but a map performs

 * all key comparisons using its <tt>compareTo</tt> (or <tt>compare</tt>)

 * 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

 * <i>is</i> well-defined even if its ordering is inconsistent with equals; it

 * just fails to obey the general contract of the <tt>Map</tt> 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 <i>must</i> 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 <tt>iterator</tt> method of the collections

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

 * <i>fail-fast</i>: if the map is structurally modified at any time after the

 * iterator is created, in any way except through the iterator's own

 * <tt>remove</tt> 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 <tt>ConcurrentModificationException</tt> on a best-effort basis.

 * Therefore, it would be wrong to write a program that depended on this

 * exception for its correctness:   <i>the fail-fast behavior of iterators

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

 *

 * <p>All <tt>Map.Entry</tt> pairs returned by methods in this class

 * and its views represent snapshots of mappings at the time they were

 * produced. They do <em>not</em> support the <tt>Entry.setValue</tt>

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

 * associated map using <tt>put</tt>.)

 *

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

     * <i>mutually comparable</i>: <tt>k1.compareTo(k2)</tt> must not throw

     * a <tt>ClassCastException</tt> for any keys <tt>k1</tt> and

     * <tt>k2</tt> 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

     * <tt>put(Object key, Object value)</tt> call will throw a

     * <tt>ClassCastException</tt>.

     */

    public TreeMap() {

        comparator = null;

    }

    /**

     * Constructs a new, empty tree map, ordered according to the given

     * comparator.  All keys inserted into the map must be <i>mutually

     * comparable</i> by the given comparator: <tt>comparator.compare(k1,

     * k2)</tt> must not throw a <tt>ClassCastException</tt> for any keys

     * <tt>k1</tt> and <tt>k2</tt> in the map.  If the user attempts to put

     * a key into the map that violates this constraint, the <tt>put(Object

     * key, Object value)</tt> call will throw a

     * <tt>ClassCastException</tt>.

     *

     * @param comparator the comparator that will be used to order this map.

     *        If <tt>null</tt>, 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 <i>natural ordering</i> of its keys.

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

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

     * <i>mutually comparable</i>: <tt>k1.compareTo(k2)</tt> must not throw

     * a <tt>ClassCastException</tt> for any keys <tt>k1</tt> and

     * <tt>k2</tt> 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 <tt>true</tt> if this map contains a mapping for the specified

     * key.

     *

     * @param key key whose presence in this map is to be tested

     * @return <tt>true</tt> 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 <tt>true</tt> if this map maps one or more keys to the

     * specified value.  More formally, returns <tt>true</tt> if and only if

     * this map contains at least one mapping to a value <tt>v</tt> such

     * that <tt>(value==null ? v==null : value.equals(v))</tt>.  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 <tt>true</tt> if a mapping to <tt>value</tt> exists;

     *         <tt>false</tt> 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 <i>necessarily</i>

     * 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 <tt>null</tt> if the map

     * does not contain an entry for the key.

     *

     * @return this map's entry for the given key, or <tt>null</tt> 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 <tt>null</tt>.

     */

    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 <tt>null</tt>.

     */

    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 <tt>null</tt>.

     */

    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 <tt>null</tt>.

     */

    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 <tt>key</tt>, or

     *         <tt>null</tt> if there was no mapping for <tt>key</tt>.

     *         (A <tt>null</tt> return can also indicate that the map

     *         previously associated <tt>null</tt> with <tt>key</tt>.)

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