#include <iostream>
#include "Profiler.h"
#define AVG_HEAPBUILD_BU_OP "HeapBuild_BottomUp_Operations_AverageCase"
#define AVG_HEAPBUILD_TD_OP "HeapBuild_TopDown_Operations_AverageCase"
#define AVG_HEAPBUILD_OP "HeapBuild_Operations_AverageCase"
using namespace std;
Profiler profiler("HeapSort");
int OP_BU, OP_TD;

void PrintArray(int* a, int n)
{
	for (int i = 0; i < n; i++)
		cout << a[i] << " ";
	cout << "\n";
}

int* generateAvgData(int n)
{
	int* a = (int*)malloc(n * sizeof(int));
	FillRandomArray(a, n);
	return a;
}

void Heapify(int* a, int n, int i)
{

	int root;
	int left = 2 * i + 1; //the left child of the node i is at (2*i+1) index
	int right = 2 * i + 2; //the right child of the node i is at (2*i+2) index

	if (left<n && a[left]>a[i]) //we check whether or not the left child is larger than the root and if it is, the root will take the index value of the left child
	{
		root = left;
		OP_BU++;
	}
	else root = i;
	if (left < n) OP_BU++;

	if (right<n && a[right]>a[root]) //we check whether or not the right child is larger than the root and if it is, the root will take the index value of the right child
	{
		root = right;
		OP_BU++;
	}
	if (right < n) OP_BU++;

	if (root != i)
	{

		swap(a[i], a[root]);
		OP_BU += 3;
		Heapify(a, n, root); //if the root doesn't have the same value as the initial value, then we swap the terms and recursively heapify the affected subtree
	}

}


void BottomUp(int* a, int n)
{
	for (int i = n / 2 - 1; i >= 0; i--)
		Heapify(a, n, i);
}

void TopDown(int* a, int n, int position, int* heap)
{
	int parent = (position - 1) / 2;
	int x = position;
	heap[position] = a[position];
	OP_TD++;
	while (position > 0 && heap[position] > heap[parent])
	{
		OP_TD++;
		//move parent down
		swap(heap[position], heap[parent]);
		OP_TD += 3;
		position = parent;
		parent = (position - 1) / 2;
	}
	if (position > 0) OP_TD++;

}

void HeapSort(int* a, int n)
{

	BottomUp(a, n);
	for (int i = n - 1; i >= 1; i--) //We move the root at the end and we make the lowest number the root and call the Heapify subprogram on the new heap
	{
		swap(a[0], a[i]);
		n--;
		OP_BU += 3;
		Heapify(a, n, 0);
	}
}

void BottomUpDemo()
{
	int a[7] = { 2, 5, 6, 1, 9, 4, 11 };
	BottomUp(a, 7);
	PrintArray(a, 7);
}

void TopDownDemo()
{
	int a[10] = { 2,9,7,6,5,8,10,3,6,9 };
	int* heap = (int*)malloc(10 * sizeof(int));
	for (int i = 0; i < 10; i++)
		TopDown(a, 10, i, heap);
	PrintArray(heap, 10);
}

void HeapSortDemo()
{
	int a[7] = {11, 5, 6, 1, 9, 4, 2 };
	HeapSort(a, 7);
	PrintArray(a, 7);
}

void generateCharts()
{
	for (int size = 100; size <= 10000; size += 500)
	{
		int Sum_Of_OP_BU=0, Sum_Of_OP_TD = 0;
		for (int i = 1; i <= 5; i++)
		{
			OP_BU = 0;
			OP_TD = 0;
			int* a = generateAvgData(size);
			int* b = (int*)malloc(size * sizeof(int));
			int* heap = (int*)malloc(size * sizeof(int));
			for (int j = 0; j < size; j++)
				b[j] = a[j];
			BottomUp(a, size);
			for (int j = 0; j < size; j++)
				TopDown(b, size, j, heap);
			free(b);
			Sum_Of_OP_BU += OP_BU;
			Sum_Of_OP_TD += OP_TD;
		}
		float media_OP_BU, media_OP_TD;
		media_OP_BU = (float)(Sum_Of_OP_BU / 5);
		media_OP_TD = (float)(Sum_Of_OP_TD / 5);
		profiler.countOperation(AVG_HEAPBUILD_BU_OP, size, media_OP_BU);
		profiler.countOperation(AVG_HEAPBUILD_TD_OP, size, media_OP_TD);
		profiler.createGroup(AVG_HEAPBUILD_OP, AVG_HEAPBUILD_BU_OP, AVG_HEAPBUILD_TD_OP);

	}
}


int main()
{
	BottomUpDemo();
	TopDownDemo();
	HeapSortDemo();
	generateCharts();
	profiler.showReport();

	return 0;
}