/**
 * @file HeapAPI.c
 * @author Justin Brooks
 * @email jbrook09@mail.uoguelph.ca
 * @SN 0953640
 * @date July 2017
 * @brief File containing the function for the heap API
 */

#include <stdio.h>
#include <stdlib.h>
#include "HeapAPI.h"


Node *createHeapNode(void *data)
{
	if (data == NULL) return NULL;

	Node * node = malloc(sizeof(Node));
	node->data = data;
	node->pos = -1;

	return node;
}

Heap *createHeap(size_t initialSize, HEAP_TYPE htype, void (*destroyDataFP)(void *data),void (*printNodeFP)(void *toBePrinted),int (*compareFP)(const void *first, const void *second))
{
	Heap *heap = malloc(sizeof(Heap));

	heap->heap = calloc(initialSize, sizeof(Node *));
	heap->size = initialSize;

	heap->nextPosition = 0;

	heap->type = htype;

	heap->destroyData = destroyDataFP;

	heap->printNode = printNodeFP;

	heap->compare = compareFP;

	return heap;
}

Node *getParent(Heap *heap, Node *node)
{
	int pos = node->pos;
	int parentPos = PARENT(pos);

	if (parentPos > -1 && parentPos < heap->size) {
		return heap->heap[parentPos];
	}

	return NULL;
}

Node *getLeftChild(Heap *heap, Node *node)
{
	int pos = node->pos;
	int parentPos = LEFT(pos);

	if (parentPos > 0 && parentPos < heap->size) {
		return heap->heap[parentPos];
	}

	return NULL;
}

Node *getRightChild(Heap *heap, Node *node)
{
	int pos = node->pos;
	int parentPos = RIGHT(pos);

	if (parentPos > 0 && parentPos < heap->size) {
		return heap->heap[parentPos];
	}

	return NULL;
}

void insertHeapNode(Heap *heap, void *data)
{
	if (data == NULL) return;
	if (heap == NULL) return;

	int nextPosition = heap->nextPosition;

	if (nextPosition < heap->size) {

		Node *node = createHeapNode(data);
		node->pos = nextPosition;

		heap->heap[nextPosition] = node;
		heap->nextPosition++;

		reheapify(heap, node);
	}
}

void swap(Node *a, Node *b)
{
	if (a == NULL || b == NULL) return;

	void *tempData = a->data;
	a->data = b->data;
	b->data = tempData;
}

void changeHeapType(Heap *heap)
{
	if (heap == NULL) return;

	if (heap->type == MAX_HEAP) {
		heap->type = MIN_HEAP;
	} else {
		heap->type = MAX_HEAP;
	}

	sortHeap(heap);
}

void sortHeap(Heap *heap)
{

	if (heap == NULL || heap->nextPosition == 0) return;

	int i;
	int size = heap->size;

	for (i = PARENT(size); i >= 0; --i) {
		Node *tempNode = heap->heap[i];
		if (tempNode != NULL) {
			heapify(heap, size, tempNode);
		}
	}
	for(i = size - 1; i >= 0; --i) {
		if (heap->heap[i] != NULL) {
			swap(heap->heap[0], heap->heap[i]);
			heapify(heap, i, heap->heap[0]);
		}
	}
}

void heapify(Heap *heap, int size, Node *root)
{
	int (*compareFP)(const void *first, const void *second) = heap->compare;

	Node *left = getLeftChild(heap, root);
	Node *right = getRightChild(heap, root);

	if (heap->type == MIN_HEAP) {

		Node *largest = root;

		if (left != NULL && left->data != NULL) {
			if (left->pos < size && compareFP(left->data, largest->data) > 0) {
				largest = left;
			}
		}

		if (right != NULL && right->data != NULL) {
			if (right->pos < size && compareFP(right->data, largest->data) > 0) {
				largest = right;
			}
		}

		if (largest != root) {
			swap(root, largest);
			heapify(heap, size, largest);
		}

	} else {

		Node *smallest = root;

		if (left != NULL && left->data != NULL) {
			if (left->pos < size && compareFP(smallest->data, left->data) > 0) {
				smallest = left;
			}
		}

		if (right != NULL && right->data != NULL) {
			if (right->pos < size && compareFP(smallest->data, right->data) > 0) {
				smallest = right;
			}
		}

		if (smallest != root) {
			swap(root, smallest);
			heapify(heap, size, smallest);
		}
	}
}

void deleteHeap(Heap *heap)
{
	int i, size = heap->size;
	void (*destroyDataFP)(void *data) = heap->destroyData;

	for(i = 0; i < size; i++) {
		Node *node = heap->heap[i];
		if (destroyDataFP != NULL) destroyDataFP(node->data);
		free(node);
	}

	free(heap->heap);
	free(heap);
}

void deleteMinOrMax(Heap *heap)
{
	if (heap == NULL) return;

	heap->nextPosition --;

	void (*destroyDataFP)(void *data) = heap->destroyData;
	int (*compareFP)(const void *first, const void *second) = heap->compare;

	if (heap->nextPosition == 0) {

		if (destroyDataFP != NULL) destroyDataFP(heap->heap[0]->data);
		free(heap->heap[0]);
		heap->heap[heap->nextPosition] = NULL;
		return;
	}

	Node *first = heap->heap[0];
	Node *last = heap->heap[heap->nextPosition];

	swap(first, last);

	if (destroyDataFP != NULL) destroyDataFP(last->data);

	free(last);
	heap->heap[heap->nextPosition] = NULL;

	if (heap->type == MIN_HEAP) {
		for(;;) {

			Node *leftChild = getLeftChild(heap, first);
			Node *rightChild = getRightChild(heap, first);

			if (leftChild != NULL
				&& rightChild != NULL
				&& compareFP(first->data, leftChild->data) > 0
				&& compareFP(first->data, rightChild->data) > 0) {

				if (compareFP(rightChild->data, leftChild->data) > 0) {

					swap(leftChild, first);
					first = leftChild;

				} else {
					swap(rightChild, first);
					first = rightChild;
				}


			} else if (leftChild != NULL && compareFP(first->data, leftChild->data) > 0) {

				swap(leftChild, first);
				first = leftChild;

			} else if (rightChild != NULL && compareFP(first->data, rightChild->data) > 0) {

				swap(rightChild, first);
				first = rightChild;

			} else {
				break;
			}
		}
	} else {
		for(;;) {

			Node *leftChild = getLeftChild(heap, first);
			Node *rightChild = getRightChild(heap, first);



			if (leftChild != NULL
				&& rightChild != NULL
				&& compareFP(first->data, leftChild->data) < 0
				&& compareFP(first->data, rightChild->data) < 0) {

				if (compareFP(rightChild->data, leftChild->data) < 0) {
					swap(leftChild, first);
					first = leftChild;
				} else {
					swap(rightChild, first);
					first = rightChild;
				}

			} else if (leftChild != NULL && compareFP(first->data, leftChild->data) < 0) {

				swap(leftChild, first);
				first = leftChild;

			} else if (rightChild != NULL && compareFP(first->data, rightChild->data) < 0) {

				swap(rightChild, first);
				first = rightChild;

			} else {
				break;
			}
		}
	}

}

void *getMinOrMax(Heap *heap)
{
	if (heap == NULL) return NULL;
	if (heap->size == 0) return NULL;
	if (heap->nextPosition == 0) return NULL;

	Node *node = heap->heap[0];
	if (node == NULL) return NULL;

	void (*printNodeFP)(void *toBePrinted) = heap->printNode;

	if (heap->printNode != NULL) printNodeFP(node->data);

	return node->data;
}

void reheapify(Heap *heap, Node *node)
{

	if (heap == NULL) return;
	if (node == NULL) return;

	int (*compareFP)(const void *first, const void *second) = heap->compare;

	Node *parent = getParent(heap, node);

	if (heap->type == MIN_HEAP) {

		while (compareFP(node->data, parent->data) < 0) {

			if (parent->pos == node->pos) break;

			swap(node, parent);

			node = parent;
			parent = getParent(heap, node);
		}

	} else {

		while (compareFP(node->data, parent->data) > 0) {

			if (parent->pos == node->pos) break;

			swap(node, parent);

			node = parent;
			parent = getParent(heap, node);
		}
	}
}