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
 274     Return root;
 275   EndIf
 276 
 277   // Update height
 278   updateHeight(root);
 279 
 280   // Get balance factor
 281   Integer32 bf := balanceFactor(root);
 282 
 283   // If unbalanced, there are 4 cases
 284   // Left Left
 285   If bf > 1 and balanceFactor(root->leftChild) >= 0 Then
 286     Return rotateRight(root);
 287   EndIf
 288 
 289   // Left Right
 290   If bf > 1 and balanceFactor(root->leftChild) < 0 Then
 291     root->leftChild := rotateLeft(root->leftChild);
 292     Return rotateRight(root);
 293   EndIf
 294 
 295   // Right Right
 296   If bf < -1 and balanceFactor(root->rightChild) <= 0 Then
 297     Return rotateLeft(root);
 298   EndIf
 299 
 300   // Right Left
 301   If bf < -1 and balanceFactor(root->rightChild) > 0 Then
 302     root->rightChild := rotateRight(root->rightChild);
 303     Return rotateLeft(root);
 304   EndIf
 305 
 306   Return root;
 307 EndFunction
 308 
 309 // --- Keys buffer (exposed to JS) ---
 310 Integer32 keys[128];
 311 Integer32 numberOfKeys := 0;
 312 Character insert_or_delete[128];
 313 
 314 Function getAddressOfKeys() Which Returns PointerToInteger32 Does
 315   Return AddressOf(keys[0]);
 316 EndFunction
 317 
 318 Function getAddressOfInsertOrDelete() Which Returns PointerToCharacter Does
 319   Return AddressOf(insert_or_delete[0]);
 320 EndFunction
 321 
 322 Function setNumberOfKeys(Integer32 n) Which Returns Nothing Does
 323   numberOfKeys := (n < 0) ? 0 :
 324                   (n > 128) ? 128 : n;
 325 EndFunction
 326 
 327 Function getNumberOfKeys() Which Returns Integer32 Does
 328   Return numberOfKeys;
 329 EndFunction
 330 
 331 Function clearKeys() Which Returns Nothing Does
 332   numberOfKeys := 0;
 333 EndFunction
 334 
 335 // --- Layout & drawing helpers (in-order X, depth-based Y) ---
 336 Integer32 inorderCounter := 0;
 337 
 338 Function assignCoordinatesInorder(PointerToAVLNode node,
 339                                   Integer32 depth,
 340 				  Integer32 horizontalSpacing,
 341 				  Integer32 verticalSpacing)
 342     Which Returns Nothing Does
 343   If not(node) Then
 344     Return;
 345   EndIf
 346   assignCoordinatesInorder(node->leftChild,
 347                            depth + 1,
 348 			   horizontalSpacing,
 349 			   verticalSpacing);
 350   node->x := inorderCounter * horizontalSpacing;
 351   node->y := depth * verticalSpacing;
 352   inorderCounter += 1;
 353   assignCoordinatesInorder(node->rightChild,
 354                            depth + 1,
 355 			   horizontalSpacing,
 356 			   verticalSpacing);
 357 EndFunction
 358 
 359 Structure Maxima Consists Of
 360   Integer32 minimumX, maximumX;
 361 EndStructure
 362 
 363 Function findMinMaxX(PointerToAVLNode node,
 364                      PointerToMaxima m) 
 365     Which Returns Nothing Does
 366   If not(node) Then
 367     Return;
 368   EndIf
 369   If node->x < m->minimumX Then
 370     m->minimumX := node->x;
 371   EndIf
 372   If node->x > m->maximumX Then
 373     m->maximumX := node->x;
 374   EndIf
 375   findMinMaxX(node->leftChild, m);
 376   findMinMaxX(node->rightChild, m);
 377 EndFunction
 378 
 379 Function drawAVL(PointerToAVLNode node, Integer32 offsetX)
 380     Which Returns Nothing Does
 381   If not(node) Then 
 382     Return;
 383   EndIf
 384   Integer32 drawX := node->x - offsetX;
 385   Integer32 drawY := node->y;
 386   drawRectangle(drawX, drawY, 120, 60);
 387 
 388   // key text
 389   Character keyStr[16] := {0};
 390   strcat(AddressOf(keyStr[0]), "Key: ");
 391   convertIntegerToString(
 392     AddressOf(keyStr[0]) + strlen(AddressOf(keyStr[0])),
 393     node->key);
 394   drawText(drawX + 6, drawY + 14, AddressOf(keyStr[0]));
 395 
 396   // height text
 397   Character heightStr[16] := {0};
 398   strcat(AddressOf(heightStr[0]), "Height: ");
 399   convertIntegerToString(
 400     AddressOf(heightStr[0]) + strlen(AddressOf(heightStr[0])),
 401     node->height);
 402   drawText(drawX + 6, drawY + 30, AddressOf(heightStr[0]));
 403   
 404   // BalanceFactor text
 405   Character balanceFactorStr[16] := {0};
 406   strcat(AddressOf(balanceFactorStr[0]), "BF: ");
 407   convertIntegerToString(
 408     AddressOf(balanceFactorStr[0]) + strlen(AddressOf(balanceFactorStr[0])),
 409     balanceFactor(node));
 410   drawText(drawX + 6, drawY + 30 + (30 - 14), AddressOf(balanceFactorStr[0]));
 411 
 412   If node->leftChild Then
 413     drawLine(drawX + 60, drawY + 60, node->leftChild->x - offsetX + 60, node->leftChild->y);
 414     drawAVL(node->leftChild, offsetX);
 415   EndIf
 416   If node->rightChild Then
 417     drawLine(drawX + 60, drawY + 60, node->rightChild->x - offsetX + 60, node->rightChild->y);
 418     drawAVL(node->rightChild, offsetX);
 419   EndIf
 420 EndFunction
 421 
 422 // --- Free tree ---
 423 Function freeAVLTree(PointerToAVLNode node) Which Returns Nothing Does
 424   If not(node) Then
 425     Return;
 426   EndIf
 427   If node->leftChild Then 
 428     freeAVLTree(node->leftChild);
 429   EndIf
 430   If node->rightChild Then 
 431     freeAVLTree(node->rightChild);
 432   EndIf
 433   freeAVLNode(node);
 434 EndFunction
 435 
 436 // --- render() exposed to JS: build tree from keys[] and draw it ---
 437 Function render() Which Returns Nothing Does
 438   clearScreen();
 439   PointerToAVLNode root := PointerToAVLNode(0);
 440   Integer32 i := 0;
 441   While i < numberOfKeys Loop
 442     If insert_or_delete[i] = 'I' Then
 443       Character stringToBePrinted[32] := {0};
 444       strcat(AddressOf(stringToBePrinted[0]), "Inserting ");
 445       convertIntegerToString(
 446         AddressOf(stringToBePrinted[0]) + strlen(AddressOf(stringToBePrinted[0])),
 447 	keys[i]);
 448       strcat(AddressOf(stringToBePrinted[0]), "...\n");
 449       printString(AddressOf(stringToBePrinted[0]));
 450 
 451       root := avlInsert(root, keys[i]);
 452     ElseIf insert_or_delete[i] = 'D' Then
 453       Character stringToBePrinted[32] := {0};
 454       strcat(AddressOf(stringToBePrinted[0]), "Deleting ");
 455       convertIntegerToString(
 456         AddressOf(stringToBePrinted[0]) + strlen(AddressOf(stringToBePrinted[0])),
 457 	keys[i]);
 458       strcat(AddressOf(stringToBePrinted[0]), "...\n");
 459       printString(AddressOf(stringToBePrinted[0]));
 460 
 461       root := avlDelete(root, keys[i]);
 462     Else
 463       printString(R"RawString(The character array "insert_or_delete" can only contain characters 'I' and 'D'!
 464 )RawString");
 465       asm("unreachable");
 466     EndIf
 467     i += 1;
 468   EndWhile
 469 
 470   // Layout with some spacing; adjust constants as you prefer
 471   inorderCounter := 1;
 472   assignCoordinatesInorder(root, 0, 110, 90);
 473 
 474   InstantiateStructure Maxima globalMax;
 475   globalMax.minimumX := globalMax.maximumX := 0;
 476   If root Then
 477     globalMax.minimumX := root->x;
 478     globalMax.maximumX := root->x;
 479     findMinMaxX(root, AddressOf(globalMax));
 480   EndIf
 481 
 482   Integer32 margin := 20;
 483   Integer32 diagramWidth := (globalMax.maximumX - globalMax.minimumX) + 120 + margin * 2;
 484   Integer32 diagramHeight := (nodeHeight(root) + 1) * 90 + margin;
 485 
 486   setDiagramWidth(diagramWidth);
 487   setDiagramHeight(diagramHeight);
 488 
 489   drawAVL(root, globalMax.minimumX - margin);
 490 
 491   freeAVLTree(root);
 492   printString("AVL rendered.\n");
 493 EndFunction
 494 
 495 // Keep main for compatibility (just calls render), but JS can call render() directly.
 496 Function main() Which Returns Nothing Does
 497   render();
 498 EndFunction
 499