import java.util.Random;

/**
 * Priority Queue implementation using heaps.   
 * It is superior to the ArrayList based implementation in that both
 * add and remove at O(log n).  On there other hand, the heap is size fixed in order
 * to ensure that add and remove both are truly O(log n) time. 
 * 
 * @param <K>  the key
 * @param <V>  the value 
 * 
 * For methods that exactly follow the interface, see the documentation in the interface.
 * 
 * @author gtowell
 * Created APRIL 6, 2020
 * Modified: April 12, 2021
 * Modified: Oct 26, 2021
 */

@SuppressWarnings("unchecked")
public class PriorityQHeap<K extends Comparable<K>, V> extends AbstractPriorityQueue<K, V>
{

    /** The default size of the heap.  This corresponds to a max depth or 10. */
	private static final int CAPACITY = 1032;
	/** The array that holds the heap. */
	private Pair<K,V>[] backArray;
	/** The number of items actually in he heap. */
    private int size;

    /**
     * Initialize the priority queue with default values. 
	 * Make a min heap with the default size
     */
    public PriorityQHeap() {
        this(CAPACITY);
	}
	
	/**
	 * Initialize a heap. 
	 * @param order the order in which items are retrieved from the heap.
	 * @param capacity the max number of items in the heap.
	 */
    public PriorityQHeap(int capacity) {
        backArray = new Pair[capacity];
	}

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

    @Override
    public boolean isEmpty()
    {
		return size==0;
    }

    @Override
    public boolean offer(K key, V value)
	{
		if (size >= (backArray.length - 1))
			return false;
		int loc = size++;
		backArray[loc] = new Pair<K, V>(key, value);
		int upp = (loc - 1) / 2;
		while (loc != 0) {
			if (0 > backArray[loc].compareTo(backArray[upp])) {
				Pair<K, V> tmp = backArray[upp];
				backArray[upp] = backArray[loc];
				backArray[loc] = tmp;
				loc = upp;
				upp = (loc - 1) / 2;
			} else {
				break;
			}
		}
		return true;
	}

	private void removeTop()
	{
		size--;
		backArray[0] = backArray[size];
		backArray[size] = null;
		int parentLoc = 0; 
		while (true) 
		{
			int bestChildLoc;  
			int childLoc1 = parentLoc * 2 + 1; 
			int childLoc2 = parentLoc * 2 + 2; 
			if (childLoc1 >= size) 
				break; 
			if (childLoc2 >= size) {
				bestChildLoc = childLoc1; 
			} else {
				int cmp = backArray[childLoc1].compareTo(backArray[childLoc2]);
				if (cmp <= 0)
					bestChildLoc = childLoc1;
				else
					bestChildLoc = childLoc2;
			}
			if (0 > backArray[bestChildLoc].compareTo(backArray[parentLoc])) {
				Pair<K, V> tmp = backArray[bestChildLoc];
				backArray[bestChildLoc] = backArray[parentLoc];
				backArray[parentLoc] = tmp;
				parentLoc = bestChildLoc;
			} else {
				break;
			}
		}
	}
	
	

	@Override
	public V poll() {
		if (isEmpty())
			return null;
		Pair<K,V> tmp = backArray[0];
		removeTop();
		return tmp.theV;
	}

	@Override
	public V peek() {
		if (isEmpty())
			return null;
		return backArray[0].theV;
	}


	public static void main(String[] args) {
        PriorityQHeap<Integer, String> pq = new PriorityQHeap<>(CAPACITY);
        pq.offer(1,"Jane");
        pq.offer(10,"WET");
        pq.offer(5, "WAS");
        System.out.println(pq.poll());
        System.out.println(pq.poll());
        System.out.println(pq.poll());
        System.out.println();

        pq = new PriorityQHeap<>(CAPACITY);
        pq.offer(2,"Jane");
        pq.offer(1,"WET");
        pq.offer(5, "WAS");
        System.out.println(pq.poll());
        System.out.println(pq.poll());
        System.out.println(pq.poll());
				
		Random r = new Random();
		PriorityQHeap<Integer, Integer> pqi = new PriorityQHeap<>(101);
		for (int i = 0; i < 100; i++) {
			int jj = r.nextInt(1000);
			pqi.offer(jj, jj);
		}
		for (int i = 0; i < 100; i++) {
			System.out.println(String.format("%2d %4d", i, pqi.poll()));
		}
    }

}