1 #target WASI // Because we want to make sure all accesses are aligned.
   2 
   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 and 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           redBlackTreeNodes[i].parent :=
 105             PointerToRedBlackTreeNode(0);
 106       redBlackTreeNodes[i].color := 'R';
 107       redBlackTreeNodes[i].x := redBlackTreeNodes[i].y := 0;
 108       isRedBlackTreeNodeUsed[i] := 1;
 109       Return AddressOf(redBlackTreeNodes[i]);
 110     EndIf
 111     i += 1;
 112   EndWhile
 113   noMoreFreeMemory();
 114 EndFunction
 115 
 116 Function freeRedBlackTreeNode(
 117   PointerToRedBlackTreeNode node) Which Returns Nothing Does
 118   If not(isRedBlackTreeNodeWithinBounds(node)) Then
 119     segmentationFault();
 120   EndIf
 121   isRedBlackTreeNodeUsed[
 122     (node - AddressOf(redBlackTreeNodes[0])) / SizeOf(RedBlackTreeNode)] := 0;
 123 EndFunction
 124 
 125 Function RRotate(PointerToRedBlackTreeNode y)
 126   Which Returns PointerToRedBlackTreeNode Does
 127   Character stringToBePrinted[32] := {0};
 128   strcat(AddressOf(stringToBePrinted[0]), "Right-rotate around ");
 129   appendIntegerToString(
 130     AddressOf(stringToBePrinted[0]),
 131     y->key);
 132   strcat(AddressOf(stringToBePrinted[0]), ".\n");
 133   printString(AddressOf(stringToBePrinted[0]));
 134 
 135   PointerToRedBlackTreeNode x := y->leftChild;
 136   PointerToRedBlackTreeNode T2 := x->rightChild;
 137   x->rightChild := y;
 138   y->leftChild := T2;
 139   y->parent := x;
 140   If T2 Then
 141     T2->parent := y;
 142   EndIf
 143   Return x;
 144 EndFunction
 145 
 146 Function LRotate(PointerToRedBlackTreeNode x)
 147   Which Returns PointerToRedBlackTreeNode Does
 148   Character stringToBePrinted[32] := {0};
 149   strcat(AddressOf(stringToBePrinted[0]), "Left-rotate around ");
 150   appendIntegerToString(
 151     AddressOf(stringToBePrinted[0]),
 152     x->key);
 153   strcat(AddressOf(stringToBePrinted[0]), ".\n");
 154   printString(AddressOf(stringToBePrinted[0]));
 155 
 156   PointerToRedBlackTreeNode y := x->rightChild;
 157   PointerToRedBlackTreeNode T2 := y->leftChild;
 158   y->leftChild := x;
 159   x->rightChild := T2;
 160   x->parent := y;
 161   If T2 Then
 162     T2->parent := x;
 163   EndIf
 164   Return y;
 165 EndFunction
 166 
 167 PointerToRedBlackTreeNode root;
 168 Integer32 ll := 0, rr := 0, lr := 0, rl := 0;
 169 
 170 Function Insert(PointerToRedBlackTreeNode node, Integer32 X)
 171   Which Returns PointerToRedBlackTreeNode Is Declared;
 172 
 173 Function InsertRBT(PointerToRedBlackTreeNode node, Integer32 X)
 174   Which Returns PointerToRedBlackTreeNode Does
 175   PointerToRedBlackTreeNode newnode;
 176   If not(node) Then
 177     newnode := newRedBlackTreeNode();
 178     newnode->key := X;
 179     newnode->color := 'B';
 180     Return newnode;
 181   EndIf
 182   newnode := Insert(node, X);
 183   newnode->parent := PointerToRedBlackTreeNode(0);
 184   Return newnode;
 185 EndFunction
 186 
 187 Function Insert(PointerToRedBlackTreeNode node, Integer32 X)
 188   Which Returns PointerToRedBlackTreeNode Does
 189   Integer32 flag := 0;
 190   If not(node) Then
 191     PointerToRedBlackTreeNode ret := newRedBlackTreeNode();
 192     ret->key := X;
 193     Return ret;
 194   EndIf
 195   If X < node->key Then
 196     node->leftChild := Insert(node->leftChild, X);
 197     node->leftChild->parent := node;
 198     If not(node=root) Then
 199       If node->color = 'R' and node->leftChild->color = 'R' Then
 200         flag := 1;
 201       EndIf
 202     EndIf
 203   ElseIf X > node->key Then
 204     node->rightChild := Insert(node->rightChild, X);
 205     node->rightChild->parent := node;
 206     If not(node=root) Then
 207       If node->color = 'R' and node->rightChild->color = 'R' Then
 208         flag := 1;
 209       EndIf
 210     EndIf
 211   Else
 212     Return node;
 213   EndIf
 214 
 215   If ll Then
 216     node := LRotate( node );
 217     node->color := 'B';
 218     node->leftChild->color := 'R';
 219     ll := 0;
 220   ElseIf rr Then
 221     node := RRotate( node );
 222     node->color := 'B';
 223     node->rightChild->color := 'R';
 224     rr  := 0;
 225   ElseIf rl Then
 226     node->rightChild := RRotate( node->rightChild );
 227     node->rightChild->parent := node;
 228     node := LRotate( node );
 229     node->color := 'B';
 230     node->leftChild->color := 'R';
 231     rl := 0;
 232   ElseIf lr Then
 233     node->leftChild := LRotate( node->leftChild );
 234     node->leftChild->parent := node;
 235     node := RRotate( node );
 236     node->color := 'B';
 237     node->rightChild->color := 'R';
 238     lr := 0;
 239   EndIf
 240 
 241   If flag Then  // RED-RED conflict
 242     If node->parent->rightChild = node Then
 243       If node->parent->leftChild = PointerToRedBlackTreeNode(0) or node->parent->leftChild->color = 'B' Then
 244         If not(node->leftChild = PointerToRedBlackTreeNode(0)) and node->leftChild->color = 'R' Then
 245           rl := 1;
 246         ElseIf not(node->rightChild = PointerToRedBlackTreeNode(0)) and node->rightChild->color = 'R' Then
 247           ll := 1;
 248         EndIf
 249       Else
 250         node->parent->leftChild->color := 'B';
 251         node->color := 'B';
 252         If not(node->parent = root) Then
 253           node->parent->color := 'R';
 254         EndIf
 255       EndIf
 256     Else
 257       If node->parent->rightChild = PointerToRedBlackTreeNode(0) or node->parent->rightChild->color = 'B' Then
 258         If not(node->leftChild = PointerToRedBlackTreeNode(0)) and node->leftChild->color = 'R' Then
 259           rr := 1;
 260         ElseIf not(node->rightChild = PointerToRedBlackTreeNode(0)) and node->rightChild->color = 'R' Then
 261           lr := 1;
 262         EndIf
 263       Else
 264         node->parent->rightChild->color := 'B';
 265         node->color := 'B';
 266         If not(node->parent = root) Then
 267           node->parent->color := 'R';
 268         EndIf
 269       EndIf
 270     EndIf
 271     flag := 0;
 272   EndIf
 273   Return node; 
 274 EndFunction
 275 
 276 Function leftRotate(PointerToRedBlackTreeNode t) Which Returns Nothing Does
 277   Character stringToBePrinted[32] := {0};
 278   strcat(AddressOf(stringToBePrinted[0]), "Left-rotate around ");
 279   appendIntegerToString(
 280     AddressOf(stringToBePrinted[0]),
 281     t->key);
 282   strcat(AddressOf(stringToBePrinted[0]), ".\n");
 283   printString(AddressOf(stringToBePrinted[0]));
 284 
 285   PointerToRedBlackTreeNode tParent := t->rightChild;
 286   If t = root Then
 287     root := tParent;
 288   EndIf
 289   If t->parent Then
 290     If t = t->parent->leftChild Then
 291       t->parent->leftChild := tParent;
 292     Else
 293       t->parent->rightChild := tParent;
 294     EndIf
 295   EndIf
 296   tParent->parent := t->parent;
 297   t->parent := tParent;
 298   t->rightChild := tParent->leftChild;
 299   If tParent->leftChild Then
 300     tParent->leftChild->parent := t;
 301   EndIf
 302   tParent->leftChild := t;
 303 EndFunction
 304 
 305 Function rightRotate(PointerToRedBlackTreeNode t) Which Returns Nothing Does
 306   Character stringToBePrinted[32] := {0};
 307   strcat(AddressOf(stringToBePrinted[0]), "Right-rotate around ");
 308   appendIntegerToString(
 309     AddressOf(stringToBePrinted[0]),
 310     t->key);
 311   strcat(AddressOf(stringToBePrinted[0]), ".\n");
 312   printString(AddressOf(stringToBePrinted[0]));
 313 
 314   PointerToRedBlackTreeNode tParent := t->leftChild;
 315   If t = root Then
 316     root := tParent;
 317   EndIf
 318   If t->parent Then
 319     If t = t->parent->leftChild Then
 320       t->parent->leftChild := tParent;
 321     Else
 322       t->parent->rightChild := tParent;
 323     EndIf
 324   EndIf
 325   tParent->parent := t->parent;
 326   t->parent := tParent;
 327   t->leftChild := tParent->rightChild;
 328   If tParent->rightChild Then
 329     tParent->rightChild->parent := t;
 330   EndIf
 331   tParent->rightChild := t;
 332 EndFunction
 333 
 334 Function Sibling(PointerToRedBlackTreeNode v)
 335   Which Returns PointerToRedBlackTreeNode Does
 336   If not(v->parent) Then
 337     Return 0;
 338   EndIf
 339   If v = v->parent->leftChild Then
 340     Return v->parent->rightChild;
 341   EndIf
 342   Return v->parent->leftChild;
 343 EndFunction
 344 
 345 Function FixDoubleBlack(PointerToRedBlackTreeNode x) Which Returns Nothing Does
 346   If x = root Then
 347     Return;
 348   EndIf
 349   PointerToRedBlackTreeNode sibling := Sibling( x ), parent := x->parent;
 350   If not(sibling) Then
 351     FixDoubleBlack(parent);
 352   Else
 353     If sibling->color = 'R' Then
 354       parent->color := 'R';
 355       sibling->color := 'B';
 356       If sibling = sibling->parent->leftChild Then
 357         rightRotate(parent);
 358       Else 
 359         leftRotate(parent);
 360       EndIf
 361       FixDoubleBlack(x); 
 362     Else
 363       If not(sibling->leftChild = PointerToRedBlackTreeNode(0)) and sibling->leftChild->color = 'R' Then
 364         If sibling = sibling->parent->leftChild Then
 365           sibling->leftChild->color := sibling->color;
 366           sibling->color := parent->color;
 367           rightRotate(parent); 
 368         Else
 369           sibling->leftChild->color := parent->color;
 370           rightRotate(sibling);
 371           leftRotate(parent);
 372         EndIf
 373         parent->color := 'B'; 
 374       ElseIf not(sibling->rightChild = PointerToRedBlackTreeNode(0)) and sibling->rightChild->color='R' Then
 375         If sibling = sibling->parent->leftChild Then
 376           sibling->rightChild->color := parent->color;
 377           leftRotate(sibling);
 378           rightRotate(parent); 
 379         Else
 380           sibling->rightChild->color := sibling->color;
 381           sibling->color := parent->color;
 382           leftRotate(parent);
 383         EndIf
 384         parent->color := 'B';
 385       Else
 386         sibling->color := 'R';
 387         If parent->color = 'B' Then
 388           FixDoubleBlack(parent);
 389         Else
 390           parent->color := 'B';
 391         EndIf
 392       EndIf
 393     EndIf
 394   EndIf
 395 EndFunction
 396 
 397 Function SmallestNode(PointerToRedBlackTreeNode node) Which Returns
 398   PointerToRedBlackTreeNode Does
 399   PointerToRedBlackTreeNode t := node;
 400   While t -> leftChild Loop
 401     t := t->leftChild;
 402   EndWhile
 403   Return t;
 404 EndFunction
 405 
 406 Function ReplaceRBT(PointerToRedBlackTreeNode t)
 407   Which Returns PointerToRedBlackTreeNode Does
 408   If not(t->leftChild = PointerToRedBlackTreeNode(0)) and
 409     not(t->rightChild = PointerToRedBlackTreeNode(0)) Then
 410     Return SmallestNode(t->rightChild);
 411   ElseIf not(t->leftChild) and not(t->rightChild) Then
 412     Return 0;
 413   ElseIf t->leftChild Then
 414     Return t->leftChild;
 415   Else
 416     Return t->rightChild;
 417   EndIf
 418   asm("unreachable");
 419 EndFunction
 420 
 421 Function DeleteNode(PointerToRedBlackTreeNode v)
 422   Which Returns Nothing Does
 423   PointerToRedBlackTreeNode u := ReplaceRBT(v);
 424   Integer32 uvBothBlack := (not(u) or u->color = 'B') and v->color = 'B';
 425   PointerToRedBlackTreeNode parent := v->parent;
 426   If not(u) Then
 427     If v = root Then
 428       root := PointerToRedBlackTreeNode(0);
 429     Else
 430       If uvBothBlack Then
 431         FixDoubleBlack(v);
 432       Else
 433         PointerToRedBlackTreeNode vsib := Sibling(v);
 434         If vsib Then
 435           vsib->color := 'R';
 436         EndIf
 437       EndIf
 438       If v = v->parent->leftChild Then
 439         parent->leftChild := PointerToRedBlackTreeNode(0);
 440       Else
 441         parent->rightChild := PointerToRedBlackTreeNode(0);
 442       EndIf
 443     EndIf
 444     freeRedBlackTreeNode(v);
 445     Return;
 446   EndIf
 447   If v->leftChild = PointerToRedBlackTreeNode(0)
 448     or v->rightChild = PointerToRedBlackTreeNode(0) Then
 449     If v = root Then
 450       v->key := u->key;
 451       v->leftChild := v->rightChild := PointerToRedBlackTreeNode(0);
 452       freeRedBlackTreeNode(u);
 453     Else
 454       If v = v->parent->leftChild Then
 455         parent->leftChild := u;
 456       Else
 457         parent->rightChild := u;
 458       EndIf
 459       freeRedBlackTreeNode(v);
 460       u->parent := parent;
 461       If uvBothBlack Then
 462         FixDoubleBlack(u);
 463       Else
 464         u->color := 'B';
 465       EndIf
 466     EndIf
 467     Return;
 468   EndIf
 469   Integer32 tmp := u->key;
 470   u->key := v->key;
 471   v->key := tmp;
 472   DeleteNode(u);
 473 EndFunction
 474 
 475 Function SearchRBT(
 476   PointerToRedBlackTreeNode node,
 477   Integer32 X,
 478   PointerToPointerToRedBlackTreeNode parent)
 479   Which Returns Integer32 Does
 480   If not(node) Then
 481     Return 0;
 482   ElseIf node->key = X Then
 483     Return 1;
 484   EndIf
 485   ValueAt(parent) := node;
 486   If node->key > X Then
 487     Return SearchRBT(node->leftChild, X, parent);
 488   Else
 489     Return SearchRBT(node->rightChild, X, parent);
 490   EndIf
 491   asm("unreachable");
 492 EndFunction
 493 
 494 Function DeleteRBT(PointerToRedBlackTreeNode node, Integer32 X) Which Returns Nothing Does
 495   If not(node) Then
 496     Return;
 497   EndIf
 498   PointerToRedBlackTreeNode parent := PointerToRedBlackTreeNode(0);
 499   If SearchRBT(node, X, AddressOf(parent)) Then
 500     If not(parent) Then
 501       DeleteNode(node);
 502     ElseIf not(parent->leftChild = PointerToRedBlackTreeNode(0)) and
 503       parent->leftChild->key = X Then
 504       DeleteNode(parent->leftChild);
 505     Else
 506       DeleteNode(parent->rightChild);
 507     EndIf
 508   Else
 509     printString("Node to be deleted has not been found.\n");
 510   EndIf
 511 EndFunction
 512   
 513 
 514 Integer32 keys[128];
 515 Integer32 numberOfKeys := 0;
 516 Character insert_or_delete[128];
 517 
 518 Function getAddressOfKeys() Which Returns PointerToInteger32 Does
 519   Return AddressOf(keys[0]);
 520 EndFunction
 521 
 522 Function getAddressOfInsertOrDelete() Which Returns PointerToCharacter Does
 523   Return AddressOf(insert_or_delete[0]);
 524 EndFunction
 525 
 526 Function setNumberOfKeys(Integer32 n) Which Returns Nothing Does
 527   numberOfKeys := (n < 0) ? 0 :
 528     (n > 128) ? 128 : n;
 529 EndFunction
 530 
 531 Function getNumberOfKeys() Which Returns Integer32 Does
 532   Return numberOfKeys;
 533 EndFunction
 534 
 535 Function clearKeys() Which Returns Nothing Does
 536   numberOfKeys := 0;
 537 EndFunction
 538 
 539 Integer32 inorderCounter := 0;
 540 
 541 Function assignCoordinatesInorder(PointerToRedBlackTreeNode node,
 542   Integer32 depth,
 543   Integer32 horizontalSpacing,
 544   Integer32 verticalSpacing)
 545   Which Returns Nothing Does
 546   If not(node) Then
 547     Return;
 548   EndIf
 549   assignCoordinatesInorder(node->leftChild,
 550     depth + 1,
 551     horizontalSpacing,
 552     verticalSpacing);
 553   node->x := inorderCounter * horizontalSpacing;
 554   node->y := depth * verticalSpacing;
 555   inorderCounter += 1;
 556   assignCoordinatesInorder(node->rightChild,
 557     depth + 1,
 558     horizontalSpacing,
 559     verticalSpacing);
 560 EndFunction
 561 
 562 Structure Maxima Consists Of
 563   Integer32 minimumX, maximumX;
 564 EndStructure
 565 
 566 Function findMinMaxX(PointerToRedBlackTreeNode node,
 567   PointerToMaxima m) 
 568   Which Returns Nothing Does
 569   If not(node) Then
 570     Return;
 571   EndIf
 572   If node->x < m->minimumX Then
 573     m->minimumX := node->x;
 574   EndIf
 575   If node->x > m->maximumX Then
 576     m->maximumX := node->x;
 577   EndIf
 578   findMinMaxX(node->leftChild, m);
 579   findMinMaxX(node->rightChild, m);
 580 EndFunction
 581 
 582 Function drawRedBlackTree(PointerToRedBlackTreeNode node, Integer32 offsetX)
 583   Which Returns Nothing Does
 584   If not(node) Then 
 585     Return;
 586   EndIf
 587   Integer32 drawX := node->x - offsetX;
 588   Integer32 drawY := node->y;
 589   drawRectangle(drawX, drawY, 120, 60, node->color = 'R' ? "Red" : "Black");
 590 
 591   Character keyStr[8] := {0};
 592   convertIntegerToString(AddressOf(keyStr[0]), node->key);
 593   drawText(drawX + 6, drawY + 30, AddressOf(keyStr[0]));
 594 
 595   If node->leftChild Then
 596     drawLine(drawX + 60, drawY + 60, node->leftChild->x - offsetX + 60, node->leftChild->y);
 597     drawRedBlackTree(node->leftChild, offsetX);
 598   EndIf
 599   If node->rightChild Then
 600     drawLine(drawX + 60, drawY + 60, node->rightChild->x - offsetX + 60, node->rightChild->y);
 601     drawRedBlackTree(node->rightChild, offsetX);
 602   EndIf
 603 EndFunction
 604 
 605 Function freeRedBlackTree(PointerToRedBlackTreeNode node) Which Returns Nothing Does
 606   If not(node) Then
 607     Return;
 608   EndIf
 609   If node->leftChild Then 
 610     freeRedBlackTree(node->leftChild);
 611   EndIf
 612   If node->rightChild Then 
 613     freeRedBlackTree(node->rightChild);
 614   EndIf
 615   freeRedBlackTreeNode(node);
 616 EndFunction
 617 
 618 Function max(Integer32 x, Integer32 y) Which Returns Integer32 Does
 619   Return x > y ? x : y;
 620 EndFunction
 621 
 622 Function nodeHeight(PointerToRedBlackTreeNode node)
 623   Which Returns Integer32 Does
 624   Return not(node) ? 0 :
 625     max(nodeHeight(node->leftChild), nodeHeight(node->rightChild)) + 1;
 626 EndFunction
 627 
 628 Character preorderTraversal[128];
 629 
 630 Function setUpPreorderTraversal(PointerToRedBlackTreeNode node)
 631     Which Returns Nothing Does
 632   If node Then
 633     appendIntegerToString(AddressOf(preorderTraversal[0]), node->key);
 634     strcat(AddressOf(preorderTraversal[0]), " ");
 635     setUpPreorderTraversal(node->leftChild);
 636     setUpPreorderTraversal(node->rightChild);
 637   EndIf
 638 EndFunction
 639 
 640 Function getTheAddressOfPreorderTraversal() // Will be called by the
 641                                             // automated testing script.
 642     Which Returns PointerToCharacter Does
 643   Return AddressOf(preorderTraversal[0]);
 644 EndFunction
 645 
 646 // Returns 1 if node is red, 0 otherwise (null counts as black)
 647 Function isRed(PointerToRedBlackTreeNode node) Which Returns Integer32 Does
 648   If not(node) Then
 649     Return 0;
 650   EndIf
 651   Return node->color = 'R';
 652 EndFunction
 653 
 654 // Returns 1 if node is black, 0 otherwise (null counts as black)
 655 Function isBlack(PointerToRedBlackTreeNode node) Which Returns Integer32 Does
 656   If not(node) Then
 657     Return 1;
 658   EndIf
 659   Return node->color = 'B';
 660 EndFunction
 661 
 662 // Validates RB + BST properties.
 663 // Returns black-height if valid, -1 if invalid.
 664 //
 665 // We use strict BST ordering (no duplicates): minKey < key < maxKey.
 666 // Your Insert() ignores duplicates (returns node), so strict ordering is correct.
 667 Function validateRBSubtree(
 668   PointerToRedBlackTreeNode node,
 669   Integer32 minKey,
 670   Integer32 maxKey)
 671   Which Returns Integer32 Does
 672 
 673   If not(node) Then
 674     // NIL leaves are considered black and contribute 1 to black height.
 675     Return 1;
 676   EndIf
 677 
 678   // BST property (strict)
 679   If node->key <= minKey or node->key >= maxKey Then
 680     Return -1;
 681   EndIf
 682 
 683   // Color must be 'R' or 'B'
 684   If node->color != 'R' and node->color != 'B' Then
 685     Return -1;
 686   EndIf
 687 
 688   // Red node cannot have red children
 689   If node->color = 'R' Then
 690     If isRed(node->leftChild) or isRed(node->rightChild) Then
 691       Return -1;
 692     EndIf
 693   EndIf
 694 
 695   Integer32 leftBH := validateRBSubtree(node->leftChild, minKey, node->key);
 696   If leftBH < 0 Then
 697     Return -1;
 698   EndIf
 699 
 700   Integer32 rightBH := validateRBSubtree(node->rightChild, node->key, maxKey);
 701   If rightBH < 0 Then
 702     Return -1;
 703   EndIf
 704 
 705   // Black-height must match
 706   If leftBH != rightBH Then
 707     Return -1;
 708   EndIf
 709 
 710   // Add 1 if this node is black
 711   Return leftBH + (node->color = 'B' ? 1 : 0);
 712 EndFunction
 713 
 714 // Exportable entry point: returns 1 if valid, 0 if invalid.
 715 Function validateRBTree() Which Returns Integer32 Does
 716   If not(root) Then
 717     Return 1;
 718   EndIf
 719 
 720   // Root must be black
 721   If not(root->color = 'B') Then
 722     Return 0;
 723   EndIf
 724 
 725   // Use wide sentinels. Keys are Integer32, so use min/max int32.
 726   // minKey < key < maxKey must hold for all keys.
 727   Integer32 bh := validateRBSubtree(root, -2147483648, 2147483647);
 728   Return bh > 0 ? 1 : 0;
 729 EndFunction
 730 
 731 Function render() Which Returns Nothing Does
 732   clearScreen();
 733   root := PointerToRedBlackTreeNode(0);
 734   Integer32 i := 0;
 735   While i < numberOfKeys Loop
 736     If insert_or_delete[i] = 'I' Then
 737       Character stringToBePrinted[32] := {0};
 738       strcat(AddressOf(stringToBePrinted[0]), "Inserting ");
 739       appendIntegerToString(AddressOf(stringToBePrinted[0]), keys[i]);
 740       strcat(AddressOf(stringToBePrinted[0]), "...\n");
 741       printString(AddressOf(stringToBePrinted[0]));
 742       root := InsertRBT(root, keys[i]);
 743     ElseIf insert_or_delete[i] = 'D' Then
 744       Character stringToBePrinted[32] := {0};
 745       strcat(AddressOf(stringToBePrinted[0]), "Deleting ");
 746       appendIntegerToString(AddressOf(stringToBePrinted[0]), keys[i]);
 747       strcat(AddressOf(stringToBePrinted[0]), "...\n");
 748       printString(AddressOf(stringToBePrinted[0]));
 749       DeleteRBT(root, keys[i]);
 750     Else
 751       printString("The character array \"insert_or_delete\" can only contain characters 'I' and 'D'!\n");
 752       asm("unreachable");
 753     EndIf
 754     i += 1;
 755   EndWhile
 756 
 757   inorderCounter := 1;
 758   assignCoordinatesInorder(root, 0, 110, 90);
 759 
 760   InstantiateStructure Maxima globalMax;
 761   globalMax.minimumX := globalMax.maximumX := 0;
 762   If root Then
 763     globalMax.minimumX := root->x;
 764     globalMax.maximumX := root->x;
 765     findMinMaxX(root, AddressOf(globalMax));
 766   EndIf
 767 
 768   Integer32 margin := 20;
 769   Integer32 diagramWidth := (globalMax.maximumX - globalMax.minimumX) + 120 + margin * 2;
 770   Integer32 diagramHeight := (nodeHeight(root) + 1) * 90 + margin;
 771 
 772   setDiagramWidth(diagramWidth);
 773   setDiagramHeight(diagramHeight);
 774 
 775   drawRedBlackTree(root, globalMax.minimumX - margin);
 776 
 777   preorderTraversal[0] := 0;
 778   setUpPreorderTraversal(root);
 779 
 780   Integer32 ok := validateRBTree();
 781   If not(ok) Then
 782     printString("validateRBTree() failed!\n");
 783     asm("unreachable");
 784   EndIf
 785 
 786   freeRedBlackTree(root);
 787   printString("Red Black Tree rendered.\n");
 788 EndFunction
 789