#include <c_Quick3string.h>

// 小区间自适应截断降级阈值（小于此体量的碎区间直接交付级联插入排序专线）
#define COMPONENT_Q3S_CUTOFF 15

/**
 * @brief 内部原子物理接口：泛型就地连续内存块对调
 */
C_STATIC_FORCE_INLINE
void c_Q3S_InternalSwap(void* a, void* b, c_size_t size) {
    if (a == b) return;
    char* p1 = (char*)a;
    char* p2 = (char*)b;
    char temp_buf[256];
    c_size_t bytes_left = size;
    while (bytes_left > 0) {
        c_size_t chunk = (bytes_left < sizeof(temp_buf)) ? bytes_left : sizeof(temp_buf);
        memcpy(&temp_buf, p1, chunk);
        memcpy(p1, p2, chunk);
        memcpy(p2, &temp_buf, chunk);
        p1 += chunk;
        p2 += chunk;
        bytes_left -= chunk;
    }
}

/**
 * @brief 带起始偏移量 d 的全景多级深度级联字典序比对器
 */
C_STATIC_FORCE_INLINE
int c_Q3S_CascadedCompare(const void* a, const void* b, c_size_t start_d, c_Q3S_ExtractorFn extractor, void* args) {
    c_size_t cur_d = start_d;
    while (1) {
        int char_a = extractor(a, cur_d, args);
        int char_b = extractor(b, cur_d, args);
        if (char_a == char_b) {
            if (char_a == -1) return 0; // 双方完全全等
            cur_d++;
            continue;
        }
        return char_a - char_b; // 截止符 -1 属于绝对极小值
    }
}

/**
 * @brief 降级优化专线：泛型后缀级联插入排序
 */
static void c_Q3S_InsertionSort(char* base, c_size_t low, c_size_t high, c_size_t elem_size, c_Q3S_ExtractorFn extractor, c_size_t d, void* args) {
    for (c_size_t i = low + 1; i <= high; i++) {
        c_size_t j = i;
        char* item_i = base + (i * elem_size);
        char v_buf[elem_size];
        memcpy(v_buf, item_i, elem_size);

        while (j > low) {
            char* previous = base + ((j - 1) * elem_size);
            char* current  = base + (j * elem_size);
            if (c_Q3S_CascadedCompare(v_buf, previous, d, extractor, args) < 0) {
                memcpy(current, previous, elem_size);
                j--;
            } else {
                break;
            }
        }
        memcpy(base + (j * elem_size), v_buf, elem_size);
    }
}

/**
 * @brief 三向字符串快速排序递归控制核心状态机（无符号全加固闭区间版）
 */
static void c_Quick3string_Recursive(char* base, c_size_t low, c_size_t high, c_size_t elem_size, c_Q3S_ExtractorFn extractor, c_size_t d, void* args) {
    // 🌟【无符号下溢强拦截】：若当前区间上限发生下溢跨步或者区间非法，果断前置熔断破出
    if (high <= low || high == (c_size_t)-1) {
        return;
    }

    // 1. 小数组降级截断，彻底抹杀高维分治在稀疏碎片子树下的常数延迟
    if (high - low < COMPONENT_Q3S_CUTOFF) {
        c_Q3S_InsertionSort(base, low, high, elem_size, extractor, d, args);
        return;
    }

    // 2. 选择当前区间的首元素作为三向切分的基准锚定点（Pivot）
    char* pivot_item = base + (low * elem_size);
    int v = extractor(pivot_item, d, args);

    // 🌟【双指针向内对碰状态机控制线】：
    // lt 游标代表小于 v 区间的右开端点；gt 游标代表大于 v 区间的左闭端点；i 为当前探测移动指针
    c_size_t lt = low;
    c_size_t i = low + 1;
    c_size_t gt = high;

    // 3. 核心分治走查循环
    while (i <= gt && gt != (c_size_t)-1) {
        char* curr_item = base + (i * elem_size);
        int t = extractor(curr_item, d, args);

        if (t < v) {
            // 情况 A：当前字符小于切分字符，与 lt 位置就地物理对调，两组游标同步推进
            c_Q3S_InternalSwap(base + (lt * elem_size), curr_item, elem_size);
            lt++;
            i++;
        }
        else if (t > v) {
            // 情况 B：当前字符大于切分字符，与当前的 gt 尾部边缘插槽执行就地 Swap 对调
            c_Q3S_InternalSwap(curr_item, base + (gt * elem_size), elem_size);

            // 🌟 绝杀点：gt 减法单调向左逼近。为了防止其减到 0 之后发生回绕下溢，
            // 增设了严格的高位联锁前置判定，若 gt 已经逼近最左端，强制使其归 `-1` 并斩断 while
            if (gt == 0) {
                gt = (c_size_t)-1;
            } else {
                gt--;
            }
            // 注意：此时探测指针 i 保持原地不动！换进来的新内容会在下一轮循环被重新审讯判定
        }
        else {
            // 情况 C：完全相等，无伤安全滑过，游标递增
            i++;
        }
    }

    // 4. 🌟🌟🌟【级联分治三向并行递归管线】🌟🌟🌟

    // 区间 1：递归对左侧完全 [low, lt - 1] 的“小于区”执行排序。第 d 位字符保持不变
    if (lt > 0 && (lt - 1) > low) {
        c_Quick3string_Recursive(base, low, lt - 1, elem_size, extractor, d, args);
    }

    // 区间 2：递归对中央 [lt, gt] 的“等于区”执行排序！
    // 核心精髓：由于这个子区间的所有元素在第 d 位字符上已经百分之百全等，
    // 我们的字节提取器游标 d + 1 单调向右推前移，彻底略过已对齐前缀，执行深层后缀的对碰。
    // 特殊拦截：若当前切分出的基准字符本身就是终止哨兵 -1，说明这批等于区的字符串内容在物理上已经提前完结，果断斩断深层递归，不进入 d+1
    if (v >= 0 && gt != (c_size_t)-1 && gt >= lt) {
        c_Quick3string_Recursive(base, lt, gt, elem_size, extractor, d + 1, args);
    }

    // 区间 3：递归对右侧 [gt + 1, high] 的“大于区”执行排序。第 d 位字符保持不变
    if (gt != (c_size_t)-1 && high > (gt + 1)) {
        c_Quick3string_Recursive(base, gt + 1, high, elem_size, extractor, d, args);
    }
}

/**
 * @brief 工业级变长泛型三向字符串快速排序标准对外总线入口
 */
c_err_t c_Quick3string(void* base, c_size_t num, c_size_t elem_size, c_Q3S_ExtractorFn extractor, void* args) {
    if (!base || elem_size == 0 || !extractor) {
        return C_ERR_PARAM;
    }
    if (num < 2) {
        return C_ERR_OK; // 零体安全放行
    }

    char* array_base = (char*)base;
    c_Quick3string_Recursive(array_base, 0, num - 1, elem_size, extractor, 0, args);
    return C_ERR_OK;
}