/*		 
 * Copyright (C) 2002-2014 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.Iterator;
import java.util.RandomAccess;
import java.util.NoSuchElementException;
import it.unimi.dsi.fastutil.BigArrays;

#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 doubling the current length), 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>,
 * <code>addElements()</code> and <code>getElements()</code> 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 doubling the current length), 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>,
 * <code>addElements()</code> and <code>getElements()</code> 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 final static int DEFAULT_INITIAL_CAPACITY = 16;

#if ! #keys(primitive)
	/** Whether the backing big array was passed to <code>wrap()</code>. 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;

	private static final boolean ASSERTS = ASSERTS_VALUE;

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

	@SuppressWarnings("unused")
	protected BIG_ARRAY_BIG_LIST( final KEY_GENERIC_TYPE a[][], 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).
	 */

	@SuppressWarnings("unchecked")
	public BIG_ARRAY_BIG_LIST( final long capacity ) {
		if ( capacity < 0 ) throw new IllegalArgumentException( "Initial capacity (" + capacity + ") is negative" );

		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.
	 */
	 
	public BIG_ARRAY_BIG_LIST() {
		this( DEFAULT_INITIAL_CAPACITY );
	}

	/** 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( c.size() );
		for( KEY_ITERATOR KEY_EXTENDS_GENERIC i = c.iterator(); i.hasNext(); ) add( i.NEXT_KEY() );
	}

	/** 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.
	 *
	 * <p>Note that this constructor makes it easy to build big lists from literal arrays
	 * declared as <code><var>type</var>[][] {{ <var>init_values</var> }}</code>.
	 * The only constraint is that the number of initialisation values is
	 * below {@link it.unimi.dsi.fastutil.BigArrays#SEGMENT_SIZE}.
	 *
	 * @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, BIG_ARRAYS.length( a ) );
	}

	/** Creates a new big-array big list and fills it with the elements of a given big array.
	 *
	 * <p>Note that this constructor makes it easy to build big lists from literal arrays
	 * declared as <code><var>type</var>[][] {{ <var>init_values</var> }}</code>.
	 * The only constraint is that the number of initialisation values is
	 * below {@link it.unimi.dsi.fastutil.BigArrays#SEGMENT_SIZE}.
	 *
	 * @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 );
		BIG_ARRAYS.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( 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 > BIG_ARRAYS.length( a ) ) throw new IllegalArgumentException( "The specified length (" + length + ") is greater than the array size (" + BIG_ARRAYS.length( a ) + ")" );
		final BIG_ARRAY_BIG_LIST KEY_GENERIC l = new BIG_ARRAY_BIG_LIST KEY_GENERIC( 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, BIG_ARRAYS.length( a ) );
	}


	/** 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.
	 */
	@SuppressWarnings("unchecked")
	public void ensureCapacity( final long capacity ) {
#if #keys(primitive)
		a = BIG_ARRAYS.ensureCapacity( a, capacity, size );
#else
		if ( wrapped ) a = BIG_ARRAYS.ensureCapacity( a, capacity, size );
		else {
			if ( capacity > BIG_ARRAYS.length( a ) ) {
				final Object t[][] = BIG_ARRAYS.newBigArray( capacity );
				BIG_ARRAYS.copy( a, 0, t, 0, size );
				a = (KEY_GENERIC_TYPE[][])t;
			}
		}
#endif
		if ( ASSERTS ) assert size <= BIG_ARRAYS.length( a );
	}

	/** Grows this big-array big list, ensuring that it can contain the given number of entries without resizing,
	 * and in case enlarging it at least by a factor of two.
	 *
	 * @param capacity the new minimum capacity for this big-array big list.
	 */
	@SuppressWarnings("unchecked")
	private void grow( final long capacity ) {
#if #keys(primitive)
		a = BIG_ARRAYS.grow( a, capacity, size );
#else
		if ( wrapped ) a =  BIG_ARRAYS.grow( a, capacity, size );
		else {
			if ( capacity > BIG_ARRAYS.length( a ) ) {
				final int newLength = (int)Math.max( Math.min( 2 * BIG_ARRAYS.length( a ), it.unimi.dsi.fastutil.Arrays.MAX_ARRAY_SIZE ), capacity );
				final Object t[][] = BIG_ARRAYS.newBigArray( newLength );
				BIG_ARRAYS.copy( a, 0, t, 0, size );
				a = (KEY_GENERIC_TYPE[][])t;
			}			
		}
#endif
		if ( ASSERTS ) assert size <= BIG_ARRAYS.length( a );
	}

	public void add( final long index, final KEY_GENERIC_TYPE k ) {
		ensureIndex( index );
		grow( size + 1 );
		if ( index != size ) BIG_ARRAYS.copy( a, index, a, index + 1, size - index );
		BIG_ARRAYS.set( a, index, k );
		size++;
		if ( ASSERTS ) assert size <= BIG_ARRAYS.length( a );
	}

	public boolean add( final KEY_GENERIC_TYPE k ) {
		grow( size + 1 );
		BIG_ARRAYS.set( a, size++, k );
		if ( ASSERTS ) assert size <= BIG_ARRAYS.length( a );
		return true;
	}

	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 BIG_ARRAYS.get( a, index );
	}

	public long indexOf( final KEY_TYPE k ) {
		for( long i = 0; i < size; i++ ) if ( KEY_EQUALS( k, BIG_ARRAYS.get( a, i ) ) ) return i;
		return -1;
	}


	public long lastIndexOf( final KEY_TYPE k ) {
		for( long i = size; i-- != 0; ) if ( KEY_EQUALS( k, BIG_ARRAYS.get( a, i ) ) ) return i;
		return -1;
	}

	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 = BIG_ARRAYS.get( a, index );
		size--;
		if ( index != size ) BIG_ARRAYS.copy( a, index + 1, a, index, size - index );
#if #keys(reference)
		BIG_ARRAYS.set( a, size, null );
#endif
		if ( ASSERTS ) assert size <= BIG_ARRAYS.length( a );
		return old;
	}

	public boolean rem( final KEY_TYPE k ) {
		final long index = indexOf( k );
		if ( index == -1 ) return false;
		REMOVE_KEY( index );
		if ( ASSERTS ) assert size <= BIG_ARRAYS.length( a );
		return true;
	}

#if #keys(reference)
	public boolean remove( final Object o ) {
		return rem( o );
	}
#endif

	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 = BIG_ARRAYS.get( a, index );
		BIG_ARRAYS.set( a, index, k );
		return old;
	}

	public void clear() {
#if #keys(reference)
		BIG_ARRAYS.fill( a, 0, size, null );
#endif
		size = 0;
		if ( ASSERTS ) assert size <= BIG_ARRAYS.length( a );
	}

	public long size64() {
		return size;
	}		

	public void size( final long size ) {
		if ( size > BIG_ARRAYS.length( a ) ) ensureCapacity( size );
		if ( size > this.size ) BIG_ARRAYS.fill( a, this.size, size, KEY_NULL );
#if #keys(reference)
		else BIG_ARRAYS.fill( a, size, this.size, KEY_NULL );
#endif
		this.size = size;
	}		

	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</code>, this method does nothing. Otherwise, it trims the
	 * big-array length to the maximum between <code>n</code> 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.
	 */

	@SuppressWarnings("unchecked")
	public void trim( final long n ) {
		final long arrayLength = BIG_ARRAYS.length( a );
		if ( n >= arrayLength || size == arrayLength ) return;
		a = BIG_ARRAYS.trim( a, Math.max( n, size ) );
		if ( ASSERTS ) assert size <= BIG_ARRAYS.length( a );
	}


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

	public void getElements( final int from, final KEY_TYPE[][] a, final long offset, final long length ) {
		BIG_ARRAYS.copy( 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).
	 */
	public void removeElements( final int from, final int to ) {
		BigArrays.ensureFromTo( size, from, to );
		BIG_ARRAYS.copy( a, to, a, from, size - to );
		size -= ( to - from );
#if #keys(reference)
		BIG_ARRAYS.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.
	 */
	public void addElements( final int index, final KEY_GENERIC_TYPE a[][], final long offset, final long length ) {
		ensureIndex( index );
		BIG_ARRAYS.ensureOffsetLength( a, offset, length );
		grow( size + length );
		BIG_ARRAYS.copy( this.a, index, this.a, index + length, size - index );
		BIG_ARRAYS.copy( a, offset, this.a, index, length );
		size += length;
	}

	public KEY_BIG_LIST_ITERATOR KEY_GENERIC listIterator( final int index ) {
		ensureIndex( index );

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

				public boolean hasNext() { return pos < size; }
				public boolean hasPrevious() { return pos > 0; }
				public KEY_GENERIC_TYPE NEXT_KEY() { if ( ! hasNext() ) throw new NoSuchElementException(); return BIG_ARRAYS.get( a, last = pos++ ); }
				public KEY_GENERIC_TYPE PREV_KEY() { if ( ! hasPrevious() ) throw new NoSuchElementException(); return BIG_ARRAYS.get( a, last = --pos ); }
				public long nextIndex() { return pos; }
				public long previousIndex() { return pos - 1; }
				public void add( KEY_GENERIC_TYPE k ) { 
					if ( last == -1 ) throw new IllegalStateException();
					BIG_ARRAY_BIG_LIST.this.add( pos++, k ); 
					last = -1;
				}
				public void set( KEY_GENERIC_TYPE k ) { 
					if ( last == -1 ) throw new IllegalStateException();
					BIG_ARRAY_BIG_LIST.this.set( last, k );
				}
				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;
				}
			};
	}


	@SuppressWarnings("unchecked")
	public BIG_ARRAY_BIG_LIST KEY_GENERIC clone() {
		BIG_ARRAY_BIG_LIST KEY_GENERIC c = new BIG_ARRAY_BIG_LIST KEY_GENERIC( size );
		BIG_ARRAYS.copy( a, 0, c.a, 0, size );
		c.size = size;
		return c;
	}

#if #keyclass(Object)
	private boolean valEquals( final K a, final K b ) {
		return a == null ? b == null : a.equals( b );
	}
#endif

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

#if #keyclass(Object)
		while( s-- !=  0 ) if ( ! valEquals( BIG_ARRAYS.get( a1, s ), BIG_ARRAYS.get( a2, s ) ) ) return false;
#else
		while( s-- !=  0 ) if ( BIG_ARRAYS.get( a1, s ) != BIG_ARRAYS.get( a2, s ) ) return false;
#endif
		return true;
	}


#if ! #keyclass(Reference)

    /** 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.
     */
	@SuppressWarnings("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;
		KEY_GENERIC_TYPE e1, e2;
		int r, i;
		
		for( i = 0; i < s1 && i < s2; i++ ) {
			e1 = BIG_ARRAYS.get( a1, i );
			e2 = BIG_ARRAYS.get( a2, i );
			if ( ( r = KEY_CMP( e1, e2 ) ) != 0 ) return r;
		}

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


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

	@SuppressWarnings("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++ ) BIG_ARRAYS.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 #keyclass(Byte) || #keyclass(Short) || #keyclass(Character)
		return (KEY_TYPE)(r.nextInt());
#elif #keys(primitive)
		return r.NEXT_KEY(); 
#elif #keyclass(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 ) {
		System.out.println( msg );
		System.exit( 1 );
	}

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

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

	protected static void testLists( BIG_LIST m, BIG_LIST t, int n, int level ) {
		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;
		  
		try {
			java.io.File ff = new java.io.File("it.unimi.dsi.fastutil.test");
			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();
		}
		catch(Exception e) {
			e.printStackTrace();
			System.exit( 1 );
		}

#if ! #keyclass(Reference)
		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()" );

			}

		}

		{
			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 test( int n ) {
		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[] ) {
		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] ) ) test(n);
		} catch( Throwable e ) {
			e.printStackTrace( System.err );
			System.err.println( "seed: " + seed );
		}
	}

#endif

}