Imports System.Collections.Generic
Imports System.Diagnostics
Imports System.IO

Module Heapsort

    ' -----------------------------------------------------------------------
    ' ReadFile
    ' Purpose:
    '   Read non-blank 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.
    ' -----------------------------------------------------------------------
    Function ReadFile(fileSpec As String) As List(Of Integer)
        Console.Write("READING INPUT FILE...")
        Dim values As New List(Of Integer)()
        For Each line In File.ReadLines(fileSpec)
            If Not String.IsNullOrWhiteSpace(line) Then
                values.Add(Integer.Parse(line))
            End If
        Next
        Console.WriteLine("DONE.")
        Return values
    End Function

    ' -----------------------------------------------------------------------
    ' SaveFile
    ' Purpose:
    '   Write all values to a file, one integer per line.
    ' Parameters:
    '   values - list to write; fileSpec - output path.
    ' Returns:
    '   None.
    ' Variables used:
    '   value - current item written by ConvertAll.
    ' -----------------------------------------------------------------------
    Sub SaveFile(values As List(Of Integer), fileSpec As String)
        Console.Write("SAVING OUTPUT FILE...")
        File.WriteAllLines(fileSpec, values.ConvertAll(Function(value) value.ToString()))
        Console.WriteLine("DONE.")
    End Sub

    ' -----------------------------------------------------------------------
    ' SiftDown
    ' Purpose:
    '   Restore the max-heap property below root in values[0..finish).
    ' Parameters:
    '   values - list to mutate; root - subtree root; finish - exclusive end.
    ' Returns:
    '   None.
    ' Variables used:
    '   child, temp - child selection and swap storage.
    ' -----------------------------------------------------------------------
    Sub SiftDown(values As List(Of Integer), root As Integer, finish As Integer)
        While 2 * root + 1 < finish
            Dim child = 2 * root + 1
            If child + 1 < finish AndAlso values(child) < values(child + 1) Then child += 1
            If values(root) >= values(child) Then Exit Sub
            Dim temp = values(root)
            values(root) = values(child)
            values(child) = temp
            root = child
        End While
    End Sub

    ' -----------------------------------------------------------------------
    ' PerformSort
    ' Purpose:
    '   Sort values in place using heap sort and measure elapsed time.
    ' Parameters:
    '   values - list to sort.
    ' Returns:
    '   Elapsed duration in seconds.
    ' Variables used:
    '   timer, start, finish, temp - stopwatch and heap traversal state.
    ' -----------------------------------------------------------------------
    Function PerformSort(values As List(Of Integer)) As Double
        Console.Write("SORTING ELEMENTS...")
        Dim timer = Stopwatch.StartNew()
        For start = values.Count \ 2 - 1 To 0 Step -1 : SiftDown(values, start, values.Count) : Next
        For finish = values.Count - 1 To 1 Step -1
            Dim temp = values(0)
            values(0) = values(finish)
            values(finish) = temp
            SiftDown(values, 0, finish)
        Next
        timer.Stop()
        Console.WriteLine("DONE.")
        Return timer.Elapsed.TotalSeconds
    End Function

    ' -----------------------------------------------------------------------
    ' Main
    ' Purpose:
    '   Load, sort, and save the configured input data.
    ' Parameters:
    '   None.
    ' Returns:
    '   None.
    ' Variables used:
    '   values - loaded/sorted data; elapsed - measured seconds.
    ' -----------------------------------------------------------------------
    Sub Main()
        Console.WriteLine("***HEAPSORT VB .NET***")
        Dim values = ReadFile("D:/Sorting/Sorting_Input.txt")
        Dim elapsed = PerformSort(values)
        SaveFile(values, "D:/Sorting/Ouput_VB.NET.txt")
        Console.WriteLine("***RUN COMPLETE***")
        Console.WriteLine("HEAPSORT TOOK {0:F6} SECONDS.", elapsed)
    End Sub
End Module