// Exercise 2.4.29
package algs24;
import stdlib.*;
import java.util.Iterator;
import java.util.NoSuchElementException;

// To turn on assertions for a program in eclipse,
// run the program once, then go to the menubar and select
//   Run > Run Configurations... > Arguments > VM Arguments
// And add
//   -ea
// As a VM argument
public class MyMinMaxPQ<K extends Comparable<? super K>> implements Iterable<K> {
	private int N;    // number of items on priority queue
	private int MAXN; // size of the the arrays
	private K[] a;  // minheap
	private K[] b;  // maxheap

	// the array ab maps from a to b
	// the array ba maps from b to a
	// they are inverses, so i == ba[ab[i]] == ab[ba[i]] for any i
	//
	private int[] ab; // index a to b: a[i] == b[ab[i]]
	private int[] ba; // index b to a: b[i] == a[ba[i]]


	@SuppressWarnings("unchecked")
	/** Create an empty priority queue with the given initial capacity, using the given comparator. */
	public MyMinMaxPQ (int capacity) {
		MAXN = capacity;
		a = (K[]) new Comparable[MAXN + 1];
		b = (K[]) new Comparable[MAXN + 1];
		ab = new int[MAXN + 1];
		ba = new int[MAXN + 1];
		N = 0;
	}

	/** Is the priority queue empty? */
	public boolean isEmpty () { return N == 0; }

	/** Is the priority queue full? */
	public boolean isFull () { return N == MAXN; }

	/** Return the number of items on the priority queue. */
	public int size () { return N; }

	/**
	 * Return the smallest key on the priority queue. Throw an exception if the
	 * priority queue is empty.
	 */
	public K min () {
		if (isEmpty ()) throw new Error ("Priority queue underflow");
		return a[1];
	}

	/** Add a new key to the priority queue. */
	public void insert (K x) {
		if (isFull ()) throw new Error ("Priority queue overflow");
		// add x, and percolate it up to maintain heap invariant
		N++;
		a[N] = x;
		b[N] = x;
		ab[N] = N;
		ba[N] = N;
		aSwim (N);
		bSwim (N);
		assert isMinMaxHeap ();
	}

	/**
	 * Delete and return the smallest key on the priority queue. Throw an
	 * exception if the priority queue is empty.
	 */
	public K delMin () {
		if (N == 0) throw new Error ("Priority queue underflow");
		// TODO
		assert isMinMaxHeap ();
		return null;
	}
	/**
	 * Delete and return the largest key on the priority queue. Throw an
	 * exception if the priority queue is empty.
	 */
	public K delMax () {
		if (N == 0) throw new Error ("Priority queue underflow");
		// TODO
		assert isMinMaxHeap ();
		return null;
	}

	/* *********************************************************************
	 * Helper functions to restore the heap invariant.
	 **********************************************************************/

	private void aSwim (int k) {
		while (k > 1 && aGreater (k / 2, k)) {
			aExch (k, k / 2);
			k = k / 2;
		}
	}
	private void aSink (int k) {
		while (2 * k <= N) {
			int j = 2 * k;
			if (j < N && aGreater (j, j + 1)) j++;
			if (!aGreater (k, j)) break;
			aExch (k, j);
			k = j;
		}
	}
	private void bSwim (int k) {
		while (k > 1 && bLess (k / 2, k)) {
			bExch (k, k / 2);
			k = k / 2;
		}
	}
	private void bSink (int k) {
		while (2 * k <= N) {
			int j = 2 * k;
			if (j < N && bLess (j, j + 1)) j++;
			if (!bLess (k, j)) break;
			bExch (k, j);
			k = j;
		}
	}

	/* *********************************************************************
	 * Helper functions for compares and swaps.
	 **********************************************************************/
	private boolean aGreater (int i, int j) {
		return a[i].compareTo (a[j]) > 0;
	}
	private boolean bLess (int i, int j) {
		return b[i].compareTo (b[j]) < 0;
	}
	private void swap (K[] a, int i, int j) {
		K tmp = a[i];
		a[i] = a[j];
		a[j] = tmp;
	}
	private void swap (int[] a, int i, int j) {
		int tmp = a[i];
		a[i] = a[j];
		a[j] = tmp;
	}
	private void aExch (int ai, int aj) {
		int bi = ab[ai];
		int bj = ab[aj];
		swap (a, ai, aj);
		swap (ab, ai, aj);
		swap (ba, bi, bj);
	}
	private void bExch (int bi, int bj) {
		int ai = ba[bi];
		int aj = ba[bj];
		swap (b, bi, bj);
		swap (ab, ai, aj);
		swap (ba, bi, bj);
	}

	private void showHeap () {
		StdOut.print ("a:  ");
		for (int i = 1; i <= N; i++)
			StdOut.print (a[i] + " ");
		StdOut.println ();
		StdOut.print ("b:  ");
		for (int i = 1; i <= N; i++)
			StdOut.print (b[i] + " ");
		StdOut.println ();
		/*
		 * StdOut.print ("ab: "); for (int i = 1; i <= N; i++) StdOut.print
		 * (ab[i] + " "); StdOut.println (); StdOut.print ("ba: "); for (int i =
		 * 1; i <= N; i++) StdOut.print (ba[i] + " "); StdOut.println ();
		 */
	}
	private void check () {
		for (int i = 1; i <= N; i++) {
			// a and b have the same data, mapped by ab and ba
			assert a[i] == b[ab[i]];
			assert b[i] == a[ba[i]];
			// ab and ba are inverses
			assert i == ab[ba[i]];
			assert i == ba[ab[i]];
		}
	}

	private boolean isMinMaxHeap () {
		check ();
		return isMaxHeap (1) && isMinHeap (1);
	}
	private boolean isMaxHeap (int k) {
		if (k > N) return true;
		int left = 2 * k, right = 2 * k + 1;
		if (left <= N && bLess (k, left))   { StdOut.format ("Not a max heap k=%d left=%d\n",  k, left);  showHeap(); return false; }
		if (right <= N && bLess (k, right)) { StdOut.format ("Not a max heap k=%d right=%d\n", k, right); showHeap(); return false; }
		return isMaxHeap (left) && isMaxHeap (right);
	}
	private boolean isMinHeap (int k) {
		if (k > N) return true;
		int left = 2 * k, right = 2 * k + 1;
		//StdOut.format ("checkmin: %s %s %s\n", a[k], a[left], a[right]);
		if (left <= N && aGreater (k, left))   { StdOut.format ("Not a min heap k=%d left=%d\n",  k, left);  showHeap(); return false; }
		if (right <= N && aGreater (k, right)) { StdOut.format ("Not a min heap k=%d right=%d\n", k, right); showHeap(); return false; }
		return isMinHeap (left) && isMinHeap (right);
	}


	/* *********************************************************************
	 * Iterator
	 **********************************************************************/

	/**
	 * Return an iterator that iterates over all of the keys on the priority
	 * queue in ascending order.
	 * <p>
	 * The iterator doesn't implement {@code remove()} since it's optional.
	 */
	public Iterator<K> iterator () { return new HeapIterator (); }
	private class HeapIterator implements Iterator<K> {
		// create a new pq
		private MyMinMaxPQ<K> copy;

		// add all items to copy of heap
		// takes linear time since already in heap order so no keys move
		public HeapIterator () {
			copy = new MyMinMaxPQ<> (size ());
			for (int i = 1; i <= N; i++)
				copy.insert (a[i]);
		}

		public boolean hasNext () { return !copy.isEmpty (); }
		public void remove () { throw new UnsupportedOperationException (); }
		public K next () {
			if (!hasNext ()) throw new NoSuchElementException ();
			return copy.delMin ();
		}
	}

	/**
	 * A test client.
	 */
	private static int randomValue () { return StdRandom.uniform (100); }
	private static MyMinMaxPQ<Integer> randomPQ (int maxSize) {
		int minCapacity = 5;
		int capacity = StdRandom.uniform(maxSize)+minCapacity;
		MyMinMaxPQ<Integer> pq = new MyMinMaxPQ<> (capacity);
		for (int i=StdRandom.uniform (capacity); i>0; i--)
			pq.insert (randomValue());
		return pq;
	}
	private static void randomOps (MyMinMaxPQ<Integer> pq, int NUMOPS, boolean log) {
		for (int i=NUMOPS; i>0; i--) {
			switch (StdRandom.uniform (4)) {
			case 0:
				if (! pq.isEmpty()) {
					int x = pq.delMin();
					if (log) { StdOut.format ("delMin=%d\n", x); pq.showHeap(); }
				}
				break;
			case 1:
				if (! pq.isEmpty()) {
					int x = pq.delMax();
					if (log) { StdOut.format ("delMax=%d\n", x); pq.showHeap(); }
				}
				break;
			default:
				if (! pq.isFull()) {
					int x = randomValue();
					pq.insert(x);
					if (log) { StdOut.format ("insert=%d\n", x); pq.showHeap(); }
				}
				break;
			}
		}
	}
	private static void randomEmpty (MyMinMaxPQ<Integer> pq, boolean log) {
		while (! pq.isEmpty ())
			switch (StdRandom.uniform (2)) {
			case 0:
				if (! pq.isEmpty()) {
					int x = pq.delMin();
					if (log) { StdOut.format ("delMin=%d\n", x); pq.showHeap(); }
				}
				break;
			case 1:
				if (! pq.isEmpty()) {
					int x = pq.delMax();
					if (log) { StdOut.format ("delMax=%d\n", x); pq.showHeap(); }
				}
				break;
			}
	}
	private static boolean assertionsAreOn () {
		StdOut.println ("ASSERTIONS ARE ON!");
		return true;
	}
	public static void main (String[] args) {
		StdRandom.setSeed (0);
		for (int i=100; i>0; i--) {
			MyMinMaxPQ<Integer> pq = randomPQ (10);
			randomOps (pq, 10, true);
			randomEmpty (pq, true);
		}
		for (int i=100; i>0; i--) {
			MyMinMaxPQ<Integer> pq = randomPQ (1000);
			randomOps (pq, 10000, false);
			randomEmpty (pq, false);
		}
		StdOut.println ("If you don't see a statement below saying that assertions are on, then they are not on.");
		StdOut.println ("That means that you have not really tested anything!");
		StdOut.println ("You must enable assertions!");
		StdOut.println ("To enable assertions, see the instructions at the top of this .java file.");
		assert assertionsAreOn();


		//MyMinMaxPQ<Integer> pq = new MyMinMaxPQ<> (100);
		//StdIn.fromString ("10 20 30 40 50 + - + 05 25 35 - + - 70 80 05 + - - + ");  // This is not a very good test
		//StdIn.fromString ("10 20 40 50 30 + 70 60 - 30 - 50 20 +");                  // This is a good test
		//while (!StdIn.isEmpty ()) {
		//    pq.showHeap ();
		//    String item = StdIn.readString ();
		//    if (item.equals ("-")) StdOut.println ("min: " + pq.delMin ());
		//    else if (item.equals ("+")) StdOut.println ("max: " + pq.delMax ());
		//    else pq.insert (Integer.parseInt (item));
		//}
		//StdOut.println ("(" + pq.size () + " left on pq)");
	}
}