import java.util.List;
import java.util.LinkedList;
import java.util.ListIterator;

/**     Sorted LinkedList implementation of a priority queue
 *
 * The list is maintained as sorted non-INCREASING (i.e., smallest
 * at the back, largest at the front), so that removing the
 * minimal entry is an O(1) operation.  Entries are entered from
 * the front, so that on equal priority the entries will actually
 * be processed in a queue-like fashion.
 *
 * To do the non-increasing sort, there is a nested comparator
 * method that simply inverts the comparison for the Comparable
 * objects in the ArrayList.
 *
 * Methods:
 *   isEmpty  are there any entries in the queue
 *   isValid  is this a valid priority queue (cf. append)
 *   remove   remove the minimal entry
 *   peek     examine the minimal entry without removing it
 *   enter    make an entry, restoring the priority queue propery
 *   append   add entries at the end, voiding priority queue
 *   correct  turn this into a valid priority queue
 *
 * Author:  Timothy Rolfe
 *
 * Note:  the ONLY difference between this and SortedArrayPQ is
 * the actual class used for the creation of List data.
 */
public class SortedLinkedPQ implements PriorityQueue
{
   boolean DEBUG = false;

   static private class Reverse implements java.util.Comparator
   {
      // Simply reverse the roles of left (lt) and right (rt)
      public int compare (Object lt, Object rt)
      {  return ((Comparable)rt).compareTo((Comparable)lt);  }
   }

   // No constructor required.  Initialize as an empty ArrayList
   List<Comparable> data = new LinkedList<Comparable>();
   int size = 0;             // Initial size, of course, is zero.
   boolean valid = true;     // Initial empty queue is valid.

   //  Removes all of the elements from this priority queue
   public void clear()  {  data.clear();  }

   // Is the queue empty?  Check the ArrayList.
   public boolean isEmpty()  {  return data.isEmpty();  }

   // Is the queue valid?  Return the flag.
   public boolean isValid()  {  return valid;  }

   // Enter item into a valid queue, as priority queue.
   public void enter ( Comparable item )
   {
      ListIterator<Comparable> iter = data.listIterator();

      if ( !valid )  correct();

      // Note:  ordered from largest to smallest
      while ( iter.hasNext() )
      {
         Comparable check = iter.next();
         if ( item.compareTo(check) >= 0 )  // I.e, item NOT < check
         {
            iter.previous(); // Back up for insertion point
            break;           // and exit the loop
         }
      }
      // However we got here, the item goes exactly HERE
      iter.add(item);
      size++;
      if ( DEBUG )
         System.out.println(data);
   }

   // Remove an item from the priority queue.
   public Comparable remove ( )
   {
      if ( !valid )  correct();
      return data.isEmpty() ? null : data.remove(--size) ;
   }

   // Show the next item for priority queue removal
   public Comparable peek ( )
   {
      if ( !valid )  correct();
      return data.isEmpty() ? null : data.get(size-1) ;
   }

   // Add to the end of the ArrayList WITHOUT corrections.
   public void append ( Comparable item )
   {  size++; data.add(item);  valid = false; }

   // Once all the appends are finished, make it a valid again.
   public void correct ()
   {
      valid = true;
      java.util.Collections.sort ( data, new Reverse() );
      if ( DEBUG )
         System.out.println (data);
   }
}