using System.IO;
using System.Collections.Generic;
using System.Windows.Markup;
using System.Diagnostics;

namespace Heapsort
{

    internal class Program
    {
        private static void SiftDown(List<int> values, int root, int end)
        {
            while(2 * root + 1 < end)
            {
                var child = 2 * root + 1;
                if (child + 1 < end && values[child] < values[child + 1]) child++;
                if (values[root] >= values[child]) return;
                (values[root], values[child]) = (values[child], values[root]);
                root = child;
            }
        }

        private static List<int> LoadFile(string fileSpec)
        {
            Console.Write("READING INPUT FILE...");
            var values = new List<int>();
            foreach(var line in File.ReadLines(fileSpec))
            {
                if (!string.IsNullOrWhiteSpace(line)) values.Add(int.Parse(line));
            }
            Console.WriteLine("DONE.");
            return values;
        }

        private static void SaveFile(List<int> values, string fileSpec)
        {
            Console.Write("WRITING OUPUT FILE...");
            File.WriteAllLines(fileSpec, values.ConvertAll(v => v.ToString()));
            Console.WriteLine("DONE.");
        }

        private static double PerformSort(List<int> values)
        {
            Console.Write("SORTING ELEMENTS...");
            var timer = Stopwatch.StartNew();
            for (var start = values.Count / 2 - 1; start >= 0; start--) SiftDown(values, start, values.Count);
            for(var end = values.Count -1; end > 0; end--)
            {
                (values[0], values[end]) = (values[end], values[0]);
                SiftDown(values, 0, end);
            }
            timer.Stop();
            Console.WriteLine("DONE.");
            return timer.Elapsed.TotalSeconds;
        }

        static void Main(string[] args)
        {
            Console.WriteLine("***HEAPSORT C#***");
            List<int> values = LoadFile("D:/Sorting/Sorting_Input.txt");
            double elapsed = PerformSort(values);
            SaveFile(values, "D:/Sorting/Output_CSHARP.txt");
            Console.WriteLine("***RUN COMPLETE***");
            Console.WriteLine("HEAPSORT TOOK {0:F6} SECONDS.", elapsed);
        }
    }
}