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    public BTNode FindPrefix(char * key)
 243    {
 244       BTNode subString = null;
 245       int len = key ? strlen(key) : 0;
 246       while(this)
 247       {
 248          int result;
 249          if(key && this.key)
 250             result = strcmp(key, (char *)this.key);
 251          else if(key && !this.key)
 252             result = 1;
 253          else if(!key && this.key)
 254             result = -1;
 255          else
 256             result = 0;
 257
 258          if(result < 0)
 259          {
 260             if(!strncmp(key, (char *)this.key, len))
 261                subString = this;
 262             this = left;
 263          }
 264          else if(result > 0)
 265             this = right;
 266          else
 267          {
 268             subString = this;
 269             break;
 270          }
 271       }
 272       return subString;
 273    }
 274
 275    BTNode FindAll(uint key)
 276    {
 277       BTNode result = null;
 278       if(this.key == key) result = this;
 279       if(!result && left) result = left.FindAll(key);
 280       if(!result && right) result = right.FindAll(key);
 281       return result;
 282    }
 283
 284    void RemoveSwap(BTNode swap)
 285    {
 286       if(swap.left)
 287       {
 288          swap.left.parent = swap.parent;
 289          if(swap == swap.parent.left)
 290             swap.parent.left = swap.left;
 291          else if(swap == swap.parent.right)
 292             swap.parent.right = swap.left;
 293          swap.left = null;
 294       }
 295       if(swap.right)
 296       {
 297          swap.right.parent = swap.parent;
 298          if(swap == swap.parent.left)
 299             swap.parent.left = swap.right;
 300          else if(swap == swap.parent.right)
 301             swap.parent.right = swap.right;
 302          swap.right = null;
 303       }
 304
 305       if(swap == swap.parent.left) swap.parent.left = null;
 306       else if(swap == swap.parent.right) swap.parent.right = null;
 307
 308       {
 309          BTNode n;
 310          for(n = swap.parent; n; n = n.parent)
 311          {
 312             int newDepth = Max(n.left ? (n.left.depth+1) : 0, n.right ? (n.right.depth+1) : 0);
 313             if(newDepth == n.depth)
 314                break;
 315             n.depth = newDepth;
 316             if(n == this) break;
 317          }
 318       }
 319
 320       //if(!swap.left)
 321       {
 322          swap.left = left;
 323          if(left)
 324             left.parent = swap;
 325       }
 326       //if(!swap.right)
 327       {
 328           swap.right = right;
 329           if (right)
 330                right.parent = swap;
 331       }
 332       swap.parent = parent;
 333       left = null;
 334       right = null;
 335       if(parent)
 336       {
 337          if(this == parent.left) parent.left = swap;
 338          else if(this == parent.right) parent.right = swap;
 339       }
 340    }
 341
 342    BTNode RemoveSwapLeft()
 343    {
 344       BTNode swap = left ? left.maximum : right;
 345       BTNode swapParent = null;
 346       if(swap) { swapParent = swap.parent; RemoveSwap(swap); }
 347       if(parent)
 348       {
 349          if(this == parent.left) parent.left = null;
 350          else if(this == parent.right) parent.right = null;
 351       }
 352       {
 353          BTNode n;
 354          for(n = swap ? swap : parent; n; n = n.parent)
 355          {
 356             int newDepth = Max(n.left ? (n.left.depth+1) : 0, n.right ? (n.right.depth+1) : 0);
 357             if(newDepth == n.depth && n != swap)
 358                break;
 359             n.depth = newDepth;
 360          }
 361       }
 362       if(swapParent && swapParent != this)
 363          return swapParent.Rebalance();
 364       else if(swap)
 365          return swap.Rebalance();
 366       else if(parent)
 367          return parent.Rebalance();
 368       else
 369          return null;
 370    }
 371
 372    BTNode RemoveSwapRight()
 373    {
 374       BTNode result;
 375       BTNode swap = right ? right.minimum : left;
 376       BTNode swapParent = null;
 377       if(swap) { swapParent = swap.parent; RemoveSwap(swap); }
 378       if(parent)
 379       {
 380          if(this == parent.left) parent.left = null;
 381          else if(this == parent.right) parent.right = null;
 382       }
 383       {
 384          BTNode n;
 385          for(n = swap ? swap : parent; n; n = n.parent)
 386          {
 387             int newDepth = Max(n.left ? (n.left.depth+1) : 0, n.right ? (n.right.depth+1) : 0);
 388             /*
 389             if(newDepth != n.depthProp)
 390                printf("bug");
 391             */
 392             if(newDepth == n.depth && n != swap)
 393                break;
 394             n.depth = newDepth;
 395          }
 396       }
 397       if(swapParent && swapParent != this)
 398          result = swapParent.Rebalance();
 399       else if(swap)
 400          result = swap.Rebalance();
 401       else if(parent)
 402          result = parent.Rebalance();
 403       else
 404          result = null;
 405       return result;
 406    }
 407
 408    property int balanceFactor
 409    {
 410       get
 411       {
 412          int leftDepth = left ? (left.depth+1) : 0;
 413          int rightDepth = right ? (right.depth+1) : 0;
 414          return rightDepth - leftDepth;
 415       }
 416    }
 417
 418    BTNode Rebalance()
 419    {
 420       while(true)
 421       {
 422          int factor = balanceFactor;
 423          if (factor < -1)
 424          {
 425             if(left.balanceFactor == 1)
 426                DoubleRotateRight();
 427             else
 428                SingleRotateRight();
 429          }
 430          else if (factor > 1)
 431          {
 432             if(right.balanceFactor == -1)
 433                DoubleRotateLeft();
 434             else
 435                SingleRotateLeft();
 436          }
 437          if(parent)
 438             this = parent;
 439          else
 440             return this;
 441       }
 442    }
 443
 444    void SingleRotateRight()
 445    {
 446       if(parent)
 447       {
 448          if(this == parent.left)
 449             parent.left = left;
 450          else if(this == parent.right)
 451             parent.right = left;
 452       }
 453       left.parent = parent;
 454       parent = left;
 455       left = parent.right;
 456       if(left) left.parent = this;
 457       parent.right = 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 SingleRotateLeft()
 478    {
 479       if(parent)
 480       {
 481          if(this == parent.right)
 482             parent.right = right;
 483          else if(this == parent.left)
 484             parent.left = right;
 485       }
 486       right.parent = parent;
 487       parent = right;
 488       right = parent.left;
 489       if(right) right.parent = this;
 490       parent.left = this;
 491
 492       depth = Max(left ? (left.depth+1) : 0, right ? (right.depth+1) : 0);
 493       parent.depth = Max(parent.left ? (parent.left.depth+1) : 0, parent.right ? (parent.right.depth+1) : 0);
 494       {
 495          BTNode n;
 496          for(n = parent.parent; n; n = n.parent)
 497          {
 498             int newDepth = Max(n.left ? (n.left.depth+1) : 0, n.right ? (n.right.depth+1) : 0);
 499             /*
 500             if(newDepth != n.depthProp)
 501                printf("bug");
 502             */
 503             if(newDepth == n.depth)
 504                break;
 505             n.depth = newDepth;
 506          }
 507       }
 508    }
 509
 510    void DoubleRotateRight()
 511    {
 512       left.SingleRotateLeft();
 513       SingleRotateRight();
 514    }
 515
 516    void DoubleRotateLeft()
 517    {
 518       right.SingleRotateRight();
 519       SingleRotateLeft();
 520    }
 521
 522    #define NUMSIZE   4
 523
 524    char * Print(char * output, TreePrintStyle tps)
 525    {
 526       switch(tps)
 527       {
 528          case inOrder:
 529          case preOrder:
 530          case postOrder:
 531          {
 532             if(tps == preOrder) strcatf(output, "%d ", key);
 533
 534                 if (left) left.Print(output, tps);
 535
 536             if(tps == inOrder) strcatf(output, "%d ", key);
 537
 538                 if (right) right.Print(output, tps);
 539
 540             if(tps == postOrder) strcatf(output, "%d ", key);
 541
 542                 return output;
 543          }
 544          case depthOrder:
 545          {
 546             int maxDepth = depth;
 547             int curDepth;
 548
 549             for(curDepth = 0; curDepth <= maxDepth; curDepth++)
 550             {
 551                int c;
 552                for(c = 0; c<((1<<(maxDepth - curDepth))-1) * NUMSIZE / 2; c++)
 553                   strcat(output, " ");
 554                PrintDepth(output, curDepth, 0, maxDepth, true);
 555                strcat(output, "\n");
 556             }
 557             return output;
 558          }
 559       }
 560       return null;
 561    }
 562
 563    void PrintDepth(char * output, int wantedDepth, int curDepth, int maxDepth, bool last)
 564    {
 565       int c;
 566       if(wantedDepth == curDepth)
 567       {
 568          char nodeString[10] = "";
 569          int len;
 570
 571          if(this)
 572             sprintf(nodeString, "%d", key);
 573
 574          len = strlen(nodeString);
 575          for(c = 0; c<(NUMSIZE - len)/2; c++)
 576             strcat(output, " ");
 577          len += c;
 578          strcat(output, nodeString);
 579          for(c = len; c<NUMSIZE; c++)
 580             strcat(output, " ");
 581
 582          if(curDepth && !last)
 583          {
 584             for(c = 0; c<((1<<(maxDepth-curDepth)) - 1) * NUMSIZE; c++)
 585                strcat(output, " ");
 586          }
 587       }
 588       else if(curDepth <= maxDepth)
 589       {
 590          (this ? left : (BTNode)null).PrintDepth(output, wantedDepth, curDepth+1, maxDepth, last && this && !right);
 591          (this ? right : (BTNode)null).PrintDepth(output, wantedDepth, curDepth+1, maxDepth, last);
 592       }
 593    }
 594
 595    bool Check(BinaryTree tree)
 596    {
 597       bool valid = true;
 598       // Now get the height of each subtree
 599       int leftHeight  = left  ? left.depthProp+1  : 0;
 600       int rightHeight = right ? right.depthProp+1 : 0;
 601
 602       // Verify that AVL tree property is satisfied
 603       int diffHeight = rightHeight - leftHeight;
 604
 605       if(left)
 606       {
 607          if(left.parent != this)
 608          {
 609             printf("Parent not set properly at node %d\n", left.key);
 610             valid = false;
 611          }
 612          valid *= left.Check(tree);
 613       }
 614       if(right)
 615       {
 616          if(right.parent != this)
 617          {
 618             printf("Parent not set properly at node %d\n", right.key);
 619             valid = false;
 620          }
 621          valid *= right.Check(tree);
 622       }
 623
 624       if(depth != depthProp)
 625       {
 626          printf("Depth value at node %d (%d) doesn't match depth property (%d)\n", key, depth, depthProp);
 627          valid = 0;
 628       }
 629
 630       if (diffHeight < -1 || diffHeight > 1)
 631       {
 632          valid = 0;
 633          printf("Height difference is %d at node %d\n", diffHeight, key);
 634       }
 635
 636       // Verify that balance-factor is correct
 637       if (diffHeight != balanceFactor)
 638       {
 639          valid = 0;
 640          printf("Height difference %d doesnt match balance-factor of %d at node \n", diffHeight, balanceFactor, key);
 641       }
 642
 643       // Verify that search-tree property is satisfied
 644       if (left && tree.CompareKey(tree, left.key, key) > 0)
 645       {
 646          valid = false;
 647          printf("Node %d is *smaller* than left subtree %d\n", key, left.key);
 648       }
 649       if (right && tree.CompareKey(tree, right.key, key) < 0)
 650       {
 651          valid = false;
 652          printf("Node %d is *greater* than right subtree %d\n", key, right.key);
 653       }
 654       return valid;
 655    }
 656 };
 657
 658 // TODO: WHY CAN'T WE HAVE THIS ABOVE?
 659
 660 public class StringBTNode : struct // BTNode
 661 {
 662    class_fixed
 663 public:
 664    String key;
 665    StringBTNode parent, left, right;
 666    int depth;
 667
 668    void OnSerialize(IOChannel channel)
 669    {
 670       if(this)
 671       {
 672          bool truth = true;
 673          channel.Serialize(truth);
 674          channel.Serialize(key);
 675          channel.Serialize(left);
 676          channel.Serialize(right);
 677       }
 678       else
 679       {
 680          uint nothing = 0;
 681          channel.Serialize(nothing);
 682       }
 683    }
 684
 685    void OnUnserialize(IOChannel channel)
 686    {
 687       bool truth;
 688       channel.Unserialize(truth);
 689       if(truth)
 690       {
 691          // TODO: Fix typed_object issues
 692          this = eInstance_New(class(StringBTNode));
 693          channel.Unserialize(key);
 694          channel.Unserialize(left);
 695          if(left) { left.parent = (void *)this; }
 696          channel.Unserialize(right);
 697          if(right) { right.parent = (void *)this; }
 698
 699          // TODO: Precomp errors without extra brackets
 700          depth = ((BTNode)((void *)this)).depthProp;
 701       }
 702       else
 703          this = null;
 704    }
 705 }
 706