#using <System.dll>

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

double Elapsed;

// ---------------------------------------------------------------------------
// SiftDown
// Purpose:
//   Restore the max-heap property below root in values[0..finish).
// Parameters:
//   values - list to mutate; root - subtree root; finish - exclusive heap end.
// Returns:
//   None.
// Variables used:
//   child, temp - child index and swap storage.
// ---------------------------------------------------------------------------
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;
	}
}

// ---------------------------------------------------------------------------
// LoadFile
// Purpose:
//   Read non-empty lines from a file and parse them as integers.
// Parameters:
//   fileSpec - input file path.
// Returns:
//   The populated list; I/O and parse errors propagate.
// Variables used:
//   values, line - accumulated values and current input line.
// ---------------------------------------------------------------------------
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;
}

// ---------------------------------------------------------------------------
// SaveFile
// Purpose:
//   Write the list to a file, one integer per line.
// Parameters:
//   values - list to write; fileSpec - output file path.
// Returns:
//   None.
// Variables used:
//   outputFile, value - output stream and current list item.
// ---------------------------------------------------------------------------
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.");
}

// ---------------------------------------------------------------------------
// PerformSort
// Purpose:
//   Sort values in place using heap sort and measure elapsed time.
// Parameters:
//   values - list to sort.
// Returns:
//   None; stores elapsed seconds in Elapsed.
// Variables used:
//   timer, start, finish, temp - stopwatch and heap traversal state.
// ---------------------------------------------------------------------------
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.");
}

// ---------------------------------------------------------------------------
// main
// Purpose:
//   Load, sort, and save the configured input data.
// Parameters:
//   None.
// Returns:
//   Process status 0 on completion.
// Variables used:
//   values - loaded and sorted list; Elapsed - sort duration.
// ---------------------------------------------------------------------------
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);
}