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