heappqueue

#include "HeapPQueue.h"
#include "Testing/HeapTests.h"
#include "vector.h"
using namespace std;

HeapPQueue::HeapPQueue() {
    elems = new DataPoint[100];
    allocatedSize = 100;
    logicalSize = 0;
}

HeapPQueue::~HeapPQueue() {
    delete[] elems;

}

void HeapPQueue::grow() {
    allocatedSize *= 2;

    DataPoint* newElems = new DataPoint[allocatedSize];

    for (int i = 0; i < logicalSize; i++) {
        newElems[i] = elems[i];
    }

    delete[] elems;
    elems = newElems;
}

void HeapPQueue::enqueue(const DataPoint& data) {

    if (logicalSize == allocatedSize) {
        grow();
    }
    elems[logicalSize] = data;

    int numRows = determineRow(logicalSize+1);
    logicalSize++;
    int a = logicalSize;
    for (int i = 0; i < numRows; i++){
        int b = (a/2);
        if (b != 0){
            b--;
        }
        if (elems[b].weight > elems[a-1].weight){
            DataPoint temp = elems[a-1];
            elems[a-1] = elems[b];
            elems[b] = temp;
            a = b+1;
        }

    }
}

int HeapPQueue::size() const {
    return logicalSize;
}

DataPoint HeapPQueue::peek() const {
    if (isEmpty()) {
        error("You cannot peek at an empty queue");
    }
    return elems[0];
}

DataPoint HeapPQueue::dequeue() {
    if (isEmpty()) {
        error("You cannot dequeue an empty queue");
    }
    int size = logicalSize;
    DataPoint smallestValue = elems[0];
    elems[0] = elems[size-1];
    elems[size-1] = smallestValue;
    logicalSize--;
    int numRows = determineRow(logicalSize);
    int j = 0;

    for (int i = 0; i < numRows-1; i++) {
        int left = 2*j+1;
        int right = 2*j+2;


        if (logicalSize > right) {
                if (elems[left].weight >= elems[right].weight && (elems[j].weight > elems[right].weight)) {
                    DataPoint tempValue = elems[j];
                    elems[j] = elems[right];
                    elems[right] = tempValue;
                    j = right;
                }

                else if (elems[j].weight > elems[left].weight){
                    DataPoint tempValue = elems[j];
                    elems[j] = elems[left];
                    elems[left] = tempValue;
                    j = left;
                }
        }
        else if ((logicalSize == right) && (elems[j].weight > elems[left].weight)) {
            DataPoint tempValue = elems[j];
            elems[j] = elems[left];
            elems[left] = tempValue;
            j = left;
        }
    }
    logicalSize++;
    DataPoint dequeuedElem = elems[logicalSize-1];
    logicalSize--;
    return dequeuedElem;

}

bool HeapPQueue::isEmpty() const {
    return size() == 0;
}

/* This function is purely for you to use during testing. You can have it do whatever
 * you'd like, including nothing. We won't call this function during grading, so feel
 * free to fill it with whatever is most useful to you!
 *
 * TODO: Delete this comment and replace it with one describing what this function
 * actually does.
 */
void HeapPQueue::printDebugInfo() {
    /* TODO: Delete this comment and (optionally) put debugging code here. */
}