/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */

package hw10;
import java.util.*;

/**
 *
 * @author kvaradar
 */
public class AdaptablePriorityQueue<K,V> {

    protected ArrayList<LocAwareEntry<K,V>> myHeap;
    protected Comparator<K> c;
    int size = 0;

    public AdaptablePriorityQueue () {
        myHeap = new ArrayList<LocAwareEntry<K,V>>();
        myHeap.add(0,null);
        c = new DefaultComparator<K>();
    }

    public AdaptablePriorityQueue( Comparator<K> comp) {
        myHeap = new ArrayList<LocAwareEntry<K,V>>();
        myHeap.add(0,null);
        c = comp;
    }


    public int size() {return size;}

    public boolean isEmpty() {return (size == 0);}

    public Entry<K,V> min() {return myHeap.get(1);}

    public Entry<K,V> removeMin() {
    	LocAwareEntry<K, V> tmp = myHeap.get(1);
        remove(tmp);
    	return tmp;
    }

	public Entry<K,V> remove(Entry<K,V> e) {

    	LocAwareEntry<K, V> tmp = (LocAwareEntry<K, V>) e; // Cast e as a LocAwareEntry
    	int loc = tmp.getLoc(); // Store the location of entry being removed
    	swap( loc, size ); // Swap the entry being removed with the last entry

    	LocAwareEntry<K, V> ptr = myHeap.get(loc); // Create a pointer to the last entry

    	myHeap.remove(size); // Remove the last entry from the arraylist
    	size--; // decrement size

    	// While key is smaller than parent key bubble up
    	while ( loc != 1 && c.compare(ptr.getKey(), myHeap.get(loc / 2).getKey()) < 0 ) {
    		swap (loc, loc/2);
    		loc /= 2;
    	}

    	// While children exist and keys are greater then the ptr key, bubble down
    	while ( loc * 2 <= size && (c.compare(ptr.getKey(), myHeap.get(loc * 2).getKey()) > 0 ||
    			( ((loc * 2) + 1) <= size && c.compare(ptr.getKey(), myHeap.get((loc * 2) + 1).getKey()) > 0))) {

    		int smallerChild = loc * 2; // set smallerChild to left child location

    		// If a right child exists and has a smaller key then the left child, set smallerChild to right loc
    		if ( ((loc * 2) + 1) <= size && c.compare(myHeap.get(loc * 2).getKey(), myHeap.get((loc * 2) + 1).getKey()) > 0 ) {
    			smallerChild = (loc * 2) + 1;
    		}

    		swap( loc, smallerChild ); // swap with smallerChild
    		loc = smallerChild; // set new location
    	}
       return tmp;
    }

    public K replaceKey(Entry<K,V> e, K k) {
        int smallerChild;
    	LocAwareEntry<K, V> tmp = (LocAwareEntry<K, V>) e;
    	K key = tmp.getKey();
    	tmp.setKey(k);
        int loc = tmp.getLoc();
        if ((loc != 1) && (c.compare(myHeap.get(loc).getKey(), myHeap.get(loc/2).getKey()) < 0)) {
            // violation with parent
            //fix the violation
            while ((loc != 1) && (c.compare(myHeap.get(loc).getKey(), myHeap.get(loc/2).getKey()) < 0)) {
                swap(loc,loc/2);
                loc = loc/2;
            }
        }
        else { // no violation with parent, so fix possible violation with descendants
            while(size >= 2*loc) { //while there is a child
                smallerChild = 2*loc;
                if ((size > 2*loc) && (c.compare(myHeap.get(2*loc + 1).getKey(), myHeap.get(2*loc).getKey()) < 0))
                    smallerChild = 2*loc + 1;
                if (c.compare(myHeap.get(loc).getKey(),myHeap.get(smallerChild).getKey()) <= 0)
                    break;
                else {
                    swap(loc,smallerChild);
                    loc = smallerChild;
                }
            }
        }
        //remove(tmp);
        //insert(k, tmp.getValue());
        return key;
    }

	public V replaceValue(Entry<K,V> e, V v){
        LocAwareEntry<K, V> tmp = (LocAwareEntry<K, V>) e;
        V value = tmp.getValue();
        tmp.setValue(v);
        return value;
    }

    public Entry<K,V> insert (K k, V v) {
        size++;
        LocAwareEntry<K,V> newEntry = new LocAwareEntry<K,V>(k,v,size);
        myHeap.add(size,newEntry);
        int i = size;
        int j;
        while (i > 1){
            // loop to fix heap invariant
            j = i/2; //parent of i
            if (c.compare(myHeap.get(i).getKey(),myHeap.get(j).getKey()) >= 0)
                break; // exit while loop once heap invariant is fixed
            else
                swap(i,j);
            i = j;
        }
        return newEntry;
    }

    private void swap(int i, int j) {
        // swap location aware entries in indices i and j of myHeap
        myHeap.get(i).setLoc(j);
        myHeap.get(j).setLoc(i);
        LocAwareEntry<K,V> temp = myHeap.get(i);
        myHeap.set(i,myHeap.get(j));
        myHeap.set(j,temp);
    }

    public String toString() {
        // returns a string representation of the keys in the heap
        // not designed with efficiency in mind
        String s;
        s = "[";
        if (size > 0) s+= myHeap.get(1).getKey();
        for (int i = 2; i <=size; i++)
            s+= "," + myHeap.get(i).getKey();
        return s + "]";
    }


}