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

   1 namespace com;
   2
   3 import "Container"
   4
   5 default:
   6
   7 extern int __ecereVMethodID_class_OnCompare;
   8 extern int __ecereVMethodID_class_OnCopy;
   9 private:
  10
  11 enum AddSide : int { compare = 0, left = -1, right = 1};
  12
  13 public class AVLNode<class T> : IteratorPointer
  14 {
  15    class_fixed
  16
  17    thisclass parent, left, right;
  18    int depth;
  19 public:
  20    T key;
  21
  22    property thisclass prev
  23    {
  24       get
  25       {
  26          if(left)
  27             return left.maximum;
  28          while(this)
  29          {
  30             if(parent && this == parent.right)
  31                return parent;
  32             else
  33                this = parent;
  34          }
  35          return this;
  36       }
  37    }
  38
  39    property thisclass next
  40    {
  41       get
  42       {
  43          thisclass right = this.right;
  44          if(right)
  45             return right.minimum;
  46          while(this)
  47          {
  48             thisclass parent = this.parent;
  49             if(parent && this == parent.left)
  50                return parent;
  51             else
  52                this = parent;
  53          }
  54          return null;
  55       }
  56    }
  57
  58    property thisclass minimum
  59    {
  60       get { while(left) this = left; return this; }
  61    }
  62
  63    property thisclass maximum
  64    {
  65       get { while(right) this = right; return this; }
  66    }
  67
  68    property int count
  69    {
  70       get { return 1 + (left ? left.count : 0) + (right ? right.count : 0); }
  71    }
  72    property int depthProp
  73    {
  74       get
  75       {
  76          int leftDepth = left ? (left.depthProp+1) : 0;
  77          int rightDepth = right ? (right.depthProp+1) : 0;
  78          return Max(leftDepth, rightDepth);
  79       }
  80    }
  81 private:
  82
  83    void Free()
  84    {
  85         if (left) left.Free();
  86         if (right) right.Free();
  87       delete this;
  88    }
  89
  90    bool Add(Class Tclass, thisclass node, AddSide addSide)
  91    {
  92       ClassType t;
  93       int (* onCompare)(void *, void *, void *);
  94       uint offset = 0;
  95       bool reference = false;
  96       byte * a;
  97
  98       if(!Tclass)
  99          Tclass = class(uint64);
 100       t = Tclass.type;
 101       onCompare = (void *)Tclass._vTbl[__ecereVMethodID_class_OnCompare];
 102       if((t == systemClass && !Tclass.byValueSystemClass) || t == bitClass || t == enumClass || t == unitClass || t == structClass)
 103       {
 104          reference = true;
 105          offset = __ENDIAN_PAD((t == structClass) ? sizeof(void *) : Tclass.typeSize);
 106       }
 107       a = reference ? ((byte *)&node.key + offset) : ((byte *)(uintptr)node.key);
 108
 109       while(true)
 110       {
 111          int result;
 112          if(addSide)
 113             result = addSide;
 114          else
 115          {
 116             byte * b = reference ? ((byte *)&key + offset) : (byte *)(uintptr)key;
 117             result = onCompare(Tclass, a, b);
 118          }
 119          if(!result)
 120             return false;
 121          else if(result > 0)
 122          {
 123             if(right)
 124                this = right;
 125             else
 126             {
 127                         right = node;
 128                break;
 129                 }
 130         }
 131          else
 132          {
 133             if(left)
 134                this = left;
 135             else
 136             {
 137                left = node;
 138                break;
 139             }
 140         }
 141       }
 142       node.parent = this;
 143       node.depth = 0;
 144       {
 145          AVLNode<T> n;
 146          for(n = this; n; n = n.parent)
 147          {
 148             int newDepth = Max(n.left ? (n.left.depth+1) : 0, n.right ? (n.right.depth+1) : 0);
 149             if(newDepth == n.depth)
 150                break;
 151             n.depth = newDepth;
 152          }
 153       }
 154       return true;
 155    }
 156
 157    public thisclass Find(Class Tclass, const T key)
 158    {
 159       byte * a;
 160       bool reference = false;
 161       uint offset = 0;
 162       ClassType t = Tclass.type;
 163       int (* onCompare)(void *, void *, void *) = (void *)Tclass._vTbl[__ecereVMethodID_class_OnCompare];
 164
 165       reference = (t == systemClass && !Tclass.byValueSystemClass) || t == bitClass || t == enumClass || t == unitClass;
 166       offset = __ENDIAN_PAD(Tclass.typeSize);
 167       a = reference ? ((byte *)&(uint64)key) + offset : (byte *)(uintptr)key;
 168       if(t == structClass)
 169       {
 170          reference = true;
 171          offset = __ENDIAN_PAD(sizeof(void *));
 172       }
 173
 174       while(this)
 175       {
 176          // *** NEED COMPARISON OPERATOR SUPPORT HERE INVOKING OnCompare, AS WELL AS TYPE INFORMATION PASSED ***
 177          byte * b = reference ? ((byte *)&this.key) + offset : (byte *)(uintptr)this.key;
 178          int result = onCompare(Tclass, a, b);
 179          if(result < 0)
 180             this = left;
 181          else if(result > 0)
 182             this = right;
 183          else
 184             break;
 185       }
 186       return this;
 187    }
 188
 189    thisclass FindEx(Class Tclass, const T key, AVLNode */*thisclass **/ addTo, AddSide * addSide)
 190    {
 191       byte * a;
 192       bool reference = false;
 193       uint offset = 0;
 194       ClassType t = Tclass.type;
 195       int (* onCompare)(void *, void *, void *) = (void *)Tclass._vTbl[__ecereVMethodID_class_OnCompare];
 196
 197       reference = (t == systemClass && !Tclass.byValueSystemClass) || t == bitClass || t == enumClass || t == unitClass;
 198       offset = __ENDIAN_PAD(Tclass.typeSize);
 199       a = reference ? ((byte *)&(uint64)key) + offset : (byte *)(uintptr)key;
 200       if(t == structClass)
 201       {
 202          reference = true;
 203          offset = __ENDIAN_PAD(sizeof(void *));
 204       }
 205
 206       if(Tclass == class(uint))
 207       {
 208          uint ia = *(uint *)a;
 209          while(this)
 210          {
 211             uint ib = *(uint *)(reference ? ((byte *)&this.key) + offset : (byte *)(uintptr)this.key);
 212             int result = ia > ib ? 1 : ia < ib ? -1 : 0;
 213             if(result)
 214             {
 215                thisclass node = result < 0 ? left : right;
 216                if(!node)
 217                {
 218                   if(addTo) *addTo = this;
 219                   if(addSide) *addSide = (AddSide)result;
 220                }
 221                this = node;
 222             }
 223             else
 224                break;
 225          }
 226       }
 227       else
 228       {
 229          while(this)
 230          {
 231             byte * b = reference ? ((byte *)&this.key) + offset : (byte *)(uintptr)this.key;
 232             int result = onCompare(Tclass, a, b);
 233             if(result)
 234             {
 235                thisclass node = result < 0 ? left : right;
 236                if(!node)
 237                {
 238                   if(addTo) *addTo = this;
 239                   if(addSide) *addSide = (AddSide)result;
 240                }
 241                this = node;
 242             }
 243             else
 244                break;
 245          }
 246       }
 247       return this;
 248    }
 249
 250    thisclass FindAll(const T key)
 251    {
 252       AVLNode<T> result = null;
 253       // *** FIND ALL COMPARES KEY FOR EQUALITY, NOT USING OnCompare ***
 254       if(this.key == key) result = this;
 255       if(!result && left) result = left.FindAll(key);
 256       if(!result && right) result = right.FindAll(key);
 257       return result;
 258    }
 259
 260    void RemoveSwap(thisclass swap)
 261    {
 262       if(swap.left)
 263       {
 264          swap.left.parent = swap.parent;
 265          if(swap == swap.parent.left)
 266             swap.parent.left = swap.left;
 267          else if(swap == swap.parent.right)
 268             swap.parent.right = swap.left;
 269          swap.left = null;
 270       }
 271       if(swap.right)
 272       {
 273          swap.right.parent = swap.parent;
 274          if(swap == swap.parent.left)
 275             swap.parent.left = swap.right;
 276          else if(swap == swap.parent.right)
 277             swap.parent.right = swap.right;
 278          swap.right = null;
 279       }
 280
 281       if(swap == swap.parent.left) swap.parent.left = null;
 282       else if(swap == swap.parent.right) swap.parent.right = null;
 283
 284       {
 285          AVLNode<T> n;
 286          for(n = swap.parent; n; n = n.parent)
 287          {
 288             int newDepth = Max(n.left ? (n.left.depth+1) : 0, n.right ? (n.right.depth+1) : 0);
 289             if(newDepth == n.depth)
 290                break;
 291             n.depth = newDepth;
 292             if(n == this) break;
 293          }
 294       }
 295
 296       swap.left = left;
 297       if(left)
 298          left.parent = swap;
 299
 300        swap.right = right;
 301        if (right)
 302             right.parent = swap;
 303
 304       swap.parent = parent;
 305       left = null;
 306       right = null;
 307       if(parent)
 308       {
 309          if(this == parent.left) parent.left = swap;
 310          else if(this == parent.right) parent.right = swap;
 311       }
 312    }
 313
 314    thisclass RemoveSwapLeft()
 315    {
 316       thisclass swap = left ? left.maximum : right;
 317       thisclass swapParent = null;
 318       if(swap) { swapParent = swap.parent; RemoveSwap(swap); }
 319       if(parent)
 320       {
 321          if(this == parent.left) parent.left = null;
 322          else if(this == parent.right) parent.right = null;
 323       }
 324       {
 325          AVLNode<T> n;
 326          for(n = swap ? swap : parent; n; n = n.parent)
 327          {
 328             int newDepth = Max(n.left ? (n.left.depth+1) : 0, n.right ? (n.right.depth+1) : 0);
 329             if(newDepth == n.depth && n != swap)
 330                break;
 331             n.depth = newDepth;
 332          }
 333       }
 334       if(swapParent && swapParent != this)
 335          return swapParent.Rebalance();
 336       else if(swap)
 337          return swap.Rebalance();
 338       else if(parent)
 339          return parent.Rebalance();
 340       else
 341          return null;
 342    }
 343
 344    thisclass RemoveSwapRight()
 345    {
 346       thisclass result;
 347       thisclass swap = right ? right.minimum : left;
 348       thisclass swapParent = null;
 349       if(swap) { swapParent = swap.parent; RemoveSwap(swap); }
 350       if(parent)
 351       {
 352          if(this == parent.left) parent.left = null;
 353          else if(this == parent.right) parent.right = null;
 354       }
 355       {
 356          AVLNode<T> n;
 357          for(n = swap ? swap : parent; n; n = n.parent)
 358          {
 359             int newDepth = Max(n.left ? (n.left.depth+1) : 0, n.right ? (n.right.depth+1) : 0);
 360
 361             if(newDepth == n.depth && n != swap)
 362                break;
 363             n.depth = newDepth;
 364          }
 365       }
 366       if(swapParent && swapParent != this)
 367          result = swapParent.Rebalance();
 368       else if(swap)
 369          result = swap.Rebalance();
 370       else if(parent)
 371          result = parent.Rebalance();
 372       else
 373          result = null;
 374       return result;
 375    }
 376
 377    property int balanceFactor
 378    {
 379       get
 380       {
 381          int leftDepth = left ? (left.depth+1) : 0;
 382          int rightDepth = right ? (right.depth+1) : 0;
 383          return rightDepth - leftDepth;
 384       }
 385    }
 386
 387    thisclass Rebalance()
 388    {
 389       while(true)
 390       {
 391          int factor = balanceFactor;
 392          if (factor < -1)
 393          {
 394             if(left.balanceFactor == 1)
 395                DoubleRotateRight();
 396             else
 397                SingleRotateRight();
 398          }
 399          else if (factor > 1)
 400          {
 401             if(right.balanceFactor == -1)
 402                DoubleRotateLeft();
 403             else
 404                SingleRotateLeft();
 405          }
 406          if(parent)
 407             this = parent;
 408          else
 409             return this;
 410       }
 411    }
 412
 413    void SingleRotateRight()
 414    {
 415       if(parent)
 416       {
 417          if(this == parent.left)
 418             parent.left = left;
 419          else if(this == parent.right)
 420             parent.right = left;
 421       }
 422       left.parent = parent;
 423       parent = left;
 424       left = parent.right;
 425       if(left) left.parent = this;
 426       parent.right = this;
 427
 428       depth = Max(left ? (left.depth+1) : 0, right ? (right.depth+1) : 0);
 429       parent.depth = Max(parent.left ? (parent.left.depth+1) : 0, parent.right ? (parent.right.depth+1) : 0);
 430       {
 431          AVLNode<T> n;
 432          for(n = parent.parent; n; n = n.parent)
 433          {
 434             int newDepth = Max(n.left ? (n.left.depth+1) : 0, n.right ? (n.right.depth+1) : 0);
 435             if(newDepth == n.depth)
 436                break;
 437             n.depth = newDepth;
 438          }
 439       }
 440    }
 441
 442    void SingleRotateLeft()
 443    {
 444       if(parent)
 445       {
 446          if(this == parent.right)
 447             parent.right = right;
 448          else if(this == parent.left)
 449             parent.left = right;
 450       }
 451       right.parent = parent;
 452       parent = right;
 453       right = parent.left;
 454       if(right) right.parent = this;
 455       parent.left = this;
 456
 457       depth = Max(left ? (left.depth+1) : 0, right ? (right.depth+1) : 0);
 458       parent.depth = Max(parent.left ? (parent.left.depth+1) : 0, parent.right ? (parent.right.depth+1) : 0);
 459       {
 460          AVLNode<T> n;
 461          for(n = parent.parent; n; n = n.parent)
 462          {
 463             int newDepth = Max(n.left ? (n.left.depth+1) : 0, n.right ? (n.right.depth+1) : 0);
 464             if(newDepth == n.depth)
 465                break;
 466             n.depth = newDepth;
 467          }
 468       }
 469    }
 470
 471    void DoubleRotateRight()
 472    {
 473       left.SingleRotateLeft();
 474       SingleRotateRight();
 475    }
 476
 477    void DoubleRotateLeft()
 478    {
 479       right.SingleRotateRight();
 480       SingleRotateLeft();
 481    }
 482 }
 483
 484 public class CustomAVLTree<class BT:AVLNode, class KT = uint64> : Container<BT, I = KT>
 485 {
 486    class_fixed
 487
 488 public:
 489    BT root;
 490    int count;
 491
 492    IteratorPointer GetFirst() { return (IteratorPointer) (root ? root.minimum : null); }
 493    IteratorPointer GetLast()  { return (IteratorPointer) (root ? root.maximum : null); }
 494    IteratorPointer GetPrev(IteratorPointer node) { return ((BT)node).prev; }
 495    IteratorPointer GetNext(IteratorPointer node) { return ((BT)node).next; }
 496    BT GetData(IteratorPointer node) { return (BT)node; }
 497    bool SetData(IteratorPointer node, BT data)
 498    {
 499       // Not supported for CustomAVLTree
 500       return false;
 501    }
 502
 503    IteratorPointer Add(BT node)
 504    {
 505       if(!root)
 506          root = node;
 507       else
 508       {
 509          Class Tclass = class(BT).templateArgs[0].dataTypeClass;
 510          if(!Tclass)
 511          {
 512             Tclass = class(BT).templateArgs[0].dataTypeClass =
 513                eSystem_FindClass(__thisModule.application, class(BT).templateArgs[0].dataTypeString);
 514          }
 515          if(root.Add(Tclass, node, 0))
 516             root = node.Rebalance();
 517          else
 518             return null;
 519       }
 520       count++;
 521       return (IteratorPointer)node;
 522    }
 523
 524    private IteratorPointer AddEx(BT node, BT addNode, AddSide addSide)
 525    {
 526       if(!root)
 527          root = node;
 528       else
 529       {
 530          Class Tclass = class(BT).templateArgs[0].dataTypeClass;
 531          if(!Tclass)
 532          {
 533             Tclass = class(BT).templateArgs[0].dataTypeClass =
 534                eSystem_FindClass(__thisModule.application, class(BT).templateArgs[0].dataTypeString);
 535          }
 536          if(addNode.Add(Tclass, node, addSide))
 537             root = node.Rebalance();
 538          else
 539             return null;
 540       }
 541       count++;
 542       return (IteratorPointer)node;
 543    }
 544
 545    void Remove(IteratorPointer node)
 546    {
 547       BT parent = ((BT)node).parent;
 548
 549       if(parent || root == (BT)node)
 550       {
 551          root = ((BT)node).RemoveSwapRight();
 552          count--;
 553          ((BT)node).parent = null;
 554       }
 555    }
 556
 557    void Delete(IteratorPointer _item)
 558    {
 559       BT item = (BT)_item;
 560       // THIS SHOULDN'T BE CALLING THE VIRTUAL FUNCTION
 561       CustomAVLTree::Remove(_item);
 562       delete item;
 563    }
 564
 565    void Free()
 566    {
 567       BT item;
 568       item = root;
 569       while(item)
 570       {
 571          if(item.left)
 572          {
 573             BT left = item.left;
 574             item.left = null;
 575             item = left;
 576          }
 577          else if(item.right)
 578          {
 579             BT right = item.right;
 580             item.right = null;
 581             item = right;
 582          }
 583          else
 584          {
 585             BT parent = item.parent;
 586             delete item;
 587             item = parent;
 588          }
 589       }
 590       root = null;
 591       count = 0;
 592    }
 593
 594    IteratorPointer Find(BT value)
 595    {
 596       return (IteratorPointer)value;
 597    }
 598
 599    BT GetAtPosition(const KT pos, bool create, bool * justAdded)
 600    {
 601       // TODO: FindEx / AddEx & create nodes if create is true?
 602       return root ? root.Find(class(KT), pos) : null;
 603    }
 604 }