/* Base class for Lab 4
   Requires heapdisplay for graphical display of heap (used in main)

   The BinHeap base class uses an array (T[] H) to implement a
   Prioirty Queue with the highest priority value on top of the heap.
   The BinHeap class implements the following principal functions:

   public int size() // returns number of values in heap
   public int capacity() // returns current capacity of heap
   public T[] getArray() // returns H array (for heapdisplay calls)
   public void doublecap() // doubles capacity of heap, called by insert
   protected int left, right, parent(int i): calculates indices
   protected void swap(int i, int k): swap H[i] with H[k]
   protected int swapup(int i): swap H[i] upwards if necessary
   protected int swapdown(int i): swap H[i] downwards if necessary
   public void enqueue(T x): insert x into heap, O(log n) worst, O(1) average
   public T dequeue(): delete and return top value, O(log n)
   public T peek(): return top (highest priority) value without delete, O(1)
   public boolean Contains(T x): search for x by .equals, O(n)
        Note: x.equals(y) != (x.compareTo(y)==0)
*/

// This version of the heap places the largest priority value on top.
public class BinHeap<T extends Comparable<T>>
{
    protected T[] H; // the heap array underneath
    protected int size; // number of values in heap
    public int size() { return size; }
    public int capacity() { return H.length; }

    @SuppressWarnings("unchecked")  /*compiler directive, not real code*/
    public BinHeap(int cap)// constructor initializes array
    {
	if (cap<1) throw new RuntimeException("invalid heap capacity");
	H = (T[]) new Comparable[cap]; // compiler warning
	size = 0;
    }
    public BinHeap(T[] A)// alt constructor takes external array
    {   if (A==null || A.length<1)
	    throw new RuntimeException("invalid heap array");
	H = A; size=0;
    }
    public BinHeap() {} // obligatory default constructor: needed if
                        // other constructors exist (java specific)


    @SuppressWarnings("unchecked")  /*compiler directive, not real code*/    
    public void doublecap() // double capacity of heap (resize)
    {
	T[] H2 = (T[]) new Comparable[H.length*2]; // compiler warning
	for(int i=0;i<size;i++) H2[i]=H[i];
	this.H = H2;
    } // need to override in subclass because of unchecked type cast

    // Index calculations with root always at 0 **
    protected int left(int i) { return 2*i+1; }
    protected int right(int i) { return 2*i+2; }
    protected int parent(int i) { return (i-1)/2; }

    // swap H[i] with H[k]:
    protected void swap(int i, int k) // swap H[i] with H[k]
    {
	if (i<0 || i>=size || k<0 || k>=size) return; // don't swap
	T tmp = H[i]; H[i]=H[k]; H[k]=tmp;
    }
    
    // separate swap up/down procedures (size must be set correctly)
    protected int swapup(int i)// swap up value at index i, returns new index
    {
	if (i<0 || i>=size || H[i]==null)
	    throw new RuntimeException("invalid swapup index: "+i);
	int p = parent(i);
	while(i>0 && H[i].compareTo(H[p])>0)
	    {
		swap(i,p);
		i = p;
		p = parent(p);
	    }//while
	return i; // new position of original H[i], not used
    }//swapup
    
    protected int swapdown(int i) // size must be preset to correct value
    {
	if (i<0 || i>=size || H[i]==null)
	    throw new RuntimeException("invalid swapdown index: "+i);
	int si = 0; // must be non-neg to start loop
	while (si>=0)  // si is the "swap candidate index"
	    {
		si = -1; // -1 means no swap
		int li = left(i), ri=right(i);
		if (li<size && H[li].compareTo(H[i])>0) si = li;
		if (ri<size && H[ri].compareTo(H[i])>0 && H[ri].compareTo(H[li])>0) si = ri;
		if (si != -1) {
		    swap(i,si);
		    i = si; // move i down
		}
	    }//while can swap
	return i; // new position of original H[i], not used
    }//swapdown

    // insert or enqueue, worst cast O(log n), average O(1)
    public void enqueue(T x) { insert(x); } // alias
    public void insert(T x)
    {
	if (x==null) throw new RuntimeException("null can't be inserted");
	if (size+1>=H.length) doublecap();
	H[size] = x;  // temporarily place at bottom of heap
	size++;
	if (size>1) swapup(size-1);
    }//insert

    //delete top value, O(log n) worst and average
    public T dequeue() { return deletetop(); } // aliases
    public T poll() { return deletetop(); }    
    public T deletetop() // return highest
    {
	if (size<1) throw new RuntimeException("Heap underflow");
	T answer = H[0]; // value to be returned
	H[0] = H[size-1];  // move last value to top, temporarily
	H[size-1] = null;  // removes duplicate pointer
	size--;         // make sure this is called after the swap
	if (size>1) swapdown(0); //reposition(0);
	return answer;
    }//deletetop
    public T peek() // return top value without delete
    {
	if (size<1) throw new RuntimeException("Heap underflow");
	else return H[0];
    }

    // should override with better version (though it'll still be O(n))
    public boolean Contains(T x) 
    {
	for(T y:H) if (x.equals(y)) return true;
	return false;
    } 
    // worst case O(n).

    public T[] getArray() { return H; } // access to underlying array
	                                // needed by heapdisplay calls
    /* ///    for testing
    public static void main(String[] av)
    {
	int n = 200;
	BinHeap<Integer> PQ = new BinHeap<Integer>(1);
	while (n-->=0) PQ.insert( (int)(Math.random()*n*n) );
	System.out.println("Q capacity is "+PQ.capacity());
	heapdisplay W = new heapdisplay(1024,768);
	W.drawtree(PQ.getArray(),PQ.size); // draws array as complete bin. tree
	while (PQ.size()>0) System.out.print(PQ.poll()+" ");

	// create heap of "Student" Objects
	BinHeap<Student> SQ = new BinHeap<Student>(10);
	SQ.insert(new Student("Nev Erstudy",1));
	SQ.insert(new Student("Haten Umbers",4)); // Haten has higher priority
	SQ.insert(new Student("Isa Taparty",2));
	System.out.println("\nHighest prioirty student: "+SQ.peek());
	// But what if the priority of an object can change? ...
    }//main
    */
}//BinHeap

/*  Sample HeapValue class
class Student implements HeapValue<Student> // HeapValue extends Comparable
{
    int priority;  // some priority, used to define compareTo
    int index;     // for getIndex and setIndex (not same as priority)
    String name;   // something that represents arbitrary info in the object
    double gpa;    // boring stuff related to student, etc..
    public Student(String n, int p) {name=n; priority=p; } // constructor
    public int compareTo(Student x)  // implementation of Comparable
    { return priority - x.priority; }
    public int getIndex() { return index; }  // implementation of HeapValue
    public void setIndex(int i) {index=i; }
    public void setpriority(int p) { priority=p; } // change priority
    public String toString() {return priority+":"+name; }
}
*/