public class PriorityQueue extends LList
{
	//Enqueue without priority
	public void enqueue (Object o)
	{
		enqueue(o,0);
	}
	
	//enqueue with priority
	public void enqueue (Object o, int priority)
    {
		//when key is true stop inserting
		boolean key = false;
        
		//if the list is not empty
		if(!this.isEmpty())
        {
			
			this.setFirst();
			
			//while current value is not null check
			while (this.currValue() != null && key != true)
			{
				//priority is greater than the previous priority
				if(priority >= this.currPriority())
				{
					if (priority >0)
					{
						if (priority == this.currPriority())
						{
							//if the priority is the same
							while(this.currPriority() == priority)
							{
								this.next();
							}
							this.insert(o, priority);
							key = true;
						}
                        
						//if not the same
						else
						{
							this.insert(o, priority);
							key = true;
						}
					}
                    
					//if priority is 0
					else
					{
						this.insert(o, priority);
						key = true;
					}                                          
				}
				if (priority != this.currPriority())
                	this.next();
			}       
        }
            
		else
		{
			this.insert(o,priority);
		}
    }

	// clear
	public void clear ()
	{
		head.setNext(null);         
		curr = tail = head;       
		num = 0;
	}
	
	//dequeue
	public Object dequeue ()
	{
		this.setFirst();
		return this.remove();
		
	}
	
	//checks if empty
	public boolean isEmpty()
	{
		if (head.next() == null)
			return true;
		else
			return false;
	}
	
	//print
	public void print()
	{
		if (isEmpty())
			  System.out.println("()");
		else 
		{
		  System.out.print("( ");
		  for (setFirst(); isInList(); next())
			System.out.print(currValue() + " ");
		  System.out.println(")");
		}
	
	}
	
	//find size
	public int size()
	{
		int a =0;
		a = length();
		
		return a;
	}
}

class LList 
{ // Linked list class
	  protected Link head;            // Pointer to list header
	  protected Link tail;            // Pointer to last Object in list
	  protected Link curr;            // Pointer to current Object
	  protected int num;
	  LList(int sz) {
	 setup();
	  }    // Constructor -- Ignore sz
	  LList() {
	 setup();
	  }          // Constructor
	  private void setup() 
	  {        // Do initialization
	    tail = head = curr = new Link(null);
	    num = 0;
	  } // Create header node
	  public void clear() 
	  {         // Remove all Objects from list
		  head.setNext(null);         // Drop access to rest of links
		  curr = tail = head;         // Reinitialize
		  num = 0;
	  }
	  // Insert Object at current position
	  public void insert(Object it, int n) {
	 /* in 1.4, we can say:
	      assert (curr != null) : "No current element.";
	    Leave this in old form for now:
	 */
	 Assert.notNull(curr, "No current element");
	 curr.setNext(new Link(it,n, curr.next()));
	 if (tail == curr)           // Appended new Object
	   tail = curr.next();
	  }
	  // Insert Object at end of list
	  public void append(Object it,int n) {
	 tail.setNext(new Link(it,n, null));
	 tail = tail.next();
	  }
	  public Object remove() {      // Remove and return current Object
	 if (!isInList())
	   return null;
	 Object it = curr.next().element();    // Remember value
	 if (tail == curr.next())
	   tail = curr;       // Removed last: set tail
	 curr.setNext(curr.next().next());     // Remove from list
	 return it;                            // Return value removed
	  }
	  public void setFirst()        // Set curr to first position
	  { curr = head; }
	  public void next() {          // Move curr to next position
	    if (curr != null) curr = curr.next();
	  }
	  public void prev() {          // Move curr to previous position
	 if ((curr == null) || (curr == head)) { // No previous Object
	   curr = null;
	   return;
	 }           //   so just return
	 Link temp = head;           // Start at front of list
	 while ((temp != null) && (temp.next() != curr))
	   temp = temp.next();
	 curr = temp;                // Found previous link
	  }
	  public int length() {         // Return current length of list
	 int cnt = 0;
	 for (Link temp = head.next(); temp != null; temp = temp.next())
	    cnt++;                   // Count the number of Objects
	 return cnt;
	  }
	  public void setPos(int pos) { // Set curr to specified position
	 curr = head;
	 for(int i=0; (curr!=null) && (i<pos); i++)
	   curr = curr.next();
	  }
	  public void setValue(Object it) { // Set current Object's value
	 /* in 1.4, we can say:
	      assert (isInList()) : "No current element.";
	    Leave this in old form for now:
	 */
	 Assert.notFalse(isInList());
	    curr.next().setElement(it);
	  }
	  public Object currValue() {   // Return value of current Object
	 if (!isInList())
	   return null;
	 return curr.next().element();
	  }
	  public int currPriority() { //Return the current priority of the object
	   if(!isInList())
	    return 0;
	   return curr.next().priority();
	  }
	  
	  public boolean isEmpty() {    // Return true if list is empty
	    return head.next() == null;
	  }
	  public boolean isInList() {   // True if curr is within list
	    return (curr != null) && (curr.next() != null);
	  }
	  public void print() {         // Print out the list's elements
	 if (isEmpty())
	   System.out.println("()");
	 else {
	   System.out.print("( ");
	   for (setFirst(); isInList(); next())
	  System.out.print(currValue() + " ");
	   System.out.println(")");
	 }
	  }
	} // class LList


class Link {         // A singly linked list node
	 
	  private Object element;   // Object for this node
	  private Link next;        // Pointer to next node in list
	  private int num;
	 
	  Link(Object it,int n, Link nextval) {         // Constructor 1
	    element = it;
	    next = nextval;
	    num = n;
	  }   //  Given Object
	 
	  Link(Link nextval) {
	        next = nextval;
	  } // Constructor 2
	 
	  Link next() {
	        return next;
	  }
	 
	  Link setNext(Link nextval) {
	        next = nextval;
	        return next;
	  }
	 
	  Object element() {
	        return element;
	  }
	  
	  int priority() {
	          return num;
	  }
	 
	  Object setElement(Object it) {
	        element = it;
	        return element;
	  }
	  
	  int setPriority(int i) {
	          num = i;
	          return i;
	  }
	 
	} // class Link 

	  
class Assert 
{
		    static public void notFalse(boolean b)
	                       throws IllegalArgumentException {
	        if(b == false)
	            throw new IllegalArgumentException(
	                            "boolean expression false");
		    }
		    static public void notNull(Object obj)
	                       throws IllegalArgumentException {
	        if(obj == null)
	            throw new IllegalArgumentException("null argument");
    }

	    static public void notFalse(boolean b, String s)
	                               throws IllegalArgumentException {
	        if(b == false)
	            throw new IllegalArgumentException(s);
	    }
	    static public void notNull(Object obj, String s)
	                               throws IllegalArgumentException {
	        if(obj == null)
	            throw new IllegalArgumentException(s);
	    }
}