/**
 * The HeapPriorityQueue class implements the PriorityQueue 
 * interface by means of a heap.  The heap is implemented by 
 * means of an array.
 *
 * @version     1.5    May 18, 2001
 * @author      Franck van Breugel
 * @see PriorityQueue
 * @see Comparator
 * @see Item
 */
public class HeapPriorityQueue implements PriorityQueue 
{
    public static final int CAPACITY = 1000;  // default maximal capacity of this priority queue

    private Item[] heap;                      // array containing the items of this priority queue
    private int capacity;                     // maximal capacity of this priority queue
    private int size;                         // size of this priority queue
    private Comparator comparator;            // contains method isLessThan to compare keys

    /** 
     * Constructs a priority queue of default capacity with specified 
     * comparator. 
     * @param comparator Comparator containing method isLessThan
     * to compare keys.
     */
    public HeapPriorityQueue(Comparator comparator) 
    {
        this(CAPACITY, comparator);
    } 

    /** 
     * Constructs a priority queue of specified capacity with specified 
     * comparator.  
     * If the specified capacity is negative, the default capacity is 
     * used instead.
     * @param capacity the capacity of the priority queue.
     * @param comparator Comparator containing method isLessThan
     * to compare keys.
     */
    public HeapPriorityQueue(int capacity, Comparator comparator) 
    {
        if (capacity < 0) 
        {
            capacity = CAPACITY;
        }
        this.heap = new Item[capacity + 1]; // level number 0 is not used
        this.capacity = capacity;
        this.comparator = comparator;
        this.size = 0;
    }        
   
    /** 
     * Returns the size of this priority queue. 
     * @return The size of this priority queue.
     */
    public int size() 
    {
        return size;
    }

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

    /**
     * Swaps the items in the heap with the specified level numbers.
     * @param first Level number of item to be swapped.
     * @param second Level number of item to be swapped.
     */
    private void swap(int first, int second) 
    {
        Item temp = heap[first];
        heap[first] = heap[second];
        heap[second] = temp;
    }

    /**
     * Item with specified level number is bubbled up.
     * @param index Level number of item to be bubbled up.
     */
    private void bubbleUp(int index) 
    {
        if (index != 1) 
        {
             int parent = index / 2;
             if (comparator.isLessThan(heap[index].key(), heap[parent].key())) 
             {
                 swap(index, parent);
                 bubbleUp(parent);
             }
        }
    }

    /**
     * Item with specified level number is bubbled down.
     * @param index Level number of item to be bubbled down.
     */
    private void bubbleDown(int index) 
    {
        if (2 * index <= size) 
        {
             int child;
             if (2 * index == size) 
             {
                 child = 2 * index;
             } 
             else if (comparator.isLessThan(heap[2 * index].key(), heap[2 * index + 1].key())) 
             {
                 child = 2 * index;
             } 
             else 
             {
                 child = 2 * index + 1;
             }
             if (comparator.isLessThan(heap[child].key(), heap[index].key())) 
             {
                 swap(index, child);
                 bubbleDown(child);
             }
        }
    }

    /**
     * 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 PriorityQueueFullException, InvalidKeyException 
    {
        if (size >= capacity) 
        {
            throw new PriorityQueueFullException("Priority queue overflow.");
        }
        if (!comparator.isComparable(key)) 
        {
            throw new InvalidKeyException("The key is not valid");
        }
        size++;
        heap[size] = new Item(key, element);
        bubbleUp(size);
    }

    /**
     * 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 
    {
        if (isEmpty()) 
        {
            throw new EmptyContainerException("Priority queue is empty.");
        }
        return heap[1].element();
    }

    /**
     * Returns the smallest key in this priority queue.
     * Throws an EmptyContainerException if this priority queue is empty.
     * @return The smallest key.
     * @exception EmptyContainerException if this priority queue is empty.
     */
    public Object minKey() throws EmptyContainerException 
    {
        if (isEmpty()) 
        {
            throw new EmptyContainerException("Priority queue is empty.");
        }
        return heap[1].key();
    }

    /**
     * Removes an item with the smallest key from this priority queue
     * and returns the element of the item.
     * Throws an 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 
    {
        if (isEmpty()) 
        {
            throw new EmptyContainerException("Priority queue is empty.");
        }
        Object element = heap[1].element();
        swap(1, size);
        heap[size] = null;
        size--;
        bubbleDown(1);
        return element;
    }

    /**
     * Returns a string representation of the subtree of the heap
     * rooted at the specified level number.
     * @param index The level number of the root of the subtree.
     * @return A string representation of the subtree of the heap
     * rooted at the specified level number.
     */
    private String preorderPrint(int index) 
    {
        String string;
        if (heap[index] == null || index > size) 
        {
            return " ";
        } 
        else 
        {
            return (heap[index].toString() + "(" + preorderPrint(2 * index) + "," + preorderPrint(2 * index + 1) + ")");
        }
    }

    /**
     * Returns a string representation of the heap.
     * @returns A string representation of the heap.
     */
    public String toString() 
    {
        return preorderPrint(1);
    } 

}