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