ArrayList.drv

/*
 * Copyright (C) 2002-2023 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;

import java.util.Arrays;
import java.util.Collection;
import java.util.Iterator;
import java.util.RandomAccess;
import java.util.NoSuchElementException;
#if KEYS_REFERENCE
import java.lang.reflect.Array;
import java.util.Comparator;
import java.util.stream.Collector;
import java.util.function.Consumer;
#endif

#if KEYS_PRIMITIVE

/** A type-specific array-based list; provides some additional methods that use polymorphism to avoid (un)boxing.
 *
 * <p>This class implements a lightweight, fast, open, optimized,
 * reuse-oriented version of array-based lists. Instances of this class
 * represent a list with an array that is enlarged as needed when new entries
 * are created (by increasing its current length by 50%), but is
 * <em>never</em> made smaller (even on a {@link #clear()}). A family of
 * {@linkplain #trim() trimming methods} lets you control the size of the
 * backing array; this is particularly useful if you reuse instances of this class.
 * Range checks are equivalent to those of {@code java.util}'s classes, but
 * they are delayed as much as possible. The backing array is exposed by the
 * {@link #elements()} method.
 *
 * <p>This class implements the bulk methods {@code removeElements()},
 * {@code addElements()} and {@code getElements()} using
 * high-performance system calls (e.g., {@link
 * System#arraycopy(Object,int,Object,int,int) System.arraycopy()}) instead of
 * expensive loops.
 *
 * @see java.util.ArrayList
 */

public class ARRAY_LIST KEY_GENERIC extends ABSTRACT_LIST KEY_GENERIC implements RandomAccess, Cloneable, java.io.Serializable {
	private static final long serialVersionUID = -7046029254386353130L;


#else

/** A type-specific array-based list; provides some additional methods that use polymorphism to avoid (un)boxing.
 *
 * <p>This class implements a lightweight, fast, open, optimized,
 * reuse-oriented version of array-based lists. Instances of this class
 * represent a list with an array that is enlarged as needed when new entries
 * are created (by increasing its current length by 50%), but is
 * <em>never</em> made smaller (even on a {@link #clear()}). A family of
 * {@linkplain #trim() trimming methods} lets you control the size of the
 * backing array; this is particularly useful if you reuse instances of this class.
 * Range checks are equivalent to those of {@link java.util}'s classes, but
 * they are delayed as much as possible.
 *
 * <p>The backing array is exposed by the {@link #elements()} method. If an instance
 * of this class was created {@linkplain #wrap(Object[],int) by wrapping},
 * backing-array reallocations will be performed using reflection, so that
 * {@link #elements()} can return an array of the same type of the original array: the comments
 * about efficiency made in {@link it.unimi.dsi.fastutil.objects.ObjectArrays} apply here.
 * Moreover, you must take into consideration that assignment to an array
 * not of type {@code Object[]} is slower due to type checking.
 *
 * <p>This class implements the bulk methods {@code removeElements()},
 * {@code addElements()} and {@code getElements()} using
 * high-performance system calls (e.g., {@link
 * System#arraycopy(Object,int,Object,int,int) System.arraycopy()}) instead of
 * expensive loops.
 *
 * @see java.util.ArrayList
 */

public class ARRAY_LIST KEY_GENERIC extends ABSTRACT_LIST KEY_GENERIC implements RandomAccess, Cloneable, java.io.Serializable {
	private static final long serialVersionUID = -7046029254386353131L;


#endif

	/** The initial default capacity of an array list. */
	public static final int DEFAULT_INITIAL_CAPACITY = 10;

#if ! KEYS_PRIMITIVE
	/** Whether the backing array was passed to {@code wrap()}. In
	 * this case, we must reallocate with the same type of array. */
	protected final boolean wrapped;
#endif

	/** The backing array. */
	protected transient KEY_GENERIC_TYPE a[];

	/** The current actual size of the list (never greater than the backing-array length). */
	protected int size;

	/** Ensures that the component type of the given array is the proper type.
	 * This is irrelevant for primitive types, so it will just do a trivial copy.
	 * But for Reference types, you can have a {@code String[]} masquerading as an {@code Object[]},
	 * which is a case we need to prepare for because we let the user give an array to use directly
	 * with {@link #wrap}.
	 */
	SUPPRESS_WARNINGS_KEY_UNCHECKED
	private static final KEY_GENERIC KEY_GENERIC_TYPE[] copyArraySafe(KEY_GENERIC_TYPE[] a, int length) {
		if (length == 0) return KEY_GENERIC_ARRAY_CAST ARRAYS.EMPTY_ARRAY;
#if KEYS_PRIMITIVE
		return java.util.Arrays.copyOf(a, length);
#else
		return (KEY_GENERIC_TYPE[])java.util.Arrays.copyOf(a, length, KEY_TYPE[].class);
#endif
	}

	private static final KEY_GENERIC KEY_GENERIC_TYPE[] copyArrayFromSafe(ARRAY_LIST KEY_GENERIC l) {
		return copyArraySafe(l.a, l.size);
	}

	/** Creates a new array list using a given array.
	 *
	 * <p>This constructor is only meant to be used by the wrapping methods.
	 *
	 * @param a the array that will be used to back this array list.
	 */

	protected ARRAY_LIST(final KEY_GENERIC_TYPE a[], @SuppressWarnings("unused") boolean wrapped) {
		this.a = a;
#if ! KEYS_PRIMITIVE
		this.wrapped = wrapped;
#endif
	}

	SUPPRESS_WARNINGS_KEY_UNCHECKED
	private void initArrayFromCapacity(final int capacity) {
		if (capacity < 0) throw new IllegalArgumentException("Initial capacity (" + capacity + ") is negative");
		if (capacity == 0) a = KEY_GENERIC_ARRAY_CAST ARRAYS.EMPTY_ARRAY;
		else a = KEY_GENERIC_ARRAY_CAST new KEY_TYPE[capacity];
	}

	/** Creates a new array list with given capacity.
	 *
	 * @param capacity the initial capacity of the array list (may be 0).
	 */
	public ARRAY_LIST(final int capacity) {
		initArrayFromCapacity(capacity);
#if ! KEYS_PRIMITIVE
		this.wrapped = false;
#endif
	}

	/** Creates a new array list with {@link #DEFAULT_INITIAL_CAPACITY} capacity. */

	SUPPRESS_WARNINGS_KEY_UNCHECKED
	public ARRAY_LIST() {
		a = KEY_GENERIC_ARRAY_CAST ARRAYS.DEFAULT_EMPTY_ARRAY; // We delay allocation
#if ! KEYS_PRIMITIVE
		wrapped = false;
#endif
	}

	/** Creates a new array list and fills it with a given collection.
	 *
	 * @param c a collection that will be used to fill the array list.
	 */

	public ARRAY_LIST(final Collection<? extends KEY_GENERIC_CLASS> c) {
		if (c instanceof ARRAY_LIST) {
			a = copyArrayFromSafe((ARRAY_LIST KEY_EXTENDS_GENERIC)c);
			size = a.length;
		} else {
			initArrayFromCapacity(c.size());
			if (c instanceof LIST) {
				((LIST KEY_EXTENDS_GENERIC)c).getElements(0, a, 0, size = c.size());
			} else {
#if KEYS_PRIMITIVE
				size = ITERATORS.unwrap(ITERATORS.AS_KEY_ITERATOR(c.iterator()), a);
#else
				size = ITERATORS.unwrap(c.iterator(), a);
#endif
			}
		}
#if ! KEYS_PRIMITIVE
		this.wrapped = false;
#endif
	}

	/** Creates a new array list and fills it with a given type-specific collection.
	 *
	 * @param c a type-specific collection that will be used to fill the array list.
	 */

	public ARRAY_LIST(final COLLECTION KEY_EXTENDS_GENERIC c) {
		if (c instanceof ARRAY_LIST) {
			a = copyArrayFromSafe((ARRAY_LIST KEY_EXTENDS_GENERIC)c);
			size = a.length;
		} else {
			initArrayFromCapacity(c.size());
			if (c instanceof LIST) {
				((LIST KEY_EXTENDS_GENERIC)c).getElements(0, a, 0, size = c.size());
			} else {
				size = ITERATORS.unwrap(c.iterator(), a);
			}
		}
#if ! KEYS_PRIMITIVE
		this.wrapped = false;
#endif
	}

	/** Creates a new array list and fills it with a given type-specific list.
	 *
	 * @param l a type-specific list that will be used to fill the array list.
	 */

	public ARRAY_LIST(final LIST KEY_EXTENDS_GENERIC l) {
		if (l instanceof ARRAY_LIST) {
			a = copyArrayFromSafe((ARRAY_LIST KEY_EXTENDS_GENERIC)l);
			size = a.length;
		} else {
			initArrayFromCapacity(l.size());
			l.getElements(0, a, 0, size = l.size());
		}
#if ! KEYS_PRIMITIVE
		this.wrapped = false;
#endif
	}

	/** Creates a new array list and fills it with the elements of a given array.
	 *
	 * @param a an array whose elements will be used to fill the array list.
	 */

	public ARRAY_LIST(final KEY_GENERIC_TYPE a[]) {
		this(a, 0, a.length);
	}

	/** Creates a new array list and fills it with the elements of a given array.
	 *
	 * @param a an array whose elements will be used to fill the array list.
	 * @param offset the first element to use.
	 * @param length the number of elements to use.
	 */

	public ARRAY_LIST(final KEY_GENERIC_TYPE a[], final int offset, final int length) {
		this(length);
		System.arraycopy(a, offset, this.a, 0, length);
		size = length;
	}

	/** Creates a new array list and fills it with the elements returned by an iterator..
	 *
	 * @param i an iterator whose returned elements will fill the array list.
	 */

	public ARRAY_LIST(final Iterator<? extends KEY_GENERIC_CLASS> i) {
		this();
		while(i.hasNext()) this.add(KEY_CLASS2TYPE(i.next()));
	}

	/** Creates a new array list and fills it with the elements returned by a type-specific iterator..
	 *
	 * @param i a type-specific iterator whose returned elements will fill the array list.
	 */

	public ARRAY_LIST(final KEY_ITERATOR KEY_EXTENDS_GENERIC i) {
		this();
		while(i.hasNext()) this.add(i.NEXT_KEY());
	}

#if KEYS_PRIMITIVE
	/** Returns the backing array of this list.
	 *
	 * @return the backing array.
	 */

	public KEY_GENERIC_TYPE[] elements() {
		return a;
	}
#else
	/** Returns the backing array of this list.
	 *
	 * <p>If this array list was created by wrapping a given array, it is guaranteed
	 * that the type of the returned array will be the same. Otherwise, the returned
	 * array will be of type {@link Object Object[]} (in spite of the declared return type).
	 *
	 * <p><strong>Warning</strong>: This behaviour may cause (unfathomable)
	 * run-time errors if a method expects an array
	 * actually of type {@code K[]}, but this methods returns an array
	 * of type {@link Object Object[]}.
	 *
	 * @return the backing array.
	 */

	public K[] elements() {
		return a;
	}
#endif

	/** Wraps a given array into an array list of given size.
	 *
	 * <p>Note it is guaranteed
	 * that the type of the array returned by {@link #elements()} will be the same
	 * (see the comments in the class documentation).
	 *
	 * @param a an array to wrap.
	 * @param length the length of the resulting array list.
	 * @return a new array list of the given size, wrapping the given array.
	 */

	public static KEY_GENERIC ARRAY_LIST KEY_GENERIC wrap(final KEY_GENERIC_TYPE a[], final int length) {
		if (length > a.length) throw new IllegalArgumentException("The specified length (" + length + ") is greater than the array size (" + a.length + ")");
		final ARRAY_LIST KEY_GENERIC l = new ARRAY_LIST KEY_GENERIC_DIAMOND(a, true);
		l.size = length;
		return l;
	}

	/** Wraps a given array into an array list.
	 *
	 * <p>Note it is guaranteed
	 * that the type of the array returned by {@link #elements()} will be the same
	 * (see the comments in the class documentation).
	 *
	 * @param a an array to wrap.
	 * @return a new array list wrapping the given array.
	 */

	public static KEY_GENERIC ARRAY_LIST KEY_GENERIC wrap(final KEY_GENERIC_TYPE a[]) {
		return wrap(a, a.length);
	}

	/** Creates a new empty array list.
	 *
	 * @return a new empty array list.
	 */
	public static KEY_GENERIC ARRAY_LIST KEY_GENERIC of() {
		return new ARRAY_LIST KEY_GENERIC_DIAMOND();
	}

	/** Creates an array list using an array of elements.
	 *
	 * @param init a the array the will become the new backing array of the array list.
	 * @return a new array list backed by the given array.
	 * @see #wrap
	 */
	SAFE_VARARGS
	public static KEY_GENERIC ARRAY_LIST KEY_GENERIC of(final KEY_GENERIC_TYPE... init) {
		return wrap(init);
	}

#if KEYS_INT_LONG_DOUBLE
	/** Collects the result of a primitive {@code Stream} into a new ArrayList.
	 *
	 * <p>This method performs a terminal operation on the given {@code Stream}
	 *
	 * @apiNote Taking a primitive stream instead of returning something like a
	 * {@link java.util.stream.Collector Collector} is necessary because there is no
	 * primitive {@code Collector} equivalent in the Java API.
	 */
	 public static KEY_GENERIC ARRAY_LIST KEY_GENERIC toList(JDK_PRIMITIVE_STREAM stream) {
	 	return stream.collect(
	 		ARRAY_LIST::new,
	 		ARRAY_LIST::add,
	 		ARRAY_LIST::addAll);
	 }

	/** Collects the result of a primitive {@code Stream} into a new ArrayList, potentially pre-allocated to handle the given size.
	 *
	 * <p>This method performs a terminal operation on the given {@code Stream}
	 *
	 * @apiNote Taking a primitive stream instead returning something like a
	 * {@link java.util.stream.Collector Collector} is necessary because there is no
	 * primitive {@code Collector} equivalent in the Java API.
	 */
	public static KEY_GENERIC ARRAY_LIST KEY_GENERIC toListWithExpectedSize(JDK_PRIMITIVE_STREAM stream, int expectedSize) {
 		if (expectedSize <= DEFAULT_INITIAL_CAPACITY) {
 			// Already below default capacity. Just use all default construction instead of fiddling with atomics in SizeDecreasingSupplier
 			return toList(stream);
		}
		return stream.collect(
			new COLLECTIONS.SizeDecreasingSupplier<
#if KEYS_REFERENCE
					K,
#endif
					ARRAY_LIST KEY_GENERIC>(
				expectedSize, (int size) ->
					size <= DEFAULT_INITIAL_CAPACITY ? new ARRAY_LIST KEY_GENERIC() : new ARRAY_LIST KEY_GENERIC(size)),
			ARRAY_LIST::add,
			ARRAY_LIST::addAll);
	}
#elif KEYS_REFERENCE
	// Collector wants a function that returns the collection being added to.
	ARRAY_LIST KEY_GENERIC combine(ARRAY_LIST KEY_EXTENDS_GENERIC toAddFrom) {
		addAll(toAddFrom);
		return this;
	}

	private static final Collector<KEY_TYPE, ?, ARRAY_LIST<KEY_TYPE>> TO_LIST_COLLECTOR =
		Collector.of(
			ARRAY_LIST::new,
			ARRAY_LIST::add,
			ARRAY_LIST::combine);

	/** Returns a {@link Collector} that collects a {@code Stream}'s elements into a new ArrayList. */
	SUPPRESS_WARNINGS_KEY_UNCHECKED_RAWTYPES
	public static KEY_GENERIC Collector<KEY_GENERIC_TYPE, ?, ARRAY_LIST KEY_GENERIC> toList() {
		return (Collector) TO_LIST_COLLECTOR;
	}

 	/** Returns a {@link Collector} that collects a {@code Stream}'s elements into a new ArrayList, potentially pre-allocated to handle the given size. */
 	public static KEY_GENERIC Collector<KEY_GENERIC_TYPE, ?, ARRAY_LIST KEY_GENERIC> toListWithExpectedSize(int expectedSize) {
 		if (expectedSize <= DEFAULT_INITIAL_CAPACITY) {
 			// Already below default capacity. Just use all default construction instead of fiddling with atomics in SizeDecreasingSupplier
 			return toList();
		}
 		return Collector.of(
 			new COLLECTIONS.SizeDecreasingSupplier<
#if KEYS_REFERENCE
				K,
#endif
				ARRAY_LIST KEY_GENERIC>(
			expectedSize, (int size) ->
				size <= DEFAULT_INITIAL_CAPACITY ? new ARRAY_LIST KEY_GENERIC() : new ARRAY_LIST KEY_GENERIC(size)),
		ARRAY_LIST::add,
		ARRAY_LIST::combine);
	}
#endif

	/** Ensures that this array list can contain the given number of entries without resizing.
	 *
	 * @param capacity the new minimum capacity for this array list.
	 */
	SUPPRESS_WARNINGS_KEY_UNCHECKED
	public void ensureCapacity(final int capacity) {
		if (capacity <= a.length || (a == ARRAYS.DEFAULT_EMPTY_ARRAY && capacity <= DEFAULT_INITIAL_CAPACITY)) return;
#if KEYS_PRIMITIVE
		a = ARRAYS.ensureCapacity(a, capacity, size);
#else
		if (wrapped) a = ARRAYS.ensureCapacity(a, capacity, size);
		else {
			if (capacity > a.length) {
				final Object t[] = new Object[capacity];
				System.arraycopy(a, 0, t, 0, size);
				a = (KEY_GENERIC_TYPE[])t;
			}
		}
#endif
		assert size <= a.length;
	}

	/** Grows this array list, ensuring that it can contain the given number of entries without resizing,
	 * and in case increasing the current capacity at least by a factor of 50%.
	 *
	 * @param capacity the new minimum capacity for this array list.
	 */
	SUPPRESS_WARNINGS_KEY_UNCHECKED
	private void grow(int capacity) {
		if (capacity <= a.length) return;
		if (a != ARRAYS.DEFAULT_EMPTY_ARRAY)
			capacity = (int)Math.max(Math.min((long)a.length + (a.length >> 1), it.unimi.dsi.fastutil.Arrays.MAX_ARRAY_SIZE), capacity);
		else if (capacity < DEFAULT_INITIAL_CAPACITY) capacity = DEFAULT_INITIAL_CAPACITY;
#if KEYS_PRIMITIVE
		a = ARRAYS.forceCapacity(a, capacity, size);
#else
		if (wrapped) a = ARRAYS.forceCapacity(a, capacity, size);
		else {
			final Object t[] = new Object[capacity];
			System.arraycopy(a, 0, t, 0, size);
			a = (KEY_GENERIC_TYPE[])t;
		}
#endif
		assert size <= a.length;
	}

	@Override
	public void add(final int index, final KEY_GENERIC_TYPE k) {
		ensureIndex(index);
		grow(size + 1);
		if (index != size) System.arraycopy(a, index, a, index + 1, size - index);
		a[index] = k;
		size++;
		assert size <= a.length;
	}

	@Override
	public boolean add(final KEY_GENERIC_TYPE k) {
		grow(size + 1);
		a[size++] = k;
		assert size <= a.length;
		return true;
	}

	@Override
	public KEY_GENERIC_TYPE GET_KEY(final int index) {
		if (index >= size) throw new IndexOutOfBoundsException("Index (" + index + ") is greater than or equal to list size (" + size + ")");
		return a[index];
	}

	@Override
	public int indexOf(final KEY_TYPE k) {
		for(int i = 0; i < size; i++) if (KEY_EQUALS(k, a[i])) return i;
		return -1;
	}


	@Override
	public int lastIndexOf(final KEY_TYPE k) {
		for(int i = size; i-- != 0;) if (KEY_EQUALS(k, a[i])) return i;
		return -1;
	}

	@Override
	public KEY_GENERIC_TYPE REMOVE_KEY(final int index) {
		if (index >= size) throw new IndexOutOfBoundsException("Index (" + index + ") is greater than or equal to list size (" + size + ")");
		final KEY_GENERIC_TYPE old = a[index];
		size--;
		if (index != size) System.arraycopy(a, index + 1, a, index, size - index);
#if KEYS_REFERENCE
		a[size] = null;
#endif
		assert size <= a.length;
		return old;
	}

	@Override
	public boolean REMOVE(final KEY_TYPE k) {
		int index = indexOf(k);
		if (index == -1) return false;
		REMOVE_KEY(index);
		assert size <= a.length;
		return true;
	}

	@Override
	public KEY_GENERIC_TYPE set(final int index, final KEY_GENERIC_TYPE k) {
		if (index >= size) throw new IndexOutOfBoundsException("Index (" + index + ") is greater than or equal to list size (" + size + ")");
		KEY_GENERIC_TYPE old = a[index];
		a[index] = k;
		return old;
	}

	@Override
	public void clear() {
#if KEYS_REFERENCE
		Arrays.fill(a, 0, size, null);
#endif
		size = 0;
		assert size <= a.length;
	}

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

	@Override
	public void size(final int size) {
		if (size > a.length) a = ARRAYS.forceCapacity(a, size, this.size);
		if (size > this.size) Arrays.fill(a, this.size, size, KEY_NULL);
#if KEYS_REFERENCE
		else Arrays.fill(a, size, this.size, KEY_NULL);
#endif
		this.size = size;
	}

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

	/** Trims this array list so that the capacity is equal to the size.
	 *
	 * @see java.util.ArrayList#trimToSize()
	 */
	public void trim() {
		trim(0);
	}

	/** Trims the backing array if it is too large.
	 *
	 * If the current array length is smaller than or equal to
	 * {@code n}, this method does nothing. Otherwise, it trims the
	 * array length to the maximum between {@code n} and {@link #size()}.
	 *
	 * <p>This method is useful when reusing lists.  {@linkplain #clear() Clearing a
	 * list} leaves the array length untouched. If you are reusing a list
	 * many times, you can call this method with a typical
	 * size to avoid keeping around a very large array just
	 * because of a few large transient lists.
	 *
	 * @param n the threshold for the trimming.
	 */

	SUPPRESS_WARNINGS_KEY_UNCHECKED
	public void trim(final int n) {
		// TODO: use Arrays.trim() and preserve type only if necessary
		if (n >= a.length || size == a.length) return;
		final KEY_GENERIC_TYPE t[] = KEY_GENERIC_ARRAY_CAST new KEY_TYPE[Math.max(n, size)];
		System.arraycopy(a, 0, t, 0, size);
		a = t;
		assert size <= a.length;
	}

	private class SubList extends ABSTRACT_LIST.SUBLIST_RANDOM_ACCESS KEY_GENERIC {
		private static final long serialVersionUID = -3185226345314976296L;

		protected SubList(int from, int to) {
			super(ARRAY_LIST.this, from, to);
		}

		// Most of the inherited methods should be fine, but we can override a few of them for performance.

		// Needed because we can't access the parent class' instance variables directly in a different instance of SubList.
		private KEY_GENERIC_TYPE[] getParentArray() {
			return a;
		}

		@Override
		public KEY_GENERIC_TYPE GET_KEY(int i) {
			ensureRestrictedIndex(i);
			return a[i + from];
		}

		private final class SubListIterator extends ITERATORS.AbstractIndexBasedListIterator KEY_GENERIC {

			// We are using pos == 0 to be 0 relative to SubList.from (meaning you need to do a[from + i] when accessing array).
			SubListIterator(int index) {
				super(0, index);
			}

			@Override
			protected final KEY_GENERIC_TYPE get(int i) { return a[from + i]; }
			@Override
			protected final void add(int i, KEY_GENERIC_TYPE k) { SubList.this.add(i, k); }
			@Override
			protected final void set(int i, KEY_GENERIC_TYPE k) { SubList.this.set(i, k); }
			@Override
			protected final void remove(int i) { SubList.this.REMOVE_KEY(i); }
			@Override
			protected final int getMaxPos() { return to - from; }

			@Override
			public KEY_GENERIC_TYPE NEXT_KEY() { if (! hasNext()) throw new NoSuchElementException(); return a[from + (lastReturned = pos++)]; }
			@Override
			public KEY_GENERIC_TYPE PREV_KEY() { if (! hasPrevious()) throw new NoSuchElementException(); return a[from + (lastReturned = --pos)]; }

			@Override
			public void forEachRemaining(final METHOD_ARG_KEY_CONSUMER action) {
				final int max = to - from;
				while(pos < max) {
					action.accept(a[from + (lastReturned = pos++)]);
				}
			}
		}

		@Override
		public KEY_LIST_ITERATOR KEY_GENERIC listIterator(int index) {
			return new SubListIterator(index);
		}

		private final class SubListSpliterator extends SPLITERATORS.LateBindingSizeIndexBasedSpliterator KEY_GENERIC {

			// We are using pos == 0 to be 0 relative to real array 0
			SubListSpliterator() {
				super(from);
			}

			private SubListSpliterator(int pos, int maxPos) {
				super(pos, maxPos);
			}

			@Override
			protected final int getMaxPosFromBackingStore() { return to; }

	 		@Override
			protected final KEY_GENERIC_TYPE get(int i) { return a[i]; }
			@Override
			protected final SubListSpliterator makeForSplit(int pos, int maxPos) {
				return new SubListSpliterator(pos, maxPos);
			}
			@Override
			public boolean tryAdvance(final METHOD_ARG_KEY_CONSUMER action) {
				if (pos >= getMaxPos()) return false;
				action.accept(a[pos++]);
				return true;
			}
			@Override
			public void forEachRemaining(final METHOD_ARG_KEY_CONSUMER action) {
				final int max = getMaxPos();
				while(pos < max) {
					action.accept(a[pos++]);
				}
			}
		}

		@Override
		public KEY_SPLITERATOR KEY_GENERIC spliterator() {
			return new SubListSpliterator();
		}

		boolean contentsEquals(KEY_GENERIC_TYPE[] otherA, int otherAFrom, int otherATo) {
			if (a == otherA && from == otherAFrom && to == otherATo) return true;
			if (otherATo - otherAFrom != size()) {
				return false;
			}
			int pos = from, otherPos = otherAFrom;
			// We have already assured that the two ranges are the same size, so we only need to check one bound.
			// TODO When minimum version of Java becomes Java 9, use the Arrays.equals which takes bounds, which is vectorized.
			// Make sure to split out the reference equality case when you do this.
#if KEY_CLASS_Object
			while(pos < to) if (!java.util.Objects.equals(a[pos++], otherA[otherPos++])) return false;
#else
			while(pos < to) if (a[pos++] != otherA[otherPos++]) return false;
#endif
			return true;
		}

		@Override
		public boolean equals(Object o) {
			if (o == this) return true;
			if (o == null) return false;
			if (!(o instanceof java.util.List)) return false;
			if (o instanceof ARRAY_LIST) {
				SUPPRESS_WARNINGS_KEY_UNCHECKED
				ARRAY_LIST KEY_GENERIC other = (ARRAY_LIST KEY_GENERIC) o;
				return contentsEquals(other.a, 0, other.size());
			}
			if (o instanceof ARRAY_LIST.SubList) {
				SUPPRESS_WARNINGS_KEY_UNCHECKED
				ARRAY_LIST KEY_GENERIC.SubList other = (ARRAY_LIST KEY_GENERIC.SubList) o;
				return contentsEquals(other.getParentArray(), other.from, other.to);
			}
			return super.equals(o);
		}

#if ! KEYS_USE_REFERENCE_EQUALITY
		SUPPRESS_WARNINGS_KEY_UNCHECKED
		int contentsCompareTo(KEY_GENERIC_TYPE[] otherA, int otherAFrom, int otherATo) {
#if KEYS_PRIMITIVE // Can't make this assumption for reference types in case we have a goofy Comparable that doesn't compare itself equal
			if (a == otherA && from == otherAFrom && to == otherATo) return 0;
#endif
			// TODO When minimum version of Java becomes Java 9, use Arrays.compare, which vectorizes.
			KEY_GENERIC_TYPE e1, e2;
			int r, i, j;
			for(i = from, j = otherAFrom; i < to && i < otherATo; i++, j++) {
				e1 = a[i];
				e2 = otherA[j];
				if ((r = KEY_CMP(e1, e2)) != 0) return r;
			}
			return i < otherATo ? -1 : (i < to ? 1 : 0);
		}

		SUPPRESS_WARNINGS_KEY_UNCHECKED
		@Override
		public int compareTo(final java.util.List <? extends KEY_GENERIC_CLASS> l) {
			if (l instanceof ARRAY_LIST) {
				SUPPRESS_WARNINGS_KEY_UNCHECKED
				ARRAY_LIST KEY_GENERIC other = (ARRAY_LIST KEY_GENERIC) l;
				return contentsCompareTo(other.a, 0, other.size());
			}
			if (l instanceof ARRAY_LIST.SubList) {
				SUPPRESS_WARNINGS_KEY_UNCHECKED
				ARRAY_LIST KEY_GENERIC.SubList other = (ARRAY_LIST KEY_GENERIC.SubList) l;
				return contentsCompareTo(other.getParentArray(), other.from, other.to);
			}
			return super.compareTo(l);
		}
#endif
		// We don't override subList as we want AbstractList's "sub-sublist" nesting handling,
		// which would be tricky to do here.
		// TODO Do override it so array access isn't sent through N indirections.
		// This will likely mean making this class static.
	}

	@Override
	public LIST KEY_GENERIC subList(int from, int to) {
		if (from == 0 && to == size()) return this;
		ensureIndex(from);
		ensureIndex(to);
		if (from > to) throw new IndexOutOfBoundsException("Start index (" + from + ") is greater than end index (" + to + ")");
		return new SubList(from, to);
	}

	/** Copies element of this type-specific list into the given array using optimized system calls.
	 *
	 * @param from the start index (inclusive).
	 * @param a the destination array.
	 * @param offset the offset into the destination array where to store the first element copied.
	 * @param length the number of elements to be copied.
	 */
	@Override
	public void getElements(final int from, final KEY_TYPE[] a, final int offset, final int length) {
		ARRAYS.ensureOffsetLength(a, offset, length);
		System.arraycopy(this.a, from, a, offset, length);
	}

	/** Removes elements of this type-specific list using optimized system calls.
	 *
	 * @param from the start index (inclusive).
	 * @param to the end index (exclusive).
	 */
	@Override
	public void removeElements(final int from, final int to) {
		it.unimi.dsi.fastutil.Arrays.ensureFromTo(size, from, to);
		System.arraycopy(a, to, a, from, size - to);
		size -= (to - from);
#if KEYS_REFERENCE
		int i = to - from;
		while(i-- != 0) a[size + i] = null;
#endif
	}


	/** Adds elements to this type-specific list using optimized system calls.
	 *
	 * @param index the index at which to add elements.
	 * @param a the array containing the elements.
	 * @param offset the offset of the first element to add.
	 * @param length the number of elements to add.
	 */
	@Override
	public void addElements(final int index, final KEY_GENERIC_TYPE a[], final int offset, final int length) {
		ensureIndex(index);
		ARRAYS.ensureOffsetLength(a, offset, length);
		grow(size + length);
		System.arraycopy(this.a, index, this.a, index + length, size - index);
		System.arraycopy(a, offset, this.a, index, length);
		size += length;
	}

	/** Sets elements to this type-specific list using optimized system calls.
	 *
	 * @param index the index at which to start setting elements.
	 * @param a the array containing the elements.
	 * @param offset the offset of the first element to add.
	 * @param length the number of elements to add.
	 */
	@Override
	public void setElements(final int index, final KEY_GENERIC_TYPE a[], final int offset, final int length) {
		ensureIndex(index);
		ARRAYS.ensureOffsetLength(a, offset, length);
		if (index + length > size) throw new IndexOutOfBoundsException("End index (" + (index + length) + ") is greater than list size (" + size + ")");
		System.arraycopy(a, offset, this.a, index, length);
	}

	@Override
	public void forEach(final METHOD_ARG_KEY_CONSUMER action) {
		for (int i = 0; i < size; ++i) {
			action.accept(a[i]);
		}
	}

	@Override
	public boolean addAll(int index, final STD_KEY_COLLECTION KEY_EXTENDS_GENERIC c) {
		if (c instanceof LIST) {
			return addAll(index, (LIST KEY_EXTENDS_GENERIC)c);
		}
		ensureIndex(index);
		int n = c.size();
		if (n == 0) return false;
		grow(size + n);
		System.arraycopy(a, index, a, index + n, size - index);
		final STD_KEY_ITERATOR KEY_EXTENDS_GENERIC i = c.iterator();
		size += n;
		while(n-- != 0) a[index++] = i.NEXT_KEY();
		assert size <= a.length;
		return true;
	}

	@Override
	public boolean addAll(final int index, final LIST KEY_EXTENDS_GENERIC l) {
		ensureIndex(index);
		final int n = l.size();
		if (n == 0) return false;
		grow(size + n);
		System.arraycopy(a, index, a, index + n, size - index);
		l.getElements(0, a, index, n);
		size += n;
		assert size <= a.length;
		return true;
	}

	@Override
	public boolean removeAll(final STD_KEY_COLLECTION KEY_GENERIC_WILDCARD c) {
		final KEY_TYPE[] a = this.a;
		int j = 0;
		for(int i = 0; i < size; i++)
			if (! c.contains(a[i])) a[j++] = a[i];
#if KEYS_REFERENCE
		Arrays.fill(a, j, size, null);
#endif
		final boolean modified = size != j;
		size = j;
		return modified;
	}

#if KEYS_PRIMITIVE

	@Override
	public KEY_TYPE[] toArray(KEY_TYPE[] a) {
		if (a == null || a.length < size) a = java.util.Arrays.copyOf(a, size);
		System.arraycopy(this.a, 0, a, 0, size);
		return a;
	}

#else

	@Override
	public Object[] toArray() {
		final int size = size();
		// A subtle part of the spec says the returned array must be Object[] exactly.
		if (size == 0) return it.unimi.dsi.fastutil.objects.ObjectArrays.EMPTY_ARRAY;
		return Arrays.copyOf(a, size, Object[].class);
	}

	SUPPRESS_WARNINGS_KEY_UNCHECKED
	@Override
	public <T> T[] toArray(T[] a) {
		if (a == null) {
			a = (T[]) new Object[size()];
		} else if (a.length < size()) {
			a = (T[]) Array.newInstance(a.getClass().getComponentType(), size());
		}
		System.arraycopy(this.a, 0, a, 0, size());
		if (a.length > size()) {
			a[size()] = null;
		}
		return a;
	}
#endif

	@Override
	public KEY_LIST_ITERATOR KEY_GENERIC listIterator(final int index) {
		ensureIndex(index);

		return new KEY_LIST_ITERATOR KEY_GENERIC() {
				int pos = index, last = -1;

				@Override
				public boolean hasNext() { return pos < size; }
				@Override
				public boolean hasPrevious() { return pos > 0; }
				@Override
				public KEY_GENERIC_TYPE NEXT_KEY() { if (! hasNext()) throw new NoSuchElementException(); return a[last = pos++]; }
				@Override
				public KEY_GENERIC_TYPE PREV_KEY() { if (! hasPrevious()) throw new NoSuchElementException(); return a[last = --pos]; }
				@Override
				public int nextIndex() { return pos; }
				@Override
				public int previousIndex() { return pos - 1; }
				@Override
				public void add(KEY_GENERIC_TYPE k) {
					ARRAY_LIST.this.add(pos++, k);
					last = -1;
				}
				@Override
				public void set(KEY_GENERIC_TYPE k) {
					if (last == -1) throw new IllegalStateException();
					ARRAY_LIST.this.set(last, k);
				}
				@Override
				public void remove() {
					if (last == -1) throw new IllegalStateException();
					ARRAY_LIST.this.REMOVE_KEY(last);
					/* If the last operation was a next(), we are removing an element *before* us, and we must decrease pos correspondingly. */
					if (last < pos) pos--;
					last = -1;
				}
				@Override
				public void forEachRemaining(final METHOD_ARG_KEY_CONSUMER action) {
					while (pos < size) {
						action.accept(a[last = pos++]);
					}
				}
				@Override
				public int back(int n) {
					if (n < 0) throw new IllegalArgumentException("Argument must be nonnegative: " + n);
					final int remaining = size - pos;
					if (n < remaining) {
						pos -= n;
					} else {
						n = remaining;
						pos = 0;
					}
					last = pos;
					return n;
				}
				@Override
				public int skip(int n) {
					if (n < 0) throw new IllegalArgumentException("Argument must be nonnegative: " + n);
					final int remaining = size - pos;
					if (n < remaining) {
						pos += n;
					} else {
						n = remaining;
						pos = size;
					}
					last = pos - 1;
					return n;
				}
			};
	}

	// If you update this, you will probably want to update ArraySet as well
	private final class Spliterator implements KEY_SPLITERATOR KEY_GENERIC {
		// Until we split, we will track the size of the list.
		// Once we split, then we stop updating on structural modifications.
		// Aka, size is late-binding.
		boolean hasSplit = false;
		int pos, max;

#ifdef TEST
		// Sentinel to make sure we don't accidentally use size when we mean max
		@Deprecated
		private final Object size = null;
#endif

		public Spliterator() {
			this(0, ARRAY_LIST.this.size, false);
		}

		private Spliterator(int pos, int max, boolean hasSplit) {
			assert pos <= max : "pos " + pos + " must be <= max " + max;
			this.pos = pos;
			this.max = max;
			this.hasSplit = hasSplit;
		}

		private int getWorkingMax() {
			return hasSplit ? max : ARRAY_LIST.this.size;
		}

		@Override
		public int characteristics() { return SPLITERATORS.LIST_SPLITERATOR_CHARACTERISTICS; }

		@Override
		public long estimateSize() { return getWorkingMax() - pos; }

		@Override
		public boolean tryAdvance(final METHOD_ARG_KEY_CONSUMER action) {
			if (pos >= getWorkingMax()) return false;
			action.accept(a[pos++]);
			return true;
		}

		@Override
		public void forEachRemaining(final METHOD_ARG_KEY_CONSUMER action) {
			for (final int max = getWorkingMax(); pos < max; ++pos) {
				action.accept(a[pos]);
			}
		}

		@Override
		public long skip(long n) {
			if (n < 0) throw new IllegalArgumentException("Argument must be nonnegative: " + n);
			final int max = getWorkingMax();
			if (pos >= max) return 0;
			final int remaining = max - pos;
			if (n < remaining) {
				pos = it.unimi.dsi.fastutil.SafeMath.safeLongToInt(pos + n);
				return n;
			}
			n = remaining;
			pos = max;
			return n;
		}

		@Override
		public KEY_SPLITERATOR KEY_GENERIC trySplit() {
			final int max = getWorkingMax();
			int retLen = (max - pos) >> 1;
			if (retLen <= 1) return null;
			// Update instance max with the last seen list size (if needed) before continuing
			this.max = max;
			int myNewPos = pos + retLen;
			int retMax = myNewPos;
			int oldPos = pos;
			this.pos = myNewPos;
			this.hasSplit = true;
			return new Spliterator(oldPos, retMax, true);
		}
	}

	/** {@inheritDoc}
	 *
	 * <p>The returned spliterator is late-binding; it will track structural changes
	 * after the current index, up until the first {@link java.util.Spliterator#trySplit() trySplit()},
	 * at which point the maximum index will be fixed.
	 * <br>Structural changes before the current index or after the first
	 * {@link java.util.Spliterator#trySplit() trySplit()} will result in unspecified behavior.
	 */
	@Override
	public KEY_SPLITERATOR KEY_GENERIC spliterator() {
		// If it wasn't for the possibility of the list being expanded or shrunk,
		// we could return SPLITERATORS.wrap(a, 0, size).
		return new Spliterator();
	}

	SUPPRESS_WARNINGS_KEY_UNCHECKED
	@Override
	public void sort(final KEY_COMPARATOR KEY_SUPER_GENERIC comp) {
		if (comp == null) {
			ARRAYS.stableSort(a, 0, size);
		} else {
			ARRAYS.stableSort(a, 0, size, comp);
		}
	}

	@Override
	public void unstableSort(final KEY_COMPARATOR KEY_SUPER_GENERIC comp) {
		if (comp == null) {
			ARRAYS.unstableSort(a, 0, size);
		} else {
			ARRAYS.unstableSort(a, 0, size, comp);
		}
	}

	@Override
	SUPPRESS_WARNINGS_KEY_UNCHECKED
	public ARRAY_LIST KEY_GENERIC clone() {
		ARRAY_LIST KEY_GENERIC cloned = null;
		// Test for fastpath we can do if exactly an ArrayList
		if (getClass() == ARRAY_LIST.class) {
			// Preserve backwards compatibility and make new list have Object[] even if it was wrapped from some subclass.
			cloned = new ARRAY_LIST KEY_GENERIC_DIAMOND(copyArraySafe(a, size), false);
			cloned.size = size;
		} else {
			try {
				cloned = (ARRAY_LIST KEY_GENERIC)super.clone();
			} catch (CloneNotSupportedException err) {
				// Can't happen
				throw new InternalError(err);
			}
			// Preserve backwards compatibility and make new list have Object[] even if it was wrapped from some subclass.
			cloned.a = copyArraySafe(a, size);
#if ! KEYS_PRIMITIVE
			// We can't clear cloned.wrapped because it is final.
#endif
		}
		return cloned;
	}

	/** Compares this type-specific array list to another one.
	 *
	 * @apiNote This method exists only for sake of efficiency. The implementation
	 * inherited from the abstract implementation would already work.
	 *
	 * @param l a type-specific array list.
	 * @return true if the argument contains the same elements of this type-specific array list.
	 */
	public boolean equals(final ARRAY_LIST KEY_GENERIC l) {
		// TODO When minimum version of Java becomes Java 9, use the Arrays.equals which takes bounds, which is vectorized.
		if (l == this) return true;
		int s = size();
		if (s != l.size()) return false;
		final KEY_GENERIC_TYPE[] a1 = a;
		final KEY_GENERIC_TYPE[] a2 = l.a;

		if (a1 == a2 && s == l.size()) return true;

#if KEY_CLASS_Object
		while(s-- !=  0) if (! java.util.Objects.equals(a1[s], a2[s])) return false;
#else
		while(s-- !=  0) if (a1[s] != a2[s]) return false;
#endif
		return true;
	}

#if KEYS_REFERENCE
	@SuppressWarnings({"unchecked", "unlikely-arg-type"})
#else
	@SuppressWarnings("unlikely-arg-type")
#endif
	@Override
	public boolean equals(final Object o) {
		if (o == this) return true;
		if (o == null) return false;
		if (!(o instanceof java.util.List)) return false;
		if (o instanceof ARRAY_LIST) {
			// Safe cast because we are only going to take elements from other list, never give them
			return equals((ARRAY_LIST KEY_GENERIC) o);
		}
		if (o instanceof ARRAY_LIST.SubList) {
			// Safe cast because we are only going to take elements from other list, never give them
			// Sublist has an optimized sub-array based comparison, reuse that.
			return ((ARRAY_LIST KEY_GENERIC.SubList)o).equals(this);
		}
		return super.equals(o);
	}

#if ! KEYS_USE_REFERENCE_EQUALITY

	/** Compares this array list to another array list.
	 *
	 * @apiNote This method exists only for sake of efficiency. The implementation
	 * inherited from the abstract implementation would already work.
	 *
	 * @param l an array list.
	 * @return a negative integer,
	 * zero, or a positive integer as this list is lexicographically less than, equal
	 * to, or greater than the argument.
	 */
	SUPPRESS_WARNINGS_KEY_UNCHECKED
	public int compareTo(final ARRAY_LIST KEY_EXTENDS_GENERIC l) {
		final int s1 = size(), s2 = l.size();
		final KEY_GENERIC_TYPE a1[] = a, a2[] = l.a;
#if KEYS_PRIMITIVE // Can't make this assumption for reference types in case we have a goofy Comparable that doesn't compare itself equal
		if (a1 == a2 && s1 == s2) return 0;
#endif

		// TODO When minimum version of Java becomes Java 9, use Arrays.compare, which vectorizes.
		KEY_GENERIC_TYPE e1, e2;
		int r, i;

		for(i = 0; i < s1 && i < s2; i++) {
			e1 = a1[i];
			e2 = a2[i];
			if ((r = KEY_CMP(e1, e2)) != 0) return r;
		}

		return i < s2 ? -1 : (i < s1 ? 1 : 0);
	}

	SUPPRESS_WARNINGS_KEY_UNCHECKED
	@Override
	public int compareTo(final java.util.List <? extends KEY_GENERIC_CLASS> l) {
		if (l instanceof ARRAY_LIST) {
			return compareTo((ARRAY_LIST KEY_EXTENDS_GENERIC)l);
		}
		if (l instanceof ARRAY_LIST.SubList) {
			// Must negate because we are inverting the order of the comparison.
			return -((ARRAY_LIST KEY_GENERIC.SubList) l).compareTo(this);
		}
		return super.compareTo(l);
	}
#endif

	private void writeObject(java.io.ObjectOutputStream s) throws java.io.IOException {
		s.defaultWriteObject();
		for(int i = 0; i < size; i++) s.WRITE_KEY(a[i]);
	}

	SUPPRESS_WARNINGS_KEY_UNCHECKED
	private void readObject(java.io.ObjectInputStream s) throws java.io.IOException, ClassNotFoundException {
		s.defaultReadObject();
		a = KEY_GENERIC_ARRAY_CAST new KEY_TYPE[size];
		for(int i = 0; i < size; i++) a[i] = KEY_GENERIC_CAST s.READ_KEY();
	}


#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();
#elif KEY_CLASS_Object
		return Integer.toBinaryString(r.nextInt());
#else
		return new java.io.Serializable() {};
#endif
	}

	private static int genIndex(int size) {
		return size == 0 ? 0 : r.nextInt(size);
	}

	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 final int WARMUP_CYCLES = 12;
	private static final int NUM_RUNS = 25;
	private static final int GC_EVERY = 5;
	// TODO Use a ASSERTS like preprocessor variable?
	private static final boolean PARALLEL_STREAMS = Boolean.getBoolean("useParallelStreams");

	private static final int intDivRoundUp(int numerator, int denominator) {
		return (numerator + denominator - 1) / denominator;
	}

	// WARNING: This benchmark runs in amortized time O(n^(3/2)). Don't choose huge n values for this test (about 10,000,000 starts showing significant slowdown)
	private static void speedTest(final int n, boolean comp) {
		if (n < 0) throw new IllegalArgumentException("n: " + n + " must be >0 (overflow?)");
		java.util.ArrayList t;
		ARRAY_LIST m;

		int i;
		int j;
		KEY_TYPE k[] = new KEY_TYPE[n];
		KEY_TYPE nk[] = new KEY_TYPE[n];
		int randIndexes[] = new int[n];
		long ns;

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

		final int nRandom = (int)Math.sqrt(n);
		final int nSequential = n - nRandom;

		double totAddEnd = 0, totAddRandom = 0, totYes = 0, totNo = 0, totIter = 0, totRemEnd = 0, totRemRandom = 0, toStreamSum = 0, d;

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

			if ((j + 1) % GC_EVERY == 0) System.gc();

			t = new java.util.ArrayList(16);

			/* We add to t at a random position. */
			ns = System.nanoTime();
			for(i = 0; i < nRandom; i++) t.add(randIndexes[i], KEY2OBJ(k[i]));
			d = (System.nanoTime() - ns) / (double)nRandom;
			if (j >= WARMUP_CYCLES) totAddRandom += d;
			System.out.print("AddToRandom: " + format(d) + "ns ");

			/* We add to t at end. */
			ns = System.nanoTime();
			for(; i < n; i++) t.add(KEY2OBJ(k[i]));
			d = (System.nanoTime() - ns) / (double)nSequential;
			if (j >= WARMUP_CYCLES) totAddEnd += d;
			System.out.print("AddToEnd: " + format(d) + "ns ");

			/* We check things in t. */
			ns = System.nanoTime();
			for(i = 0; i < nRandom;  i++) t.contains(KEY2OBJ(k[i]));
			d = (System.nanoTime() - ns) / (double)nRandom;
			if (j >= WARMUP_CYCLES) totYes += d;
			System.out.print("Yes: " + format(d) + "ns ");

			/* We check for things likely not in t. */
			ns = System.nanoTime();
			for(i = 0; i < nRandom;  i++) t.contains(KEY2OBJ(nk[i]));
			d = (System.nanoTime() - ns) / (double)nRandom;
			if (j >= WARMUP_CYCLES) totNo += d;
			System.out.print("No: " + format(d) + "ns ");

			/* We iterate on t. */
			ns = System.nanoTime();
			for(java.util.Iterator it = t.iterator(); it.hasNext(); it.next());
			d = (System.nanoTime() - ns) / (double)n;
			if (j >= WARMUP_CYCLES) totIter += d;
			System.out.print("Iter: " + format(d) + "ns ");

#if KEYS_PRIMITIVE && ! KEY_CLASS_Boolean
			/* We sum on t. */
			ns = System.nanoTime();
#if KEYS_BYTE_CHAR_SHORT_FLOAT
			// Since the primitive stream has to upcast to a widened primitive, for fairness we will upcast here too
#endif
			java.util.stream.Stream<KEY_CLASS> tStream = ((java.util.List<KEY_CLASS>)t).stream();
			if (PARALLEL_STREAMS) tStream = tStream.parallel();
#if KEY_CLASS_Character
			tStream.MAP_TO_KEY_WIDENED(Character::charValue).sum();
#else
			tStream.MAP_TO_KEY_WIDENED(KEY_CLASS::KEY_WIDENED_VALUE).sum();
#endif
			d = (System.nanoTime() - ns) / (double)n;
			if (j >= WARMUP_CYCLES) toStreamSum += d;
			System.out.print("Stream sum: " + format(d) + "ns ");
#endif

			// Don't bother with remove(KEY); that is just going to be a contains + remove random.
			/* We remove from end */
			ns = System.nanoTime();
			for(i = 0; i < nSequential;  i++) t.remove(t.size() - 1);
			d = (System.nanoTime() - ns) / (double)nSequential;
			if (j >= WARMUP_CYCLES) totRemEnd += d;
			System.out.print("RemEnd: " + format(d) + "ns ");

			/* We remove randomly */
			ns = System.nanoTime();
			for(i = 0; i < nRandom;  i++) t.remove(randIndexes[t.size() - 1]);
			d = (System.nanoTime() - ns) / (double)nRandom;
			if (j >= WARMUP_CYCLES) totRemRandom += d;
			System.out.print("RemRandom: " + format(d) + "ns ");

			System.out.println();
		}

		System.out.println();
		System.out.println("java.util AddToRandom: " + format(totAddRandom/(j-WARMUP_CYCLES)) + " AddToEnd: " + format(totAddEnd/(j-WARMUP_CYCLES)) + "ns Yes: " + format(totYes/(j-WARMUP_CYCLES)) + "ns No: " + format(totNo/(j-WARMUP_CYCLES)) + "ns Iter: " + format(totIter/(j-WARMUP_CYCLES)) + "ns StreamSum: " + format(toStreamSum/(j-WARMUP_CYCLES)) + "ns RemEnd: " + format(totRemEnd/(j-WARMUP_CYCLES)) + "ns RemRandom: " + format(totRemRandom/(j-WARMUP_CYCLES)) + "ns");

		System.out.println();

		totAddEnd = totAddRandom = totYes = totNo = totIter = totRemEnd = totRemRandom = toStreamSum = 0;
		}

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

			if ((j + 1) % GC_EVERY == 0) System.gc();

			m = new ARRAY_LIST(16);

			/* We add to m at a random position. */
			ns = System.nanoTime();
			for(i = 0; i < nRandom; i++) m.add(randIndexes[i], k[i]);
			d = (System.nanoTime() - ns) / (double)nRandom;
			if (j >= WARMUP_CYCLES) totAddRandom += d;
			System.out.print("AddToRandom: " + format(d) + "ns ");

			/* We add to m at end. */
			ns = System.nanoTime();
			for(; i < n;  i++) m.add(k[i]);
			d = (System.nanoTime() - ns) / (double)nSequential;
			if (j >= WARMUP_CYCLES) totAddEnd += d;
			System.out.print("AddToEnd: " + format(d) + "ns ");

			/* We check things in m. */
			ns = System.nanoTime();
			for(i = 0; i < nRandom;  i++) m.contains(k[i]);
			d = (System.nanoTime() - ns) / (double)nRandom;
			if (j >= WARMUP_CYCLES) totYes += d;
			System.out.print("Yes: " + format(d) + "ns ");

			/* We check for things likely not in m. */
			ns = System.nanoTime();
			for(i = 0; i < nRandom;  i++) m.contains(nk[i]);
			d = (System.nanoTime() - ns) / (double)nRandom;
			if (j >= WARMUP_CYCLES) totNo += d;
			System.out.print("No: " + format(d) + "ns ");

			/* We iterate on m. */
			ns = System.nanoTime();
			for(KEY_ITERATOR it = (KEY_ITERATOR)m.iterator(); it.hasNext(); it.NEXT_KEY());
			d = (System.nanoTime() - ns) / (double)n;
			if (j >= WARMUP_CYCLES) totIter += d;
			System.out.print("Iter: " + format(d) + "ns ");

#if KEYS_PRIMITIVE && ! KEY_CLASS_Boolean
			/* We sum on m. */
			ns = System.nanoTime();
			JDK_PRIMITIVE_STREAM mStream = m.KEY_WIDENED_STREAM_METHOD();
			if (PARALLEL_STREAMS) mStream = mStream.parallel();
			mStream.sum();
			d = (System.nanoTime() - ns) / (double)n;
			if (j >= WARMUP_CYCLES) toStreamSum += d;
			System.out.print("Stream sum: " + format(d) + "ns ");
#endif

			// Don't bother with rem(KEY); that is just going to be a contains + remove random.
			/* We remove from end */
			ns = System.nanoTime();
			for(i = 0; i < nSequential;  i++) m.REMOVE_KEY(m.size() - 1);
			d = (System.nanoTime() - ns) / (double)nSequential;
			if (j >= WARMUP_CYCLES) totRemEnd += d;
			System.out.print("RemEnd: " + format(d) + "ns ");

			/* We remove randomly */
			ns = System.nanoTime();
			for(i = 0; i < nRandom;  i++) m.REMOVE_KEY(randIndexes[m.size() - 1]);
			d = (System.nanoTime() - ns) / (double)nRandom;
			if (j >= WARMUP_CYCLES) totRemRandom += d;
			System.out.print("RemRandom: " + format(d) + "ns ");

			System.out.println();
		}

		System.out.println();
		System.out.println("fastutil AddToRandom: " + format(totAddRandom/(j-WARMUP_CYCLES)) + " AddToEnd: " + format(totAddEnd/(j-WARMUP_CYCLES)) +  "ns Yes: " + format(totYes/(j-WARMUP_CYCLES)) + "ns No: " + format(totNo/(j-WARMUP_CYCLES)) + "ns Iter: " + format(totIter/(j-WARMUP_CYCLES)) + "ns StreamSum: " + format(toStreamSum/(j-WARMUP_CYCLES)) + "ns RemEnd: " + format(totRemEnd/(j-WARMUP_CYCLES)) + "ns RemRandom: " + format(totRemRandom/(j-WARMUP_CYCLES)) + "ns");

		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 void ensure(boolean cond, java.util.function.Supplier<String> msgSupplier) {
		if (cond) return;
		fatal(msgSupplier.get());
	}

	private static Object[] k, v, nk;
	private static KEY_TYPE kt[];
	private static KEY_TYPE nkt[];
	private static ARRAY_LIST topList;

	protected static void testLists(LIST m, java.util.List t, int n, int level) throws Exception {
		long ms;
		Exception mThrowsIllegal, tThrowsIllegal, mThrowsOutOfBounds, tThrowsOutOfBounds;
		Object rt = null;
		KEY_TYPE rm = KEY_NULL;

		if (level > 4) return;


		/* Now we check that both sets agree on random keys. For m we use the polymorphic method. */

		for(int i = 0; i < n; i++) {
			int p = r.nextInt() % (n * 2);

			KEY_TYPE T = genKey();
			mThrowsOutOfBounds = tThrowsOutOfBounds  = null;

			try {
				m.set(p, T);
			}
			catch (IndexOutOfBoundsException e) { mThrowsOutOfBounds = e; }
			try {
				t.set(p, KEY2OBJ(T));
			}
			catch (IndexOutOfBoundsException e) { tThrowsOutOfBounds = e; }

			ensure((mThrowsOutOfBounds == null) == (tThrowsOutOfBounds == null), "Error (" + level + ", " + seed + "): set() divergence at start in IndexOutOfBoundsException for index " + p + "  (" + mThrowsOutOfBounds + ", " + tThrowsOutOfBounds + ")");
			if (mThrowsOutOfBounds == null) ensure(t.get(p).equals(KEY2OBJ(m.GET_KEY(p))), "Error (" + level + ", " + seed + "): m and t differ after set() on position " + p + " (" + m.GET_KEY(p) + ", " + t.get(p) + ")");

			p = r.nextInt() % (n * 2);
			mThrowsOutOfBounds = tThrowsOutOfBounds  = null;

			try {
				m.GET_KEY(p);
			}
			catch (IndexOutOfBoundsException e) { mThrowsOutOfBounds = e; }
			try {
				t.get(p);
			}
			catch (IndexOutOfBoundsException e) { tThrowsOutOfBounds = e; }

			ensure((mThrowsOutOfBounds == null) == (tThrowsOutOfBounds == null), "Error (" + level + ", " + seed + "): get() divergence at start in IndexOutOfBoundsException for index " + p + "  (" + mThrowsOutOfBounds + ", " + tThrowsOutOfBounds + ")");
			if (mThrowsOutOfBounds == null) ensure(t.get(p).equals(KEY2OBJ(m.GET_KEY(p))), "Error (" + level + ", " + seed + "): m and t differ aftre get() on position " + p + " (" + m.GET_KEY(p) + ", " + t.get(p) + ")");

		}

		/* Now we check that both sets agree on random keys. For m we use the standard method. */

		for(int i = 0; i < n; i++) {
			int p = r.nextInt() % (n * 2);

			mThrowsOutOfBounds = tThrowsOutOfBounds  = null;

			try {
				m.get(p);
			}
			catch (IndexOutOfBoundsException e) { mThrowsOutOfBounds = e; }
			try {
				t.get(p);
			}
			catch (IndexOutOfBoundsException e) { tThrowsOutOfBounds = e; }

			ensure((mThrowsOutOfBounds == null) == (tThrowsOutOfBounds == null), "Error (" + level + ", " + seed + "): get() divergence at start in IndexOutOfBoundsException for index " + p + "  (" + mThrowsOutOfBounds + ", " + tThrowsOutOfBounds + ")");
			if (mThrowsOutOfBounds == null) ensure(t.get(p).equals(m.get(p)), "Error (" + level + ", " + seed + "): m and t differ at start on position " + p + " (" + m.get(p) + ", " + t.get(p) + ")");

		}

		/* 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.iterator(); i.hasNext();) {
			ensure(m.contains(i.next()), "Error (" + level + ", " + seed + "): m and t differ on an entry after insertion (iterating on t)");
		}

		/* Now we check that m actually holds that data, but iterating on m. */
		for(Iterator i=m.listIterator(); i.hasNext();) {
			ensure(t.contains(i.next()), "Error (" + level + ", " + seed + "): m and t differ on an entry 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();
			ensure(m.contains(T) == t.contains(KEY2OBJ(T)), "Error (" + level + ", " + seed + "): divergence in content 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();
			ensure(m.contains(KEY2OBJ(T)) == t.contains(KEY2OBJ(T)), "Error (" + level + ", " + seed + "): divergence in content between t and m (polymorphic method)");
		}

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

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

			try {
				m.add(T);
			}
			catch (IndexOutOfBoundsException e) { mThrowsOutOfBounds = e; }

			try {
				t.add(KEY2OBJ(T));
			}
			catch (IndexOutOfBoundsException e) { tThrowsOutOfBounds = e; }

			T = genKey();
			int p = r.nextInt() % (2 * n + 1);

			mThrowsOutOfBounds = tThrowsOutOfBounds  = null;

			try {
				m.add(p, T);
			}
			catch (IndexOutOfBoundsException e) { mThrowsOutOfBounds = e; }

			try {
				t.add(p, KEY2OBJ(T));
			}
			catch (IndexOutOfBoundsException e) { tThrowsOutOfBounds = e; }


			ensure((mThrowsOutOfBounds == null) == (tThrowsOutOfBounds == null), "Error (" + level + ", " + seed + "): add() divergence in IndexOutOfBoundsException for index " + p + " for " + T + " (" + mThrowsOutOfBounds + ", " + tThrowsOutOfBounds + ")");

			p = r.nextInt() % (2 * n + 1);

			mThrowsOutOfBounds = tThrowsOutOfBounds  = null;

			try {
				rm = m.REMOVE_KEY(p);
			}
			catch (IndexOutOfBoundsException e) { mThrowsOutOfBounds = e; }

			try {
				rt = t.remove(p);
			}
			catch (IndexOutOfBoundsException e) { tThrowsOutOfBounds = e; }


			ensure((mThrowsOutOfBounds == null) == (tThrowsOutOfBounds == null), "Error (" + level + ", " + seed + "): remove() divergence in IndexOutOfBoundsException for index " + p + " (" + mThrowsOutOfBounds + ", " + tThrowsOutOfBounds + ")");
			if (mThrowsOutOfBounds == null) ensure(rt.equals(KEY2OBJ(rm)), "Error (" + level + ", " + seed + "): divergence in remove() between t and m (" + rt + ", " + rm + ")");
		}

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

#if KEYS_PRIMITIVE
		/* Now we sort the data and make sure the results is the same. */
		m.sort(null);
		t.sort(null);
		ensure(m.equals(t), "Error (" + level + ", " + seed + "): ! m.equals(t) after sort");
		ensure(t.equals(m), "Error (" + level + ", " + seed + "): ! t.equals(m) after sort");
#endif

		/* Now we add random data in m and t using addAll on a collection, checking that the result is the same. */

		for(int i=0; i<n;  i++) {
			int p = r.nextInt() % (2 * n + 1);
			Collection m1 = new java.util.ArrayList();
			int s = r.nextInt(n / 2 + 1);
			for(int j = 0; j < s; j++) m1.add(KEY2OBJ(genKey()));

			mThrowsOutOfBounds = tThrowsOutOfBounds  = null;

			try {
				m.addAll(p, m1);
			}
			catch (IndexOutOfBoundsException e) { mThrowsOutOfBounds = e; }

			try {
				t.addAll(p, m1);
			}
			catch (IndexOutOfBoundsException e) { tThrowsOutOfBounds = e; }

			ensure((mThrowsOutOfBounds == null) == (tThrowsOutOfBounds == null), "Error (" + level + ", " + seed + "): addAll() divergence in IndexOutOfBoundsException for index " + p + " for " + m1 + " (" + mThrowsOutOfBounds + ", " + tThrowsOutOfBounds + ")");

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

		if (m.size() > n) {
			m.size(n);
			while(t.size() != n) t.remove(t.size() -1);
		}

		/* Now we add random data in m and t using addAll on a type-specific collection, checking that the result is the same. */

		for(int i=0; i<n;  i++) {
			int p = r.nextInt() % (2 * n + 1);
			COLLECTION m1 = new ARRAY_LIST();
			Collection t1 = new java.util.ArrayList();
			int s = r.nextInt(n / 2 + 1);
			for(int j = 0; j < s; j++) {
				KEY_TYPE x = genKey();
				m1.add(x);
				t1.add(KEY2OBJ(x));
			}

			mThrowsOutOfBounds = tThrowsOutOfBounds  = null;

			try {
				m.addAll(p, m1);
			}
			catch (IndexOutOfBoundsException e) { mThrowsOutOfBounds = e; }

			try {
				t.addAll(p, t1);
			}
			catch (IndexOutOfBoundsException e) { tThrowsOutOfBounds = e; }

			ensure((mThrowsOutOfBounds == null) == (tThrowsOutOfBounds == null), "Error (" + level + ", " + seed + "): polymorphic addAll() divergence in IndexOutOfBoundsException for index " + p + " for " + m1 + " (" + mThrowsOutOfBounds + ", " + tThrowsOutOfBounds + ")");

			ensure(m.equals(t), () -> "Error (" + level + ", " + seed + m + t + "): ! m.equals(t) after polymorphic addAll");
			ensure(t.equals(m), () -> "Error (" + level + ", " + seed + m + t + "): ! t.equals(m) after polymorphic addAll");
		}

		if (m.size() > n) {
			m.size(n);
			while(t.size() != n) t.remove(t.size() -1);
		}

		/* Now we add random data in m and t using addAll on a list, checking that the result is the same. */

		for(int i=0; i<n;  i++) {
			int p = r.nextInt() % (2 * n + 1);
			LIST m1 = new ARRAY_LIST();
			Collection t1 = new java.util.ArrayList();
			int s = r.nextInt(n / 2 + 1);
			for(int j = 0; j < s; j++) {
				KEY_TYPE x = genKey();
				m1.add(x);
				t1.add(KEY2OBJ(x));
			}

			mThrowsOutOfBounds = tThrowsOutOfBounds  = null;

			try {
				m.addAll(p, m1);
			}
			catch (IndexOutOfBoundsException e) { mThrowsOutOfBounds = e; }

			try {
				t.addAll(p, t1);
			}
			catch (IndexOutOfBoundsException e) { tThrowsOutOfBounds = e; }

			ensure((mThrowsOutOfBounds == null) == (tThrowsOutOfBounds == null), "Error (" + level + ", " + seed + "): list addAll() divergence in IndexOutOfBoundsException for index " + p + " for " + m1 + " (" + mThrowsOutOfBounds + ", " + tThrowsOutOfBounds + ")");

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

		/* Now we add random data in m and t using addElements, checking that the result is the same. */

		for(int i=0; i<n;  i++) {
			int p = r.nextInt() % (2 * n + 1);
			Collection t1 = new java.util.ArrayList();
			int s = r.nextInt(n / 2 + 1);
			KEY_TYPE a[] = new KEY_TYPE [s];
			for(int j = 0; j < s; j++) {
				KEY_TYPE x = genKey();
				t1.add(KEY2OBJ(x));
				a[j] = x;
			}

			mThrowsOutOfBounds = tThrowsOutOfBounds  = null;

			try {
				m.addElements(p, a);
			}
			catch (IndexOutOfBoundsException e) { mThrowsOutOfBounds = e; }

			try {
				t.addAll(p, t1);
			}
			catch (IndexOutOfBoundsException e) { tThrowsOutOfBounds = e; }

			ensure((mThrowsOutOfBounds == null) == (tThrowsOutOfBounds == null), "Error (" + level + ", " + seed + "): list addElements() divergence in IndexOutOfBoundsException for index " + p + " for " + t1 + " (" + mThrowsOutOfBounds + ", " + tThrowsOutOfBounds + ")");

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

		if (m.size() > n) {
			m.size(n);
			while(t.size() != n) t.remove(t.size() -1);
		}

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

		for(Iterator i=t.iterator(); i.hasNext();) {
			ensure(m.contains(i.next()), "Error (" + level + ", " + seed + "): m and t differ on an entry after removal (iterating on t)");
		}

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

		for(Iterator i=m.listIterator(); i.hasNext();) {
			ensure(t.contains(i.next()), "Error (" + level + ", " + seed + "): m and t differ on an entry after removal (iterating on m)");
		}

		/* Now we check that both sets agree on random keys. For m we use the standard method. */

		for(int i = 0; i < n; i++) {
			int p = r.nextInt() % (n * 2);

			mThrowsOutOfBounds = tThrowsOutOfBounds  = null;

			try {
				m.get(p);
			}
			catch (IndexOutOfBoundsException e) { mThrowsOutOfBounds = e; }
			try {
				t.get(p);
			}
			catch (IndexOutOfBoundsException e) { tThrowsOutOfBounds = e; }

			ensure((mThrowsOutOfBounds == null) == (tThrowsOutOfBounds == null), "Error (" + level + ", " + seed + "): get() divergence in IndexOutOfBoundsException for index " + p + "  (" + mThrowsOutOfBounds + ", " + tThrowsOutOfBounds + ")");
			if (mThrowsOutOfBounds == null) ensure(t.get(p).equals(m.get(p)), "Error (" + level + ", " + seed + "): m and t differ on position " + p + " (" + m.get(p) + ", " + t.get(p) +")");

		}

		/* Now we inquiry about the content with indexOf()/lastIndexOf(). */

		for(int i=0; i<10*n;  i++) {
			KEY_TYPE T = genKey();
			ensure(m.indexOf(KEY2OBJ(T)) == t.indexOf(KEY2OBJ(T)),
					"Error (" + level + ", " + seed + "): indexOf() divergence for " + T + "  (" + m.indexOf(KEY2OBJ(T)) + ", " + t.indexOf(KEY2OBJ(T)) + ")");
			ensure(m.lastIndexOf(KEY2OBJ(T)) == t.lastIndexOf(KEY2OBJ(T)),
					"Error (" + level + ", " + seed + "): lastIndexOf() divergence for " + T + "  (" + m.lastIndexOf(KEY2OBJ(T)) + ", " + t.lastIndexOf(KEY2OBJ(T)) + ")");
			ensure(m.indexOf(T) == t.indexOf(KEY2OBJ(T)),
					"Error (" + level + ", " + seed + "): polymorphic indexOf() divergence for " + T + "  (" + m.indexOf(T) + ", " + t.indexOf(KEY2OBJ(T)) + ")");
			ensure(m.lastIndexOf(T) == t.lastIndexOf(KEY2OBJ(T)),
					"Error (" + level + ", " + seed + "): polymorphic lastIndexOf() divergence for " + T + "  (" + m.lastIndexOf(T) + ", " + t.lastIndexOf(KEY2OBJ(T)) + ")");
		}

		/* Now we check cloning. */

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

		/* Now we play with constructors. */
		ensure(m.equals(new ARRAY_LIST((Collection)m)), "Error (" + level + ", " + seed + "): m does not equal new (Collection m)");
		ensure((new ARRAY_LIST((Collection)m)).equals(m), "Error (" + level + ", " + seed + "): new (Collection m)does not equal m");
		ensure(m.equals(new ARRAY_LIST(new java.util.ArrayList(m))), "Error (" + level + ", " + seed + "): m does not equal new (Collection m)");
		ensure((new ARRAY_LIST(new java.util.ArrayList(m)).equals(m)), "Error (" + level + ", " + seed + "): new (Collection m)does not equal m");
		ensure(m.equals(new ARRAY_LIST((COLLECTION)m)), "Error (" + level + ", " + seed + "): m does not equal new (type-specific Collection m)");
		ensure((new ARRAY_LIST((COLLECTION)m)).equals(m), "Error (" + level + ", " + seed + "): new (type-specific Collection m) does not equal m");
		ensure(m.equals(new ARRAY_LIST((LIST)m)), "Error (" + level + ", " + seed + "): m does not equal new (type-specific List m)");
		ensure((new ARRAY_LIST((LIST)m)).equals(m), "Error (" + level + ", " + seed + "): new (type-specific List m) does not equal m");
		ensure(m.equals(new ARRAY_LIST(m.listIterator())), "Error (" + level + ", " + seed + "): m does not equal new (m.listIterator())");
		ensure((new ARRAY_LIST(m.listIterator())).equals(m), "Error (" + level + ", " + seed + "): new (m.listIterator()) does not equal m");
		ensure(m.equals(new ARRAY_LIST(m.iterator())), "Error (" + level + ", " + seed + "): m does not equal new (m.type_specific_iterator())");
		ensure((new ARRAY_LIST(m.iterator())).equals(m), "Error (" + level + ", " + seed + "): new (m.type_specific_iterator()) does not equal m");

		/* Now we play with conversion to array, wrapping and copying. */
		ensure(m.equals(new ARRAY_LIST(m.TO_KEY_ARRAY())), "Error (" + level + ", " + seed + "): m does not equal new (toArray(m))");
		ensure((new ARRAY_LIST(m.TO_KEY_ARRAY())).equals(m), "Error (" + level + ", " + seed + "): new (toArray(m)) does not equal m");
		ensure(m.equals(wrap(m.TO_KEY_ARRAY())), "Error (" + level + ", " + seed + "): m does not equal wrap (toArray(m))");
		ensure((wrap(m.TO_KEY_ARRAY())).equals(m), "Error (" + level + ", " + seed + "): wrap (toArray(m)) does not equal m");


		int h = m.hashCode();

		/* Now we save and read m. */

		LIST 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 = (LIST)ois.readObject();
			ois.close();
			ff.delete();
		}

#if ! KEYS_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. */

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

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

		/* Now we play with iterators. */

		{
			KEY_LIST_ITERATOR i;
			java.util.ListIterator j;
			Object J;
			i = m.listIterator();
			j = t.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(i.next().equals(J = j.next()), "Error (" + level + ", " + seed + "): divergence in next()");

					if (r.nextFloat() < 0.2) {
						i.remove();
						j.remove();
					}
					else if (r.nextFloat() < 0.2) {
						KEY_TYPE T = genKey();
						i.set(T);
						j.set(KEY2OBJ(T));
					}
					else if (r.nextFloat() < 0.2) {
						KEY_TYPE T = genKey();
						i.add(T);
						j.add(KEY2OBJ(T));
					}
				}
				else if (r.nextFloat() < .2 && i.hasPrevious()) {
					ensure(i.previous().equals(J = j.previous()), "Error (" + level + ", " + seed + "): divergence in previous()");

					if (r.nextFloat() < 0.2) {
						i.remove();
						j.remove();
					}
					else if (r.nextFloat() < 0.2) {
						KEY_TYPE T = genKey();
						i.set(T);
						j.set(KEY2OBJ(T));
					}
					else if (r.nextFloat() < 0.2) {
						KEY_TYPE T = genKey();
						i.add(T);
						j.add(KEY2OBJ(T));
					}
				}

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

			}

		}

		/* Now we play with spliterators.
		 *
		 * Or rather we would, except comparing results of spliterators directly is a bit painful.
		 * However, there is an easy workaround; use streams, which are built on Spliterators.
		 */
		{
#if KEYS_REFERENCE
			java.util.stream.Stream<KEY_TYPE> i = m.stream();
			java.util.stream.Stream<KEY_TYPE> j = t.stream();
#elif KEY_CLASS_Boolean
			java.util.stream.Stream<KEY_CLASS> i = m.stream();
			java.util.stream.Stream<KEY_CLASS> j = t.stream();
#else
			JDK_PRIMITIVE_STREAM i = m.KEY_WIDENED_STREAM_METHOD();
			java.util.stream.Stream<KEY_CLASS> j = t.stream();
#endif

			if (PARALLEL_STREAMS) {
				i = i.parallel();
				j = j.parallel();
			}

#if KEYS_REFERENCE || KEY_CLASS_Boolean
			Object[] iArray = i.toArray();
			Object[] jArray = j.toArray();
#elif KEY_CLASS_Character
			KEY_TYPE_WIDENED[] iArray = i.toArray();
			KEY_TYPE_WIDENED[] jArray = j.MAP_TO_KEY_WIDENED(c -> (int)c.charValue()).toArray();
#else
			KEY_TYPE_WIDENED[] iArray = i.toArray();
			KEY_TYPE_WIDENED[] jArray = j.MAP_TO_KEY_WIDENED(Number::KEY_WIDENED_VALUE).toArray();
#endif
			ensure(java.util.Arrays.equals(iArray, jArray), "Error (" + level + ", " + seed + "): divergence in toArray() from streams (" + java.util.Arrays.toString(iArray) + " != " + java.util.Arrays.toString(jArray) + ")");
		}

		{
			Object previous = null;
			Object I, J;
			int from = r.nextInt(m.size() +1);
			KEY_LIST_ITERATOR i;
			java.util.ListIterator j;
			i = m.listIterator(from);
			j = t.listIterator(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() , "Error (" + level + ", " + seed + "): divergence in hasPrevious() (iterator with starting point " + from + ")");

				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);

					if (r.nextFloat() < 0.2) {
						//System.err.println("Removing in next");
						i.remove();
						j.remove();
					}
					else if (r.nextFloat() < 0.2) {
						KEY_TYPE T = genKey();
						i.set(T);
						j.set(KEY2OBJ(T));
					}
					else if (r.nextFloat() < 0.2) {
						KEY_TYPE T = genKey();
						i.add(T);
						j.add(KEY2OBJ(T));
					}
				}
				else if (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.2) {
						//System.err.println("Removing in prev");
						i.remove();
						j.remove();
					}
					else if (r.nextFloat() < 0.2) {
						KEY_TYPE T = genKey();
						i.set(T);
						j.set(KEY2OBJ(T));
					}
					else if (r.nextFloat() < 0.2) {
						KEY_TYPE T = genKey();
						i.add(T);
						j.add(KEY2OBJ(T));
					}
				}
			}

		}

		/* 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 subset. */

		if (! m.isEmpty()) {
			int start = r.nextInt(m.size());
			int end = start + r.nextInt(m.size() - start);
			//System.err.println("Checking subList from " + start + " to " + end + " (level=" + (level+1) + ")...");
			testLists(m.subList(start, end), t.subList(start, end), n, level + 1);

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

		}

		m.clear();
		t.clear();
		ensure(m.isEmpty(), "Error (" + level + ", " + seed + "): m is not empty after clear()");
	}


	protected static void runTest(int n) throws Exception {
		ARRAY_LIST m = new ARRAY_LIST();
		java.util.ArrayList t = new java.util.ArrayList();
		topList = m;
		k = new Object[n];
		nk = new Object[n];
		kt = new KEY_TYPE[n];
		nkt = new KEY_TYPE[n];

		for(int i = 0; i < n; i++) {
#if KEYS_REFERENCE
			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
		}

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

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

		testLists(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

}