// Descending priority, the higher the key, the higher the priority
@SuppressWarnings({"unchecked"})
public class PriorityQueueArray2<T extends Comparable<T>> {   
	
	private T[] pqArray;
    private int length;
    private int maxSize;
     
    public PriorityQueueArray2(int capacity) {
    	maxSize = capacity;
        pqArray = (T[])new Comparable[capacity];	        
    }
    
    //Add at the end without sorting, Time O(1), Space O(1), 
    public void enqueue(T value ) {
        if(length == maxSize) {
            System.out.println("The priority queue is full! can not enqueue " + value);
            return;
        }
        pqArray[length] = value;
        length++;
    }
     
    //Find the biggest and delete it, Time O(n), Space O(1)
    public T dequeue() {
        if (isEmpty()) {
            System.out.println("The priority queue is empty! can not dequeue.");
            return null;
        }
        int maxIndex = 0;
        for (int i = 1; i < length; i++) { //search for biggest
            if (pqArray[i].compareTo (pqArray[maxIndex]) > 0) { 
                maxIndex = i; 
            } 
        } 
        T item = pqArray[maxIndex]; 
        System.out.println("dequeue: " + item);
        length--; 
        pqArray[maxIndex] = pqArray[length]; //move the last to this spot
        return item;
    }
    
    //Find the biggest and return it, Time O(n), Space O(1)
    public T peek() {
        if (isEmpty() ){
            System.out.println("The priority queue is empty!");
            return null;
        }
        int maxIndex = 0;
        for (int i = 1; i < length; i++) { //search for biggest
            if (pqArray[i].compareTo (pqArray[maxIndex]) > 0) { 
                maxIndex = i; 
            } 
        } 
        return pqArray[maxIndex];
    }
    
    //print all, in insert order, Time O(n), Space O(1)
    public void print() {
    	System.out.print("Priority Queue: ");
    	for (int i = 0; i < length; i++)
    		System.out.print(pqArray[i] + " ");
    	System.out.println();
    }
    
    //return length of array, Time O(1), Space O(1), 
    public int size() {
    	return pqArray.length;
    }
    
    //Check empty, Time O(1), Space O(1), 
    private boolean isEmpty() {
    	return length == 0;
    }
     
    public static void main(String a[]){
    	PriorityQueueArray2<Integer> pq = new PriorityQueueArray2<>(5);
        pq.enqueue(30);
        pq.enqueue(12);
        pq.enqueue(20);
        pq.enqueue(15);       
        pq.enqueue(54);  
        pq.enqueue(66);
        pq.print();
        System.out.println("size: " + pq.size());
        System.out.println("peek: " + pq.peek());
        
        //dequeue
        pq.dequeue();
        pq.print();
        System.out.println("size: " + pq.size());
        System.out.println("peek: " + pq.peek());
        
        
        //enqueue again
        pq.enqueue(66);
        pq.enqueue(98);
        pq.print();
        System.out.println("size: " + pq.size());
        System.out.println("peek: " + pq.peek());
    }
}