package edu.uwm.cs351;

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

import junit.framework.TestCase;

public class PriorityQueue<T> {
	/**
	 * An priority queue using a parallel-array-based ternary tree max heap
	 */
	private final int INITIAL_CAPACITY = 7;
	private T[] data;
	private int[] priorities;
	private int manyItems;

	private static boolean doReport = true;
	private boolean report(String message) {
		if (doReport) System.err.println("Invariant error: " + message);
		return false;
	}

	protected PriorityQueue(boolean ignored) {} // don't change: used by invariant checker

	private boolean wellFormed() {
		// TODO: Check invariant
		// 1. neither array can be null
		if(data == null) return  report("data is null");
		if(priorities == null) return report("priorities is null");
		// 2. manyItems must be between 0 and data's length
		if(manyItems < 0 || manyItems > data.length) return report("manyItems is data's range");
		// 3. manyItems must be between 0 and priorities' length
		if(manyItems < 0 || manyItems > priorities.length) return report("manyItems is priorities's range");
		// 4. all children have lower priority than their parents
		if(data.length != priorities.length) return report("hey ");
		for(int i = 0; i < data.length; i++) {
			if(priorities[(i-1)/3] < priorities[i])
				return report("one or more children has a higher priority than its parent");
		}
		return true;
	}
	//TODO: optional helper method to check the children of a given node

	/**
	 * Create a new PriorityQueue
	 */
	@SuppressWarnings("unchecked")
	public PriorityQueue() {
		data = (T[])new Object[INITIAL_CAPACITY];
		priorities = new int[INITIAL_CAPACITY];
		assert wellFormed() : "invariant broken at end of constructor";
	}

	/**
	 * Add an element to the PriorityQueue
	 * @param element the element to be added
	 * @param priority the priority of the added element
	 * @return true
	 */
	public boolean add(T element, int priority) {
		//TODO: add a ProfileLink to the end of the array, and then bubble it up
		assert wellFormed() : "invariant broken at start of add";
		ensureCapacity(manyItems+1);
		//add the new element at the end of the array
		data[manyItems] = element;
		//update the priority accordingly
		priorities[manyItems] = priority;
		bubbleUp(manyItems);
		manyItems++;
		assert wellFormed() : "invariant broken at end of add";
		return true;
	}

	/**
	 * Remove and return the highest priority element from the PriorityQueue
	 * @return the highest priority element, now removed
	 * @throws NoSuchElementException if empty
	 */
	public T remove() {
		//TODO: remove and return the first Profile Link
		//    replace it with the last ProfileLink
		//    and then bubble it down
		assert wellFormed() : "invariant broken at start of remove";
		if(size()==0) throw new NoSuchElementException("the heap is empty");
		T highestPriorityElement = data[0];
		//putting the last element on the root
		data[0] = data[manyItems-1];
		data[manyItems-1] = null;
		//rearranging the priorities after shifting elements
		priorities[0] = priorities[manyItems-1];
		priorities[manyItems-1] = 0;
		bubbleDown();
		manyItems--;
		assert wellFormed() : "invariant broken at end of remove";
		return highestPriorityElement;
	}

	/**
	 * Return the size of the PriorityQueue
	 * @return the number of elements
	 */
	public int size() {
		//TODO: return the size of the queue
		assert wellFormed() : "invariant broken at start of size";
		return manyItems;
	}

	/**
	 * Check if the PriorityQueue is empty
	 * @return whether the PriorityQueue is empty
	 */
	public boolean isEmpty() {
		//TODO: return whether the queue is empty
		assert wellFormed() : "invariant broken at start of isEmpty";
		return size()<1 ? true: false;
	}

	@Override
	public String toString() {
		return Arrays.toString(data);
	}

	@SuppressWarnings("unchecked")
	private void ensureCapacity(int minimumCapacity)
	{
		Object[] newArray;
		int[] newPriorities;
		if(data.length < minimumCapacity)
		{
			int newCapacity = data.length *2;
			if(newCapacity < minimumCapacity)
				newCapacity = minimumCapacity;
			newArray = new Object[newCapacity];
			newPriorities = new int[newCapacity];
			for(int i=0; i<manyItems; i++) {
				newArray[i] = data[i];
				newPriorities[i] = priorities[i];
			}
			data = (T[])newArray;
			priorities = newPriorities;
		}
	}

	//TODO: optional helper methods
	//    bubbleDown
	//    bubbleUp
	//    other useful utility methods?
	
	//Private getters for children and parent indexes
	private int getLeftChildIndex (int parentIndex){
		return 3*parentIndex+1;
	}
	private int getMiddleChildIndex (int parentIndex){
		return 3*parentIndex+2;
	}
	private int getRightChildIndex (int parentIndex){
		return 3*parentIndex+3;
	}
	private int getParentIndex (int childIndex){
		return (childIndex-1)/3;
	}
	
	//Private helpers that check if the node has the a left, right and middle child to avoid ArrayIndexOutOfBoundsException
	private boolean hasleftChild (int parentIndex){
		int leftChild = getLeftChildIndex(parentIndex) ;
		return leftChild < manyItems && data[leftChild] != null? true: false; //this checks to see if the index is in bounds and the content isn't null
	}
	private boolean hasMiddleChild (int parentIndex){
		int middleChild = getMiddleChildIndex(parentIndex) ;
		return middleChild < manyItems && data[middleChild] != null? true: false; 
	}
	private boolean hasrightChild (int parentIndex){
		int rightChild = getRightChildIndex(parentIndex);
		return rightChild < manyItems&& data[rightChild] != null? true: false; 
	}
	//bubble Up, bubbleDonw Helpers, swap 
	private void bubbleUp(int index){
		while(priorities[index] > priorities[getParentIndex(index)]){
			int parentIndex = getParentIndex(index);
			swap(index, parentIndex);
			index = parentIndex;
		}
	}

	private void bubbleDown(){
		int i = 0;
		while( hasleftChild(i)){//the left child is always to first one filled so if the left subtree is empty there is no need to check the others.
			int higherChildIndex = getLeftChildIndex(i);//this int keeps track of the index of the child with the highest priority
			if( hasMiddleChild(i)) {
				//determines which child has the highest priority
				int middleIndex = getMiddleChildIndex(i);
				higherChildIndex = priorities[higherChildIndex] < priorities[middleIndex]? middleIndex: higherChildIndex;
			}
			if( hasrightChild(i)) {
				int rightIndex = getRightChildIndex(i);
				higherChildIndex = priorities[higherChildIndex] < priorities[rightIndex]? rightIndex: higherChildIndex;
			}
			if(priorities[i] < priorities[higherChildIndex])
				swap(i, higherChildIndex);
			i = higherChildIndex;
		}
	}

	private void swap(int index1, int index2){
		//swap data
		T tempElement = data[index1];
		data[index1] = data[index2];
		data[index2] = tempElement; 
		//swap priority
		int tempIndex = priorities[index1];
		priorities[index1] = priorities[index2];
		priorities[index2] = tempIndex;
	}

	public static class TestInvariant extends TestCase {

		PriorityQueue<String> self;

		@Override
		public void setUp() {
			self = new PriorityQueue<String>(false);
		}

		public void testNull() {
			assertFalse(self.wellFormed());
			self.manyItems = 0;
			assertFalse(self.wellFormed());
			self.data = new String[0];
			assertFalse(self.wellFormed());
			self.data = null;
			self.priorities = new int[0];
			assertFalse(self.wellFormed());
		}

		public void testEmpty() {
			self.data = new String[0];
			self.priorities = new int[0];
			self.manyItems = 0;
			assertTrue(self.wellFormed());
			self.manyItems = -1;
			assertFalse(self.wellFormed());
			self.manyItems = 1;
			assertFalse(self.wellFormed());
		}

		public void unevenArrays() {
			self.data = new String[1];
			self.priorities = new int[2];
			self.manyItems = 1;
			assertTrue(self.wellFormed());
			self.manyItems = 2;
			assertFalse(self.wellFormed());
			self.data = new String[3];
			assertTrue(self.wellFormed());
			self.manyItems = 3;
			assertFalse(self.wellFormed());
		}

		public void testSmall() {
			self.data = new String[2];
			self.priorities = new int[2];
			self.priorities[0] = 1;
			self.priorities[1] = 1;
			self.manyItems = 2;
			assertTrue(self.wellFormed());
			self.priorities[1] = 0;
			assertTrue(self.wellFormed());
			self.priorities[1] = 2;
			assertFalse(self.wellFormed());
		}

		public void testMedium() {
			self.data = new String[4];
			self.priorities = new int[4];
			self.priorities[0] = 8;
			self.priorities[1] = 3;
			self.priorities[2] = 4;
			self.priorities[3] = 1;
			self.manyItems = 4;
			assertTrue(self.wellFormed());
			self.priorities[1] = 11;
			assertFalse(self.wellFormed());
			self.priorities[1] = 1;
			self.priorities[2] = 12;
			assertFalse(self.wellFormed());
			self.priorities[2] = 2;
			self.priorities[3] = 12;
			assertFalse(self.wellFormed());
			self.priorities[3] = 5;
			assertTrue(self.wellFormed());
		}

		public void testLarge() {
			self.data = new String[21];
			self.priorities = new int[21];

			self.priorities[0] = 100;

			self.priorities[1] = 99;
			self.priorities[2] = 13;
			self.priorities[3] = 86;

			self.priorities[4] = 89;
			self.priorities[5] = 40;
			self.priorities[6] = 53;
			self.priorities[7] = 12;
			self.priorities[8] = 5;
			self.priorities[9] = 11;
			self.priorities[10] = 22;
			self.priorities[11] = 65;
			self.priorities[12] = 65;

			self.priorities[13] = 88;
			self.priorities[14] = 88;
			self.priorities[15] = 86;
			self.priorities[16] = 15;
			self.priorities[17] = 39;
			self.priorities[18] = 35;

			self.manyItems = 19;
			assertTrue(self.wellFormed());
			self.priorities[7] = 14;
			assertFalse(self.wellFormed());
			self.priorities[7] = 12;
			self.priorities[8] = 14;
			assertFalse(self.wellFormed());
			self.priorities[8] = 5;
			self.priorities[9] = 14;
			assertFalse(self.wellFormed());
			self.priorities[9] = 11;

			self.priorities[16] = 44;
			assertFalse(self.wellFormed());
			self.priorities[16] = 15;
			self.priorities[17] = 44;
			assertFalse(self.wellFormed());
			self.priorities[17] = 39;
			self.priorities[18] = 44;
			assertFalse(self.wellFormed());
			self.priorities[18] = 35;

			self.priorities[4] = 86;
			assertFalse(self.wellFormed());
			self.priorities[4] = 89;
			self.priorities[5] = 36;
			assertFalse(self.wellFormed());
			self.priorities[5] = 40;

			self.priorities[0] = 99;
			assertTrue(self.wellFormed());
		}
	}

}