/* TreeMap.java -- a class providing a basic Red-Black Tree data structure,   mapping Object --> Object   Copyright (C) 1998, 1999, 2000, 2001, 2002 Free Software Foundation, Inc.This file is part of GNU Classpath.GNU Classpath is free software; you can redistribute it and/or modifyit under the terms of the GNU General Public License as published bythe Free Software Foundation; either version 2, or (at your option)any later version.GNU Classpath is distributed in the hope that it will be useful, butWITHOUT ANY WARRANTY; without even the implied warranty ofMERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNUGeneral Public License for more details.You should have received a copy of the GNU General Public Licensealong with GNU Classpath; see the file COPYING.  If not, write to theFree Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA02111-1307 USA.Linking this library statically or dynamically with other modules ismaking a combined work based on this library.  Thus, the terms andconditions of the GNU General Public License cover the wholecombination.As a special exception, the copyright holders of this library give youpermission to link this library with independent modules to produce anexecutable, regardless of the license terms of these independentmodules, and to copy and distribute the resulting executable underterms of your choice, provided that you also meet, for each linkedindependent module, the terms and conditions of the license of thatmodule.  An independent module is a module which is not derived fromor based on this library.  If you modify this library, you may extendthis exception to your version of the library, but you are notobligated to do so.  If you do not wish to do so, delete thisexception statement from your version. */package java.util;import java.io.Serializable;import java.io.ObjectOutputStream;import java.io.ObjectInputStream;import java.io.IOException;/** * This class provides a red-black tree implementation of the SortedMap * interface.  Elements in the Map will be sorted by either a user-provided * Comparator object, or by the natural ordering of the keys. * * The algorithms are adopted from Corman, Leiserson, and Rivest's * <i>Introduction to Algorithms.</i>  TreeMap guarantees O(log n) * insertion and deletion of elements.  That being said, there is a large * enough constant coefficient in front of that "log n" (overhead involved * in keeping the tree balanced), that TreeMap may not be the best choice * for small collections. If something is already sorted, you may want to * just use a LinkedHashMap to maintain the order while providing O(1) access. * * TreeMap is a part of the JDK1.2 Collections API.  Null keys are allowed * only if a Comparator is used which can deal with them; natural ordering * cannot cope with null.  Null values are always allowed. Note that the * ordering must be <i>consistent with equals</i> to correctly implement * the Map interface. If this condition is violated, the map is still * well-behaved, but you may have suprising results when comparing it to * other maps.<p> * * This implementation is not synchronized. If you need to share this between * multiple threads, do something like:<br> * <code>SortedMap m *       = Collections.synchronizedSortedMap(new TreeMap(...));</code><p> * * The iterators are <i>fail-fast</i>, meaning that any structural * modification, except for <code>remove()</code> called on the iterator * itself, cause the iterator to throw a * <code>ConcurrentModificationException</code> rather than exhibit * non-deterministic behavior. * * @author Jon Zeppieri * @author Bryce McKinlay * @author Eric Blake <ebb9@email.byu.edu> * @see Map * @see HashMap * @see Hashtable * @see LinkedHashMap * @see Comparable * @see Comparator * @see Collection * @see Collections#synchronizedSortedMap(SortedMap) * @since 1.2 * @status updated to 1.4 */public class TreeMap extends AbstractMap  implements SortedMap, Cloneable, Serializable{  // Implementation note:  // A red-black tree is a binary search tree with the additional properties  // that all paths to a leaf node visit the same number of black nodes,  // and no red node has red children. To avoid some null-pointer checks,  // we use the special node nil which is always black, has no relatives,  // and has key and value of null (but is not equal to a mapping of null).  /**   * Compatible with JDK 1.2.   */  private static final long serialVersionUID = 919286545866124006L;  /**   * Color status of a node. Package visible for use by nested classes.   */  static final int RED = -1,                   BLACK = 1;  /**   * Sentinal node, used to avoid null checks for corner cases and make the   * delete rebalance code simpler. The rebalance code must never assign   * the parent, left, or right of nil, but may safely reassign the color   * to be black. This object must never be used as a key in a TreeMap, or   * it will break bounds checking of a SubMap.   */  static final Node nil = new Node(null, null, BLACK);  static    {      // Nil is self-referential, so we must initialize it after creation.      nil.parent = nil;      nil.left = nil;      nil.right = nil;    }  /**   * The root node of this TreeMap.   */  private transient Node root = nil;  /**   * The size of this TreeMap. Package visible for use by nested classes.   */  transient int size;  /**   * The cache for {@link #entrySet()}.   */  private transient Set entries;  /**   * Counts the number of modifications this TreeMap has undergone, used   * by Iterators to know when to throw ConcurrentModificationExceptions.   * Package visible for use by nested classes.   */  transient int modCount;  /**   * This TreeMap's comparator, or null for natural ordering.   * Package visible for use by nested classes.   * @serial the comparator ordering this tree, or null   */  final Comparator comparator;  /**   * Class to represent an entry in the tree. Holds a single key-value pair,   * plus pointers to parent and child nodes.   *   * @author Eric Blake <ebb9@email.byu.edu>   */  private static final class Node extends AbstractMap.BasicMapEntry  {    // All fields package visible for use by nested classes.    /** The color of this node. */    int color;    /** The left child node. */    Node left = nil;    /** The right child node. */    Node right = nil;    /** The parent node. */    Node parent = nil;    /**     * Simple constructor.     * @param key the key     * @param value the value     */    Node(Object key, Object value, int color)    {      super(key, value);      this.color = color;    }  }  /**   * Instantiate a new TreeMap with no elements, using the keys' natural   * ordering to sort. All entries in the map must have a key which implements   * Comparable, and which are <i>mutually comparable</i>, otherwise map   * operations may throw a {@link ClassCastException}. Attempts to use   * a null key will throw a {@link NullPointerException}.   *   * @see Comparable   */  public TreeMap()  {    this((Comparator) null);  }  /**   * Instantiate a new TreeMap with no elements, using the provided comparator   * to sort. All entries in the map must have keys which are mutually   * comparable by the Comparator, otherwise map operations may throw a   * {@link ClassCastException}.   *   * @param comparator the sort order for the keys of this map, or null   *        for the natural order   */  public TreeMap(Comparator c)  {    comparator = c;  }  /**   * Instantiate a new TreeMap, initializing it with all of the elements in   * the provided Map.  The elements will be sorted using the natural   * ordering of the keys. This algorithm runs in n*log(n) time. All entries   * in the map must have keys which implement Comparable and are mutually   * comparable, otherwise map operations may throw a   * {@link ClassCastException}.   *   * @param map a Map, whose entries will be put into this TreeMap   * @throws ClassCastException if the keys in the provided Map are not   *         comparable   * @throws NullPointerException if map is null   * @see Comparable   */  public TreeMap(Map map)  {    this((Comparator) null);    putAll(map);  }  /**   * Instantiate a new TreeMap, initializing it with all of the elements in   * the provided SortedMap.  The elements will be sorted using the same   * comparator as in the provided SortedMap. This runs in linear time.   *   * @param sm a SortedMap, whose entries will be put into this TreeMap   * @throws NullPointerException if sm is null   */  public TreeMap(SortedMap sm)  {    this(sm.comparator());    int pos = sm.size();    Iterator itr = sm.entrySet().iterator();    fabricateTree(pos);    Node node = firstNode();    while (--pos >= 0)      {        Map.Entry me = (Map.Entry) itr.next();        node.key = me.getKey();        node.value = me.getValue();        node = successor(node);      }  }  /**   * Clears the Map so it has no keys. This is O(1).   */  public void clear()  {    if (size > 0)      {        modCount++;        root = nil;        size = 0;      }  }  /**   * Returns a shallow clone of this TreeMap. The Map itself is cloned,   * but its contents are not.   *   * @return the clone   */  public Object clone()  {    TreeMap copy = null;    try      {        copy = (TreeMap) super.clone();      }    catch (CloneNotSupportedException x)      {      }    copy.entries = null;    copy.fabricateTree(size);    Node node = firstNode();    Node cnode = copy.firstNode();    while (node != nil)      {        cnode.key = node.key;        cnode.value = node.value;        node = successor(node);        cnode = copy.successor(cnode);      }    return copy;  }  /**   * Return the comparator used to sort this map, or null if it is by   * natural order.   *   * @return the map's comparator   */  public Comparator comparator()  {    return comparator;  }  /**   * Returns true if the map contains a mapping for the given key.   *   * @param key the key to look for   * @return true if the key has a mapping   * @throws ClassCastException if key is not comparable to map elements   * @throws NullPointerException if key is null and the comparator is not   *         tolerant of nulls   */  public boolean containsKey(Object key)  {    return getNode(key) != nil;  }  /**   * Returns true if the map contains at least one mapping to the given value.   * This requires linear time.   *   * @param value the value to look for   * @return true if the value appears in a mapping   */  public boolean containsValue(Object value)  {    Node node = firstNode();    while (node != nil)      {        if (equals(value, node.value))          return true;        node = successor(node);      }    return false;  }  /**   * Returns a "set view" of this TreeMap's entries. The set is backed by   * the TreeMap, so changes in one show up in the other.  The set supports   * element removal, but not element addition.<p>   *   * Note that the iterators for all three views, from keySet(), entrySet(),   * and values(), traverse the TreeMap in sorted sequence.   *   * @return a set view of the entries   * @see #keySet()   * @see #values()   * @see Map.Entry   */  public Set entrySet()  {    if (entries == null)      // Create an AbstractSet with custom implementations of those methods      // that can be overriden easily and efficiently.      entries = new AbstractSet()      {        public int size()        {          return size;        }        public Iterator iterator()        {          return new TreeIterator(ENTRIES);        }        public void clear()        {          TreeMap.this.clear();        }        public boolean contains(Object o)        {          if (! (o instanceof Map.Entry))            return false;          Map.Entry me = (Map.Entry) o;          Node n = getNode(me.getKey());          return n != nil && AbstractSet.equals(me.getValue(), n.value);      }        public boolean remove(Object o)        {          if (! (o instanceof Map.Entry))            return false;          Map.Entry me = (Map.Entry) o;          Node n = getNode(me.getKey());          if (n != nil && AbstractSet.equals(me.getValue(), n.value))            {              removeNode(n);              return true;            }          return false;        }      };    return entries;  }  /**   * Returns the first (lowest) key in the map.   *   * @return the first key   * @throws NoSuchElementException if the map is empty   */  public Object firstKey()  {    if (root == nil)      throw new NoSuchElementException();    return firstNode().key;  }  /**   * Return the value in this TreeMap associated with the supplied key,   * or <code>null</code> if the key maps to nothing.  NOTE: Since the value   * could also be null, you must use containsKey to see if this key   * actually maps to something.   *   * @param key the key for which to fetch an associated value   * @return what the key maps to, if present   * @throws ClassCastException if key is not comparable to elements in the map   * @throws NullPointerException if key is null but the comparator does not   *         tolerate nulls   * @see #put(Object, Object)   * @see #containsKey(Object)   */  public Object get(Object key)  {    // Exploit fact that nil.value == null.    return getNode(key).value;  }