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

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

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.")

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

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

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()