// file:    MyPriorityQueue.java
// author:  Robert Keller
// purpose: Implement PriorityQueue interface

import java.util.*;

/**
 * Objects are inserted using enqueue and removed using dequeueMin,
 * which always returns the minimum in the Comparable ordering.
 * This implementation maintains the items in increasing order at all times.
 */

class MyPriorityQueue implements PriorityQueue
{
/**
 * reference to the first PCell in the queue, which is always the minimum
 * element in the PriorityQueue.
 */

protected PCell head;

/**
 * The Comparator to be used for comparing elements in selecting the
 * minimum.
 */

protected Comparator comp;


/**
 * Construct a MyPriorityQueue.
 */

MyPriorityQueue(Comparator _comp)
  {
  head = null;
  comp = _comp;
  }


/**
 * Insert an Object in the PriorityQueue.
 *
 * @param item the Object to be inserted
 */

public void enqueue(Object item)
  {
  // If the PriorityQueue is empty, or the item to be inserted is the
  // new minimum, it goes at the head of the queue.

  if( head == null || comp.compare(item,  head.data) < 0 )
    {
    head = new PCell(item, head);
    return;
    }

  // If the PriorityQueue is non empty and the item to be inserted is
  // not the new minimum, then find the PCell that will come before it
  // and insert it in the list.

  for( PCell ptr = head; ptr != null; ptr = ptr.next )
    {
    if( ptr.next == null || comp.compare(item, ptr.next.data) < 0 )
      {
      ptr.next = new PCell(item, ptr.next);
      return;
      }
    }
  }


/**
 * Remove the minimum Object from the PriorityQueue.
 *
 * @return the Object removed
 * @exception EmptyQueueException if the PriorityQueue is empty
 */

public Object dequeueMin() throws EmptyQueueException
  {
  if( head == null )
    {
    throw new EmptyQueueException();
    }

  Object result = head.data;
  head = head.next;
  return result;
  }


/**
 * Indicate whether or not the PriorityQueue is empty
 *
 * @return boolean indicating whether or not the Queue is empty
 */

public boolean isEmpty()
  {
  return head == null;
  }


/**
 * Cell containing a PriorityQueue element
 */

class PCell
  {
  /**
   * the data item
   */

  Object data;


  /**
   * reference to the PCell containing the next greater data item
   */

  PCell next;


  /**
   * construct a PCell
   * @param _data the data item in the PCell
   * @param _next reference to a PCell containing the next larger data item
   */

  PCell(Object _data, PCell _next)
    {
    data = _data;
    next = _next;
    }
  }

}