|
273
|
1 #include <stdio.h>
|
|
|
2
|
|
|
3 #include "../context.h"
|
|
|
4
|
|
|
5 extern enum Relational compare(struct Node* node1, struct Node* node2);
|
|
|
6
|
|
|
7 Tree* createRedBlackTree(struct Context* context) {
|
|
|
8 struct Tree* tree = new Tree();
|
|
|
9 struct RedBlackTree* redBlackTree = new RedBlackTree();
|
|
|
10 tree->tree = (union Data*)redBlackTree;
|
|
|
11 redBlackTree->root = NULL;
|
|
279
|
12 redBlackTree->nodeStack = createSingleLinkedStack(context);
|
|
273
|
13 tree->put = C_putRedBlackTree;
|
|
|
14 tree->get = C_getRedBlackTree;
|
|
|
15 // tree->remove = C_removeRedBlackTree;
|
|
|
16 // tree->clear = C_clearRedBlackTree;
|
|
|
17 return tree;
|
|
|
18 }
|
|
|
19
|
|
|
20 void printTree1(union Data* data) {
|
|
|
21 struct Node* node = &data->Node;
|
|
|
22 if (node == NULL) {
|
|
|
23 printf("NULL");
|
|
|
24 } else {
|
|
|
25 printf("key = %d (", node->key);
|
|
|
26 printTree1((union Data*)(node->right));
|
|
|
27 printf("), (");
|
|
|
28 printTree1((union Data*)(node->left));
|
|
|
29 printf(")");
|
|
|
30 }
|
|
|
31 }
|
|
|
32
|
|
|
33 void printTree(union Data* data) {
|
|
|
34 printTree1(data);
|
|
|
35 printf("\n");
|
|
|
36 }
|
|
|
37
|
|
|
38 __code putRedBlackTree(struct RedBlackTree* traverse, struct Node* node, struct Node* root, struct Node* newNode) {
|
|
|
39 printTree((union Data*)(traverse->root));
|
|
|
40 traverse->newNode = newNode;
|
|
|
41 traverse->root = newNode; // this should done at stackClear
|
|
|
42 traverse->parent = NULL;
|
|
|
43 if (root) {
|
|
|
44 traverse->current = root;
|
|
|
45 traverse->result = compare(traverse->current, node);
|
|
280
|
46 goto meta(context, C_replaceNode);
|
|
273
|
47 }
|
|
|
48
|
|
280
|
49 goto meta(context, C_insertNode);
|
|
273
|
50 }
|
|
|
51
|
|
|
52 __code putRedBlackTree_stub(struct Context* context) {
|
|
|
53 struct Node* newNode = &ALLOCATE(context, Node)->Node;
|
|
|
54 goto putRedBlackTree(context,
|
|
|
55 &Gearef(context, Tree)->tree->Tree.tree->RedBlackTree,
|
|
|
56 Gearef(context, Tree)->node,
|
|
|
57 Gearef(context, Tree)->tree->Tree.tree->RedBlackTree.root,
|
|
|
58 newNode
|
|
|
59 );
|
|
|
60 }
|
|
|
61
|
|
|
62 __code replaceNode(struct RedBlackTree* traverse, struct Node* oldNode, struct Node* newNode, struct Stack* nodeStack) {
|
|
|
63 traverse->previous = newNode;
|
|
|
64 *newNode = *oldNode;
|
|
|
65 nodeStack->stack = (union Data*)traverse->nodeStack;
|
|
|
66 nodeStack->data = (union Data*)(newNode);
|
|
|
67 nodeStack->next = C_replaceNode1;
|
|
|
68 goto meta(context, traverse->nodeStack->push);
|
|
|
69 }
|
|
|
70
|
|
|
71 __code replaceNode_stub(struct Context* context) {
|
|
|
72 goto replaceNode(context,
|
|
|
73 &Gearef(context, Tree)->tree->Tree.tree->RedBlackTree,
|
|
|
74 Gearef(context, Tree)->tree->Tree.tree->RedBlackTree.current,
|
|
|
75 //context->data[D_RedBlackTree]->RedBlackTree.newNode,
|
|
|
76 Gearef(context, Tree)->tree->Tree.tree->RedBlackTree.newNode,
|
|
|
77 Gearef(context, Stack));
|
|
|
78 }
|
|
|
79
|
|
|
80 __code replaceNode1(struct RedBlackTree* traverse, struct Node* node, struct Node* oldNode, struct Node* newNode, struct Node* newnewNode, int result, __code next(...)) {
|
|
|
81 if (result == EQ) {
|
|
|
82 newNode->value = node->value;
|
|
|
83 // go to stack clear
|
|
|
84 goto meta(context, next);
|
|
|
85 } else if (result == GT) {
|
|
|
86 traverse->current = oldNode->right;
|
|
|
87 newNode->right = newnewNode;
|
|
|
88 } else {
|
|
|
89 traverse->current = oldNode->left;
|
|
|
90 newNode->left = newnewNode;
|
|
|
91 }
|
|
|
92 traverse->newNode = newnewNode;
|
|
|
93 if (traverse->current) {
|
|
|
94 traverse->result = compare(traverse->current, node);
|
|
280
|
95 goto meta(context, C_replaceNode);
|
|
273
|
96 }
|
|
280
|
97 goto meta(context, C_insertNode);
|
|
273
|
98
|
|
|
99 }
|
|
|
100
|
|
|
101 __code replaceNode1_stub(struct Context* context) {
|
|
|
102 struct Node* newnewNode = &ALLOCATE(context, Node)->Node;
|
|
|
103 goto replaceNode1(context,
|
|
|
104 &Gearef(context, Tree)->tree->Tree.tree->RedBlackTree,
|
|
|
105 Gearef(context, Tree)->node,
|
|
|
106 Gearef(context, Tree)->tree->Tree.tree->RedBlackTree.current,
|
|
|
107 Gearef(context, Tree)->tree->Tree.tree->RedBlackTree.previous,
|
|
|
108 newnewNode,
|
|
|
109 Gearef(context, Tree)->tree->Tree.tree->RedBlackTree.result,
|
|
|
110 Gearef(context, Tree)->next);
|
|
|
111 }
|
|
|
112
|
|
|
113 __code insertNode(struct RedBlackTree* traverse, struct Stack *nodeStack, struct Node* node, struct Node* newNode) {
|
|
|
114 *newNode = *node;
|
|
|
115 newNode->color = Red;
|
|
|
116 traverse->current = newNode;
|
|
|
117 nodeStack->stack = (union Data*)traverse->nodeStack;
|
|
|
118 nodeStack->next = C_insertCase1;
|
|
|
119 goto meta(context, traverse->nodeStack->get2);
|
|
|
120 }
|
|
|
121
|
|
|
122 __code insertNode_stub(struct Context* context) {
|
|
|
123 goto insertNode(context,
|
|
|
124 &Gearef(context, Tree)->tree->Tree.tree->RedBlackTree,
|
|
|
125 Gearef(context, Stack),
|
|
|
126 Gearef(context, Tree)->node,
|
|
|
127 Gearef(context, Tree)->tree->Tree.tree->RedBlackTree.newNode);
|
|
|
128 }
|
|
|
129
|
|
|
130 __code insertCase1(struct RedBlackTree* traverse, struct Node *parent, struct Node *grandparent) {
|
|
|
131 if (parent != NULL) {
|
|
|
132 traverse->parent = parent;
|
|
|
133 traverse->grandparent = grandparent;
|
|
280
|
134 goto meta(context, C_insertCase2);
|
|
273
|
135 }
|
|
|
136 traverse->root->color = Black;
|
|
280
|
137 goto meta(context, C_stackClear);
|
|
273
|
138 }
|
|
|
139
|
|
|
140 __code insertCase1_stub(struct Context* context) {
|
|
|
141 goto insertCase1(context,
|
|
|
142 &Gearef(context, Tree)->tree->Tree.tree->RedBlackTree,
|
|
|
143 &context->data[D_Stack]->Stack.data->Node,
|
|
|
144 &context->data[D_Stack]->Stack.data1->Node);
|
|
|
145 }
|
|
|
146
|
|
|
147 __code insertCase2(struct RedBlackTree* traverse) {
|
|
|
148 if (traverse->parent->color == Black) {
|
|
280
|
149 goto meta(context, C_stackClear);
|
|
273
|
150 }
|
|
280
|
151 goto meta(context, C_insertCase3);
|
|
273
|
152 }
|
|
|
153
|
|
|
154 __code insertCase2_stub(struct Context* context) {
|
|
|
155 goto insertCase2(context, &Gearef(context, Tree)->tree->Tree.tree->RedBlackTree);
|
|
|
156 }
|
|
|
157
|
|
|
158 __code insertCase3(struct RedBlackTree* traverse, struct Stack* nodeStack) {
|
|
|
159 struct Node* uncle;
|
|
|
160
|
|
|
161 if (traverse->grandparent->left == traverse->parent)
|
|
|
162 uncle = traverse->grandparent->right;
|
|
|
163 else
|
|
|
164 uncle = traverse->grandparent->left;
|
|
|
165
|
|
|
166 if (uncle && (uncle->color == Red)) {
|
|
|
167 // do insertcase1 on grandparent, stack must be pop by two
|
|
|
168 traverse->parent->color = Black;
|
|
|
169 uncle->color = Black;
|
|
|
170 traverse->grandparent->color = Red;
|
|
|
171 traverse->current = traverse->grandparent;
|
|
|
172 nodeStack->stack = (union Data*)traverse->nodeStack;
|
|
|
173 nodeStack->next = C_insertCase1;
|
|
|
174 goto meta(context, traverse->nodeStack->pop2);
|
|
|
175 }
|
|
280
|
176 goto meta(context, C_insertCase4);
|
|
273
|
177 }
|
|
|
178
|
|
|
179 __code insertCase3_stub(struct Context* context) {
|
|
|
180 goto insertCase3(context, &Gearef(context, Tree)->tree->Tree.tree->RedBlackTree,
|
|
|
181 Gearef(context, Stack));
|
|
|
182 }
|
|
|
183
|
|
|
184 __code insertCase4(struct RedBlackTree* traverse, struct RotateTree* rotateTree) {
|
|
|
185 struct Stack* nodeStack = traverse->nodeStack;
|
|
|
186
|
|
|
187 if ((traverse->current == traverse->parent->right) && (traverse->parent == traverse->grandparent->left)) {
|
|
|
188 traverse->current = traverse->current->left;
|
|
|
189 traverse->parent = traverse->grandparent;
|
|
|
190
|
|
|
191 rotateTree->traverse = traverse;
|
|
|
192 rotateTree->next = C_insertCase5;
|
|
|
193
|
|
|
194 nodeStack->stack = (union Data*)traverse->nodeStack;
|
|
|
195 nodeStack->next = C_rotateLeft;
|
|
|
196 goto meta(context, nodeStack->pop);
|
|
|
197 } else if ((traverse->current == traverse->parent->left) && (traverse->parent == traverse->grandparent->right)) {
|
|
|
198 traverse->parent = traverse->grandparent;
|
|
|
199 traverse->current = traverse->current->right;
|
|
|
200
|
|
|
201 rotateTree->traverse = traverse;
|
|
|
202 rotateTree->next = C_insertCase5;
|
|
|
203
|
|
|
204 nodeStack->stack = (union Data*)traverse->nodeStack;
|
|
|
205 nodeStack->next = C_rotateRight;
|
|
|
206 goto meta(context, nodeStack->pop);
|
|
|
207 }
|
|
|
208
|
|
280
|
209 goto meta(context, C_insertCase5);
|
|
273
|
210 }
|
|
|
211
|
|
|
212 __code insertCase4_stub(struct Context* context) {
|
|
|
213 goto insertCase4(context, &Gearef(context, Tree)->tree->Tree.tree->RedBlackTree, Gearef(context, RotateTree));
|
|
|
214 }
|
|
|
215
|
|
|
216 __code insertCase5(struct RedBlackTree* traverse,struct Stack *nodeStack) {
|
|
|
217 nodeStack->stack = (union Data*)traverse->nodeStack;
|
|
|
218 nodeStack->next = C_insertCase51;
|
|
|
219 goto meta(context, traverse->nodeStack->pop2);
|
|
|
220 }
|
|
|
221
|
|
|
222 __code insertCase5_stub(struct Context* context) {
|
|
|
223 goto insertCase5(context, &Gearef(context, Tree)->tree->Tree.tree->RedBlackTree, Gearef(context, Stack));
|
|
|
224 }
|
|
|
225
|
|
|
226 __code insertCase51(struct RedBlackTree* traverse, struct RotateTree *rotateTree, struct Node* current, struct Node* parent, struct Node* grandparent) {
|
|
|
227 traverse->parent = parent;
|
|
|
228 traverse->grandparent = grandparent;
|
|
|
229
|
|
|
230 parent->color = Black;
|
|
|
231 grandparent->color = Red;
|
|
|
232
|
|
|
233 traverse->current = grandparent;
|
|
|
234
|
|
|
235 rotateTree->traverse = traverse;
|
|
|
236 rotateTree->next = C_stackClear;
|
|
|
237
|
|
|
238 if ((current == parent->left) && (parent == grandparent->left))
|
|
280
|
239 goto meta(context, C_rotateRight);
|
|
273
|
240 else
|
|
280
|
241 goto meta(context, C_rotateLeft);
|
|
273
|
242 }
|
|
|
243
|
|
|
244 __code insertCase51_stub(struct Context* context) {
|
|
|
245 struct Node* parent = &context->data[D_Stack]->Stack.data->Node;
|
|
|
246 struct Node* grandparent = &context->data[D_Stack]->Stack.data1->Node;
|
|
|
247 goto insertCase51(context,
|
|
|
248 &Gearef(context, Tree)->tree->Tree.tree->RedBlackTree,
|
|
|
249 Gearef(context, RotateTree),
|
|
|
250 Gearef(context, Tree)->tree->Tree.tree->RedBlackTree.current,
|
|
|
251 parent,
|
|
|
252 grandparent);
|
|
|
253 }
|
|
|
254
|
|
|
255 __code rotateLeft(struct RedBlackTree* traverse,struct Stack* nodeStack) {
|
|
|
256 nodeStack->stack = (union Data*)traverse->nodeStack;
|
|
|
257 nodeStack->next = C_rotateLeft1;
|
|
|
258 goto meta(context, traverse->nodeStack->get);
|
|
|
259 }
|
|
|
260
|
|
|
261 __code rotateLeft_stub(struct Context* context) {
|
|
|
262 struct RedBlackTree* traverse = context->data[D_RotateTree]->RotateTree.traverse;
|
|
|
263 goto rotateLeft(context, traverse, Gearef(context, Stack));
|
|
|
264 }
|
|
|
265
|
|
|
266 __code rotateLeft1(struct Node* node, struct RedBlackTree* traverse, struct Node *parent,struct RotateTree *rotateTree) {
|
|
|
267 struct Node* tmp = node->right;
|
|
|
268
|
|
|
269 if (parent) {
|
|
|
270 if (node == parent->left)
|
|
|
271 parent->left = tmp;
|
|
|
272 else
|
|
|
273 parent->right = tmp;
|
|
|
274 } else {
|
|
|
275 traverse->root = tmp;
|
|
|
276 }
|
|
|
277
|
|
|
278 node->right = tmp->left;
|
|
|
279 tmp->left = node;
|
|
|
280 traverse->current = tmp;
|
|
|
281
|
|
|
282 goto meta(context, rotateTree->next);
|
|
|
283 }
|
|
|
284
|
|
|
285 __code rotateLeft1_stub(struct Context* context) {
|
|
|
286 struct RedBlackTree* traverse = context->data[D_RotateTree]->RotateTree.traverse;
|
|
|
287 struct Node* parent = &context->data[D_Stack]->Stack.data->Node;
|
|
|
288 goto rotateLeft1(context,
|
|
|
289 traverse->current,
|
|
|
290 traverse,
|
|
|
291 parent,
|
|
|
292 Gearef(context, RotateTree));
|
|
|
293 }
|
|
|
294
|
|
|
295 __code rotateRight(struct RedBlackTree* traverse,struct Stack *nodeStack) {
|
|
|
296 nodeStack->stack = (union Data*)traverse->nodeStack;
|
|
|
297 nodeStack->next = C_rotateRight1;
|
|
|
298 goto meta(context, traverse->nodeStack->get);
|
|
|
299 }
|
|
|
300
|
|
|
301 __code rotateRight_stub(struct Context* context) {
|
|
|
302 struct RedBlackTree* traverse = context->data[D_RotateTree]->RotateTree.traverse;
|
|
|
303 goto rotateLeft(context, traverse, Gearef(context, Stack));
|
|
|
304 }
|
|
|
305
|
|
|
306 __code rotateRight1(struct Node* node, struct RedBlackTree* traverse,struct Node *parent,struct RotateTree *rotateTree) {
|
|
|
307 struct Node* tmp = node->left;
|
|
|
308
|
|
|
309 if (parent) {
|
|
|
310 if (node == parent->left)
|
|
|
311 parent->left = tmp;
|
|
|
312 else
|
|
|
313 parent->right = tmp;
|
|
|
314 } else {
|
|
|
315 traverse->root = tmp;
|
|
|
316 }
|
|
|
317
|
|
|
318 node->left = tmp->right;
|
|
|
319 tmp->right = node;
|
|
|
320 traverse->current = tmp;
|
|
|
321
|
|
|
322 goto meta(context, rotateTree->next);
|
|
|
323 }
|
|
|
324
|
|
|
325 __code rotateRight1_stub(struct Context* context) {
|
|
|
326 struct RedBlackTree* traverse = context->data[D_RotateTree]->RotateTree.traverse;
|
|
|
327 struct Node* parent = &context->data[D_Stack]->Stack.data->Node;
|
|
|
328 goto rotateRight1(context,
|
|
|
329 traverse->current,
|
|
|
330 traverse,
|
|
|
331 parent,
|
|
|
332 Gearef(context, RotateTree));
|
|
|
333 }
|
|
|
334
|
|
|
335 __code stackClear(struct RedBlackTree* traverse,struct Stack *nodeStack, __code next(...)) {
|
|
|
336 traverse->current = 0;
|
|
|
337 nodeStack->stack = (union Data*)traverse->nodeStack;
|
|
|
338 nodeStack->next = next;
|
|
|
339 goto meta(context, traverse->nodeStack->clear);
|
|
|
340 }
|
|
|
341
|
|
|
342 __code stackClear_stub(struct Context* context) {
|
|
|
343 goto stackClear(context, &Gearef(context, Tree)->tree->Tree.tree->RedBlackTree, Gearef(context, Stack),
|
|
|
344 Gearef(context, Tree)->next);
|
|
|
345 }
|
|
|
346
|
|
|
347
|
|
|
348 __code getRedBlackTree(struct RedBlackTree* traverse, __code next(...)) {
|
|
|
349 if (traverse->root) {
|
|
|
350 traverse->current = traverse->root;
|
|
|
351
|
|
280
|
352 goto meta(context, C_search);
|
|
273
|
353 }
|
|
|
354
|
|
|
355 goto next(...);
|
|
|
356 }
|
|
|
357
|
|
|
358 __code getRedBlackTree_stub(struct Context* context) {
|
|
|
359 goto getRedBlackTree(context, &Gearef(context, Tree)->tree->Tree.tree->RedBlackTree, Gearef(context, Tree)->next);
|
|
|
360 }
|
|
|
361
|
|
|
362 __code search(struct RedBlackTree* traverse, struct Node* node, __code next(...)) {
|
|
|
363 // compare(context, traverse, traverse->current->key, node->key);
|
|
|
364 traverse->result = compare(traverse->current, node);
|
|
|
365 if (traverse->result == EQ) {
|
|
|
366 *node = *traverse->current;
|
|
|
367
|
|
|
368 goto meta(context, next);
|
|
|
369 } else if (traverse->result == GT) {
|
|
|
370 traverse->current = traverse->current->right;
|
|
|
371 } else {
|
|
|
372 traverse->current = traverse->current->left;
|
|
|
373 }
|
|
|
374
|
|
|
375 if (traverse->current)
|
|
280
|
376 goto meta(context, C_search);
|
|
273
|
377
|
|
|
378 goto next(...);
|
|
|
379 }
|
|
|
380
|
|
|
381 __code search_stub(struct Context* context) {
|
|
|
382 goto search(context, &Gearef(context, Tree)->tree->Tree.tree->RedBlackTree, Gearef(context, Node), Gearef(context, Tree)->next);
|
|
|
383 }
|
|
|
384
|
|
|
385 /* /\* __code delete(struct Context* context, struct Tree* tree) { *\/ */
|
|
|
386 /* /\* if (tree->root) { *\/ */
|
|
|
387 /* /\* stack_push(context->code_stack, &context->next); *\/ */
|
|
|
388 /* /\* context->next = Delete1; *\/ */
|
|
|
389 /* /\* goto meta(context, Get); *\/ */
|
|
|
390 /* /\* } *\/ */
|
|
|
391
|
|
|
392 /* /\* goto meta(context, context->next); *\/ */
|
|
|
393 /* /\* } *\/ */
|
|
|
394
|
|
|
395 /* /\* __code delete_stub(struct Context* context) { *\/ */
|
|
|
396 /* /\* goto delete(context, &context->data[Tree]->tree); *\/ */
|
|
|
397 /* /\* } *\/ */
|
|
|
398
|
|
|
399 /* /\* __code delete1(struct Context* context, struct Tree* tree, struct Allocate* allocate) { *\/ */
|
|
|
400 /* /\* allocate->size = sizeof(struct Node); *\/ */
|
|
|
401 /* /\* allocator(context); *\/ */
|
|
|
402
|
|
|
403 /* /\* struct Node* root = tree->root; *\/ */
|
|
|
404
|
|
|
405 /* /\* tree->root = &context->data[context->dataNum]->node; *\/ */
|
|
|
406 /* /\* tree->current = root; *\/ */
|
|
|
407
|
|
|
408 /* /\* compare(context, tree, tree->current->key, context->data[Node]->node.key); *\/ */
|
|
|
409
|
|
|
410 /* /\* goto meta(context, Replace_d1); *\/ */
|
|
|
411 /* /\* } *\/ */
|
|
|
412
|
|
|
413 /* /\* __code delete1_stub(struct Context* context) { *\/ */
|
|
|
414 /* /\* goto delete1(context, &context->data[Tree]->tree, &context->data[Allocate]->allocate); *\/ */
|
|
|
415 /* /\* } *\/ */
|
|
|
416
|
|
|
417 /* /\* __code delete2(struct Context* context, struct Node* current) { *\/ */
|
|
|
418 /* /\* if (current->color == Black) { *\/ */
|
|
|
419 /* /\* struct Node* child = current->right == NULL ? current->left : current->right; *\/ */
|
|
|
420 /* /\* current->color = child == NULL ? Black : child->color; *\/ */
|
|
|
421
|
|
|
422 /* /\* goto meta(context, DeleteCase1); *\/ */
|
|
|
423 /* /\* } *\/ */
|
|
|
424
|
|
|
425 /* /\* goto meta(context, Delete3); *\/ */
|
|
|
426 /* /\* } *\/ */
|
|
|
427
|
|
|
428 /* /\* __code delete2_stub(struct Context* context) { *\/ */
|
|
|
429 /* /\* goto delete2(context, context->data[Tree]->tree.current); *\/ */
|
|
|
430 /* /\* } *\/ */
|
|
|
431
|
|
|
432 /* /\* __code delete3(struct Context* context, struct Tree* tree, struct Node* current) { *\/ */
|
|
|
433 /* /\* struct Node* tmp = current->right == NULL ? current->left : current->right; *\/ */
|
|
|
434
|
|
|
435 /* /\* if (current->parent) { *\/ */
|
|
|
436 /* /\* if (current == current->parent->left) *\/ */
|
|
|
437 /* /\* current->parent->left = tmp; *\/ */
|
|
|
438 /* /\* else *\/ */
|
|
|
439 /* /\* current->parent->right = tmp; *\/ */
|
|
|
440 /* /\* } else { *\/ */
|
|
|
441 /* /\* tree->root = tmp; *\/ */
|
|
|
442 /* /\* } *\/ */
|
|
|
443
|
|
|
444 /* /\* if (tmp) *\/ */
|
|
|
445 /* /\* tmp->parent = current->parent; *\/ */
|
|
|
446
|
|
|
447 /* /\* if (current->parent == NULL && tmp) *\/ */
|
|
|
448 /* /\* tmp->color = Black; *\/ */
|
|
|
449
|
|
|
450 /* /\* current == current->parent->left ? (current->parent->left = NULL) : (current->parent->right = NULL); *\/ */
|
|
|
451
|
|
|
452 /* /\* stack_pop(context->code_stack, &context->next); *\/ */
|
|
|
453 /* /\* goto meta(context, context->next); *\/ */
|
|
|
454 /* /\* } *\/ */
|
|
|
455
|
|
|
456 /* /\* __code delete3_stub(struct Context* context) { *\/ */
|
|
|
457 /* /\* goto delete3(context, &context->data[Tree]->tree, context->data[Tree]->tree.current); *\/ */
|
|
|
458 /* /\* } *\/ */
|
|
|
459
|
|
|
460 /* /\* __code replaceNodeForDelete1(struct Context* context, struct Tree* tree, struct Node* oldNode, struct Node* newNode, int result) { *\/ */
|
|
|
461 /* /\* *newNode = *oldNode; *\/ */
|
|
|
462
|
|
|
463 /* /\* if (result == EQ) *\/ */
|
|
|
464 /* /\* goto meta(context, Replace_d2); *\/ */
|
|
|
465 /* /\* else if (result == GT) *\/ */
|
|
|
466 /* /\* tree->current = newNode->right; *\/ */
|
|
|
467 /* /\* else *\/ */
|
|
|
468 /* /\* tree->current = newNode->left; *\/ */
|
|
|
469
|
|
|
470 /* /\* tree->current->parent = newNode; *\/ */
|
|
|
471
|
|
|
472 /* /\* if (tree->current->left == NULL && tree->current->right == NULL) *\/ */
|
|
|
473 /* /\* goto meta(context, Delete2); *\/ */
|
|
|
474
|
|
|
475 /* /\* if (result == GT) *\/ */
|
|
|
476 /* /\* newNode->right = context->heap; *\/ */
|
|
|
477 /* /\* else if (result == LT) *\/ */
|
|
|
478 /* /\* newNode->left = context->heap; *\/ */
|
|
|
479
|
|
|
480 /* /\* allocator(context); *\/ */
|
|
|
481
|
|
|
482 /* /\* compare(context, tree, tree->current->key, context->data[Node]->node.key); *\/ */
|
|
|
483
|
|
|
484 /* /\* goto meta(context, Replace_d1); *\/ */
|
|
|
485 /* /\* } *\/ */
|
|
|
486
|
|
|
487 /* /\* __code replaceNodeForDelete1_stub(struct Context* context) { *\/ */
|
|
|
488 /* /\* goto replaceNodeForDelete1(context, &context->data[Tree]->tree, context->data[Tree]->tree.current, &context->data[context->dataNum]->node, context->data[Tree]->tree.result); *\/ */
|
|
|
489 /* /\* } *\/ */
|
|
|
490
|
|
|
491 /* /\* __code replaceNodeForDelete2(struct Context* context, struct Tree* tree, struct Node* newNode) { *\/ */
|
|
|
492 /* /\* if (tree->current->left && tree->current->right) { *\/ */
|
|
|
493 /* /\* newNode->left->parent = newNode; *\/ */
|
|
|
494 /* /\* tree->current = newNode->left; *\/ */
|
|
|
495 /* /\* newNode->left = context->heap; *\/ */
|
|
|
496 /* /\* tree->deleted = newNode; *\/ */
|
|
|
497
|
|
|
498 /* /\* allocator(context); *\/ */
|
|
|
499 /* /\* tree->current->parent = newNode; *\/ */
|
|
|
500
|
|
|
501 /* /\* goto meta(context, FindMax1); *\/ */
|
|
|
502 /* /\* } *\/ */
|
|
|
503
|
|
|
504 /* /\* goto meta(context, Delete2); *\/ */
|
|
|
505 /* /\* } *\/ */
|
|
|
506
|
|
|
507 /* /\* __code replaceNodeForDelete2_stub(struct Context* context) { *\/ */
|
|
|
508 /* /\* goto replaceNodeForDelete2(context, &context->data[Tree]->tree, &context->data[context->dataNum]->node); *\/ */
|
|
|
509 /* /\* } *\/ */
|
|
|
510
|
|
|
511 /* /\* __code findMax1(struct Context* context, struct Tree* tree, struct Node* oldNode, struct Node* newNode) { *\/ */
|
|
|
512 /* /\* *newNode = *oldNode; *\/ */
|
|
|
513
|
|
|
514 /* /\* if (newNode->right) *\/ */
|
|
|
515 /* /\* goto meta(context, FindMax2); *\/ */
|
|
|
516
|
|
|
517 /* /\* tree->deleted->key = newNode->key; *\/ */
|
|
|
518 /* /\* tree->deleted->value = newNode->value; *\/ */
|
|
|
519
|
|
|
520 /* /\* tree->current = newNode; *\/ */
|
|
|
521
|
|
|
522 /* /\* goto meta(context, Delete2); *\/ */
|
|
|
523 /* /\* } *\/ */
|
|
|
524
|
|
|
525 /* /\* __code findMax1_stub(struct Context* context) { *\/ */
|
|
|
526 /* /\* goto findMax1(context, &context->data[Tree]->tree, context->data[Tree]->tree.current, &context->data[context->dataNum]->node); *\/ */
|
|
|
527 /* /\* } *\/ */
|
|
|
528
|
|
|
529
|
|
|
530 /* /\* __code findMax2(struct Context* context, struct Tree* tree, struct Node* oldNode, struct Node* newNode) { *\/ */
|
|
|
531 /* /\* *newNode = *oldNode; *\/ */
|
|
|
532
|
|
|
533 /* /\* if (newNode->right->right) { *\/ */
|
|
|
534 /* /\* tree->current = newNode->right; *\/ */
|
|
|
535 /* /\* newNode->right = context->heap; *\/ */
|
|
|
536
|
|
|
537 /* /\* allocator(context); *\/ */
|
|
|
538 /* /\* tree->current->parent = newNode; *\/ */
|
|
|
539
|
|
|
540 /* /\* goto meta(context, FindMax2); *\/ */
|
|
|
541 /* /\* } *\/ */
|
|
|
542
|
|
|
543 /* /\* tree->deleted->key = newNode->right->key; *\/ */
|
|
|
544 /* /\* tree->deleted->value = newNode->right->value; *\/ */
|
|
|
545
|
|
|
546 /* /\* tree->current = newNode; *\/ */
|
|
|
547
|
|
|
548 /* /\* goto meta(context, Delete2); *\/ */
|
|
|
549 /* /\* } *\/ */
|
|
|
550
|
|
|
551 /* /\* __code findMax2_stub(struct Context* context) { *\/ */
|
|
|
552 /* /\* goto findMax2(context, &context->data[Tree]->tree, context->data[Tree]->tree.current, &context->data[context->dataNum]->node); *\/ */
|
|
|
553 /* /\* } *\/ */
|
|
|
554
|
|
|
555 /* /\* __code deleteCase1(struct Context* context, struct Node* current) { *\/ */
|
|
|
556 /* /\* if (current->parent) *\/ */
|
|
|
557 /* /\* goto meta(context, DeleteCase2); *\/ */
|
|
|
558
|
|
|
559 /* /\* goto meta(context, Delete3); *\/ */
|
|
|
560 /* /\* } *\/ */
|
|
|
561
|
|
|
562 /* /\* __code deleteCase1_stub(struct Context* context) { *\/ */
|
|
|
563 /* /\* goto deleteCase1(context, context->data[Tree]->tree.current); *\/ */
|
|
|
564 /* /\* } *\/ */
|
|
|
565
|
|
|
566 /* /\* __code deleteCase2(struct Context* context, struct Tree* tree, struct Node* current) { *\/ */
|
|
|
567 /* /\* struct Node* sibling = current == current->parent->left ? current->parent->right : current->parent->left; *\/ */
|
|
|
568
|
|
|
569 /* /\* if ((sibling == NULL ? Black : sibling->color) == Red) { *\/ */
|
|
|
570 /* /\* current->parent->color = Red; *\/ */
|
|
|
571 /* /\* sibling->color = Black; *\/ */
|
|
|
572
|
|
|
573 /* /\* current == current->parent->left ? (current->parent->left = context->heap) : (current->parent->right = context->heap); *\/ */
|
|
|
574 /* /\* allocator(context); *\/ */
|
|
|
575 /* /\* context->data[context->dataNum]->node = *sibling; *\/ */
|
|
|
576
|
|
|
577 /* /\* tree->current = current->parent; *\/ */
|
|
|
578
|
|
|
579 /* /\* context->next = DeleteCase3; *\/ */
|
|
|
580 /* /\* stack_push(context->code_stack, &context->next); *\/ */
|
|
|
581
|
|
|
582 /* /\* if (current == current->parent->left) *\/ */
|
|
|
583 /* /\* goto meta(context, RotateL); *\/ */
|
|
|
584 /* /\* else *\/ */
|
|
|
585 /* /\* goto meta(context, RotateR); *\/ */
|
|
|
586 /* /\* } *\/ */
|
|
|
587
|
|
|
588 /* /\* goto meta(context, DeleteCase3); *\/ */
|
|
|
589 /* /\* } *\/ */
|
|
|
590
|
|
|
591 /* /\* __code deleteCase2_stub(struct Context* context) { *\/ */
|
|
|
592 /* /\* goto deleteCase2(context, &context->data[Tree]->tree, context->data[Tree]->tree.current); *\/ */
|
|
|
593 /* /\* } *\/ */
|
|
|
594
|
|
|
595 /* /\* __code deleteCase3(struct Context* context, struct Tree* tree, struct Node* current) { *\/ */
|
|
|
596 /* /\* struct Node* sibling = current == current->parent->left ? current->parent->right : current->parent->left; *\/ */
|
|
|
597
|
|
|
598 /* /\* if (current->parent->color == Black && *\/ */
|
|
|
599 /* /\* (sibling == NULL ? Black : sibling->color) == Black && *\/ */
|
|
|
600 /* /\* (sibling->left == NULL ? Black : sibling->left->color) == Black && *\/ */
|
|
|
601 /* /\* (sibling->right == NULL ? Black : sibling->right->color) == Black) { *\/ */
|
|
|
602 /* /\* sibling->color = Red; *\/ */
|
|
|
603
|
|
|
604 /* /\* tree->current = current->parent; *\/ */
|
|
|
605 /* /\* goto meta(context, DeleteCase1); *\/ */
|
|
|
606 /* /\* } *\/ */
|
|
|
607
|
|
|
608 /* /\* goto meta(context, DeleteCase4); *\/ */
|
|
|
609 /* /\* } *\/ */
|
|
|
610
|
|
|
611 /* /\* __code deleteCase3_stub(struct Context* context) { *\/ */
|
|
|
612 /* /\* goto deleteCase3(context, &context->data[Tree]->tree, context->data[Tree]->tree.current); *\/ */
|
|
|
613 /* /\* } *\/ */
|
|
|
614
|
|
|
615 /* /\* __code deleteCase4(struct Context* context, struct Node* current) { *\/ */
|
|
|
616 /* /\* struct Node* sibling = current == current->parent->left ? current->parent->right : current->parent->left; *\/ */
|
|
|
617
|
|
|
618 /* /\* if (current->parent->color == Red && *\/ */
|
|
|
619 /* /\* (sibling == NULL ? Black : sibling->color) == Black && *\/ */
|
|
|
620 /* /\* (sibling->left == NULL ? Black : sibling->left->color) == Black && *\/ */
|
|
|
621 /* /\* (sibling->right == NULL ? Black : sibling->right->color) == Black) { *\/ */
|
|
|
622 /* /\* sibling->color = Red; *\/ */
|
|
|
623 /* /\* current->parent->color = Black; *\/ */
|
|
|
624
|
|
|
625 /* /\* goto meta(context, Delete3); *\/ */
|
|
|
626 /* /\* } *\/ */
|
|
|
627
|
|
|
628 /* /\* goto meta(context, DeleteCase5); *\/ */
|
|
|
629 /* /\* } *\/ */
|
|
|
630
|
|
|
631 /* /\* __code deleteCase4_stub(struct Context* context) { *\/ */
|
|
|
632 /* /\* goto deleteCase4(context, context->data[Tree]->tree.current); *\/ */
|
|
|
633 /* /\* } *\/ */
|
|
|
634
|
|
|
635 /* /\* __code deleteCase5(struct Context* context, struct Tree* tree, struct Node* current) { *\/ */
|
|
|
636 /* /\* struct Node* sibling = current == current->parent->left ? current->parent->right : current->parent->left; *\/ */
|
|
|
637 /* /\* sibling->parent = current->parent; *\/ */
|
|
|
638
|
|
|
639 /* /\* if (current == current->parent->left && *\/ */
|
|
|
640 /* /\* (sibling == NULL ? Black : sibling->color) == Black && *\/ */
|
|
|
641 /* /\* (sibling->left == NULL ? Black : sibling->left->color) == Red && *\/ */
|
|
|
642 /* /\* (sibling->right == NULL ? Black : sibling->right->color) == Black) { *\/ */
|
|
|
643 /* /\* sibling->color = Red; *\/ */
|
|
|
644 /* /\* sibling->left->color = Black; *\/ */
|
|
|
645
|
|
|
646 /* /\* sibling == sibling->parent->left ? (sibling->parent->left = context->heap) : (sibling->parent->right = context->heap); *\/ */
|
|
|
647 /* /\* allocator(context); *\/ */
|
|
|
648 /* /\* struct Node* tmp = &context->data[context->dataNum]->node; *\/ */
|
|
|
649 /* /\* *tmp = *sibling; *\/ */
|
|
|
650 /* /\* tmp->parent = current; *\/ */
|
|
|
651
|
|
|
652 /* /\* tmp->left = context->heap; *\/ */
|
|
|
653 /* /\* allocator(context); *\/ */
|
|
|
654 /* /\* context->data[context->dataNum]->node = *sibling->left; *\/ */
|
|
|
655 /* /\* context->data[context->dataNum]->node.parent = tmp; *\/ */
|
|
|
656
|
|
|
657 /* /\* tree->current = tmp; *\/ */
|
|
|
658
|
|
|
659 /* /\* context->next = DeleteCase6; *\/ */
|
|
|
660 /* /\* stack_push(context->code_stack, &context->next); *\/ */
|
|
|
661
|
|
|
662 /* /\* goto meta(context, RotateR); *\/ */
|
|
|
663 /* /\* } else if (current == current->parent->right && *\/ */
|
|
|
664 /* /\* (sibling == NULL ? Black : sibling->color) == Black && *\/ */
|
|
|
665 /* /\* (sibling->left == NULL ? Black : sibling->left->color) == Black && *\/ */
|
|
|
666 /* /\* (sibling->right == NULL ? Black : sibling->right->color) == Red) { *\/ */
|
|
|
667 /* /\* sibling->color = Red; *\/ */
|
|
|
668 /* /\* sibling->right->color = Black; *\/ */
|
|
|
669
|
|
|
670 /* /\* sibling == sibling->parent->left ? (sibling->parent->left = context->heap) : (sibling->parent->right = context->heap); *\/ */
|
|
|
671 /* /\* allocator(context); *\/ */
|
|
|
672 /* /\* struct Node* tmp = &context->data[context->dataNum]->node; *\/ */
|
|
|
673 /* /\* *tmp = *sibling; *\/ */
|
|
|
674 /* /\* tmp->parent = current; *\/ */
|
|
|
675
|
|
|
676 /* /\* tmp->right = context->heap; *\/ */
|
|
|
677 /* /\* allocator(context); *\/ */
|
|
|
678 /* /\* context->data[context->dataNum]->node = *sibling->right; *\/ */
|
|
|
679 /* /\* context->data[context->dataNum]->node.parent = tmp; *\/ */
|
|
|
680
|
|
|
681 /* /\* tree->current = tmp; *\/ */
|
|
|
682
|
|
|
683 /* /\* context->next = DeleteCase6; *\/ */
|
|
|
684 /* /\* stack_push(context->code_stack, &context->next); *\/ */
|
|
|
685 /* /\* goto meta(context, RotateL); *\/ */
|
|
|
686 /* /\* } *\/ */
|
|
|
687
|
|
|
688 /* /\* goto meta(context, DeleteCase6); *\/ */
|
|
|
689 /* /\* } *\/ */
|
|
|
690
|
|
|
691 /* /\* __code deleteCase5_stub(struct Context* context) { *\/ */
|
|
|
692 /* /\* goto deleteCase5(context, &context->data[Tree]->tree, context->data[Tree]->tree.current); *\/ */
|
|
|
693 /* /\* } *\/ */
|
|
|
694
|
|
|
695 /* /\* __code deleteCase6(struct Context* context, struct Tree* tree, struct Node* current) { *\/ */
|
|
|
696 /* /\* struct Node* sibling = current == current->parent->left ? current->parent->right : current->parent->left; *\/ */
|
|
|
697
|
|
|
698 /* /\* sibling == sibling->parent->left ? (sibling->parent->left = context->heap) : (sibling->parent->right = context->heap); *\/ */
|
|
|
699 /* /\* allocator(context); *\/ */
|
|
|
700 /* /\* struct Node* tmp = &context->data[context->dataNum]->node; *\/ */
|
|
|
701 /* /\* *tmp = *sibling; *\/ */
|
|
|
702 /* /\* tmp->parent = current; *\/ */
|
|
|
703
|
|
|
704 /* /\* tmp->color = current->parent->color; *\/ */
|
|
|
705 /* /\* current->parent->color = Black; *\/ */
|
|
|
706
|
|
|
707 /* /\* context->next = Delete3; *\/ */
|
|
|
708 /* /\* stack_push(context->code_stack, &context->next); *\/ */
|
|
|
709
|
|
|
710 /* /\* if (current == current->parent->left) { *\/ */
|
|
|
711 /* /\* tmp->right->color = Black; *\/ */
|
|
|
712 /* /\* tree->current = current->parent; *\/ */
|
|
|
713
|
|
|
714 /* /\* goto meta(context, RotateL); *\/ */
|
|
|
715 /* /\* } else { *\/ */
|
|
|
716 /* /\* tmp->left->color = Black; *\/ */
|
|
|
717 /* /\* tree->current = current->parent; *\/ */
|
|
|
718
|
|
|
719 /* /\* goto meta(context, RotateR); *\/ */
|
|
|
720 /* /\* } *\/ */
|
|
|
721 /* /\* } *\/ */
|
|
|
722
|
|
|
723 /* /\* __code deleteCase6_stub(struct Context* context) { *\/ */
|
|
|
724 /* /\* goto deleteCase6(context, &context->data[Tree]->tree, context->data[Tree]->tree.current); *\/ */
|
|
|
725 /* /\* } *\/ */
|
