/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */
package Priority_queue;

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

/**
 * An implementation of a priority queue using an array-based heap.
 *
 * @author Michael T. Goodrich
 * @author Roberto Tamassia
 * @author Michael H. Goldwasser
 *
 * @author antoniosilva
 *
 */
public class HeapPriorityQueue<K, V> extends AbstractPriorityQueue<K, V> {

    /**
     * primary collection of priority queue entries
     */
    protected ArrayList<Entry<K, V>> heap = new ArrayList<>();

    /**
     * Creates an empty priority queue based on the natural ordering of its
     * keys.
     */
    public HeapPriorityQueue() {
        super();
    }

    /**
     * Creates an empty priority queue using the given comparator to order keys.
     *
     * @param comp comparator defining the order of keys in the priority queue
     */
    public HeapPriorityQueue(Comparator<K> comp) {
        super(comp);
    }

    /**
     * Creates a priority queue initialized with the respective key-value pairs.
     * The two arrays given will be paired element-by-element. They are presumed
     * to have the same length. (If not, entries will be created only up to the
     * length of the shorter of the arrays)
     *
     * @param keys an array of the initial keys for the priority queue
     * @param values an array of the initial values for the priority queue
     */
    public HeapPriorityQueue(K[] keys, V[] values) {
        super();
        for (int j = 0; j < Math.min(keys.length, values.length); j++) {
            heap.add(new PQEntry<>(keys[j], values[j]));
        }
        buildHeap();
    }

    // protected utilities
    protected int parent(int j) {
        return (j - 1) / 2;
    }     // truncating division

    protected int left(int j) {
        return 2 * j + 1;
    }

    protected int right(int j) {
        return 2 * j + 2;
    }

    protected boolean hasLeft(int j) {
        return left(j) < heap.size();
    }

    protected boolean hasRight(int j) {
        return right(j) < heap.size();
    }

    /**
     * Exchanges the entries at indices i and j of the array list.
     */
    protected void swap(int i, int j) {
        Entry<K, V> temp = heap.get(i);
        heap.set(i, heap.get(j));
        heap.set(j, temp);
    }

    /**
     * Moves the entry at index j higher, if necessary, to restore the heap
     * property.
     */
    protected void percolateUp(int j) {
        int index = parent(j);
        while (index != 0 && compare(heap.get(j), heap.get(index)) < 0) {
            swap(j, index);
            j = index;
            index = parent(j);
        }
    }

    /**
     * Moves the entry at index j lower, if necessary, to restore the heap
     * property.
     */
    protected void percolateDown(int i) {
        int indLeft = 2 * i + 1;
        int indRight = 2 * i + 2;
        boolean swaps = true;
        while (indLeft < heap.size() && swaps) {
            int smallindex = indLeft;
            if (indRight < heap.size()) {
                if (compare(heap.get(indRight), heap.get(indLeft)) < 0) {
                    smallindex = indRight;
                }
            }
            if (compare(heap.get(i), heap.get(smallindex)) > 0) {
                swap(i, smallindex); //change	the	elem	by	the
                i = smallindex; //child	with	the	highest
                indLeft = 2 * i + 1;
                indRight = 2 * i + 2;
            } else {
                swaps = false;
            }
        }
    }

    /**
     * Performs a batch bottom-up construction of the heap in O(n) time.
     */
    protected void buildHeap() {
        throw new UnsupportedOperationException("Not supported yet.");
    }

    // public methods
    /**
     * Returns the number of items in the priority queue.
     *
     * @return number of items
     */
    @Override
    public int size() {
        return heap.size();
    }

    /**
     * Returns (but does not remove) an entry with minimal key.
     *
     * @return entry having a minimal key (or null if empty)
     */
    @Override
    public Entry<K, V> min() {
        return heap.get(heap.size() - 1);
    }

    /**
     * Inserts a key-value pair and return the entry created.
     *
     * @param key the key of the new entry
     * @param value the associated value of the new entry
     * @return the entry storing the new key-value pair
     * @throws IllegalArgumentException if the key is unacceptable for this
     * queue
     */
    @Override
    public Entry<K, V> insert(K key, V value) throws IllegalArgumentException {
        PQEntry<K, V> temp = new PQEntry<>(key, value);
        heap.add(temp);
        percolateUp(heap.size() - 1);
        return temp;
    }

    /**
     * Removes and returns an entry with minimal key.
     *
     * @return the removed entry (or null if empty)
     */
    @Override
    public Entry<K, V> removeMin() {
        swap(0, heap.size() - 1);
        Entry<K, V> e = heap.remove(heap.size() - 1);
        percolateDown(0);
        return e;
    }

    public ArrayList<Entry<K, V>> getHeap() {
        return heap;
    }

    @Override
    public String toString() {
        System.out.println("flag");
        for (Entry<K, V> entry : heap) {
            System.out.println(entry.getKey() + "entry: " + entry.getValue() + "\n");
        }
        return "";
    }

    public void sort(ArrayList<V> vector) {
        int size = heap.size();
        for (int i = 0; i < size; i++) {
            vector.add(i, removeMin().getValue());
        }
    }

    @Override
    public HeapPriorityQueue<K, V> clone() {
        HeapPriorityQueue<K, V> heapAux = new HeapPriorityQueue<>();
        for (Entry<K, V> entry : heap) {
            heapAux.insert(entry.getKey(), entry.getValue());
        }
        return heapAux;
    }

    public HeapPriorityQueue<K, V> newHeap(HeapPriorityQueue<K, V> heap2, K value) {
        int i = 0;
        for (Entry<K, V> entry : this.heap) {
            if(!entry.getKey().equals(value)) {
                heap2.insert(entry.getKey(), entry.getValue());
            }
        }
        return heap2;
    }

}