#include <iostream>
#include <time.h>
#include <string>
#include <fstream>
#include <stdio.h>

using namespace std;

void Swap(unsigned int i, unsigned int j, int A[])
{
	int z= A[i];
	A[i] = A[j];
	A[j] = z;
}

unsigned int Right(unsigned int i)
{
	return 2 * i + 1;
}

unsigned int Left(unsigned int i)
{
	return 2 * i;
}

void Sift(unsigned int p, unsigned int q, int A[])
{
	unsigned int k, l = Left(p), r = Right(p);

	if (l <= q && A[l] > A[p])
		k = l;
	else
		k = p;

	if (r <= q && A[r] > A[k])
		k = r;

	if (k != p)
    {
		Swap(k, p, A);   
		Sift(k, q, A);
    }
}

void Heapsort(int A[], unsigned int N)
{
	unsigned int r = N / 2 + 1;

	while (r > 1)
    {
        r = r - 1;
        Sift(r, N, A);
    }
      
	r = N;
	while (r > 1)
    {
        Swap(1, r, A);
        r = r - 1;    Sift(1, r, A); 
    }
}

#define DEBUG 0

int main()
{
	//Function declarations.
	int Nothing();
	int createList(int*&, bool, bool, int);

	srand(clock());   //Initializes the pseudo-random generator;

	const int NUMBER_OF_TIMES_FOR_CLOCK = 5;   //IMPORTANT: Number of times to repeat the test, to eliminate the possible clock error.
	const int NUMBER_OF_NEEDED_DOTS = 1000; 
	const int MAX_SIZE_OF_ARRAY = 100000;
	const int FREQUENCY_FOR_PROGRESS = 100;
	const std::string NAME_OF_OUTPUT_FILE = "heapsortresult.txt";   //Where we will print the results.

	clock_t initialTime = 0;
	clock_t finalTime = 0;
	clock_t runningTime = 0;
	clock_t uselessTime = 0;

	std::ofstream out(NAME_OF_OUTPUT_FILE.c_str());

	int dotCounter = 0;     //Variable that controls the number of dots written in the file.

	//While we don't have enough dots for the graph...
	for (; dotCounter < NUMBER_OF_NEEDED_DOTS; ++dotCounter)
	{
		int* A = 0;        //The array that will contain the numbers to sort.
		int* ref = 0;      //The array that will be used to reset A at each end of sort (because we need to repeat the sort...)
		int* dummyArr = 0; //The array that will be used to substract the affectation time.
		int size;          //The size of A.

		size = createList(ref, true, false, MAX_SIZE_OF_ARRAY);   //We create the array and we will obtain its size.

		A = new int[size];
		//We set A before the first sort...
		for (int i = 0 ; i < size; ++i)
		{
			A[i] = ref[i];
		}

		int loopCount = 0;      //Variable that counts the number of times we do the same treatment.

		//Start counting!
		initialTime = clock();

		while (loopCount != NUMBER_OF_TIMES_FOR_CLOCK)
		{
			//IMPORTANT: Put treatment between the two commentary lines.
			//------------------------------------------------
			Heapsort(A, size);

			//WARNING: We will need to substract all the time of the treatment below.
			for (int i = 0; i < size; ++i)
			{
				A[i] = ref[i];
			}
			//------------------------------------------------

			++loopCount;
		}

		//End counting!
		finalTime = clock();

		runningTime = finalTime - initialTime;  //runningTime is the number of ticks

		loopCount = 0;   //We reset the loop count, to eliminate all unnecessary time.

		if (DEBUG)
			printf("About to allocate a dummy array of size %d\n", size);

		dummyArr = new int[size];     //We need a dummy array, to eliminate all the time wasted by resetting A.

		if (DEBUG)
			printf("After allocating a dummy array of size %d\n", size);

		//Start counting!
		initialTime = clock();

		//Null job to eliminate all unneccesary time.
		while (loopCount != NUMBER_OF_TIMES_FOR_CLOCK)
		{
			Nothing();     //because of branching to heapSort  
			for (int i = 0; i < size; ++i)    //because of the resetting of A.
			{
				dummyArr[i] = ref[i];
			}
			++loopCount;   //because of the increment.
		}

		//Finish counting!
		finalTime = clock();

		uselessTime = finalTime - initialTime;
		finalTime = runningTime - uselessTime;

		//Proper deletion of used dynamic memory.
		delete[] dummyArr;
		delete[] ref;
		//delete[] A;

		initialTime = 0;
		finalTime = 0;
		runningTime = 0;
		uselessTime = 0;

		//We write in the file the size of the array and the time it took to sort it.
		out << size << " " << finalTime << " " << std::endl;

		if (dotCounter % FREQUENCY_FOR_PROGRESS == 0)
		{
			std::cout << "Wrote " << dotCounter << " dots" << std::endl;
		}
	}
	
	out.close();

	return 0;
}

//Generates a random number with a very low probability of having the upper bound as a result.
//The srand must be initialized in the main() function that calls it.
int generateRandomNumber(int upperBound)
{
	return (int) (((double) rand() / RAND_MAX) * upperBound);
}

//Creates a list with a random size and with random numbers, if desired.
//We can tell to this function if we want some numbers to be swapped, in order to nearly sort the list.
int createList(int*& arr, bool random, bool nearlySorted, int maxSize)
{
	int size = generateRandomNumber(maxSize);
	arr = new int[size];

	for (int i = 0; i < size; ++i)
	{
		if (random)
			arr[i] = generateRandomNumber(RAND_MAX);
		else
			arr[i] = i;
	}
	if (nearlySorted)
	{
		for (int i = 0; i < (size / 50); ++i)
		{
			Swap(generateRandomNumber(size-1), generateRandomNumber(size-1), arr);
		}
	}

	return size;
}

//Necessary to simulate a call, in order to substract it to the total time.
int Nothing()
{
	return 0;
}