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

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

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

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

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

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