1#include <structures/treap.h>
2
3static void rotate_left(struct treap_tree *tree, struct treap_node *x) {
4 struct treap_node *y = x->right;
5 x->right = y->left;
6 if (y->left) {
7 y->left->parent = x;
8 }
9 y->parent = x->parent;
10 if (!x->parent) {
11 tree->root = y;
12 } else if (x == x->parent->left) {
13 x->parent->left = y;
14 } else {
15 x->parent->right = y;
16 }
17 y->left = x;
18 x->parent = y;
19}
20
21static void rotate_right(struct treap_tree *tree, struct treap_node *y) {
22 struct treap_node *x = y->left;
23 y->left = x->right;
24 if (x->right) {
25 x->right->parent = y;
26 }
27 x->parent = y->parent;
28 if (!y->parent) {
29 tree->root = x;
30 } else if (y == y->parent->left) {
31 y->parent->left = x;
32 } else {
33 y->parent->right = x;
34 }
35 x->right = y;
36 y->parent = x;
37}
38
39void treap_tree_init(struct treap_tree *tree,
40 const struct treap_node_ops *ops) {
41 tree->root = NULL;
42 tree->ops = ops;
43}
44
45void treap_insert(struct treap_tree *tree, struct treap_node *node) {
46 node->left = node->right = node->parent = NULL;
47
48 if (!tree->root) {
49 tree->root = node;
50 return;
51 }
52
53 struct treap_node *cur = tree->root;
54 struct treap_node *p = NULL;
55 int cmp = 0;
56
57 while (cur) {
58 p = cur;
59 cmp = tree->ops->cmp(node, cur);
60 if (cmp < 0) {
61 cur = cur->left;
62 } else {
63 cur = cur->right;
64 }
65 }
66
67 node->parent = p;
68 if (cmp < 0) {
69 p->left = node;
70 } else {
71 p->right = node;
72 }
73
74 while (node->parent && node->priority < node->parent->priority) {
75 if (node == node->parent->left) {
76 rotate_right(tree, y: node->parent);
77 } else {
78 rotate_left(tree, x: node->parent);
79 }
80 }
81}
82
83void treap_remove(struct treap_tree *tree, struct treap_node *node) {
84 if (!tree || !tree->root || !node) {
85 return;
86 }
87
88 while (node->left || node->right) {
89 if (node->left && node->right) {
90 if (node->left->priority < node->right->priority) {
91 rotate_right(tree, y: node);
92 } else {
93 rotate_left(tree, x: node);
94 }
95 } else if (node->left) {
96 rotate_right(tree, y: node);
97 } else {
98 rotate_left(tree, x: node);
99 }
100 }
101
102 if (node->parent) {
103 if (node == node->parent->left) {
104 node->parent->left = NULL;
105 } else {
106 node->parent->right = NULL;
107 }
108 } else {
109 tree->root = NULL;
110 }
111
112 node->left = node->right = node->parent = NULL;
113}
114
115struct treap_node *treap_find(const struct treap_tree *tree, const void *key) {
116 if (!tree || !tree->root) {
117 return NULL;
118 }
119
120 struct treap_node *cur = tree->root;
121 while (cur) {
122 int cmp = tree->ops->cmp_key(cur, key);
123 if (cmp == 0) {
124 return cur;
125 } else if (cmp > 0) {
126 cur = cur->left;
127 } else {
128 cur = cur->right;
129 }
130 }
131
132 return NULL;
133}
134
135struct treap_node *treap_first(const struct treap_tree *tree) {
136 if (!tree || !tree->root) {
137 return NULL;
138 }
139 struct treap_node *node = tree->root;
140 while (node->left) {
141 node = node->left;
142 }
143 return node;
144}
145
146struct treap_node *treap_last(const struct treap_tree *tree) {
147 if (!tree || !tree->root) {
148 return NULL;
149 }
150 struct treap_node *node = tree->root;
151 while (node->right) {
152 node = node->right;
153 }
154 return node;
155}
156
157struct treap_node *treap_next(const struct treap_node *node) {
158 if (!node) {
159 return NULL;
160 }
161
162 if (node->right) {
163 node = node->right;
164 while (node->left) {
165 node = node->left;
166 }
167 return (struct treap_node *) node;
168 }
169
170 struct treap_node *parent = node->parent;
171 while (parent && node == parent->right) {
172 node = parent;
173 parent = parent->parent;
174 }
175 return parent;
176}
177
178struct treap_node *treap_prev(const struct treap_node *node) {
179 if (!node) {
180 return NULL;
181 }
182
183 if (node->left) {
184 node = node->left;
185 while (node->right) {
186 node = node->right;
187 }
188 return (struct treap_node *) node;
189 }
190
191 struct treap_node *parent = node->parent;
192 while (parent && node == parent->left) {
193 node = parent;
194 parent = parent->parent;
195 }
196 return parent;
197}
198