package no.uib.ii.inf102.f18.mandatory1;

import java.util.NoSuchElementException;

public class IndexMinPQ<Key extends Comparable<Key>> implements IIndexPQ<Key> {
    private int n;          //number of elements in PQ
    private int maxN;       //maximum number of elements in PQ
    private int[] pq;       //binary heap using 1-based indexing
    private int[] qp;       //inverse: qp[pg[i]] ? pq[qp[i]] = i
    private Key[] keys;     //items with priorities

    @SuppressWarnings("unchecked")
    public IndexMinPQ(int maxN) {
        keys = (Key[]) new Comparable[maxN + 1];
        pq = new int[maxN + 1];
        qp = new int[maxN + 1];
        for (int i = 0; i < maxN; i++) qp[i] = -1;
        /*
        if (maxN < 0) throw new IllegalArgumentException();
        this.maxN = maxN;
        n = 0;
        keys = (Key[]) new Comparable[maxN + 1];    // make this of length maxN??
        pq   = new int[maxN + 1];
        qp   = new int[maxN + 1];                   // make this of length maxN??
        for (int i = 0; i <= maxN; i++)
            qp[i] = -1;
        */
    }

    @Override
    public void add(int index, Key key) {
        //if (index < 0 || index >= maxN) throw new IllegalArgumentException();
        //if (!contains(index)) throw new NoSuchElementException("index is not in the priority queue");
        n++;
        qp[index] = n;
        pq[n] = index;
        keys[index] = key;
        swim(n);
    }

    @Override
    public void changeKey(int index, Key key) {
        //if (index < 0 || index >= maxN) throw new IllegalArgumentException();
        //if (!contains(index)) throw new NoSuchElementException("index is not in the priority queue");
        keys[index] = key;
        swim(qp[index]);
        sink(qp[index]);
    }

    @Override
    public boolean contains(int index) {
        return qp[index] != -1;
    }

    @Override
    public void delete(int index) {
        //if (index < 0 || index >= maxN) throw new IllegalArgumentException();
        //if (!contains(index)) throw new NoSuchElementException("index is not in the priority queue");
        int i = qp[index];
        exch(i, n--);
        swim(i);
        sink(i);
        keys[index] = null;
        qp[index] = -1;
    }

    @Override
    public Key getKey(int index) {
        return keys[index];
    }

    @Override
    public Key peekKey() {
        if (n == 0) return null;
        return keys[pq[n]];
    }

    @Override
    public int peek() {
        if (n == 0) return -1;
        return qp[1];
    }

    @Override
    public int poll() {
        if (n == 0) return -1;
        int min = pq[1];
        exch(1, n--);
        sink(1);
        assert min == pq[n+1];
        qp[min] = -1;
        keys[min] = null;
        pq[n+1] = -1;
        return min;
    }

    @Override
    public int size() {
        return n;
    }

    @Override
    public boolean isEmpty() {
        return n == 0;
    }

    private void exch(int i, int j) {
        int swap = pq[i];
        pq[i] = pq[j];
        pq[j] = swap;
        qp[pq[i]] = i;
        qp[pq[j]] = j;
    }

    private void swim(int k) {
        while (k > 1 && greater(k/2, k)) {
            exch(k, k/2);
            k = k/2;
        }
    }

    private void sink(int k) {
        while (2*k <= n) {
            int j = 2*k;
            if (j < n && greater(j, j+1)) j++;
            if (!greater(k, j)) break;
            exch(k, j);
            k = j;
        }
    }

    private boolean greater(int j, int i) {
        return keys[pq[i]].compareTo(keys[pq[j]]) > 0;
    }

}