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 not(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 Function render() Which Returns Nothing Does
388 clearScreen();
389 root := PointerToNode(0);
390 Integer32 i := 0;
391 While i < numberOfKeys Loop
392 If insert_or_delete[i] = 'I' Then
393 Character stringToBePrinted[32] := {0};
394 strcat(AddressOf(stringToBePrinted[0]), "Inserting ");
395 appendIntegerToString(
396 AddressOf(stringToBePrinted[0]),
397 keys[i]);
398 strcat(AddressOf(stringToBePrinted[0]), "...\n");
399 printString(AddressOf(stringToBePrinted[0]));
400
401 root := Insert(root, keys[i]);
402 ElseIf insert_or_delete[i] = 'D' Then
403 Character stringToBePrinted[32] := {0};
404 strcat(AddressOf(stringToBePrinted[0]), "Deleting ");
405 appendIntegerToString(
406 AddressOf(stringToBePrinted[0]),
407 keys[i]);
408 strcat(AddressOf(stringToBePrinted[0]), "...\n");
409 printString(AddressOf(stringToBePrinted[0]));
410
411 root := Delete(root, keys[i]);
412 ElseIf insert_or_delete[i] = 'S' Then
413 Character stringToBePrinted[32] := {0};
414 strcat(AddressOf(stringToBePrinted[0]), "Searching for ");
415 appendIntegerToString(
416 AddressOf(stringToBePrinted[0]),
417 keys[i]);
418 strcat(AddressOf(stringToBePrinted[0]), "...\n");
419 printString(AddressOf(stringToBePrinted[0]));
420
421 root := Search(root, keys[i]);
422 ElseIf insert_or_delete[i] = 'B' Then
423 Character stringToBePrinted[64] := {0};
424 strcat(AddressOf(stringToBePrinted[0]), "Inserting ");
425 appendIntegerToString(
426 AddressOf(stringToBePrinted[0]),
427 keys[i]);
428 strcat(AddressOf(stringToBePrinted[0]), " as if we were doing a Binary Search Tree...\n");
429 printString(AddressOf(stringToBePrinted[0]));
430
431 root := InsertBST(root, keys[i]);
432 Else
433 printString(R"RawString(The character array "insert_or_delete" can only contain characters 'I', 'B', 'S', and 'D'!
434 )RawString");
435 asm("unreachable");
436 EndIf
437 i += 1;
438 EndWhile
439
440 inorderCounter := 1;
441 assignCoordinatesInorder(root, 0, 110, 90);
442
443 InstantiateStructure Maxima globalMax;
444 globalMax.minimumX := globalMax.maximumX := 0;
445 If root Then
446 globalMax.minimumX := root->x;
447 globalMax.maximumX := root->x;
448 findMinMaxX(root, AddressOf(globalMax));
449 EndIf
450
451 Integer32 margin := 20;
452 Integer32 diagramWidth := (globalMax.maximumX - globalMax.minimumX) + 120 + margin * 2;
453 Integer32 diagramHeight := (nodeHeight(root) + 1) * 90 + margin;
454
455 setDiagramWidth(diagramWidth);
456 setDiagramHeight(diagramHeight);
457
458 drawTree(root, globalMax.minimumX - margin);
459
460 freeTree(root);
461 printString("Splay Tree rendered.\n");
462 EndFunction
463