from pathlib import Path
import time
from typing import List, Union

# ---------------------------------------------------------------------------
# read_file
# Purpose:
#   Read non-blank lines from a path as decimal integers.
# Parameters:
#   fileSpec - input path as a string or Path.
# Returns:
#   A list of integers; raises ValueError with the line number on invalid data.
# Variables used:
#   values, input_file, line_number, line, text - input parsing state.
# ---------------------------------------------------------------------------
def read_file(fileSpec: Union[str, Path]) -> List[int]:
    print("READING INPUT FILE...")
    values: List[int] = []
    with Path(fileSpec).open(encoding="ascii") as input_file:
        for line_number, line in enumerate(input_file, start=1):
            text = line.strip()
            if text:
                try:
                    values.append(int(text))
                except ValueError as error:
                    raise ValueError(
                        f"Invalid integer on line {line_number}: {text!r}"
                    ) from error
    print("DONE.")
    return values

# ---------------------------------------------------------------------------
# save_file
# Purpose:
#   Write each integer in values to a file on its own line.
# Parameters:
#   values - integer list; fileSpec - output path as string or Path.
# Returns:
#   None.
# Variables used:
#   output_file - open text stream.
# ---------------------------------------------------------------------------
def save_file(values: List[int], fileSpec: Union[str, Path]) -> None:
    print("WRITING OUTPUT FILE...")
    with Path(fileSpec).open("w", encoding="ascii") as output_file:
        for value in values:
            print(value, file=output_file)
    print("DONE.")

# ---------------------------------------------------------------------------
# sift_down
# 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 - index of the larger child.
# ---------------------------------------------------------------------------
def sift_down(values: List[int], root: int, end: int) -> None:
    while 2 * root + 1 < end:
        child = 2 * root + 1
        if child + 1 < end and values[child] < values[child + 1]:
            child += 1
        if values[root] >= values[child]:
            return
        values[root],values[child]=values[child],values[root]
        root = child

    # ---------------------------------------------------------------------------
    # heapsort
    # Purpose:
    #   Sort values in place using heap sort and measure elapsed time.
    # Parameters:
    #   values - integer list to sort.
    # Returns:
    #   Elapsed duration in seconds.
    # Variables used:
    #   startTime, endTime - performance-counter snapshots; start/end - heap bounds.
    # ---------------------------------------------------------------------------
def heapsort(values: List[int]) -> float:
    print("SORTING ELEMENTS...")
    startTime = time.perf_counter()
    for start in range(len(values) // 2 - 1, -1, -1):
        sift_down(values, start, len(values))
    for end in range(len(values) - 1, 0, -1):
        values[0], values[end] = values[end], values[0]
        sift_down(values, 0, end)
    endTime = time.perf_counter()
    print("DONE.")
    return endTime - startTime

# ---------------------------------------------------------------------------
# main
# Purpose:
#   Load, sort, save, and report timing for the configured input.
# Parameters:
#   None.
# Returns:
#   None.
# Variables used:
#   values - loaded/sorted data; elapsed - duration returned by heapsort.
# ---------------------------------------------------------------------------
def main() -> None:
    print("***HEAPSORT PYTHON***")
    values = read_file("D:/Sorting/Sorting_Input.txt")
    elapsed = heapsort(values)
    save_file(values, "D:/Sorting/Output_PYTHON.txt")
    print("***RUN COMPLETE***")
    print(f"HEAPSORT TOOK {elapsed:.6f} SECONDS.")

if __name__ == "__main__":
    main()