#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;

/*
 * -------------------------------------------------------------------
 * LoadFile
 * Purpose:
 *   Read non-blank integer records from the named input file into the program's collection or shared array.
 * Parameters:
 *   fileSpec - input or output file path.
 * Returns:
 *   The loaded integer sequence, or the count/status specified by this implementation.
 * Side effects:
 *   Opens and closes the input file; populates the collection or shared array and may update its element count.
 * -------------------------------------------------------------------
 */
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;
}

/*
 * -------------------------------------------------------------------
 * SaveFile
 * Purpose:
 *   Write the sorted integer collection or shared array to the named output file, one value per line.
 * Parameters:
 *   values - integer sequence being read, sorted, or written in place.
 *   fileSpec - input or output file path.
 * Returns:
 *   No value; writes the output file.
 * Side effects:
 *   Creates or replaces the output file and reports file progress.
 * -------------------------------------------------------------------
 */
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;
}

/*
 * -------------------------------------------------------------------
 * SiftDown
 * Purpose:
 *   Restore max-heap order below the specified root within the active heap range.
 * Parameters:
 *   values - integer sequence being read, sorted, or written in place.
 *   root - current root index in the heap portion.
 *   start - inclusive first index of the range being processed.
 *   finish - exclusive end index of the range being processed.
 * Returns:
 *   No value; rearranges the range in place.
 * Side effects:
 *   Mutates the sequence and may stop early once the heap property is restored.
 * -------------------------------------------------------------------
 */
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;
	}
}

/*
 * -------------------------------------------------------------------
 * Heapsort
 * Purpose:
 *   Sort the selected range in place with heapsort; introsort uses this as its worst-case fallback.
 * Parameters:
 *   values - integer sequence being read, sorted, or written in place.
 *   start - inclusive first index of the range being processed.
 *   finish - exclusive end index of the range being processed.
 * Returns:
 *   No value; sorts the range in place.
 * Side effects:
 *   Mutates the selected range and increments the heapsort counter where present.
 * -------------------------------------------------------------------
 */
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);	 
	}
}

/*
 * -------------------------------------------------------------------
 * Insertionsort
 * Purpose:
 *   Sort the selected range in place with insertion sort, the low-overhead path for short ranges.
 * Parameters:
 *   values - integer sequence being read, sorted, or written in place.
 *   start - inclusive first index of the range being processed.
 *   finish - exclusive end index of the range being processed.
 * Returns:
 *   No value; sorts the range in place.
 * Side effects:
 *   Mutates the selected range and increments the insertion-sort counter where present.
 * -------------------------------------------------------------------
 */
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;
	}
}

/*
 * -------------------------------------------------------------------
 * Partition
 * Purpose:
 *   Partition the selected range around its middle-element pivot, then return the first index of the right-hand range.
 * Parameters:
 *   values - integer sequence being read, sorted, or written in place.
 *   start - inclusive first index of the range being processed.
 *   finish - exclusive end index of the range being processed.
 * Returns:
 *   The first index of the right partition; both resulting ranges remain within the original bounds.
 * Side effects:
 *   Mutates the selected range in place; uses a middle element as pivot and advances inward scanning indices.
 * -------------------------------------------------------------------
 */
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;
}

/*
 * -------------------------------------------------------------------
 * Introsort
 * Purpose:
 *   Sort the selected range in place: use insertion sort for short ranges, heapsort when the depth budget is exhausted, otherwise partition and recurse.
 * Parameters:
 *   values - integer sequence being read, sorted, or written in place.
 *   start - inclusive first index of the range being processed.
 *   finish - exclusive end index of the range being processed.
 *   maxDepth - remaining partition-depth budget before the heapsort fallback.
 * Returns:
 *   No value; sorts the selected range in place.
 * Side effects:
 *   Mutates the selected range and updates the introsort counter; recursive calls reduce the depth budget.
 * -------------------------------------------------------------------
 */
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);
	}
}

/*
 * -------------------------------------------------------------------
 * log2
 * Purpose:
 *   Compute the integer base-2 size estimate used to initialize introsort's partition-depth budget.
 * Parameters:
 *   x - positive integer whose base-2 size estimate is computed.
 * Returns:
 *   An integer base-2 size estimate.
 * Side effects:
 *   Does not modify the input sequence.
 * -------------------------------------------------------------------
 */
int log2(unsigned long x)
{
	int n = 0;
	while(x > 1)
	{
		x >>= 1;
		n++;
	}
	return n;
}

/*
 * -------------------------------------------------------------------
 * PerformSort
 * Purpose:
 *   Choose an initial depth budget, run the top-level introsort, and measure its elapsed time.
 * Parameters:
 *   values - integer sequence being read, sorted, or written in place.
 * Returns:
 *   Elapsed time measured by this implementation.
 * Side effects:
 *   Starts/stops a timer, prints progress, and invokes introsort on the full sequence.
 * -------------------------------------------------------------------
 */
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);
}

/*
 * -------------------------------------------------------------------
 * main
 * Purpose:
 *   Program entry point: load the integer data, sort it, write the result, and report timing and algorithm call counts.
 * Parameters:
 *   None; this routine reads arguments from its enclosing context or shared state.
 * Returns:
 *   The program exit status, if the language/runtime defines one; otherwise no value.
 * Side effects:
 *   Performs file I/O, invokes sorting, and prints elapsed time and per-algorithm counters.
 * -------------------------------------------------------------------
 */
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;
}