RBTreeMap.drv

/*
 * Copyright (C) 2002-2024 Sebastiano Vigna
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */


package PACKAGE;

#if ! KEYS_REFERENCE
import it.unimi.dsi.fastutil.objects.AbstractObjectSortedSet;
import it.unimi.dsi.fastutil.objects.ObjectBidirectionalIterator;
import it.unimi.dsi.fastutil.objects.ObjectListIterator;
import it.unimi.dsi.fastutil.objects.ObjectSortedSet;
#endif

#if KEY_INDEX != VALUE_INDEX && !(KEYS_REFERENCE && VALUES_REFERENCE)
import VALUE_PACKAGE.VALUE_COLLECTION;
import VALUE_PACKAGE.VALUE_ABSTRACT_COLLECTION;
import VALUE_PACKAGE.VALUE_ITERATOR;
#if VALUES_PRIMITIVE
import VALUE_PACKAGE.VALUE_LIST_ITERATOR;
#endif
#endif

import java.util.Comparator;
import java.util.Iterator;
import java.util.Map;
import java.util.SortedMap;
import java.util.NoSuchElementException;

/** A type-specific red-black tree map with a fast, small-footprint implementation.
 *
 * <p>The iterators provided by the views of this class are type-specific {@linkplain
 * it.unimi.dsi.fastutil.BidirectionalIterator bidirectional iterators}.
 * Moreover, the iterator returned by {@code iterator()} can be safely cast
 * to a type-specific {@linkplain java.util.ListIterator list iterator}.
 *
 */

public class RB_TREE_MAP KEY_VALUE_GENERIC extends ABSTRACT_SORTED_MAP KEY_VALUE_GENERIC implements java.io.Serializable, Cloneable {

	/** A reference to the root entry. */
	protected transient Entry KEY_VALUE_GENERIC tree;

	/** Number of entries in this map. */
	protected int count;

	/** The first key in this map. */
	protected transient Entry KEY_VALUE_GENERIC firstEntry;

	/** The last key in this map. */
	protected transient Entry KEY_VALUE_GENERIC lastEntry;

	/** Cached set of entries. */
	protected transient ObjectSortedSet<MAP.Entry KEY_VALUE_GENERIC> entries;

	/** Cached set of keys. */
	protected transient SORTED_SET KEY_GENERIC keys;

	/** Cached collection of values. */
	protected transient VALUE_COLLECTION VALUE_GENERIC values;

	/** The value of this variable remembers, after a {@code put()}
	 * or a {@code remove()}, whether the <em>domain</em> of the map
	 * has been modified. */
	protected transient boolean modified;

	/** This map's comparator, as provided in the constructor. */
	protected Comparator<? super KEY_GENERIC_CLASS> storedComparator;

	/** This map's actual comparator; it may differ from {@link #storedComparator} because it is
		always a type-specific comparator, so it could be derived from the former by wrapping. */
	protected transient KEY_COMPARATOR KEY_SUPER_GENERIC actualComparator;

	private static final long serialVersionUID = -7046029254386353129L;

	{
		allocatePaths();
	}

	/** Creates a new empty tree map.
	 */

	public RB_TREE_MAP() {
		tree = null;
		count = 0;
	}

	/** Generates the comparator that will be actually used.
	 *
	 * <p>When a given {@link Comparator} is specified and stored in {@link
	 * #storedComparator}, we must check whether it is type-specific.  If it is
	 * so, we can used directly, and we store it in {@link #actualComparator}. Otherwise,
	 * we adapt it using a helper static method.
	 */
	private void setActualComparator() {
#if KEY_CLASS_Object
		actualComparator = storedComparator;
#else
		actualComparator = COMPARATORS.AS_KEY_COMPARATOR(storedComparator);
#endif
	}


	/** Creates a new empty tree map with the given comparator.
	 *
	 * @param c a (possibly type-specific) comparator.
	 */

	public RB_TREE_MAP(final Comparator<? super KEY_GENERIC_CLASS> c) {
		this();
		storedComparator = c;
		setActualComparator();
	}


	/** Creates a new tree map copying a given map.
	 *
	 * @param m a {@link Map} to be copied into the new tree map.
	 */

	public RB_TREE_MAP(final Map<? extends KEY_GENERIC_CLASS, ? extends VALUE_GENERIC_CLASS> m) {
		this();
		putAll(m);
	}

	/** Creates a new tree map copying a given sorted map (and its {@link Comparator}).
	 *
	 * @param m a {@link SortedMap} to be copied into the new tree map.
	 */

	public RB_TREE_MAP(final SortedMap<KEY_GENERIC_CLASS,VALUE_GENERIC_CLASS> m) {
		this(m.comparator());
		putAll(m);
	}

	/** Creates a new tree map copying a given map.
	 *
	 * @param m a type-specific map to be copied into the new tree map.
	 */

	public RB_TREE_MAP(final MAP KEY_VALUE_EXTENDS_GENERIC m) {
		this();
		putAll(m);
	}

	/** Creates a new tree map copying a given sorted map (and its {@link Comparator}).
	 *
	 * @param m a type-specific sorted map to be copied into the new tree map.
	 */

	public RB_TREE_MAP(final SORTED_MAP KEY_VALUE_GENERIC m) {
		this(m.comparator());
		putAll(m);
	}

	/** Creates a new tree map using the elements of two parallel arrays and the given comparator.
	 *
	 * @param k the array of keys of the new tree map.
	 * @param v the array of corresponding values in the new tree map.
	 * @param c a (possibly type-specific) comparator.
	 * @throws IllegalArgumentException if {@code k} and {@code v} have different lengths.
	 */

	public RB_TREE_MAP(final KEY_GENERIC_TYPE[] k, final VALUE_GENERIC_TYPE v[], final Comparator<? super KEY_GENERIC_CLASS> c) {
		this(c);
		if (k.length != v.length) throw new IllegalArgumentException("The key array and the value array have different lengths (" + k.length + " and " + v.length + ")");
		for(int i = 0; i < k.length; i++) this.put(k[i], v[i]);
	}

	/** Creates a new tree map using the elements of two parallel arrays.
	 *
	 * @param k the array of keys of the new tree map.
	 * @param v the array of corresponding values in the new tree map.
	 * @throws IllegalArgumentException if {@code k} and {@code v} have different lengths.
	 */

	public RB_TREE_MAP(final KEY_GENERIC_TYPE[] k, final VALUE_GENERIC_TYPE v[]) {
		this(k, v, null);
	}

	/*
	 * The following methods implements some basic building blocks used by
	 * all accessors.  They are (and should be maintained) identical to those used in RBTreeSet.drv.
	 *
	 * The put()/remove() code is derived from Ben Pfaff's GNU libavl
	 * (https://adtinfo.org/). If you want to understand what's
	 * going on, you should have a look at the literate code contained therein
	 * first.
	 */


	/** Compares two keys in the right way.
	 *
	 * <p>This method uses the {@link #actualComparator} if it is non-{@code null}.
	 * Otherwise, it resorts to primitive type comparisons or to {@link Comparable#compareTo(Object) compareTo()}.
	 *
	 * @param k1 the first key.
	 * @param k2 the second key.
	 * @return a number smaller than, equal to or greater than 0, as usual
	 * (i.e., when k1 &lt; k2, k1 = k2 or k1 &gt; k2, respectively).
	 */

	SUPPRESS_WARNINGS_KEY_UNCHECKED
	final int compare(final KEY_GENERIC_TYPE k1, final KEY_GENERIC_TYPE k2) {
		return actualComparator == null ? KEY_CMP(k1, k2) : actualComparator.compare(k1, k2);
	}

	/** Returns the entry corresponding to the given key, if it is in the tree; {@code null}, otherwise.
	 *
	 * @param k the key to search for.
	 * @return the corresponding entry, or {@code null} if no entry with the given key exists.
	 */

	final Entry KEY_VALUE_GENERIC findKey(final KEY_GENERIC_TYPE k) {
		Entry KEY_VALUE_GENERIC e = tree;
		int cmp;

		while (e != null && (cmp = compare(k, e.key)) != 0) e = cmp < 0 ? e.left() : e.right();

		return e;
	}

	/** Locates a key.
	 *
	 * @param k a key.
	 * @return the last entry on a search for the given key; this will be
	 * the given key, if it present; otherwise, it will be either the smallest greater key or the greatest smaller key.
	 */

	final Entry KEY_VALUE_GENERIC locateKey(final KEY_GENERIC_TYPE k) {
		Entry KEY_VALUE_GENERIC e = tree, last = tree;
		int cmp = 0;

		while (e != null && (cmp = compare(k, e.key)) != 0) {
			last = e;
			e = cmp < 0 ? e.left() : e.right();
		}

		return cmp == 0 ? e : last;
	}

	/** This vector remembers the path and the direction followed during the
	 *  current insertion. It suffices for about 2<sup>32</sup> entries. */
	private transient boolean dirPath[];
	private transient Entry KEY_VALUE_GENERIC nodePath[];

	SUPPRESS_WARNINGS_KEY_VALUE_UNCHECKED_RAWTYPES
	private void allocatePaths() {
		dirPath = new boolean[64];
		nodePath = new Entry[64];
	}

#if VALUES_PRIMITIVE && !VALUE_CLASS_Boolean
	/** Adds an increment to value currently associated with a key.
	 *
	 * <p>Note that this method respects the {@linkplain #defaultReturnValue() default return value} semantics: when
	 * called with a key that does not currently appears in the map, the key
	 * will be associated with the default return value plus
	 * the given increment.
	 *
	 * @param k the key.
	 * @param incr the increment.
	 * @return the old value, or the {@linkplain #defaultReturnValue() default return value} if no value was present for the given key.
	 */
	public VALUE_GENERIC_TYPE addTo(final KEY_GENERIC_TYPE k, final VALUE_GENERIC_TYPE incr) {
		Entry KEY_VALUE_GENERIC e = add(k);
		final VALUE_GENERIC_TYPE oldValue = e.value;
		e.value += incr;
		return oldValue;
	}
#endif

	@Override
	public VALUE_GENERIC_TYPE put(final KEY_GENERIC_TYPE k, final VALUE_GENERIC_TYPE v) {
		Entry KEY_VALUE_GENERIC e = add(k);
		final VALUE_GENERIC_TYPE oldValue = e.value;
		e.value = v;
		return oldValue;
	}

	/** Returns a node with key k in the balanced tree, creating one with defRetValue if necessary.
	 *
	 * @param k the key
	 * @return a node with key k. If a node with key k already exists, then that node is returned,
	 * otherwise a new node with defRetValue is created ensuring that the tree is balanced
	 * after creation of the node.
	 */
	private Entry KEY_VALUE_GENERIC add(final KEY_GENERIC_TYPE k) {
		/* After execution of this method, modified is true iff a new entry has been inserted. */
		REQUIRE_KEY_NON_NULL(k)
		modified = false;
		int maxDepth = 0;

		Entry KEY_VALUE_GENERIC e;

		if (tree == null) { // The case of the empty tree is treated separately.
			count++;
			e = tree = lastEntry = firstEntry = new Entry KEY_VALUE_GENERIC_DIAMOND(k, defRetValue);
		}
		else {
			Entry KEY_VALUE_GENERIC p = tree;
			int cmp, i = 0;

			while(true) {
				if ((cmp = compare(k, p.key)) == 0) {
					// We clean up the node path, or we could have stale references later.
					while(i-- != 0) nodePath[i] = null;
					return p;
				}

				nodePath[i] = p;

				if (dirPath[i++] = cmp > 0) {
					if (p.succ()) {
						count++;
						e = new Entry KEY_VALUE_GENERIC_DIAMOND(k, defRetValue);

						if (p.right == null) lastEntry = e;

						e.left = p;
						e.right = p.right;

						p.right(e);

						break;
					}

					p = p.right;
				}
				else {
					if (p.pred()) {
						count++;
						e = new Entry KEY_VALUE_GENERIC_DIAMOND(k, defRetValue);

						if (p.left == null) firstEntry = e;

						e.right = p;
						e.left = p.left;

						p.left(e);

						break;
					}

					p = p.left;
				}
			}

			modified = true;
			maxDepth = i--;

			while(i > 0 && ! nodePath[i].black()) {
				if (! dirPath[i - 1]) {
					Entry KEY_VALUE_GENERIC y = nodePath[i - 1].right;

					if (! nodePath[i - 1].succ() && ! y.black()) {
						nodePath[i].black(true);
						y.black(true);
						nodePath[i - 1].black(false);
						i -= 2;
					}
					else {
						Entry KEY_VALUE_GENERIC x;

						if (! dirPath[i]) y = nodePath[i];
						else {
							x = nodePath[i];
							y = x.right;
							x.right = y.left;
							y.left = x;
							nodePath[i - 1].left = y;

							if (y.pred()) {
								y.pred(false);
								x.succ(y);
							}
						}

						x = nodePath[i - 1];
						x.black(false);
						y.black(true);

						x.left = y.right;
						y.right = x;
						if (i < 2) tree = y;
						else {
							if (dirPath[i - 2]) nodePath[i - 2].right = y;
							else nodePath[i - 2].left = y;
						}

						if (y.succ()) {
							y.succ(false);
							x.pred(y);
						}
						break;
					}
				}
				else {
					Entry KEY_VALUE_GENERIC y = nodePath[i - 1].left;

					if (! nodePath[i - 1].pred() && ! y.black()) {
						nodePath[i].black(true);
						y.black(true);
						nodePath[i - 1].black(false);
						i -= 2;
					}
					else {
						Entry KEY_VALUE_GENERIC x;

						if (dirPath[i]) y = nodePath[i];
						else {
							x = nodePath[i];
							y = x.left;
							x.left = y.right;
							y.right = x;
							nodePath[i - 1].right = y;

							if (y.succ()) {
								y.succ(false);
								x.pred(y);
							}

						}

						x = nodePath[i - 1];
						x.black(false);
						y.black(true);

						x.right = y.left;
						y.left = x;
						if (i < 2) tree = y;
						else {
							if (dirPath[i - 2]) nodePath[i - 2].right = y;
							else nodePath[i - 2].left = y;
						}

						if (y.pred()){
							y.pred(false);
							x.succ(y);
						}

						break;
					}
				}
			}
		}
		tree.black(true);
		// We clean up the node path, or we could have stale references later.
		while(maxDepth-- != 0) nodePath[maxDepth] = null;
		return e;
	}


	/* After execution of this method, {@link #modified} is true iff an entry
	has been deleted. */

	SUPPRESS_WARNINGS_KEY_UNCHECKED
	@Override
	public VALUE_GENERIC_TYPE REMOVE_VALUE(final KEY_TYPE k) {
		modified = false;

		if (tree == null) return defRetValue;

		Entry KEY_VALUE_GENERIC p = tree;
		int cmp;
		int i = 0;
		final KEY_GENERIC_TYPE kk = KEY_GENERIC_CAST k;

		while(true) {
			if ((cmp = compare(kk, p.key)) == 0) break;

			dirPath[i] = cmp > 0;
			nodePath[i] = p;

			if (dirPath[i++]) {
				if ((p = p.right()) == null) {
					// We clean up the node path, or we could have stale references later.
					while(i-- != 0) nodePath[i] = null;
					return defRetValue;
				}
			}
			else {
				if ((p = p.left()) == null) {
					// We clean up the node path, or we could have stale references later.
					while(i-- != 0) nodePath[i] = null;
					return defRetValue;
				}
			}

		}

		if (p.left == null) firstEntry = p.next();
		if (p.right == null) lastEntry = p.prev();

		if (p.succ()) {
			if (p.pred()) {
				if (i == 0) tree = p.left;
				else {
					if (dirPath[i - 1]) nodePath[i - 1].succ(p.right);
					else nodePath[i - 1].pred(p.left);
				}
			}
			else {
				p.prev().right = p.right;

				if (i == 0) tree = p.left;
				else {
					if (dirPath[i - 1]) nodePath[i - 1].right = p.left;
					else nodePath[i - 1].left = p.left;
				}
			}
		}
		else {
			boolean color;
			Entry KEY_VALUE_GENERIC r = p.right;

			if (r.pred()) {
				r.left = p.left;
				r.pred(p.pred());
				if (! r.pred()) r.prev().right = r;
				if (i == 0) tree = r;
				else {
					if (dirPath[i - 1]) nodePath[i - 1].right = r;
					else nodePath[i - 1].left = r;
				}

				color = r.black();
				r.black(p.black());
				p.black(color);
				dirPath[i] = true;
				nodePath[i++] = r;
			}
			else {
				Entry KEY_VALUE_GENERIC s;
				int j = i++;

				while(true) {
					dirPath[i] = false;
					nodePath[i++] = r;
					s = r.left;
					if (s.pred()) break;
					r = s;
				}

				dirPath[j] = true;
				nodePath[j] = s;

				if (s.succ()) r.pred(s);
				else r.left = s.right;

				s.left = p.left;

				if (! p.pred()) {
					p.prev().right = s;
					s.pred(false);
				}

				s.right(p.right);

				color = s.black();
				s.black(p.black());
				p.black(color);

				if (j == 0) tree = s;
				else {
					if (dirPath[j - 1]) nodePath[j - 1].right = s;
					else nodePath[j - 1].left = s;
				}
			}
		}

		int maxDepth = i;

		if (p.black()) {
			for(; i > 0; i--) {
				if (dirPath[i - 1] && ! nodePath[i - 1].succ() ||
					 ! dirPath[i - 1] && ! nodePath[i - 1].pred()) {
					Entry KEY_VALUE_GENERIC x = dirPath[i - 1] ? nodePath[i - 1].right : nodePath[i - 1].left;

					if (! x.black()) {
						x.black(true);
						break;
					}
				}

				if (! dirPath[i - 1]) {
					Entry KEY_VALUE_GENERIC w = nodePath[i - 1].right;

					if (! w.black()) {
						w.black(true);
						nodePath[i - 1].black(false);

						nodePath[i - 1].right = w.left;
						w.left = nodePath[i - 1];

						if (i < 2) tree = w;
						else {
							if (dirPath[i - 2]) nodePath[i - 2].right = w;
							else nodePath[i - 2].left = w;
						}

						nodePath[i] = nodePath[i - 1];
						dirPath[i] = false;
						nodePath[i - 1] = w;
						if (maxDepth == i++) maxDepth++;

						w = nodePath[i - 1].right;
					}

					if ((w.pred() || w.left.black()) &&
						 (w.succ() || w.right.black())) {
						w.black(false);
					}
					else {
						if (w.succ() || w.right.black()) {
							Entry KEY_VALUE_GENERIC y = w.left;

							y.black (true);
							w.black(false);
							w.left = y.right;
							y.right = w;
							w = nodePath[i - 1].right = y;

							if (w.succ()) {
								w.succ(false);
								w.right.pred(w);
							}
						}

						w.black(nodePath[i - 1].black());
						nodePath[i - 1].black(true);
						w.right.black(true);

						nodePath[i - 1].right = w.left;
						w.left = nodePath[i - 1];

						if (i < 2) tree = w;
						else {
							if (dirPath[i - 2]) nodePath[i - 2].right = w;
							else nodePath[i - 2].left = w;
						}

						if (w.pred()) {
							w.pred(false);
							nodePath[i - 1].succ(w);
						}
						break;
					}
				}
				else {
					Entry KEY_VALUE_GENERIC w = nodePath[i - 1].left;

					if (! w.black()) {
						w.black (true);
						nodePath[i - 1].black(false);

						nodePath[i - 1].left = w.right;
						w.right = nodePath[i - 1];

						if (i < 2) tree = w;
						else {
							if (dirPath[i - 2]) nodePath[i - 2].right = w;
							else nodePath[i - 2].left = w;
						}

						nodePath[i] = nodePath[i - 1];
						dirPath[i] = true;
						nodePath[i - 1] = w;
						if (maxDepth == i++) maxDepth++;

						w = nodePath[i - 1].left;
					}

					if ((w.pred() || w.left.black()) &&
						 (w.succ() || w.right.black())) {
						w.black(false);
					}
					else {
						if (w.pred() || w.left.black()) {
							Entry KEY_VALUE_GENERIC y = w.right;

							y.black(true);
							w.black (false);
							w.right = y.left;
							y.left = w;
							w = nodePath[i - 1].left = y;

							if (w.pred()) {
								w.pred(false);
								w.left.succ(w);
							}
						}

						w.black(nodePath[i - 1].black());
						nodePath[i - 1].black(true);
						w.left.black(true);

						nodePath[i - 1].left = w.right;
						w.right = nodePath[i - 1];

						if (i < 2) tree = w;
						else {
							if (dirPath[i - 2]) nodePath[i - 2].right = w;
							else nodePath[i - 2].left = w;
						}

						if (w.succ()) {
							w.succ(false);
							nodePath[i - 1].pred(w);
						}
						break;
					}
				}
			}

			if (tree != null) tree.black(true);
		}

		modified = true;
		count--;
		// We clean up the node path, or we could have stale references later.
		while(maxDepth-- != 0) nodePath[maxDepth] = null;
		return p.value;
	}


	@Override
	public boolean containsValue(final VALUE_TYPE v) {
		final ValueIterator i = new ValueIterator();
		VALUE_TYPE ev;

		int j = count;
		while(j-- != 0) {
			ev = i.NEXT_VALUE();
			if (VALUE_EQUALS(ev, v)) return true;
		}

		return false;
	}


	@Override
	public void clear() {
		count = 0;
		tree = null;
		entries = null;
		values = null;
		keys = null;
		firstEntry = lastEntry = null;
	}


	/** This class represent an entry in a tree map.
	 *
	 * <p>We use the only "metadata", i.e., {@link Entry#info}, to store
	 * information about color, predecessor status and successor status.
	 *
	 * <p>Note that since the class is recursive, it can be
	 * considered equivalently a tree.
	 */

	private static final class Entry KEY_VALUE_GENERIC extends ABSTRACT_MAP.BasicEntry KEY_VALUE_GENERIC implements Cloneable {
		/** The the bit in this mask is true, the node is black. */
		private static final int BLACK_MASK = 1;
		/** If the bit in this mask is true, {@link #right} points to a successor. */
		private static final int SUCC_MASK = 1 << 31;
		/** If the bit in this mask is true, {@link #left} points to a predecessor. */
		private static final int PRED_MASK = 1 << 30;
		/** The pointers to the left and right subtrees. */
		Entry KEY_VALUE_GENERIC left, right;
		/** This integers holds different information in different bits (see {@link #SUCC_MASK} and {@link #PRED_MASK}. */
		int info;

		Entry() {
			super(KEY_NULL, VALUE_NULL);
		}

		/** Creates a new entry with the given key and value.
		 *
		 * @param k a key.
		 * @param v a value.
		 */
		Entry(final KEY_GENERIC_TYPE k, final VALUE_GENERIC_TYPE v) {
			super(k, v);
			info = SUCC_MASK | PRED_MASK;
		}

		/** Returns the left subtree.
		 *
		 * @return the left subtree ({@code null} if the left
		 * subtree is empty).
		 */
		Entry KEY_VALUE_GENERIC left() {
			return (info & PRED_MASK) != 0 ? null : left;
		}

		/** Returns the right subtree.
		 *
		 * @return the right subtree ({@code null} if the right
		 * subtree is empty).
		 */
		Entry KEY_VALUE_GENERIC right() {
			return (info & SUCC_MASK) != 0 ? null : right;
		}

		/** Checks whether the left pointer is really a predecessor.
		 * @return true if the left pointer is a predecessor.
		 */
		boolean pred() {
			return (info & PRED_MASK) != 0;
		}

		/** Checks whether the right pointer is really a successor.
		 * @return true if the right pointer is a successor.
		 */
		boolean succ() {
			return (info & SUCC_MASK) != 0;
		}

		/** Sets whether the left pointer is really a predecessor.
		 * @param pred if true then the left pointer will be considered a predecessor.
		 */
		void pred(final boolean pred) {
			if (pred) info |= PRED_MASK;
			else info &= ~PRED_MASK;
		}

		/** Sets whether the right pointer is really a successor.
		 * @param succ if true then the right pointer will be considered a successor.
		 */
		void succ(final boolean succ) {
			if (succ) info |= SUCC_MASK;
			else info &= ~SUCC_MASK;
		}

		/** Sets the left pointer to a predecessor.
		 * @param pred the predecessr.
		 */
		void pred(final Entry KEY_VALUE_GENERIC pred) {
			info |= PRED_MASK;
			left = pred;
		}

		/** Sets the right pointer to a successor.
		 * @param succ the successor.
		 */
		void succ(final Entry KEY_VALUE_GENERIC succ) {
			info |= SUCC_MASK;
			right = succ;
		}

		/** Sets the left pointer to the given subtree.
		 * @param left the new left subtree.
		 */
		void left(final Entry KEY_VALUE_GENERIC left) {
			info &= ~PRED_MASK;
			this.left = left;
		}

		/** Sets the right pointer to the given subtree.
		 * @param right the new right subtree.
		 */
		void right(final Entry KEY_VALUE_GENERIC right) {
			info &= ~SUCC_MASK;
			this.right = right;
		}


		/** Returns whether this node is black.
		 * @return true iff this node is black.
		 */
		boolean black() {
			return (info & BLACK_MASK) != 0;
		}

		/** Sets whether this node is black.
		 * @param black if true, then this node becomes black; otherwise, it becomes red..
		 */
		void black(final boolean black) {
			if (black) info |= BLACK_MASK;
			else info &= ~BLACK_MASK;
		}

		/** Computes the next entry in the set order.
		 *
		 * @return the next entry ({@code null}) if this is the last entry).
		 */

		Entry KEY_VALUE_GENERIC next() {
			Entry KEY_VALUE_GENERIC next = this.right;
			if ((info & SUCC_MASK) == 0) while ((next.info & PRED_MASK) == 0) next = next.left;
			return next;
		}

		/** Computes the previous entry in the set order.
		 *
		 * @return the previous entry ({@code null}) if this is the first entry).
		 */

		Entry KEY_VALUE_GENERIC prev() {
			Entry KEY_VALUE_GENERIC prev = this.left;
			if ((info & PRED_MASK) == 0) while ((prev.info & SUCC_MASK) == 0) prev = prev.right;
			return prev;
		}

		@Override
		public VALUE_GENERIC_TYPE setValue(final VALUE_GENERIC_TYPE value) {
			final VALUE_GENERIC_TYPE oldValue = this.value;
			this.value = value;
			return oldValue;
		}

		@Override
		SUPPRESS_WARNINGS_KEY_VALUE_UNCHECKED
		public Entry KEY_VALUE_GENERIC clone() {
			Entry KEY_VALUE_GENERIC c;
			try {
				c = (Entry KEY_VALUE_GENERIC)super.clone();
			}
			catch(CloneNotSupportedException cantHappen) {
				throw new InternalError();
			}

			c.key = key;
			c.value = value;
			c.info = info;

			return c;
		}

		@Override
		@SuppressWarnings("unchecked")
		public boolean equals(final Object o) {
			if (!(o instanceof Map.Entry)) return false;
			Map.Entry <KEY_GENERIC_CLASS, VALUE_GENERIC_CLASS> e = (Map.Entry <KEY_GENERIC_CLASS, VALUE_GENERIC_CLASS>)o;

			return KEY_EQUALS(key, KEY_CLASS2TYPE(e.getKey())) && VALUE_EQUALS(value, VALUE_CLASS2TYPE(e.getValue()));
		}

		@Override
		public int hashCode() {
			return KEY2JAVAHASH_NOT_NULL(key) ^ VALUE2JAVAHASH(value);
		}


		@Override
		public String toString() {
			return key + "=>" + value;
		}

		/*
		  public void prettyPrint() {
		  prettyPrint(0);
		  }

		  public void prettyPrint(int level) {
		  if (pred()) {
		  for (int i = 0; i < level; i++)
		  System.err.print("  ");
		  System.err.println("pred: " + left);
		  }
		  else if (left != null)
		  left.prettyPrint(level +1);
		  for (int i = 0; i < level; i++)
		  System.err.print("  ");
		  System.err.println(key + "=" + value + " (" + balance() + ")");
		  if (succ()) {
		  for (int i = 0; i < level; i++)
		  System.err.print("  ");
		  System.err.println("succ: " + right);
		  }
		  else if (right != null)
		  right.prettyPrint(level + 1);
		  }*/
	}

	/*
	  public void prettyPrint() {
	  System.err.println("size: " + count);
	  if (tree != null) tree.prettyPrint();
	  }*/

	SUPPRESS_WARNINGS_KEY_UNCHECKED
	@Override
	public boolean containsKey(final KEY_TYPE k) {
		RETURN_FALSE_IF_KEY_NULL(k)
		return findKey(KEY_GENERIC_CAST k) != null;
	}

	@Override
	public int size() {
		return count;
	}

	@Override
	public boolean isEmpty() {
		return count == 0;
	}

	SUPPRESS_WARNINGS_KEY_UNCHECKED
	@Override
	public VALUE_GENERIC_TYPE GET_VALUE(final KEY_TYPE k) {
		final Entry KEY_VALUE_GENERIC e = findKey(KEY_GENERIC_CAST k);
		return e == null ? defRetValue : e.value;
	}

	@Override
	public KEY_GENERIC_TYPE FIRST_KEY() {
		if (tree == null) throw new NoSuchElementException();
		return firstEntry.key;
	}

	@Override
	public KEY_GENERIC_TYPE LAST_KEY() {
		if (tree == null) throw new NoSuchElementException();
		return lastEntry.key;
	}


	/** An abstract iterator on the whole range.
	 *
	 * <p>This class can iterate in both directions on a threaded tree.
	 */

	private class TreeIterator {
		/** The entry that will be returned by the next call to {@link java.util.ListIterator#previous()} (or {@code null} if no previous entry exists). */
		Entry KEY_VALUE_GENERIC prev;
		/** The entry that will be returned by the next call to {@link java.util.ListIterator#next()} (or {@code null} if no next entry exists). */
		Entry KEY_VALUE_GENERIC next;
		/** The last entry that was returned (or {@code null} if we did not iterate or used {@link #remove()}). */
		Entry KEY_VALUE_GENERIC curr;
		/** The current index (in the sense of a {@link java.util.ListIterator}). Note that this value is not meaningful when this {@link TreeIterator} has been created using the nonempty constructor.*/
		int index = 0;

		TreeIterator() {
			next = firstEntry;
		}

		TreeIterator(final KEY_GENERIC_TYPE k) {
			if ((next = locateKey(k)) != null) {
				if (compare(next.key, k) <= 0) {
					prev = next;
					next = next.next();
				}
				else prev = next.prev();
			}
		}

		public boolean hasNext() { return next != null; }
		public boolean hasPrevious() { return prev != null; }

		void updateNext() {
			next = next.next();
		}

		Entry KEY_VALUE_GENERIC nextEntry() {
			if (! hasNext()) throw new NoSuchElementException();
			curr = prev = next;
			index++;
			updateNext();
			return curr;
		}

		void updatePrevious() {
			prev = prev.prev();
		}

		Entry KEY_VALUE_GENERIC previousEntry() {
			if (! hasPrevious()) throw new NoSuchElementException();
			curr = next = prev;
			index--;
			updatePrevious();
			return curr;
		}

		public int nextIndex() {
			return index;
		}

		public int previousIndex() {
			return index - 1;
		}

		public void remove() {
			if (curr == null) throw new IllegalStateException();
			/* If the last operation was a next(), we are removing an entry that preceeds
			   the current index, and thus we must decrement it. */
			if (curr == prev) index--;
			next = prev = curr;
			updatePrevious();
			updateNext();
			RB_TREE_MAP.this.REMOVE_VALUE(curr.key);
			curr = null;
		}

		public int skip(final int n) {
			int i = n;
			while(i-- != 0 && hasNext()) nextEntry();
			return n - i - 1;
		}

		public int back(final int n) {
			int i = n;
			while(i-- != 0 && hasPrevious()) previousEntry();
			return n - i - 1;
		}
	}


	/** An iterator on the whole range.
	 *
	 * <p>This class can iterate in both directions on a threaded tree.
	 */

	private class EntryIterator extends TreeIterator implements ObjectListIterator<MAP.Entry KEY_VALUE_GENERIC> {
		EntryIterator() {}

		EntryIterator(final KEY_GENERIC_TYPE k) {
			super(k);
		}

		@Override
		public MAP.Entry KEY_VALUE_GENERIC next() { return nextEntry(); }
		@Override
		public MAP.Entry KEY_VALUE_GENERIC previous() { return previousEntry(); }
	}


	@Override
	SUPPRESS_WARNINGS_KEY_UNCHECKED
	public ObjectSortedSet<MAP.Entry KEY_VALUE_GENERIC> ENTRYSET() {
		if (entries == null) entries = new AbstractObjectSortedSet<MAP.Entry KEY_VALUE_GENERIC>() {
				final Comparator<? super MAP.Entry KEY_VALUE_GENERIC> comparator = (RB_TREE_MAP.this.actualComparator == null ? 
						(Comparator<MAP.Entry KEY_VALUE_GENERIC>) (x, y) -> KEY_CMP(x.ENTRY_GET_KEY(), y.ENTRY_GET_KEY()) :
						(Comparator<MAP.Entry KEY_VALUE_GENERIC>) (x, y) -> RB_TREE_MAP.this.actualComparator.compare(x.ENTRY_GET_KEY(), y.ENTRY_GET_KEY())
				);
					

				@Override
				public Comparator<? super MAP.Entry KEY_VALUE_GENERIC> comparator() { return comparator; }

				@Override
				public ObjectBidirectionalIterator<MAP.Entry KEY_VALUE_GENERIC> iterator() { return new EntryIterator(); }

				@Override
				public ObjectBidirectionalIterator<MAP.Entry KEY_VALUE_GENERIC> iterator(final MAP.Entry KEY_VALUE_GENERIC from) { return new EntryIterator(from.ENTRY_GET_KEY()); }

				@Override
				SUPPRESS_WARNINGS_KEY_UNCHECKED
				public boolean contains(final Object o) {
					if (o == null || !(o instanceof Map.Entry)) return false;
					final Map.Entry<?,?> e = (Map.Entry<?,?>)o;
					if (e.getKey() == null) return false;
#if KEYS_PRIMITIVE
					if (! (e.getKey() instanceof KEY_CLASS)) return false;
#endif
#if VALUES_PRIMITIVE
					if (e.getValue() == null || ! (e.getValue() instanceof VALUE_CLASS)) return false;
#endif
					final Entry KEY_VALUE_GENERIC f = findKey(KEY_OBJ2TYPE(KEY_GENERIC_CAST e.getKey()));
					return e.equals(f);
				}

				@Override
				SUPPRESS_WARNINGS_KEY_UNCHECKED
				public boolean remove(final Object o) {
					if (!(o instanceof Map.Entry)) return false;
					final Map.Entry<?,?> e = (Map.Entry<?,?>)o;
					if (e.getKey() == null) return false;
#if KEYS_PRIMITIVE
					if (! (e.getKey() instanceof KEY_CLASS)) return false;
#endif
#if VALUES_PRIMITIVE
					if (e.getValue() == null || ! (e.getValue() instanceof VALUE_CLASS)) return false;
#endif
					final Entry KEY_VALUE_GENERIC f = findKey(KEY_OBJ2TYPE(KEY_GENERIC_CAST e.getKey()));
					if (f == null || ! VALUE_EQUALS(f.ENTRY_GET_VALUE(), VALUE_OBJ2TYPE(e.getValue()))) return false;
					RB_TREE_MAP.this.REMOVE_VALUE(f.key);
					return true;
				}

				@Override
				public int size() { return count; }

				@Override
				public void clear() { RB_TREE_MAP.this.clear(); }

				@Override
				public MAP.Entry KEY_VALUE_GENERIC first() { return firstEntry; }

				@Override
				public MAP.Entry KEY_VALUE_GENERIC last() { return lastEntry; }

				@Override
				public ObjectSortedSet<MAP.Entry KEY_VALUE_GENERIC> subSet(MAP.Entry KEY_VALUE_GENERIC from, MAP.Entry KEY_VALUE_GENERIC to) { return subMap(from.ENTRY_GET_KEY(), to.ENTRY_GET_KEY()).ENTRYSET(); }

				@Override
				public ObjectSortedSet<MAP.Entry KEY_VALUE_GENERIC> headSet(MAP.Entry KEY_VALUE_GENERIC to) { return headMap(to.ENTRY_GET_KEY()).ENTRYSET(); }

				@Override
				public ObjectSortedSet<MAP.Entry KEY_VALUE_GENERIC> tailSet(MAP.Entry KEY_VALUE_GENERIC from) { return tailMap(from.ENTRY_GET_KEY()).ENTRYSET(); }
			};

		return entries;
	}

	/** An iterator on the whole range of keys.
	 *
	 * <p>This class can iterate in both directions on the keys of a threaded tree. We
	 * simply override the {@link java.util.ListIterator#next()}/{@link java.util.ListIterator#previous()} methods (and possibly
	 * their type-specific counterparts) so that they return keys instead of entries.
	 */
	private final class KeyIterator extends TreeIterator implements KEY_LIST_ITERATOR KEY_GENERIC {
		public KeyIterator() {}
		public KeyIterator(final KEY_GENERIC_TYPE k) { super(k); }

		@Override
		public KEY_GENERIC_TYPE NEXT_KEY() { return nextEntry().key; }

		@Override
		public KEY_GENERIC_TYPE PREV_KEY() { return previousEntry().key; }
	};


	/** A keyset implementation using a more direct implementation for iterators. */
	private class KeySet extends ABSTRACT_SORTED_MAP KEY_VALUE_GENERIC.KeySet {
		@Override
		public KEY_BIDI_ITERATOR KEY_GENERIC iterator() { return new KeyIterator();	}
		@Override
		public KEY_BIDI_ITERATOR KEY_GENERIC iterator(final KEY_GENERIC_TYPE from) { return new KeyIterator(from); }
	}

	/** Returns a type-specific sorted set view of the keys contained in this map.
	 *
	 * <p>In addition to the semantics of {@link java.util.Map#keySet()}, you can
	 * safely cast the set returned by this call to a type-specific sorted
	 * set interface.
	 *
	 * @return a type-specific sorted set view of the keys contained in this map.
	 */
	@Override
	public SORTED_SET KEY_GENERIC keySet() {
		if (keys == null) keys = new KeySet();
		return keys;
	}

	/** An iterator on the whole range of values.
	 *
	 * <p>This class can iterate in both directions on the values of a threaded tree. We
	 * simply override the {@link java.util.ListIterator#next()}/{@link java.util.ListIterator#previous()} methods (and possibly
	 * their type-specific counterparts) so that they return values instead of entries.
	 */
	private final class ValueIterator extends TreeIterator implements VALUE_LIST_ITERATOR VALUE_GENERIC {
		@Override
		public VALUE_GENERIC_TYPE NEXT_VALUE() { return nextEntry().value; }

		@Override
		public VALUE_GENERIC_TYPE PREV_VALUE() { return previousEntry().value; }
	};

	/** Returns a type-specific collection view of the values contained in this map.
	 *
	 * <p>In addition to the semantics of {@link java.util.Map#values()}, you can
	 * safely cast the collection returned by this call to a type-specific collection
	 * interface.
	 *
	 * @return a type-specific collection view of the values contained in this map.
	 */
	@Override
	public VALUE_COLLECTION VALUE_GENERIC values() {
		if (values == null) values = new VALUE_ABSTRACT_COLLECTION VALUE_GENERIC() {
				@Override
				public VALUE_ITERATOR VALUE_GENERIC iterator() { return new ValueIterator(); }
				@Override
				public boolean contains(final VALUE_TYPE k) { return containsValue(k); }
				@Override
				public int size() { return count; }
				@Override
				public void clear() { RB_TREE_MAP.this.clear(); }
			};

		return values;
	}

	@Override
	public KEY_COMPARATOR KEY_SUPER_GENERIC comparator() { return actualComparator; }

	@Override
	public SORTED_MAP KEY_VALUE_GENERIC headMap(KEY_GENERIC_TYPE to) { return new Submap(KEY_NULL, true, to, false); }

	@Override
	public SORTED_MAP KEY_VALUE_GENERIC tailMap(KEY_GENERIC_TYPE from) { return new Submap(from, false, KEY_NULL, true); }

	@Override
	public SORTED_MAP KEY_VALUE_GENERIC subMap(KEY_GENERIC_TYPE from, KEY_GENERIC_TYPE to) { return new Submap(from, false, to, false); }

	/** A submap with given range.
	 *
	 * <p>This class represents a submap. One has to specify the left/right
	 * limits (which can be set to -&infin; or &infin;). Since the submap is a
	 * view on the map, at a given moment it could happen that the limits of
	 * the range are not any longer in the main map. Thus, things such as
	 * {@link java.util.SortedMap#firstKey()} or {@link java.util.Collection#size()} must be always computed
	 * on-the-fly.
	 */
	private final class Submap extends ABSTRACT_SORTED_MAP KEY_VALUE_GENERIC implements java.io.Serializable {
		private static final long serialVersionUID = -7046029254386353129L;

		/** The start of the submap range, unless {@link #bottom} is true. */
		KEY_GENERIC_TYPE from;
		/** The end of the submap range, unless {@link #top} is true. */
		KEY_GENERIC_TYPE to;
		/** If true, the submap range starts from -&infin;. */
		boolean bottom;
		/** If true, the submap range goes to &infin;. */
		boolean top;
		/** Cached set of entries. */
		protected transient ObjectSortedSet<MAP.Entry KEY_VALUE_GENERIC> entries;
		/** Cached set of keys. */
		protected transient SORTED_SET KEY_GENERIC keys;
		/** Cached collection of values. */
		protected transient VALUE_COLLECTION VALUE_GENERIC values;

		/** Creates a new submap with given key range.
		 *
		 * @param from the start of the submap range.
		 * @param bottom if true, the first parameter is ignored and the range starts from -&infin;.
		 * @param to the end of the submap range.
		 * @param top if true, the third parameter is ignored and the range goes to &infin;.
		 */
		public Submap(final KEY_GENERIC_TYPE from, final boolean bottom, final KEY_GENERIC_TYPE to, final boolean top) {
			if (! bottom && ! top && RB_TREE_MAP.this.compare(from, to) > 0) throw new IllegalArgumentException("Start key (" + from  + ") is larger than end key (" + to + ")");

			this.from = from;
			this.bottom = bottom;
			this.to = to;
			this.top = top;
			this.defRetValue = RB_TREE_MAP.this.defRetValue;
		}

		@Override
		public void clear() {
			final SubmapIterator i = new SubmapIterator();
			while(i.hasNext()) {
				i.nextEntry();
				i.remove();
			}
		}

		/** Checks whether a key is in the submap range.
		 * @param k a key.
		 * @return true if is the key is in the submap range.
		 */
		final boolean in(final KEY_GENERIC_TYPE k) {
			return (bottom || RB_TREE_MAP.this.compare(k, from) >= 0) &&
				(top || RB_TREE_MAP.this.compare(k, to) < 0);
		}

		@Override
		public ObjectSortedSet<MAP.Entry KEY_VALUE_GENERIC> ENTRYSET() {
			if (entries == null) entries = new AbstractObjectSortedSet<MAP.Entry KEY_VALUE_GENERIC>() {
					@Override
					public ObjectBidirectionalIterator<MAP.Entry KEY_VALUE_GENERIC> iterator() {
						return new SubmapEntryIterator();
					}

					@Override
					public ObjectBidirectionalIterator<MAP.Entry KEY_VALUE_GENERIC> iterator(final MAP.Entry KEY_VALUE_GENERIC from) {
						return new SubmapEntryIterator(from.ENTRY_GET_KEY());
					}

					@Override
					public Comparator<? super MAP.Entry KEY_VALUE_GENERIC> comparator() { return RB_TREE_MAP.this.ENTRYSET().comparator(); }

					@Override
					SUPPRESS_WARNINGS_KEY_UNCHECKED
					public boolean contains(final Object o) {
						if (!(o instanceof Map.Entry)) return false;
						final Map.Entry<?,?> e = (Map.Entry<?,?>)o;
#if KEYS_PRIMITIVE
						if (e.getKey() == null || ! (e.getKey() instanceof KEY_CLASS)) return false;
#endif
#if VALUES_PRIMITIVE
						if (e.getValue() == null || ! (e.getValue() instanceof VALUE_CLASS)) return false;
#endif
						final RB_TREE_MAP.Entry KEY_VALUE_GENERIC f = findKey(KEY_OBJ2TYPE(KEY_GENERIC_CAST e.getKey()));
						return f != null && in(f.key) && e.equals(f);
					}

					@Override
					SUPPRESS_WARNINGS_KEY_UNCHECKED
					public boolean remove(final Object o) {
						if (!(o instanceof Map.Entry)) return false;
						final Map.Entry<?,?> e = (Map.Entry<?,?>)o;
#if KEYS_PRIMITIVE
						if (e.getKey() == null || ! (e.getKey() instanceof KEY_CLASS)) return false;
#endif
#if VALUES_PRIMITIVE
						if (e.getValue() == null || ! (e.getValue() instanceof VALUE_CLASS)) return false;
#endif
						final RB_TREE_MAP.Entry KEY_VALUE_GENERIC f = findKey(KEY_OBJ2TYPE(KEY_GENERIC_CAST e.getKey()));
						if (f != null && in(f.key)) Submap.this.REMOVE_VALUE(f.key);
						return f != null;
					}

					@Override
					public int size() {
						int c = 0;
						for(Iterator<?> i = iterator(); i.hasNext(); i.next()) c++;
						return c;
					}

					@Override
					public boolean isEmpty() { return ! new SubmapIterator().hasNext(); }

					@Override
					public void clear() { Submap.this.clear(); }

					@Override
					public MAP.Entry KEY_VALUE_GENERIC first() { return firstEntry(); }

					@Override
					public MAP.Entry KEY_VALUE_GENERIC last() { return lastEntry(); }

					@Override
					public ObjectSortedSet<MAP.Entry KEY_VALUE_GENERIC> subSet(MAP.Entry KEY_VALUE_GENERIC from, MAP.Entry KEY_VALUE_GENERIC to) { return subMap(from.ENTRY_GET_KEY(), to.ENTRY_GET_KEY()).ENTRYSET(); }

					@Override
					public ObjectSortedSet<MAP.Entry KEY_VALUE_GENERIC> headSet(MAP.Entry KEY_VALUE_GENERIC to) { return headMap(to.ENTRY_GET_KEY()).ENTRYSET(); }

					@Override
					public ObjectSortedSet<MAP.Entry KEY_VALUE_GENERIC> tailSet(MAP.Entry KEY_VALUE_GENERIC from) { return tailMap(from.ENTRY_GET_KEY()).ENTRYSET(); }
				};

			return entries;
		}

		private class KeySet extends ABSTRACT_SORTED_MAP KEY_VALUE_GENERIC.KeySet {
			@Override
			public KEY_BIDI_ITERATOR KEY_GENERIC iterator() { return new SubmapKeyIterator(); }
			@Override
			public KEY_BIDI_ITERATOR KEY_GENERIC iterator(final KEY_GENERIC_TYPE from) { return new SubmapKeyIterator(from); }
		}

		@Override
		public SORTED_SET KEY_GENERIC keySet() {
			if (keys == null) keys = new KeySet();
			return keys;
		}

		@Override
		public VALUE_COLLECTION VALUE_GENERIC values() {
			if (values == null) values = new VALUE_ABSTRACT_COLLECTION VALUE_GENERIC() {
					@Override
					public VALUE_ITERATOR VALUE_GENERIC iterator() { return new SubmapValueIterator(); }
					@Override
					public boolean contains(final VALUE_TYPE k) { return containsValue(k); }
					@Override
					public int size() { return Submap.this.size(); }
					@Override
					public void clear() { Submap.this.clear(); }
				};

			return values;
		}

					@Override
		SUPPRESS_WARNINGS_KEY_UNCHECKED
		public boolean containsKey(final KEY_TYPE k) {
			RETURN_FALSE_IF_KEY_NULL(k)
			return in(KEY_GENERIC_CAST k) && RB_TREE_MAP.this.containsKey(k);
		}

		@Override
		public boolean containsValue(final VALUE_TYPE v) {
			final SubmapIterator i = new SubmapIterator();
			VALUE_TYPE ev;

			while(i.hasNext()) {
				ev = i.nextEntry().value;
				if (VALUE_EQUALS(ev, v)) return true;
			}

			return false;
		}

		@Override
		SUPPRESS_WARNINGS_KEY_UNCHECKED
		public VALUE_GENERIC_TYPE GET_VALUE(final KEY_TYPE k) {
			final RB_TREE_MAP.Entry KEY_VALUE_GENERIC e;
			final KEY_GENERIC_TYPE kk = KEY_GENERIC_CAST k;
			return in(kk) && (e = findKey(kk)) != null ? e.value : this.defRetValue;
		}

		@Override
		public VALUE_GENERIC_TYPE put(final KEY_GENERIC_TYPE k, final VALUE_GENERIC_TYPE v) {
			modified = false;
			if (! in(k)) throw new IllegalArgumentException("Key (" + k + ") out of range [" + (bottom ? "-" : String.valueOf(from)) + ", " + (top ? "-" : String.valueOf(to)) + ")");
			final VALUE_GENERIC_TYPE oldValue = RB_TREE_MAP.this.put(k, v);
			return modified ? this.defRetValue : oldValue;
		}

		@Override
		SUPPRESS_WARNINGS_KEY_UNCHECKED
		public VALUE_GENERIC_TYPE REMOVE_VALUE(final KEY_TYPE k) {
			modified = false;
			if (! in(KEY_GENERIC_CAST k)) return this.defRetValue;
			final VALUE_GENERIC_TYPE oldValue = RB_TREE_MAP.this.REMOVE_VALUE(k);
			return modified ? oldValue : this.defRetValue;
		}

		@Override
		public int size() {
			final SubmapIterator i = new SubmapIterator();
			int n = 0;

			while(i.hasNext()) {
				n++;
				i.nextEntry();
			}

			return n;
		}

		@Override
		public boolean isEmpty() { return ! new SubmapIterator().hasNext(); }

		@Override
		public KEY_COMPARATOR KEY_SUPER_GENERIC comparator() { return actualComparator; }

		@Override
		public SORTED_MAP KEY_VALUE_GENERIC headMap(final KEY_GENERIC_TYPE to) {
			if (top) return new Submap(from, bottom, to, false);
			return compare(to, this.to) < 0 ? new Submap(from, bottom, to, false) : this;
		}

		@Override
		public SORTED_MAP KEY_VALUE_GENERIC tailMap(final KEY_GENERIC_TYPE from) {
			if (bottom) return new Submap(from, false, to, top);
			return compare(from, this.from) > 0 ? new Submap(from, false, to, top) : this;
		}

		@Override
		public SORTED_MAP KEY_VALUE_GENERIC subMap(KEY_GENERIC_TYPE from, KEY_GENERIC_TYPE to) {
			if (top && bottom) return new Submap(from, false, to, false);
			if (! top) to = compare(to, this.to) < 0 ? to : this.to;
			if (! bottom) from = compare(from, this.from) > 0 ? from : this.from;
			if (! top && ! bottom && from == this.from && to == this.to) return this;
			return new Submap(from, false, to, false);
		}

		/** Locates the first entry.
		 *
		 * @return the first entry of this submap, or {@code null} if the submap is empty.
		 */
		public RB_TREE_MAP.Entry KEY_VALUE_GENERIC firstEntry() {
			if (tree == null) return null;
			// If this submap goes to -infinity, we return the main map first entry; otherwise, we locate the start of the map.
			RB_TREE_MAP.Entry KEY_VALUE_GENERIC e;
			if (bottom) e = firstEntry;
			else {
				e = locateKey(from);
				// If we find either the start or something greater we're OK.
				if (compare(e.key, from) < 0) e = e.next();
			}
			// Finally, if this submap doesn't go to infinity, we check that the resulting key isn't greater than the end.
			if (e == null || ! top && compare(e.key, to) >= 0) return null;
			return e;
		}

		/** Locates the last entry.
		 *
		 * @return the last entry of this submap, or {@code null} if the submap is empty.
		 */
		public RB_TREE_MAP.Entry KEY_VALUE_GENERIC lastEntry() {
			if (tree == null) return null;
			// If this submap goes to infinity, we return the main map last entry; otherwise, we locate the end of the map.
			RB_TREE_MAP.Entry KEY_VALUE_GENERIC e;
			if (top) e = lastEntry;
			else {
				e = locateKey(to);
				// If we find something smaller than the end we're OK.
				if (compare(e.key, to) >= 0) e = e.prev();
			}
			// Finally, if this submap doesn't go to -infinity, we check that the resulting key isn't smaller than the start.
			if (e == null || ! bottom && compare(e.key, from) < 0) return null;
			return e;
		}

		@Override
		public KEY_GENERIC_TYPE FIRST_KEY() {
			RB_TREE_MAP.Entry KEY_VALUE_GENERIC e = firstEntry();
			if (e == null) throw new NoSuchElementException();
			return e.key;
		}

		@Override
		public KEY_GENERIC_TYPE LAST_KEY() {
			RB_TREE_MAP.Entry KEY_VALUE_GENERIC e = lastEntry();
			if (e == null) throw new NoSuchElementException();
			return e.key;
		}

		/** An iterator for subranges.
		 *
		 * <p>This class inherits from {@link TreeIterator}, but overrides the methods that
		 * update the pointer after a {@link java.util.ListIterator#next()} or {@link java.util.ListIterator#previous()}. If we would
		 * move out of the range of the submap we just overwrite the next or previous
		 * entry with {@code null}.
		 */
		private class SubmapIterator extends TreeIterator {
			SubmapIterator() {
				next = firstEntry();
			}

			SubmapIterator(final KEY_GENERIC_TYPE k) {
				this();

				if (next != null) {
					if (! bottom && compare(k, next.key) < 0) prev = null;
					else if (! top && compare(k, (prev = lastEntry()).key) >= 0) next = null;
					else {
						next = locateKey(k);

						if (compare(next.key, k) <= 0) {
							prev = next;
							next = next.next();
						}
						else prev = next.prev();
					}
				}
			}

			@Override
			void updatePrevious() {
				prev = prev.prev();
				if (! bottom && prev != null && RB_TREE_MAP.this.compare(prev.key, from) < 0) prev = null;
			}

			@Override
			void updateNext() {
				next = next.next();
				if (! top && next != null && RB_TREE_MAP.this.compare(next.key, to) >= 0) next = null;
			}
		}

		private class SubmapEntryIterator extends SubmapIterator implements ObjectListIterator<MAP.Entry KEY_VALUE_GENERIC> {
			SubmapEntryIterator() {}

			SubmapEntryIterator(final KEY_GENERIC_TYPE k) {
				super(k);
			}

			@Override
			public MAP.Entry KEY_VALUE_GENERIC next() { return nextEntry(); }
			@Override
			public MAP.Entry KEY_VALUE_GENERIC previous() { return previousEntry(); }
		}


		/** An iterator on a subrange of keys.
		 *
		 * <p>This class can iterate in both directions on a subrange of the
		 * keys of a threaded tree. We simply override the {@link
		 * java.util.ListIterator#next()}/{@link java.util.ListIterator#previous()} methods (and possibly their
		 * type-specific counterparts) so that they return keys instead of
		 * entries.
		 */
		private final class SubmapKeyIterator extends SubmapIterator implements KEY_LIST_ITERATOR KEY_GENERIC {
			public SubmapKeyIterator() { super(); }
			public SubmapKeyIterator(KEY_GENERIC_TYPE from) { super(from); }

			@Override
			public KEY_GENERIC_TYPE NEXT_KEY() { return nextEntry().key; }
			@Override
			public KEY_GENERIC_TYPE PREV_KEY() { return previousEntry().key; }
		};

		/** An iterator on a subrange of values.
		 *
		 * <p>This class can iterate in both directions on the values of a
		 * subrange of the keys of a threaded tree. We simply override the
		 * {@link java.util.ListIterator#next()}/{@link java.util.ListIterator#previous()} methods (and possibly their
		 * type-specific counterparts) so that they return values instead of
		 * entries.
		 */
		private final class SubmapValueIterator extends SubmapIterator implements VALUE_LIST_ITERATOR VALUE_GENERIC {
			@Override
			public VALUE_GENERIC_TYPE NEXT_VALUE() { return nextEntry().value; }
			@Override
			public VALUE_GENERIC_TYPE PREV_VALUE() { return previousEntry().value; }
		};
	}


	/** Returns a deep copy of this tree map.
	 *
	 * <p>This method performs a deep copy of this tree map; the data stored in the
	 * set, however, is not cloned. Note that this makes a difference only for object keys.
	 *
	 * @return a deep copy of this tree map.
	 */
	@Override
	SUPPRESS_WARNINGS_KEY_VALUE_UNCHECKED
	public RB_TREE_MAP KEY_VALUE_GENERIC clone() {
		RB_TREE_MAP KEY_VALUE_GENERIC c;
		try {
			c = (RB_TREE_MAP KEY_VALUE_GENERIC)super.clone();
		}
		catch(CloneNotSupportedException cantHappen) {
			throw new InternalError();
		}

		c.keys = null;
		c.values = null;
		c.entries = null;
		c.allocatePaths();

		if (count != 0) {
			// Also this apparently unfathomable code is derived from GNU libavl.
			Entry KEY_VALUE_GENERIC e, p, q, rp = new Entry KEY_VALUE_GENERIC_DIAMOND(), rq = new Entry KEY_VALUE_GENERIC_DIAMOND();

			p = rp;
			rp.left(tree);

			q = rq;
			rq.pred(null);

			while(true) {
				if (! p.pred()) {
					e = p.left.clone();
					e.pred(q.left);
					e.succ(q);
					q.left(e);

					p = p.left;
					q = q.left;
				}
				else {
					while(p.succ()) {
						p = p.right;

						if (p == null) {
							q.right = null;
							c.tree = rq.left;

							c.firstEntry = c.tree;
							while(c.firstEntry.left != null) c.firstEntry = c.firstEntry.left;
							c.lastEntry = c.tree;
							while(c.lastEntry.right != null) c.lastEntry = c.lastEntry.right;

							return c;
						}
						q = q.right;
					}

					p = p.right;
					q = q.right;
				}

				if (! p.succ()) {
					e = p.right.clone();
					e.succ(q.right);
					e.pred(q);
					q.right(e);
				}
			}
		}

		return c;
	}


	private void writeObject(java.io.ObjectOutputStream s) throws java.io.IOException {
		int n = count;
		EntryIterator i = new EntryIterator();
		Entry KEY_VALUE_GENERIC e;

		s.defaultWriteObject();

		while(n-- != 0) {
			e = i.nextEntry();
			s.WRITE_KEY(e.key);
			s.WRITE_VALUE(e.value);
		}
	}


	/** Reads the given number of entries from the input stream, returning the corresponding tree.
	 *
	 * @param s the input stream.
	 * @param n the (positive) number of entries to read.
	 * @param pred the entry containing the key that preceeds the first key in the tree.
	 * @param succ the entry containing the key that follows the last key in the tree.
	 */
	SUPPRESS_WARNINGS_KEY_VALUE_UNCHECKED
	private Entry KEY_VALUE_GENERIC readTree(final java.io.ObjectInputStream s, final int n, final Entry KEY_VALUE_GENERIC pred, final Entry KEY_VALUE_GENERIC succ) throws java.io.IOException, ClassNotFoundException {
		if (n == 1) {
			final Entry KEY_VALUE_GENERIC top = new Entry KEY_VALUE_GENERIC_DIAMOND(KEY_GENERIC_CAST s.READ_KEY(), VALUE_GENERIC_CAST s.READ_VALUE());
			top.pred(pred);
			top.succ(succ);
			top.black(true);

			return top;
		}

		if (n == 2) {
			/* We handle separately this case so that recursion will
			 *always* be on nonempty subtrees. */
			final Entry KEY_VALUE_GENERIC top = new Entry KEY_VALUE_GENERIC_DIAMOND(KEY_GENERIC_CAST s.READ_KEY(), VALUE_GENERIC_CAST s.READ_VALUE());
			top.black(true);
			top.right(new Entry KEY_VALUE_GENERIC_DIAMOND(KEY_GENERIC_CAST s.READ_KEY(), VALUE_GENERIC_CAST s.READ_VALUE()));
			top.right.pred(top);
			top.pred(pred);
			top.right.succ(succ);

			return top;
		}

		// The right subtree is the largest one.
		final int rightN = n / 2, leftN = n - rightN - 1;

		final Entry KEY_VALUE_GENERIC top = new Entry KEY_VALUE_GENERIC_DIAMOND();

		top.left(readTree(s, leftN, pred, top));

		top.key = KEY_GENERIC_CAST s.READ_KEY();
		top.value = VALUE_GENERIC_CAST s.READ_VALUE();
		top.black(true);

		top.right(readTree(s, rightN, top, succ));

		if (n + 2 == ((n + 2)  & -(n + 2))) top.right.black(false); // Quick test for determining whether n + 2 is a power of 2.

		return top;
	}

	private void readObject(java.io.ObjectInputStream s) throws java.io.IOException, ClassNotFoundException {
		s.defaultReadObject();
		/* The storedComparator is now correctly set, but we must restore
		   on-the-fly the actualComparator. */
		setActualComparator();
		allocatePaths();

		if (count != 0) {
			tree = readTree(s, count, null, null);
			Entry KEY_VALUE_GENERIC e;

			e = tree;
			while(e.left() != null) e = e.left();
			firstEntry = e;

			e = tree;
			while(e.right() != null) e = e.right();
			lastEntry = e;
		}
	}

#ifdef ASSERTS_CODE
	private void checkNodePath() {
		for(int i = nodePath.length; i-- != 0;) assert nodePath[i] == null : i;
	}

	private static KEY_VALUE_GENERIC int checkTree(Entry KEY_VALUE_GENERIC e, int d, int D) {
		if (e == null) return 0;
		if (e.black()) d++;
		if (e.left() != null) D = checkTree(e.left(), d, D);
		if (e.right() != null) D = checkTree(e.right(), d, D);
		if (e.left() == null && e.right() == null) {
			if (D == -1) D = d;
			else if (D != d) throw new AssertionError("Mismatch between number of black nodes (" + D + " and " + d + ")");
		}
		return D;
	}
#endif



#ifdef TEST

	private static long seed = System.currentTimeMillis();
	private static java.util.Random r = new java.util.Random(seed);

	private static KEY_TYPE genKey() {
#if KEY_CLASS_Byte || KEY_CLASS_Short || KEY_CLASS_Character
		return (KEY_TYPE)(r.nextInt());
#elif KEYS_PRIMITIVE
		return r.NEXT_KEY();
#else
		return Integer.toBinaryString(r.nextInt());
#endif
	}

	private static VALUE_TYPE genValue() {
#if VALUE_CLASS_Byte || VALUE_CLASS_Short || VALUE_CLASS_Character
		return (VALUE_TYPE)(r.nextInt());
#elif VALUES_PRIMITIVE
		return r.NEXT_VALUE();
#elif !VALUES_USE_REFERENCE_EQUALITY || KEYS_USE_REFERENCE_EQUALITY
		return Integer.toBinaryString(r.nextInt());
#else
		return new java.io.Serializable() {};
#endif
	}


	private static java.text.NumberFormat format = new java.text.DecimalFormat("#,###.00");
	private static java.text.FieldPosition p = new java.text.FieldPosition(0);

	private static String format(double d) {
		StringBuffer s = new StringBuffer();
		return format.format(d, s, p).toString();
	}

	private static void speedTest(int n, boolean comp) {
		int i, j;
		RB_TREE_MAP m;
		java.util.TreeMap t;
		KEY_TYPE k[] = new KEY_TYPE[n];
		KEY_TYPE nk[] = new KEY_TYPE[n];
		VALUE_TYPE v[] = new VALUE_TYPE[n];
		long ms;

		for(i = 0; i < n; i++) {
			k[i] = genKey();
			nk[i] = genKey();
			v[i] = genValue();
		}

		double totPut = 0, totYes = 0, totNo = 0, totAddTo = 0, totIterFor = 0, totIterBack = 0, totRemYes = 0, d, dd, ddd;

		if (comp) { for(j = 0; j < 20; j++) {

			t = new java.util.TreeMap();


			/* We first add all pairs to t. */
			for(i = 0; i < n;  i++) t.put(KEY2OBJ(k[i]), VALUE2OBJ(v[i]));

			/* Then we remove the first half and put it back. */
			for(i = 0; i < n/2;  i++) t.remove(KEY2OBJ(k[i]));

			ms = System.currentTimeMillis();
			for(i = 0; i < n/2;  i++) t.put(KEY2OBJ(k[i]), VALUE2OBJ(v[i]));
			d = System.currentTimeMillis() - ms;

			/* Then we remove the other half and put it back again. */
			ms = System.currentTimeMillis();
			for(i = n/2; i < n;  i++) t.remove(KEY2OBJ(k[i]));
			dd = System.currentTimeMillis() - ms ;

			ms = System.currentTimeMillis();
			for(i = n/2; i < n;  i++) t.put(KEY2OBJ(k[i]), VALUE2OBJ(v[i]));
			d += System.currentTimeMillis() - ms;
			if (j > 2) totPut += n/d;
			System.out.print("Add: " + format(n/d) +" K/s ");

			/* Then we remove again the first half. */
			ms = System.currentTimeMillis();
			for(i = 0; i < n/2;  i++) t.remove(KEY2OBJ(k[i]));
			dd += System.currentTimeMillis() - ms ;
			if (j > 2) totRemYes += n/dd;
			System.out.print("RemYes: " + format(n/dd) +" K/s ");

			/* And then we put it back. */
			for(i = 0; i < n/2;  i++) t.put(KEY2OBJ(k[i]), VALUE2OBJ(v[i]));

			#if VALUES_PRIMITIVE && !VALUE_CLASS_Boolean
	  /* we perform n/2 addTo() operations with get then put */
	  ms = System.currentTimeMillis();
	  for(i = 0; i < n/2; i++) t.put(KEY2OBJ(k[i]), (VALUE_TYPE) ((VALUE_CLASS) t.get(KEY2OBJ(k[i])) + i));
	  ddd = System.currentTimeMillis() - ms;
	  if (j > 2) totAddTo += n/ddd;
	  System.out.print("AddTo: " + format(n/ddd) +" K/s ");
	  #endif

			/* We check for pairs in t. */
			ms = System.currentTimeMillis();
			for(i = 0; i < n;  i++) t.containsKey(KEY2OBJ(k[i]));
			d = 1.0 * n / (System.currentTimeMillis() - ms);
			if (j > 2) totYes += d;
			System.out.print("Yes: " + format(d) +" K/s ");

			/* We check for pairs not in t. */
			ms = System.currentTimeMillis();
			for(i = 0; i < n;  i++) t.containsKey(KEY2OBJ(nk[i]));
			d = 1.0 * n / (System.currentTimeMillis() - ms);
			if (j > 2) totNo += d;
			System.out.print("No: " + format(d) +" K/s ");

			/* We iterate on t. */
			ms = System.currentTimeMillis();
			for(Iterator it = t.entrySet().iterator(); it.hasNext(); it.next());
			d = 1.0 * n / (System.currentTimeMillis() - ms);
			if (j > 2) totIterFor += d;
			System.out.print("IterFor: " + format(d) +" K/s ");

			System.out.println();
		}

		System.out.println();
		System.out.println("java.util Put: " + format(totPut/(j-3)) + " K/s RemYes: " + format(totRemYes/(j-3)) + " K/s Yes: " + format(totYes/(j-3)) + " K/s No: " + format(totNo/(j-3))+ "K/s AddTo: " + format(totAddTo/(j-3)) + " K/s IterFor: " + format(totIterFor/(j-3))  + " K/s");

		System.out.println();

		t = null;
		totPut = totYes = totNo = totIterFor = totIterBack = totRemYes = 0;

		}

		for(j = 0; j < 20; j++) {

			m = new RB_TREE_MAP();


			/* We first add all pairs to m. */
			for(i = 0; i < n;  i++) m.put(k[i], v[i]);

			/* Then we remove the first half and put it back. */
			for(i = 0; i < n/2;  i++) m.remove(k[i]);

			ms = System.currentTimeMillis();
			for(i = 0; i < n/2;  i++) m.put(k[i], v[i]);
			d = System.currentTimeMillis() - ms;

			/* Then we remove the other half and put it back again. */
			ms = System.currentTimeMillis();
			for(i = n/2; i < n;  i++) m.remove(k[i]);
			dd = System.currentTimeMillis() - ms ;

			ms = System.currentTimeMillis();
			for(i = n/2; i < n;  i++) m.put(k[i], v[i]);
			d += System.currentTimeMillis() - ms;
			if (j > 2) totPut += n/d;
			System.out.print("Add: " + format(n/d) +" K/s ");

			/* Then we remove again the first half. */
			ms = System.currentTimeMillis();
			for(i = 0; i < n/2;  i++) m.remove(k[i]);
			dd += System.currentTimeMillis() - ms ;
			if (j > 2) totRemYes += n/dd;
			System.out.print("RemYes: " + format(n/dd) +" K/s ");

			/* And then we put it back. */
			for(i = 0; i < n/2;  i++) m.put(k[i], v[i]);

			#if VALUES_PRIMITIVE && !VALUE_CLASS_Boolean
	  /* we perform n/2 addTo() operations with get then put */
	  ms = System.currentTimeMillis();
	  for(i = 0; i < n/2; i++) m.addTo(k[i], (VALUE_TYPE) i);
	  ddd = System.currentTimeMillis() - ms;
	  if (j > 2) totAddTo += n/ddd;
	  System.out.print("AddTo: " + format(n/ddd) +" K/s ");
	  #endif

			/* We check for pairs in m. */
			ms = System.currentTimeMillis();
			for(i = 0; i < n;  i++) m.containsKey(k[i]);
			d = 1.0 * n / (System.currentTimeMillis() - ms);
			if (j > 2) totYes += d;
			System.out.print("Yes: " + format(d) +" K/s ");

			/* We check for pairs not in m. */
			ms = System.currentTimeMillis();
			for(i = 0; i < n;  i++) m.containsKey(nk[i]);
			d = 1.0 * n / (System.currentTimeMillis() - ms);
			if (j > 2) totNo += d;
			System.out.print("No: " + format(d) +" K/s ");

			/* We iterate on m. */
			java.util.ListIterator it = (java.util.ListIterator)m.entrySet().iterator();
			ms = System.currentTimeMillis();
			for(; it.hasNext(); it.next());
			d = 1.0 * n / (System.currentTimeMillis() - ms);
			if (j > 2) totIterFor += d;
			System.out.print("IterFor: " + format(d) +" K/s ");

			/* We iterate back on m. */
			ms = System.currentTimeMillis();
			for(; it.hasPrevious(); it.previous());
			d = 1.0 * n / (System.currentTimeMillis() - ms);
			if (j > 2) totIterBack += d;
			System.out.print("IterBack: " + format(d) +" K/s ");

			System.out.println();
		}


		System.out.println();
		System.out.println("fastutil Put: " + format(totPut/(j-3)) + " K/s RemYes: " + format(totRemYes/(j-3)) + " K/s Yes: " + format(totYes/(j-3)) + " K/s No: " + format(totNo/(j-3))+ "K/s AddTo: " + format(totAddTo/(j-3)) + " K/s IterFor: " + format(totIterFor/(j-3))  + " K/s");

		System.out.println();

	}


	private static void fatal(String msg) {
		throw new AssertionError(msg);
	}

	private static void ensure(boolean cond, String msg) {
		if (cond) return;
		fatal(msg);
	}

	private static Object[] k, v, nk;
	private static KEY_TYPE kt[];
	private static KEY_TYPE nkt[];
	private static VALUE_TYPE vt[];
	private static RB_TREE_MAP topMap;

	protected static void testMaps(SORTED_MAP m, SortedMap t, int n, int level) throws Exception {
		long ms;
		boolean mThrowsIllegal, tThrowsIllegal, mThrowsNoElement, tThrowsNoElement;
		Object rt = null, rm = null;

		if (level > 4) return;


		/* Now we check that both maps agree on first/last keys. */

		mThrowsNoElement = mThrowsIllegal = tThrowsNoElement = tThrowsIllegal = false;

		try {
			m.firstKey();
		}
		catch (NoSuchElementException e) { mThrowsNoElement = true; }
		try {
			t.firstKey();
		}
		catch (NoSuchElementException e) { tThrowsNoElement = true; }

		ensure(mThrowsNoElement == tThrowsNoElement, "Error (" + level + ", " + seed + "): firstKey() divergence at start in NoSuchElementException  (" + mThrowsNoElement + ", " + tThrowsNoElement + ")");
		if (! mThrowsNoElement) ensure(t.firstKey().equals(m.firstKey()), "Error (" + level + ", " + seed + "): m and t differ at start on their first key (" + m.firstKey() + ", " + t.firstKey() +")");

		mThrowsNoElement = mThrowsIllegal = tThrowsNoElement = tThrowsIllegal = false;

		try {
			m.lastKey();
		}
		catch (NoSuchElementException e) { mThrowsNoElement = true; }
		try {
			t.lastKey();
		}
		catch (NoSuchElementException e) { tThrowsNoElement = true; }

		ensure(mThrowsNoElement == tThrowsNoElement, "Error (" + level + ", " + seed + "): lastKey() divergence at start in NoSuchElementException  (" + mThrowsNoElement + ", " + tThrowsNoElement + ")");


		if (! mThrowsNoElement) ensure(t.lastKey().equals(m.lastKey()), "Error (" + level + ", " + seed + "): m and t differ at start on their last key (" + m.lastKey() + ", " + t.lastKey() +")");


		/* Now we check that m and t are equal. */
		if (!m.equals(t) || ! t.equals(m)) System.err.println("m: " + m + " t: " + t);

		ensure(m.equals(t), "Error (" + level + ", " + seed + "): ! m.equals(t) at start");
		ensure(t.equals(m), "Error (" + level + ", " + seed + "): ! t.equals(m) at start");



		/* Now we check that m actually holds that data. */
		for(Iterator i=t.entrySet().iterator(); i.hasNext();) {
			java.util.Map.Entry e = (java.util.Map.Entry)i.next();
			ensure(java.util.Objects.equals(e.getValue(), m.get(e.getKey())), "Error (" + level + ", " + seed + "): m and t differ on an entry ("+e+") after insertion (iterating on t)");
		}

		/* Now we check that m actually holds that data, but iterating on m. */
		for(Iterator i=m.entrySet().iterator(); i.hasNext();) {
			Entry e = (Entry)i.next();
			ensure(java.util.Objects.equals(e.getValue(), t.get(e.getKey())), "Error (" + level + ", " + seed + "): m and t differ on an entry ("+e+") after insertion (iterating on m)");
		}

		/* Now we check that m actually holds the same keys. */
		for(Iterator i=t.keySet().iterator(); i.hasNext();) {
			Object o = i.next();
			ensure(m.containsKey(o), "Error (" + level + ", " + seed + "): m and t differ on a key ("+o+") after insertion (iterating on t)");
			ensure(m.keySet().contains(o), "Error (" + level + ", " + seed + "): m and t differ on a key ("+o+", in keySet()) after insertion (iterating on t)");
		}

		/* Now we check that m actually holds the same keys, but iterating on m. */
		for(Iterator i=m.keySet().iterator(); i.hasNext();) {
			Object o = i.next();
			ensure(t.containsKey(o), "Error (" + level + ", " + seed + "): m and t differ on a key after insertion (iterating on m)");
			ensure(t.keySet().contains(o), "Error (" + level + ", " + seed + "): m and t differ on a key (in keySet()) after insertion (iterating on m)");
		}


		/* Now we check that m actually hold the same values. */
		for(Iterator i=t.values().iterator(); i.hasNext();) {
			Object o = i.next();
			ensure(m.containsValue(o), "Error (" + level + ", " + seed + "): m and t differ on a value after insertion (iterating on t)");
			ensure(m.values().contains(o), "Error (" + level + ", " + seed + "): m and t differ on a value (in values()) after insertion (iterating on t)");
		}

		/* Now we check that m actually hold the same values, but iterating on m. */
		for(Iterator i=m.values().iterator(); i.hasNext();) {
			Object o = i.next();
			ensure(t.containsValue(o), "Error (" + level + ", " + seed + "): m and t differ on a value after insertion (iterating on m)");
			ensure(t.values().contains(o), "Error (" + level + ", " + seed + "): m and t differ on a value (in values()) after insertion (iterating on m)");
		}

		/* Now we check that inquiries about random data give the same answer in m and t. For
		   m we use the polymorphic method. */

		for(int i=0; i<n;  i++) {
			KEY_TYPE T = genKey();

			mThrowsNoElement = mThrowsIllegal = tThrowsNoElement = tThrowsIllegal = false;

			try {
				m.containsKey(KEY2OBJ(T));
			}
			catch (NoSuchElementException e) { mThrowsNoElement = true; }
			catch (IllegalArgumentException e) { mThrowsIllegal = true; }

			try {
				t.containsKey(KEY2OBJ(T));
			}
			catch (NoSuchElementException e) { tThrowsNoElement = true; }
			catch (IllegalArgumentException e) { tThrowsIllegal = true; }

			ensure(mThrowsNoElement == tThrowsNoElement, "Error (" + level + ", " + seed + "): containsKey() divergence in NoSuchElementException (" + mThrowsNoElement + ", " + tThrowsNoElement + ")");
			ensure(mThrowsIllegal == tThrowsIllegal, "Error (" + level + ", " + seed + "): containsKey() divergence in IllegalArgumentException (" + mThrowsIllegal + ", " + tThrowsIllegal + ")");
			if (!mThrowsNoElement && !mThrowsIllegal) {
				ensure(m.containsKey(KEY2OBJ(T)) == t.containsKey(KEY2OBJ(T)), "Error (" + level + ", " + seed + "): divergence in keys between t and m (polymorphic method)");

#if KEY_CLASS_Object && ! (VALUES_REFERENCE)
				if ((m.GET_VALUE(T) != VALUE_NULL) != ((t.get(KEY2OBJ(T)) == null ? VALUE_NULL : VALUE_OBJ2TYPE(t.get(KEY2OBJ(T)))) != VALUE_NULL) ||
					t.get(KEY2OBJ(T)) != null &&
					! VALUE2OBJ(m.GET_VALUE(T)).equals(t.get(KEY2OBJ(T))))
#else
					if ((m.get(T) != VALUE_NULL) != ((t.get(KEY2OBJ(T)) == null ? VALUE_NULL : VALUE_OBJ2TYPE(t.get(KEY2OBJ(T)))) != VALUE_NULL) ||
						t.get(KEY2OBJ(T)) != null &&
						! m.get(KEY2OBJ(T)).equals(t.get(KEY2OBJ(T))))
#endif
						{
							ensure(false, "Error (" + level + ", " + seed + "): divergence between t and m (polymorphic method)");
						}
			}
		}

		/* Again, we check that inquiries about random data give the same answer in m and t, but
		   for m we use the standard method. */

		for(int i=0; i<n;  i++) {
			KEY_TYPE T = genKey();

			mThrowsNoElement = mThrowsIllegal = tThrowsNoElement = tThrowsIllegal = false;

			try {
				m.get(KEY2OBJ(T));
			}
			catch (NoSuchElementException e) { mThrowsNoElement = true; }
			catch (IllegalArgumentException e) { mThrowsIllegal = true; }

			try {
				t.get(KEY2OBJ(T));
			}
			catch (NoSuchElementException e) { tThrowsNoElement = true; }
			catch (IllegalArgumentException e) { tThrowsIllegal = true; }

			ensure(mThrowsNoElement == tThrowsNoElement, "Error (" + level + ", " + seed + "): get() divergence in NoSuchElementException for " + T + " (" + mThrowsNoElement + ", " + tThrowsNoElement + ")");
			ensure(mThrowsIllegal == tThrowsIllegal, "Error (" + level + ", " + seed + "): get() divergence in IllegalArgumentException for " + T + " (" + mThrowsIllegal + ", " + tThrowsIllegal + ")");
			if (!mThrowsNoElement && !mThrowsIllegal) ensure(java.util.Objects.equals(m.get(KEY2OBJ(T)), t.get(KEY2OBJ(T))), "Error (" + level + ", " + seed + "): divergence between t and m (standard method)");
		}

		/* Now we put and remove random data in m and t, checking that the result is the same. */

		for(int i=0; i<20*n;  i++) {
			KEY_TYPE T = genKey();
			VALUE_TYPE U = genValue();

			mThrowsNoElement = mThrowsIllegal = tThrowsNoElement = tThrowsIllegal = false;

			try {
				rm = m.put(KEY2OBJ(T), VALUE2OBJ(U));
			}
			catch (NoSuchElementException e) { mThrowsNoElement = true; }
			catch (IllegalArgumentException e) { mThrowsIllegal = true; }

			try {
				rt = t.put(KEY2OBJ(T), VALUE2OBJ(U));
			}
			catch (NoSuchElementException e) { tThrowsNoElement = true; }
			catch (IllegalArgumentException e) { tThrowsIllegal = true; }


			ensure(mThrowsNoElement == tThrowsNoElement, "Error (" + level + ", " + seed + "): put() divergence in NoSuchElementException for " + T + " (" + mThrowsNoElement + ", " + tThrowsNoElement + ")");
			ensure(mThrowsIllegal == tThrowsIllegal, "Error (" + level + ", " + seed + "): put() divergence in IllegalArgumentException for " + T + " (" + mThrowsIllegal + ", " + tThrowsIllegal + ")");
			if (!mThrowsNoElement && !mThrowsIllegal) ensure(java.util.Objects.equals(rm, rt), "Error (" + level + ", " + seed + "): divergence in put() between t and m (" + rt + ", " + rm + ")");

			T = genKey();

			mThrowsNoElement = mThrowsIllegal = tThrowsNoElement = tThrowsIllegal = false;

			try {
				rm = m.remove(KEY2OBJ(T));
			}
			catch (NoSuchElementException e) { mThrowsNoElement = true; }
			catch (IllegalArgumentException e) { mThrowsIllegal = true; }

			try {
				rt = t.remove(KEY2OBJ(T));
			}
			catch (NoSuchElementException e) { tThrowsNoElement = true; }
			catch (IllegalArgumentException e) { tThrowsIllegal = true; }


			ensure(mThrowsNoElement == tThrowsNoElement, "Error (" + level + ", " + seed + "): remove() divergence in NoSuchElementException for " + T + " (" + mThrowsNoElement + ", " + tThrowsNoElement + ")");
			ensure(mThrowsIllegal == tThrowsIllegal, "Error (" + level + ", " + seed + "): remove() divergence in IllegalArgumentException for " + T + " (" + mThrowsIllegal + ", " + tThrowsIllegal + ")");
			if (!mThrowsNoElement && !mThrowsIllegal) ensure(java.util.Objects.equals(rm, rt), "Error (" + level + ", " + seed + "): divergence in remove() between t and m (" + rt + ", " + rm + ")");
		}

		ensure(m.equals(t), "Error (" + level + ", " + seed + "): ! m.equals(t) after removal");
		ensure(t.equals(m), "Error (" + level + ", " + seed + "): ! t.equals(m) after removal");

		/* Now we check that m actually holds the same data. */

		for(Iterator i=t.entrySet().iterator(); i.hasNext();) {
			java.util.Map.Entry e = (java.util.Map.Entry)i.next();
			ensure(java.util.Objects.equals(e.getValue(), m.get(e.getKey())), "Error (" + level + ", " + seed + "): m and t differ on an entry ("+e+") after removal (iterating on t)");
		}

		/* Now we check that m actually holds that data, but iterating on m. */

		for(Iterator i=m.entrySet().iterator(); i.hasNext();) {
			Entry e = (Entry)i.next();
			ensure(java.util.Objects.equals(e.getValue(), t.get(e.getKey())), "Error (" + level + ", " + seed + "): m and t differ on an entry ("+e+") after removal (iterating on m)");
		}

		/* Now we check that m actually holds the same keys. */

		for(Iterator i=t.keySet().iterator(); i.hasNext();) {
			Object o = i.next();
			ensure(m.containsKey(o), "Error (" + level + ", " + seed + "): m and t differ on a key ("+o+") after removal (iterating on t)");
			ensure(m.keySet().contains(o), "Error (" + level + ", " + seed + "): m and t differ on a key ("+o+", in keySet()) after removal (iterating on t)");
		}

		/* Now we check that m actually holds the same keys, but iterating on m. */

		for(Iterator i=m.keySet().iterator(); i.hasNext();) {
			Object o = i.next();
			ensure(t.containsKey(o), "Error (" + level + ", " + seed + "): m and t differ on a key after removal (iterating on m)");
			ensure(t.keySet().contains(o), "Error (" + level + ", " + seed + "): m and t differ on a key (in keySet()) after removal (iterating on m)");
		}


		/* Now we check that m actually hold the same values. */

		for(Iterator i=t.values().iterator(); i.hasNext();) {
			Object o = i.next();
			ensure(m.containsValue(o), "Error (" + level + ", " + seed + "): m and t differ on a value after removal (iterating on t)");
			ensure(m.values().contains(o), "Error (" + level + ", " + seed + "): m and t differ on a value (in values()) after removal (iterating on t)");
		}

		/* Now we check that m actually hold the same values, but iterating on m. */

		for(Iterator i=m.values().iterator(); i.hasNext();) {
			Object o = i.next();
			ensure(t.containsValue(o), "Error (" + level + ", " + seed + "): m and t differ on a value after removal (iterating on m)");
			ensure(t.values().contains(o), "Error (" + level + ", " + seed + "): m and t differ on a value (in values()) after removal (iterating on m)");
		}

		/* Now we check that both maps agree on first/last keys. */

		mThrowsNoElement = mThrowsIllegal = tThrowsNoElement = tThrowsIllegal = false;

		try {
			m.firstKey();
		}
		catch (NoSuchElementException e) { mThrowsNoElement = true; }
		try {
			t.firstKey();
		}
		catch (NoSuchElementException e) { tThrowsNoElement = true; }

		ensure(mThrowsNoElement == tThrowsNoElement, "Error (" + level + ", " + seed + "): firstKey() divergence in NoSuchElementException  (" + mThrowsNoElement + ", " + tThrowsNoElement + ")");
		if (! mThrowsNoElement) ensure(t.firstKey().equals(m.firstKey()), "Error (" + level + ", " + seed + "): m and t differ on their first key (" + m.firstKey() + ", " + t.firstKey() +")");

		mThrowsNoElement = mThrowsIllegal = tThrowsNoElement = tThrowsIllegal = false;

		try {
			m.lastKey();
		}
		catch (NoSuchElementException e) { mThrowsNoElement = true; }
		try {
			t.lastKey();
		}
		catch (NoSuchElementException e) { tThrowsNoElement = true; }

		ensure(mThrowsNoElement == tThrowsNoElement, "Error (" + level + ", " + seed + "): lastKey() divergence in NoSuchElementException  (" + mThrowsNoElement + ", " + tThrowsNoElement + ")");

		if (! mThrowsNoElement) ensure(t.lastKey().equals(m.lastKey()), "Error (" + level + ", " + seed + "): m and t differ on their last key (" + m.lastKey() + ", " + t.lastKey() +")");

		/* Now we check cloning. */

		if (level == 0) {
			ensure(m.equals(((RB_TREE_MAP)m).clone()), "Error (" + level + ", " + seed + "): m does not equal m.clone()");
			ensure(((RB_TREE_MAP)m).clone().equals(m), "Error (" + level + ", " + seed + "): m.clone() does not equal m");
			m = (RB_TREE_MAP)((RB_TREE_MAP)m).clone();
		}

		int h = m.hashCode();


		/* Now we save and read m. */

		SORTED_MAP m2 = null;

		{
			java.io.File ff = new java.io.File("it.unimi.dsi.fastutil.test." + m.getClass().getSimpleName() + "." + n);
			java.io.OutputStream os = new java.io.FileOutputStream(ff);
			java.io.ObjectOutputStream oos = new java.io.ObjectOutputStream(os);

			oos.writeObject(m);
			oos.close();

			java.io.InputStream is = new java.io.FileInputStream(ff);
			java.io.ObjectInputStream ois = new java.io.ObjectInputStream(is);

			m2 = (SORTED_MAP)ois.readObject();
			ois.close();
			ff.delete();
		}

#if !VALUES_USE_REFERENCE_EQUALITY
		ensure(m2.hashCode() == h, "Error (" + level + ", " + seed + "): hashCode() changed after save/read");

		/* Now we check that m2 actually holds that data. */

		ensure(m2.equals(t), "Error (" + level + ", " + seed + "): ! m2.equals(t) after save/read");
		ensure(t.equals(m2), "Error (" + level + ", " + seed + "): ! t.equals(m2) after save/read");
		/* Now we take out of m everything, and check that it is empty. */
#else
		m2.clear();
		m2.putAll(m);
#endif

		for(Iterator i=t.keySet().iterator(); i.hasNext();) m2.remove(i.next());

		ensure(m2.isEmpty(), "Error (" + level + ", " + seed + "): m2 is not empty (as it should be)");

		/* Now we play with iterators. */

		{
			java.util.ListIterator i, j;
			Map.Entry E, F;
			Object J;
			i = (java.util.ListIterator)m.entrySet().iterator();
			j = new java.util.LinkedList(t.entrySet()).listIterator();

			for(int k = 0; k < 2*n; k++) {
				ensure(i.hasNext() == j.hasNext(), "Error (" + level + ", " + seed + "): divergence in hasNext()");
				ensure(i.hasPrevious() == j.hasPrevious(), "Error (" + level + ", " + seed + "): divergence in hasPrevious()");

				if (r.nextFloat() < .8 && i.hasNext()) {
					ensure((E=(Entry)i.next()).getKey().equals(J = (F=(Map.Entry)j.next()).getKey()), "Error (" + level + ", " + seed + "): divergence in next()");

					if (r.nextFloat() < 0.3) {
						i.remove();
						j.remove();
						t.remove(J);
					}
					else if (r.nextFloat() < 0.3) {
						Object U = VALUE2OBJ(genValue());
						E.setValue(U);
		                t.put(F.getKey(), U);
					}
				}
				else if (r.nextFloat() < .2 && i.hasPrevious()) {
					ensure((E=(Entry)i.previous()).getKey().equals(J = (F=(Map.Entry)j.previous()).getKey()), "Error (" + level + ", " + seed + "): divergence in previous()");

					if (r.nextFloat() < 0.3) {
						i.remove();
						j.remove();
						t.remove(J);
					}
					else if (r.nextFloat() < 0.3) {
						Object U = VALUE2OBJ(genValue());
						E.setValue(U);
		                t.put(F.getKey(), U);
					}
				}

				ensure(i.nextIndex() == j.nextIndex(), "Error (" + level + ", " + seed + "): divergence in nextIndex()");
				ensure(i.previousIndex() == j.previousIndex(), "Error (" + level + ", " + seed + "): divergence in previousIndex()");

			}
		}

		{
			boolean badPrevious = false;
			Object previous = null;
			it.unimi.dsi.fastutil.BidirectionalIterator i;
			java.util.ListIterator j;
			Object I, J;
			KEY_TYPE from = genKey();
			j = new java.util.LinkedList(t.keySet()).listIterator();
			while(j.hasNext()) {
				Object k = j.next();
				if (((Comparable)k).compareTo(KEY2OBJ(from)) > 0) {
					badPrevious = true;
					j.previous();
					break;
				}
				previous = k;
			}

			i = (it.unimi.dsi.fastutil.BidirectionalIterator)((SORTED_SET)m.keySet()).iterator(from);

			for(int k = 0; k < 2*n; k++) {
				ensure(i.hasNext() == j.hasNext(), "Error (" + level + ", " + seed + "): divergence in hasNext() (iterator with starting point " + from + ")");
				ensure(i.hasPrevious() == j.hasPrevious() || badPrevious && (i.hasPrevious() == (previous != null)), "Error (" + level + ", " + seed + "): divergence in hasPrevious() (iterator with starting point " + from + ")" + badPrevious);

				if (r.nextFloat() < .8 && i.hasNext()) {
					ensure((I = i.next()).equals(J = j.next()), "Error (" + level + ", " + seed + "): divergence in next() (" + I + ", " + J + ", iterator with starting point " + from + ")");
					//System.err.println("Done next " + I + " " + J + "  " + badPrevious);

					badPrevious = false;

					if (r.nextFloat() < 0.5) {
						//System.err.println("Removing in next");
						i.remove();
						j.remove();
						t.remove(J);
					}
				}
				else if (!badPrevious && r.nextFloat() < .2 && i.hasPrevious()) {
					ensure((I = i.previous()).equals(J = j.previous()), "Error (" + level + ", " + seed + "): divergence in previous() (" + I + ", " + J + ", iterator with starting point " + from + ")");

					if (r.nextFloat() < 0.5) {
						//System.err.println("Removing in prev");
						i.remove();
						j.remove();
						t.remove(J);
					}
				}
			}

		}

		/* Now we check that m actually holds that data. */

		ensure(m.equals(t), "Error (" + level + ", " + seed + "): ! m.equals(t) after iteration");
		ensure(t.equals(m), "Error (" + level + ", " + seed + "): ! t.equals(m) after iteration");

		/* Now we select a pair of keys and create a submap. */

		if (! m.isEmpty()) {
			java.util.ListIterator i;
			Object start = m.firstKey(), end = m.firstKey();
			for(i = (java.util.ListIterator)m.keySet().iterator(); i.hasNext() && r.nextFloat() < .3; start = end = i.next());
			for(; i.hasNext() && r.nextFloat() < .95; end = i.next());

			//System.err.println("Checking subMap from " + start + " to " + end + " (level=" + (level+1) + ")...");
			testMaps((SORTED_MAP)m.subMap((KEY_CLASS) start, (KEY_CLASS)end), t.subMap(start, end), n, level + 1);

			ensure(m.equals(t), "Error (" + level + ", " + seed + "): ! m.equals(t) after subMap");
			ensure(t.equals(m), "Error (" + level + ", " + seed + "): ! t.equals(m) after subMap");

			//System.err.println("Checking headMap to " + end + " (level=" + (level+1) + ")...");
			testMaps((SORTED_MAP)m.headMap((KEY_CLASS)end), t.headMap(end), n, level + 1);

			ensure(m.equals(t), "Error (" + level + ", " + seed + "): ! m.equals(t) after headMap");
			ensure(t.equals(m), "Error (" + level + ", " + seed + "): ! t.equals(m) after headMap");

			//System.err.println("Checking tailMap from " + start + " (level=" + (level+1) + ")...");
			testMaps((SORTED_MAP)m.tailMap((KEY_CLASS)start), t.tailMap(start), n, level + 1);

			ensure(m.equals(t), "Error (" + level + ", " + seed + "): ! m.equals(t) after tailMap");
			ensure(t.equals(m), "Error (" + level + ", " + seed + "): ! t.equals(m) after tailMap");
		}


	}


	private static void runTest(int n) throws Exception {
		RB_TREE_MAP m = new RB_TREE_MAP();
		SortedMap t = new java.util.TreeMap();
		topMap = m;
		k = new Object[n];
		v = new Object[n];
		nk = new Object[n];
		kt = new KEY_TYPE[n];
		nkt = new KEY_TYPE[n];
		vt = new VALUE_TYPE[n];

		for(int i = 0; i < n; i++) {
#if KEY_CLASS_Object
			k[i] = kt[i] = genKey();
			nk[i] = nkt[i] = genKey();
#else
			k[i] = new KEY_CLASS(kt[i] = genKey());
			nk[i] = new KEY_CLASS(nkt[i] = genKey());
#endif
#if VALUES_REFERENCE
			v[i] = vt[i] = genValue();
#else
			v[i] = new VALUE_CLASS(vt[i] = genValue());
#endif
		}

		/* We add pairs to t. */
		for(int i = 0; i < n;  i++) t.put(k[i], v[i]);

		/* We add to m the same data */
		m.putAll(t);

		testMaps(m, t, n, 0);

		System.out.println("Test OK");
		return;
	}


	public static void main(String args[]) throws Exception {
		int n  = Integer.parseInt(args[1]);
		if (args.length > 2) r = new java.util.Random(seed = Long.parseLong(args[2]));

		try {
			if ("speedTest".equals(args[0]) || "speedComp".equals(args[0])) speedTest(n, "speedComp".equals(args[0]));
			else if ("test".equals(args[0])) runTest(n);
		} catch(Throwable e) {
			e.printStackTrace(System.err);
			System.err.println("seed: " + seed);
			throw e;
		}
	}

#endif


}