//-------------------------------------------------------------------
// CSE 461 - Winter 1998
//
//  Homework 1: Priority Queue in Java
//
// Sample Solution - Andy Collins - acollins@cs.washington.edu
//
// This one is a more advanced solution with a slightly different
// setup.
//-------------------------------------------------------------------

import java.util.*;
import java.io.*;


//-------------------------------------------------------------------
// class PriorityQueue: a priority queue
//
// This class is not terribly efficient, but it has several 
// interesting properties:
//
// * It can hold objects of any class, since it treats them
//   as Objects.
//
// * Clients can specify priorties at insert time, or they 
//   can store objects which implement the Prioritized interface
//   and self-identify their priorities.
//
// * Priorities for objects supporting the Prioritized interface
//   may be changed at any time.
//
// * The priorities are stable, in the sense that elements added
//   with the same priority come out FIFO.
//-------------------------------------------------------------------
interface Prioritized
{
   public double Priority ();
}

class NoMoreElements extends Exception
{
}

public class PriorityQueue
{
   public static void main (String args[])
   {
      PriorityQueue pq = new PriorityQueue ();
      Random r = new Random ();

      for (int i=0; i<10; ++i)
         pq.Insert (new Integer (i), r.nextDouble ());
      System.out.println ("Dequeuing");
      while (pq.Length () > 0)
         try
            {
            System.out.println ("   " + pq.Remove ()); 
            }
         catch (Exception e)
            {
            }
   }

   public PriorityQueue ()
   {
      items = new Vector ();
   }

   public void Insert (Object element, double priority)
   {
      items.addElement (new PriorityPair (new SimplePrioritized (element, priority), 
                                          element)); 
   }

   public void Insert (Prioritized element)
   {
      items.addElement (new PriorityPair (element, element));
   }

   public Object Remove () throws NoMoreElements
   {
      Enumeration e = items.elements ();
      if (!e.hasMoreElements ())
         throw new NoMoreElements ();

      PriorityPair retval = (PriorityPair) e.nextElement ();
      double retvalPriority = retval.prioritized.Priority ();

      while (e.hasMoreElements ())
         {
         PriorityPair next = (PriorityPair) e.nextElement ();
         double nextPriority = next.prioritized.Priority ();

         if (nextPriority > retvalPriority)
            {
            retval = next;
            retvalPriority = nextPriority;
            }
         }

      items.removeElement (retval);
      return retval.data;
   }

   public int Length ()
   {
      return items.size ();
   }

   private Vector items;
}

class SimplePrioritized implements Prioritized
{
   public SimplePrioritized (Object c, double p)
   {
      contents = c;
      priority = p;
   }

   public double Priority ()
   {
      return priority;
   }

   public Object Contents ()
   {
      return contents;
   }

   private Object contents;
   private double priority;
}

class PriorityPair
{
   public PriorityPair (Prioritized p, Object o)
   {
      prioritized = p;
      data = o;
   }

   public Prioritized prioritized;
   public Object data;
}