#ifndef INCLUDED_C_HEAPSORT_H
#define INCLUDED_C_HEAPSORT_H

#ifndef INCLUDED_C_BASE_H
#include <c_Base.h>
#endif /*INCLUDED_C_BASE_H*/

#ifndef INCLUDED_C_MEMORY_H
#include <c_Memory.h>
#endif /*INCLUDED_C_MEMORY_H*/



/* ------------------------------------------------------------------------------------------------------------------ */
/*  */


/**
 * Internal macro helper to swap two arbitrary blocks of memory of given size.
 */
C_STATIC_FORCE_INLINE
void c_SwapInternal(char* a, char* b, c_size_t size, void* temp) {
    if (a == b) return;
    memcpy(temp, a, size);
    memcpy(a, b, size);
    memcpy(b, temp, size);
}

/**
 * Standard Sift-Down structural loop modified to build/maintain a Max-Heap.
 */
C_STATIC_FORCE_INLINE
void c_Heapify(char* arr, c_size_t num, c_size_t root, c_size_t size,
                             void* temp, int (*compar)(const void*, const void*)) {
    c_int_t current = root;

    while (1) {
        c_int_t left_child = (2 * current) + 1;
        c_int_t right_child = (2 * current) + 2;
        c_int_t largest = current;

        if (left_child < num &&
            compar(arr + (left_child * size), arr + (largest * size)) > 0) {
            largest = left_child;
        }

        if (right_child < num &&
            compar(arr + (right_child * size), arr + (largest * size)) > 0) {
            largest = right_child;
        }

        if (largest == current) {
            break;
        }

        c_SwapInternal(arr + (current * size), arr + (largest * size), size, temp);
        current = largest;
    }
}

/* ------------------------------------------------------------------------------------------------------------------ */
/*  */

/**
 * Top-Level Framework Entry Point for Heapsort.
 * Time Complexity: O(n log n) | Space Complexity: O(1) in-place | Stable: No
 */
C_STATIC_FORCE_INLINE
void c_HeapSort(void* base, c_size_t num, c_size_t size,
                int (*compar)(const void*, const void*)) {
    if (base == NULL || num < 2 || size == 0) return;

    char* arr = (char*)base;

#define HEAP_STACK_LIMIT 128
    char stack_buf[HEAP_STACK_LIMIT];
    void* temp = (size <= HEAP_STACK_LIMIT) ? stack_buf : C_ALLOC(size);
    if (temp == NULL) return;

    // Safely cast size parameters to signed c_int_t variables before starting the algorithm loops
    c_int_t total_items = (c_int_t)num;

    // Phase 1: Build the Max-Heap from the bottom up (Floyd's heap construction)
    for (c_int_t i = (total_items / 2) - 1; i >= 0; i--) {
        c_Heapify(arr, total_items, i, size, temp, compar);
    }

    // Phase 2: In-place sorted array extraction
    for (c_int_t k = total_items - 1; k > 0; k--) {
        // Swap root max element to current end positions
        c_SwapInternal(arr, arr + (k * size), size, temp);

        // Re-heapify the remaining sub-heap structure
        c_Heapify(arr, k, 0, size, temp, compar);
    }

    if (size > HEAP_STACK_LIMIT) {
        C_FREE(temp);
    }
#undef HEAP_STACK_LIMIT
}

#endif /*INCLUDED_C_HEAPSORT_H*/