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

IntroSorts = 0
InsertionSorts = 0
HeapSorts = 0

def load_file(fileSpec: Union[str, Path]) -> List[int]:
    print("READING INPUT FILE...",end="")
    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("SAVING OUTPUT FILE...",end="")
    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, start: int, end: int) -> None:
    while start + 2 * (root - start) + 1 < end:
        child = start + 2 * (root - start) + 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 heap_sort(values: List[int], start: int, end: int) -> None:
    global HeapSorts
    HeapSorts += 1
    for root in range(start + (end - start) // 2 - 1, start, -1):
        sift_down(values, root, start, end)
    for last in range(end - 1, start + 1, -1):
        values[start],values[last] = values[last],values[start]
        sift_down(values, start, start, last)

def insertion_sort(values: List[int], start: int, end: int) -> None:
    global InsertionSorts
    InsertionSorts += 1
    for index in range(start + 1, end, +1):
        value = values[index]
        pos = index - 1
        while pos >= start and values[pos] > value:
            values[pos + 1] = values[pos]
            pos -= 1
        values[pos + 1] = value

def partition(values: List[int], start: int, end: int) -> int:
    left = start
    right = end - 1
    pivot = values[start + math.floor((end - start) / 2)]
    while left <= right:
        while values[left] < pivot:
            left += 1
        while values[right] > pivot:
            right -= 1
        if left <= right:
            values[left],values[right] = values[right],values[left]
            left += 1
            right -= 1
    return left

def intro_sort(values: List[int], start: int, end: int, maxdepth: int) -> None:
    global IntroSorts
    IntroSorts += 1
    length = end - start
    if length <= 1:
        return
    if length < 16:
        insertion_sort(values, start, end)
    elif maxdepth <= 0:
        heap_sort(values, start, end)
    else:
        part = partition(values, start, end)
        intro_sort(values,start,part,maxdepth - 1)
        intro_sort(values,part,end,maxdepth - 1)

def perform_sort(values: List[int]) -> float:
    print("SORTING ELEMENTS...",end="")
    startTime = time.perf_counter()
    maxdepth = 0
    if len(values) > 1:
        maxdepth = log2(len(values)) * 2
    intro_sort(values, 0, len(values), maxdepth)
    endTime = time.perf_counter()
    print("DONE.")
    return endTime - startTime

def log2(x: int) -> int:
    n = 0
    while x > 0:
        x /= 2
        n += 1
    return n

def main() -> None:
    print("========INTROSORT PYTHON========")
    values = load_file("D:/Sorting/Sorting_Input.txt")
    elapsed = perform_sort(values)
    save_file(values, "D:/Sorting/Output_Python.txt")
    print("==========RUN COMPLETE==========")
    print(f"INTROSORT TOOK {elapsed:.6f} SECONDS.")
    print("================================")
    print("SORT CALLED | TIMES")
    print("------------+-------------------")
    print(f"Intro      | {IntroSorts}")
    print(f"Insert     | {InsertionSorts}")
    print(f"Heap       | {HeapSorts}")
    print("--------------------------------")

if __name__ == "__main__":
    main()