85 lines
3.3 KiB
C
85 lines
3.3 KiB
C
|
#include "c_IndexMinPQ.h"
|
||
|
|
#include "c_Test.h"
|
||
|
|
|
||
|
|
#include <stdlib.h>
|
||
|
|
#include <stdio.h>
|
||
|
|
|
||
|
|
static int index_pq_compare_ints(const void* a, const void* b, void* args) {
|
||
|
|
(void)args;
|
||
|
|
int arg1 = *(const int*)a;
|
||
|
|
int arg2 = *(const int*)b;
|
||
|
|
if (arg1 < arg2) return -1;
|
||
|
|
if (arg1 > arg2) return 1;
|
||
|
|
return 0;
|
||
|
|
}
|
||
|
|
|
||
|
|
TEST_CASE(test_c_IndexMinPQ_DecreaseKeyDijkstraFlow) {
|
||
|
|
c_IndexMinPQ_t ipq;
|
||
|
|
// 允许最大的顶点唯一标识范围为 0 到 9 (共10个元素上界)
|
||
|
|
c_err_t err = c_IndexMinPQ_Init(&ipq, 10, sizeof(int), index_pq_compare_ints, NULL, &c_DefaultAllocator);
|
||
|
|
ASSERT_INT_EQ(C_ERR_OK, err);
|
||
|
|
|
||
|
|
// 模拟 Dijkstra 算法节点入队。唯一顶点ID为索引，其当前的极值距离为键值
|
||
|
|
int dist_vertex_0 = 45;
|
||
|
|
int dist_vertex_1 = 88;
|
||
|
|
int dist_vertex_2 = 15; // 此时顶点 2 距离最小 (15)
|
||
|
|
|
||
|
|
ASSERT_INT_EQ(C_ERR_OK, c_IndexMinPQ_Push(&ipq, 0, &dist_vertex_0));
|
||
|
|
ASSERT_INT_EQ(C_ERR_OK, c_IndexMinPQ_Push(&ipq, 1, &dist_vertex_1));
|
||
|
|
ASSERT_INT_EQ(C_ERR_OK, c_IndexMinPQ_Push(&ipq, 2, &dist_vertex_2));
|
||
|
|
|
||
|
|
// 全局唯一状态包含校验
|
||
|
|
ASSERT_TRUE(c_IndexMinPQ_Contains(&ipq, 0));
|
||
|
|
ASSERT_TRUE(c_IndexMinPQ_Contains(&ipq, 1));
|
||
|
|
ASSERT_TRUE(c_IndexMinPQ_Contains(&ipq, 2));
|
||
|
|
ASSERT_TRUE(!c_IndexMinPQ_Contains(&ipq, 5)); // 不包含未插入的 5
|
||
|
|
|
||
|
|
// 🌟【核心剧变测试】：在图算法流转中，顶点 1 经过松弛（Relaxation），其距离突然被更新缩短到 4
|
||
|
|
// 此时顶点 1 (键值 4) 瞬间越级打破局面，逆袭变成本索引堆的绝对最小值！
|
||
|
|
int relax_dist_vertex_1 = 4;
|
||
|
|
ASSERT_INT_EQ(C_ERR_OK, c_IndexMinPQ_Change(&ipq, 1, &relax_dist_vertex_1));
|
||
|
|
|
||
|
|
c_size_t popped_index = 999;
|
||
|
|
|
||
|
|
// 第一次 Pop 弹出的绝对必须是更新后全局距离最短的顶点 1，而不是原先的顶点 2！
|
||
|
|
ASSERT_INT_EQ(C_ERR_OK, c_IndexMinPQ_Pop(&ipq, &popped_index));
|
||
|
|
ASSERT_INT_EQ(1, (int)popped_index);
|
||
|
|
ASSERT_TRUE(!c_IndexMinPQ_Contains(&ipq, 1)); // 弹出后状态注销
|
||
|
|
|
||
|
|
// 第二次 Pop 弹出的应该是次短的原顶点 2
|
||
|
|
ASSERT_INT_EQ(C_ERR_OK, c_IndexMinPQ_Pop(&ipq, &popped_index));
|
||
|
|
ASSERT_INT_EQ(2, (int)popped_index);
|
||
|
|
|
||
|
|
// 最后弹出顶点 0
|
||
|
|
ASSERT_INT_EQ(C_ERR_OK, c_IndexMinPQ_Pop(&ipq, &popped_index));
|
||
|
|
ASSERT_INT_EQ(0, (int)popped_index);
|
||
|
|
|
||
|
|
// 终极空堆校验
|
||
|
|
ASSERT_INT_EQ(C_ERR_EMPTY, c_IndexMinPQ_Pop(&ipq, &popped_index));
|
||
|
|
|
||
|
|
c_IndexMinPQ_Destroy(&ipq);
|
||
|
|
}
|
||
|
|
|
||
|
|
TEST_CASE(test_c_IndexMinPQ_ParamConstraints) {
|
||
|
|
c_IndexMinPQ_t local_ipq;
|
||
|
|
int dummy_val = 100;
|
||
|
|
|
||
|
|
// 验证越界输入或空参数的前置状态码拦截线
|
||
|
|
ASSERT_INT_EQ(C_ERR_PARAM, c_IndexMinPQ_Init(NULL, 10, sizeof(int), index_pq_compare_ints, NULL, NULL));
|
||
|
|
|
||
|
|
ASSERT_INT_EQ(C_ERR_OK, c_IndexMinPQ_Init(&local_ipq, 10, sizeof(int), index_pq_compare_ints, NULL, NULL));
|
||
|
|
ASSERT_INT_EQ(C_ERR_PARAM, c_IndexMinPQ_Push(&local_ipq, 999, &dummy_val)); // 999 远超 max_elements(10)
|
||
|
|
|
||
|
|
c_IndexMinPQ_Destroy(&local_ipq);
|
||
|
|
}
|
||
|
|
|
||
|
|
// ==========================================
|
||
|
|
// 5. 主集成入口
|
||
|
|
// ==========================================
|
||
|
|
int main(void) {
|
||
|
|
TEST_START(C_IndexMinPQ_Isolated_TestSuite);
|
||
|
|
RUN_TEST(test_c_IndexMinPQ_DecreaseKeyDijkstraFlow);
|
||
|
|
RUN_TEST(test_c_IndexMinPQ_ParamConstraints);
|
||
|
|
TEST_REPORT();
|
||
|
|
return (g_test_registry.failed_count > 0 ? 1 : 0);
|
||
|
|
}
|