COP 3530
Section U02
Spring 2015


                       The PriorityQueue Class
                       =======================



import java.util.AbstractCollection;
import java.util.Queue;
import java.util.Comparator;
import java.util.NoSuchElementException;
import java.util.Collection;
import java.util.Queue;
import java.util.Iterator;


public class PriorityQueue<T> extends AbstractCollection<T>
             implements Queue<T>
{

    // the fields
    private int currentSize; // the number of elements in the heap
    private T[] array; // the heap array
    private Comparator<? super T> cmp;
    private static final int DEFAULT_CAPACITY = 100;

    /** Construct an empty PriorityQueue */
    public PriorityQueue()
    {
        currentSize = 0;
        cmp = null;
        array = (T[]) new Object[DEFAULT_CAPACITY + 1];
    }

    /* Construct an empty priority queue with a specific comparator */
    public PriorityQueue( Comparator <? super T> c)
    {
        currentSize = 0;
        cmp = c;
        array = (T[]) new Object[DEFAULT_CAPACITY + 1];
    }

    /* Construct a priority queue from another collection */
    public PriorityQueue(Collection<? extends T> coll)
    {
        cmp = null;
        currentSize = coll.size();
        array = (T[]) new Object[ (currentSize + 2) * 11/10];

        int i = 1;
        for ( T item: coll)
            array[i++] = item;
        buildHeap();
        for (int j = 0; j <= currentSize; j++)
            System.out.println(array[j]);
    }

    // return the current size
    public int size()
    {
        return currentSize;
    }

    // empty the priority queue
    public void clear()
    {
        currentSize = 0;
    }

    // construct an iterator
    public Iterator<T> iterator()
    {
        // ...
        return null;
    }

    // returns the smallest item in the priority queue
    // @throws NoSuchElementException if the queue is empty
    public T element()
    {
        if (isEmpty())
            throw new NoSuchElementException();
        return array[1];
    }

    // peek is required by the interface Queue
    // @returns the head or null if the queue is empty
     public T peek()
    {
        if (isEmpty())
            return null;
        return array[1];
    }

    // poll is required by the interface queue
    // remove the head of the list
    // @returns the smallest item in the priority queue
    //  @returns null if the queue is empty
    public T poll()
    {
        if (isEmpty())
            return null;
        T minItem = array[1];
        array[1] = array[currentSize--];
        percolateDown(1);

        return minItem;
    }

    
    
    // offer is required by the interface Queue
    // it is the same as add
    public boolean offer(T x)
    {
        return add(x);
    }

    // add an element to the priority queue
     // return true
    public boolean add( T x)
    {
        if (currentSize + 1 == array.length )
            doubleArray();
        // percolate up
        int hole = ++currentSize;
        array[0] = x;

        for (; compare(x, array[hole/2]) < 0; hole /= 2)
            array[hole] = array[hole/2];
        array[hole] = x;
        return true;
    }

    // removes the smallest item in the priority queue
    // @throws NoSuchElementException if empty
    public T remove()
    {
        T minItem = element();
        array[1] = array[currentSize--];
        percolateDown(1);

        return minItem;
    }

    // remove the item at index i
    // if i is not a valid subscript, throw a no such element exception
    // return the replaced item
    public T remove(int i)
    {
        // check if i is legal
        if (i < 1 || i > currentSize)
            throw new NoSuchElementException("No such element");
        if (i == 1)
            return remove();
        // save array[i]
        T out = array[i];
        array[i] = array[currentSize--];
        // percolate up or down ?
        if (compare(array[i],array[i/2]) > 0)
            percolateDown(i); // percolate down
        else // percolate up
        {
            // percolate up
            int hole = i;
            array[0] = array[i];
            for (; compare(array[0], array[hole/2]) < 0; hole /= 2)
                array[hole] = array[hole/2];
            array[hole] = array[0];
        }    
        return out;
    }        
    
    // print the queue
    public void printQueue()
    {
        if (currentSize == 0)
            System.out.println("Empty queue");
        else
        {
            for (int i = 1; i <= currentSize; i++)
                System.out.println(array[i]);
        }    
    }    
    
    // internal method to percolate down in the heap
    // @param hole is the index at which the percolate begins
    private void percolateDown( int hole)
    {
        int child;
        T tmp = array[hole];

        for (; hole * 2 <= currentSize; hole = child)
        {
            child = hole * 2;
            if (child != currentSize &&
                   compare(array[child+1], array[child]) < 0)
                child++;
            if (compare(array[child], tmp) < 0)
                array[hole] = array[child];
            else
                break;
        }
        array[hole] = tmp;
    }

    // establish the heap property for an arbitrary arrangement of items
    private void buildHeap()
    {
        for (int i = currentSize / 2 ; i > 0; i--)

            percolateDown(i);
    }

    private void doubleArray()
    {
        // ...
    }
    
    // from figure 19.70
    private int compare(T lhs, T rhs)
    {
        if ( cmp == null)
            return ((Comparable) lhs).compareTo(rhs);
        else
            return cmp.compare(lhs,rhs);
    }

    // return true if it is empty and false otherwise
    public boolean isEmpty()
    {
        return currentSize == 0;
    }

}