# algorithms.py with metrics
import math
import time


def _snap(steps, record_steps, a, active_i, boundary=-1):
    if record_steps:
        steps.append(
            {"array": a.copy(), "active_index": active_i, "sorted_boundary": boundary}
        )


def insertion_sort(arr, record_steps: bool = True):
    a = arr.copy()
    steps = []
    comparisons = 0
    moves = 0
    start = time.perf_counter()
    for i in range(1, len(a)):
        key = a[i]
        j = i - 1
        # at least one comparison if entering the while loop
        while j >= 0:
            comparisons += 1
            if a[j] > key:
                a[j + 1] = a[j]
                moves += 1
                _snap(steps, record_steps, a, j + 1, i)
                j -= 1
            else:
                break
        a[j + 1] = key
        moves += 1
        _snap(steps, record_steps, a, j + 1, i)
    end = time.perf_counter()
    metrics = {"comparisons": comparisons, "moves": moves, "seconds": end - start}
    return steps, metrics


def merge_sort(arr, record_steps: bool = True):
    a = arr.copy()
    steps = []
    comparisons = 0
    moves = 0
    start = time.perf_counter()

    def merge(left, mid, right):
        nonlocal comparisons, moves
        # Create copies of subarrays
        left_part = a[left : mid + 1]
        right_part = a[mid + 1 : right + 1]
        i = j = 0
        k = left

        # Merge while both parts have elements
        while i < len(left_part) and j < len(right_part):
            comparisons += 1  # one comparison each loop
            if left_part[i] <= right_part[j]:
                a[k] = left_part[i]
                moves += 1
                _snap(steps, record_steps, a, k, right)
                i += 1
            else:
                a[k] = right_part[j]
                moves += 1
                _snap(steps, record_steps, a, k, right)
                j += 1
            k += 1

        # Copy remaining elements of left_part
        while i < len(left_part):
            a[k] = left_part[i]
            moves += 1
            _snap(steps, record_steps, a, k, right)
            i += 1
            k += 1

        # Copy remaining elements of right_part
        while j < len(right_part):
            a[k] = right_part[j]
            moves += 1
            _snap(steps, record_steps, a, k, right)
            j += 1
            k += 1

    def sort(left, right):
        if left >= right:
            return
        mid = (left + right) // 2
        sort(left, mid)
        sort(mid + 1, right)
        merge(left, mid, right)

    if len(a) > 0:
        sort(0, len(a) - 1)

    end = time.perf_counter()
    metrics = {"comparisons": comparisons, "moves": moves, "seconds": end - start}
    return steps, metrics


def quick_sort(arr, record_steps: bool = True):
    a = arr.copy()
    steps = []
    comparisons = 0
    moves = 0

    def swap(i, j, *, active_i=None, sorted_b=None):
        nonlocal moves
        if i == j:
            return
        (
            a[i],
            a[j],
        ) = (
            a[j],
            a[i],
        )
        moves += 2
        _snap(
            steps,
            record_steps,
            a,
            i if active_i is None else active_i,
            -1 if sorted_b is None else sorted_b,
        )

    def partition(low, high):
        nonlocal comparisons, moves
        pivot = a[high]
        i = low - 1
        # compare high-1 and pivot
        for j in range(low, high):
            comparisons += 1
            if a[j] <= pivot:
                i += 1
                swap(i, j, active_i=j)
        # put pivot back to place
        swap(i + 1, high, active_i=i + 1, sorted_b=i + 1)
        return i + 1

    def qs(low, high):
        if low < high:
            p = partition(low, high)
            qs(low, p - 1)
            qs(p + 1, high)

    start = time.perf_counter()
    if a:
        qs(0, len(a) - 1)
    seconds = time.perf_counter() - start

    metrics = {"comparisons": comparisons, "moves": moves, "seconds": seconds}
    return steps, metrics


def counting_sort(arr, k=None, record_steps: bool = True):
    a = arr.copy()
    steps = []
    comparisons = 0
    moves = 0
    if not a:
        return steps, {"comparisons": 0, "moves": 0, "seconds": 0.0}

    # negatifleri desteklemiyorsak koruma (istersen offset ile destekleyebilirsin)
    if min(a) < 0:
        raise ValueError("Counting Sort: negatif değerler desteklenmiyor.")

    # k (değer aralığı) verilmediyse max+1 al
    if k is None:
        k = max(a) + 1

    start = time.perf_counter()

    count = [0] * k
    for v in a:
        count[v] += 1
    for i in range(1, k):
        count[i] += count[i - 1]

    out = [0] * len(a)
    for v in reversed(a):
        count[v] -= 1
        out[count[v]] = v

    for i, v in enumerate(out):
        a[i] = v
        moves += 1
        _snap(steps, record_steps, a, i, i)

    seconds = time.perf_counter() - start
    return steps, {"comparisons": comparisons, "moves": moves, "seconds": seconds}


def radix_sort_lsd(arr, base=10, record_steps: bool = True):
    a = arr.copy()
    steps = []
    comparisons = 0
    moves = 0

    if not a:
        return steps, {"comparisons": 0, "moves": 0, "seconds": 0.0}
    if base < 2:
        raise ValueError("radix base must be >= 2")

    start = time.perf_counter()

    def digit(x, exp):
        return (x // exp) % base

    exp = 1
    maxv = max(a)

    # for each digit place
    while maxv // exp > 0:
        # stable counting sort by current digit
        count = [0] * base

        # count
        for v in a:
            d = digit(v, exp)
            count[d] += 1

        # prefix sums
        for i in range(1, base):
            count[i] += count[i - 1]

        # build output(scan from right)
        out = [0] * len(a)
        for i in range(len(a) - 1, -1, -1):
            v = a[i]
            d = digit(v, exp)
            count[d] -= 1
            out[count[d]] = v

        for i, v in enumerate(out):
            a[i] = v
            moves += 1
            _snap(steps, record_steps, a, i, i)
        exp *= base

    seconds = time.perf_counter() - start
    metrics = {"comparisons": comparisons, "moves": moves, "seconds": seconds}
    return steps, metrics


# --- Heap Sort (max-heap, in-place) with metrics & step recording ---
# steps: her adımda {"array": a.copy(), "active_index": i, "sorted_boundary": b}
# - active_index: o karede yeni yazılan / swap’e giren indeks
# - sorted_boundary: heapsort’ta sıralı kuyruk (suffix) başlangıcı; j >= boundary -> "sorted"
# metrics:
# - comparisons: her a[l] > a[m] veya a[r] > a[m] kontrolü 1 karşılaştırma
# - moves: diziye her yazma 1; swap 2 move
def heap_sort(arr, record_steps: bool = True):
    a = arr.copy()
    steps = []
    comparisons = 0
    moves = 0

    heap_sorted = -1

    def snapshot(active_i, boundary):
        _snap(steps, record_steps, a, active_i, boundary)

    def swap(i, j):
        nonlocal moves
        if i == j:
            return
        a[i], a[j] = a[j], a[i]
        moves += 2
        snapshot(i, heap_sorted)

    def heapify(n, i):
        nonlocal comparisons
        while True:
            largest = i
            l = 2 * i + 1
            r = 2 * i + 2

            if l < n:
                comparisons += 1
                if a[l] > a[largest]:
                    largest = l
            if r < n:
                comparisons += 1
                if a[r] > a[largest]:
                    largest = r
            if largest == i:
                break

            swap(i, largest)
            i = largest

    start = time.perf_counter()

    n = len(a)
    if n <= 1:
        metrics = {"comparisons": 0, "moves": 0, "seconds": 0.0}
        return steps, metrics

    # build max heap
    for i in range(n // 2 - 1, -1, -1):
        heapify(n, i)
    # extract max
    for end in range(n - 1, 0, -1):
        swap(0, end)
        heap_sorted = end
        heapify(end, 0)

    seconds = time.perf_counter() - start
    metrics = {"comparisons": comparisons, "moves": moves, "seconds": seconds}
    return steps, metrics


def shell_sort(arr, record_steps: bool = True):
    a = arr.copy()
    steps = []
    comparisons = 0
    moves = 0

    def snap(active_i, boundary=-1):
        _snap(steps, record_steps, a, active_i, boundary)

    start = time.perf_counter()

    n = len(a)
    if n <= 1:
        return steps, {"comparisons": 0, "moves": 0, "seconds": 0.0}

    gap = n // 2
    while gap > 0:
        for i in range(gap, n):
            key = a[i]
            j = i - gap

            while j >= 0:
                comparisons += 1
                if a[j] > key:
                    a[j + gap] = a[j]
                    moves += 1
                    snap(j + gap)
                    j -= gap
                else:
                    break
            a[j + gap] = key
            moves += 1
            snap(j + gap)

        gap //= 2

    seconds = time.perf_counter() - start
    metrics = {"comparisons": comparisons, "moves": moves, "seconds": seconds}
    return steps, metrics


def bucket_sort(arr, num_buckets=None, record_steps: bool = True):
    a = arr.copy()
    steps = []
    comparisons = 0
    moves = 0

    if not a:
        return steps, {"comparisons": 0, "moves": 0, "seconds": 0.0}

    n = len(a)

    if num_buckets is None:
        num_buckets = max(1, int(math.sqrt(n)))

    start = time.perf_counter()

    maxv = max(a)

    # normlize values range between 0 and 1
    if maxv == 0:
        seconds = time.perf_counter() - start

        for i, v in enumerate(a):
            _snap(steps, record_steps, a, i, i)
        return steps, {"comparisons": 0, "moves": 0, "seconds": seconds}

    normalized = [x / (maxv + 1.0) for x in a]

    # create buckets
    buckets = [[] for _ in range(num_buckets)]

    # split values to buckets
    for v_norm, v_orig in zip(normalized, a):
        idx = int(v_norm * num_buckets)
        if idx >= num_buckets:
            idx = num_buckets - 1
        buckets[idx].append(v_orig)

    # sort buckets

    for b in buckets:
        for i in range(1, len(b)):
            key = b[i]
            j = i - 1
            while j >= 0:
                comparisons += 1
                if b[j] > key:
                    b[j + 1] = b[j]
                    j -= 1
                else:
                    break
            b[j + 1] = key

    # save at main
    write_i = 0
    for b in buckets:
        for v in b:
            a[write_i] = v
            moves += 1
            _snap(steps, record_steps, a, write_i, write_i)
            write_i += 1

    seconds = time.perf_counter() - start
    metrics = {"comparisons": comparisons, "moves": moves, "seconds": seconds}
    return steps, metrics