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

std::clock_t start_time;
std::clock_t end_time;

// ---------------------------------------------------------------------------
// SiftDown
// Purpose:
//   Restore the max-heap property below root in values[0..end).
// Parameters:
//   values - array to mutate; root - subtree root; end - exclusive heap end.
// Returns:
//   None.
// Variables used:
//   child - selected child index.
// ---------------------------------------------------------------------------
void SiftDown(std::vector<int>& values, int root, int end)
{
	while(2 * root + 1 < end) 
	{
		int child = 2 * root + 1;
		if(child + 1 < end && values[child] < values[child + 1]) child++;
		if(values[root] >= values[child]) return;
		std::swap(values[root], values[child]);
		root = child;
	}
}

// ---------------------------------------------------------------------------
// LoadFile
// Purpose:
//   Read non-empty lines from a file and parse them as integers.
// Parameters:
//   fileSpec - input file path.
// Returns:
//   The loaded vector; throws on open or parse errors.
// Variables used:
//   inputFile, line, parser, value - stream and parsing state.
// ---------------------------------------------------------------------------
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 interger in sorting input file.");
			values.push_back(value);
		}
	}
	inputFile.close();
	std::cout << "DONE." << std::endl;
	return values;
}

// ---------------------------------------------------------------------------
// SaveFile
// Purpose:
//   Write every vector element to a file, one per line.
// Parameters:
//   values - values to write; fileSpec - output file path.
// Returns:
//   None; throws if the output file cannot be opened.
// Variables used:
//   outputFile, v - output stream and vector index.
// ---------------------------------------------------------------------------
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 sorting output file.");
	for(std::size_t v=0;v<values.size();v++)
	{
		outputFile << values[v] << std::endl;
	}
	outputFile.close();
	std::cout << "DONE." << std::endl;
}

// ---------------------------------------------------------------------------
// PerformSort
// Purpose:
//   Sort values in place using max-heap construction and extraction.
// Parameters:
//   values - vector to sort.
// Returns:
//   None; records CPU clock ticks in start_time and end_time.
// Variables used:
//   start, end - heap indices; start_time, end_time - timing state.
// ---------------------------------------------------------------------------
void PerformSort(std::vector<int>& values)
{
	std::cout << "SORTING ELEMENTS...";
	start_time = std::clock();
	for(int start = static_cast<int>(values.size()) / 2 - 1; start >= 0; start--) SiftDown(values, start, values.size());
	for(int end = static_cast<int>(values.size()) - 1;end > 0; end--)
	{
		std::swap(values[0],values[end]);
		SiftDown(values, 0, end);
	}
	end_time = std::clock();
	std::cout << "DONE." << std::endl;
}

// ---------------------------------------------------------------------------
// main
// Purpose:
//   Load, sort, and save the configured input data.
// Parameters:
//   None.
// Returns:
//   Process status 0 on success.
// Variables used:
//   values - input and sorted data; seconds - displayed elapsed value.
// ---------------------------------------------------------------------------
int main()
{
	std::cout << "***HEAPSORT Borland C++***" << std::endl;
	std::vector<int> values = LoadFile("D:/Sorting/Sorting_Input.txt");
	PerformSort(values);
	SaveFile(values, "D:/Sorting/Output_BorlandCPP.txt");
	double seconds = (double)(end_time - start_time);
	std::cout << "***RUN COMPLETE***" << std::endl;
	std::cout << "HEAPSORT TOOK " << seconds << " SECONDS." << std::endl;
	return 0;
}