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

package adaptablepriorityqueue;
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() {
        // remove entry with smallest key, and return it
        return null;
    }

    public Entry<K,V> remove(Entry<K,V> e) {
        // remove entry e from the priority queue. You can
        // assume the entry is a valid LocAwareEntry.
        return null;
    }

    public K replaceKey(Entry<K,V> e, K k) {
        // replace the key of entry e in the priority queue with given key k, and
        // return old key. Assume entry is valid as before.
        return null;
    }

    public V replaceValue(Entry<K,V> e, V v){
        // replace the value of entry e in the priority queue with given
        // value v, and return old value
        return null;
    }


    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 respresentation 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 + "]";
    }
}