<# ---------------------------------------------------------------------------
Read-File
Purpose:
    Read non-blank lines from a file and parse them as integers.
Parameters:
    FilePath - path to the input file.
Returns:
    A custom object containing the integer list in its Values property.
Variables used:
    values - parsed integers; line - current input line.
--------------------------------------------------------------------------- #>
function Read-File {
    param([string] $FilePath)
    Write-Host "READING INPUT FILE..."
    $values = [Collections.Generic.List[int]]::new()
    foreach ($line in [IO.File]::ReadLines($FilePath)) {
        if (-not [string]::IsNullOrWhiteSpace($line)) {
            $values.Add([int]::Parse($line))
        }
    }
    Write-Host "DONE."
    return [PSCustomObject]@{ Values = $values }
}

<# ---------------------------------------------------------------------------
Save-File
Purpose:
    Write each integer in Values to a file on its own line.
Parameters:
    Values - integer list to write; FilePath - output file path.
Returns:
    None.
Variables used:
    None beyond the parameters.
--------------------------------------------------------------------------- #>
function Save-File {
    param(
        [Collections.Generic.List[int]] $Values,
        [string] $FilePath
    )
    Write-Host "WRITING OUTPUT FILE..."
    [IO.File]::WriteAllLines($FilePath, [string[]] $Values)
    Write-Host "DONE."
}

<# ---------------------------------------------------------------------------
Sift-Down
Purpose:
    Restore the max-heap property below Root within Values[0..End).
Parameters:
    Values - list to mutate; Root - subtree root; End - exclusive heap end.
Returns:
    None; mutates Values in place.
Variables used:
    child - index of the larger child.
--------------------------------------------------------------------------- #>
function Sift-Down {
    param(
        [Collections.Generic.List[int]] $Values,
        [int] $Root,
        [int] $End
    )
    while (2 * $Root + 1 -lt $End) {
        $child = 2 * $Root + 1
        if ($child + 1 -lt $End -and $Values[$child] -lt $Values[$child + 1]) {
            $child++
        }
        if ($Values[$Root] -ge $Values[$child]) {
            return
        }
        $Values[$Root], $Values[$child] = $Values[$child], $Values[$Root]
        $Root = $child
    }
}

<# ---------------------------------------------------------------------------
Invoke-Heapsort
Purpose:
    Sort Values in place using heap sort and measure elapsed time.
Parameters:
    Values - integer list to sort.
Returns:
    Elapsed sort duration in seconds.
Variables used:
    timer - stopwatch; start/end - heap bounds during heap construction/extraction.
--------------------------------------------------------------------------- #>
function Invoke-Heapsort {
    param([Collections.Generic.List[int]] $Values)
    Write-Host "SORTING ELEMENTS..."
    $timer = [System.Diagnostics.Stopwatch]::StartNew()
    for ($start = [math]::Floor($Values.Count / 2) - 1; $start -ge 0; $start--) {
        Sift-Down $Values $start $Values.Count
    }
    for ($end = $Values.Count - 1; $end -gt 0; $end--) {
        $Values[0], $Values[$end] = $Values[$end], $Values[0]
        Sift-Down $Values 0 $end
    }
    $timer.Stop()
    Write-Host "DONE."
    return $timer.Elapsed.TotalSeconds
}

<# ---------------------------------------------------------------------------
Main script
Purpose:
    Load, sort, and save the configured input data, then report elapsed time.
Parameters:
    None; input and output paths are configured in the script.
Returns:
    None.
Variables used:
    wrapper - object returned by Read-File; values - data to sort; elapsed - seconds.
--------------------------------------------------------------------------- #>
Write-Host "***HEAPSORT POWERSHELL***"
$wrapper = Read-File "D:\Sorting\Sorting_Input.txt"
$values  = $wrapper.Values
$elapsed = Invoke-Heapsort $values
Save-File $values "D:\Sorting\Output_PS.txt"
Write-Host "***RUN COMPLETE***"
Write-Host ("HEAPSORT TOOK {0:F6} SECONDS." -f $elapsed)