/*
 * 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.ObjectBidirectionalIterable;
import it.unimi.dsi.fastutil.objects.ObjectBidirectionalIterator;
import it.unimi.dsi.fastutil.objects.ObjectSortedSet;
import it.unimi.dsi.fastutil.objects.ObjectSortedSets;
#endif

import PACKAGE.SORTED_MAP.FastSortedEntrySet;

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

/** A class providing static methods and objects that do useful things with type-specific sorted maps.
 *
 * @see java.util.Collections
 */

public final class SORTED_MAPS {

	private SORTED_MAPS() {}

	/** Returns a comparator for entries based on a given comparator on keys.
	 *
	 * @param comparator a comparator on keys.
	 * @return the associated comparator on entries.
	 */
	public static KEY_GENERIC Comparator<? super Map.Entry<KEY_GENERIC_CLASS, ?>> entryComparator(final KEY_COMPARATOR KEY_SUPER_GENERIC comparator) {
		return (Comparator<Map.Entry<KEY_GENERIC_CLASS, ?>>) (x, y) -> comparator.compare(KEY_CLASS2TYPE(x.getKey()), KEY_CLASS2TYPE(y.getKey()));
	}

	/** Returns a bidirectional iterator that will be {@linkplain FastSortedEntrySet fast}, if possible, on the {@linkplain Map#entrySet() entry set} of the provided {@code map}.
	 * @param map a map from which we will try to extract a (fast) bidirectional iterator on the entry set.
	 * @return a bidirectional iterator on the entry set of the given map that will be fast, if possible.
	 * @since 8.0.0
	 */
	SUPPRESS_WARNINGS_KEY_VALUE_UNCHECKED
	public static KEY_VALUE_GENERIC ObjectBidirectionalIterator<MAP.Entry KEY_VALUE_GENERIC> fastIterator(SORTED_MAP KEY_VALUE_GENERIC map) {
		final ObjectSortedSet<MAP.Entry KEY_VALUE_GENERIC> entries = map.ENTRYSET();
		return entries instanceof SORTED_MAP.FastSortedEntrySet ? ((SORTED_MAP.FastSortedEntrySet KEY_VALUE_GENERIC) entries).fastIterator() : entries.iterator();
	}

	/** Returns an iterable yielding a bidirectional iterator that will be {@linkplain FastSortedEntrySet fast}, if possible, on the {@linkplain Map#entrySet() entry set} of the provided {@code map}.
	 * @param map a map from which we will try to extract an iterable yielding a (fast) bidirectional iterator on the entry set.
	 * @return an iterable yielding a bidirectional iterator on the entry set of the given map that will be fast, if possible.
	 * @since 8.0.0
	 */
	SUPPRESS_WARNINGS_KEY_VALUE_UNCHECKED
	public static KEY_VALUE_GENERIC ObjectBidirectionalIterable<MAP.Entry KEY_VALUE_GENERIC> fastIterable(SORTED_MAP KEY_VALUE_GENERIC map) {
		final ObjectSortedSet<MAP.Entry KEY_VALUE_GENERIC> entries = map.ENTRYSET();
		return entries instanceof SORTED_MAP.FastSortedEntrySet ? ((SORTED_MAP.FastSortedEntrySet KEY_VALUE_GENERIC)entries)::fastIterator : entries;
	}


	/** An immutable class representing an empty type-specific sorted map.
	 *
	 * <p>This class may be useful to implement your own in case you subclass
	 * a type-specific sorted map.
	 */

	public static class EmptySortedMap KEY_VALUE_GENERIC extends MAPS.EmptyMap KEY_VALUE_GENERIC implements SORTED_MAP KEY_VALUE_GENERIC, java.io.Serializable, Cloneable {

		private static final long serialVersionUID = -7046029254386353129L;

		protected EmptySortedMap() {}

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

		@Override
		public ObjectSortedSet<MAP.Entry KEY_VALUE_GENERIC> ENTRYSET() { return ObjectSortedSets.EMPTY_SET; }

#if KEYS_PRIMITIVE || VALUES_PRIMITIVE
		/** {@inheritDoc}
		 * @deprecated Please use the corresponding type-specific method instead. */
		@Deprecated
#else
		/** {@inheritDoc} */
#endif
		@Override
		public ObjectSortedSet<Map.Entry<KEY_GENERIC_CLASS, VALUE_GENERIC_CLASS>> entrySet() { return ObjectSortedSets.EMPTY_SET; }

		SUPPRESS_WARNINGS_KEY_UNCHECKED
		@Override
		public SORTED_SET KEY_GENERIC keySet() { return SORTED_SETS.EMPTY_SET; }

		SUPPRESS_WARNINGS_KEY_VALUE_UNCHECKED
		@Override
		public SORTED_MAP KEY_VALUE_GENERIC subMap(final KEY_GENERIC_TYPE from, final KEY_GENERIC_TYPE to) { return EMPTY_MAP; }

		SUPPRESS_WARNINGS_KEY_VALUE_UNCHECKED
		@Override
		public SORTED_MAP KEY_VALUE_GENERIC headMap(final KEY_GENERIC_TYPE to) { return EMPTY_MAP; }

		SUPPRESS_WARNINGS_KEY_VALUE_UNCHECKED
		@Override
		public SORTED_MAP KEY_VALUE_GENERIC tailMap(final KEY_GENERIC_TYPE from) { return EMPTY_MAP; }

		@Override
		public KEY_GENERIC_TYPE FIRST_KEY() { throw new NoSuchElementException(); }

		@Override
		public KEY_GENERIC_TYPE LAST_KEY() { throw new NoSuchElementException(); }

#if KEYS_PRIMITIVE
		/** {@inheritDoc}
		 * @deprecated Please use the corresponding type-specific method instead. */
		@Deprecated
		@Override
		public SORTED_MAP KEY_VALUE_GENERIC headMap(KEY_GENERIC_CLASS oto) { return headMap(KEY_CLASS2TYPE(oto)); }

		/** {@inheritDoc}
		 * @deprecated Please use the corresponding type-specific method instead. */
		@Deprecated
		@Override
		public SORTED_MAP KEY_VALUE_GENERIC tailMap(KEY_GENERIC_CLASS ofrom) { return tailMap(KEY_CLASS2TYPE(ofrom)); }

		/** {@inheritDoc}
		 * @deprecated Please use the corresponding type-specific method instead. */
		@Deprecated
		@Override
		public SORTED_MAP KEY_VALUE_GENERIC subMap(KEY_GENERIC_CLASS ofrom, KEY_GENERIC_CLASS oto) { return subMap(KEY_CLASS2TYPE(ofrom), KEY_CLASS2TYPE(oto)); }

		/** {@inheritDoc}
		 * @deprecated Please use the corresponding type-specific method instead. */
		@Deprecated
		@Override
		public KEY_GENERIC_CLASS firstKey() { return KEY2OBJ(FIRST_KEY()); }

		/** {@inheritDoc}
		 * @deprecated Please use the corresponding type-specific method instead. */
		@Deprecated
		@Override
		public KEY_GENERIC_CLASS lastKey() { return KEY2OBJ(LAST_KEY()); }
#endif
	}



	/** An empty sorted map (immutable). It is serializable and cloneable.
	 */
	SUPPRESS_WARNINGS_KEY_VALUE_RAWTYPES
	public static final EmptySortedMap EMPTY_MAP = new EmptySortedMap();

#if KEYS_REFERENCE || VALUES_REFERENCE
	/** Returns an empty sorted map (immutable). It is serializable and cloneable.
	 *
	 * <p>This method provides a typesafe access to {@link #EMPTY_MAP}.
	 * @return an empty sorted map (immutable).
	 */
	@SuppressWarnings("unchecked")
	public static KEY_VALUE_GENERIC SORTED_MAP KEY_VALUE_GENERIC emptyMap() {
		return EMPTY_MAP;
	}
#endif

	/** An immutable class representing a type-specific singleton sorted map.
	 *
	 * <p>This class may be useful to implement your own in case you subclass
	 * a type-specific sorted map.
	 */

	public static class Singleton KEY_VALUE_GENERIC extends MAPS.Singleton KEY_VALUE_GENERIC implements SORTED_MAP KEY_VALUE_GENERIC, java.io.Serializable, Cloneable {

		private static final long serialVersionUID = -7046029254386353129L;

		protected final KEY_COMPARATOR KEY_SUPER_GENERIC comparator;

		protected Singleton(final KEY_GENERIC_TYPE key, final VALUE_GENERIC_TYPE value, KEY_COMPARATOR KEY_SUPER_GENERIC comparator) {
			super(key, value);
			this.comparator = comparator;
		}

		protected Singleton(final KEY_GENERIC_TYPE key, final VALUE_GENERIC_TYPE value) {
			this(key, value, null);
		}

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

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

		SUPPRESS_WARNINGS_KEY_UNCHECKED
		@Override
		public ObjectSortedSet<MAP.Entry KEY_VALUE_GENERIC> ENTRYSET() { if (entries == null) entries = ObjectSortedSets.singleton(new ABSTRACT_MAP.BasicEntry KEY_VALUE_GENERIC_DIAMOND(key, value), entryComparator(comparator)); return (ObjectSortedSet<MAP.Entry KEY_VALUE_GENERIC>)entries; }

#if KEYS_PRIMITIVE || VALUES_PRIMITIVE
		/** {@inheritDoc}
		 * @deprecated Please use the corresponding type-specific method instead. */
		@Deprecated
#else
		/** {@inheritDoc} */
#endif
		@Override
		@SuppressWarnings({ "rawtypes", "unchecked" })
		public ObjectSortedSet<Map.Entry<KEY_GENERIC_CLASS, VALUE_GENERIC_CLASS>> entrySet() { return (ObjectSortedSet)ENTRYSET(); }

		@Override
		public SORTED_SET KEY_GENERIC keySet() { if (keys == null) keys = SORTED_SETS.singleton(key, comparator); return (SORTED_SET KEY_GENERIC)keys; }

		SUPPRESS_WARNINGS_KEY_VALUE_UNCHECKED
		@Override
		public SORTED_MAP KEY_VALUE_GENERIC subMap(final KEY_GENERIC_TYPE from, final KEY_GENERIC_TYPE to) { if (compare(from, key) <= 0 && compare(key, to) < 0) return this; return EMPTY_MAP; }

		SUPPRESS_WARNINGS_KEY_VALUE_UNCHECKED
		@Override
		public SORTED_MAP KEY_VALUE_GENERIC headMap(final KEY_GENERIC_TYPE to) { if (compare(key, to) < 0) return this; return EMPTY_MAP; }

		SUPPRESS_WARNINGS_KEY_VALUE_UNCHECKED
		@Override
		public SORTED_MAP KEY_VALUE_GENERIC tailMap(final KEY_GENERIC_TYPE from) { if (compare(from, key) <= 0) return this; return EMPTY_MAP; }

		@Override
		public KEY_GENERIC_TYPE FIRST_KEY() { return key; }

		@Override
		public KEY_GENERIC_TYPE LAST_KEY() { return key; }

#if KEYS_PRIMITIVE
		/** {@inheritDoc}
		 * @deprecated Please use the corresponding type-specific method instead. */
		@Deprecated
		@Override
		public SORTED_MAP KEY_VALUE_GENERIC headMap(KEY_GENERIC_CLASS oto) { return headMap(KEY_CLASS2TYPE(oto)); }

		/** {@inheritDoc}
		 * @deprecated Please use the corresponding type-specific method instead. */
		@Deprecated
		@Override
		public SORTED_MAP KEY_VALUE_GENERIC tailMap(KEY_GENERIC_CLASS ofrom) { return tailMap(KEY_CLASS2TYPE(ofrom)); }

		/** {@inheritDoc}
		 * @deprecated Please use the corresponding type-specific method instead. */
		@Deprecated
		@Override
		public SORTED_MAP KEY_VALUE_GENERIC subMap(KEY_GENERIC_CLASS ofrom, KEY_GENERIC_CLASS oto) { return subMap(KEY_CLASS2TYPE(ofrom), KEY_CLASS2TYPE(oto)); }

		/** {@inheritDoc}
		 * @deprecated Please use the corresponding type-specific method instead. */
		@Deprecated
		@Override
		public KEY_GENERIC_CLASS firstKey() { return KEY2OBJ(FIRST_KEY()); }

		/** {@inheritDoc}
		 * @deprecated Please use the corresponding type-specific method instead. */
		@Deprecated
		@Override
		public KEY_GENERIC_CLASS lastKey() { return KEY2OBJ(LAST_KEY()); }
#endif
	}

	/** Returns a type-specific immutable sorted map containing only the specified pair. The returned sorted map is serializable and cloneable.
	 *
	 * <p>Note that albeit the returned map is immutable, its default return value may be changed.
	 *
	 * @param key the only key of the returned sorted map.
	 * @param value the only value of the returned sorted map.
	 * @return a type-specific immutable sorted map containing just the pair {@code &lt;key,value&gt;}.
	 */

	public static KEY_VALUE_GENERIC SORTED_MAP KEY_VALUE_GENERIC singleton(final KEY_GENERIC_CLASS key, VALUE_GENERIC_CLASS value) { return new Singleton KEY_VALUE_GENERIC_DIAMOND(KEY_CLASS2TYPE(key), VALUE_CLASS2TYPE(value));}

	/** Returns a type-specific immutable sorted map containing only the specified pair. The returned sorted map is serializable and cloneable.
	 *
	 * <p>Note that albeit the returned map is immutable, its default return value may be changed.
	 *
	 * @param key the only key of the returned sorted map.
	 * @param value the only value of the returned sorted map.
	 * @param comparator the comparator to use in the returned sorted map.
	 * @return a type-specific immutable sorted map containing just the pair {@code &lt;key,value&gt;}.
	 */

	public static KEY_VALUE_GENERIC SORTED_MAP KEY_VALUE_GENERIC singleton(final KEY_GENERIC_CLASS key, VALUE_GENERIC_CLASS value, KEY_COMPARATOR KEY_SUPER_GENERIC comparator) { return new Singleton KEY_VALUE_GENERIC_DIAMOND(KEY_CLASS2TYPE(key), VALUE_CLASS2TYPE(value), comparator); }

#if KEYS_PRIMITIVE || VALUES_PRIMITIVE

	/** Returns a type-specific immutable sorted map containing only the specified pair. The returned sorted map is serializable and cloneable.
	 *
	 * <p>Note that albeit the returned map is immutable, its default return value may be changed.
	 *
	 * @param key the only key of the returned sorted map.
	 * @param value the only value of the returned sorted map.
	 * @return a type-specific immutable sorted map containing just the pair {@code &lt;key,value&gt;}.
	 */

	public static KEY_VALUE_GENERIC SORTED_MAP KEY_VALUE_GENERIC singleton(final KEY_GENERIC_TYPE key, final VALUE_GENERIC_TYPE value) {
		return new Singleton KEY_VALUE_GENERIC_DIAMOND(key, value);
	}

	/** Returns a type-specific immutable sorted map containing only the specified pair. The returned sorted map is serializable and cloneable.
	 *
	 * <p>Note that albeit the returned map is immutable, its default return value may be changed.
	 *
	 * @param key the only key of the returned sorted map.
	 * @param value the only value of the returned sorted map.
	 * @param comparator the comparator to use in the returned sorted map.
	 * @return a type-specific immutable sorted map containing just the pair {@code &lt;key,value&gt;}.
	 */

	public static KEY_VALUE_GENERIC SORTED_MAP KEY_VALUE_GENERIC singleton(final KEY_GENERIC_TYPE key, final VALUE_GENERIC_TYPE value, KEY_COMPARATOR KEY_SUPER_GENERIC comparator) {
		return new Singleton KEY_VALUE_GENERIC_DIAMOND(key, value, comparator);
	}

#endif


		/** A synchronized wrapper class for sorted maps. */

	public static class SynchronizedSortedMap KEY_VALUE_GENERIC extends MAPS.SynchronizedMap KEY_VALUE_GENERIC implements SORTED_MAP KEY_VALUE_GENERIC, java.io.Serializable {

		private static final long serialVersionUID = -7046029254386353129L;

		protected final SORTED_MAP KEY_VALUE_GENERIC sortedMap;

		protected SynchronizedSortedMap(final SORTED_MAP KEY_VALUE_GENERIC m, final Object sync) {
			super(m, sync);
			sortedMap = m;
		}

		protected SynchronizedSortedMap(final SORTED_MAP KEY_VALUE_GENERIC m) {
			super(m);
			sortedMap = m;
		}

		@Override
		public KEY_COMPARATOR KEY_SUPER_GENERIC comparator() { synchronized(sync) { return sortedMap.comparator(); } }

		@Override
		public ObjectSortedSet<MAP.Entry KEY_VALUE_GENERIC> ENTRYSET() { if (entries == null) entries = ObjectSortedSets.synchronize(sortedMap.ENTRYSET(), sync); return (ObjectSortedSet<MAP.Entry KEY_VALUE_GENERIC>)entries; }

#if KEYS_PRIMITIVE || VALUES_PRIMITIVE
		/** {@inheritDoc}
		 * @deprecated Please use the corresponding type-specific method instead. */
		@Deprecated
#else
		/** {@inheritDoc} */
#endif
		@Override
		@SuppressWarnings({ "rawtypes", "unchecked" })
		public ObjectSortedSet<Map.Entry<KEY_GENERIC_CLASS, VALUE_GENERIC_CLASS>> entrySet() { return (ObjectSortedSet)ENTRYSET(); }

		@Override
		public SORTED_SET KEY_GENERIC keySet() { if (keys == null) keys = SORTED_SETS.synchronize(sortedMap.keySet(), sync); return (SORTED_SET KEY_GENERIC)keys; }

		@Override
		public SORTED_MAP KEY_VALUE_GENERIC subMap(final KEY_GENERIC_TYPE from, final KEY_GENERIC_TYPE to) { return new SynchronizedSortedMap KEY_VALUE_GENERIC_DIAMOND(sortedMap.subMap(from, to), sync); }

		@Override
		public SORTED_MAP KEY_VALUE_GENERIC headMap(final KEY_GENERIC_TYPE to) { return new SynchronizedSortedMap KEY_VALUE_GENERIC_DIAMOND(sortedMap.headMap(to), sync); }

		@Override
		public SORTED_MAP KEY_VALUE_GENERIC tailMap(final KEY_GENERIC_TYPE from) { return new SynchronizedSortedMap KEY_VALUE_GENERIC_DIAMOND(sortedMap.tailMap(from), sync); }

		@Override
		public KEY_GENERIC_TYPE FIRST_KEY() {  synchronized(sync) { return sortedMap.FIRST_KEY(); } }

		@Override
		public KEY_GENERIC_TYPE LAST_KEY() {  synchronized(sync) { return sortedMap.LAST_KEY(); } }

#if KEYS_PRIMITIVE
		/** {@inheritDoc}
		 * @deprecated Please use the corresponding type-specific method instead. */
		@Deprecated
		@Override
		public KEY_GENERIC_CLASS firstKey() {  synchronized(sync) { return sortedMap.firstKey(); } }

		/** {@inheritDoc}
		 * @deprecated Please use the corresponding type-specific method instead. */
		@Deprecated
		@Override
		public KEY_GENERIC_CLASS lastKey() {  synchronized(sync) { return sortedMap.lastKey(); } }

		/** {@inheritDoc}
		 * @deprecated Please use the corresponding type-specific method instead. */
		@Deprecated
		@Override
		public SORTED_MAP KEY_VALUE_GENERIC subMap(final KEY_GENERIC_CLASS from, final KEY_GENERIC_CLASS to) { return new SynchronizedSortedMap KEY_VALUE_GENERIC_DIAMOND(sortedMap.subMap(from, to), sync); }

		/** {@inheritDoc}
		 * @deprecated Please use the corresponding type-specific method instead. */
		@Deprecated
		@Override
		public SORTED_MAP KEY_VALUE_GENERIC headMap(final KEY_GENERIC_CLASS to) { return new SynchronizedSortedMap KEY_VALUE_GENERIC_DIAMOND(sortedMap.headMap(to), sync); }

		/** {@inheritDoc}
		 * @deprecated Please use the corresponding type-specific method instead. */
		@Deprecated
		@Override
		public SORTED_MAP KEY_VALUE_GENERIC tailMap(final KEY_GENERIC_CLASS from) { return new SynchronizedSortedMap KEY_VALUE_GENERIC_DIAMOND(sortedMap.tailMap(from), sync); }
#endif


	}

	/** Returns a synchronized type-specific sorted map backed by the given type-specific sorted map.
	 *
	 * @param m the sorted map to be wrapped in a synchronized sorted map.
	 * @return a synchronized view of the specified sorted map.
	 * @see java.util.Collections#synchronizedSortedMap(SortedMap)
	 */
	public static KEY_VALUE_GENERIC SORTED_MAP KEY_VALUE_GENERIC synchronize(final SORTED_MAP KEY_VALUE_GENERIC m) { return new SynchronizedSortedMap KEY_VALUE_GENERIC_DIAMOND(m); }

	/** Returns a synchronized type-specific sorted map backed by the given type-specific sorted map, using an assigned object to synchronize.
	 *
	 * @param m the sorted map to be wrapped in a synchronized sorted map.
	 * @param sync an object that will be used to synchronize the access to the sorted sorted map.
	 * @return a synchronized view of the specified sorted map.
	 * @see java.util.Collections#synchronizedSortedMap(SortedMap)
	 */

	public static KEY_VALUE_GENERIC SORTED_MAP KEY_VALUE_GENERIC synchronize(final SORTED_MAP KEY_VALUE_GENERIC m, final Object sync) { return new SynchronizedSortedMap KEY_VALUE_GENERIC_DIAMOND(m, sync); }




	/** An unmodifiable wrapper class for sorted maps. */

	public static class UnmodifiableSortedMap KEY_VALUE_GENERIC extends MAPS.UnmodifiableMap KEY_VALUE_GENERIC implements SORTED_MAP KEY_VALUE_GENERIC, java.io.Serializable {

		private static final long serialVersionUID = -7046029254386353129L;

		protected final SORTED_MAP KEY_GENERIC_VALUE_EXTENDS_GENERIC sortedMap;

		protected UnmodifiableSortedMap(final SORTED_MAP KEY_GENERIC_VALUE_EXTENDS_GENERIC m) {
			super(m);
			sortedMap = m;
		}

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

		@SuppressWarnings({ "rawtypes", "unchecked" })
		@Override
		public ObjectSortedSet<MAP.Entry KEY_VALUE_GENERIC> ENTRYSET() { if (entries == null) entries = ObjectSortedSets.unmodifiable((ObjectSortedSet)sortedMap.ENTRYSET()); return (ObjectSortedSet<MAP.Entry KEY_VALUE_GENERIC>)entries; }

#if KEYS_PRIMITIVE || VALUES_PRIMITIVE
		/** {@inheritDoc}
		 * @deprecated Please use the corresponding type-specific method instead. */
		@Deprecated
#else
		/** {@inheritDoc} */
#endif
		@Override
		@SuppressWarnings({ "rawtypes", "unchecked" })
		public ObjectSortedSet<Map.Entry<KEY_GENERIC_CLASS, VALUE_GENERIC_CLASS>> entrySet() { return (ObjectSortedSet)ENTRYSET(); }

		@Override
		public SORTED_SET KEY_GENERIC keySet() { if (keys == null) keys = SORTED_SETS.unmodifiable(sortedMap.keySet()); return (SORTED_SET KEY_GENERIC)keys; }

		@Override
		public SORTED_MAP KEY_VALUE_GENERIC subMap(final KEY_GENERIC_TYPE from, final KEY_GENERIC_TYPE to) { return new UnmodifiableSortedMap KEY_VALUE_GENERIC_DIAMOND(sortedMap.subMap(from, to)); }

		@Override
		public SORTED_MAP KEY_VALUE_GENERIC headMap(final KEY_GENERIC_TYPE to) { return new UnmodifiableSortedMap KEY_VALUE_GENERIC_DIAMOND(sortedMap.headMap(to)); }

		@Override
		public SORTED_MAP KEY_VALUE_GENERIC tailMap(final KEY_GENERIC_TYPE from) { return new UnmodifiableSortedMap KEY_VALUE_GENERIC_DIAMOND(sortedMap.tailMap(from)); }

		@Override
		public KEY_GENERIC_TYPE FIRST_KEY() {  return sortedMap.FIRST_KEY(); }

		@Override
		public KEY_GENERIC_TYPE LAST_KEY() {  return sortedMap.LAST_KEY(); }

#if KEYS_PRIMITIVE
		/** {@inheritDoc}
		 * @deprecated Please use the corresponding type-specific method instead. */
		@Deprecated
		@Override
		public KEY_GENERIC_CLASS firstKey() {  return sortedMap.firstKey(); }

		/** {@inheritDoc}
		 * @deprecated Please use the corresponding type-specific method instead. */
		@Deprecated
		@Override
		public KEY_GENERIC_CLASS lastKey() {  return sortedMap.lastKey(); }

		/** {@inheritDoc}
		 * @deprecated Please use the corresponding type-specific method instead. */
		@Deprecated
		@Override
		public SORTED_MAP KEY_VALUE_GENERIC subMap(final KEY_GENERIC_CLASS from, final KEY_GENERIC_CLASS to) { return new UnmodifiableSortedMap KEY_VALUE_GENERIC_DIAMOND(sortedMap.subMap(from, to)); }

		/** {@inheritDoc}
		 * @deprecated Please use the corresponding type-specific method instead. */
		@Deprecated
		@Override
		public SORTED_MAP KEY_VALUE_GENERIC headMap(final KEY_GENERIC_CLASS to) { return new UnmodifiableSortedMap KEY_VALUE_GENERIC_DIAMOND(sortedMap.headMap(to)); }

		/** {@inheritDoc}
		 * @deprecated Please use the corresponding type-specific method instead. */
		@Deprecated
		@Override
		public SORTED_MAP KEY_VALUE_GENERIC tailMap(final KEY_GENERIC_CLASS from) { return new UnmodifiableSortedMap KEY_VALUE_GENERIC_DIAMOND(sortedMap.tailMap(from)); }
#endif


	}

	/** Returns an unmodifiable type-specific sorted map backed by the given type-specific sorted map.
	 *
	 * @param m the sorted map to be wrapped in an unmodifiable sorted map.
	 * @return an unmodifiable view of the specified sorted map.
	 * @see java.util.Collections#unmodifiableSortedMap(SortedMap)
	 */
	public static KEY_VALUE_GENERIC SORTED_MAP KEY_VALUE_GENERIC unmodifiable(final SORTED_MAP KEY_GENERIC_VALUE_EXTENDS_GENERIC m) { return new UnmodifiableSortedMap KEY_VALUE_GENERIC_DIAMOND(m); }



#if defined(TEST) && ! KEYS_USE_REFERENCE_EQUALITY

	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) {
		System.out.println("There are presently no speed tests for this class.");
	}

	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 SORTED_MAP topMap;

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

		if (level > 1) return;


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

		mThrowsNoElement = mThrowsIllegal = tThrowsNoElement = tThrowsIllegal = false;

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

		ensure(mThrowsNoElement == tThrowsNoElement, "Error (" + level + ", " + seed + "): firstKey() divergence at start in java.util.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 (java.util.NoSuchElementException e) { mThrowsNoElement = true; }
		try {
			t.lastKey();
		}
		catch (java.util.NoSuchElementException e) { tThrowsNoElement = true; }

		ensure(mThrowsNoElement == tThrowsNoElement, "Error (" + level + ", " + seed + "): lastKey() divergence at start in java.util.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(java.util.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(java.util.Iterator i=m.entrySet().iterator(); i.hasNext();) {
			java.util.Map.Entry e = (java.util.Map.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(java.util.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(java.util.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(java.util.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(java.util.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 (java.util.NoSuchElementException e) { mThrowsNoElement = true; }
			catch (IllegalArgumentException e) { mThrowsIllegal = true; }

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

			ensure(mThrowsNoElement == tThrowsNoElement, "Error (" + level + ", " + seed + "): containsKey() divergence in java.util.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 (java.util.NoSuchElementException e) { mThrowsNoElement = true; }
			catch (IllegalArgumentException e) { mThrowsIllegal = true; }

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

			ensure(mThrowsNoElement == tThrowsNoElement, "Error (" + level + ", " + seed + "): get() divergence in java.util.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 = mThrowsUnsupp = tThrowsUnsupp = false;

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

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

			ensure(mThrowsNoElement == tThrowsNoElement, "Error (" + level + ", " + seed + "): put() divergence in java.util.NoSuchElementException for " + T + " (" + mThrowsNoElement + ", " + tThrowsNoElement + ")");
			ensure(mThrowsIllegal == tThrowsIllegal, "Error (" + level + ", " + seed + "): put() divergence in IllegalArgumentException for " + T + " (" + mThrowsIllegal + ", " + tThrowsIllegal + ")");
			//ensure(mThrowsUnsupp == tThrowsUnsupp, "Error (" + level + ", " + seed + "): put() divergence in UnsupportedOperationException for " + T + " (" + mThrowsUnsupp + ", " + tThrowsUnsupp + ") " + m);
			if (!mThrowsNoElement && !mThrowsIllegal && !mThrowsUnsupp) 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 = mThrowsUnsupp = tThrowsUnsupp = false;

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

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


			ensure(mThrowsNoElement == tThrowsNoElement, "Error (" + level + ", " + seed + "): remove() divergence in java.util.NoSuchElementException for " + T + " (" + mThrowsNoElement + ", " + tThrowsNoElement + ")");
			ensure(mThrowsIllegal == tThrowsIllegal, "Error (" + level + ", " + seed + "): remove() divergence in IllegalArgumentException for " + T + " (" + mThrowsIllegal + ", " + tThrowsIllegal + ")");
			//ensure(mThrowsUnsupp == tThrowsUnsupp, "Error (" + level + ", " + seed + "): remove() divergence in UnsupportedOperationException for " + T + " (" + mThrowsUnsupp + ", " + tThrowsUnsupp + ") " + m);
			if (!mThrowsNoElement && !mThrowsIllegal && !mThrowsUnsupp) 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(java.util.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(java.util.Iterator i=m.entrySet().iterator(); i.hasNext();) {
			java.util.Map.Entry e = (java.util.Map.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(java.util.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(java.util.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(java.util.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(java.util.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 (java.util.NoSuchElementException e) { mThrowsNoElement = true; }
		try {
			t.firstKey();
		}
		catch (java.util.NoSuchElementException e) { tThrowsNoElement = true; }

		ensure(mThrowsNoElement == tThrowsNoElement, "Error (" + level + ", " + seed + "): firstKey() divergence in java.util.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 (java.util.NoSuchElementException e) { mThrowsNoElement = true; }
		try {
			t.lastKey();
		}
		catch (java.util.NoSuchElementException e) { tThrowsNoElement = true; }

		ensure(mThrowsNoElement == tThrowsNoElement, "Error (" + level + ", " + seed + "): lastKey() divergence in java.util.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(((Singleton)m).clone()), "Error (" + level + ", " + seed + "): m does not equal m.clone()");
			ensure(((Singleton)m).clone().equals(m), "Error (" + level + ", " + seed + "): m.clone() does not equal m");
			m = (SORTED_MAP)((Singleton)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. */
#endif

		/* Now we play with iterators. */

		{
			java.util.ListIterator i, j;
			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(((java.util.Map.Entry)i.next()).getKey().equals(J = ((Map.Entry)j.next()).getKey()), "Error (" + level + ", " + seed + "): divergence in next()");

				}
				else if (r.nextFloat() < .2 && i.hasPrevious()) {
					ensure(((java.util.Map.Entry)i.previous()).getKey().equals(J = ((Map.Entry)j.previous()).getKey()), "Error (" + level + ", " + seed + "): divergence in previous()");

				}

				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) {
					}
				}
				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) {
					}
				}
			}

		}

		/* 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 test() throws Exception {
		int n = 1;
		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
		}

		SORTED_MAP m = new Singleton(kt[0], vt[0]);
		topMap = m;
		SortedMap t1 = new java.util.TreeMap();
		t1.put(k[0], v[0]);
		SortedMap t = java.util.Collections.unmodifiableSortedMap(t1);

		testMaps(m, t, n, 0);

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


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

		try {
			test();
		} catch(Throwable e) {
			e.printStackTrace(System.err);
			System.err.println("seed: " + seed);
			throw e;
		}
	}

#endif


}