#include "HeapADT.h"
#include <string>

using namespace std;

template <typename E> class Heap : public HeapADT<E>
{
private:
    E* heap;
    int maxSize;
    int n;
    template<typename Comp>
    void siftdown(int pos) {
        while (!isLeaf(pos)) {
            int j = left(pos);
            int rc = right(pos);
            if ((rc < n) && Comp::prior(heap[rc], heap[j])){
                j = rc;
            }
            if (Comp::prior(heap[pos], heap[j])){ return; }
            swap(heap, pos, j);
            pos = j;
        }
    }
    void heapfy(int pos){
        int temp, leftTemp, rightTemp, heapTemp;
        leftTemp = left(pos);
        rightTemp = right(pos);

        if((heap[pos] < heap[leftTemp]) || (heap[pos]< heap[rightTemp]))        {

            if(heap[leftTemp] > heap[rightTemp])            {
                swap(heap[pos], pos, leftTemp);
                heapTemp = leftTemp;
            }

            else            {
                swap(heap[pos],pos,rightTemp);
                heapTemp = rightTemp;
            }
            heapfy(heapTemp);
        }
    }
public:
    Heap(E* h, int num, int max)     {
        heap = h;
        n = num;
        maxSize = max;
        buildMaxHeap();
    }
    void swap(E A[], int i, int j) {
        E aux = heap[i];
        heap[i] = heap[j];
        heap[j] = aux;
    }
    int size() const{
        return n;
    }
    bool isLeaf(int pos) const     {
        return (pos >= n/2) && (pos < n);
    }
    int left(int pos) const  {
        return 2*pos + 1;
    }
    int right(int pos) const  {
        return 2*pos + 2;
    }
    int parent(int pos) const  {
        return (pos-1)/2;
    }
    void buildMaxHeap()  {
        for (int i=n/2-1; i>=0; i--) {
            siftdown(i);
        }
    }
    template<typename Comp>
    void insert(const E& it) {
        if (n < maxSize) {
            int curr = n++;
            heap[curr] = it;

            while ((curr!=0) &&
                   (Comp::prior(heap[curr], heap[parent(curr)]))) {
                swap(heap, curr, parent(curr));
                curr = parent(curr);
            }
        }
        else{
            string strAux = "Heap is full!";
            return strAux;
        }
    }
    E removefirst() {
        if(n > 0){
            swap(heap, 0, --n);
            if (n != 0){
                siftdown(0);
            }
            return heap[n];
        }
        else{
            string strAux = "Heap is empty";
            return strAux;
        }
    }
    template<typename Comp>
    E remove(int pos) {
        if((pos >= 0) && (pos < n)){
            if (pos == (n-1)){
                n--; }

            else
            {
                swap(heap, pos, --n);
                while ((pos != 0) &&
                       (Comp::prior(heap[pos], heap[parent(pos)]))) {
                    swap(heap, pos, parent(pos));
                    pos = parent(pos);
                }
                if (n != 0) {
                    siftdown(pos);
                }
            }
            return heap[n];
        }
        else{
            string strAux = "Bad position";
            return strAux;
        }
    }
};