/**
 * The UnsortedSequencePriorityQueue class implements the PriorityQueue interface by means of
 * an unsorted sequence.
 *
 * @version     1.3    May 30, 2002
 * @author      Franck van Breugel
 * @see PriorityQueue
 * @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.
     * Throws an EmptyContainerException if the sequence is empty.
     *
     * @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.
     * Throws an EmptyContainerException if this priority queue is empty.
     *
     * @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.
     * Throws a EmptyContainerException if this priority queue is empty.
     *
     * @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.
     * Throws a EmptyContainerException if this priority queue is empty.
     *
     * @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();
    }
}