/*
 * 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.Arrays;
import java.util.Comparator;

import it.unimi.dsi.fastutil.PriorityQueue;
#else
import java.util.Iterator;
#endif

import java.util.Collection;
import java.util.NoSuchElementException;


/** A type-specific heap-based priority queue.
 *
 * <p>Instances of this class represent a priority queue 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.
 */

public class HEAP_PRIORITY_QUEUE KEY_GENERIC implements PRIORITY_QUEUE KEY_GENERIC, java.io.Serializable {
	private static final long serialVersionUID = 1L;

	/** The heap array. */
	SUPPRESS_WARNINGS_KEY_UNCHECKED
	protected transient KEY_GENERIC_TYPE[] heap = KEY_GENERIC_ARRAY_CAST ARRAYS.EMPTY_ARRAY;

	/** The number of elements in this queue. */
	protected int size;

	/** The type-specific comparator used in this queue. */
	protected KEY_COMPARATOR KEY_SUPER_GENERIC c;

	/** Creates a new empty queue with a given capacity and comparator.
	 *
	 * @param capacity the initial capacity of this queue.
	 * @param c the comparator used in this queue, or {@code null} for the natural order.
	 */
	SUPPRESS_WARNINGS_KEY_UNCHECKED
	public HEAP_PRIORITY_QUEUE(int capacity, KEY_COMPARATOR KEY_SUPER_GENERIC c) {
		if (capacity > 0) this.heap = KEY_GENERIC_ARRAY_CAST new KEY_TYPE[capacity];
		this.c = c;
	}

	/** Creates a new empty queue with a given capacity and using the natural order.
	 *
	 * @param capacity the initial capacity of this queue.
	 */
	public HEAP_PRIORITY_QUEUE(int capacity) {
		this(capacity, null);
	}

	/** Creates a new empty queue with a given comparator.
	 *
	 * @param c the comparator used in this queue, or {@code null} for the natural order.
	 */
	public HEAP_PRIORITY_QUEUE(KEY_COMPARATOR KEY_SUPER_GENERIC c) {
		this(0, c);
	}

	/** Creates a new empty queue using the natural order.
	 */
	public HEAP_PRIORITY_QUEUE() {
		this(0, 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 a an array.
	 * @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_PRIORITY_QUEUE(final KEY_GENERIC_TYPE[] a, int size, final KEY_COMPARATOR KEY_SUPER_GENERIC c) {
		this(c);
		this.heap = a;
		this.size = size;
		HEAPS.makeHeap(a, 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 a an array.
	 * @param c the comparator used in this queue, or {@code null} for the natural order.
	 */
	public HEAP_PRIORITY_QUEUE(final KEY_GENERIC_TYPE[] a, final KEY_COMPARATOR KEY_SUPER_GENERIC c) {
		this(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 a an array.
	 * @param size the number of elements to be included in the queue.
	 */
	public HEAP_PRIORITY_QUEUE(final KEY_GENERIC_TYPE[] a, int size) {
		this(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 a an array.
	 */
	public HEAP_PRIORITY_QUEUE(final KEY_GENERIC_TYPE[] a) {
		this(a, a.length);
	}

#if KEYS_PRIMITIVE

	/** Creates a queue using the elements in a type-specific collection using a given comparator.
	 *
	 * <p>This constructor is more efficient than enqueing the elements of {@code collection} one by one.
	 *
	 * @param collection a collection; its elements will be used to initialize the queue.
	 * @param c the comparator used in this queue, or {@code null} for the natural order.
	 */
	public HEAP_PRIORITY_QUEUE(final COLLECTION KEY_EXTENDS_GENERIC collection, final KEY_COMPARATOR KEY_SUPER_GENERIC c) {
		this(collection.TO_KEY_ARRAY(), c);
	}

	/** Creates a queue using the elements in a type-specific collection using the natural order.
	 *
	 * <p>This constructor is
	 * more efficient than enqueing the elements of {@code collection} one by one.
	 *
	 * @param collection a collection; its elements will be used to initialize the queue.
	 */
	public HEAP_PRIORITY_QUEUE(final COLLECTION KEY_EXTENDS_GENERIC collection) {
		this(collection, null);
	}

	/** Creates a queue using the elements in a collection using a given comparator.
	 *
	 * <p>This constructor is more efficient than enqueing the elements of {@code collection} one by one.
	 *
	 * @param collection a collection; its elements will be used to initialize the queue.
	 * @param c the comparator used in this queue, or {@code null} for the natural order.
	 */
	public HEAP_PRIORITY_QUEUE(final Collection<? extends KEY_GENERIC_CLASS> collection, final KEY_COMPARATOR KEY_SUPER_GENERIC c) {
		this(collection.size(), c);
		final Iterator<? extends KEY_GENERIC_CLASS> iterator = collection.iterator();
		final int size = collection.size();
		for(int i = 0 ; i < size; i++) heap[i] = KEY_OBJ2TYPE(iterator.next());
	}

	/** Creates a queue using the elements in a collection using the natural order.
	 *
	 * <p>This constructor is
	 * more efficient than enqueing the elements of {@code collection} one by one.
	 *
	 * @param collection a collection; its elements will be used to initialize the queue.
	 */
	public HEAP_PRIORITY_QUEUE(final Collection<? extends KEY_GENERIC_CLASS> collection) {
		this(collection, null);
	}
#else
	/** Creates a queue using the elements in a collection using a given comparator.
	 *
	 * <p>This constructor is more efficient than enqueing the elements of {@code collection} one by one.
	 *
	 * @param collection a collection; its elements will be used to initialize the queue.
	 * @param c the comparator used in this queue, or {@code null} for the natural order.
	 */
	SUPPRESS_WARNINGS_KEY_UNCHECKED
	public HEAP_PRIORITY_QUEUE(final Collection<? extends KEY_GENERIC_CLASS> collection, final KEY_COMPARATOR KEY_SUPER_GENERIC c) {
		this(KEY_GENERIC_ARRAY_CAST collection.toArray(), c);
	}

	/** Creates a queue using the elements in a collection using the natural order.
	 *
	 * <p>This constructor is
	 * more efficient than enqueing the elements of {@code collection} one by one.
	 *
	 * @param collection a collection; its elements will be used to initialize the queue.
	 */
	public HEAP_PRIORITY_QUEUE(final Collection<? extends KEY_GENERIC_CLASS> collection) {
		this(collection, null);
	}
#endif

	@Override
		public void enqueue(KEY_GENERIC_TYPE x) {
		if (size == heap.length) heap = ARRAYS.grow(heap, size + 1);

		heap[size++] = x;
		HEAPS.upHeap(heap, size, size - 1, c);
	}

	@Override
	public KEY_GENERIC_TYPE DEQUEUE() {
		if (size == 0) throw new NoSuchElementException();

		final KEY_GENERIC_TYPE result = heap[0];
		heap[0] = heap[--size];
#if KEY_CLASS_Object
		heap[size] = null;
#endif
		if (size != 0) HEAPS.downHeap(heap, size, 0, c);
		return result;
	}

	@Override
	public KEY_GENERIC_TYPE FIRST() {
		if (size == 0) throw new NoSuchElementException();
		return heap[0];
	}

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

	@Override
	public int size() { return size; }

	@Override
	public void clear() {
#if KEY_CLASS_Object
		Arrays.fill(heap, 0, size, null);
#endif
		size = 0;
	}

	/** Trims the underlying heap array so that it has exactly {@link #size()} elements. */

	public void trim() {
		heap = ARRAYS.trim(heap, size);
	}

	@Override
	public KEY_COMPARATOR KEY_SUPER_GENERIC comparator() { return c; }

	private void writeObject(java.io.ObjectOutputStream s) throws java.io.IOException {
		s.defaultWriteObject();
		s.writeInt(heap.length);
		final KEY_GENERIC_TYPE[] heap = this.heap;
		for(int i = 0; i < size; i++) s.WRITE_KEY(heap[i]);
	}

	SUPPRESS_WARNINGS_KEY_UNCHECKED
	private void readObject(java.io.ObjectInputStream s) throws java.io.IOException, ClassNotFoundException {
		s.defaultReadObject();
		final KEY_GENERIC_TYPE[] heap = this.heap = KEY_GENERIC_ARRAY_CAST new KEY_TYPE[s.readInt()];
		for(int i = 0; i < size; i++) heap[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 boolean heapEqual(KEY_TYPE[] a, KEY_TYPE[] b, int sizea, int sizeb) {
		if (sizea != sizeb) return false;
		KEY_TYPE[] aa = (KEY_TYPE[])a.clone();
		KEY_TYPE[] bb = (KEY_TYPE[])b.clone();
		java.util.Arrays.sort(aa, 0, sizea);
		java.util.Arrays.sort(bb, 0, sizeb);
		while(sizea-- != 0) if (! KEY_EQUALS(aa[sizea], bb[sizea])) return false;
		return true;
	}

	private static KEY_TYPE k[];

	protected static void runTest(int n) throws Exception {
		long ms;
		Exception mThrowsIllegal, tThrowsIllegal, mThrowsOutOfBounds, tThrowsOutOfBounds, mThrowsNoElement, tThrowsNoElement;
		KEY_TYPE rm = KEY_NULL, rt = KEY_NULL;
		k = new KEY_TYPE[n];

		for(int i = 0; i < n; i++) k[i] = genKey();

		HEAP_PRIORITY_QUEUE m = new HEAP_PRIORITY_QUEUE(COMPARATORS.NATURAL_COMPARATOR);
		ARRAY_PRIORITY_QUEUE t = new ARRAY_PRIORITY_QUEUE(COMPARATORS.NATURAL_COMPARATOR);

		/* We add pairs to t. */
		for(int i = 0; i < n / 2;  i++) {
			t.enqueue(k[i]);
			m.enqueue(k[i]);
		}

		ensure(heapEqual(m.heap, t.array, m.size(), t.size()), "Error (" + seed + "): m and t differ after creation (" + m + ", " + t + ")");

		if (m.size() != 0) {
			ensure(KEY_EQUALS(m.FIRST(), t.FIRST()), "Error (" + seed + "): m and t differ in first element after creation (" + m.FIRST() + ", " + t.FIRST() + ")");
		}

		/* 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.enqueue(k[j]);
					m.enqueue(k[j]);
				}
			}

			KEY_TYPE T = genKey();

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

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

			try {
				t.enqueue(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.array, m.size(), t.size()), "Error (" + seed + "): m and t differ after enqueue (" + m + ", " + t + ")");

			if (m.size() != 0) {
				ensure(KEY_EQUALS(m.FIRST(), t.FIRST()), "Error (" + seed + "): m and t differ in first element after enqueue (" + m.FIRST() + ", " + t.FIRST() + ")");
			}

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

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

			try {
				rt = t.DEQUEUE();
			}
			catch (IndexOutOfBoundsException e) { tThrowsOutOfBounds = e; }
			catch (IllegalArgumentException e) { tThrowsIllegal = e; }
			catch (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 NoSuchElementException  (" + mThrowsNoElement + ", " + tThrowsNoElement + ")");
			if (mThrowsOutOfBounds == null) ensure(KEY_EQUALS(rt, rm) , "Error (" + seed + "): divergence in dequeue() between t and m (" + rt + ", " + rm + ")");


			ensure(heapEqual(m.heap, t.array, m.size(), t.size()), "Error (" + seed + "): m and t differ after dequeue (" + m + ", " + t + ")");

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

			/* Now we save and read m. */

			{
				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);

				m = (HEAP_PRIORITY_QUEUE)ois.readObject();
				ois.close();
				ff.delete();
			}

			ensure(heapEqual(m.heap, t.array, m.size(), t.size()), "Error (" + seed + "): m and t differ after save/read");

			HEAP_PRIORITY_QUEUE m2 = new HEAP_PRIORITY_QUEUE(t.array, t.size());
			ARRAY_PRIORITY_QUEUE t2 = new ARRAY_PRIORITY_QUEUE(m.heap, m.size());
			m = m2;
			t = t2;

			ensure(heapEqual(m.heap, t.array, m.size(), t.size()), "Error (" + seed + "): m and t differ after wrap (" + m + ", " + t + ")");

			if (m.size() != 0) {
				ensure(KEY_EQUALS(m.FIRST(), t.FIRST()), "Error (" + seed + "): m and t differ in first element after wrap (" + m.FIRST() + ", " + t.FIRST() + ")");
			}

			if (m.size() != 0 && ((new OPEN_HASH_SET(m.heap, 0, m.size)).size() == m.size())) {

				int j = t.size(), M = --j;
#if KEYS_PRIMITIVE
				while(j-- != 0) if (KEY_LESS(t.array[j], t.array[M])) M = j;
#else
				while(j-- != 0) if (((Comparable)t.array[j]).compareTo(t.array[M])< 0) M = j;
#endif

				m.heap[0] = t.array[M] = genKey();

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

				ensure(heapEqual(m.heap, t.array, m.size(), t.size()), "Error (" + seed + "): m and t differ after change (" + m + ", " + t + ")");

				if (m.size() != 0) {
					ensure(KEY_EQUALS(m.FIRST(), t.FIRST()), "Error (" + seed + "): m and t differ in first element after change (" + m.FIRST() + ", " + t.FIRST() + ")");
				}
			}
		}


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

}