cKit/Search/c_RedBlackBST.t.c

#include "c_RedBlackBST.h"
#include "c_Test.h"
#include <stdlib.h>
#include <stdio.h>

static int rbbst_compare_chars(const void* a, const void* b, void* args) {
    (void)args;
    char char1 = *(const char*)a;
    char char2 = *(const char*)b;
    return char1 - char2;
}

TEST_CASE(test_c_RedBlackBST_CharColorFlow) {
    c_RedBlackBST_t tree;
    c_err_t err = c_RedBlackBST_Init(&tree, sizeof(char), sizeof(int), rbbst_compare_chars, NULL, &c_DefaultAllocator);
    ASSERT_INT_EQ(C_ERR_OK, err);

    // 🌟【高强度测试】：连续输入偏斜升序数据
    char keys[] = { 'A', 'B', 'C', 'D', 'E' };
    int vals[] = { 10, 20, 30, 40, 50 };

    for (int i = 0; i < 5; i++) {
        ASSERT_INT_EQ(C_ERR_OK, c_RedBlackBST_Put(&tree, &keys[i], &vals[i]));
    }
    ASSERT_INT_EQ(5, (int)tree.size);

    // 验证经过旋转后的树根节点确实符合 2-3 树的中位数上提，而不是退化链表
    char root_key = *(char*)(tree.root->key);
    ASSERT_TRUE(root_key != 'A');

    // 🌟 核心断言：根据 LLRB 契约，最终留在树最顶端的根节点的父链接颜色必须为黑色字符 'B'！
    ASSERT_INT_EQ(C_RB_BLACK, tree.root->color);

    // 验证 Get 检索的完好命中
    int extracted_val = 0;
    char target_key_D = 'D';
    ASSERT_INT_EQ(C_ERR_OK, c_RedBlackBST_Get(&tree, &target_key_D, &extracted_val));
    ASSERT_INT_EQ(40, extracted_val);

    ASSERT_TRUE(c_RedBlackBST_Contains(&tree, &target_key_D));

    c_RedBlackBST_Destroy(&tree);
}

TEST_CASE(test_c_RedBlackBST_EdgeToxicity) {
    c_RedBlackBST_t local_tree;
    c_RedBlackBST_Init(&local_tree, sizeof(char), sizeof(int), rbbst_compare_chars, NULL, NULL);

    char k = 'X'; int v = 99;
    ASSERT_INT_EQ(C_ERR_PARAM, c_RedBlackBST_Init(NULL, sizeof(char), sizeof(int), rbbst_compare_chars, NULL, NULL));
    ASSERT_INT_EQ(C_ERR_PARAM, c_RedBlackBST_Put(NULL, &k, &v));

    c_RedBlackBST_Destroy(&local_tree);
}

TEST_CASE(test_c_RedBlackBST_CascadeDeleteFlow) {
    c_RedBlackBST_t tree;
    c_err_t err = c_RedBlackBST_Init(&tree, sizeof(char), sizeof(int), rbbst_compare_chars, NULL, &c_DefaultAllocator);
    ASSERT_INT_EQ(C_ERR_OK, err);

    // 1. 先填充空表，验证初次空表下的 Delete 状态码契约是否为标准的 C_ERR_EMPTY
    char key_X = 'X';
    ASSERT_INT_EQ(C_ERR_EMPTY, c_RedBlackBST_Delete(&tree, &key_X));

    // 2. 密集录入数据，触发多层级左旋、右旋自平衡，构建标准 2-3 树拓扑
    char keys[] = { 'M', 'E', 'S', 'A', 'R', 'C', 'W' };
    int vals[]  = { 10,  20,  30,  40,  50,  60,  70  };
    c_size_t num = sizeof(keys) / sizeof(keys[0]);

    for (c_size_t i = 0; i < num; i++) {
        ASSERT_INT_EQ(C_ERR_OK, c_RedBlackBST_Put(&tree, &keys[i], &vals[i]));
    }
    ASSERT_INT_EQ(7, (int)tree.size);

    // 3. 【第一轮绝杀】：删除处于树底部的叶子边缘节点 'A'
    char key_A = 'A';
    ASSERT_INT_EQ(C_ERR_OK, c_RedBlackBST_Delete(&tree, &key_A));
    ASSERT_INT_EQ(6, (int)tree.size); // 有效递减
    int get_verify = 0;
    ASSERT_INT_EQ(C_ERR_NOTFOUND, c_RedBlackBST_Get(&tree, &key_A, &get_verify));

    // 4. 【第二轮绝杀】：删除拥有双向完好子树、处于核心中间分水岭的枢纽根节点 'M'
    // 修复后的控制流应当极其完美地调用 InternalDeleteMin 从右子树剥离后继者，无伤缝合红黑黑高
    char key_M = 'M';
    ASSERT_INT_EQ(C_ERR_OK, c_RedBlackBST_Delete(&tree, &key_M));
    ASSERT_INT_EQ(5, (int)tree.size);
    ASSERT_INT_EQ(C_ERR_NOTFOUND, c_RedBlackBST_Get(&tree, &key_M, &get_verify));

    // 5. 验证大动荡过后，其余未被删除的邻居兄弟节点依旧稳固且可被 O(log N) 正常 Get
    char key_C = 'C';
    ASSERT_INT_EQ(C_ERR_OK, c_RedBlackBST_Get(&tree, &key_C, &get_verify));
    ASSERT_INT_EQ(60, get_verify);

    char key_W = 'W';
    ASSERT_INT_EQ(C_ERR_OK, c_RedBlackBST_Get(&tree, &key_W, &get_verify));
    ASSERT_INT_EQ(70, get_verify);

    // 🌟【终极颜色完整性断言】：数据大洗牌后，驻留在最顶层的新树根节点颜色字符，必须依然被强行洗回完美的黑色 `'B'`！
    ASSERT_INT_EQ(C_RB_BLACK, (int)tree.root->color);

    c_RedBlackBST_Destroy(&tree);
}

TEST_CASE(test_c_RedBlackBST_DeleteDefenses) {
    c_RedBlackBST_t local_tree;
    c_RedBlackBST_Init(&local_tree, sizeof(char), sizeof(int), rbbst_compare_chars, NULL, NULL);

    char k = 'Q';
    // 6. 验证入参非法的强参数过滤
    ASSERT_INT_EQ(C_ERR_PARAM, c_RedBlackBST_Delete(NULL, &k));
    ASSERT_INT_EQ(C_ERR_PARAM, c_RedBlackBST_Delete(&local_tree, NULL));

    c_RedBlackBST_Destroy(&local_tree);
}

// ==========================================
// 5. 主集成入口
// ==========================================
int main(void) {
    TEST_START(C_RedBlackBST_CharColor_TestSuite);
    RUN_TEST(test_c_RedBlackBST_CharColorFlow);
    RUN_TEST(test_c_RedBlackBST_EdgeToxicity);

    RUN_TEST(test_c_RedBlackBST_CascadeDeleteFlow);
    RUN_TEST(test_c_RedBlackBST_DeleteDefenses);

    TEST_REPORT();
    return (g_test_registry.failed_count > 0 ? 1 : 0);
}