1#include "structures/tests/test_internal.h"
2
3TEST_GROUP_DECLARE(treap);
4
5struct test_treap_node {
6 int key;
7 struct treap_node node;
8};
9
10static int test_treap_cmp(const struct treap_node *a,
11 const struct treap_node *b) {
12 int ka = treap_entry(a, struct test_treap_node, node)->key;
13 int kb = treap_entry(b, struct test_treap_node, node)->key;
14 return (ka > kb) - (ka < kb);
15}
16
17static int test_treap_cmp_key(const struct treap_node *a, const void *key) {
18 int ka = treap_entry(a, struct test_treap_node, node)->key;
19 int kk = *(const int *) key;
20 return (ka > kk) - (ka < kk);
21}
22
23static const struct treap_node_ops test_treap_ops = {
24 .cmp = test_treap_cmp,
25 .cmp_key = test_treap_cmp_key,
26};
27
28static bool verify_treap_invariants(struct treap_node *n, int *min, int *max) {
29 if (!n) {
30 return true;
31 }
32
33 int k = treap_entry(n, struct test_treap_node, node)->key;
34
35 if (min && k <= *min) {
36 return false;
37 }
38 if (max && k >= *max) {
39 return false;
40 }
41
42 /* Heap invariant (min-heap on priority) */
43 if (n->left) {
44 if (n->left->priority < n->priority || n->left->parent != n) {
45 return false;
46 }
47 if (!verify_treap_invariants(n: n->left, min, max: &k)) {
48 return false;
49 }
50 }
51 if (n->right) {
52 if (n->right->priority < n->priority || n->right->parent != n) {
53 return false;
54 }
55 if (!verify_treap_invariants(n: n->right, min: &k, max)) {
56 return false;
57 }
58 }
59
60 return true;
61}
62
63TEST_DECLARE_UNIT(treap, basic_operations) {
64 struct treap_tree tree;
65 treap_tree_init(tree: &tree, ops: &test_treap_ops);
66
67 struct test_treap_node nodes[8];
68 int keys[8] = {40, 20, 60, 10, 30, 50, 70, 25};
69 uint32_t priorities[8] = {100, 50, 80, 200, 30, 150, 90, 10};
70
71 for (int i = 0; i < 8; i++) {
72 nodes[i].key = keys[i];
73 treap_init_node(n: &nodes[i].node, priority: priorities[i]);
74 treap_insert(tree: &tree, node: &nodes[i].node);
75 TEST_ASSERT(verify_treap_invariants(tree.root, NULL, NULL));
76 }
77
78 /* Verify search */
79 for (int i = 0; i < 8; i++) {
80 struct treap_node *found = treap_find(tree: &tree, key: &keys[i]);
81 TEST_ASSERT_NONNULL(found);
82 TEST_ASSERT_EQ(found, &nodes[i].node);
83 }
84
85 int missing = 999;
86 TEST_ASSERT_NULL(treap_find(&tree, &missing));
87
88 /* In-order traversal must be strictly ascending */
89 struct treap_node *cur = treap_first(tree: &tree);
90 int prev = -1;
91 int count = 0;
92 while (cur) {
93 int k = treap_entry(cur, struct test_treap_node, node)->key;
94 TEST_ASSERT_GT_S(k, prev);
95 prev = k;
96 count++;
97 cur = treap_next(node: cur);
98 }
99 TEST_ASSERT_EQ(count, 8);
100
101 /* Test removal */
102 for (int i = 0; i < 8; i++) {
103 treap_remove(tree: &tree, node: &nodes[i].node);
104 TEST_ASSERT(verify_treap_invariants(tree.root, NULL, NULL));
105 TEST_ASSERT_NULL(treap_find(&tree, &keys[i]));
106 }
107
108 TEST_ASSERT(treap_tree_empty(&tree));
109
110 return TEST_SUCCESS;
111}
112