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