package se.chalmers.cs.gf.graph;

import java.util.Comparator;
import java.util.ArrayList;

/**
 *  A priority queue implemented with heap.
 */
public class HeapPriorityQueue<K,V> implements PriorityQueue<K,V> {
   
        private static final int DEFAULT_CAPACITY = 16;

        private Comparator<K> comp;

        private ArrayList<Entry<K,V>> vec;

        public HeapPriorityQueue(Comparator<K> comp) {
                this(comp, DEFAULT_CAPACITY);
        }

        public HeapPriorityQueue(Comparator<K> comp, int n) {
                this.comp = comp;

                // want capacity = 2^m && capacity >= n
                // that is, n rounded up to the nearest power of 2
                int capacity = 2;
                while (capacity < n)
                        capacity *= 2;

                vec = new ArrayList<Entry<K,V>>(capacity);
                vec.add(null); // first position is empty
        }

        public static <K extends Comparable<K>,V> HeapPriorityQueue<K,V> create() {
                return new HeapPriorityQueue<K,V>(new NaturalComparator<K>());
        }

        public static <K extends Comparable<K>,V> HeapPriorityQueue<K,V> create(int n) {
                return new HeapPriorityQueue<K,V>(new NaturalComparator<K>(), n);
        }

        public static <K,V> HeapPriorityQueue<K,V> create(Comparator<K> comp) {
                return new HeapPriorityQueue<K,V>(comp);
        }

        public static <K,V> HeapPriorityQueue<K,V> create(Comparator<K> comp, int n) {
                return new HeapPriorityQueue<K,V>(comp, n);
        }

        private int first() { return 1; }
        private int last() { return size(); }
        private int left(int i) { return i * 2; }
        private int right(int i) { return i * 2 + 1; }
        private int parent(int i) { return i / 2; }
        private boolean isInternal(int i) { return i >= first() && i <= last(); }
        private int compare(int i, int j) { 
                return comp.compare(vec.get(i).key, vec.get(j).key); 
        }

        private void swap(int i, int j) {
                Entry<K,V> tmp = vec.get(i);
                vec.set(i, vec.get(j));
                vec.set(j, tmp);
        }

        public void insertItem(K key, V element) {
                vec.add(new Entry<K,V>(key, element));

                // bubble up
                int i = last();
                while (i != first()) {
                        int p = parent(i);
                        if (compare(i, p) >= 0)
                                break;
                        swap(i,p);
                        i = p;
                }
        }

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

        public V minElement() {
                if (isEmpty())
                        return null;
                return vec.get(first()).element;
        }

        public K minKey() {
                if (isEmpty())
                        return null;
                return vec.get(first()).key;
        }

        public V removeMin() {
                if (isEmpty())
                        return null;

                V e = vec.get(first()).element;
                Entry<K,V> last = vec.remove(vec.size()-1);
                if (isEmpty())
                        return e;
                vec.set(first(), last);

                // bubble down
                int i = first();
                while (isInternal(left(i))) { // done when both children are external
                        int c; 
                        int l = left(i);
                        int r = right(i);
                        if (!isInternal(r)) {
                                // only left is internal
                                c = l;
                        } else {
                                // both are internal, pick the smallest
                                c = (compare(l, r) <= 0) ? l : r;
                        }
                        // is heap-order property satisfied?
                        if (compare(i, c) <= 0)
                                break;
                        swap(i, c);
                        i = c;
                }

                return e;
        }

        public int size() {
                return vec.size() - 1;
        }


        private static class Entry<K,V> {
                public K key;
                public V element;
                public Entry(K key, V element) {
                        this.key = key;
                        this.element = element;
                }
                public String toString() { return key + " => " + element; }
        }

}