/**
   The HeapPriorityQueue class implements the PriorityQueue 
   interface by means of a heap.  The heap is implemented by 
   means of an array.
  
   @author      Franck van Breugel
   @version     1.5    May 18, 2001
   @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;
    }        
   
    public int size() 
    {
        return size;
    }

    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);
             }
        }
    }

    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);
    }

    public Object minElement() throws EmptyContainerException 
    {
        if (isEmpty()) 
        {
            throw new EmptyContainerException("Priority queue is empty.");
        }
        return heap[1].element();
    }

    public Object minKey() throws EmptyContainerException 
    {
        if (isEmpty()) 
        {
            throw new EmptyContainerException("Priority queue is empty.");
        }
        return heap[1].key();
    }

    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);
    } 
}