/* File: PriorityQueue.java - May 2011 */
package l25;

/**
 *  A class implementing a priority queue
 *
 *  @author Michael Albert
 *
 */
public class PriorityQueue<T>{

   private ArrayHeap<QueueNode<T>> heap;
   private static int arrivalNumber = 0;

   public PriorityQueue() {
      heap = new ArrayHeap<QueueNode<T>>();
   }

   public void add(T item, int priority) {
      heap.add(new QueueNode<T>(item, priority));
   }

   public T removeNext() {
      return heap.remove().value;
   }

   public boolean isEmpty() {
      return heap.isEmpty();
   }

   public int size() {
      return heap.size();
   }

   private class QueueNode<T> implements Comparable<QueueNode<T>>{
      
      private T value;
      private int priority;
      private int arrival;

      private QueueNode(T value, int priority) {
         this.value = value;
         this.priority = priority;
         this.arrival = arrivalNumber;
         arrivalNumber++;
      }

      public int compareTo(QueueNode<T> other) {
         if (this.priority < other.priority) return -1;
         if (this.priority > other.priority) return 1;
         return other.arrival - this.arrival;
      }

   }
}