package DataStructures;

/**
 * Binary heap implementation of a priority queue, in which items of
 * the same priority are removed in order of insertion.<p>
 *
 * @see <a href="http://java.sun.com/products/j2se/1.5/docs/api/java/lang/Comparable.html">Comparable</a>
 * @see DataStructures.BinaryHeap
 * @param <E> the type of elements held in this heap
 * @author Peter Williams */

public class StrictBinaryHeap<E extends Comparable<? super E>> 
    implements PriorityQueue<E> {

    private BinaryHeap<HeapItem<E>> h;  // the heap
    private static int ticks = 0;       // the number of insertions so far

    private class HeapItem<E extends Comparable<? super E>> 
	implements Comparable<HeapItem<E>> {
        E item;
        int time;
        HeapItem(E item, int time) {
            this.item = item;
            this.time = time;
        }
        public int compareTo(HeapItem<E> other) {
            int result = item.compareTo(other.item);
            if (result == 0) { // items have same original priority
                result = other.time - time;
                // so earlier items now have higher priority
            }
            return result;
        }
    }
  
    /**
     * Constructs the binary heap.
     */
    public StrictBinaryHeap() {
        h = new BinaryHeap<HeapItem<E>>();
    }
  
    /**
     * Tests if the heap is empty.
     */
    public boolean isEmpty() {
        return h.isEmpty();
    }

    /**
     * Returns the current size of the queue.
     */
    public int size() {
        return h.size();
    }
  
    /**
     * Adds an item to the heap.
     */
    public void add(E item) {
        h.add(new HeapItem<E>(item, ticks++));
    }
  
    /**
     * Removes an item of highest priority item from the heap.<p>
     * 
     * If several items are currently of highest priority, returns them
     * in order of insertion.<p>
     *
     * @return the first item of highest priority that was inserted into the heap.
     * @exception NoSuchElementException if the heap is empty.
     */
    public E remove() {
        return h.remove().item;
    }

}