#using <System.dll>

using namespace System;
using namespace System::Collections::Generic;
using namespace System::Diagnostics;
using namespace System::IO;

double Elapsed;

void SiftDown(List<int>^ values, int root, int finish)
{
	while (2 * root + 1 < finish)
	{
		int child = 2 * root + 1;
		if (child + 1 < finish && values[child] < values[child + 1]) child++;
		if (values[root] >= values[child]) return;
		int temp = values[root];
		values[root] = values[child];
		values[child] = temp;
		root = child;
	}
}

List<int>^ LoadFile(String^ fileSpec)
{
	Console::Write("READING INPUT FILE...");
	List<int>^ values = gcnew List<int>();
	for each (String ^ line in File::ReadLines(fileSpec))
	{
		if (!String::IsNullOrWhiteSpace(line)) values->Add(Int32::Parse(line));
	}
	Console::WriteLine("DONE.");
	return values;
}

void SaveFile(List<int>^ values, String^ fileSpec)
{
	Console::Write("SAVING OUTPUT FILE...");
	StreamWriter^ outputFile = gcnew StreamWriter(fileSpec);
	for each (int value in values)outputFile->WriteLine(value);
	outputFile->Close();
	Console::WriteLine("DONE.");
}

void PerformSort(List<int>^ values)
{
	Console::Write("SORTING ELEMENTS...");
	Stopwatch^ timer = Stopwatch::StartNew();
	for (int start = values->Count / 2 - 1; start >= 0; start--) SiftDown(values, start, values->Count);
	for (int finish = values->Count - 1; finish > 0; finish--) {
		int temp = values[0];
		values[0] = values[finish];
		values[finish] = temp;
		SiftDown(values, 0, finish);
	}
	timer->Stop();
	Elapsed = timer->Elapsed.TotalSeconds;
	Console::WriteLine("DONE.");
}

int main()
{
	Console::WriteLine("***HEAPSORT C++ .NET***");
	List<int>^ values = LoadFile("D:/Sorting/Sorting_Input.txt");
	PerformSort(values);
	SaveFile(values, "D:/Sorting/Output_CPP.NET.txt");
	Console::WriteLine("***RUN COMPLETE***");
	Console::WriteLine("HEAPSORT TOOK {0:F6} SECONDS.", Elapsed);
}