/**
   The UnsortedSequencePriorityQueue class implements the PriorityQueue interface by means of
   an unsorted sequence.
  
   @author      Franck van Breugel
   @version     1.3    May 30, 2002
   @see Comparator
   @see Item
*/
public class UnsortedSequencePriorityQueue implements PriorityQueue 
{
    private Sequence sequence; // unsorted sequence containing the items of this priority queue
    private Comparator comparator; // contains method isLessThan to compare keys

    /**
       Constructs an UnsortedSequencePriorityQueue from the specified sequence and comparator. 
       
       @param sequence sequence to store the items of this priority queue.
       @param comparator object which contains method isLessThan to compare keys of this priority queue.
    */
    public UnsortedSequencePriorityQueue(Sequence sequence, Comparator comparator) 
    {
	/* empty sequence */
        while (!sequence.isEmpty()) 
	{
            try 
	    {
                sequence.remove(sequence.first());
            } 
	    catch (Exception e) 
	    {
                System.err.println("Unexpected exception: " + e.getMessage());
            }
        }

        this.sequence = sequence;
        this.comparator = comparator;
    }

    /**
       Returns the key of the specified position.
      
       @param position position containing an Item.
       @return the key of the specified position.
    */
    private Object key(Position position)
    {
	return ((Item) position.element()). key();
    }

    /** 
       Returns the size of this priority queue. 
      
       @return the size of this priority queue.
    */
    public int size() 
    {
        return sequence.size();
    }

    /** 
       Tests if this priority queue is empty. 
      
       @return true if this priority queue is empty, false otherwise.
    */
    public boolean isEmpty() 
    {
        return sequence.isEmpty();
    }

    /**
       Adds the specified element with the specified key to the priority queue.
      
       @param key key of element to be added.
       @param element element to be added.
    */
    public void insertItem(Object key, Object element) throws InvalidKeyException 
    {
        if (!comparator.isComparable(key)) 
	{
            throw new InvalidKeyException("The key is not valid");
        }
        sequence.insertLast(new Item(key, element));
    }

    /**
       Returns a position of sequence with the minimal key.
      
       @return a position of sequence with the minimal key.
       @exception EmptyContainerException if the sequence is empty.
    */
    private Position minPosition() throws EmptyContainerException 
    {
        Position position = sequence.first(); // throws EmptyContainerException if sequence is empty
        Position minimum = sequence.first();
        while (position != sequence.last()) 
	{
            /* minimum is the position with the minimal key from the first
               position of sequence upto (and excluding) position */
            position = sequence.after(position);
            if (comparator.isLessThan(key(position), key(minimum)))
	    {
                minimum = position;
            }
	}
        return minimum;
    }

    /**
       Returns an element with the smallest key in this priority queue.
      
       @return element with the smallest key.
       @exception EmptyContainerException if this priority queue is empty.
    */
    public Object minElement() throws EmptyContainerException 
    {
        return ((Item) minPosition().element()).element();
    }

    /**
       Returns the smallest key in this priority queue.
      
       @return the smallest key.
       @exception EmptyContainerException if this priority queue is empty.
    */
    public Object minKey() throws EmptyContainerException 
    {
        return key(minPosition());
    }

    /**
       Removes an item with the smallest key from this priority queue
       and returns the element of the item.
      
       @return Element of an item with the smallest key.
       @exception EmptyContainerException if this priority queue is empty.
    */
    public Object removeMinElement() throws EmptyContainerException 
    {
        return ((Item) sequence.remove(minPosition())).element();
    }
}