/**
  * @param <K> the Key element. This must implement Comparable.
 * @param <V> The Value element.  This could be anything.
 * 
 * For methods that exactly follow the interface, see the documentation in 
 * the interface.  This implements a priority queue built on top of an 
 * unordered array.  (Note that this comment violates encapsulation.)
 * 
 * Functions that follow the AbstractClass or interface
 * are not documented here
 * 
 * @author gtowell
 * Created APRIL 6, 2020
 * Modified: April 12, 2021
 * Modified: Oct 26, 2021
 */
public class PriorityQueue<K extends Comparable<K>, V>  extends AbstractPriorityQueue<K,V> {
    
    /** Default capacity */
    private static int CAPACITY = 200;

    /** The thing actually holding the data in the priority queue.  Using an ArrayList
     * to get unbounded length.  
     */
    private Pair<K,V>[] pqStore;

    /** The number of items in the priority queue */
    private int size;

    /**
     * Build an array list of the default capacity
     */
    public PriorityQueue() {
        this(CAPACITY);
    }

    @SuppressWarnings("unchecked")
    /** 
     * Return an array list of the given capacity
     * @param initialCapacity -- the capacity
     */
    public PriorityQueue(int initialCapacity) {
        pqStore = (Pair<K,V>[]) new Pair[initialCapacity];
        this.size=0;
    }

    public int size() {
        return size;
    }

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

    public boolean offer(K newK, V newV) {
        if (size==CAPACITY)
            return false;
        Pair<K,V> entry = new Pair<>(newK, newV);
        pqStore[size]=entry;
        size++;
        return true;
    }

    /**
     * find and return the index of the next item from the priority queue
     * @return the next item
     */
    private int  getNext() {
        if (isEmpty())
            return -1;
        // if there are entries, then go through them all to find the next one.
        // must do this because entries are in no particular order.
        int lmin = 0; 
        for (int i=1; i<size; i++) {
            Pair<K,V> curr = pqStore[i];
            if (pqStore[lmin].compareTo(curr) > 0) {
                lmin=i;
            }
        }
        return lmin;
    }

    private void remove(int lmin) {
        for (int i=lmin; i<size-1; i++) {
            pqStore[i] = pqStore[i+1];
        }
        pqStore[size-1]=null;
        size--;
    }

    public V poll() {
        if (isEmpty())
            return null;
        int lmin = getNext();
        Pair<K,V> entry = pqStore[lmin];
        remove(lmin);
        return entry.theV;
    }

    public V peek() {
        if (isEmpty())
            return null;
        int lmin = getNext();
        Pair<K,V> entry = pqStore[lmin];
        return entry.theV;
    }

    public String toString() {
        StringBuilder sb = new StringBuilder("PQ[");
        for (int i=0; i<size; i++)
            sb.append(i+pqStore[i].toString());
        sb.append(" ]");
        return sb.toString();
    }
    public static void main(String[] args) {
        PriorityQueue<Integer, String> pq = new PriorityQueue<>();
        pq.offer(1,"Jane");
        pq.offer(2,"WET");
        pq.offer(5, "WAS");
        System.out.println(pq);
        System.out.println(pq.poll());
        System.out.println(pq);
        System.out.println(pq.poll());
        System.out.println(pq);
        System.out.println(pq.poll());
        System.out.println(pq);
        System.out.println();

        pq = new PriorityQueue<>();
        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());
    }

}