/*
 * Copyright (C) 2003-2024 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 KEY_CLASS_Object
import java.util.Comparator;
#endif

#if ! KEY_CLASS_Integer
import it.unimi.dsi.fastutil.ints.IntArrays;
#endif

import java.util.Arrays;
import java.util.NoSuchElementException;

/** A type-specific heap-based indirect priority queue.
 *
 * <p>Instances of this class use an additional <em>inversion array</em>, of the same length of the reference array,
 * to keep track of the heap position containing a given element of the reference array. The priority queue is
 * represented using a heap. The heap is enlarged as needed, but it is never
 * shrunk. Use the {@link #trim()} method to reduce its size, if necessary.
 *
 * @implSpec This implementation does <em>not</em> allow one to enqueue several times the same index.
 */

public class HEAP_INDIRECT_PRIORITY_QUEUE KEY_GENERIC extends HEAP_SEMI_INDIRECT_PRIORITY_QUEUE KEY_GENERIC {

	/** The inversion array. */
	protected final int inv[];

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

		this.inv = new int[refArray.length];
		Arrays.fill(inv, -1);
	}

	/** Creates a new empty queue with a given capacity and using the natural order.
	 *
	 * @param refArray the reference array.
	 * @param capacity the initial capacity of this queue.
	 */
	public HEAP_INDIRECT_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 and a given comparator.
	 *
	 * @param refArray the reference array.
	 * @param c the comparator used in this queue, or {@code null} for the natural order.
	 */
	public HEAP_INDIRECT_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 using the natural order.
	 * @param refArray the reference array.
	 */
	public HEAP_INDIRECT_PRIORITY_QUEUE(KEY_GENERIC_TYPE[] refArray) {
		this(refArray, refArray.length, null);
	}


	/** Wraps a given array in a queue using a given comparator.
	 *
	 * <p>The queue returned by this method will be backed by the given array.
	 * The first {@code size} element of the array will be rearranged so to form a heap (this is
	 * more efficient than enqueing the elements of {@code a} one by one).
	 *
	 * @param refArray the reference array.
	 * @param a an array of indices into {@code refArray}.
	 * @param size the number of elements to be included in the queue.
	 * @param c the comparator used in this queue, or {@code null} for the natural order.
	 */
	public HEAP_INDIRECT_PRIORITY_QUEUE(final KEY_GENERIC_TYPE[] refArray, final int[] a, final int size, final KEY_COMPARATOR KEY_SUPER_GENERIC c) {
		this(refArray, 0, c);
		this.heap = a;
		this.size = size;
		int i = size;
		while(i-- != 0) {
			if (inv[a[i]] != -1) throw new IllegalArgumentException("Index " + a[i] + " appears twice in the heap");
			inv[a[i]] = i;
		}
		INDIRECT_HEAPS.makeHeap(refArray, a, inv, size, c);
	}


	/** Wraps a given array in a queue using a given comparator.
	 *
	 * <p>The queue returned by this method will be backed by the given array.
	 * The elements of the array will be rearranged so to form a heap (this is
	 * more efficient than enqueing the elements of {@code a} one by one).
	 *
	 * @param refArray the reference array.
	 * @param a an array of indices into {@code refArray}.
	 * @param c the comparator used in this queue, or {@code null} for the natural order.
	 */
	public HEAP_INDIRECT_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.
	 *
	 * <p>The queue returned by this method will be backed by the given array.
	 * The first {@code size} element of the array will be rearranged so to form a heap (this is
	 * more efficient than enqueing the elements of {@code a} one by one).
	 *
	 * @param refArray the reference array.
	 * @param a an array of indices into {@code refArray}.
	 * @param size the number of elements to be included in the queue.
	 */
	public HEAP_INDIRECT_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.
	 *
	 * <p>The queue returned by this method will be backed by the given array.
	 * The elements of the array will be rearranged so to form a heap (this is
	 * more efficient than enqueing the elements of {@code a} one by one).
	 *
	 * @param refArray the reference array.
	 * @param a an array of indices into {@code refArray}.
	 */
	public HEAP_INDIRECT_PRIORITY_QUEUE(final KEY_GENERIC_TYPE[] refArray, final int[] a) {
		this(refArray, a, a.length);
	}

	@Override
	public void enqueue(final int x) {
		if (inv[x] >= 0) throw new IllegalArgumentException("Index " + x + " belongs to the queue");

		if (size == heap.length) heap = IntArrays.grow(heap, size + 1);

		inv[heap[size] = x] = size++;

		INDIRECT_HEAPS.upHeap(refArray, heap, inv, size, size - 1, c);
	}

	@Override
	public boolean contains(final int index) {
		return inv[index] >= 0;
	}

	@Override
	public int dequeue() {
		if (size == 0) throw new NoSuchElementException();
		final int result = heap[0];
		if (--size != 0) inv[heap[0] = heap[size]] = 0;
		inv[result] = -1;

		if (size != 0) INDIRECT_HEAPS.downHeap(refArray, heap, inv, size, 0, c);
		return result;
	}

	@Override
	public void changed() {
		INDIRECT_HEAPS.downHeap(refArray, heap, inv, size, 0, c);
	}

	@Override
	public void changed(final int index) {
		final int pos = inv[index];
		if (pos < 0) throw new IllegalArgumentException("Index " + index + " does not belong to the queue");
		final int newPos = INDIRECT_HEAPS.upHeap(refArray, heap, inv, size, pos, c);
		INDIRECT_HEAPS.downHeap(refArray, heap, inv, size, newPos, c);
	}

	/** Rebuilds this queue in a bottom-up fashion (in linear time). */
	@Override
	public void allChanged() { INDIRECT_HEAPS.makeHeap(refArray, heap, inv, size, c); }

	@Override
	public boolean remove(final int index) {
		final int result = inv[index];
		if (result < 0) return false;
		inv[index] = -1;

		if (result < --size) {
			inv[heap[result] = heap[size]] = result;
			final int newPos = INDIRECT_HEAPS.upHeap(refArray, heap, inv, size, result, c);
			INDIRECT_HEAPS.downHeap(refArray, heap, inv, size, newPos, c);
		}

		return true;
	}

	@Override
	public void clear() {
		size = 0;
		Arrays.fill(inv, -1);
	}

#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} and {@code secondary}. Each of them contains
			a permutation of {@code n} among the indices 0, 1, ..., {@code N}-1 in such a way that the corresponding
			objects be sorted with respect to the two comparators.
			We also need an array {@code inSec[]} so that {@code inSec[k]} is the index of {@code secondary}
			containing {@code k}.
		*/
		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 boolean remove() {
			if (n == 0) throw new java.util.NoSuchElementException();
			if (inSec[primary[0]] == -1) return false;
			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 true;
			}
			secondary[ins] = secondary[n-1];
			inSec[secondary[ins]] = ins;
			// Heapify
			n--;
			heapifyPrimary(0);
			swimSecondary(ins);
			return true;
		}

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

		public void remove(int index) {
			if (index >= refArray.length) throw new IndexOutOfBoundsException();
			if (inSec[index] == -1) return;
			int ins = inSec[index];
			inSec[index] = -1;
			// Copy a leaf
			primary[ins] = primary[n-1];
			if (ins == n-1) {
				n--;
				swimPrimary(ins);
				return;
			}
			secondary[ins] = secondary[n-1];
			inSec[secondary[ins]] = ins;
			// Heapify
			n--;
			swimPrimary(ins);
			swimSecondary(ins);
		}

		/** Signals that the minimum element with respect to the comparator has changed.
		 */
		public void change() {
			if (n == 0) throw new java.util.NoSuchElementException();
			if (inSec[primary[0]] == -1) throw new IllegalArgumentException();
			int ins = inSec[primary[0]];
			heapifyPrimary(0);
			swimSecondary(ins);
		}

		public void change(int index) {
			if (index >= refArray.length) throw new IndexOutOfBoundsException();
			if (inSec[index] == -1) throw new IllegalArgumentException();
			if (n == 0) throw new java.util.NoSuchElementException();
			int ins = inSec[index];
			swimPrimary(ins);
			swimSecondary(ins);
		}

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



		public String toString() {
			String s = "[";
			for (int i = 0; i < n; i++)
				s += refArray[primary[i]]+", ";
			return s+ "]";
		}
	}

	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 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 runTest(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_INDIRECT_PRIORITY_QUEUE m = new HEAP_INDIRECT_PRIORITY_QUEUE(refArray, COMPARATORS.NATURAL_COMPARATOR);
		TestQueue t = new TestQueue(refArray, COMPARATORS.NATURAL_COMPARATOR, COMPARATORS.NATURAL_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 after creation (" + m + ", " + t + ")");
		ensure(invEqual(m.inv, t.inSec), "Error (" + seed + "): m and t differ in inversion arrays after creation (" + java.util.Arrays.toString(m.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 after enqueue (" + m + ", " + t + ")");
			ensure(invEqual(m.inv, t.inSec), "Error (" + seed + "): m and t differ in inversion arrays after enqueue (" + java.util.Arrays.toString(m.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() + ")");
			}

			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 after dequeue (" + m + ", " + t + ")");
			ensure(invEqual(m.inv, t.inSec), "Error (" + seed + "): m and t differ in inversion arrays after dequeue (" + java.util.Arrays.toString(m.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() + ")");
			}


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

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

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

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

			ensure(heapEqual(m.heap, t.primary, m.size(), t.size()), "Error (" + seed + "): m and t differ after remove(int) (" + m + ", " + t + ")");
			ensure(invEqual(m.inv, t.inSec), "Error (" + seed + "): m and t differ in inversion arrays after remove(int) (" + java.util.Arrays.toString(m.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 remove(int) (" + m.first() + ", " + t.top() + ")");
			}


			pos = r.nextInt(n * 2);

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

			try {
				t.change(pos);
			}
			catch (IndexOutOfBoundsException e) { tThrowsOutOfBounds = e; }
			catch (IllegalArgumentException e) { tThrowsIllegal = e; }
			catch (java.util.NoSuchElementException e) { tThrowsNoElement = e; }

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

			ensure(heapEqual(m.heap, t.primary, m.size(), t.size()), "Error (" + seed + "): m and t differ after change(int) (" + m + ", " + t + ")");
			ensure(invEqual(m.inv, t.inSec), "Error (" + seed + "): m and t differ in inversion arrays after change(int) (" + java.util.Arrays.toString(m.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 change(int) (" + m.first() + ", " + t.top() + ")");
			}

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

				refArray[m.first()] = genKey();

				m.changed();
				t.change();

				ensure(heapEqual(m.heap, t.primary, m.size(), t.size()), "Error (" + seed + "): m and t differ after change (" + m + ", " + t + ")");
				ensure(invEqual(m.inv, t.inSec), "Error (" + seed + "): m and t differ in inversion arrays after change (" + java.util.Arrays.toString(m.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 change (" + m.first() + ", " + t.top() + ")");
				}
			}
		}


		/* 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[]) 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

}