1 // AVLInAEC/AVLInAEC.aec
   2 // AVL demo with JavaScript API: expose keys buffer + setters/getters + render()
   3 // Uses same externals as Huffman demo for drawing.
   4 
   5 #target WASI // Because we want to make sure all accesses are aligned, as the 
   6              // AI I am using seems to assume that when writing the JavaScript.
   7 
   8 Function noMoreFreeMemory() Which Returns Nothing Is External;
   9 Function segmentationFault() Which Returns Nothing Is External;
  10 Function printString(PointerToCharacter string) Which Returns Nothing Is External;
  11 Function clearScreen() Which Returns Nothing Is External;
  12 Function setDiagramWidth(Integer32 width) Which Returns Nothing Is External;
  13 Function setDiagramHeight(Integer32 height) Which Returns Nothing Is External;
  14 Function drawLine(Integer32 x1, Integer32 y1, Integer32 x2, Integer32 y2)
  15     Which Returns Nothing Is External;
  16 Function drawRectangle(Integer32 x, Integer32 y, Integer32 width, Integer32 height)
  17     Which Returns Nothing Is External;
  18 Function drawText(Integer32 x, Integer32 y, PointerToCharacter text)
  19     Which Returns Nothing Is External;
  20 
  21 Integer32 NDEBUG := 1;
  22 
  23 // --- String helpers (small set copied/adapted from Huffman demo) ---
  24 Function strlen(PointerToCharacter str) Which Returns Integer32 Does
  25   If str = 0 Then
  26     Return 0;
  27   EndIf
  28   Integer32 length := 0;
  29   While ValueAt(str + length) Loop
  30     length += 1;
  31   EndWhile
  32   Return length;
  33 EndFunction
  34 
  35 Function strcpy(PointerToCharacter dest, PointerToCharacter src) Which Returns Nothing Does
  36   While ValueAt(src) Loop
  37     ValueAt(dest) := ValueAt(src);
  38     dest += 1;
  39     src += 1;
  40   EndWhile
  41   ValueAt(dest) := 0;
  42 EndFunction
  43 
  44 Function strcat(PointerToCharacter dest, PointerToCharacter src) Which Returns Nothing Does
  45   strcpy(dest + strlen(dest), src);
  46 EndFunction
  47 
  48 Function reverseString(PointerToCharacter string) Which Returns Nothing Does
  49   PointerToCharacter pointerToLastCharacter := string + strlen(string) - 1;
  50   While pointerToLastCharacter - string > 0 Loop
  51     Character tmp := ValueAt(string);
  52     ValueAt(string) := ValueAt(pointerToLastCharacter);
  53     ValueAt(pointerToLastCharacter) := tmp;
  54     string += 1;
  55     pointerToLastCharacter -= 1;
  56   EndWhile
  57 EndFunction
  58 
  59 Function convertIntegerToString(PointerToCharacter string, Integer32 number) 
  60     Which Returns Nothing Does
  61   Integer32 isNumberNegative := 0;
  62   If number < 0 Then
  63     number := -number;
  64     isNumberNegative := 1;
  65   EndIf
  66   Integer32 i := 0;
  67   While number >= 10 Loop
  68     ValueAt(string + i) := '0' + mod(number, 10);
  69     number /= 10;
  70     i += 1;
  71   EndWhile
  72   ValueAt(string + i) := '0' + number;
  73   i += 1;
  74   If isNumberNegative Then 
  75     ValueAt(string + i) := '-';
  76     i += 1;
  77   EndIf
  78   ValueAt(string + i) := 0;
  79   reverseString(string);
  80 EndFunction
  81 
  82 // --- AVL node pool and helpers (pool like Huffman demo) ---
  83 Structure AVLNode Consists Of
  84   Integer32 key;
  85   PointerToAVLNode leftChild, rightChild;
  86   Integer32 height;
  87   Integer32 x, y;
  88 EndStructure
  89 
  90 InstantiateStructure AVLNode avlNodes[128];
  91 Integer16 isAVLNodeUsed[128];
  92 
  93 Function isAVLNodeWithinBounds(PointerToAVLNode node) Which Returns Integer32 Does
  94   Return AddressOf(avlNodes[0]) <= node <= AddressOf(avlNodes[128 - 1]) and
  95       mod(node - AddressOf(avlNodes[0]), SizeOf(AVLNode)) = 0;
  96 EndFunction
  97 
  98 Function newAVLNode() Which Returns PointerToAVLNode Does
  99   Integer16 i := 0;
 100   While i < 128 Loop
 101     If not(isAVLNodeUsed[i]) Then
 102       avlNodes[i].key := 0;
 103       avlNodes[i].leftChild := avlNodes[i].rightChild := PointerToAVLNode(0);
 104       avlNodes[i].height := 1;
 105       avlNodes[i].x := avlNodes[i].y := 0;
 106       isAVLNodeUsed[i] := 1;
 107       Return AddressOf(avlNodes[i]);
 108     EndIf
 109     i += 1;
 110   EndWhile
 111   noMoreFreeMemory();
 112 EndFunction
 113 
 114 Function freeAVLNode(PointerToAVLNode node) Which Returns Nothing Does
 115   If not(isAVLNodeWithinBounds(node)) Then
 116     segmentationFault();
 117   EndIf
 118   isAVLNodeUsed[(node - AddressOf(avlNodes[0])) / SizeOf(AVLNode)] := 0;
 119 EndFunction
 120 
 121 // --- Height and rotation helpers ---
 122 Function nodeHeight(PointerToAVLNode node) Which Returns Integer32 Does
 123   If not(node) Then
 124     Return 0;
 125   EndIf
 126   Return node->height;
 127 EndFunction
 128 
 129 Function max(Integer32 a, Integer32 b) Which Returns Integer32 Does
 130   Return a > b ? a : b;
 131 EndFunction
 132 
 133 Function updateHeight(PointerToAVLNode node) Which Returns Nothing Does
 134   If not(node) Then 
 135     Return;
 136   EndIf
 137   node->height := max(nodeHeight(node->leftChild), nodeHeight(node->rightChild)) + 1;
 138 EndFunction
 139 
 140 Function balanceFactor(PointerToAVLNode node) Which Returns Integer32 Does
 141   If not(node) Then
 142     Return 0;
 143   EndIf
 144   Return nodeHeight(node->leftChild) - nodeHeight(node->rightChild);
 145 EndFunction
 146 
 147 Function rotateRight(PointerToAVLNode y) Which Returns PointerToAVLNode Does
 148   Character stringToBePrinted[32] := {0};
 149   strcat(AddressOf(stringToBePrinted[0]), "Right-rotate around ");
 150   convertIntegerToString(
 151     AddressOf(stringToBePrinted[0]) + strlen(AddressOf(stringToBePrinted[0])),
 152     y->key);
 153   strcat(AddressOf(stringToBePrinted[0]), ".\n");
 154   printString(AddressOf(stringToBePrinted[0]));
 155 
 156   PointerToAVLNode x := y->leftChild;
 157   PointerToAVLNode T2 := x->rightChild;
 158   x->rightChild := y;
 159   y->leftChild := T2;
 160   updateHeight(y);
 161   updateHeight(x);
 162   Return x;
 163 EndFunction
 164 
 165 Function rotateLeft(PointerToAVLNode x) Which Returns PointerToAVLNode Does
 166   Character stringToBePrinted[32] := {0};
 167   strcat(AddressOf(stringToBePrinted[0]), "Left-rotate around ");
 168   convertIntegerToString(
 169     AddressOf(stringToBePrinted[0]) + strlen(AddressOf(stringToBePrinted[0])),
 170     x->key);
 171   strcat(AddressOf(stringToBePrinted[0]), ".\n");
 172   printString(AddressOf(stringToBePrinted[0]));
 173 
 174   PointerToAVLNode y := x->rightChild;
 175   PointerToAVLNode T2 := y->leftChild;
 176   y->leftChild := x;
 177   x->rightChild := T2;
 178   updateHeight(x);
 179   updateHeight(y);
 180   Return y;
 181 EndFunction
 182 
 183 // --- AVL insert (no duplicates) ---
 184 Function avlInsert(PointerToAVLNode node, Integer32 key) 
 185     Which Returns PointerToAVLNode Does
 186   If not(node) Then
 187     PointerToAVLNode n := newAVLNode();
 188     n->key := key;
 189     n->leftChild := n->rightChild := PointerToAVLNode(0);
 190     n->height := 1;
 191     Return n;
 192   EndIf
 193 
 194   If key < node->key Then
 195     node->leftChild := avlInsert(node->leftChild, key);
 196   ElseIf key > node->key Then
 197     node->rightChild := avlInsert(node->rightChild, key);
 198   Else // equal -> ignore duplicate
 199     Return node;
 200   EndIf
 201 
 202   updateHeight(node);
 203   Integer32 bf := balanceFactor(node);
 204 
 205   // LL
 206   If bf > 1 and key < node->leftChild->key Then
 207     Return rotateRight(node);
 208   EndIf
 209 
 210   // RR
 211   If bf < -1 and key > node->rightChild->key Then
 212     Return rotateLeft(node);
 213   EndIf
 214 
 215   // LR
 216   If bf > 1 and key > node->leftChild->key Then
 217     node->leftChild := rotateLeft(node->leftChild);
 218     Return rotateRight(node);
 219   EndIf
 220 
 221   // RL
 222   If bf < -1 and key < node->rightChild->key Then
 223     node->rightChild := rotateRight(node->rightChild);
 224     Return rotateLeft(node);
 225   EndIf
 226 
 227   Return node;
 228 EndFunction
 229 
 230 // --- AVL delete (new) ---
 231 Function minValueNode(PointerToAVLNode node)
 232   Which Returns PointerToAVLNode Does
 233   PointerToAVLNode current := node;
 234   While current->leftChild Loop
 235     current := current->leftChild;
 236   EndWhile
 237   Return current;
 238 EndFunction
 239 
 240 Function avlDelete(PointerToAVLNode root, Integer32 key)
 241     Which Returns PointerToAVLNode Does
 242   If not(root) Then
 243     Return root;
 244   EndIf
 245 
 246   // Standard BST delete
 247   If key < root->key Then
 248     root->leftChild := avlDelete(root->leftChild, key);
 249   ElseIf key > root->key Then
 250     root->rightChild := avlDelete(root->rightChild, key);
 251   Else
 252     // Node with only one child or no child
 253     If not(root->leftChild) Then
 254       PointerToAVLNode temp := root->rightChild;
 255       // free root
 256       freeAVLNode(root);
 257       Return temp;
 258     ElseIf not(root->rightChild) Then
 259       PointerToAVLNode temp := root->leftChild;
 260       freeAVLNode(root);
 261       Return temp;
 262     EndIf
 263 
 264     // Node with two children: Get inorder successor (smallest in the right subtree)
 265     PointerToAVLNode temp := minValueNode(root->rightChild);
 266     // Copy the inorder successor's key to this node
 267     root->key := temp->key;
 268     // Delete the inorder successor
 269     root->rightChild := avlDelete(root->rightChild, temp->key);
 270   EndIf
 271 
 272   // If the tree had only one node then return
 273   If not(root) Then Return root;
 274   EndIf
 275 
 276   // Update height
 277   updateHeight(root);
 278 
 279   // Get balance factor
 280   Integer32 bf := balanceFactor(root);
 281 
 282   // If unbalanced, there are 4 cases
 283   // Left Left
 284   If bf > 1 and balanceFactor(root->leftChild) >= 0 Then
 285     Return rotateRight(root);
 286   EndIf
 287 
 288   // Left Right
 289   If bf > 1 and balanceFactor(root->leftChild) < 0 Then
 290     root->leftChild := rotateLeft(root->leftChild);
 291     Return rotateRight(root);
 292   EndIf
 293 
 294   // Right Right
 295   If bf < -1 and balanceFactor(root->rightChild) <= 0 Then
 296     Return rotateLeft(root);
 297   EndIf
 298 
 299   // Right Left
 300   If bf < -1 and balanceFactor(root->rightChild) > 0 Then
 301     root->rightChild := rotateRight(root->rightChild);
 302     Return rotateLeft(root);
 303   EndIf
 304 
 305   Return root;
 306 EndFunction
 307 
 308 // --- Keys buffer (exposed to JS) ---
 309 Integer32 keys[128];
 310 Integer32 numberOfKeys := 0;
 311 Character insert_or_delete[128];
 312 
 313 Function getAddressOfKeys() Which Returns PointerToInteger32 Does
 314   Return AddressOf(keys[0]);
 315 EndFunction
 316 
 317 Function getAddressOfInsertOrDelete() Which Returns PointerToCharacter Does
 318   Return AddressOf(insert_or_delete[0]);
 319 EndFunction
 320 
 321 Function setNumberOfKeys(Integer32 n) Which Returns Nothing Does
 322   numberOfKeys := (n < 0) ? 0 :
 323                   (n > 128) ? 128 : n;
 324 EndFunction
 325 
 326 Function getNumberOfKeys() Which Returns Integer32 Does
 327   Return numberOfKeys;
 328 EndFunction
 329 
 330 Function clearKeys() Which Returns Nothing Does
 331   numberOfKeys := 0;
 332 EndFunction
 333 
 334 // --- Layout & drawing helpers (in-order X, depth-based Y) ---
 335 Integer32 inorderCounter := 0;
 336 
 337 Function assignCoordinatesInorder(PointerToAVLNode node,
 338                                   Integer32 depth,
 339 				  Integer32 horizontalSpacing,
 340 				  Integer32 verticalSpacing)
 341     Which Returns Nothing Does
 342   If not(node) Then
 343     Return;
 344   EndIf
 345   assignCoordinatesInorder(node->leftChild,
 346                            depth + 1,
 347 			   horizontalSpacing,
 348 			   verticalSpacing);
 349   node->x := inorderCounter * horizontalSpacing;
 350   node->y := depth * verticalSpacing;
 351   inorderCounter += 1;
 352   assignCoordinatesInorder(node->rightChild,
 353                            depth + 1,
 354 			   horizontalSpacing,
 355 			   verticalSpacing);
 356 EndFunction
 357 
 358 Structure Maxima Consists Of
 359   Integer32 minimumX, maximumX;
 360 EndStructure
 361 
 362 Function findMinMaxX(PointerToAVLNode node,
 363                      PointerToMaxima m) 
 364     Which Returns Nothing Does
 365   If not(node) Then
 366     Return;
 367   EndIf
 368   If node->x < m->minimumX Then
 369     m->minimumX := node->x;
 370   EndIf
 371   If node->x > m->maximumX Then
 372     m->maximumX := node->x;
 373   EndIf
 374   findMinMaxX(node->leftChild, m);
 375   findMinMaxX(node->rightChild, m);
 376 EndFunction
 377 
 378 Function drawAVL(PointerToAVLNode node, Integer32 offsetX)
 379     Which Returns Nothing Does
 380   If not(node) Then 
 381     Return;
 382   EndIf
 383   Integer32 drawX := node->x - offsetX;
 384   Integer32 drawY := node->y;
 385   drawRectangle(drawX, drawY, 120, 60);
 386 
 387   // key text
 388   Character keyStr[16] := {0};
 389   strcat(AddressOf(keyStr[0]), "Key: ");
 390   convertIntegerToString(
 391     AddressOf(keyStr[0]) + strlen(AddressOf(keyStr[0])),
 392     node->key);
 393   drawText(drawX + 6, drawY + 14, AddressOf(keyStr[0]));
 394 
 395   // height text
 396   Character heightStr[16] := {0};
 397   strcat(AddressOf(heightStr[0]), "Height: ");
 398   convertIntegerToString(
 399     AddressOf(heightStr[0]) + strlen(AddressOf(heightStr[0])),
 400     node->height);
 401   drawText(drawX + 6, drawY + 30, AddressOf(heightStr[0]));
 402   
 403   // BalanceFactor text
 404   Character balanceFactorStr[16] := {0};
 405   strcat(AddressOf(balanceFactorStr[0]), "BF: ");
 406   convertIntegerToString(
 407     AddressOf(balanceFactorStr[0]) + strlen(AddressOf(balanceFactorStr[0])),
 408     balanceFactor(node));
 409   drawText(drawX + 6, drawY + 30 + (30 - 14), AddressOf(balanceFactorStr[0]));
 410 
 411   If node->leftChild Then
 412     drawLine(drawX + 60, drawY + 60, node->leftChild->x - offsetX + 60, node->leftChild->y);
 413     drawAVL(node->leftChild, offsetX);
 414   EndIf
 415   If node->rightChild Then
 416     drawLine(drawX + 60, drawY + 60, node->rightChild->x - offsetX + 60, node->rightChild->y);
 417     drawAVL(node->rightChild, offsetX);
 418   EndIf
 419 EndFunction
 420 
 421 // --- Free tree ---
 422 Function freeAVLTree(PointerToAVLNode node) Which Returns Nothing Does
 423   If not(node) Then
 424     Return;
 425   EndIf
 426   If node->leftChild Then 
 427     freeAVLTree(node->leftChild);
 428   EndIf
 429   If node->rightChild Then 
 430     freeAVLTree(node->rightChild);
 431   EndIf
 432   freeAVLNode(node);
 433 EndFunction
 434 
 435 // --- render() exposed to JS: build tree from keys[] and draw it ---
 436 Function render() Which Returns Nothing Does
 437   clearScreen();
 438   PointerToAVLNode root := PointerToAVLNode(0);
 439   Integer32 i := 0;
 440   While i < numberOfKeys Loop
 441     If insert_or_delete[i] = 'I' Then
 442       Character stringToBePrinted[32] := {0};
 443       strcat(AddressOf(stringToBePrinted[0]), "Inserting ");
 444       convertIntegerToString(
 445         AddressOf(stringToBePrinted[0]) + strlen(AddressOf(stringToBePrinted[0])),
 446 	keys[i]);
 447       strcat(AddressOf(stringToBePrinted[0]), "...\n");
 448       printString(AddressOf(stringToBePrinted[0]));
 449 
 450       root := avlInsert(root, keys[i]);
 451     ElseIf insert_or_delete[i] = 'D' Then
 452       Character stringToBePrinted[32] := {0};
 453       strcat(AddressOf(stringToBePrinted[0]), "Deleting ");
 454       convertIntegerToString(
 455         AddressOf(stringToBePrinted[0]) + strlen(AddressOf(stringToBePrinted[0])),
 456 	keys[i]);
 457       strcat(AddressOf(stringToBePrinted[0]), "...\n");
 458       printString(AddressOf(stringToBePrinted[0]));
 459 
 460       root := avlDelete(root, keys[i]);
 461     Else
 462       printString(R"RawString(The character array "insert_or_delete" can only contain characters 'I' and 'D'!
 463 )RawString");
 464       asm("unreachable");
 465     EndIf
 466     i += 1;
 467   EndWhile
 468 
 469   // Layout with some spacing; adjust constants as you prefer
 470   inorderCounter := 1;
 471   assignCoordinatesInorder(root, 0, 110, 90);
 472 
 473   InstantiateStructure Maxima globalMax;
 474   globalMax.minimumX := globalMax.maximumX := 0;
 475   If root Then
 476     globalMax.minimumX := root->x;
 477     globalMax.maximumX := root->x;
 478     findMinMaxX(root, AddressOf(globalMax));
 479   EndIf
 480 
 481   Integer32 margin := 20;
 482   Integer32 diagramWidth := (globalMax.maximumX - globalMax.minimumX) + 120 + margin * 2;
 483   Integer32 diagramHeight := (nodeHeight(root) + 1) * 90 + margin;
 484 
 485   setDiagramWidth(diagramWidth);
 486   setDiagramHeight(diagramHeight);
 487 
 488   drawAVL(root, globalMax.minimumX - margin);
 489 
 490   freeAVLTree(root);
 491   printString("AVL rendered.\n");
 492 EndFunction
 493 
 494 // Keep main for compatibility (just calls render), but JS can call render() directly.
 495 Function main() Which Returns Nothing Does
 496   render();
 497 EndFunction
 498