The Ecere SDK - sdk/blob - ecere/src/com/BTNode.ec

   1 namespace sys;
   2
   3 import "instance"
   4
   5 #include <stdarg.h>
   6
   7 public enum TreePrintStyle { inOrder, postOrder, preOrder, depthOrder };
   8
   9 public void strcatf(char * string, char * format, ...)
  10 {
  11    va_list args;
  12    va_start(args, format);
  13    vsprintf(string+strlen(string),format,args);
  14    va_end(args);
  15 }
  16
  17 public class BTNode : struct
  18 {
  19    class_fixed
  20 public:
  21    uint key;
  22    BTNode parent, left, right;
  23    int depth;
  24
  25    void OnSerialize(IOChannel channel)
  26    {
  27       if(this)
  28       {
  29          bool truth = true;
  30          channel.Serialize(truth);
  31          channel.Serialize(key);
  32          channel.Serialize(left);
  33          channel.Serialize(right);
  34       }
  35       else
  36       {
  37          uint nothing = 0;
  38          channel.Serialize(nothing);
  39       }
  40    }
  41
  42    void OnUnserialize(IOChannel channel)
  43    {
  44       bool truth;
  45       channel.Unserialize(truth);
  46       if(truth)
  47       {
  48          // TODO: Fix typed_object issues
  49          this = eInstance_New(class(BTNode));
  50          channel.Unserialize(key);
  51          channel.Unserialize(left);
  52          if(left) { left.parent = (void *)this; }
  53          channel.Unserialize(right);
  54          if(right) { right.parent = (void *)this; }
  55          depth = ((BTNode)(void *)this).depthProp;
  56       }
  57       else
  58          this = null;
  59    }
  60
  61    property BTNode prev
  62    {
  63       get
  64       {
  65          if(left)
  66             return left.maximum;
  67          while(this)
  68          {
  69             if(parent && this == parent.right)
  70                return parent;
  71             else
  72                this = parent;
  73          }
  74          return this;
  75       }
  76    }
  77
  78    property BTNode next
  79    {
  80       get
  81       {
  82          BTNode right = this.right;
  83          if(right)
  84             return right.minimum;
  85          while(this)
  86          {
  87             BTNode parent = this.parent;
  88             if(parent && this == parent.left)
  89                return parent;
  90             else
  91                this = parent;
  92          }
  93          return null;
  94       }
  95    }
  96
  97    property BTNode minimum
  98    {
  99       get { while(left) this = left; return this; }
 100    }
 101
 102    property BTNode maximum
 103    {
 104       get { while(right) this = right; return this; }
 105    }
 106
 107    property int count
 108    {
 109       get { return 1 + (left ? left.count : 0) + (right ? right.count : 0); }
 110    }
 111    property int depthProp
 112    {
 113       get
 114       {
 115          int leftDepth = left ? (left.depthProp+1) : 0;
 116          int rightDepth = right ? (right.depthProp+1) : 0;
 117          return Max(leftDepth, rightDepth);
 118       }
 119    }
 120 private:
 121
 122    void Free(void (*FreeKey)(void * key))
 123    {
 124         if (left) left.Free(FreeKey);
 125         if (right) right.Free(FreeKey);
 126       if(FreeKey) FreeKey((void *)key);
 127       delete this;
 128    }
 129
 130    bool Add(BinaryTree tree, BTNode node)
 131    {
 132       uint newKey = node.key;
 133       while(true)
 134       {
 135          //int result = (newKey > key) ? 1 : ((newKey < key) ? - 1 : 0);
 136          int result = tree.CompareKey(tree, newKey, key);
 137          if(!result)
 138          {
 139 #ifdef _DEBUG
 140             // sprintf("Adding item already in binary tree\n");
 141 #endif
 142             return false;
 143          }
 144          else if(result > 0)
 145          {
 146             if(right)
 147                this = right;
 148             else
 149             {
 150                node.parent = this;
 151                         right = node;
 152                node.depth = 0;
 153                {
 154                   BTNode n;
 155                   for(n = this; n; n = n.parent)
 156                   {
 157                      int newDepth = Max(n.left ? (n.left.depth+1) : 0, n.right ? (n.right.depth+1) : 0);
 158                      if(newDepth == n.depth)
 159                         break;
 160                      n.depth = newDepth;
 161                   }
 162                }
 163                return true;
 164                 }
 165         }
 166          else
 167          {
 168             if(left)
 169                this = left;
 170             else
 171             {
 172                node.parent = this;
 173                left = node;
 174                node.depth = 0;
 175                {
 176                   BTNode n;
 177                   for(n = this; n; n = n.parent)
 178                   {
 179                      int newDepth = Max(n.left ? (n.left.depth+1) : 0, n.right ? (n.right.depth+1) : 0);
 180                      if(newDepth == n.depth)
 181                         break;
 182                      n.depth = newDepth;
 183                   }
 184                }
 185                return true;
 186             }
 187         }
 188       }
 189    }
 190
 191    bool FindNode(BTNode node)
 192    {
 193       if(this == node)
 194          return true;
 195       else if(left && left.FindNode(node))
 196          return true;
 197       else if(right && right.FindNode(node))
 198          return true;
 199       return false;
 200    }
 201
 202    BTNode Find(BinaryTree tree, uint key)
 203    {
 204       while(this)
 205       {
 206          // int result = (key > this.key) ? 1 : ((key < this.key) ? - 1 : 0);
 207          int result = tree.CompareKey(tree, key, this.key);
 208          if(result < 0)
 209             this = left;
 210          else if(result > 0)
 211             this = right;
 212          else
 213             break;
 214       }
 215       return this;
 216    }
 217
 218    public BTNode FindString(char * key)
 219    {
 220       while(this)
 221       {
 222          int result;
 223          if(key && this.key)
 224             result = strcmp(key, (char *)this.key);
 225          else if(key && !this.key)
 226             result = 1;
 227          else if(!key && this.key)
 228             result = -1;
 229          else
 230             result = 0;
 231
 232          if(result < 0)
 233             this = left;
 234          else if(result > 0)
 235             this = right;
 236          else
 237             break;
 238       }
 239       return this;
 240    }
 241
 242    BTNode FindAll(uint key)
 243    {
 244       BTNode result = null;
 245       if(this.key == key) result = this;
 246       if(!result && left) result = left.FindAll(key);
 247       if(!result && right) result = right.FindAll(key);
 248       return result;
 249    }
 250
 251    void RemoveSwap(BTNode swap)
 252    {
 253       if(swap.left)
 254       {
 255          swap.left.parent = swap.parent;
 256          if(swap == swap.parent.left)
 257             swap.parent.left = swap.left;
 258          else if(swap == swap.parent.right)
 259             swap.parent.right = swap.left;
 260          swap.left = null;
 261       }
 262       if(swap.right)
 263       {
 264          swap.right.parent = swap.parent;
 265          if(swap == swap.parent.left)
 266             swap.parent.left = swap.right;
 267          else if(swap == swap.parent.right)
 268             swap.parent.right = swap.right;
 269          swap.right = null;
 270       }
 271
 272       if(swap == swap.parent.left) swap.parent.left = null;
 273       else if(swap == swap.parent.right) swap.parent.right = null;
 274
 275       {
 276          BTNode n;
 277          for(n = swap.parent; n; n = n.parent)
 278          {
 279             int newDepth = Max(n.left ? (n.left.depth+1) : 0, n.right ? (n.right.depth+1) : 0);
 280             if(newDepth == n.depth)
 281                break;
 282             n.depth = newDepth;
 283             if(n == this) break;
 284          }
 285       }
 286
 287       //if(!swap.left)
 288       {
 289          swap.left = left;
 290          if(left)
 291             left.parent = swap;
 292       }
 293       //if(!swap.right)
 294       {
 295           swap.right = right;
 296           if (right)
 297                right.parent = swap;
 298       }
 299       swap.parent = parent;
 300       left = null;
 301       right = null;
 302       if(parent)
 303       {
 304          if(this == parent.left) parent.left = swap;
 305          else if(this == parent.right) parent.right = swap;
 306       }
 307    }
 308
 309    BTNode RemoveSwapLeft()
 310    {
 311       BTNode swap = left ? left.maximum : right;
 312       BTNode swapParent = null;
 313       if(swap) { swapParent = swap.parent; RemoveSwap(swap); }
 314       if(parent)
 315       {
 316          if(this == parent.left) parent.left = null;
 317          else if(this == parent.right) parent.right = null;
 318       }
 319       {
 320          BTNode n;
 321          for(n = swap ? swap : parent; n; n = n.parent)
 322          {
 323             int newDepth = Max(n.left ? (n.left.depth+1) : 0, n.right ? (n.right.depth+1) : 0);
 324             if(newDepth == n.depth && n != swap)
 325                break;
 326             n.depth = newDepth;
 327          }
 328       }
 329       if(swapParent && swapParent != this)
 330          return swapParent.Rebalance();
 331       else if(swap)
 332          return swap.Rebalance();
 333       else if(parent)
 334          return parent.Rebalance();
 335       else
 336          return null;
 337    }
 338
 339    BTNode RemoveSwapRight()
 340    {
 341       BTNode result;
 342       BTNode swap = right ? right.minimum : left;
 343       BTNode swapParent = null;
 344       if(swap) { swapParent = swap.parent; RemoveSwap(swap); }
 345       if(parent)
 346       {
 347          if(this == parent.left) parent.left = null;
 348          else if(this == parent.right) parent.right = null;
 349       }
 350       {
 351          BTNode n;
 352          for(n = swap ? swap : parent; n; n = n.parent)
 353          {
 354             int newDepth = Max(n.left ? (n.left.depth+1) : 0, n.right ? (n.right.depth+1) : 0);
 355             /*
 356             if(newDepth != n.depthProp)
 357                printf("bug");
 358             */
 359             if(newDepth == n.depth && n != swap)
 360                break;
 361             n.depth = newDepth;
 362          }
 363       }
 364       if(swapParent && swapParent != this)
 365          result = swapParent.Rebalance();
 366       else if(swap)
 367          result = swap.Rebalance();
 368       else if(parent)
 369          result = parent.Rebalance();
 370       else
 371          result = null;
 372       return result;
 373    }
 374
 375    property int balanceFactor
 376    {
 377       get
 378       {
 379          int leftDepth = left ? (left.depth+1) : 0;
 380          int rightDepth = right ? (right.depth+1) : 0;
 381          return rightDepth - leftDepth;
 382       }
 383    }
 384
 385    BTNode Rebalance()
 386    {
 387       while(true)
 388       {
 389          int factor = balanceFactor;
 390          if (factor < -1)
 391          {
 392             if(left.balanceFactor == 1)
 393                DoubleRotateRight();
 394             else
 395                SingleRotateRight();
 396          }
 397          else if (factor > 1)
 398          {
 399             if(right.balanceFactor == -1)
 400                DoubleRotateLeft();
 401             else
 402                SingleRotateLeft();
 403          }
 404          if(parent)
 405             this = parent;
 406          else
 407             return this;
 408       }
 409    }
 410
 411    void SingleRotateRight()
 412    {
 413       if(parent)
 414       {
 415          if(this == parent.left)
 416             parent.left = left;
 417          else if(this == parent.right)
 418             parent.right = left;
 419       }
 420       left.parent = parent;
 421       parent = left;
 422       left = parent.right;
 423       if(left) left.parent = this;
 424       parent.right = this;
 425
 426       depth = Max(left ? (left.depth+1) : 0, right ? (right.depth+1) : 0);
 427       parent.depth = Max(parent.left ? (parent.left.depth+1) : 0, parent.right ? (parent.right.depth+1) : 0);
 428       {
 429          BTNode n;
 430          for(n = parent.parent; n; n = n.parent)
 431          {
 432             int newDepth = Max(n.left ? (n.left.depth+1) : 0, n.right ? (n.right.depth+1) : 0);
 433             /*
 434             if(newDepth != n.depthProp)
 435                printf("bug");
 436             */
 437             if(newDepth == n.depth)
 438                break;
 439             n.depth = newDepth;
 440          }
 441       }
 442    }
 443
 444    void SingleRotateLeft()
 445    {
 446       if(parent)
 447       {
 448          if(this == parent.right)
 449             parent.right = right;
 450          else if(this == parent.left)
 451             parent.left = right;
 452       }
 453       right.parent = parent;
 454       parent = right;
 455       right = parent.left;
 456       if(right) right.parent = this;
 457       parent.left = this;
 458
 459       depth = Max(left ? (left.depth+1) : 0, right ? (right.depth+1) : 0);
 460       parent.depth = Max(parent.left ? (parent.left.depth+1) : 0, parent.right ? (parent.right.depth+1) : 0);
 461       {
 462          BTNode n;
 463          for(n = parent.parent; n; n = n.parent)
 464          {
 465             int newDepth = Max(n.left ? (n.left.depth+1) : 0, n.right ? (n.right.depth+1) : 0);
 466             /*
 467             if(newDepth != n.depthProp)
 468                printf("bug");
 469             */
 470             if(newDepth == n.depth)
 471                break;
 472             n.depth = newDepth;
 473          }
 474       }
 475    }
 476
 477    void DoubleRotateRight()
 478    {
 479       left.SingleRotateLeft();
 480       SingleRotateRight();
 481    }
 482
 483    void DoubleRotateLeft()
 484    {
 485       right.SingleRotateRight();
 486       SingleRotateLeft();
 487    }
 488
 489    #define NUMSIZE   4
 490
 491    char * Print(char * output, TreePrintStyle tps)
 492    {
 493       switch(tps)
 494       {
 495          case inOrder:
 496          case preOrder:
 497          case postOrder:
 498          {
 499             if(tps == preOrder) strcatf(output, "%d ", key);
 500
 501                 if (left) left.Print(output, tps);
 502
 503             if(tps == inOrder) strcatf(output, "%d ", key);
 504
 505                 if (right) right.Print(output, tps);
 506
 507             if(tps == postOrder) strcatf(output, "%d ", key);
 508
 509                 return output;
 510          }
 511          case depthOrder:
 512          {
 513             int maxDepth = depth;
 514             int curDepth;
 515
 516             for(curDepth = 0; curDepth <= maxDepth; curDepth++)
 517             {
 518                int c;
 519                for(c = 0; c<((1<<(maxDepth - curDepth))-1) * NUMSIZE / 2; c++)
 520                   strcat(output, " ");
 521                PrintDepth(output, curDepth, 0, maxDepth, true);
 522                strcat(output, "\n");
 523             }
 524             return output;
 525          }
 526       }
 527       return null;
 528    }
 529
 530    void PrintDepth(char * output, int wantedDepth, int curDepth, int maxDepth, bool last)
 531    {
 532       int c;
 533       if(wantedDepth == curDepth)
 534       {
 535          char nodeString[10] = "";
 536          int len;
 537
 538          if(this)
 539             sprintf(nodeString, "%d", key);
 540
 541          len = strlen(nodeString);
 542          for(c = 0; c<(NUMSIZE - len)/2; c++)
 543             strcat(output, " ");
 544          len += c;
 545          strcat(output, nodeString);
 546          for(c = len; c<NUMSIZE; c++)
 547             strcat(output, " ");
 548
 549          if(curDepth && !last)
 550          {
 551             for(c = 0; c<((1<<(maxDepth-curDepth)) - 1) * NUMSIZE; c++)
 552                strcat(output, " ");
 553          }
 554       }
 555       else if(curDepth <= maxDepth)
 556       {
 557          (this ? left : (BTNode)null).PrintDepth(output, wantedDepth, curDepth+1, maxDepth, last && this && !right);
 558          (this ? right : (BTNode)null).PrintDepth(output, wantedDepth, curDepth+1, maxDepth, last);
 559       }
 560    }
 561
 562    bool Check(BinaryTree tree)
 563    {
 564       bool valid = true;
 565       // Now get the height of each subtree
 566       int leftHeight  = left  ? left.depthProp+1  : 0;
 567       int rightHeight = right ? right.depthProp+1 : 0;
 568
 569       // Verify that AVL tree property is satisfied
 570       int diffHeight = rightHeight - leftHeight;
 571
 572       if(left)
 573       {
 574          if(left.parent != this)
 575          {
 576             printf("Parent not set properly at node %d\n", left.key);
 577             valid = false;
 578          }
 579          valid *= left.Check(tree);
 580       }
 581       if(right)
 582       {
 583          if(right.parent != this)
 584          {
 585             printf("Parent not set properly at node %d\n", right.key);
 586             valid = false;
 587          }
 588          valid *= right.Check(tree);
 589       }
 590
 591       if(depth != depthProp)
 592       {
 593          printf("Depth value at node %d (%d) doesn't match depth property (%d)\n", key, depth, depthProp);
 594          valid = 0;
 595       }
 596
 597       if (diffHeight < -1 || diffHeight > 1)
 598       {
 599          valid = 0;
 600          printf("Height difference is %d at node %d\n", diffHeight, key);
 601       }
 602
 603       // Verify that balance-factor is correct
 604       if (diffHeight != balanceFactor)
 605       {
 606          valid = 0;
 607          printf("Height difference %d doesnt match balance-factor of %d at node \n", diffHeight, balanceFactor, key);
 608       }
 609
 610       // Verify that search-tree property is satisfied
 611       if (left && tree.CompareKey(tree, left.key, key) > 0)
 612       {
 613          valid = false;
 614          printf("Node %d is *smaller* than left subtree %d\n", key, left.key);
 615       }
 616       if (right && tree.CompareKey(tree, right.key, key) < 0)
 617       {
 618          valid = false;
 619          printf("Node %d is *greater* than right subtree %d\n", key, right.key);
 620       }
 621       return valid;
 622    }
 623 };
 624
 625 // TODO: WHY CAN'T WE HAVE THIS ABOVE?
 626
 627 public class StringBTNode : struct // BTNode
 628 {
 629    class_fixed
 630 public:
 631    String key;
 632    StringBTNode parent, left, right;
 633    int depth;
 634
 635    void OnSerialize(IOChannel channel)
 636    {
 637       if(this)
 638       {
 639          bool truth = true;
 640          channel.Serialize(truth);
 641          channel.Serialize(key);
 642          channel.Serialize(left);
 643          channel.Serialize(right);
 644       }
 645       else
 646       {
 647          uint nothing = 0;
 648          channel.Serialize(nothing);
 649       }
 650    }
 651
 652    void OnUnserialize(IOChannel channel)
 653    {
 654       bool truth;
 655       channel.Unserialize(truth);
 656       if(truth)
 657       {
 658          // TODO: Fix typed_object issues
 659          this = eInstance_New(class(StringBTNode));
 660          channel.Unserialize(key);
 661          channel.Unserialize(left);
 662          if(left) { left.parent = (void *)this; }
 663          channel.Unserialize(right);
 664          if(right) { right.parent = (void *)this; }
 665
 666          // TODO: Precomp errors without extra brackets
 667          depth = ((BTNode)((void *)this)).depthProp;
 668       }
 669       else
 670          this = null;
 671    }
 672 }
 673