/*		 
 * Copyright (C) 2003-2014 Paolo Boldi and Sebastiano Vigna 
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License. 
 */


package PACKAGE;

#if #keyclass(Object)
import java.util.Comparator;
import it.unimi.dsi.fastutil.IndirectDoublePriorityQueue;
#endif

/** A type-specific array-based indirect double priority queue.
 *
 * <P>Instances of this class are based on a single array. This implementation
 * is extremely inefficient, but it is difficult to beat when the size of the
 * queue is very small.  The array is enlarged as needed, but it is never
 * shrunk. Use the {@link #trim()} method to reduce its size, if necessary.
 *
 * <P>Either comparator may be <code>null</code>, indicating that natural comparison should take place. Of course,
 * it makes little sense having them equal.
 */

public class ARRAY_INDIRECT_DOUBLE_PRIORITY_QUEUE KEY_GENERIC extends ARRAY_INDIRECT_PRIORITY_QUEUE KEY_GENERIC implements INDIRECT_DOUBLE_PRIORITY_QUEUE KEY_GENERIC {

	/** The secondary comparator. */
	protected KEY_COMPARATOR KEY_SUPER_GENERIC secondaryComparator;

	/** Creates a new empty queue with a given capacity.
	 *
	 * @param refArray the reference array.
	 * @param capacity the initial capacity of this queue.
	 * @param c the primary comparator used in this queue, or <code>null</code> for the natural order.
	 * @param d the secondary comparator used in this queue, or <code>null</code> for the natural order.
	 */
	public ARRAY_INDIRECT_DOUBLE_PRIORITY_QUEUE( KEY_GENERIC_TYPE[] refArray, int capacity, KEY_COMPARATOR KEY_SUPER_GENERIC c, KEY_COMPARATOR KEY_SUPER_GENERIC d ) {
		super( refArray, capacity, c );
		secondaryComparator = d;
	}


	/** Creates a new empty queue with a given capacity.
	 *
	 * <P>This constructor uses as secondary comparator the opposite order of <code>c</code>.
	 *
	 * @param refArray the reference array.
	 * @param capacity the initial capacity of this queue.
	 * @param c the primary comparator used in this queue, or <code>null</code> for the natural order.
	 */
	@SuppressWarnings("unchecked")
	public ARRAY_INDIRECT_DOUBLE_PRIORITY_QUEUE( KEY_GENERIC_TYPE[] refArray, int capacity, KEY_COMPARATOR KEY_SUPER_GENERIC c ) {
		super( refArray, capacity, c == null ? COMPARATORS.OPPOSITE_COMPARATOR : COMPARATORS.oppositeComparator( c ) );
	}


	/** Creates a new empty queue with a given capacity and natural order as primary comparator.
	 *
	 * <P>This constructor uses as secondary comparator the opposite of the natural order.
	 *
	 * @param refArray the reference array.
	 * @param capacity the initial capacity of this queue.
	 */
	public ARRAY_INDIRECT_DOUBLE_PRIORITY_QUEUE( KEY_GENERIC_TYPE[] refArray, int capacity ) {
		this( refArray, capacity, null );
	}


	/** Creates a new empty queue with capacity equal to the length of the reference array.
	 *
	 * @param refArray the reference array.
	 * @param c the primary comparator used in this queue, or <code>null</code> for the natural order.
	 * @param d the secondary comparator used in this queue, or <code>null</code> for the natural order.
	 */
	public ARRAY_INDIRECT_DOUBLE_PRIORITY_QUEUE( KEY_GENERIC_TYPE[] refArray, KEY_COMPARATOR KEY_SUPER_GENERIC c, KEY_COMPARATOR KEY_SUPER_GENERIC d ) {
		this( refArray, refArray.length, c, d );
	}

	/** Creates a new empty queue with capacity equal to the length of the reference array.
	 *
	 * <P>This constructor uses as secondary comparator the opposite order of <code>c</code>.
	 *
	 * @param refArray the reference array.
	 * @param c the primary comparator used in this queue, or <code>null</code> for the natural order.
	 */
	public ARRAY_INDIRECT_DOUBLE_PRIORITY_QUEUE( KEY_GENERIC_TYPE[] refArray, KEY_COMPARATOR KEY_SUPER_GENERIC c ) {
		this( refArray, refArray.length, c );
	}

	/** Creates a new empty queue with capacity equal to the length of the reference array and natural order as primary comparator.
	 *
	 * <P>This constructor uses as secondary comparator the opposite of the natural order.
	 *
	 * @param refArray the reference array.
	 */
	public ARRAY_INDIRECT_DOUBLE_PRIORITY_QUEUE( KEY_GENERIC_TYPE[] refArray ) {
		this( refArray, refArray.length, null );
	}


	/** Wraps a given array in a queue using the given comparators.
	 *
	 * <P>The queue returned by this method will be backed by the given array.
	 *
	 * @param refArray the reference array.
	 * @param a an array of indices into <code>refArray</code>.
	 * @param size the number of elements to be included in the queue.
	 * @param c the primary comparator used in this queue, or <code>null</code> for the natural order.
	 * @param d the secondary comparator used in this queue, or <code>null</code> for the natural order.
	 */
	public ARRAY_INDIRECT_DOUBLE_PRIORITY_QUEUE( final KEY_GENERIC_TYPE[] refArray, final int[] a, int size, final KEY_COMPARATOR KEY_SUPER_GENERIC c, final KEY_COMPARATOR KEY_SUPER_GENERIC d ) {
		this( refArray, 0, c, d );
		this.array = a;
		this.size = size;
	}

	/** Wraps a given array in a queue using the given comparators.
	 *
	 * <P>The queue returned by this method will be backed by the given array.
	 *
	 * @param refArray the reference array.
	 * @param a an array of indices into <code>refArray</code>.
	 * @param c the primary comparator used in this queue, or <code>null</code> for the natural order.
	 * @param d the secondary comparator used in this queue, or <code>null</code> for the natural order.
	 */
	public ARRAY_INDIRECT_DOUBLE_PRIORITY_QUEUE( final KEY_GENERIC_TYPE[] refArray, final int[] a, final KEY_COMPARATOR KEY_SUPER_GENERIC c, final KEY_COMPARATOR KEY_SUPER_GENERIC d ) {
		this( refArray, a, a.length, c, d );
	}


	/** Wraps a given array in a queue using a given comparator and its opposite.
	 *
	 * <P>The queue returned by this method will be backed by the given array.
	 *
	 * @param refArray the reference array.
	 * @param a an array of indices into <code>refArray</code>.
	 * @param size the number of elements to be included in the queue.
	 * @param c the comparator used in this queue, or <code>null</code> for the natural order.
	 */
	public ARRAY_INDIRECT_DOUBLE_PRIORITY_QUEUE( final KEY_GENERIC_TYPE[] refArray, final int[] a, int size, final KEY_COMPARATOR KEY_SUPER_GENERIC c ) {
		this( refArray, 0, c );
		this.array = a;
		this.size = size;
	}


	/** Wraps a given array in a queue using a given comparator and its opposite.
	 *
	 * <P>The queue returned by this method will be backed by the given array.
	 *
	 * @param refArray the reference array.
	 * @param a an array of indices into <code>refArray</code>.
	 * @param c the comparator used in this queue, or <code>null</code> for the natural order.
	 */
	public ARRAY_INDIRECT_DOUBLE_PRIORITY_QUEUE( final KEY_GENERIC_TYPE[] refArray, final int[] a, final KEY_COMPARATOR KEY_SUPER_GENERIC c ) {
		this( refArray, a, a.length, c );
	}

	/** Wraps a given array in a queue using the natural order and its opposite.
	 *
	 * <P>The queue returned by this method will be backed by the given array.
	 *
	 * @param refArray the reference array.
	 * @param a an array of indices into <code>refArray</code>.
	 * @param size the number of elements to be included in the queue.
	 */
	public ARRAY_INDIRECT_DOUBLE_PRIORITY_QUEUE( final KEY_GENERIC_TYPE[] refArray, final int[] a, int size ) {
		this( refArray, a, size, null );
	}


	/** Wraps a given array in a queue using the natural order and its opposite.
	 *
	 * <P>The queue returned by this method will be backed by the given array.
	 *
	 * @param refArray the reference array.
	 * @param a an array of indices into <code>refArray</code>.
	 */
	public ARRAY_INDIRECT_DOUBLE_PRIORITY_QUEUE( final KEY_GENERIC_TYPE[] refArray, final int[] a ) {
		this( refArray, a, a.length );
	}

	/** Returns the index (in {@link #array}) of the smallest element w.r.t. the {@linkplain #secondaryComparator secondary comparator}. */

	@SuppressWarnings("unchecked")
	private int findSecondaryFirst() {
		int i = size;
		int firstIndex = --i;
		KEY_GENERIC_TYPE first = refArray[ array[ firstIndex ] ];

		if ( secondaryComparator == null ) while( i-- != 0 ) { if ( KEY_LESS( refArray[ array[ i ] ], first ) ) first = refArray[ array[ firstIndex = i ] ]; }
		else while( i-- != 0 ) { if ( secondaryComparator.compare( refArray[ array[ i ] ], first ) < 0 ) first = refArray[ array[ firstIndex = i ] ]; }

		return firstIndex;
	}

	@SuppressWarnings("unchecked")
	private int findSecondaryLast() {
		int i = size;
		int lastIndex = --i;
		KEY_GENERIC_TYPE last = refArray[ array[ lastIndex ] ];

		if ( secondaryComparator == null ) while( i-- != 0 ) { if ( KEY_LESS( last, refArray[ array[ i ] ] ) ) last = refArray[ array[ lastIndex = i ] ]; }
		else while( i-- != 0 ) { if ( secondaryComparator.compare( last, refArray[ array[ i ] ] ) < 0 ) last = refArray[ array[ lastIndex = i ] ]; }

		return lastIndex;
	}


	public int secondaryFirst() {
		return array[ findSecondaryFirst() ];
	}


	public int secondaryLast() {
		return array[ findSecondaryLast() ];
	}

	public int secondaryFront( int[] a ) {
		final KEY_GENERIC_TYPE secondaryTop = refArray[ array[ findSecondaryFirst() ] ];
		int i = size, c = 0;
		while( i-- != 0 ) if ( KEY_EQUALS_NOT_NULL( secondaryTop, refArray[ array[ i ] ] ) ) a[ c++ ] = array[ i ];
		return c;
	}

	public void changed( int i ) {}

	/** Returns the secondary comparator of this queue.
	 *
	 * @return the secondary comparator of this queue.
	 * @see #secondaryFirst()
	 */
	public KEY_COMPARATOR KEY_SUPER_GENERIC secondaryComparator() { return secondaryComparator; }

#ifdef TEST

	/** The original class, now just used for testing. */

	private static class TestQueue {

		/** The reference array */
		private KEY_TYPE refArray[];
		/** Its length */
		private int N;
		/** The number of elements in the heaps */
		private int n;
		/** The two comparators */
		private KEY_COMPARATOR primaryComp, secondaryComp;
		/** Two indirect heaps are used, called <code>primary</code> and <code>secondary</code>. Each of them contains
			a permutation of <code>n</code> among the indices 0, 1, ..., <code>N</code>-1 in such a way that the corresponding
			objects be sorted with respect to the two comparators.
			We also need an array <code>inSec[]</code> so that <code>inSec[k]</code> is the index of <code>secondary</code> 
			containing <code>k</code>.
		*/
		private int primary[], secondary[], inSec[];

		/** Builds a double indirect priority queue.
		 *  @param refArray The reference array.
		 *  @param primaryComp The primary comparator.
		 *  @param secondaryComp The secondary comparator.
		 */
		public TestQueue( KEY_TYPE refArray[], KEY_COMPARATOR primaryComp, KEY_COMPARATOR secondaryComp ) {
			this.refArray = refArray;
			this.N = refArray.length;
			assert this.N != 0;
			this.n = 0;
			this.primaryComp = primaryComp;
			this.secondaryComp = secondaryComp;
			this.primary = new int[N];
			this.secondary = new int[N];
			this.inSec = new int[N];
			java.util.Arrays.fill( inSec, -1 );
		}

		/** Adds an index to the queue. Notice that the index should not be already present in the queue.
		 *  @param i The index to be added
		 */
		public void add( int i ) {
			if ( i < 0 || i >= refArray.length ) throw new IndexOutOfBoundsException();
			if ( inSec[ i ] >= 0 ) throw new IllegalArgumentException();
			primary[n] = i;
			secondary[n] = i; inSec[i] = n;
			n++;
			swimPrimary( n-1 );
			swimSecondary( n-1 );
		}

		/** Heapify the primary heap.
		 *  @param i The index of the heap to be heapified.
		 */
		private void heapifyPrimary( int i ) {
			int dep = primary[i];
			int child;

			while ( ( child = 2*i+1 ) < n ) {
				if ( child+1 < n && primaryComp.compare( refArray[primary[child+1]], refArray[primary[child]] ) < 0 ) child++;
				if ( primaryComp.compare( refArray[dep], refArray[primary[child]] ) <= 0 ) break;
				primary[i] = primary[child];
				i = child;
			}
			primary[i] = dep;
		}

		/** Heapify the secondary heap.
		 *  @param i The index of the heap to be heapified.
		 */
		private void heapifySecondary( int i ) {
			int dep = secondary[i];
			int child;

			while ( ( child = 2*i+1 ) < n ) {
				if ( child+1 < n && secondaryComp.compare( refArray[secondary[child+1]], refArray[secondary[child]] ) < 0 ) child++;
				if ( secondaryComp.compare( refArray[dep], refArray[secondary[child]] ) <= 0 ) break;
				secondary[i] = secondary[child]; inSec[secondary[i]] = i;
				i = child;
			}
			secondary[i] = dep; inSec[secondary[i]] = i;
		}

		/** Swim and heapify the primary heap.
		 *  @param i The index to be moved.
		 */
		private void swimPrimary( int i ) {
			int dep = primary[i];
			int parent;

			while ( i != 0 && ( parent = ( i - 1 ) / 2 ) >= 0 ) {
				if ( primaryComp.compare( refArray[primary[parent]], refArray[dep] ) <= 0 ) break;
				primary[i] = primary[parent];
				i = parent;
			}
			primary[i] = dep;
			heapifyPrimary( i );
		}

		/** Swim and heapify the secondary heap.
		 *  @param i The index to be moved.
		 */
		private void swimSecondary( int i ) {
			int dep = secondary[i];
			int parent;

			while ( i != 0 && ( parent = ( i - 1 ) / 2 ) >= 0 ) {
				if ( secondaryComp.compare( refArray[secondary[parent]], refArray[dep] ) <= 0 ) break;
				secondary[i] = secondary[parent]; inSec[secondary[i]] = i;
				i = parent;
			}
			secondary[i] = dep; inSec[secondary[i]] = i;
			heapifySecondary( i );
		}

		/** Returns the minimum element with respect to the primary comparator.
			@return the minimum element.
		*/
		public int top() {
			if ( n == 0 ) throw new java.util.NoSuchElementException();
			return primary[0];
		}

		/** Returns the minimum element with respect to the secondary comparator.
			@return the minimum element.
		*/
		public int secTop() {
			if ( n == 0 ) throw new java.util.NoSuchElementException();
			return secondary[0];
		}

		/** Removes the minimum element with respect to the primary comparator.
		 *  @return the removed element.
		 */
		public void remove() {
			if ( n == 0 ) throw new java.util.NoSuchElementException();
			int result = primary[0];
			int ins = inSec[result];
			inSec[ result ] = -1;
			// Copy a leaf 
			primary[0] = primary[n-1];
			if ( ins == n-1 ) {
				n--;
				heapifyPrimary( 0 );	
				return;
			}
			secondary[ins] = secondary[n-1]; 
			inSec[secondary[ins]] = ins;
			// Heapify
			n--;
			heapifyPrimary( 0 );
			swimSecondary( ins );
		}

		public void clear() {
			while( size() != 0 ) remove();
		}

		public void remove( int index ) {
			if ( n == 0 ) throw new java.util.NoSuchElementException();
			int result = primary[index];
			int ins = inSec[result];
			inSec[ result ] = -1;
			// Copy a leaf 
			primary[index] = primary[n-1];
			if ( ins == n-1 ) {
				n--;
				swimPrimary( index );	
				return;
			}
			secondary[ins] = secondary[n-1]; 
			inSec[secondary[ins]] = ins;
			// Heapify
			n--;
			swimPrimary( index );
			swimSecondary( ins );
		}

		/** Signals that the minimum element with respect to the comparator has changed.
		 */
		public void change() {
			int ins = inSec[primary[0]];
			heapifyPrimary( 0 );
			swimSecondary( ins );
		}

		public void change(int index) {
			int ins = inSec[primary[index]];
			swimPrimary( index );
			swimSecondary( ins );
		}

		/** Returns the number of elements in the queue.
		 *  @return the size of the queue
		 */
		public int size() {
			return n;
		}
	}


	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 boolean heapEqual( int[] a, int[] b, int sizea, int sizeb ) {
		if ( sizea != sizeb ) return false;
		while( sizea-- != 0 ) if ( a[sizea] != b[sizea] ) return false;
		return true;
	}

	private static boolean invEqual( int inva[], int[] invb ) {
		int i = inva.length;
		while( i-- != 0 ) if ( inva[ i ] != invb[ i ] ) return false;
		return true;
	}



	protected static void test( int n ) {
		long ms;
		Exception mThrowsIllegal, tThrowsIllegal, mThrowsOutOfBounds, tThrowsOutOfBounds, mThrowsNoElement, tThrowsNoElement;
		int rm = 0, rt = 0;
		KEY_TYPE[] refArray = new KEY_TYPE[ n ];

		for( int i = 0; i < n; i++ ) refArray[ i ] = genKey();
		  
		HEAP_SESQUI_INDIRECT_DOUBLE_PRIORITY_QUEUE m = new HEAP_SESQUI_INDIRECT_DOUBLE_PRIORITY_QUEUE( refArray );
		TestQueue t = new TestQueue( refArray, COMPARATORS.NATURAL_COMPARATOR, COMPARATORS.OPPOSITE_COMPARATOR );

		/* We add pairs to t. */
		for( int i = 0; i < n / 2;  i++ ) {
			t.add( i );
			m.enqueue( i );
		}
		
		ensure( heapEqual( m.heap, t.primary, m.size(), t.size() ), "Error (" + seed + "): m and t differ in primary heap after creation (" + m + ", " + t + ")" );
		ensure( heapEqual( m.secondaryQueue.heap, t.secondary, m.size(), t.size() ), "Error (" + seed + "): m and t differ in secondary heap after creation (" + m + ", " + t + ")" );
		ensure( invEqual( m.secondaryQueue.inv, t.inSec ), "Error (" + seed + "): m and t differ in inversion arrays after creation (" + java.util.Arrays.toString( m.secondaryQueue.inv ) + ", " + java.util.Arrays.toString( t.inSec ) + ")" );

		/* 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++ ) {
			if ( r.nextDouble() < 0.01 ) {
				t.clear();
				m.clear();
				for( int j = 0; j < n / 2;  j++ ) {
					t.add( j );
					m.enqueue( j );
				}
			}

			int T = r.nextInt( 2 * n );

			mThrowsNoElement = tThrowsNoElement = mThrowsOutOfBounds = tThrowsOutOfBounds = mThrowsIllegal = tThrowsIllegal = null;

			try {
				m.enqueue( T );
			}
			catch ( IndexOutOfBoundsException e ) { mThrowsOutOfBounds = e; }
			catch ( IllegalArgumentException e ) { mThrowsIllegal = e; }

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

			ensure( ( mThrowsOutOfBounds == null ) == ( tThrowsOutOfBounds == null ), "Error (" + seed + "): enqueue() divergence in IndexOutOfBoundsException for " + T + " (" + mThrowsOutOfBounds + ", " + tThrowsOutOfBounds + ")" );
			ensure( ( mThrowsIllegal == null ) == ( tThrowsIllegal == null ), "Error (" + seed + "): enqueue() divergence in IllegalArgumentException for " + T + " (" + mThrowsIllegal + ", " + tThrowsIllegal + ")" );

			ensure( heapEqual( m.heap, t.primary, m.size(), t.size() ), "Error (" + seed + "): m and t differ in primary heap after enqueue (" + m + ", " + t + ")" );
			ensure( heapEqual( m.secondaryQueue.heap, t.secondary, m.size(), t.size() ), "Error (" + seed + "): m and t differ in secondary heap after enqueue (" + m + ", " + t + ")" );
			ensure( invEqual( m.secondaryQueue.inv, t.inSec ), "Error (" + seed + "): m and t differ in inversion arrays after enqueue (" + java.util.Arrays.toString( m.secondaryQueue.inv ) + ", " + java.util.Arrays.toString( t.inSec ) + ")" );
			
			if ( m.size() != 0 ) {
				ensure( m.first() == t.top(), "Error (" + seed + "): m and t differ in first element after enqueue (" + m.first() + ", " + t.top() + ")");
				ensure( m.secondaryFirst() == t.secTop(), "Error (" + seed + "): m and t differ in secondary first element after enqueue (" + m.secondaryFirst() + ", " + t.secTop() + ")");
			}


			mThrowsNoElement = tThrowsNoElement = mThrowsOutOfBounds = tThrowsOutOfBounds = mThrowsIllegal = tThrowsIllegal = null;

			try {
				rm = m.dequeue();
			}
			catch ( IndexOutOfBoundsException e ) { mThrowsOutOfBounds = e; }
			catch ( IllegalArgumentException e ) { mThrowsIllegal = e; }
			catch ( java.util.NoSuchElementException e ) { mThrowsNoElement = e; }

			try {
				rt = t.top();
				t.remove();
			}
			catch ( IndexOutOfBoundsException e ) { tThrowsOutOfBounds = e; }
			catch ( IllegalArgumentException e ) { tThrowsIllegal = e; }
			catch ( java.util.NoSuchElementException e ) { tThrowsNoElement = e; }

			ensure( ( mThrowsOutOfBounds == null ) == ( tThrowsOutOfBounds == null ), "Error (" + seed + "): dequeue() divergence in IndexOutOfBoundsException (" + mThrowsOutOfBounds + ", " + tThrowsOutOfBounds + ")" );
			ensure( ( mThrowsIllegal == null ) == ( tThrowsIllegal == null ), "Error (" + seed + "): dequeue() divergence in IllegalArgumentException  (" + mThrowsIllegal + ", " + tThrowsIllegal + ")" );
			ensure( ( mThrowsNoElement == null ) == ( tThrowsNoElement == null ), "Error (" + seed + "): dequeue() divergence in java.util.NoSuchElementException  (" + mThrowsNoElement + ", " + tThrowsNoElement + ")" );
			if ( mThrowsOutOfBounds == null ) ensure( rt == rm , "Error (" + seed + "): divergence in dequeue() between t and m (" + rt + ", " + rm + ")" );

			ensure( heapEqual( m.heap, t.primary, m.size(), t.size() ), "Error (" + seed + "): m and t differ in primary heap after dequeue (" + m + ", " + t + ")" );
			ensure( heapEqual( m.secondaryQueue.heap, t.secondary, m.size(), t.size() ), "Error (" + seed + "): m and t differ in secondary heap after dequeue (" + m + ", " + t + ")" );
			ensure( invEqual( m.secondaryQueue.inv, t.inSec ), "Error (" + seed + "): m and t differ in inversion arrays after dequeue (" + java.util.Arrays.toString( m.secondaryQueue.inv ) + ", " + java.util.Arrays.toString( t.inSec ) + ")" );

			if ( m.size() != 0 ) {
				ensure( m.first() == t.top(), "Error (" + seed + "): m and t differ in first element after dequeue (" + m.first() + ", " + t.top() + ")");
				ensure( m.secondaryFirst() == t.secTop(), "Error (" + seed + "): m and t differ in secondary first element after dequeue (" + m.secondaryFirst() + ", " + t.secTop() + ")");
			}

			if ( m.size() != 0 ) {

				refArray[ m.first() ] = genKey();
				
				m.changed();
				t.change();
				
				ensure( m.size() == t.size(), "Error (" + seed + "): m and t differ in size after change (" + m.size() + ", " + t.size() + ")");
				
				ensure( m.first() == t.top(), "Error (" + seed + "): m and t differ in first element after change (" + m.first() + ", " + t.top() + ")");
				ensure( m.secondaryFirst() == t.secTop(), "Error (" + seed + "): m and t differ in secondary first element after change (" + m.secondaryFirst() + ", " + t.secTop() + ")");
			}
		}


		/* Now we check that m actually holds the same data. */
		  
		m.clear();
		ensure( m.isEmpty(), "Error (" + seed + "): m is not empty after clear()" );

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



	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

}