/* 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 modify
it under the terms of the GNU General Public License as published by
the 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, but
WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
General Public License for more details.

You should have received a copy of the GNU General Public License
along with GNU Classpath; see the file COPYING.  If not, write to the
Free Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
02111-1307 USA.

Linking this library statically or dynamically with other modules is
making a combined work based on this library.  Thus, the terms and
conditions of the GNU General Public License cover the whole
combination.

As a special exception, the copyright holders of this library give you
permission to link this library with independent modules to produce an
executable, regardless of the license terms of these independent
modules, and to copy and distribute the resulting executable under
terms of your choice, provided that you also meet, for each linked
independent module, the terms and conditions of the license of that
module.  An independent module is a module which is not derived from
or based on this library.  If you modify this library, you may extend
this exception to your version of the library, but you are not
obligated to do so.  If you do not wish to do so, delete this
exception 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 Node hiddenNil;
	static Node getNil() {
		if (hiddenNil == null) {
			Node n = new Node(BLACK);
			// Nil is self-referential, so we must initialize it after creation.
			n.parent = n;
			n.left = n;
			n.right = n;
			hiddenNil = n;
		}
		return hiddenNil;
	}

	/**
	 * The root node of this TreeMap.
	 */
	private transient Node root = getNil();

	/**
	 * 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;
		/** The right child node. */
		Node right;
		/** The parent node. */
		Node parent;

		/**
		 * Simple constructor.
		 * @param key the key
		 * @param value the value
		 */
		Node(Object key, Object value, int color) {
			super(key, value);
			this.color = color;
			Node nil = getNil();
			this.left = nil;
			this.right = nil;
			this.parent = nil;
		}
		
		/**
		 * Special constructor for use in getNil() to avoid endless recursion
		 * @param color
		 */
		Node(int color) {
			super(null, null);
			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 = getNil();
			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 != getNil()) {
			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) != getNil();
	}

	/**
	 * 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 != getNil()) {
			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 != getNil() && 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 != getNil() && 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