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 Which Returns Nothing Is External;
14 Function drawText(Integer32 x, Integer32 y, PointerToCharacter text)
15 Which Returns Nothing Is External;
16
17 Function strlen(PointerToCharacter str) Which Returns Integer32 Does
18 If str = 0 Then
19 Return 0;
20 EndIf
21 Integer32 length := 0;
22 While ValueAt(str + length) Loop
23 length += 1;
24 EndWhile
25 Return length;
26 EndFunction
27
28 Function strcpy(PointerToCharacter dest, PointerToCharacter src) Which Returns Nothing Does
29 While ValueAt(src) Loop
30 ValueAt(dest) := ValueAt(src);
31 dest += 1;
32 src += 1;
33 EndWhile
34 ValueAt(dest) := 0;
35 EndFunction
36
37 Function strcat(PointerToCharacter dest, PointerToCharacter src) Which Returns Nothing Does
38 strcpy(dest + strlen(dest), src);
39 EndFunction
40
41 Function reverseString(PointerToCharacter string) Which Returns Nothing Does
42 PointerToCharacter pointerToLastCharacter := string + strlen(string) - 1;
43 While pointerToLastCharacter - string > 0 Loop
44 Character tmp := ValueAt(string);
45 ValueAt(string) := ValueAt(pointerToLastCharacter);
46 ValueAt(pointerToLastCharacter) := tmp;
47 string += 1;
48 pointerToLastCharacter -= 1;
49 EndWhile
50 EndFunction
51
52 Function convertIntegerToString(PointerToCharacter string, Integer32 number)
53 Which Returns Nothing Does
54 Integer32 isNumberNegative := 0;
55 If number < 0 Then
56 number *= -1;
57 isNumberNegative := 1;
58 EndIf
59 Integer32 i := 0;
60 While number >= 10 Loop
61 ValueAt(string + i) := '0' + mod(number, 10);
62 number /= 10;
63 i += 1;
64 EndWhile
65 ValueAt(string + i) := '0' + number;
66 i += 1;
67 If isNumberNegative Then
68 ValueAt(string + i) := '-';
69 i += 1;
70 EndIf
71 ValueAt(string + i) := 0;
72 reverseString(string);
73 EndFunction
74
75 Function appendIntegerToString(PointerToCharacter string, Integer32 number)
76 Which Returns Nothing Does
77 convertIntegerToString(string + strlen(string), number);
78 EndFunction
79
80 Structure Node Consists Of
81 Integer32 key;
82 PointerToNode left, right;
83 Integer32 x, y;
84 EndStructure
85
86 InstantiateStructure Node nodes[128];
87 Integer16 isNodeUsed[128];
88
89 Function isNodeWithinBounds(
90 PointerToNode node) Which Returns Integer32 Does
91 Return AddressOf(nodes[0]) <= node <= AddressOf(nodes[128 - 1]) and
92 mod(node - AddressOf(nodes[0]), SizeOf(Node)) = 0;
93 EndFunction
94
95 Function newNode() Which Returns PointerToNode Does
96 Integer16 i := 0;
97 While i < 128 Loop
98 If not(isNodeUsed[i]) Then
99 nodes[i].key := 0;
100 nodes[i].left :=
101 nodes[i].right :=
102 PointerToNode(0);
103 nodes[i].x := nodes[i].y := 0;
104 isNodeUsed[i] := 1;
105 Return AddressOf(nodes[i]);
106 EndIf
107 i += 1;
108 EndWhile
109 noMoreFreeMemory();
110 asm("unreachable");
111 EndFunction
112
113 Function freeNode(
114 PointerToNode node) Which Returns Nothing Does
115 If not(isNodeWithinBounds(node)) Then
116 segmentationFault();
117 EndIf
118 isNodeUsed[
119 (node - AddressOf(nodes[0])) / SizeOf(Node)] := 0;
120 EndFunction
121
122 PointerToNode root;
123
124 Function InsertBST(PointerToNode node, Integer32 key)
125 Which Returns PointerToNode Does
126 If not(node) Then
127 PointerToNode newNode := newNode();
128 newNode->key := key;
129 Return newNode;
130 EndIf
131 If node->key > key Then
132 node->left := InsertBST(node->left, key);
133 ElseIf node->key < key Then
134 node->right := InsertBST(node->right, key);
135 EndIf
136 Return node;
137 EndFunction
138
139
140 Function RRotate(PointerToNode y)
141 Which Returns PointerToNode Does
142 Character stringToBePrinted[32] := {0};
143 strcat(AddressOf(stringToBePrinted[0]), "Right-rotate around ");
144 appendIntegerToString(
145 AddressOf(stringToBePrinted[0]),
146 y->key);
147 strcat(AddressOf(stringToBePrinted[0]), ".\n");
148 printString(AddressOf(stringToBePrinted[0]));
149
150 PointerToNode x := y->left;
151 PointerToNode T2 := x->right;
152 x->right := y;
153 y->left := T2;
154 Return x;
155 EndFunction
156
157 Function LRotate(PointerToNode x)
158 Which Returns PointerToNode Does
159 Character stringToBePrinted[32] := {0};
160 strcat(AddressOf(stringToBePrinted[0]), "Left-rotate around ");
161 appendIntegerToString(
162 AddressOf(stringToBePrinted[0]),
163 x->key);
164 strcat(AddressOf(stringToBePrinted[0]), ".\n");
165 printString(AddressOf(stringToBePrinted[0]));
166
167 PointerToNode y := x->right;
168 PointerToNode T2 := y->left;
169 y->left := x;
170 x->right := T2;
171 Return y;
172 EndFunction
173
174 Function Splay(PointerToNode node, Integer32 X)
175 Which Returns PointerToNode Does
176 If not(node) or node->key = X Then
177 Return node;
178 ElseIf node->key > X Then
179 If not(node->left) Then
180 Return node;
181 ElseIf node->left->key > X Then
182 printString("ZIG-ZIG case\n");
183 node->left->left := Splay(node->left->left, X);
184 node := RRotate(node);
185 ElseIf node->left->key < X Then
186 printString("ZIG-ZAG case\n");
187 node->left->right := Splay(node->left->right, X);
188 If node->left->right Then
189 node->left := LRotate(node->left);
190 EndIf
191 EndIf
192 If not(node->left) Then
193 Return node;
194 Else
195 Return RRotate(node);
196 EndIf
197 Else
198 If not(node->right) Then
199 Return node;
200 ElseIf node->right->key > X Then
201 printString("ZAG-ZIG case\n");
202 node->right->left := Splay(node->right->left, X);
203 If node->right->left Then
204 node->right := RRotate(node->right);
205 EndIf
206 ElseIf node->right->key < X Then
207 printString("ZAG-ZAG case\n");
208 node->right->right := Splay(node->right->right, X);
209 node := LRotate(node);
210 EndIf
211 If not(node->right) Then
212 Return node;
213 Else
214 Return LRotate(node);
215 EndIf
216 EndIf
217 asm("unreachable");
218 EndFunction
219
220 Function Insert(PointerToNode node, Integer32 X)
221 Which Returns PointerToNode Does
222 If not(node) Then
223 PointerToNode newnode := newNode();
224 newnode->key := X;
225 Return newnode;
226 EndIf
227 node := Splay(node, X);
228 If node->key = X Then
229 Return node;
230 EndIf
231 PointerToNode newnode := newNode();
232 newnode->key := X;
233
234 If node->key > X Then
235 newnode->right := node;
236 newnode->left := node->left;
237 node->left := PointerToNode(0);
238 Else
239 newnode->left := node;
240 newnode->right := node->right;
241 node->right := PointerToNode(0);
242 EndIf
243 Return newnode;
244 EndFunction
245
246 Function Delete(PointerToNode node, Integer32 X)
247 Which Returns PointerToNode Does
248 PointerToNode temp;
249 If not(node) Then
250 Return node;
251 EndIf
252 node := Splay(node, X);
253 If X != node->key Then
254 Return node;
255 EndIf
256 If not(node->left) Then
257 temp := node;
258 node := node->right;
259 Else
260 temp := node;
261 node := Splay(node->left, X);
262 node->right := temp->right;
263 EndIf
264 freeNode(temp);
265 Return node;
266 EndFunction
267
268 Function Search(PointerToNode node, Integer32 X)
269 Which Returns PointerToNode Does
270 Return Splay(node, X);
271 EndFunction
272
273 Integer32 keys[128];
274 Integer32 numberOfKeys := 0;
275 Character insert_or_delete[128];
276
277 Function getAddressOfKeys() Which Returns PointerToInteger32 Does
278 Return AddressOf(keys[0]);
279 EndFunction
280
281 Function getAddressOfInsertOrDelete() Which Returns PointerToCharacter Does
282 Return AddressOf(insert_or_delete[0]);
283 EndFunction
284
285 Function setNumberOfKeys(Integer32 n) Which Returns Nothing Does
286 numberOfKeys := (n < 0) ? 0 :
287 (n > 128) ? 128 : n;
288 EndFunction
289
290 Function getNumberOfKeys() Which Returns Integer32 Does
291 Return numberOfKeys;
292 EndFunction
293
294 Function clearKeys() Which Returns Nothing Does
295 numberOfKeys := 0;
296 EndFunction
297
298 Integer32 inorderCounter := 0;
299
300 Function assignCoordinatesInorder(PointerToNode node,
301 Integer32 depth,
302 Integer32 horizontalSpacing,
303 Integer32 verticalSpacing)
304 Which Returns Nothing Does
305 If not(node) Then
306 Return;
307 EndIf
308 assignCoordinatesInorder(node->left,
309 depth + 1,
310 horizontalSpacing,
311 verticalSpacing);
312 node->x := inorderCounter * horizontalSpacing;
313 node->y := depth * verticalSpacing;
314 inorderCounter += 1;
315 assignCoordinatesInorder(node->right,
316 depth + 1,
317 horizontalSpacing,
318 verticalSpacing);
319 EndFunction
320
321 Structure Maxima Consists Of
322 Integer32 minimumX, maximumX;
323 EndStructure
324
325 Function findMinMaxX(PointerToNode node,
326 PointerToMaxima m)
327 Which Returns Nothing Does
328 If not(node) Then
329 Return;
330 EndIf
331 If node->x < m->minimumX Then
332 m->minimumX := node->x;
333 EndIf
334 If node->x > m->maximumX Then
335 m->maximumX := node->x;
336 EndIf
337 findMinMaxX(node->left, m);
338 findMinMaxX(node->right, m);
339 EndFunction
340
341 Function drawTree(PointerToNode node, Integer32 offsetX)
342 Which Returns Nothing Does
343 If not(node) Then
344 Return;
345 EndIf
346 Integer32 drawX := node->x - offsetX;
347 Integer32 drawY := node->y;
348 drawRectangle(drawX, drawY, 120, 60);
349
350 Character keyStr[8] := {0};
351 convertIntegerToString(AddressOf(keyStr[0]), node->key);
352 drawText(drawX + 6, drawY + 30, AddressOf(keyStr[0]));
353
354 If node->left Then
355 drawLine(drawX + 60, drawY + 60, node->left->x - offsetX + 60, node->left->y);
356 drawTree(node->left, offsetX);
357 EndIf
358 If node->right Then
359 drawLine(drawX + 60, drawY + 60, node->right->x - offsetX + 60, node->right->y);
360 drawTree(node->right, offsetX);
361 EndIf
362 EndFunction
363
364 Function freeTree(PointerToNode node) Which Returns Nothing Does
365 If not(node) Then
366 Return;
367 EndIf
368 If node->left Then
369 freeTree(node->left);
370 EndIf
371 If node->right Then
372 freeTree(node->right);
373 EndIf
374 freeNode(node);
375 EndFunction
376
377 Function max(Integer32 x, Integer32 y) Which Returns Integer32 Does
378 Return x > y ? x : y;
379 EndFunction
380
381 Function nodeHeight(PointerToNode node)
382 Which Returns Integer32 Does
383 Return not(node) ? 0 :
384 max(nodeHeight(node->left), nodeHeight(node->right)) + 1;
385 EndFunction
386
387 Character preorderTraversal[256] := {0};
389 Character inorderTraversal[256] := {0};
390 Integer32 preorderIndex := 0;
391 Integer32 inorderIndex := 0;
392
393 Function getAddressOfPreorderTraversal() Which Returns PointerToCharacter Does
394 Return AddressOf(preorderTraversal[0]);
395 EndFunction
396
397 Function getAddressOfInorderTraversal() Which Returns PointerToCharacter Does
398 Return AddressOf(inorderTraversal[0]);
399 EndFunction
400
401 Function clearTraversalBuffers() Which Returns Nothing Does
402 preorderIndex := 0;
403 inorderIndex := 0;
404 preorderTraversal[0] := 0;
405 inorderTraversal[0] := 0;
406 EndFunction
407
408 Function appendToPreorder(Integer32 number) Which Returns Nothing Does
410 Character tmp[16] := {0};
411 convertIntegerToString(AddressOf(tmp[0]), number);
412
413 Integer32 i := 0;
414 While ValueAt(AddressOf(tmp[0]) + i) Loop
415 preorderTraversal[preorderIndex] := ValueAt(AddressOf(tmp[0]) + i);
416 preorderIndex += 1;
417 i += 1;
418 EndWhile
419 preorderTraversal[preorderIndex] := ' ';
420 preorderIndex += 1;
421 preorderTraversal[preorderIndex] := 0;
422 EndFunction
423
424 Function appendToInorder(Integer32 number) Which Returns Nothing Does
426 Character tmp[16] := {0};
427 convertIntegerToString(AddressOf(tmp[0]), number);
428
429 Integer32 i := 0;
430 While ValueAt(AddressOf(tmp[0]) + i) Loop
431 inorderTraversal[inorderIndex] := ValueAt(AddressOf(tmp[0]) + i);
432 inorderIndex += 1;
433 i += 1;
434 EndWhile
435 inorderTraversal[inorderIndex] := ' ';
436 inorderIndex += 1;
437 inorderTraversal[inorderIndex] := 0;
438 EndFunction
439
440 Function buildPreorderTraversal(PointerToNode node) Which Returns Nothing Does
441 If not(node) Then
442 Return;
443 EndIf
444 appendToPreorder(node->key);
445 buildPreorderTraversal(node->left);
446 buildPreorderTraversal(node->right);
447 EndFunction
448
449 Function buildInorderTraversal(PointerToNode node) Which Returns Nothing Does
450 If not(node) Then
451 Return;
452 EndIf
453 buildInorderTraversal(node->left);
454 appendToInorder(node->key);
455 buildInorderTraversal(node->right);
456 EndFunction
457
458 Function computeTraversals() Which Returns Nothing Does
459 clearTraversalBuffers();
460 buildPreorderTraversal(root);
461 buildInorderTraversal(root);
462 preorderTraversal[preorderIndex] := 0;
464 inorderTraversal[inorderIndex] := 0;
465 EndFunction
466
467 Function render() Which Returns Nothing Does
468 clearScreen();
469 root := PointerToNode(0);
470 Integer32 i := 0;
471 While i < numberOfKeys Loop
472 If insert_or_delete[i] = 'I' Then
473 Character stringToBePrinted[32] := {0};
474 strcat(AddressOf(stringToBePrinted[0]), "Inserting ");
475 appendIntegerToString(
476 AddressOf(stringToBePrinted[0]),
477 keys[i]);
478 strcat(AddressOf(stringToBePrinted[0]), "...\n");
479 printString(AddressOf(stringToBePrinted[0]));
480
481 root := Insert(root, keys[i]);
482 ElseIf insert_or_delete[i] = 'D' Then
483 Character stringToBePrinted[32] := {0};
484 strcat(AddressOf(stringToBePrinted[0]), "Deleting ");
485 appendIntegerToString(
486 AddressOf(stringToBePrinted[0]),
487 keys[i]);
488 strcat(AddressOf(stringToBePrinted[0]), "...\n");
489 printString(AddressOf(stringToBePrinted[0]));
490
491 root := Delete(root, keys[i]);
492 ElseIf insert_or_delete[i] = 'S' Then
493 Character stringToBePrinted[32] := {0};
494 strcat(AddressOf(stringToBePrinted[0]), "Searching for ");
495 appendIntegerToString(
496 AddressOf(stringToBePrinted[0]),
497 keys[i]);
498 strcat(AddressOf(stringToBePrinted[0]), "...\n");
499 printString(AddressOf(stringToBePrinted[0]));
500
501 root := Search(root, keys[i]);
502 ElseIf insert_or_delete[i] = 'B' Then
503 Character stringToBePrinted[64] := {0};
504 strcat(AddressOf(stringToBePrinted[0]), "Inserting ");
505 appendIntegerToString(
506 AddressOf(stringToBePrinted[0]),
507 keys[i]);
508 strcat(AddressOf(stringToBePrinted[0]), " as if we were doing a Binary Search Tree...\n");
509 printString(AddressOf(stringToBePrinted[0]));
510
511 root := InsertBST(root, keys[i]);
512 Else
513 printString(R"RawString(The character array "insert_or_delete" can only contain characters 'I', 'B', 'S', and 'D'!
514 )RawString");
515 asm("unreachable");
516 EndIf
517 i += 1;
518 EndWhile
519
520 inorderCounter := 1;
521 assignCoordinatesInorder(root, 0, 110, 90);
522
523 InstantiateStructure Maxima globalMax;
524 globalMax.minimumX := globalMax.maximumX := 0;
525 If root Then
526 globalMax.minimumX := root->x;
527 globalMax.maximumX := root->x;
528 findMinMaxX(root, AddressOf(globalMax));
529 EndIf
530
531 Integer32 margin := 20;
532 Integer32 diagramWidth := (globalMax.maximumX - globalMax.minimumX) + 120 + margin * 2;
533 Integer32 diagramHeight := (nodeHeight(root) + 1) * 90 + margin;
534
535 setDiagramWidth(diagramWidth);
536 setDiagramHeight(diagramHeight);
537
538 drawTree(root, globalMax.minimumX - margin);
539
540 computeTraversals();
541
542 freeTree(root);
543 printString("Splay Tree rendered.\n");
544 EndFunction
545