//
//  Ioan Ivanov
//  Partners: Liam Dwindell and Jack Cottrell
//  November 7th, 2019
//  This file consists of the functions for the BinHeap lab

// Screenshot
// https://gyazo.com/e4bab6a64a10e45ba1bb3f4c248e03f7

// First word: The Ghost of Xunantunich
// Second word: Samhainophobia - A fear for Halloween
// There is no third word


#include "BinHeap.hpp"
#include <string>
#include <iostream>
#include <stdlib.h>
using namespace std;

BinHeap::BinHeap(string arr[], int len) {
    heaplen = 0;
    arrlen = len;
    heap = new string[arrlen];
    for(int i = 0; i < len; i++) {
        insertHeap(arr[i]);

    }
    printHeap();
}

BinHeap::~BinHeap() {
    delete [] heap;
}

void BinHeap::printHeap() {
    cout << endl;
    for(int i = 0; i < arrlen; i++) {
        cout << i << ", ";
    }
    cout << endl;
    for(int i = 0; i < heaplen; i++) {
        cout << heap[i] << ", ";
    }
    cout << endl;
}

int BinHeap::findMax(int x, int y) {
    if((x < heaplen) && (y < heaplen)) {
        if(heap[x] > heap[y]) {
            return(x);

        } else {
            return(y);

        }

    } else if(x < heaplen) {
        return x;

    } else {
        return -1;
    }
}

void BinHeap::insertHeap(string s) {
    if(heaplen == arrlen){
        cout << "Heap is full" << endl;
        return;
    }
    heaplen++;
    int i = heaplen;
    heap[i] = s;
    bubbleUp(i);
}

string BinHeap::deleteHeap() {
    string last_element = heap[heaplen-1];
    string first_element = heap[0];
    heap[0] = last_element;
    heaplen -= 1;
    bubbleDown(0);

    return first_element;
}

void BinHeap::bubbleUp(int i) {
    if(i && heap[parent(i)] < heap[i]) {
        swap(heap[i], heap[parent(i)]);
        bubbleUp(parent(i));
    }
}

void BinHeap::bubbleDown(int i) {
    int left = leftChild(i);
    int right = rightChild(i);
    int largest = i;
    if(left < heaplen && heap[left] > heap[i]) {
        largest = left;
    }
    if(right < heaplen && heap[right] > heap[largest]) {
        largest = right;
    }
    if(largest != i) {
        swap(heap[i], heap[largest]);
        bubbleDown(largest);
    }
}

string BinHeap::deleteHeap2() {
    string last_element = heap[heaplen-1];
    string first_element = heap[0];
    heap[0] = last_element;
    heap[heaplen-1] = first_element;
    heaplen -= 1;
    bubbleDown(0);

    return first_element;
}

void BinHeap::deleteAll() {
    int temp = heaplen;
    for(int i = 0; i < temp; i++){
    deleteHeap2();
    }
}

int BinHeap::parent(int i) {
    return (i - 1) / 2;
}

int BinHeap::leftChild(int i) {
    return (2 * i + 1);
}

int BinHeap::rightChild(int i) {
    return (2 * i + 2);
}