1 #target WASI
3 Function noMoreFreeMemory() Which Returns Nothing Is External;
4 Function segmentationFault() Which Returns Nothing Is External;
5 Function printString(PointerToCharacter string) Which Returns Nothing Is External;
6 Function clearScreen() Which Returns Nothing Is External;
7 Function setDiagramWidth(Integer32 width) Which Returns Nothing Is External;
8 Function setDiagramHeight(Integer32 height) Which Returns Nothing Is External;
9 Function drawLine(Integer32 x1, Integer32 y1, Integer32 x2, Integer32 y2)
10 Which Returns Nothing Is External;
11 Function drawRectangle(Integer32 x, Integer32 y,
12 Integer32 width, Integer32 height,
13 PointerToCharacter color)
14 Which Returns Nothing Is External;
15 Function drawText(Integer32 x, Integer32 y, PointerToCharacter text)
16 Which Returns Nothing Is External;
17
18 Function strlen(PointerToCharacter str) Which Returns Integer32 Does
19 If str = 0 Then
20 Return 0;
21 EndIf
22 Integer32 length := 0;
23 While ValueAt(str + length) Loop
24 length += 1;
25 EndWhile
26 Return length;
27 EndFunction
28
29 Function strcpy(PointerToCharacter dest, PointerToCharacter src) Which Returns Nothing Does
30 While ValueAt(src) Loop
31 ValueAt(dest) := ValueAt(src);
32 dest += 1;
33 src += 1;
34 EndWhile
35 ValueAt(dest) := 0;
36 EndFunction
37
38 Function strcat(PointerToCharacter dest, PointerToCharacter src) Which Returns Nothing Does
39 strcpy(dest + strlen(dest), src);
40 EndFunction
41
42 Function reverseString(PointerToCharacter string) Which Returns Nothing Does
43 PointerToCharacter pointerToLastCharacter := string + strlen(string) - 1;
44 While pointerToLastCharacter - string > 0 Loop
45 Character tmp := ValueAt(string);
46 ValueAt(string) := ValueAt(pointerToLastCharacter);
47 ValueAt(pointerToLastCharacter) := tmp;
48 string += 1;
49 pointerToLastCharacter -= 1;
50 EndWhile
51 EndFunction
52
53 Function convertIntegerToString(PointerToCharacter string, Integer32 number)
54 Which Returns Nothing Does
55 Integer32 isNumberNegative := 0;
56 If number < 0 Then
57 number := -number;
58 isNumberNegative := 1;
59 EndIf
60 Integer32 i := 0;
61 While number >= 10 Loop
62 ValueAt(string + i) := '0' + mod(number, 10);
63 number /= 10;
64 i += 1;
65 EndWhile
66 ValueAt(string + i) := '0' + number;
67 i += 1;
68 If isNumberNegative Then
69 ValueAt(string + i) := '-';
70 i += 1;
71 EndIf
72 ValueAt(string + i) := 0;
73 reverseString(string);
74 EndFunction
75
76 Function appendIntegerToString(PointerToCharacter string, Integer32 number)
77 Which Returns Nothing Does
78 convertIntegerToString(string + strlen(string), number);
79 EndFunction
80
81 Structure RedBlackTreeNode Consists Of
82 Integer32 key;
83 PointerToRedBlackTreeNode leftChild, rightChild, parent;
84 Character color;
85 Integer32 x, y;
86 EndStructure
87
88 InstantiateStructure RedBlackTreeNode redBlackTreeNodes[128];
89 Integer16 isRedBlackTreeNodeUsed[128];
90
91 Function isRedBlackTreeNodeWithinBounds(
92 PointerToRedBlackTreeNode node) Which Returns Integer32 Does
93 Return AddressOf(redBlackTreeNodes[0]) <= node <= AddressOf(redBlackTreeNodes[128 - 1]) and
94 mod(node - AddressOf(redBlackTreeNodes[0]), SizeOf(RedBlackTreeNode)) = 0;
95 EndFunction
96
97 Function newRedBlackTreeNode() Which Returns PointerToRedBlackTreeNode Does
98 Integer16 i := 0;
99 While i < 128 Loop
100 If not(isRedBlackTreeNodeUsed[i]) Then
101 redBlackTreeNodes[i].key := 0;
102 redBlackTreeNodes[i].leftChild :=
103 redBlackTreeNodes[i].rightChild :=
104 PointerToRedBlackTreeNode(0);
105 redBlackTreeNodes[i].color := 'R';
106 redBlackTreeNodes[i].x := redBlackTreeNodes[i].y := 0;
107 isRedBlackTreeNodeUsed[i] := 1;
108 Return AddressOf(redBlackTreeNodes[i]);
109 EndIf
110 i += 1;
111 EndWhile
112 noMoreFreeMemory();
113 EndFunction
114
115 Function freeRedBlackTreeNode(
116 PointerToRedBlackTreeNode node) Which Returns Nothing Does
117 If not(isRedBlackTreeNodeWithinBounds(node)) Then
118 segmentationFault();
119 EndIf
120 isRedBlackTreeNodeUsed[
121 (node - AddressOf(redBlackTreeNodes[0])) / SizeOf(RedBlackTreeNode)] := 0;
122 EndFunction
123
124 Function RRotate(PointerToRedBlackTreeNode y)
125 Which Returns PointerToRedBlackTreeNode Does
126 Character stringToBePrinted[32] := {0};
127 strcat(AddressOf(stringToBePrinted[0]), "Right-rotate around ");
128 appendIntegerToString(
129 AddressOf(stringToBePrinted[0]),
130 y->key);
131 strcat(AddressOf(stringToBePrinted[0]), ".\n");
132 printString(AddressOf(stringToBePrinted[0]));
133
134 PointerToRedBlackTreeNode x := y->leftChild;
135 PointerToRedBlackTreeNode T2 := x->rightChild;
136 x->rightChild := y;
137 y->leftChild := T2;
138 y->parent := x;
139 If T2 Then
140 T2->parent := y;
141 EndIf
142 Return x;
143 EndFunction
144
145 Function LRotate(PointerToRedBlackTreeNode x)
146 Which Returns PointerToRedBlackTreeNode Does
147 Character stringToBePrinted[32] := {0};
148 strcat(AddressOf(stringToBePrinted[0]), "Left-rotate around ");
149 appendIntegerToString(
150 AddressOf(stringToBePrinted[0]),
151 x->key);
152 strcat(AddressOf(stringToBePrinted[0]), ".\n");
153 printString(AddressOf(stringToBePrinted[0]));
154
155 PointerToRedBlackTreeNode y := x->rightChild;
156 PointerToRedBlackTreeNode T2 := y->leftChild;
157 y->leftChild := x;
158 x->rightChild := T2;
159 x->parent := y;
160 If T2 Then
161 T2->parent := x;
162 EndIf
163 Return y;
164 EndFunction
165
166 PointerToRedBlackTreeNode root;
167 Integer32 ll := 0, rr := 0, lr := 0, rl := 0;
168
169 Function Insert(PointerToRedBlackTreeNode node, Integer32 X)
170 Which Returns PointerToRedBlackTreeNode Is Declared;
171
172 Function InsertRBT(PointerToRedBlackTreeNode node, Integer32 X)
173 Which Returns PointerToRedBlackTreeNode Does
174 PointerToRedBlackTreeNode newnode;
175 If not(node) Then
176 newnode := newRedBlackTreeNode();
177 newnode->key := X;
178 newnode->color := 'B';
179 Return newnode;
180 EndIf
181 newnode := Insert(node, X);
182 newnode->parent := PointerToRedBlackTreeNode(0);
183 Return newnode;
184 EndFunction
185
186 Function Insert(PointerToRedBlackTreeNode node, Integer32 X)
187 Which Returns PointerToRedBlackTreeNode Does
188 Integer32 flag := 0;
189 If node = 0 Then
190 PointerToRedBlackTreeNode ret := newRedBlackTreeNode();
191 ret->key := X;
192 Return ret;
193 EndIf
194 If X < node->key Then
195 node->leftChild := Insert(node->leftChild, X);
196 node->leftChild->parent := node;
197 If not(node=root) Then
198 If node->color = 'R' and node->leftChild->color = 'R' Then
199 flag := 1;
200 EndIf
201 EndIf
202 ElseIf X > node->key Then
203 node->rightChild := Insert(node->rightChild, X);
204 node->rightChild->parent := node;
205 If not(node=root) Then
206 If node->color = 'R' and node->rightChild->color = 'R' Then
207 flag := 1;
208 EndIf
209 EndIf
210 Else
211 Return node;
212 EndIf
213
214 If ll Then
215 node := LRotate( node );
216 node->color := 'B';
217 node->leftChild->color := 'R';
218 ll := 0;
219 ElseIf rr Then
220 node := RRotate( node );
221 node->color := 'B';
222 node->rightChild->color := 'R';
223 rr := 0;
224 ElseIf rl Then
225 node->rightChild := RRotate( node->rightChild );
226 node->rightChild->parent := node;
227 node := LRotate( node );
228 node->color := 'B';
229 node->leftChild->color := 'R';
230 rl := 0;
231 ElseIf lr Then
232 node->leftChild := LRotate( node->leftChild );
233 node->leftChild->parent := node;
234 node := RRotate( node );
235 node->color := 'B';
236 node->rightChild->color := 'R';
237 lr := 0;
238 EndIf
239
240 If flag Then If node->parent->rightChild = node Then
242 If node->parent->leftChild = 0 or node->parent->leftChild->color = 'B' Then
243 If not(node->leftChild = 0) and node->leftChild->color = 'R' Then
244 rl := 1;
245 ElseIf not(node->rightChild = 0) and node->rightChild->color = 'R' Then
246 ll := 1;
247 EndIf
248 Else
249 node->parent->leftChild->color := 'B';
250 node->color := 'B';
251 If not(node->parent = root) Then
252 node->parent->color := 'R';
253 EndIf
254 EndIf
255 Else
256 If node->parent->rightChild = 0 or node->parent->rightChild->color = 'B' Then
257 If not(node->leftChild = 0) and node->leftChild->color = 'R' Then
258 rr := 1;
259 ElseIf not(node->rightChild = 0) and node->rightChild->color = 'R' Then
260 lr := 1;
261 EndIf
262 Else
263 node->parent->rightChild->color := 'B';
264 node->color := 'B';
265 If not(node->parent = root) Then
266 node->parent->color := 'R';
267 EndIf
268 EndIf
269 EndIf
270 flag := 0;
271 EndIf
272 Return node;
273 EndFunction
274
275 Function leftRotate(PointerToRedBlackTreeNode t) Which Returns Nothing Does
276 Character stringToBePrinted[32] := {0};
277 strcat(AddressOf(stringToBePrinted[0]), "Left-rotate around ");
278 appendIntegerToString(
279 AddressOf(stringToBePrinted[0]),
280 t->key);
281 strcat(AddressOf(stringToBePrinted[0]), ".\n");
282 printString(AddressOf(stringToBePrinted[0]));
283
284 PointerToRedBlackTreeNode tParent := t->rightChild;
285 If t = root Then
286 root := tParent;
287 EndIf
288 If t->parent Then
289 If t = t->parent->leftChild Then
290 t->parent->leftChild := tParent;
291 Else
292 t->parent->rightChild := tParent;
293 EndIf
294 EndIf
295 tParent->parent := t->parent;
296 t->parent := tParent;
297 t->rightChild := tParent->leftChild;
298 If tParent->leftChild Then
299 tParent->leftChild->parent := t;
300 EndIf
301 tParent->leftChild := t;
302 EndFunction
303
304 Function rightRotate(PointerToRedBlackTreeNode t) Which Returns Nothing Does
305 Character stringToBePrinted[32] := {0};
306 strcat(AddressOf(stringToBePrinted[0]), "Right-rotate around ");
307 appendIntegerToString(
308 AddressOf(stringToBePrinted[0]),
309 t->key);
310 strcat(AddressOf(stringToBePrinted[0]), ".\n");
311 printString(AddressOf(stringToBePrinted[0]));
312
313 PointerToRedBlackTreeNode tParent := t->leftChild;
314 If t = root Then
315 root := tParent;
316 EndIf
317 If t->parent Then
318 If t = t->parent->leftChild Then
319 t->parent->leftChild := tParent;
320 Else
321 t->parent->rightChild := tParent;
322 EndIf
323 EndIf
324 tParent->parent := t->parent;
325 t->parent := tParent;
326 t->leftChild := tParent->rightChild;
327 If tParent->rightChild Then
328 tParent->rightChild->parent := t;
329 EndIf
330 tParent->rightChild := t;
331 EndFunction
332
333 Function Sibling(PointerToRedBlackTreeNode v)
334 Which Returns PointerToRedBlackTreeNode Does
335 If not(v->parent) Then
336 Return 0;
337 EndIf
338 If v = v->parent->leftChild Then
339 Return v->parent->rightChild;
340 EndIf
341 Return v->parent->leftChild;
342 EndFunction
343
344 Function FixDoubleBlack(PointerToRedBlackTreeNode x) Which Returns Nothing Does
345 If x = root Then
346 Return;
347 EndIf
348 PointerToRedBlackTreeNode sibling := Sibling( x ), parent := x->parent;
349 If not(sibling) Then
350 FixDoubleBlack(parent);
351 Else
352 If sibling->color = 'R' Then
353 parent->color := 'R';
354 sibling->color := 'B';
355 If sibling = sibling->parent->leftChild Then
356 rightRotate(parent);
357 Else
358 leftRotate(parent);
359 EndIf
360 FixDoubleBlack(x);
361 Else
362 If not(sibling->leftChild = 0) and sibling->leftChild->color = 'R' Then
363 If sibling = sibling->parent->leftChild Then
364 sibling->leftChild->color := sibling->color;
365 sibling->color := parent->color;
366 rightRotate(parent);
367 Else
368 sibling->leftChild->color := parent->color;
369 rightRotate(sibling);
370 leftRotate(parent);
371 EndIf
372 parent->color := 'B';
373 ElseIf not(sibling->rightChild = 0) and sibling->rightChild->color='R' Then
374 If sibling = sibling->parent->leftChild Then
375 sibling->rightChild->color := parent->color;
376 leftRotate(sibling);
377 rightRotate(parent);
378 Else
379 sibling->rightChild->color := sibling->color;
380 sibling->color := parent->color;
381 leftRotate(parent);
382 EndIf
383 parent->color := 'B';
384 Else
385 sibling->color := 'R';
386 If parent->color = 'B' Then
387 FixDoubleBlack(parent);
388 Else
389 parent->color := 'B';
390 EndIf
391 EndIf
392 EndIf
393 EndIf
394 EndFunction
395
396 Function SmallestNode(PointerToRedBlackTreeNode node) Which Returns
397 PointerToRedBlackTreeNode Does
398 PointerToRedBlackTreeNode t := node;
399 While t -> leftChild Loop
400 t := t->leftChild;
401 EndWhile
402 Return t;
403 EndFunction
404
405 Function ReplaceRBT(PointerToRedBlackTreeNode t)
406 Which Returns PointerToRedBlackTreeNode Does
407 If not(t->leftChild = 0) and not(t->rightChild = 0) Then
408 Return SmallestNode(t->rightChild);
409 ElseIf not(t->leftChild) and not(t->rightChild) Then
410 Return 0;
411 ElseIf t->leftChild Then
412 Return t->leftChild;
413 Else
414 Return t->rightChild;
415 EndIf
416 asm("unreachable");
417 EndFunction
418
419 Function DeleteNode(PointerToRedBlackTreeNode v)
420 Which Returns Nothing Does
421 PointerToRedBlackTreeNode u := ReplaceRBT(v);
422 Integer32 uvBothBlack := (not(u) or u->color = 'B') and v->color = 'B';
423 PointerToRedBlackTreeNode parent := v->parent;
424 If not(u) Then
425 If v = root Then
426 root := PointerToRedBlackTreeNode(0);
427 Else
428 If uvBothBlack Then
429 FixDoubleBlack(v);
430 Else
431 PointerToRedBlackTreeNode vsib := Sibling(v);
432 If vsib Then
433 vsib->color := 'R';
434 EndIf
435 EndIf
436 If v = v->parent->leftChild Then
437 parent->leftChild := PointerToRedBlackTreeNode(0);
438 Else
439 parent->rightChild := PointerToRedBlackTreeNode(0);
440 EndIf
441 EndIf
442 freeRedBlackTreeNode(v);
443 Return;
444 EndIf
445 If v->leftChild = 0 or v->rightChild = 0 Then
446 If v = root Then
447 v->key := u->key;
448 v->leftChild := v->rightChild := PointerToRedBlackTreeNode(0);
449 freeRedBlackTreeNode(u);
450 Else
451 If v = v->parent->leftChild Then
452 parent->leftChild := u;
453 Else
454 parent->rightChild := u;
455 EndIf
456 freeRedBlackTreeNode(v);
457 u->parent := parent;
458 If uvBothBlack Then
459 FixDoubleBlack(u);
460 Else
461 u->color := 'B';
462 EndIf
463 EndIf
464 Return;
465 EndIf
466 Integer32 tmp := u->key;
467 u->key := v->key;
468 v->key := tmp;
469 DeleteNode(u);
470 EndFunction
471
472 Function SearchRBT(
473 PointerToRedBlackTreeNode node,
474 Integer32 X,
475 PointerToPointerToRedBlackTreeNode parent)
476 Which Returns Integer32 Does
477 If not(node) Then
478 Return 0;
479 ElseIf node->key = X Then
480 Return 1;
481 EndIf
482 ValueAt(parent) := node;
483 If node->key > X Then
484 Return SearchRBT(node->leftChild, X, parent);
485 Else
486 Return SearchRBT(node->rightChild, X, parent);
487 EndIf
488 asm("unreachable");
489 EndFunction
490
491 Function DeleteRBT(PointerToRedBlackTreeNode node, Integer32 X) Which Returns Nothing Does
492 If not(node) Then
493 Return;
494 EndIf
495 PointerToRedBlackTreeNode parent := PointerToRedBlackTreeNode(0);
496 If SearchRBT(node,X,AddressOf(parent)) Then
497 If not(parent) Then
498 DeleteNode(node);
499 ElseIf not(parent->leftChild = 0) and parent->leftChild->key = X) Then
500 DeleteNode(parent->leftChild);
501 Else
502 DeleteNode(parent->rightChild);
503 EndIf
504 Else
505 printString("Node to be deleted has not been found.\n");
506 EndIf
507 EndFunction
508
509
510 Integer32 keys[128];
511 Integer32 numberOfKeys := 0;
512 Character insert_or_delete[128];
513
514 Function getAddressOfKeys() Which Returns PointerToInteger32 Does
515 Return AddressOf(keys[0]);
516 EndFunction
517
518 Function getAddressOfInsertOrDelete() Which Returns PointerToCharacter Does
519 Return AddressOf(insert_or_delete[0]);
520 EndFunction
521
522 Function setNumberOfKeys(Integer32 n) Which Returns Nothing Does
523 numberOfKeys := (n < 0) ? 0 :
524 (n > 128) ? 128 : n;
525 EndFunction
526
527 Function getNumberOfKeys() Which Returns Integer32 Does
528 Return numberOfKeys;
529 EndFunction
530
531 Function clearKeys() Which Returns Nothing Does
532 numberOfKeys := 0;
533 EndFunction
534
535 Integer32 inorderCounter := 0;
536
537 Function assignCoordinatesInorder(PointerToRedBlackTreeNode node,
538 Integer32 depth,
539 Integer32 horizontalSpacing,
540 Integer32 verticalSpacing)
541 Which Returns Nothing Does
542 If not(node) Then
543 Return;
544 EndIf
545 assignCoordinatesInorder(node->leftChild,
546 depth + 1,
547 horizontalSpacing,
548 verticalSpacing);
549 node->x := inorderCounter * horizontalSpacing;
550 node->y := depth * verticalSpacing;
551 inorderCounter += 1;
552 assignCoordinatesInorder(node->rightChild,
553 depth + 1,
554 horizontalSpacing,
555 verticalSpacing);
556 EndFunction
557
558 Structure Maxima Consists Of
559 Integer32 minimumX, maximumX;
560 EndStructure
561
562 Function findMinMaxX(PointerToRedBlackTreeNode node,
563 PointerToMaxima m)
564 Which Returns Nothing Does
565 If not(node) Then
566 Return;
567 EndIf
568 If node->x < m->minimumX Then
569 m->minimumX := node->x;
570 EndIf
571 If node->x > m->maximumX Then
572 m->maximumX := node->x;
573 EndIf
574 findMinMaxX(node->leftChild, m);
575 findMinMaxX(node->rightChild, m);
576 EndFunction
577
578 Function drawRedBlackTree(PointerToRedBlackTreeNode node, Integer32 offsetX)
579 Which Returns Nothing Does
580 If not(node) Then
581 Return;
582 EndIf
583 Integer32 drawX := node->x - offsetX;
584 Integer32 drawY := node->y;
585 drawRectangle(drawX, drawY, 120, 60, node->color = 'R' ? "Red" : "Black");
586
587 Character keyStr[8] := {0};
588 convertIntegerToString(AddressOf(keyStr[0]), node->key);
589 drawText(drawX + 6, drawY + 30, AddressOf(keyStr[0]));
590
591 If node->leftChild Then
592 drawLine(drawX + 60, drawY + 60, node->leftChild->x - offsetX + 60, node->leftChild->y);
593 drawRedBlackTree(node->leftChild, offsetX);
594 EndIf
595 If node->rightChild Then
596 drawLine(drawX + 60, drawY + 60, node->rightChild->x - offsetX + 60, node->rightChild->y);
597 drawRedBlackTree(node->rightChild, offsetX);
598 EndIf
599 EndFunction
600
601 Function freeRedBlackTree(PointerToRedBlackTreeNode node) Which Returns Nothing Does
602 If not(node) Then
603 Return;
604 EndIf
605 If node->leftChild Then
606 freeRedBlackTree(node->leftChild);
607 EndIf
608 If node->rightChild Then
609 freeRedBlackTree(node->rightChild);
610 EndIf
611 freeRedBlackTreeNode(node);
612 EndFunction
613
614 Function max(Integer32 x, Integer32 y) Which Returns Integer32 Does
615 Return x > y ? x : y;
616 EndFunction
617
618 Function nodeHeight(PointerToRedBlackTreeNode node)
619 Which Returns Integer32 Does
620 Return not(node) ? 0 :
621 max(nodeHeight(node->leftChild), nodeHeight(node->rightChild)) + 1;
622 EndFunction
623
624 Function render() Which Returns Nothing Does
625 clearScreen();
626 root := PointerToRedBlackTreeNode(0);
627 Integer32 i := 0;
628 While i < numberOfKeys Loop
629 If insert_or_delete[i] = 'I' Then
630 Character stringToBePrinted[32] := {0};
631 strcat(AddressOf(stringToBePrinted[0]), "Inserting ");
632 appendIntegerToString(
633 AddressOf(stringToBePrinted[0]),
634 keys[i]);
635 strcat(AddressOf(stringToBePrinted[0]), "...\n");
636 printString(AddressOf(stringToBePrinted[0]));
637
638 root := InsertRBT(root, keys[i]);
639 ElseIf insert_or_delete[i] = 'D' Then
640 Character stringToBePrinted[32] := {0};
641 strcat(AddressOf(stringToBePrinted[0]), "Deleting ");
642 appendIntegerToString(
643 AddressOf(stringToBePrinted[0]),
644 keys[i]);
645 strcat(AddressOf(stringToBePrinted[0]), "...\n");
646 printString(AddressOf(stringToBePrinted[0]));
647
648 DeleteRBT(root, keys[i]);
649 Else
650 printString(R"RawString(The character array "insert_or_delete" can only contain characters 'I' and 'D'!
651 )RawString");
652 asm("unreachable");
653 EndIf
654 i += 1;
655 EndWhile
656
657 inorderCounter := 1;
658 assignCoordinatesInorder(root, 0, 110, 90);
659
660 InstantiateStructure Maxima globalMax;
661 globalMax.minimumX := globalMax.maximumX := 0;
662 If root Then
663 globalMax.minimumX := root->x;
664 globalMax.maximumX := root->x;
665 findMinMaxX(root, AddressOf(globalMax));
666 EndIf
667
668 Integer32 margin := 20;
669 Integer32 diagramWidth := (globalMax.maximumX - globalMax.minimumX) + 120 + margin * 2;
670 Integer32 diagramHeight := (nodeHeight(root) + 1) * 90 + margin;
671
672 setDiagramWidth(diagramWidth);
673 setDiagramHeight(diagramHeight);
674
675 drawRedBlackTree(root, globalMax.minimumX - margin);
676
677 freeRedBlackTree(root);
678 printString("Red Black Tree rendered.\n");
679 EndFunction
680