package edu.caltech.cs2.datastructures;

import edu.caltech.cs2.interfaces.IDictionary;
import edu.caltech.cs2.interfaces.IPriorityQueue;

import java.util.Iterator;

public class MinFourHeap<E> implements IPriorityQueue<E> {

    private static final int DEFAULT_CAPACITY = 10;

    private int size;
    private PQElement<E>[] data;
    private IDictionary<E, Integer> keyToIndexMap;

    /**
     * Creates a new empty heap with DEFAULT_CAPACITY.
     */
    public MinFourHeap() {
        this.size = 0;
        this.data = new PQElement[DEFAULT_CAPACITY];
        this.keyToIndexMap = new ChainingHashDictionary<>(MoveToFrontDictionary::new);
    }

    @Override
    public void increaseKey(PQElement<E> key) {
        if(keyToIndexMap.get(key.data) == null) {
            throw new IllegalArgumentException();
        }
        int idx = keyToIndexMap.get(key.data);
        data[idx] = key;
        percD(data[idx]);
    }

    @Override
    public void decreaseKey(PQElement<E> key) {
        if(keyToIndexMap.get(key.data) == null) {
            throw new IllegalArgumentException();
        }
        int idx = keyToIndexMap.get(key.data);
        data[idx] = key;
        percU(data[idx]);
    }

    @Override
    public boolean enqueue(PQElement<E> epqElement) {
        if(data.length == size) {
            resize();
        }
        if(keyToIndexMap.containsKey(epqElement.data)) {
            throw new IllegalArgumentException();
        }
        keyToIndexMap.put(epqElement.data, size);
        data[size] = epqElement;
        percU(epqElement);
        size++;
        return true;
    }

    @Override
    public PQElement<E> dequeue() {
        PQElement<E> head = data[0];
        PQElement<E> tail = data[size - 1];
        data[0] = data[size - 1];
        keyToIndexMap.remove(head.data);
        data[size - 1] = null;
        size--;
        percD(tail);
        return head;
    }

    @Override
    public PQElement<E> peek() {
        return data[0];
    }

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

    @Override
    public Iterator<PQElement<E>> iterator() {
        return null;
    }

    private void resize() {
        PQElement<E>[] newArray = new PQElement[data.length * 2];
        for(int i = 0; i < data.length; i++) {
            newArray[i] = data[i];
        }
        data = newArray;
    }

    private void percU(PQElement<E> pq) {
        int idx = keyToIndexMap.get(pq.data);
        int parentIdx = (idx - 1)/4;
        while(data[parentIdx].priority > data[idx].priority) {
            PQElement<E> temp = data[idx];
            updateMap(data[parentIdx], idx);
            updateMap(data[idx], parentIdx);
            data[idx] = data[parentIdx];
            data[parentIdx] = temp;
            idx = parentIdx;
            parentIdx = (idx - 1)/4;
        }
    }

    private void percD(PQElement<E> pq) {
        while(getMinChild(pq) > - 1 && pq.priority > data[getMinChild(pq)].priority) {
            int idx = keyToIndexMap.get(pq.data);
            int smallestIdx = getMinChild(pq);
            PQElement<E> temp = data[smallestIdx];
            data[idx] = temp;
            updateMap(temp, idx);
            data[smallestIdx] = data[idx];
            updateMap(pq, smallestIdx);
        }
    }

    private int getMinChild(PQElement<E> pq) {
        int idx = keyToIndexMap.get(pq.data);
        int smallestIdx = idx * 4 + 1;
        if(smallestIdx > size) {
            return -1;
        }
        for(int i = idx * 4 + 1; i <= idx * 4 + 4 && i < size; i++) {
            if(data[smallestIdx].priority > data[i].priority) {
                smallestIdx = i;
            }
        }
        return smallestIdx;
    }

    private void updateMap(PQElement<E> pq, int newIndex) {
        if(keyToIndexMap.containsKey(pq.data)) {
            keyToIndexMap.remove(pq.data);
        }
        keyToIndexMap.put(pq.data, newIndex);
    }
}