#using <System.dll>
#include <cmath>

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

int HeapSorts = 0;
int IntroSorts = 0;
int InsertionSorts = 0;

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 SiftDown(List<int>^ values, int root, int start, int end)
{
    while (start + 2 * (root - start) + 1 < end)
    {
        int child = start + 2 * (root - start) + 1;
        if (child + 1 < end && 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;
    }
}
void Heapsort(List<int>^ values, int start, int end)
{
    HeapSorts++;
    for (int root = start + (end - start) / 2 - 1; root >= start; root--)SiftDown(values, root, start, end);
    for (int last = end - 1; last > start; last--)
    {
        int temp = values[start];
        values[start] = values[last];
        values[last] = temp;
        SiftDown(values, start, start, last);
    }
}
void Insertionsort(List<int>^ values, int start, int end)
{
    InsertionSorts++;
    int value, pos;
    for (int index = start; index < end; index++)
    {
        value = values[index];
        pos = index - 1;
        while (pos >= start && values[pos] > value)
        {
            values[pos + 1] = values[pos];
            pos--;
        }
        values[pos + 1] = value;
    }
}
int Partition(List<int>^ values, int start, int end)
{
    int left = start;
    int right = end - 1;
    int pivot = values[start + (end - start) / 2];
    while (left <= right)
    {
        while (values[left] < pivot)left++;
        while (values[right] > pivot)right--;
        if (left <= right)
        {
            int temp = values[left];
            values[left] = values[right];
            values[right] = temp;
            left++;
            right--;
        }
    }
    return left;
}
void Introsort(List<int>^ values, int start, int end, int maxDepth)
{
    IntroSorts++;
    int length = end - start;
    if (length <= 1) return;
    if (length < 16)Insertionsort(values, start, end);
    else if (maxDepth <= 0)Heapsort(values, start, end);
    else
    {
        int partition = Partition(values, start, end);
        Introsort(values, start, partition, maxDepth - 1);
        Introsort(values, partition, end, maxDepth - 1);
    }
}
double PerformSort(List<int>^ values)
{
    Console::Write("SORTING ELEMENTS...");
    Stopwatch^ timer = Stopwatch::StartNew();
    int maxDepth = values->Count > 1 ? (int)std::log2(values->Count) * 2 : 0;
    Introsort(values, 0, values->Count, maxDepth);
    timer->Stop();
    Console::WriteLine("DONE.");
    return timer->Elapsed.TotalMilliseconds;
}
int main()
{
    Console::WriteLine("=======INTROSORT C++ .Net=======");
    List<int>^ values = LoadFile("D:/Sorting/Sorting_Input.txt");
    double elapsed = PerformSort(values);
    SaveFile(values, "D:/Sorting/Output_CPP_Net.txt");
    Console::WriteLine("==========RUN COMPLETE==========");
    Console::WriteLine("INTROSORT TOOK {0:F6} SECONDS.", elapsed);
    Console::WriteLine("================================");
    Console::WriteLine("SORT CALLED | TIMES");
    Console::WriteLine("------------+-------------------");
    Console::WriteLine("Intro       | {0}", IntroSorts);
    Console::WriteLine("Insertion   | {0}", InsertionSorts);
    Console::WriteLine("Heap        | {0}", HeapSorts);
    Console::WriteLine("================================");
}