// Sample solution to lab 4, with Comparator + Comparable

import java.util.Comparator;

public class FlexQueue<T extends HeapValue<T>> extends BinHeap<T>
{
    @Override
    public void setComparator(Comparator<T> c)
    {
	if (c==null) return;
	cmp = c;
	heapify(); // must re-arrange the entire heap
    }
    
    @SuppressWarnings("unchecked")  // compiler directive (optional)
    public FlexQueue(int cap)    //
     { super();                  // calls default base constructor
       H = (T[]) new HeapValue[cap];
       size=0;
     }
    public FlexQueue(int cap, boolean invert) // option to invert comparator
    {
	this(cap);
	if (invert) cmp = (x,y)->y.compareTo(x); // invert comparator
    }
    
    public FlexQueue(T[] A)        // alternate constructor takes 
     {                             // external array, avoids compiler warning
       super(A);
     }
    public FlexQueue(T[] A, int s)
    {   if (A==null || A.length<1 || s<0 || s>=A.length)
	    throw new RuntimeException("invalid heap array");
	H = A;  size = s;
	heapify();  // implemented below
    }
    
    public void drawheap() // requires my heapdisplay.java program
    {
	//        heapdisplay W = new heapdisplay(1024,768);
	//        W.drawtree(H,size);
    }

    @SuppressWarnings("unchecked")  // compiler directive (optional)    
    @Override                       // guard against misspellings
    public void doublecap() // required override because of unchecked type cast
    {
	T[] H2 = (T[]) new HeapValue[H.length*2]; // compiler warning
	for(int i=0;i<size;i++) H2[i]=H[i];
	this.H = H2;
    } //all methods that recreates generic arrays must be overriden

    // This is the most important method to override, no need to override
    // swapup and swapdown.
    protected void swap(int i, int 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;
	H[i].setIndex(i);  H[k].setIndex(k);
    }

    // need to override to set initial index in object
    public void insert(T x) // alias enqueue
    {
	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
	H[size].setIndex(size);   // setindex inserted here for requeue
	size++;
	if (size>1) swapup(size-1);
    }//insert
    
    // will try to call superclass.deletetop, but there's some
    // repetitive code with checking the size.
    public T deletetop() // aliases dequeue, poll
    {
	if (size>=0) 
	    {
		H[size-1].setIndex(0);
		return super.deletetop();
	    }
	else throw new RuntimeException("Heap underflow");
	/*  from superclass.deletetop:
	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

    // REQUEUE:
    public void requeue(T x)
    {
	//if (x==null) return;  // should probably throw exception here
	int xi = x.getIndex();
	if (xi<0 || xi>=size || H[xi]!=x)
	    throw new RuntimeException("invalid heap index");
	int newi = swapup(xi);
	if (newi==xi) swapdown(xi); // only call if swapup didn't change xi
    }

    //HEAPIFY:
    public void heapify()
    {
	for(int i = size-1-(size+1)/2;i>=0;i--) // must go backwards
	    swapdown(i);
    }

    /*
    public static void main(String[] av)
    {
	// create heap of "Student" Objects
	FlexQueue<Student> SQ = new FlexQueue<Student>(10);

	Student isa = new Student("Isa Taparty",8);// keep pointer to a student
	SQ.insert(new Student("Nev Erstudy",16));
	SQ.insert(new Student("Haten Umbers",4)); // Haten has higher priority
	SQ.insert(isa);
	System.out.println("\nHighest prioirty student: "+SQ.peek());

	SQ.setComparator( (x,y)->y.compareTo(x) ); // invert comparator		
	// infer public class someclass implements Comparator<Student>
	// { public int compare(Student x, Student y) {return y.compareTo(x);}}
	System.out.println("Highest prioirty student now: "+SQ.peek());
	
	isa.setpriority(1);
	SQ.requeue(isa);   /// requeue called here
	System.out.println("Highest prioirty student now: "+SQ.peek());

    }//main
    */
}//FlexQueue

/*  for testing ...
// heapsort
class sorter<Type extends Comparable<Type>>
{
    public void heapsort(Type[] A)  
    {   // No extra array is used...
	BinHeap<Type> BH = new BinHeap<Type>(A);
	for(int i=0;i<A.length;i++) BH.enqueue(A[i]);
	for(int i=A.length-1;i>=0;i--) A[i] = BH.dequeue();
	// insert/delete from opposite ends to not interfere with heap ops
    } // could call O(n) heapify on A if it was implemented in BinHeap
}

// sample class of objects that can be inserted into a FlexQueue:
class Student implements HeapValue<Student>
{
    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
    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; }
}
*/