#include <algorithm>
#include <ctime>
#include <fstream>
#include <iostream>
#include <stdexcept>
#include <sstream>
#include <string>
#include <vector>

int Heaps = 0;
int Insertions = 0;
int Intros = 0;

std::vector<int> LoadFile(const std::string& fileSpec)
{
	std::cout << "READING INPUT FILE...";
	std::ifstream inputFile(fileSpec.c_str());
	if(!inputFile) throw std::runtime_error("Unable to open sorting input file.");
	std::vector<int> values;
	std::string line;
	while(std::getline(inputFile,line))
	{
		if(!line.empty())
		{
			std::istringstream parser(line);
			int value;
			if(!(parser >> value)) throw std::runtime_error("Invalid integer in sorting input file.");
			values.push_back(value);
		}
	}
	inputFile.close();
	std::cout << "DONE." << std::endl;
	return values;
}

void SaveFile(std::vector<int> values, const std::string& fileSpec)
{
	std::cout << "SAVING OUTPUT FILE...";
	std::ofstream outputFile(fileSpec.c_str());
	if(!outputFile) throw std::runtime_error("Unable to open sorted output file.");
	for(std::size_t v=0;v<values.size();v++)
	{
		outputFile << values[v] << std::endl;
	}
	outputFile.close();
	std::cout << "DONE." << std::endl;
}

void SiftDown(std::vector<int>& values, int root, int start, int finish)
{
	while(start + 2 * (root - start) + 1 < finish)
	{
		int child = start + 2 * (root - start) + 1;
		if(child + 1 < finish && values[child] < values[child + 1]) child++;
		if(values[root] >= values[child])return;
		std::swap(values[root],values[child]);
		root = child;
	}
}

void Heapsort(std::vector<int>& values, int start, int finish)
{
	Heaps++;
	for(int root = start + (finish - start) / 2 - 1; root >= start; root--) SiftDown(values, root, start, finish);
	for(int last = finish - 1; last > start; last--)
	{
	  std::swap(values[start],values[last]);
	  SiftDown(values, start, start, last);	 
	}
}

void Insertionsort(std::vector<int>& values, int start, int finish)
{
	Insertions++;
	int value, pos;
	for(int index = start; index < finish; index++)
	{
		value = values[index];
		pos = index - 1;
		while(pos >= start && values[pos] > value)
		{
			values[pos + 1] = values[pos];
			pos--;
		}
		values[pos + 1] = value;
	}
}

int Partition(std::vector<int>& values, int start, int finish)
{
	int left = start;
	int right = finish - 1;
	int pivot = values[start + (finish - start) / 2];
	while (left <= right)
	{
		while(values[left] < pivot) left++;
		while(values[right] > pivot) right--;
		if(left <= right)
		{
			std::swap(values[left],values[right]);
			left++;
			right--;
		}
	}
	return left;
}

void Introsort(std::vector<int>& values, int start, int finish, int maxDepth)
{
	Intros++;
	int length = finish - start;
	if (length <= 1) return;
	if (length < 16) Insertionsort(values,start,finish);
	else if (maxDepth <= 0) Heapsort(values,start,finish);
	else
	{
		int partition = Partition(values, start, finish);
		Introsort(values, start, partition, maxDepth - 1);
		Introsort(values, partition, finish, maxDepth - 1);
	}
}

int log2(unsigned long x)
{
	int n = 0;
	while(x > 1)
	{
		x >>= 1;
		n++;
	}
	return n;
}

double PerformSort(std::vector<int>& values)
{
	std::cout << "SORTING ELEMENTS...";
	std::clock_t start_time = std::clock();
	int maxDepth = values.size() > 0 ? static_cast<int>(log2(values.size())) * 2 : 0;
	Introsort(values, 0, values.size(), maxDepth);
	std::clock_t end_time = std::clock();
	std::cout << "DONE." << std::endl;
	return (double)(end_time - start_time);
}

int main()
{
	std::cout << "=====INTROSORT Borland C++======" << std::endl;
	std::vector<int> values = LoadFile("D:/Sorting/Sorting_Input.txt");
	double elapsed = PerformSort(values);
	SaveFile(values, "D:/Sorting/Output_BorlandCPP.txt");
	std::cout << "==========RUN COMPLETE==========" << std::endl;
	std::cout << "INTROSORT TOOK " << elapsed << " SECONDS." << std::endl;
	std::cout << "================================" << std::endl;
	std::cout << "SORT CALLED | TIMES" << std::endl;
	std::cout << "------------+-------------------" << std::endl;
	std::cout << "Intro       | " << Intros << std::endl;
	std::cout << "Insertion   | " << Insertions << std::endl;
	std::cout << "Heap        | " << Heaps << std::endl;
	std::cout << "================================" << std::endl;
	return 0;
}