/*
 * This implementation of a heap priority queue builds the heap
 * top-down.  
 */

import java.io.*;
import java.util.*;

public class HeapPQ implements PriorityQueue
{	
	ArrayList heap;					//The array to store the heap
	Comparator comparator;			//The comparator to use
	
	/*
	 * HeapPQ() -
	 * create an empty heap priority queue
	 */
	public HeapPQ () {
		heap=new ArrayList();
		comparator=null;
	}
	
	/*
	 * HeapPQ(Comparator comparator)
	 * sets the comparator to use
	 */
	public HeapPQ (Comparator comparator) {
		this();
		this.comparator=comparator;
	}

	/*
	 * HeapPQ(Collection collection)
	 * creates a heap and fills it with the collection specified
	 */
	public HeapPQ (Collection collection) {
		heap=new ArrayList(collection.size());
		Iterator iter=collection.iterator();
		while (iter.hasNext()) {
			add(iter.next());
		}
		comparator=null;
	}
	
	/*
	 * Returns the size of the heap
	 * @return the size of the heap
	 */
	public int size () {
		return heap.size();
	}
	
	/*
	 * Returns an iterator for the heap
	 * @return an iterator for the heap
	 */
	public Iterator iterator() { 
     return Collections.unmodifiableList(heap).iterator(); 
     } 
	
	/*
	 * Adds an element to the heap and moves
	 * it to the proper location
	 * @return true if successful, false otherwise
	 */
	public boolean add (Object x) {
		//Add the element to the end of the array
		heap.add(x);
		//And bubble it up to the right location
		bubbleUp(heap.size()-1);
		return true;
	}
	
	/*
	 * Moves an item up to the proper location in the heap
	 */
	protected void bubbleUp(int index) {
		//If we're at the root, we're done
		if (index==0) return;
		//Calculate the index of your parent
		int parentIndex=(index-1)/2;
		Comparable child=(Comparable)heap.get(index);
		Comparable parent=(Comparable)heap.get(parentIndex);
		//If we are less than our parent, swap and keep bubbling
		if (compare(child,parent)<0) {
			heap.set(index,parent);
			heap.set(parentIndex,child);
			bubbleUp(parentIndex);
		}
	}

	public int compare(Comparable c1, Comparable c2) {
		if (comparator==null) {
			return c1.compareTo(c2);
		}
		else {
			return comparator.compare(c1,c2);
		}
	}
	
	/*
	 * Moves an item down to the proper location in the heap
	 */
	public void bubbleDown(int index) {
		int size=heap.size();

		//Calculate the indices for our children
		int lchild=index*2+1;
		//If there is no left child, just return
		if (lchild>(size-1)) return;
		int rchild=index*2+2;

		//Figure out which child is the smaller child
		Comparable parent=(Comparable)heap.get(index);

		//if there is only one child, use the left child
		Comparable child=(Comparable)heap.get(lchild);
		int childIndex=lchild;

		if (rchild<size) {
			//Check if the right child is smaller than the
			//left child, and if so, use that as the child
			//to compare with
			Comparable rightChild=(Comparable)heap.get(rchild);
			if (compare(rightChild,child)<0) {
				child=rightChild;
				childIndex=rchild;
			}
		}

		//If the we are larger than a child, swap with
		//the smaller child and keep bubbling
		if (compare(parent,child)>0) {
			heap.set(childIndex,parent);
			heap.set(index,child);
			bubbleDown(childIndex);
		}
	}
	
	/*
	 * Returns the first (lowest) object in the PQ.
	 * @return the first object
	 * @exception NoSuchElementException if the PQ is empty
	 */
	public Object getFirst () {
		//If the heap is empty, throw the proper exception
		if (heap.size()==0) {
			throw new NoSuchElementException("Priority Queue is empty!");
		}
		//Return the root element
		return heap.get(0);
	}
	
	/**
	 * Returns the first (lowest) object in the PQ and remove it.
	 * @return the first object
	 * @exception NoSuchElementException if the PQ is empty
	 */
	public Object removeFirst () {
		//If the heap is empty, throw the proper exception
		if (heap.size()==0) {
			throw new NoSuchElementException("Priority Queue is empty!");
		}
		//If there are more elements in the heap, swap
		//the last item to the root, and bubble down
		if (heap.size()>=2) {
			Object value=heap.get(0);
			heap.set(0,heap.remove(heap.size()-1));
			//And bubbleDown
			bubbleDown(0);
			return value;
		}
		//otherwise, just remove the first element
		else {
			return heap.remove(0);
		}
	}
	
	/**
	 * Returns the Comparator being used by this PQ, or null
	 * if the elements' natural order is being used.
	 * @return the Comparator being used
	 */
	public Comparator comparator () {
		return comparator;
	}
	
	/*
	 * clear() 
	 * just clear the heap
	 */
	public void clear () {
		heap.clear();
	}

	/*
	 * These methods are not required for HW5
	 */
	public boolean addAll(Collection c) {System.out.println("Not implemented!"); return false;}
	public boolean contains(Object o) {System.out.println("Not implemented!"); return false;}
	public boolean containsAll(Collection c) {System.out.println("Not implemented!"); return false;}
	public boolean equals(Object o) {System.out.println("Not implemented!"); return false;}
	public int hashCode() {System.out.println("Not implemented!"); return -1;} 
	public boolean isEmpty() {System.out.println("Not implemented!"); return false;}
	public boolean remove(Object o) {System.out.println("Not implemented!"); return false;}
	public boolean removeAll(Collection c) {System.out.println("Not implemented!"); return false;}
	public boolean retainAll(Collection c){System.out.println("Not implemented!"); return false;} 
	public Object[] toArray(){System.out.println("Not implemented!"); return null;} 
	public Object[] toArray(Object[] a) {System.out.println("Not implemented!"); return null;}
	
}