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

namespace Heapsort
{

    internal class Program
    {
        // -------------------------------------------------------------------
        // SiftDown
        // Purpose:
        //   Restore the max-heap property below root in values[0..end).
        // Parameters:
        //   values - list to mutate; root - subtree root; end - exclusive heap end.
        // Returns:
        //   None.
        // Variables used:
        //   child - selected child index.
        // -------------------------------------------------------------------
        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;
            }
        }

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

        // -------------------------------------------------------------------
        // SaveFile
        // Purpose:
        //   Write all values to a file, one integer per line.
        // Parameters:
        //   values - list to write; fileSpec - output path.
        // Returns:
        //   None.
        // Variables used:
        //   v - current value being converted for output.
        // -------------------------------------------------------------------
        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.");
        }

        // -------------------------------------------------------------------
        // PerformSort
        // Purpose:
        //   Sort values in place using heap sort and measure elapsed time.
        // Parameters:
        //   values - list to sort.
        // Returns:
        //   Elapsed sort duration in seconds.
        // Variables used:
        //   timer, start, end - stopwatch and heap bounds.
        // -------------------------------------------------------------------
        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;
        }

        // -------------------------------------------------------------------
        // Main
        // Purpose:
        //   Load, sort, and save the configured input data.
        // Parameters:
        //   args - process command-line arguments (unused).
        // Returns:
        //   None.
        // Variables used:
        //   values - loaded/sorted data; elapsed - measured seconds.
        // -------------------------------------------------------------------
        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);
        }
    }
}