// implement a priority queue using a linked list
// first item on list is the highest priority item

class PQAsListAlt implements SeqStructure{

    private ListNode list;
    int size = 0;
    // two cursors:
    private ListNode current;
    private ListNode previous;
    
    public PQAsListAlt() { }
    
    // helper method, not part of interface
    // linear search
    private void scan(PQElement pin) {
	current = list;
	previous = null;
	if (size == 0) return;
	
	// scan PQ till you find 
	while (current != null && pin.compareTo(current.getItem()) <= 0){
	    previous = current;
	    current = current.getNext();
	}
    }
    
    
    public void put(Object pin) {
	PQElement p = (PQElement)pin;
	scan(p);
	if (previous == null) // make pin the first element
	    list = new ListNode(pin, list);
	else 
	    previous.setNext(new ListNode(pin,current));
	size = size + 1;
    }
    
    public Object get() { // remove and return head of list l
	if (size != 0){
	    Object o = list.getItem();
	    list = list.getNext();
	    size = size - 1;
	    return o;}
	else {
	    System.out.println("Attempt to dequeue from empty priority queue");
	    return null;
	}
    }
    
    public String toString() {
	if (size == 0) return "Empty Priority Queue \n";
	else 
	    return "Priority Queue elements from first to last are:\n" + list;
    }
    
    public int size() {
	return size; 
    }
    
    public boolean isEmpty() {
	return (size == 0);
    }
    
} // end of class PQAsList

public class TestPQAsListAlt {

    public static void main(String[] args) {
	
	PQAsList pq = new PQAsList();
	System.out.println(pq); //should print empty
	pq.put(new PQElement("Bill",3));
	System.out.println(pq); //should print ((Bill,3))
	pq.put(new PQElement("Monica",1));
	System.out.println(pq); //should print ((Bill,3),(Monica,1))
	pq.put(new PQElement("Hillary",4));
	System.out.println(pq); //should print ((Hillary,4),(Bill,3),(Monica,1))
	pq.put(new PQElement("Newt",3));
	System.out.println(pq);//should print ((Hillary,4),(Bill,3),(Newt,3)(Monica,1))
	System.out.println("Get->" + pq.get()); //(Hillary,4)
	System.out.println(pq); //((Bill,3),(Newt,3),(Monica,1))
	pq.put(new PQElement("Gennifer",2)); 
	System.out.println(pq);//((Bill,3),(Newt,3),(Gennifer,2),(Monica,1))
	System.out.println("Get->" + pq.get());// (Bill,3)
	System.out.println(pq); //((Newt,3),(Gennifer,2),(Monica,1))
	System.out.println("Get->" + pq.get());//(Newt,3)
	System.out.println(pq);//((Gennifer,2),(Monica,1))
	System.out.println("Get->" + pq.get());//(Gennier,2)
	System.out.println(pq);//((Monica,1))
	System.out.println("Get->" + pq.get());//(Monica,1)
	System.out.println(pq);//empty PQ
    }
}