|
417
|
1 module RedBlackTree where
|
|
|
2
|
|
|
3 open import stack
|
|
|
4
|
|
|
5 record Tree {a t : Set} (treeImpl : Set) : Set where
|
|
|
6 field
|
|
|
7 tree : treeImpl
|
|
427
|
8 putImpl : treeImpl -> a -> (treeImpl -> t) -> t
|
|
|
9 getImpl : treeImpl -> (treeImpl -> Maybe a -> t) -> t
|
|
|
10
|
|
|
11 putTree : {a t : Set} -> Tree -> a -> (Tree -> t) -> t
|
|
|
12 putTree {a} {t} t0 d next = (putImpl t0) (tree t0) d (\t1 -> next (record t0 {tree = t1;} ))
|
|
|
13
|
|
|
14
|
|
|
15 getTree : {a t : Set} -> Tree -> (Tree -> t) -> t
|
|
|
16 getTree {a} {t} t0 next = (getImpl t0) (tree t0) (\t1 -> next t0)
|
|
|
17
|
|
417
|
18
|
|
425
|
19 data Color : Set where
|
|
|
20 Red : Color
|
|
|
21 Black : Color
|
|
|
22
|
|
|
23 record Node (a : Set) : Set where
|
|
|
24 field
|
|
|
25 node : Element a
|
|
|
26 right : Maybe (Node a)
|
|
|
27 left : Maybe (Node a)
|
|
|
28 color : Color
|
|
|
29
|
|
417
|
30 record RedBlackTree (a : Set) : Set where
|
|
|
31 field
|
|
425
|
32 root : Maybe (Node a)
|
|
417
|
33 stack : Stack
|
|
425
|
34
|
|
417
|
35 open RedBlackTree
|
|
|
36
|
|
|
37 putRedBlackTree : {Data t : Set} -> RedBlackTree Data -> Data -> (Code : RedBlackTree Data -> t) -> t
|
|
425
|
38 putRedBlackTree tree datum next with (root tree)
|
|
|
39 ... | Nothing = insertNode tree datum next
|
|
|
40 ... | Just n = findNode tree datum n (\ tree1 -> insertNode tree1 datum next)
|
|
|
41
|
|
|
42 findNode : {Data t : Set} -> RedBlackTree Data -> Data -> Node Data -> (Code : RedBlackTree Data (RedBlackTree Data -> t) -> t) -> t
|
|
427
|
43 findNode tree datum n next = push (stack tree) n (\ s -> findNode1 (record tree {stack = s }) datum n next)
|
|
425
|
44
|
|
|
45 findNode1 : {Data t : Set} -> RedBlackTree Data -> Data -> Data -> (Code : RedBlackTree Data (RedBlackTree Data -> t) -> t) -> t
|
|
|
46 findNode1 tree datum n next with (compare datum n)
|
|
428
|
47 ... | EQ = popStack (tree stack) (\s d -> findNode3 d (record tree { root = just (record n {node = datum}); stack = s }) next)
|
|
425
|
48 ... | GT = findNode2 tree datum (right n) next
|
|
|
49 ... | LT = findNode2 tree datum (left n) next
|
|
417
|
50 where
|
|
425
|
51 findNode2 tree datum nothing next = insertNode tree datum next
|
|
427
|
52 findNode2 tree datum (just n) next = findNode (record tree {root = just n}) datum n next
|
|
428
|
53 findNode3 nothing tree next = next tree
|
|
|
54 findNode3 (just n) tree next =
|
|
|
55 popStack (tree stack) (\s d -> findNode3 d (record { root = record n {right = } })
|
|
425
|
56
|
|
|
57 insertNode tree datum next = get2 (stack tree) (\ s d1 d2 -> insertCase1 ( record { root = root tree; stack = s }) datum d1 d2 next)
|
|
|
58
|
|
|
59 insertCase1 tree datum nothing grandparent next = next (record { root = ?; stack = createSingleLinkedStack })
|
|
|
60 insertCase1 tree datum (just parent) grandparent next = insertCase2 tree datum parent grandparent next
|
|
|
61
|
|
|
62 insertCase2 tree datum parent grandparent next with (color parent)
|
|
|
63 ... | Red = insertCase3 tree datum parent grandparent next
|
|
|
64 ... | Black = next (record { root = ?; stack = createSingleLinkedStack })
|
|
|
65
|
|
|
66 insertCase3 tree datum parent grandparent next
|
|
417
|
67
|
|
|
68 getRedBlackTree : {a t : Set} -> RedBlackTree a -> (Code : RedBlackTree a -> (Maybe a) -> t) -> t
|
|
425
|
69 getRedBlackTree tree cs with (root tree)
|
|
417
|
70 ... | Nothing = cs tree Nothing
|
|
|
71 ... | Just d = cs stack1 (Just data1)
|
|
|
72 where
|
|
|
73 data1 = datum d
|
|
425
|
74 stack1 = record { root = (next d) }
|
|
|
75
|
|
|
76
|
|
|
77 __code insertCase3(struct RedBlackTree* tree) {
|
|
|
78 struct Stack* nodeStack = tree->nodeStack;
|
|
|
79 struct Node* uncle;
|
|
|
80
|
|
|
81 if (tree->grandparent->left == tree->parent)
|
|
|
82 uncle = tree->grandparent->right;
|
|
|
83 else
|
|
|
84 uncle = tree->grandparent->left;
|
|
|
85
|
|
|
86 if (uncle && (uncle->color == Red)) {
|
|
|
87 // do insertcase1 on grandparent, stack must be pop by two
|
|
|
88 tree->parent->color = Black;
|
|
|
89 uncle->color = Black;
|
|
|
90 tree->grandparent->color = Red;
|
|
|
91 tree->current = tree->grandparent;
|
|
|
92 goto nodeStack->pop2(insertCase1);
|
|
|
93 }
|
|
|
94 goto insertCase4();
|
|
|
95 }
|
|
|
96
|
|
|
97 __code insertCase4(struct RedBlackTree* tree, struct RotateTree* rotateTree) {
|
|
|
98 struct Stack* nodeStack = tree->nodeStack;
|
|
|
99
|
|
|
100 if ((tree->current == tree->parent->right) && (tree->parent == tree->grandparent->left)) {
|
|
|
101 tree->current = tree->current->left;
|
|
|
102 tree->parent = tree->grandparent;
|
|
|
103
|
|
|
104 rotateTree->traverse = tree;
|
|
|
105 rotateTree->next = C_insertCase5;
|
|
|
106
|
|
|
107 goto nodeStack->pop(rotateLeft);
|
|
|
108 } else if ((tree->current == tree->parent->left) && (tree->parent == tree->grandparent->right)) {
|
|
|
109 tree->parent = tree->grandparent;
|
|
|
110 tree->current = tree->current->right;
|
|
|
111
|
|
|
112 rotateTree->traverse = tree;
|
|
|
113 rotateTree->next = C_insertCase5;
|
|
|
114
|
|
|
115 goto nodeStack->pop(rotateRight);
|
|
|
116 }
|
|
|
117
|
|
|
118 goto insertCase5();
|
|
|
119 }
|
|
|
120
|
|
|
121 __code insertCase5(struct RedBlackTree* tree) {
|
|
|
122 struct Stack* nodeStack = tree->nodeStack;
|
|
|
123 goto nodeStack->pop2(insertCase51);
|
|
|
124 }
|
|
|
125
|
|
|
126 __code insertCase51(struct RedBlackTree* tree, struct RotateTree* rotateTree, struct Node* parent, struct Node* grandparent) {
|
|
|
127 struct Node* current = tree->current;
|
|
|
128 tree->parent = parent;
|
|
|
129 tree->grandparent = grandparent;
|
|
|
130
|
|
|
131 parent->color = Black;
|
|
|
132 grandparent->color = Red;
|
|
|
133
|
|
|
134 tree->current = grandparent;
|
|
|
135
|
|
|
136 rotateTree->traverse = tree;
|
|
|
137 rotateTree->next = C_stackClear;
|
|
|
138
|
|
|
139 if ((current == parent->left) && (parent == grandparent->left))
|
|
|
140 goto rotateRight();
|
|
|
141 else
|
|
|
142 goto rotateLeft();
|
|
|
143 }
|
|
|
144
|
|
|
145 __code insertCase51_stub(struct Context* context) {
|
|
|
146 struct Node* parent = &context->data[D_Stack]->Stack.data->Node;
|
|
|
147 struct Node* grandparent = &context->data[D_Stack]->Stack.data1->Node;
|
|
|
148 goto insertCase51(context,
|
|
|
149 &Gearef(context, Tree)->tree->Tree.tree->RedBlackTree,
|
|
|
150 Gearef(context, RotateTree),
|
|
|
151 parent,
|
|
|
152 grandparent);
|
|
|
153 }
|
|
|
154
|
|
|
155 __code rotateLeft(struct RedBlackTree* tree, struct Stack* nodeStack) {
|
|
|
156 nodeStack->stack = (union Data*)tree->nodeStack;
|
|
|
157 nodeStack->next = C_rotateLeft1;
|
|
|
158 goto meta(context, tree->nodeStack->get);
|
|
|
159 }
|
|
|
160
|
|
|
161 __code rotateLeft_stub(struct Context* context) {
|
|
|
162 struct RedBlackTree* traverse = context->data[D_RotateTree]->RotateTree.traverse;
|
|
|
163 goto rotateLeft(context, traverse, Gearef(context, Stack));
|
|
|
164 }
|
|
|
165
|
|
|
166 __code rotateLeft1(struct Node* node, struct RedBlackTree* tree, struct Node* parent, struct RotateTree* rotateTree) {
|
|
|
167 struct Node* tmp = node->right;
|
|
|
168
|
|
|
169 if (parent) {
|
|
|
170 if (node == parent->left)
|
|
|
171 parent->left = tmp;
|
|
|
172 else
|
|
|
173 parent->right = tmp;
|
|
|
174 } else {
|
|
|
175 tree->root = tmp;
|
|
|
176 }
|
|
|
177
|
|
|
178 node->right = tmp->left;
|
|
|
179 tmp->left = node;
|
|
|
180 tree->current = tmp;
|
|
|
181
|
|
|
182 goto meta(context, rotateTree->next);
|
|
|
183 }
|
|
|
184
|
|
|
185 __code rotateLeft1_stub(struct Context* context) {
|
|
|
186 struct RedBlackTree* traverse = context->data[D_RotateTree]->RotateTree.traverse;
|
|
|
187 struct Node* parent = &context->data[D_Stack]->Stack.data->Node;
|
|
|
188 goto rotateLeft1(context,
|
|
|
189 traverse->current,
|
|
|
190 traverse,
|
|
|
191 parent,
|
|
|
192 Gearef(context, RotateTree));
|
|
|
193 }
|
|
|
194
|
|
|
195 __code rotateRight(struct RedBlackTree* tree, struct Stack* nodeStack) {
|
|
|
196 nodeStack->stack = (union Data*)tree->nodeStack;
|
|
|
197 nodeStack->next = C_rotateRight1;
|
|
|
198 goto meta(context, tree->nodeStack->get);
|
|
|
199 }
|
|
|
200
|
|
|
201 __code rotateRight_stub(struct Context* context) {
|
|
|
202 struct RedBlackTree* traverse = context->data[D_RotateTree]->RotateTree.traverse;
|
|
|
203 goto rotateLeft(context, traverse, Gearef(context, Stack));
|
|
|
204 }
|
|
|
205
|
|
|
206 __code rotateRight1(struct Node* node, struct RedBlackTree* traverse,struct Node *parent,struct RotateTree *rotateTree) {
|
|
|
207 struct Node* tmp = node->left;
|
|
|
208
|
|
|
209 if (parent) {
|
|
|
210 if (node == parent->left)
|
|
|
211 parent->left = tmp;
|
|
|
212 else
|
|
|
213 parent->right = tmp;
|
|
|
214 } else {
|
|
|
215 traverse->root = tmp;
|
|
|
216 }
|
|
|
217
|
|
|
218 node->left = tmp->right;
|
|
|
219 tmp->right = node;
|
|
|
220 traverse->current = tmp;
|
|
|
221
|
|
|
222 goto meta(context, rotateTree->next);
|
|
|
223 }
|
|
|
224
|
|
|
225 __code rotateRight1_stub(struct Context* context) {
|
|
|
226 struct RedBlackTree* traverse = context->data[D_RotateTree]->RotateTree.traverse;
|
|
|
227 struct Node* parent = &context->data[D_Stack]->Stack.data->Node;
|
|
|
228 goto rotateRight1(context,
|
|
|
229 traverse->current,
|
|
|
230 traverse,
|
|
|
231 parent,
|
|
|
232 Gearef(context, RotateTree));
|
|
|
233 }
|
|
|
234
|
|
|
235 __code stackClear(struct RedBlackTree* tree, struct Stack* nodeStack, __code next(...)) {
|
|
|
236 tree->current = 0;
|
|
|
237 nodeStack->stack = (union Data*)tree->nodeStack;
|
|
|
238 nodeStack->next = next;
|
|
|
239 goto meta(context, tree->nodeStack->clear);
|
|
|
240 }
|
|
|
241
|
|
|
242 __code getRedBlackTree(struct RedBlackTree* tree, __code next(...)) {
|
|
|
243 if (tree->root) {
|
|
|
244 tree->current = tree->root;
|
|
|
245
|
|
|
246 goto search();
|
|
|
247 }
|
|
|
248
|
|
|
249 goto next(...);
|
|
|
250 }
|
|
|
251
|
|
|
252 __code search(struct RedBlackTree* tree, struct Node* node, __code next(...)) {
|
|
|
253 // compare(context, traverse, traverse->current->key, node->key);
|
|
|
254 tree->result = compare(tree->current, node);
|
|
|
255 if (tree->result == EQ) {
|
|
|
256 *node = *tree->current;
|
|
|
257
|
|
|
258 goto meta(context, next);
|
|
|
259 } else if (tree->result == GT) {
|
|
|
260 tree->current = tree->current->right;
|
|
|
261 } else {
|
|
|
262 tree->current = tree->current->left;
|
|
|
263 }
|
|
|
264
|
|
|
265 if (tree->current)
|
|
|
266 goto meta(context, C_search);
|
|
|
267
|
|
|
268 goto next(...);
|
|
|
269 }
|
|
|
270
|
|
|
271 /* /\* __code delete(struct Context* context, struct Tree* tree) { *\/ */
|
|
|
272 /* /\* if (tree->root) { *\/ */
|
|
|
273 /* /\* stack_push(context->code_stack, &context->next); *\/ */
|
|
|
274 /* /\* context->next = Delete1; *\/ */
|
|
|
275 /* /\* goto meta(context, Get); *\/ */
|
|
|
276 /* /\* } *\/ */
|
|
|
277
|
|
|
278 /* /\* goto meta(context, context->next); *\/ */
|
|
|
279 /* /\* } *\/ */
|
|
|
280
|
|
|
281 /* /\* __code delete_stub(struct Context* context) { *\/ */
|
|
|
282 /* /\* goto delete(context, &context->data[Tree]->tree); *\/ */
|
|
|
283 /* /\* } *\/ */
|
|
|
284
|
|
|
285 /* /\* __code delete1(struct Context* context, struct Tree* tree, struct Allocate* allocate) { *\/ */
|
|
|
286 /* /\* allocate->size = sizeof(struct Node); *\/ */
|
|
|
287 /* /\* allocator(context); *\/ */
|
|
|
288
|
|
|
289 /* /\* struct Node* root = tree->root; *\/ */
|
|
|
290
|
|
|
291 /* /\* tree->root = &context->data[context->dataNum]->node; *\/ */
|
|
|
292 /* /\* tree->current = root; *\/ */
|
|
|
293
|
|
|
294 /* /\* compare(context, tree, tree->current->key, context->data[Node]->node.key); *\/ */
|
|
|
295
|
|
|
296 /* /\* goto meta(context, Replace_d1); *\/ */
|
|
|
297 /* /\* } *\/ */
|
|
|
298
|
|
|
299 /* /\* __code delete1_stub(struct Context* context) { *\/ */
|
|
|
300 /* /\* goto delete1(context, &context->data[Tree]->tree, &context->data[Allocate]->allocate); *\/ */
|
|
|
301 /* /\* } *\/ */
|
|
|
302
|
|
|
303 /* /\* __code delete2(struct Context* context, struct Node* current) { *\/ */
|
|
|
304 /* /\* if (current->color == Black) { *\/ */
|
|
|
305 /* /\* struct Node* child = current->right == NULL ? current->left : current->right; *\/ */
|
|
|
306 /* /\* current->color = child == NULL ? Black : child->color; *\/ */
|
|
|
307
|
|
|
308 /* /\* goto meta(context, DeleteCase1); *\/ */
|
|
|
309 /* /\* } *\/ */
|
|
|
310
|
|
|
311 /* /\* goto meta(context, Delete3); *\/ */
|
|
|
312 /* /\* } *\/ */
|
|
|
313
|
|
|
314 /* /\* __code delete2_stub(struct Context* context) { *\/ */
|
|
|
315 /* /\* goto delete2(context, context->data[Tree]->tree.current); *\/ */
|
|
|
316 /* /\* } *\/ */
|
|
|
317
|
|
|
318 /* /\* __code delete3(struct Context* context, struct Tree* tree, struct Node* current) { *\/ */
|
|
|
319 /* /\* struct Node* tmp = current->right == NULL ? current->left : current->right; *\/ */
|
|
|
320
|
|
|
321 /* /\* if (current->parent) { *\/ */
|
|
|
322 /* /\* if (current == current->parent->left) *\/ */
|
|
|
323 /* /\* current->parent->left = tmp; *\/ */
|
|
|
324 /* /\* else *\/ */
|
|
|
325 /* /\* current->parent->right = tmp; *\/ */
|
|
|
326 /* /\* } else { *\/ */
|
|
|
327 /* /\* tree->root = tmp; *\/ */
|
|
|
328 /* /\* } *\/ */
|
|
|
329
|
|
|
330 /* /\* if (tmp) *\/ */
|
|
|
331 /* /\* tmp->parent = current->parent; *\/ */
|
|
|
332
|
|
|
333 /* /\* if (current->parent == NULL && tmp) *\/ */
|
|
|
334 /* /\* tmp->color = Black; *\/ */
|
|
|
335
|
|
|
336 /* /\* current == current->parent->left ? (current->parent->left = NULL) : (current->parent->right = NULL); *\/ */
|
|
|
337
|
|
|
338 /* /\* stack_pop(context->code_stack, &context->next); *\/ */
|
|
|
339 /* /\* goto meta(context, context->next); *\/ */
|
|
|
340 /* /\* } *\/ */
|
|
417
|
341
|
|
425
|
342 /* /\* __code delete3_stub(struct Context* context) { *\/ */
|
|
|
343 /* /\* goto delete3(context, &context->data[Tree]->tree, context->data[Tree]->tree.current); *\/ */
|
|
|
344 /* /\* } *\/ */
|
|
|
345
|
|
|
346 /* /\* __code replaceNodeForDelete1(struct Context* context, struct Tree* tree, struct Node* oldNode, struct Node* newNode, int result) { *\/ */
|
|
|
347 /* /\* *newNode = *oldNode; *\/ */
|
|
|
348
|
|
|
349 /* /\* if (result == EQ) *\/ */
|
|
|
350 /* /\* goto meta(context, Replace_d2); *\/ */
|
|
|
351 /* /\* else if (result == GT) *\/ */
|
|
|
352 /* /\* tree->current = newNode->right; *\/ */
|
|
|
353 /* /\* else *\/ */
|
|
|
354 /* /\* tree->current = newNode->left; *\/ */
|
|
|
355
|
|
|
356 /* /\* tree->current->parent = newNode; *\/ */
|
|
|
357
|
|
|
358 /* /\* if (tree->current->left == NULL && tree->current->right == NULL) *\/ */
|
|
|
359 /* /\* goto meta(context, Delete2); *\/ */
|
|
|
360
|
|
|
361 /* /\* if (result == GT) *\/ */
|
|
|
362 /* /\* newNode->right = context->heap; *\/ */
|
|
|
363 /* /\* else if (result == LT) *\/ */
|
|
|
364 /* /\* newNode->left = context->heap; *\/ */
|
|
|
365
|
|
|
366 /* /\* allocator(context); *\/ */
|
|
|
367
|
|
|
368 /* /\* compare(context, tree, tree->current->key, context->data[Node]->node.key); *\/ */
|
|
|
369
|
|
|
370 /* /\* goto meta(context, Replace_d1); *\/ */
|
|
|
371 /* /\* } *\/ */
|
|
|
372
|
|
|
373 /* /\* __code replaceNodeForDelete1_stub(struct Context* context) { *\/ */
|
|
|
374 /* /\* goto replaceNodeForDelete1(context, &context->data[Tree]->tree, context->data[Tree]->tree.current, &context->data[context->dataNum]->node, context->data[Tree]->tree.result); *\/ */
|
|
|
375 /* /\* } *\/ */
|
|
|
376
|
|
|
377 /* /\* __code replaceNodeForDelete2(struct Context* context, struct Tree* tree, struct Node* newNode) { *\/ */
|
|
|
378 /* /\* if (tree->current->left && tree->current->right) { *\/ */
|
|
|
379 /* /\* newNode->left->parent = newNode; *\/ */
|
|
|
380 /* /\* tree->current = newNode->left; *\/ */
|
|
|
381 /* /\* newNode->left = context->heap; *\/ */
|
|
|
382 /* /\* tree->deleted = newNode; *\/ */
|
|
|
383
|
|
|
384 /* /\* allocator(context); *\/ */
|
|
|
385 /* /\* tree->current->parent = newNode; *\/ */
|
|
|
386
|
|
|
387 /* /\* goto meta(context, FindMax1); *\/ */
|
|
|
388 /* /\* } *\/ */
|
|
|
389
|
|
|
390 /* /\* goto meta(context, Delete2); *\/ */
|
|
|
391 /* /\* } *\/ */
|
|
|
392
|
|
|
393 /* /\* __code replaceNodeForDelete2_stub(struct Context* context) { *\/ */
|
|
|
394 /* /\* goto replaceNodeForDelete2(context, &context->data[Tree]->tree, &context->data[context->dataNum]->node); *\/ */
|
|
|
395 /* /\* } *\/ */
|
|
|
396
|
|
|
397 /* /\* __code findMax1(struct Context* context, struct Tree* tree, struct Node* oldNode, struct Node* newNode) { *\/ */
|
|
|
398 /* /\* *newNode = *oldNode; *\/ */
|
|
|
399
|
|
|
400 /* /\* if (newNode->right) *\/ */
|
|
|
401 /* /\* goto meta(context, FindMax2); *\/ */
|
|
|
402
|
|
|
403 /* /\* tree->deleted->key = newNode->key; *\/ */
|
|
|
404 /* /\* tree->deleted->value = newNode->value; *\/ */
|
|
|
405
|
|
|
406 /* /\* tree->current = newNode; *\/ */
|
|
|
407
|
|
|
408 /* /\* goto meta(context, Delete2); *\/ */
|
|
|
409 /* /\* } *\/ */
|
|
|
410
|
|
|
411 /* /\* __code findMax1_stub(struct Context* context) { *\/ */
|
|
|
412 /* /\* goto findMax1(context, &context->data[Tree]->tree, context->data[Tree]->tree.current, &context->data[context->dataNum]->node); *\/ */
|
|
|
413 /* /\* } *\/ */
|
|
|
414
|
|
|
415
|
|
|
416 /* /\* __code findMax2(struct Context* context, struct Tree* tree, struct Node* oldNode, struct Node* newNode) { *\/ */
|
|
|
417 /* /\* *newNode = *oldNode; *\/ */
|
|
|
418
|
|
|
419 /* /\* if (newNode->right->right) { *\/ */
|
|
|
420 /* /\* tree->current = newNode->right; *\/ */
|
|
|
421 /* /\* newNode->right = context->heap; *\/ */
|
|
|
422
|
|
|
423 /* /\* allocator(context); *\/ */
|
|
|
424 /* /\* tree->current->parent = newNode; *\/ */
|
|
|
425
|
|
|
426 /* /\* goto meta(context, FindMax2); *\/ */
|
|
|
427 /* /\* } *\/ */
|
|
|
428
|
|
|
429 /* /\* tree->deleted->key = newNode->right->key; *\/ */
|
|
|
430 /* /\* tree->deleted->value = newNode->right->value; *\/ */
|
|
|
431
|
|
|
432 /* /\* tree->current = newNode; *\/ */
|
|
|
433
|
|
|
434 /* /\* goto meta(context, Delete2); *\/ */
|
|
|
435 /* /\* } *\/ */
|
|
|
436
|
|
|
437 /* /\* __code findMax2_stub(struct Context* context) { *\/ */
|
|
|
438 /* /\* goto findMax2(context, &context->data[Tree]->tree, context->data[Tree]->tree.current, &context->data[context->dataNum]->node); *\/ */
|
|
|
439 /* /\* } *\/ */
|
|
|
440
|
|
|
441 /* /\* __code deleteCase1(struct Context* context, struct Node* current) { *\/ */
|
|
|
442 /* /\* if (current->parent) *\/ */
|
|
|
443 /* /\* goto meta(context, DeleteCase2); *\/ */
|
|
|
444
|
|
|
445 /* /\* goto meta(context, Delete3); *\/ */
|
|
|
446 /* /\* } *\/ */
|
|
|
447
|
|
|
448 /* /\* __code deleteCase1_stub(struct Context* context) { *\/ */
|
|
|
449 /* /\* goto deleteCase1(context, context->data[Tree]->tree.current); *\/ */
|
|
|
450 /* /\* } *\/ */
|
|
|
451
|
|
|
452 /* /\* __code deleteCase2(struct Context* context, struct Tree* tree, struct Node* current) { *\/ */
|
|
|
453 /* /\* struct Node* sibling = current == current->parent->left ? current->parent->right : current->parent->left; *\/ */
|
|
|
454
|
|
|
455 /* /\* if ((sibling == NULL ? Black : sibling->color) == Red) { *\/ */
|
|
|
456 /* /\* current->parent->color = Red; *\/ */
|
|
|
457 /* /\* sibling->color = Black; *\/ */
|
|
|
458
|
|
|
459 /* /\* current == current->parent->left ? (current->parent->left = context->heap) : (current->parent->right = context->heap); *\/ */
|
|
|
460 /* /\* allocator(context); *\/ */
|
|
|
461 /* /\* context->data[context->dataNum]->node = *sibling; *\/ */
|
|
|
462
|
|
|
463 /* /\* tree->current = current->parent; *\/ */
|
|
|
464
|
|
|
465 /* /\* context->next = DeleteCase3; *\/ */
|
|
|
466 /* /\* stack_push(context->code_stack, &context->next); *\/ */
|
|
|
467
|
|
|
468 /* /\* if (current == current->parent->left) *\/ */
|
|
|
469 /* /\* goto meta(context, RotateL); *\/ */
|
|
|
470 /* /\* else *\/ */
|
|
|
471 /* /\* goto meta(context, RotateR); *\/ */
|
|
|
472 /* /\* } *\/ */
|
|
|
473
|
|
|
474 /* /\* goto meta(context, DeleteCase3); *\/ */
|
|
|
475 /* /\* } *\/ */
|
|
|
476
|
|
|
477 /* /\* __code deleteCase2_stub(struct Context* context) { *\/ */
|
|
|
478 /* /\* goto deleteCase2(context, &context->data[Tree]->tree, context->data[Tree]->tree.current); *\/ */
|
|
|
479 /* /\* } *\/ */
|
|
|
480
|
|
|
481 /* /\* __code deleteCase3(struct Context* context, struct Tree* tree, struct Node* current) { *\/ */
|
|
|
482 /* /\* struct Node* sibling = current == current->parent->left ? current->parent->right : current->parent->left; *\/ */
|
|
|
483
|
|
|
484 /* /\* if (current->parent->color == Black && *\/ */
|
|
|
485 /* /\* (sibling == NULL ? Black : sibling->color) == Black && *\/ */
|
|
|
486 /* /\* (sibling->left == NULL ? Black : sibling->left->color) == Black && *\/ */
|
|
|
487 /* /\* (sibling->right == NULL ? Black : sibling->right->color) == Black) { *\/ */
|
|
|
488 /* /\* sibling->color = Red; *\/ */
|
|
|
489
|
|
|
490 /* /\* tree->current = current->parent; *\/ */
|
|
|
491 /* /\* goto meta(context, DeleteCase1); *\/ */
|
|
|
492 /* /\* } *\/ */
|
|
|
493
|
|
|
494 /* /\* goto meta(context, DeleteCase4); *\/ */
|
|
|
495 /* /\* } *\/ */
|
|
|
496
|
|
|
497 /* /\* __code deleteCase3_stub(struct Context* context) { *\/ */
|
|
|
498 /* /\* goto deleteCase3(context, &context->data[Tree]->tree, context->data[Tree]->tree.current); *\/ */
|
|
|
499 /* /\* } *\/ */
|
|
|
500
|
|
|
501 /* /\* __code deleteCase4(struct Context* context, struct Node* current) { *\/ */
|
|
|
502 /* /\* struct Node* sibling = current == current->parent->left ? current->parent->right : current->parent->left; *\/ */
|
|
|
503
|
|
|
504 /* /\* if (current->parent->color == Red && *\/ */
|
|
|
505 /* /\* (sibling == NULL ? Black : sibling->color) == Black && *\/ */
|
|
|
506 /* /\* (sibling->left == NULL ? Black : sibling->left->color) == Black && *\/ */
|
|
|
507 /* /\* (sibling->right == NULL ? Black : sibling->right->color) == Black) { *\/ */
|
|
|
508 /* /\* sibling->color = Red; *\/ */
|
|
|
509 /* /\* current->parent->color = Black; *\/ */
|
|
|
510
|
|
|
511 /* /\* goto meta(context, Delete3); *\/ */
|
|
|
512 /* /\* } *\/ */
|
|
|
513
|
|
|
514 /* /\* goto meta(context, DeleteCase5); *\/ */
|
|
|
515 /* /\* } *\/ */
|
|
|
516
|
|
|
517 /* /\* __code deleteCase4_stub(struct Context* context) { *\/ */
|
|
|
518 /* /\* goto deleteCase4(context, context->data[Tree]->tree.current); *\/ */
|
|
|
519 /* /\* } *\/ */
|
|
|
520
|
|
|
521 /* /\* __code deleteCase5(struct Context* context, struct Tree* tree, struct Node* current) { *\/ */
|
|
|
522 /* /\* struct Node* sibling = current == current->parent->left ? current->parent->right : current->parent->left; *\/ */
|
|
|
523 /* /\* sibling->parent = current->parent; *\/ */
|
|
|
524
|
|
|
525 /* /\* if (current == current->parent->left && *\/ */
|
|
|
526 /* /\* (sibling == NULL ? Black : sibling->color) == Black && *\/ */
|
|
|
527 /* /\* (sibling->left == NULL ? Black : sibling->left->color) == Red && *\/ */
|
|
|
528 /* /\* (sibling->right == NULL ? Black : sibling->right->color) == Black) { *\/ */
|
|
|
529 /* /\* sibling->color = Red; *\/ */
|
|
|
530 /* /\* sibling->left->color = Black; *\/ */
|
|
|
531
|
|
|
532 /* /\* sibling == sibling->parent->left ? (sibling->parent->left = context->heap) : (sibling->parent->right = context->heap); *\/ */
|
|
|
533 /* /\* allocator(context); *\/ */
|
|
|
534 /* /\* struct Node* tmp = &context->data[context->dataNum]->node; *\/ */
|
|
|
535 /* /\* *tmp = *sibling; *\/ */
|
|
|
536 /* /\* tmp->parent = current; *\/ */
|
|
|
537
|
|
|
538 /* /\* tmp->left = context->heap; *\/ */
|
|
|
539 /* /\* allocator(context); *\/ */
|
|
|
540 /* /\* context->data[context->dataNum]->node = *sibling->left; *\/ */
|
|
|
541 /* /\* context->data[context->dataNum]->node.parent = tmp; *\/ */
|
|
|
542
|
|
|
543 /* /\* tree->current = tmp; *\/ */
|
|
|
544
|
|
|
545 /* /\* context->next = DeleteCase6; *\/ */
|
|
|
546 /* /\* stack_push(context->code_stack, &context->next); *\/ */
|
|
|
547
|
|
|
548 /* /\* goto meta(context, RotateR); *\/ */
|
|
|
549 /* /\* } else if (current == current->parent->right && *\/ */
|
|
|
550 /* /\* (sibling == NULL ? Black : sibling->color) == Black && *\/ */
|
|
|
551 /* /\* (sibling->left == NULL ? Black : sibling->left->color) == Black && *\/ */
|
|
|
552 /* /\* (sibling->right == NULL ? Black : sibling->right->color) == Red) { *\/ */
|
|
|
553 /* /\* sibling->color = Red; *\/ */
|
|
|
554 /* /\* sibling->right->color = Black; *\/ */
|
|
|
555
|
|
|
556 /* /\* sibling == sibling->parent->left ? (sibling->parent->left = context->heap) : (sibling->parent->right = context->heap); *\/ */
|
|
|
557 /* /\* allocator(context); *\/ */
|
|
|
558 /* /\* struct Node* tmp = &context->data[context->dataNum]->node; *\/ */
|
|
|
559 /* /\* *tmp = *sibling; *\/ */
|
|
|
560 /* /\* tmp->parent = current; *\/ */
|
|
|
561
|
|
|
562 /* /\* tmp->right = context->heap; *\/ */
|
|
|
563 /* /\* allocator(context); *\/ */
|
|
|
564 /* /\* context->data[context->dataNum]->node = *sibling->right; *\/ */
|
|
|
565 /* /\* context->data[context->dataNum]->node.parent = tmp; *\/ */
|
|
|
566
|
|
|
567 /* /\* tree->current = tmp; *\/ */
|
|
|
568
|
|
|
569 /* /\* context->next = DeleteCase6; *\/ */
|
|
|
570 /* /\* stack_push(context->code_stack, &context->next); *\/ */
|
|
|
571 /* /\* goto meta(context, RotateL); *\/ */
|
|
|
572 /* /\* } *\/ */
|
|
|
573
|
|
|
574 /* /\* goto meta(context, DeleteCase6); *\/ */
|
|
|
575 /* /\* } *\/ */
|
|
|
576
|
|
|
577 /* /\* __code deleteCase5_stub(struct Context* context) { *\/ */
|
|
|
578 /* /\* goto deleteCase5(context, &context->data[Tree]->tree, context->data[Tree]->tree.current); *\/ */
|
|
|
579 /* /\* } *\/ */
|
|
|
580
|
|
|
581 /* /\* __code deleteCase6(struct Context* context, struct Tree* tree, struct Node* current) { *\/ */
|
|
|
582 /* /\* struct Node* sibling = current == current->parent->left ? current->parent->right : current->parent->left; *\/ */
|
|
|
583
|
|
|
584 /* /\* sibling == sibling->parent->left ? (sibling->parent->left = context->heap) : (sibling->parent->right = context->heap); *\/ */
|
|
|
585 /* /\* allocator(context); *\/ */
|
|
|
586 /* /\* struct Node* tmp = &context->data[context->dataNum]->node; *\/ */
|
|
|
587 /* /\* *tmp = *sibling; *\/ */
|
|
|
588 /* /\* tmp->parent = current; *\/ */
|
|
|
589
|
|
|
590 /* /\* tmp->color = current->parent->color; *\/ */
|
|
|
591 /* /\* current->parent->color = Black; *\/ */
|
|
|
592
|
|
|
593 /* /\* context->next = Delete3; *\/ */
|
|
|
594 /* /\* stack_push(context->code_stack, &context->next); *\/ */
|
|
|
595
|
|
|
596 /* /\* if (current == current->parent->left) { *\/ */
|
|
|
597 /* /\* tmp->right->color = Black; *\/ */
|
|
|
598 /* /\* tree->current = current->parent; *\/ */
|
|
|
599
|
|
|
600 /* /\* goto meta(context, RotateL); *\/ */
|
|
|
601 /* /\* } else { *\/ */
|
|
|
602 /* /\* tmp->left->color = Black; *\/ */
|
|
|
603 /* /\* tree->current = current->parent; *\/ */
|
|
|
604
|
|
|
605 /* /\* goto meta(context, RotateR); *\/ */
|
|
|
606 /* /\* } *\/ */
|
|
|
607 /* /\* } *\/ */
|
|
|
608
|
|
|
609 /* /\* __code deleteCase6_stub(struct Context* context) { *\/ */
|
|
|
610 /* /\* goto deleteCase6(context, &context->data[Tree]->tree, context->data[Tree]->tree.current); *\/ */
|
|
|
611 /* /\* } *\/ */
|
