/*
* Copyright (C) 2002-2022 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.Iterator;
import java.util.RandomAccess;
import java.util.NoSuchElementException;
import it.unimi.dsi.fastutil.BigArrays;
import static it.unimi.dsi.fastutil.BigArrays.length;
import it.unimi.dsi.fastutil.BigList;
import it.unimi.dsi.fastutil.Size64;
#if KEYS_REFERENCE
import java.util.function.Consumer;
import java.util.stream.Collector;
#endif
#if KEYS_PRIMITIVE
/** A type-specific big list based on a big array; provides some additional methods that use polymorphism to avoid (un)boxing.
*
* <p>This class implements a lightweight, fast, open, optimized,
* reuse-oriented version of big-array-based big lists. Instances of this class
* represent a big list with a big 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 big 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. The backing big 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 BIG_ARRAY_BIG_LIST KEY_GENERIC extends ABSTRACT_BIG_LIST KEY_GENERIC implements RandomAccess, Cloneable, java.io.Serializable {
private static final long serialVersionUID = -7046029254386353130L;
#else
/** A type-specific big-array-based big 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 big-array-based big lists. Instances of this class
* represent a big list with a big array that is enlarged as needed when new entries
* are created (by increasing its current length to 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 big 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 big array is exposed by the {@link #elements()} method. If an instance
* of this class was created {@linkplain #wrap(Object[][],long) by wrapping},
* backing-array reallocations will be performed using reflection, so that
* {@link #elements()} can return a big array of the same type of the original big array; the comments
* about efficiency made in {@link it.unimi.dsi.fastutil.objects.ObjectArrays} apply here.
*
* <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 BIG_ARRAY_BIG_LIST KEY_GENERIC extends ABSTRACT_BIG_LIST KEY_GENERIC implements RandomAccess, Cloneable, java.io.Serializable {
private static final long serialVersionUID = -7046029254386353131L;
#endif
/** The initial default capacity of a big-array big list. */
public static final int DEFAULT_INITIAL_CAPACITY = 10;
#if ! KEYS_PRIMITIVE
/** Whether the backing big array was passed to {@code wrap()}. In
* this case, we must reallocate with the same type of big array. */
protected final boolean wrapped;
#endif
/** The backing big array. */
protected transient KEY_GENERIC_TYPE a[][];
/** The current actual size of the big list (never greater than the backing-array length). */
protected long size;
/** Creates a new big-array big list using a given array.
*
* <p>This constructor is only meant to be used by the wrapping methods.
*
* @param a the big array that will be used to back this big-array big list.
*/
protected BIG_ARRAY_BIG_LIST(final KEY_GENERIC_TYPE a[][], @SuppressWarnings("unused") boolean dummy) {
this.a = a;
#if ! KEYS_PRIMITIVE
this.wrapped = true;
#endif
}
/** Creates a new big-array big list with given capacity.
*
* @param capacity the initial capacity of the array list (may be 0).
*/
SUPPRESS_WARNINGS_KEY_UNCHECKED
public BIG_ARRAY_BIG_LIST(final long capacity) {
if (capacity < 0) throw new IllegalArgumentException("Initial capacity (" + capacity + ") is negative");
if (capacity == 0) a = KEY_GENERIC_BIG_ARRAY_CAST BIG_ARRAYS.EMPTY_BIG_ARRAY;
else a = KEY_GENERIC_BIG_ARRAY_CAST BIG_ARRAYS.newBigArray(capacity);
#if ! KEYS_PRIMITIVE
wrapped = false;
#endif
}
/** Creates a new big-array big list with {@link #DEFAULT_INITIAL_CAPACITY} capacity. */
SUPPRESS_WARNINGS_KEY_UNCHECKED
public BIG_ARRAY_BIG_LIST() {
a = KEY_GENERIC_BIG_ARRAY_CAST BIG_ARRAYS.DEFAULT_EMPTY_BIG_ARRAY; // We delay allocation
#if ! KEYS_PRIMITIVE
wrapped = false;
#endif
}
/** Creates a new big-array big 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 BIG_ARRAY_BIG_LIST(final COLLECTION KEY_EXTENDS_GENERIC c) {
this(Size64.sizeOf(c));
if (c instanceof BIG_LIST) {
((BIG_LIST KEY_EXTENDS_GENERIC)c).getElements(0, a, 0, size = Size64.sizeOf(c));
} else {
for(KEY_ITERATOR KEY_EXTENDS_GENERIC i = c.iterator(); i.hasNext();) add(i.NEXT_KEY());
}
}
#if KEYS_REFERENCE
/** Creates a new big-array big list and fills it with a given collection.
*
* @param c a collection that will be used to fill the array list.
*/
public BIG_ARRAY_BIG_LIST(final Collection KEY_EXTENDS_GENERIC c) {
this(Size64.sizeOf(c));
if (c instanceof BIG_LIST) {
((BIG_LIST KEY_EXTENDS_GENERIC)c).getElements(0, a, 0, size = Size64.sizeOf(c));
} else {
for(Iterator KEY_EXTENDS_GENERIC i = c.iterator(); i.hasNext();) add(i.next());
}
}
#endif
/** Creates a new big-array big 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 BIG_ARRAY_BIG_LIST(final BIG_LIST KEY_EXTENDS_GENERIC l) {
this(l.size64());
l.getElements(0, a, 0, size = l.size64());
}
/** Creates a new big-array big list and fills it with the elements of a given big array.
*
* @param a a big array whose elements will be used to fill the array list.
*/
public BIG_ARRAY_BIG_LIST(final KEY_GENERIC_TYPE a[][]) {
this(a, 0, length(a));
}
/** Creates a new big-array big list and fills it with the elements of a given big array.
*
* @param a a big 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 BIG_ARRAY_BIG_LIST(final KEY_GENERIC_TYPE a[][], final long offset, final long length) {
this(length);
BigArrays.copy(a, offset, this.a, 0, length);
size = length;
}
/** Creates a new big-array big list and fills it with the elements returned by an iterator..
*
* @param i an iterator whose returned elements will fill the array list.
*/
public BIG_ARRAY_BIG_LIST(final Iterator<? extends KEY_GENERIC_CLASS> i) {
this();
while(i.hasNext()) this.add(KEY_CLASS2TYPE(i.next()));
}
/** Creates a new big-array big 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 BIG_ARRAY_BIG_LIST(final KEY_ITERATOR KEY_EXTENDS_GENERIC i) {
this();
while(i.hasNext()) this.add(i.NEXT_KEY());
}
#if KEYS_PRIMITIVE
/** Returns the backing big array of this big list.
*
* @return the backing big array.
*/
public KEY_GENERIC_TYPE[][] elements() {
return a;
}
#else
/** Returns the backing big array of this big list.
*
* <p>If this big-array big list was created by wrapping a given big array, it is guaranteed
* that the type of the returned big array will be the same. Otherwise, the returned
* big array will be an big array of objects.
*
* @return the backing big array.
*/
public KEY_GENERIC_TYPE[][] elements() {
return a;
}
#endif
/** Wraps a given big array into a big-array list of given size.
*
* @param a a big array to wrap.
* @param length the length of the resulting big-array list.
* @return a new big-array list of the given size, wrapping the given big array.
*/
public static KEY_GENERIC BIG_ARRAY_BIG_LIST KEY_GENERIC wrap(final KEY_GENERIC_TYPE a[][], final long length) {
if (length > length(a)) throw new IllegalArgumentException("The specified length (" + length + ") is greater than the array size (" + length(a) + ")");
final BIG_ARRAY_BIG_LIST KEY_GENERIC l = new BIG_ARRAY_BIG_LIST KEY_GENERIC_DIAMOND(a, false);
l.size = length;
return l;
}
/** Wraps a given big array into a big-array big list.
*
* @param a a big array to wrap.
* @return a new big-array big list wrapping the given array.
*/
public static KEY_GENERIC BIG_ARRAY_BIG_LIST KEY_GENERIC wrap(final KEY_GENERIC_TYPE a[][]) {
return wrap(a, length(a));
}
/** Creates a new empty big array list.
*
* @return a new empty big-array big list.
*/
public static KEY_GENERIC BIG_ARRAY_BIG_LIST KEY_GENERIC of() {
return new BIG_ARRAY_BIG_LIST KEY_GENERIC_DIAMOND();
}
/** Creates a big array list using a list of elements.
*
* @param init a list of elements that will be used to initialize the big list.
* It is possible (but not assured) that the returned big-array big list will be
* backed by the given array in one of its segments.
* @return a new big-array big list containing the given elements.
* @see BigArrays#wrap
*/
SAFE_VARARGS
public static KEY_GENERIC BIG_ARRAY_BIG_LIST KEY_GENERIC of(final KEY_GENERIC_TYPE... init) {
return wrap(BigArrays.wrap(init));
}
#if KEYS_INT_LONG_DOUBLE
/** Collects the result of a primitive {@code Stream} into a new BigArrayBigList.
*
* <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 BIG_ARRAY_BIG_LIST KEY_GENERIC toBigList(JDK_PRIMITIVE_STREAM stream) {
return stream.collect(
BIG_ARRAY_BIG_LIST::new,
BIG_ARRAY_BIG_LIST::add,
BIG_ARRAY_BIG_LIST::addAll);
}
/** Collects the result of a primitive {@code Stream} into a new BigArrayBigList.
*
* <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.
* @implNote The current implementation preallocates the full size for every worker thread when used on parallel streams.
* This can be quite wasteful, as worker threads other then the first don't usually handle the contents of the full stream.
*/
public static KEY_GENERIC BIG_ARRAY_BIG_LIST KEY_GENERIC toBigListWithExpectedSize(JDK_PRIMITIVE_STREAM stream, long expectedSize) {
return stream.collect(
() -> new BIG_ARRAY_BIG_LIST KEY_GENERIC(expectedSize),
BIG_ARRAY_BIG_LIST::add,
BIG_ARRAY_BIG_LIST::addAll);
}
#elif KEYS_REFERENCE
// Collector wants a function that returns the collection being added to.
private BIG_ARRAY_BIG_LIST KEY_GENERIC combine(BIG_ARRAY_BIG_LIST KEY_EXTENDS_GENERIC toAddFrom) {
addAll(toAddFrom);
return this;
}
private static final Collector<KEY_TYPE, ?, BIG_ARRAY_BIG_LIST<KEY_TYPE>> TO_LIST_COLLECTOR =
Collector.of(
BIG_ARRAY_BIG_LIST::new,
BIG_ARRAY_BIG_LIST::add,
BIG_ARRAY_BIG_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, ?, BIG_ARRAY_BIG_LIST KEY_GENERIC> toBigList() {
return (Collector) TO_LIST_COLLECTOR;
}
/**
* Returns a {@link Collector} that collects a {@code Stream}'s elements into a new ArrayList.
*
* @implNote The current implementation preallocates the full size for every worker thread when used on parallel streams.
* This can be quite wasteful, as worker threads other then the first don't usually handle the contents of the full stream.
*/
public static KEY_GENERIC Collector<KEY_GENERIC_TYPE, ?, BIG_ARRAY_BIG_LIST KEY_GENERIC> toBigListWithExpectedSize(long expectedSize) {
return Collector.of(
() -> new BIG_ARRAY_BIG_LIST KEY_GENERIC(expectedSize),
BIG_ARRAY_BIG_LIST::add,
BIG_ARRAY_BIG_LIST::combine);
}
#endif
/** Ensures that this big-array big list can contain the given number of entries without resizing.
*
* @param capacity the new minimum capacity for this big-array big list.
*/
SUPPRESS_WARNINGS_KEY_UNCHECKED
public void ensureCapacity(final long capacity) {
if (capacity <= length(a) || a == BIG_ARRAYS.DEFAULT_EMPTY_BIG_ARRAY) return;
#if KEYS_PRIMITIVE
a = BigArrays.forceCapacity(a, capacity, size);
#else
if (wrapped) a = BigArrays.forceCapacity(a, capacity, size);
else {
if (capacity > length(a)) {
final Object t[][] = BIG_ARRAYS.newBigArray(capacity);
BigArrays.copy(a, 0, t, 0, size);
a = (KEY_GENERIC_TYPE[][])t;
}
}
#endif
assert size <= length(a);
}
/** Grows this big-array big list, ensuring that it can contain the given number of entries without resizing,
* and in case increasing current capacity at least by a factor of 50%.
*
* @param capacity the new minimum capacity for this big-array big list.
*/
SUPPRESS_WARNINGS_KEY_UNCHECKED
private void grow(long capacity) {
final long oldLength = length(a);
if (capacity <= oldLength) return;
if (a != BIG_ARRAYS.DEFAULT_EMPTY_BIG_ARRAY) capacity = Math.max(oldLength + (oldLength >> 1), capacity);
else if (capacity < DEFAULT_INITIAL_CAPACITY) capacity = DEFAULT_INITIAL_CAPACITY;
#if KEYS_PRIMITIVE
a = BigArrays.forceCapacity(a, capacity, size);
#else
if (wrapped) a = BigArrays.forceCapacity(a, capacity, size);
else {
final Object t[][] = BIG_ARRAYS.newBigArray(capacity);
BigArrays.copy(a, 0, t, 0, size);
a = (KEY_GENERIC_TYPE[][])t;
}
#endif
assert size <= length(a);
}
@Override
public void add(final long index, final KEY_GENERIC_TYPE k) {
ensureIndex(index);
grow(size + 1);
if (index != size) BigArrays.copy(a, index, a, index + 1, size - index);
BigArrays.set(a, index, k);
size++;
assert size <= length(a);
}
@Override
public boolean add(final KEY_GENERIC_TYPE k) {
grow(size + 1);
BigArrays.set(a, size++, k);
assert size <= length(a);
return true;
}
@Override
public KEY_GENERIC_TYPE GET_KEY(final long index) {
if (index >= size) throw new IndexOutOfBoundsException("Index (" + index + ") is greater than or equal to list size (" + size + ")");
return BigArrays.get(a, index);
}
@Override
public long indexOf(final KEY_TYPE k) {
for(long i = 0; i < size; i++) if (KEY_EQUALS(k, BigArrays.get(a, i))) return i;
return -1;
}
@Override
public long lastIndexOf(final KEY_TYPE k) {
for(long i = size; i-- != 0;) if (KEY_EQUALS(k, BigArrays.get(a, i))) return i;
return -1;
}
@Override
public KEY_GENERIC_TYPE REMOVE_KEY(final long index) {
if (index >= size) throw new IndexOutOfBoundsException("Index (" + index + ") is greater than or equal to list size (" + size + ")");
final KEY_GENERIC_TYPE old = BigArrays.get(a, index);
size--;
if (index != size) BigArrays.copy(a, index + 1, a, index, size - index);
#if KEYS_REFERENCE
BigArrays.set(a, size, null);
#endif
assert size <= length(a);
return old;
}
@Override
public boolean REMOVE(final KEY_TYPE k) {
final long index = indexOf(k);
if (index == -1) return false;
REMOVE_KEY(index);
assert size <= length(a);
return true;
}
@Override
public KEY_GENERIC_TYPE set(final long 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 = BigArrays.get(a, index);
BigArrays.set(a, index, k);
return old;
}
#if KEYS_PRIMITIVE
@Override
public boolean removeAll(final COLLECTION c) {
KEY_GENERIC_TYPE[] s = null, d = null;
int ss = -1, sd = BigArrays.SEGMENT_SIZE, ds = -1, dd = BigArrays.SEGMENT_SIZE;
for (long i = 0; i < size; i++) {
if (sd == BigArrays.SEGMENT_SIZE) {
sd = 0;
s = a[++ss];
}
if (!c.contains(s[sd])) {
if (dd == BigArrays.SEGMENT_SIZE) {
d = a[++ds];
dd = 0;
}
d[dd++] = s[sd];
}
sd++;
}
final long j = BigArrays.index(ds, dd);
#if KEYS_REFERENCE
BigArrays.fill(a, j, size, null);
#endif
final boolean modified = size != j;
size = j;
return modified;
}
#endif
@Override
public boolean removeAll(final Collection<?> c) {
KEY_GENERIC_TYPE[] s = null, d = null;
int ss = -1, sd = BigArrays.SEGMENT_SIZE, ds = -1, dd = BigArrays.SEGMENT_SIZE;
for (long i = 0; i < size; i++) {
if (sd == BigArrays.SEGMENT_SIZE) {
sd = 0;
s = a[++ss];
}
if (!c.contains(KEY2OBJ(s[sd]))) {
if (dd == BigArrays.SEGMENT_SIZE) {
d = a[++ds];
dd = 0;
}
d[dd++] = s[sd];
}
sd++;
}
final long j = BigArrays.index(ds, dd);
#if KEYS_REFERENCE
BigArrays.fill(a, j, size, null);
#endif
final boolean modified = size != j;
size = j;
return modified;
}
@Override
public boolean addAll(long index, final STD_KEY_COLLECTION KEY_EXTENDS_GENERIC c) {
if (c instanceof LIST) {
return addAll(index, (LIST KEY_EXTENDS_GENERIC)c);
}
if (c instanceof BIG_LIST) {
return addAll(index, (BIG_LIST KEY_EXTENDS_GENERIC)c);
}
ensureIndex(index);
int n = c.size();
if (n == 0) return false;
grow(size + n);
BigArrays.copy(a, index, a, index + n, size - index);
final STD_KEY_ITERATOR KEY_EXTENDS_GENERIC i = c.iterator();
size += n;
assert size <= length(a);
while(n-- != 0) BigArrays.set(a, index++, i.NEXT_KEY());
return true;
}
@Override
public boolean addAll(final long index, final BIG_LIST KEY_EXTENDS_GENERIC list) {
ensureIndex(index);
final long n = list.size64();
if (n == 0) return false;
grow(size + n);
BigArrays.copy(a, index, a, index + n, size - index);
list.getElements(0, a, index, n);
size += n;
assert size <= length(a);
return true;
}
@Override
public boolean addAll(final long index, final LIST KEY_EXTENDS_GENERIC list) {
ensureIndex(index);
int n = list.size();
if (n == 0) return false;
grow(size + n);
BigArrays.copy(a, index, a, index + n, size - index);
size += n;
assert size <= length(a);
int segment = BigArrays.segment(index);
int displ = BigArrays.displacement(index);
int pos = 0;
while(n > 0) {
final int l = Math.min(a[segment].length - displ, n);
list.getElements(pos, a[segment], displ, l);
if ((displ += l) == BigArrays.SEGMENT_SIZE) {
displ = 0;
segment++;
}
pos += l;
n -= l;
}
return true;
}
@Override
public void clear() {
#if KEYS_REFERENCE
BigArrays.fill(a, 0, size, null);
#endif
size = 0;
assert size <= length(a);
}
@Override
public long size64() {
return size;
}
@Override
public void size(final long size) {
if (size > length(a)) a = BigArrays.forceCapacity(a, size, this.size);
if (size > this.size) BigArrays.fill(a, this.size, size, KEY_NULL);
#if KEYS_REFERENCE
else BigArrays.fill(a, size, this.size, KEY_NULL);
#endif
this.size = size;
}
@Override
public boolean isEmpty() {
return size == 0;
}
/** Trims this big-array big list so that the capacity is equal to the size.
*
* @see java.util.ArrayList#trimToSize()
*/
public void trim() {
trim(0);
}
/** Trims the backing big array if it is too large.
*
* If the current big array length is smaller than or equal to
* {@code n}, this method does nothing. Otherwise, it trims the
* big-array length to the maximum between {@code n} and {@link #size64()}.
*
* <p>This method is useful when reusing big lists. {@linkplain #clear() Clearing a
* big list} leaves the big-array length untouched. If you are reusing a big list
* many times, you can call this method with a typical
* size to avoid keeping around a very large big array just
* because of a few large transient big lists.
*
* @param n the threshold for the trimming.
*/
public void trim(final long n) {
final long arrayLength = length(a);
if (n >= arrayLength || size == arrayLength) return;
a = BigArrays.trim(a, Math.max(n, size));
assert size <= length(a);
}
private class SubList extends ABSTRACT_BIG_LIST.SUBLIST_RANDOM_ACCESS KEY_GENERIC {
private static final long serialVersionUID = -3185226345314976296L;
protected SubList(long from, long to) {
super(BIG_ARRAY_BIG_LIST.this, from, to);
}
// 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;
}
// Most of the inherited methods should be fine, but we can override a few of them for performance.
@Override
public KEY_GENERIC_TYPE GET_KEY(long i) {
ensureRestrictedIndex(i);
return BigArrays.get(a, i + from);
}
private final class SubListIterator extends BIG_LIST_ITERATORS.AbstractIndexBasedBigListIterator 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(long index) {
super(0, index);
}
@Override
protected final KEY_GENERIC_TYPE get(long i) { return BigArrays.get(a, from + i); }
@Override
protected final void add(long i, KEY_GENERIC_TYPE k) { SubList.this.add(i, k); }
@Override
protected final void set(long i, KEY_GENERIC_TYPE k) { SubList.this.set(i, k); }
@Override
protected final void remove(long i) { SubList.this.REMOVE_KEY(i); }
@Override
protected final long getMaxPos() { return to - from; }
@Override
public KEY_GENERIC_TYPE NEXT_KEY() { if (! hasNext()) throw new NoSuchElementException(); return BigArrays.get(a, from + (lastReturned = pos++)); }
@Override
public KEY_GENERIC_TYPE PREV_KEY() { if (! hasPrevious()) throw new NoSuchElementException(); return BigArrays.get(a, from + (lastReturned = --pos)); }
@Override
public void forEachRemaining(final METHOD_ARG_KEY_CONSUMER action) {
final long max = to - from;
while(pos < max) {
action.accept(BigArrays.get(a, from + (lastReturned = pos++)));
}
}
}
@Override
public KEY_BIG_LIST_ITERATOR KEY_GENERIC listIterator(long index) {
return new SubListIterator(index);
}
private final class SubListSpliterator extends BIG_SPLITERATORS.LateBindingSizeIndexBasedSpliterator KEY_GENERIC {
// We are using pos == 0 to be 0 relative to real array 0
SubListSpliterator() {
super(from);
}
private SubListSpliterator(long pos, long maxPos) {
super(pos, maxPos);
}
@Override
protected final long getMaxPosFromBackingStore() { return to; }
@Override
protected final KEY_GENERIC_TYPE get(long i) { return BigArrays.get(a, i); }
@Override
protected final SubListSpliterator makeForSplit(long pos, long maxPos) {
return new SubListSpliterator(pos, maxPos);
}
@Override
protected final long computeSplitPoint() {
long defaultSplit = super.computeSplitPoint();
// Align to outer array starting point if possible.
// We add/subtract one to the bounds to ensure the new pos will always shrink the range
return BigArrays.nearestSegmentStart(defaultSplit, pos + 1, getMaxPos() - 1);
}
@Override
public boolean tryAdvance(final METHOD_ARG_KEY_CONSUMER action) {
if (pos >= getMaxPos()) return false;
action.accept(BigArrays.get(a, pos++));
return true;
}
@Override
public void forEachRemaining(final METHOD_ARG_KEY_CONSUMER action) {
final long max = getMaxPos();
while(pos < max) {
action.accept(BigArrays.get(a, pos++));
}
}
}
@Override
public KEY_SPLITERATOR KEY_GENERIC spliterator() {
return new SubListSpliterator();
}
boolean contentsEquals(KEY_GENERIC_TYPE[][] otherA, long otherAFrom, long otherATo) {
if (a == otherA && from == otherAFrom && to == otherATo) return true;
if (otherATo - otherAFrom != size64()) {
return false;
}
long pos = to, otherPos = otherATo;
// We have already assured that the two ranges are the same size, so we only need to check one bound.
// If BigArrays.equals ever gets an overload that accepts bounds, use that instead
// (but make sure to break out the reference equality case).
#if KEY_CLASS_Object
while(--pos >= from) if (! java.util.Objects.equals(BigArrays.get(a, pos), BigArrays.get(otherA, --otherPos))) return false;
#else
while(--pos >= from) if (BigArrays.get(a, pos) != BigArrays.get(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 BigList)) return false;
if (o instanceof BIG_ARRAY_BIG_LIST) {
SUPPRESS_WARNINGS_KEY_UNCHECKED
BIG_ARRAY_BIG_LIST KEY_GENERIC other = (BIG_ARRAY_BIG_LIST KEY_GENERIC) o;
return contentsEquals(other.a, 0, other.size64());
}
if (o instanceof BIG_ARRAY_BIG_LIST.SubList) {
SUPPRESS_WARNINGS_KEY_UNCHECKED
BIG_ARRAY_BIG_LIST KEY_GENERIC.SubList other = (BIG_ARRAY_BIG_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, long otherAFrom, long 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;
long i, j;
for(i = from, j = otherAFrom; i < to && i < otherATo; i++, j++) {
e1 = BigArrays.get(a, i);
e2 = BigArrays.get(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 BigList <? extends KEY_GENERIC_CLASS> l) {
if (l instanceof BIG_ARRAY_BIG_LIST) {
SUPPRESS_WARNINGS_KEY_UNCHECKED
BIG_ARRAY_BIG_LIST KEY_GENERIC other = (BIG_ARRAY_BIG_LIST KEY_GENERIC) l;
return contentsCompareTo(other.a, 0, other.size64());
}
if (l instanceof BIG_ARRAY_BIG_LIST.SubList) {
SUPPRESS_WARNINGS_KEY_UNCHECKED
BIG_ARRAY_BIG_LIST KEY_GENERIC.SubList other = (BIG_ARRAY_BIG_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 BIG_LIST KEY_GENERIC subList(long from, long to) {
if (from == 0 && to == size64()) 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 big array using optimized system calls.
*
* @param from the start index (inclusive).
* @param a the destination big 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 long from, final KEY_TYPE[][] a, final long offset, final long length) {
BigArrays.copy(this.a, from, a, offset, length);
}
/** 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 long from, final KEY_TYPE[] a, final int offset, final int length) {
BigArrays.copyFromBig(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 long from, final long to) {
BigArrays.ensureFromTo(size, from, to);
BigArrays.copy(a, to, a, from, size - to);
size -= (to - from);
#if KEYS_REFERENCE
BigArrays.fill(a, size, size + to - from, 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 big 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 long index, final KEY_GENERIC_TYPE a[][], final long offset, final long length) {
ensureIndex(index);
BigArrays.ensureOffsetLength(a, offset, length);
grow(size + length);
BigArrays.copy(this.a, index, this.a, index + length, size - index);
BigArrays.copy(a, offset, this.a, index, length);
size += length;
}
/** Copies elements in the given big array into this type-specific list using optimized system calls.
*
* @param index the start index (inclusive).
* @param a the destination big 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 setElements(final long index, final KEY_TYPE[][] a, final long offset, final long length) {
BigArrays.copy(a, offset, this.a, index, length);
}
@Override
public void forEach(final METHOD_ARG_KEY_CONSUMER action) {
for (long i = 0; i < size; ++i) {
action.accept(BigArrays.get(a, i));
}
}
@Override
public KEY_BIG_LIST_ITERATOR KEY_GENERIC listIterator(final long index) {
ensureIndex(index);
return new KEY_BIG_LIST_ITERATOR KEY_GENERIC() {
long 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 BigArrays.get(a, last = pos++); }
@Override
public KEY_GENERIC_TYPE PREV_KEY() { if (! hasPrevious()) throw new NoSuchElementException(); return BigArrays.get(a, last = --pos); }
@Override
public long nextIndex() { return pos; }
@Override
public long previousIndex() { return pos - 1; }
@Override
public void add(KEY_GENERIC_TYPE k) {
BIG_ARRAY_BIG_LIST.this.add(pos++, k);
last = -1;
}
@Override
public void set(KEY_GENERIC_TYPE k) {
if (last == -1) throw new IllegalStateException();
BIG_ARRAY_BIG_LIST.this.set(last, k);
}
@Override
public void remove() {
if (last == -1) throw new IllegalStateException();
BIG_ARRAY_BIG_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(BigArrays.get(a, last = pos++));
}
}
@Override
public long back(long n) {
if (n < 0) throw new IllegalArgumentException("Argument must be nonnegative: " + n);
final long remaining = size - pos;
if (n < remaining) {
pos -= n;
} else {
n = remaining;
pos = 0;
}
last = pos;
return n;
}
@Override
public long skip(long n) {
if (n < 0) throw new IllegalArgumentException("Argument must be nonnegative: " + n);
final long remaining = size - pos;
if (n < remaining) {
pos += n;
} else {
n = remaining;
pos = size;
}
last = pos - 1;
return n;
}
};
}
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;
long 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, BIG_ARRAY_BIG_LIST.this.size, false);
}
private Spliterator(long pos, long max, boolean hasSplit) {
assert pos <= max : "pos " + pos + " must be <= max " + max;
this.pos = pos;
this.max = max;
this.hasSplit = hasSplit;
}
private long getWorkingMax() {
return hasSplit ? max : BIG_ARRAY_BIG_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(BigArrays.get(a, pos++));
return true;
}
@Override
public void forEachRemaining(final METHOD_ARG_KEY_CONSUMER action) {
for (final long max = getWorkingMax(); pos < max; ++pos) {
action.accept(BigArrays.get(a, pos));
}
}
@Override
public long skip(long n) {
if (n < 0) throw new IllegalArgumentException("Argument must be nonnegative: " + n);
final long max = getWorkingMax();
if (pos >= max) return 0;
final long remaining = max - pos;
if (n < remaining) {
pos += n;
return n;
}
n = remaining;
pos = max;
return n;
}
@Override
public KEY_SPLITERATOR KEY_GENERIC trySplit() {
final long max = getWorkingMax();
long 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;
long myNewPos = pos + retLen;
// Align to an outer array boundary if possible
// We add/subtract one to the bounds to ensure the new pos will always shrink the range
myNewPos = BigArrays.nearestSegmentStart(myNewPos, pos + 1, max - 1);
long retMax = myNewPos;
long oldPos = pos;
this.pos = myNewPos;
this.hasSplit = true;
return new Spliterator(oldPos, retMax, true);
}
}
@Override
public KEY_SPLITERATOR KEY_GENERIC spliterator() {
return new Spliterator();
}
SUPPRESS_WARNINGS_KEY_UNCHECKED
@Override
public BIG_ARRAY_BIG_LIST KEY_GENERIC clone() {
BIG_ARRAY_BIG_LIST KEY_GENERIC c;
// Test for fastpath we can do if exactly an BigArrayBigList
if (getClass() == BIG_ARRAY_BIG_LIST.class) {
c = new BIG_ARRAY_BIG_LIST KEY_GENERIC_DIAMOND(size);
c.size = size;
} else {
try {
c = (BIG_ARRAY_BIG_LIST KEY_GENERIC)super.clone();
} catch (CloneNotSupportedException e) {
// Can't happen
throw new InternalError(e);
}
c.a = KEY_GENERIC_BIG_ARRAY_CAST BIG_ARRAYS.newBigArray(size);
}
BigArrays.copy(a, 0, c.a, 0, size);
return c;
}
/** Compares this type-specific big-array list to another one.
*
* <p>This method exists only for sake of efficiency. The implementation
* inherited from the abstract implementation would already work.
*
* @param l a type-specific big-array list.
* @return true if the argument contains the same elements of this type-specific big-array list.
*/
public boolean equals(final BIG_ARRAY_BIG_LIST KEY_GENERIC l) {
if (l == this) return true;
long s = size64();
if (s != l.size64()) return false;
final KEY_GENERIC_TYPE[][] a1 = a;
final KEY_GENERIC_TYPE[][] a2 = l.a;
// Already checked s == l.size64 above
if (a1 == a2) return true;
// Backwards loop is faster then forwards loop, at least in Java 8 and below.
#if KEY_CLASS_Object
while(s-- != 0) if (! java.util.Objects.equals(BigArrays.get(a1, s), BigArrays.get(a2, s))) return false;
#else
while(s-- != 0) if (BigArrays.get(a1, s) != BigArrays.get(a2, s)) return false;
#endif
return true;
}
#if KEYS_PRIMITIVE
@SuppressWarnings("unlikely-arg-type" )
#else
@SuppressWarnings({ "unchecked", "unlikely-arg-type" })
#endif
@Override
public boolean equals(final Object o) {
if (o == this) return true;
if (o == null) return false;
if (!(o instanceof BigList)) return false;
if (o instanceof BIG_ARRAY_BIG_LIST) {
// Safe cast because we are only going to take elements from other list, never give them
return equals((BIG_ARRAY_BIG_LIST KEY_GENERIC) o);
}
if (o instanceof BIG_ARRAY_BIG_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 ((BIG_ARRAY_BIG_LIST KEY_GENERIC.SubList)o).equals(this);
}
return super.equals(o);
}
#if ! KEYS_USE_REFERENCE_EQUALITY
/** Compares this big list to another big list.
*
* <p>This method exists only for sake of efficiency. The implementation
* inherited from the abstract implementation would already work.
*
* @param l a big list.
* @return a negative integer,
* zero, or a positive integer as this big list is lexicographically less than, equal
* to, or greater than the argument.
*/
SUPPRESS_WARNINGS_KEY_UNCHECKED
public int compareTo(final BIG_ARRAY_BIG_LIST KEY_EXTENDS_GENERIC l) {
final long s1 = size64(), s2 = l.size64();
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
KEY_GENERIC_TYPE e1, e2;
int r, i;
for(i = 0; i < s1 && i < s2; i++) {
e1 = BigArrays.get(a1, i);
e2 = BigArrays.get(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 BigList <? extends KEY_GENERIC_CLASS> l) {
if (l instanceof BIG_ARRAY_BIG_LIST) {
return compareTo((BIG_ARRAY_BIG_LIST KEY_EXTENDS_GENERIC)l);
}
if (l instanceof BIG_ARRAY_BIG_LIST.SubList) {
// Must negate because we are inverting the order of the comparison.
return -((BIG_ARRAY_BIG_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(BigArrays.get(a, i));
}
SUPPRESS_WARNINGS_KEY_UNCHECKED
private void readObject(java.io.ObjectInputStream s) throws java.io.IOException, ClassNotFoundException {
s.defaultReadObject();
a = KEY_GENERIC_BIG_ARRAY_CAST BIG_ARRAYS.newBigArray(size);
for(int i = 0; i < size; i++) BigArrays.set(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 java.text.NumberFormat format = new java.text.DecimalFormat("#,###.00");
private static java.text.FieldPosition p = new java.text.FieldPosition(0);
private static String format(double d) {
StringBuffer s = new StringBuffer();
return format.format(d, s, p).toString();
}
private static void speedTest(int n, boolean comp) {
System.out.println("There are presently no speed tests for this class.");
}
private static void fatal(String msg) {
throw new AssertionError(msg);
}
private static void ensure(boolean cond, String msg) {
if (cond) return;
fatal(msg);
}
private static 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 BIG_ARRAY_BIG_LIST topList;
protected static void testLists(BIG_LIST m, BIG_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");
/* 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);
java.util.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.size64() > n) {
m.size(n);
while(t.size64() != n) t.remove(t.size64() -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 BIG_ARRAY_BIG_LIST();
java.util.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.size64() > n) {
m.size(n);
while(t.size64() != n) t.remove(t.size64() -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);
BIG_LIST m1 = new BIG_ARRAY_BIG_LIST();
java.util.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 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(((BIG_ARRAY_BIG_LIST)m).clone()), "Error (" + level + ", " + seed + "): m does not equal m.clone()");
ensure(((BIG_ARRAY_BIG_LIST)m).clone().equals(m), "Error (" + level + ", " + seed + "): m.clone() does not equal m");
}
/* Now we play with constructors. */
ensure(m.equals(new BIG_ARRAY_BIG_LIST((COLLECTION)m)), "Error (" + level + ", " + seed + "): m does not equal new (type-specific Collection m)");
ensure((new BIG_ARRAY_BIG_LIST((COLLECTION)m)).equals(m), "Error (" + level + ", " + seed + "): new (type-specific nCollection m) does not equal m");
ensure(m.equals(new BIG_ARRAY_BIG_LIST((BIG_LIST)m)), "Error (" + level + ", " + seed + "): m does not equal new (type-specific List m)");
ensure((new BIG_ARRAY_BIG_LIST((BIG_LIST)m)).equals(m), "Error (" + level + ", " + seed + "): new (type-specific List m) does not equal m");
ensure(m.equals(new BIG_ARRAY_BIG_LIST(m.listIterator())), "Error (" + level + ", " + seed + "): m does not equal new (m.listIterator())");
ensure((new BIG_ARRAY_BIG_LIST(m.listIterator())).equals(m), "Error (" + level + ", " + seed + "): new (m.listIterator()) does not equal m");
ensure(m.equals(new BIG_ARRAY_BIG_LIST(m.iterator())), "Error (" + level + ", " + seed + "): m does not equal new (m.type_specific_iterator())");
ensure((new BIG_ARRAY_BIG_LIST(m.iterator())).equals(m), "Error (" + level + ", " + seed + "): new (m.type_specific_iterator()) does not equal m");
int h = m.hashCode();
/* Now we save and read m. */
BIG_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 = (BIG_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_BIG_LIST_ITERATOR i;
KEY_BIG_LIST_ITERATOR 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.parallelStream();
java.util.stream.Stream<KEY_TYPE> j = t.parallelStream();
#elif KEY_CLASS_Boolean
java.util.stream.Stream<KEY_CLASS> i = m.parallelStream();
java.util.stream.Stream<KEY_CLASS> j = t.parallelStream();
#else
JDK_PRIMITIVE_STREAM i = m.KEY_WIDENED_PARALLEL_STREAM_METHOD();
java.util.stream.Stream<KEY_CLASS> j = t.parallelStream();
#endif
#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;
long from = m.isEmpty() ? 0 : (r.nextLong() & 0x7FFFFFFFFFFFFFFFL) % m.size64();
KEY_BIG_LIST_ITERATOR i;
KEY_BIG_LIST_ITERATOR 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()) {
long start = (r.nextLong() & 0x7FFFFFFFFFFFFFFFL) % m.size64();
long end = start + (r.nextLong() & 0x7FFFFFFFFFFFFFFFL) % (m.size64() - 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 {
BIG_ARRAY_BIG_LIST m = new BIG_ARRAY_BIG_LIST();
BIG_LIST t = BIG_LISTS.asBigList(new ARRAY_LIST());
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. */
#if KEYS_PRIMITIVE
for(int i = 0; i < n; i++) t.add((KEY_GENERIC_CLASS)k[i]);
#else
for(int i = 0; i < n; i++) t.add(k[i]);
#endif
/* 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
}