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

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

/** A type-specific array-based immutable list; provides some additional methods that use polymorphism to avoid (un)boxing.
 *
 * <p>Instances of this class are immutable
 * and (contrarily to mutable array-based list implementations) the backing array is not exposed.
 * Instances can be built using a variety of methods, but note that constructors using
 * an array will not make a defensive copy.
 *
 * <p>This class implements the bulk method {@code getElements()} using
 * high-performance system calls (e.g., {@link
 * System#arraycopy(Object,int,Object,int,int) System.arraycopy()}) instead of
 * expensive loops.
 */

public class IMMUTABLE_LIST KEY_GENERIC extends LISTS.ImmutableListBase KEY_GENERIC implements LIST KEY_GENERIC, RandomAccess, Cloneable, java.io.Serializable {
	private static final long serialVersionUID = 0L;

	SUPPRESS_WARNINGS_KEY_UNCHECKED_RAWTYPES
	static final IMMUTABLE_LIST EMPTY = new IMMUTABLE_LIST(ARRAYS.EMPTY_ARRAY);

#if KEYS_PRIMITIVE
#define _EMPTY_ARRAY ARRAYS.EMPTY_ARRAY
#else
	SUPPRESS_WARNINGS_KEY_UNCHECKED
	private static final KEY_GENERIC KEY_GENERIC_TYPE[] emptyArray() {
		return KEY_GENERIC_ARRAY_CAST ARRAYS.EMPTY_ARRAY;
	}
#define _EMPTY_ARRAY emptyArray()
#endif

	/** The backing array; all elements are part of this list. */
	private final KEY_GENERIC_TYPE[] a;

	/** Creates a new immutable list using a given array.
	 *
	 * <p>Note that this constructor does not perform a defensive copy.
	 *
	 * @param a the array that will be used to back this immutable list.
	 */

	public IMMUTABLE_LIST(final KEY_GENERIC_TYPE[] a) {
		this.a = a;
	}

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

	public IMMUTABLE_LIST(final Collection<? extends KEY_GENERIC_CLASS> c) {
#if KEYS_PRIMITIVE
		this(c.isEmpty() ? _EMPTY_ARRAY : ITERATORS.unwrap( ITERATORS.AS_KEY_ITERATOR(c.iterator())));
#else
		this(c.isEmpty() ? _EMPTY_ARRAY : ITERATORS.unwrap(c.iterator()));
#endif
	}

	/** Creates a new immutable list and fills it with a given type-specific collection.
	 *
	 * @param c a type-specific collection that will be used to fill the immutable list.
	 */
	public IMMUTABLE_LIST(final COLLECTION KEY_EXTENDS_GENERIC c) {
		this(c.isEmpty() ? _EMPTY_ARRAY : ITERATORS.unwrap(c.iterator()));
	}

	/** Creates a new immutable list and fills it with a given type-specific list.
	 *
	 * @param l a type-specific list that will be used to fill the immutable list.
	 */
	SUPPRESS_WARNINGS_KEY_UNCHECKED
	public IMMUTABLE_LIST(final LIST KEY_EXTENDS_GENERIC l) {
		this(l.isEmpty() ? _EMPTY_ARRAY : KEY_GENERIC_ARRAY_CAST new KEY_TYPE[l.size()]);
		l.getElements(0, a, 0, l.size());
	}

	/** Creates a new immutable list and fills it with the elements of a given array.
	 *
	 * @param a an array whose elements will be used to fill the immutable list.
	 * @param offset the first element to use.
	 * @param length the number of elements to use.
	 */
	SUPPRESS_WARNINGS_KEY_UNCHECKED
	public IMMUTABLE_LIST(final KEY_GENERIC_TYPE[] a, final int offset, final int length) {
		this(length == 0 ? _EMPTY_ARRAY : KEY_GENERIC_ARRAY_CAST new KEY_TYPE[length]);
		System.arraycopy(a, offset, this.a, 0, length);
	}

	/** Creates a new immutable 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 immutable list.
	 */
	public IMMUTABLE_LIST(final KEY_ITERATOR KEY_EXTENDS_GENERIC i) {
		this(i.hasNext() ? ITERATORS.unwrap(i) : _EMPTY_ARRAY);
	}

	/**
	 * Returns an empty immutable list.
	 * @return an immutable list (possibly shared) that is empty.
	 */
	 SUPPRESS_WARNINGS_KEY_UNCHECKED
	 public static KEY_GENERIC IMMUTABLE_LIST KEY_GENERIC of() {
		return EMPTY;
	 }

	/** Creates an immutable list using a list of elements.
	 *
	 * <p>Note that this method does not perform a defensive copy.
	 *
	 * @param init a list of elements that will be used to initialize the list.
	 * @return a new immutable list containing the given elements.
	 */
	SAFE_VARARGS
	public static KEY_GENERIC IMMUTABLE_LIST KEY_GENERIC of(final KEY_GENERIC_TYPE... init) {
		return init.length == 0 ? of() : new IMMUTABLE_LIST KEY_GENERIC(init);
	}

#if KEYS_INT_LONG_DOUBLE || KEYS_REFERENCE
	private static KEY_GENERIC IMMUTABLE_LIST KEY_GENERIC convertTrustedToImmutableList(ARRAY_LIST KEY_GENERIC arrayList) {
		if (arrayList.isEmpty()) {
			return of();
		}
		KEY_GENERIC_TYPE[] backingArray = arrayList.elements();
		if (arrayList.size() != backingArray.length) {
			backingArray = java.util.Arrays.copyOf(backingArray, arrayList.size());
		}
		return new IMMUTABLE_LIST KEY_GENERIC_DIAMOND (backingArray);
  }
#endif

#if KEYS_INT_LONG_DOUBLE
	/** Collects the result of a primitive {@code Stream} into a new ImmutableList.
	 *
	 * <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 IMMUTABLE_LIST KEY_GENERIC toList(JDK_PRIMITIVE_STREAM stream) {
		return convertTrustedToImmutableList(ARRAY_LIST.toList(stream));
	}

	/** Collects the result of a primitive {@code Stream} into a new ImmutableList, 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 IMMUTABLE_LIST KEY_GENERIC toListWithExpectedSize(JDK_PRIMITIVE_STREAM stream, int expectedSize) {
		return convertTrustedToImmutableList(ARRAY_LIST.toListWithExpectedSize(stream, expectedSize));
	}
#elif KEYS_REFERENCE
	private static final Collector<KEY_TYPE, ?, IMMUTABLE_LIST<KEY_TYPE>> TO_LIST_COLLECTOR =
		Collector.of(
			ARRAY_LIST::new,
			ARRAY_LIST::add,
			ARRAY_LIST::combine,
			IMMUTABLE_LIST::convertTrustedToImmutableList);

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

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

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

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


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

	@Override
	public int size() {
		return a.length;
	}

	@Override
	public boolean isEmpty() {
		return a.length == 0;
	}

   	/** 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);
	}

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

#if KEYS_PRIMITIVE
	@Override
	public KEY_TYPE[] TO_KEY_ARRAY() {
		if (a.length == 0) return ARRAYS.EMPTY_ARRAY;
		return a.clone();
	}

	@Override
	public KEY_TYPE[] toArray(KEY_TYPE[] a) {
		if (a == null || a.length < size()) a = new KEY_TYPE[this.a.length];
		System.arraycopy(this.a, 0, a, 0, size());
		return a;
	}
#else // KEYS_REFERENCE
	@Override
	public Object[] toArray() {
		// A subtle part of the spec says the returned array must be Object[] exactly.
		if (a.length == 0) return it.unimi.dsi.fastutil.objects.ObjectArrays.EMPTY_ARRAY;
		if (a.getClass() == Object[].class) return a.clone();
		return java.util.Arrays.copyOf(a, a.length, 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;

				@Override
				public boolean hasNext() { return pos < a.length; }
				@Override
				public boolean hasPrevious() { return pos > 0; }
				@Override
				public KEY_GENERIC_TYPE NEXT_KEY() { if (! hasNext()) throw new NoSuchElementException(); return a[pos++]; }
				@Override
				public KEY_GENERIC_TYPE PREV_KEY() { if (! hasPrevious()) throw new NoSuchElementException(); return a[--pos]; }
				@Override
				public int nextIndex() { return pos; }
				@Override
				public int previousIndex() { return pos - 1; }
				@Override
				public void forEachRemaining(final METHOD_ARG_KEY_CONSUMER action) {
					final KEY_GENERIC_TYPE[] a = IMMUTABLE_LIST.this.a;
					while (pos < a.length) {
						action.accept(a[pos++]);
					}
				}
				@Override
				public void add(KEY_GENERIC_TYPE k) {
					throw new UnsupportedOperationException();
				}
				@Override
				public void set(KEY_GENERIC_TYPE k) {
					throw new UnsupportedOperationException();
				}
				@Override
				public void remove() {
					throw new UnsupportedOperationException();
				}
				@Override
				public int back(int n) {
					if (n < 0) throw new IllegalArgumentException("Argument must be nonnegative: " + n);
					final int remaining = pos;
					if (n < remaining) {
						pos -= n;
					} else {
						n = remaining;
						pos = 0;
					}
					return n;
				}
				@Override
				public int skip(int n) {
					if (n < 0) throw new IllegalArgumentException("Argument must be nonnegative: " + n);
					final int remaining = a.length - pos;
					if (n < remaining) {
						pos += n;
					} else {
						n = remaining;
						pos = a.length;
					}
					return n;
				}
			};
	}

  private final class Spliterator implements KEY_SPLITERATOR KEY_GENERIC {
		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, a.length);
		}

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

		@Override
		public int characteristics() { return SPLITERATORS.LIST_SPLITERATOR_CHARACTERISTICS | java.util.Spliterator.IMMUTABLE; }

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

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

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

		@Override
		public long skip(long n) {
			if (n < 0) throw new IllegalArgumentException("Argument must be nonnegative: " + n);
			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() {
			int retLen = (max - pos) >> 1;
			if (retLen <= 1) return null;
			int myNewPos = pos + retLen;
			int retMax = myNewPos;
			int oldPos = pos;
			this.pos = myNewPos;
			return new Spliterator(oldPos, retMax);
		}
	}

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

	private final static class ImmutableSubList KEY_GENERIC extends LISTS.ImmutableListBase KEY_GENERIC implements java.util.RandomAccess, java.io.Serializable {
		private static final long serialVersionUID = 7054639518438982401L;
		final IMMUTABLE_LIST KEY_GENERIC innerList;
		final int from;
		final int to;
		/**
		 * An alias to {@code innerList}'s array to save some typing. Note that 0 in this array is actually
		 * the first element of the {@code innerList}, not this sublist. {@code a[from]} is the
		 * first element of this sublist.
		 */
		final transient KEY_GENERIC_TYPE[] a;

		/** No validation; callers must validate arguments. */
		ImmutableSubList(IMMUTABLE_LIST KEY_GENERIC innerList, int from, int to) {
			this.innerList = innerList;
			this.from = from;
			this.to = to;
			this.a = innerList.a;
		}

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

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

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

		@Override
		public int size() {
			return to - from;
		}

		@Override
		public boolean isEmpty() {
			return to <= from;
		}

		@Override
		public void getElements(final int fromSublistIndex, final KEY_TYPE[] a, final int offset, final int length) {
			ARRAYS.ensureOffsetLength(a, offset, length);
			ensureRestrictedIndex(fromSublistIndex);
			if (from + length > to)
				throw new IndexOutOfBoundsException("Final index " + (from + length) + " (startingIndex: " + from + " + length: " + length + ") is greater then list length " + size());
			System.arraycopy(this.a, fromSublistIndex + from, a, offset, length);
		}

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

#if KEYS_PRIMITIVE
		@Override
		public KEY_TYPE[] TO_KEY_ARRAY() {
			return java.util.Arrays.copyOfRange(a, from, to);
		}

		@Override
		public KEY_TYPE[] toArray(KEY_TYPE[] a) {
			if (a == null || a.length < size()) a = new KEY_TYPE[size()];
			System.arraycopy(this.a, from, a, 0, size());
			return a;
		}
#else // KEYS_REFERENCE
		@Override
		public Object[] toArray() {
			// A subtle part of the spec says the returned array must be Object[] exactly.
			return java.util.Arrays.copyOfRange(a, from, to, Object[].class);
		}

		SUPPRESS_WARNINGS_KEY_UNCHECKED
		@Override
		public KEY_GENERIC KEY_GENERIC_TYPE[] toArray(KEY_GENERIC_TYPE[] a) {
			final int size = size();
			if (a == null) {
				a = KEY_GENERIC_ARRAY_CAST new Object[size];
			} else if (a.length < size) {
				a = KEY_GENERIC_ARRAY_CAST Array.newInstance(a.getClass().getComponentType(), size);
			}
			System.arraycopy(this.a, from, 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 + from;

					@Override
					public boolean hasNext() { return pos < to; }
					@Override
					public boolean hasPrevious() { return pos > from; }
					@Override
					public KEY_GENERIC_TYPE NEXT_KEY() { if (! hasNext()) throw new NoSuchElementException(); return a[pos++]; }
					@Override
					public KEY_GENERIC_TYPE PREV_KEY() { if (! hasPrevious()) throw new NoSuchElementException(); return a[--pos]; }
					@Override
					public int nextIndex() { return pos - from; }
					@Override
					public int previousIndex() { return pos - from - 1; }
					@Override
					public void forEachRemaining(final METHOD_ARG_KEY_CONSUMER action) {
						final KEY_GENERIC_TYPE[] a = ImmutableSubList.this.a;
						while (pos < to) {
							action.accept(a[pos++]);
						}
					}
					@Override
					public void add(KEY_GENERIC_TYPE k) {
						throw new UnsupportedOperationException();
					}
					@Override
					public void set(KEY_GENERIC_TYPE k) {
						throw new UnsupportedOperationException();
					}
					@Override
					public void remove() {
						throw new UnsupportedOperationException();
					}
					@Override
					public int back(int n) {
						if (n < 0) throw new IllegalArgumentException("Argument must be nonnegative: " + n);
						final int remaining = pos - from;
						if (n < remaining) {
							pos -= n;
						} else {
							n = remaining;
							pos = from;
						}
						return n;
					}
					@Override
					public int skip(int n) {
						if (n < 0) throw new IllegalArgumentException("Argument must be nonnegative: " + n);
						final int remaining = to - pos;
						if (n < remaining) {
							pos += n;
						} else {
							n = remaining;
							pos = to;
						}
						return n;
					}
				};
		}

		private final class SubListSpliterator extends SPLITERATORS.EarlyBindingSizeIndexBasedSpliterator KEY_GENERIC {

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

			/** No validation; callers must validate arguments. */
			private SubListSpliterator(int pos, int maxPos) {
				super(pos, maxPos);
			}

			// Remember, the indexes we are getting is the real array's index, not our sublist relative index.
	 		@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 >= maxPos) return false;
				action.accept(a[pos++]);
				return true;
			}
			@Override
			public void forEachRemaining(final METHOD_ARG_KEY_CONSUMER action) {
				final KEY_GENERIC_TYPE[] a = ImmutableSubList.this.a;
				final int max = maxPos;
				while(pos < max) {
					action.accept(a[pos++]);
				}
			}
			@Override
			public int characteristics() { return SPLITERATORS.LIST_SPLITERATOR_CHARACTERISTICS | java.util.Spliterator.IMMUTABLE; }
		}

		@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 IMMUTABLE_LIST) {
				SUPPRESS_WARNINGS_KEY_UNCHECKED
				IMMUTABLE_LIST KEY_GENERIC other = (IMMUTABLE_LIST KEY_GENERIC) o;
				return contentsEquals(other.a, 0, other.size());
			}
			if (o instanceof ImmutableSubList) {
				SUPPRESS_WARNINGS_KEY_UNCHECKED
				ImmutableSubList KEY_GENERIC other = (ImmutableSubList KEY_GENERIC) o;
				return contentsEquals(other.a, 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) {
		    final KEY_GENERIC_TYPE[] a = this.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 (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 IMMUTABLE_LIST) {
				SUPPRESS_WARNINGS_KEY_UNCHECKED
				IMMUTABLE_LIST KEY_GENERIC other = (IMMUTABLE_LIST KEY_GENERIC) l;
				return contentsCompareTo(other.a, 0, other.size());
			}
			if (l instanceof ImmutableSubList) {
				SUPPRESS_WARNINGS_KEY_UNCHECKED
				ImmutableSubList KEY_GENERIC other = (ImmutableSubList KEY_GENERIC) l;
				return contentsCompareTo(other.a, other.from, other.to);
			}
			return super.compareTo(l);
		}

#endif

		private Object readResolve() throws java.io.ObjectStreamException {
			// We need to recheck the invariants of the subList and reestablish our "a" array alias.
			// Easiest way to do this is to just make a subList anew.
			// This will not cause a recopy of contents as subLists are a view, so this is all constant time.
			try {
				return innerList.subList(from, to);
			} catch (IllegalArgumentException | IndexOutOfBoundsException ex) {
				throw (java.io.InvalidObjectException) (new java.io.InvalidObjectException(ex.getMessage()).initCause(ex));
			}
		}

		SUPPRESS_WARNINGS_KEY_UNCHECKED
		@Override
		public LIST KEY_GENERIC subList(int from, int to) {
			// We don't need to worry about keeping all nested sublists up to date with bounds as we are immutable.
			// So don't even nest; just return a sublist with the immediate parent of the root list.
			ensureIndex(from);
			ensureIndex(to);
			if (from == to) return EMPTY;
			if (from > to) throw new IllegalArgumentException("Start index (" + from + ") is greater than end index (" + to + ")");
			return new ImmutableSubList KEY_GENERIC_DIAMOND(innerList, from + this.from, to + this.from);
		}
	}

	/**
	 * {@inheritDoc}
	 *
	 * @apiNote The returned list will be immutable, but is currently not declared to return an
	 * instance of {@code ImmutableList} due to complications of implementation details.
	 * This may change in a future version (in other words, do not consider the return type of
	 * this method to be stable if making a subclass of {@code ImmutableList}).
	 */
	SUPPRESS_WARNINGS_KEY_UNCHECKED
	@Override
	public LIST KEY_GENERIC subList(int from, int to) {
		if (from == 0 && to == size()) return this;
		ensureIndex(from);
		ensureIndex(to);
		if (from == to) return EMPTY;
		if (from > to) throw new IllegalArgumentException("Start index (" + from + ") is greater than end index (" + to + ")");
		return new ImmutableSubList KEY_GENERIC_DIAMOND(this, from, to);
	}


	@Override
	public IMMUTABLE_LIST KEY_GENERIC clone() {
		return this;
	}

	/** Compares this type-specific immutable 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 immutable list.
	 * @return true if the argument contains the same elements of this type-specific immutable list.
	 */
	public boolean equals(final IMMUTABLE_LIST KEY_GENERIC l) {
		if (l == this) return true;
		if (a == l.a) 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 KEYS_USE_REFERENCE_EQUALITY
		while(s-- !=  0) if (a1[s] != a2[s]) return false;
		return true;
#else
		return java.util.Arrays.equals(a1, a2);
#endif
	}

#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 IMMUTABLE_LIST) {
			return equals((IMMUTABLE_LIST KEY_GENERIC) o);
		}
		if (o instanceof ImmutableSubList) {
			// Sublist has an optimized sub-array based comparison, reuse that.
			return ((ImmutableSubList KEY_GENERIC)o).equals(this);
		}
		return super.equals(o);
	}

#if ! KEYS_USE_REFERENCE_EQUALITY
	/** Compares this immutable list to another immutable list.
	 *
	 * @apiNote This method exists only for sake of efficiency. The implementation
	 * inherited from the abstract implementation would already work.
	 *
	 * @param l an immutable 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 IMMUTABLE_LIST KEY_EXTENDS_GENERIC l) {
#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 == l.a) return 0;
#endif
		// TODO When minimum version of Java becomes Java 9, use Arrays.compare, which vectorizes.
		final int s1 = size(), s2 = l.size();
		final KEY_GENERIC_TYPE[] a1 = a, a2 = l.a;
		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 IMMUTABLE_LIST) {
			return compareTo((IMMUTABLE_LIST KEY_EXTENDS_GENERIC)l);
		}
		if (l instanceof ImmutableSubList) {
			// Safe to strip the "extends" because we will only ever take elements, never modify them (especially because it is immutable).
			ImmutableSubList KEY_GENERIC other = (ImmutableSubList KEY_GENERIC)l;
			// Must negate because we are inverting the order of the comparison.
			return -other.compareTo(this);
		}
		return super.compareTo(l);
	}
#endif
}

#undef _EMPTY_ARRAY