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       uint64 newKey = (uint64)node.key;
  91       if(!Tclass)
  92          Tclass = class(uint64);
  93       while(true)
  94       {
  95          // *** NEED COMPARISON OPERATOR SUPPORT HERE INVOKING OnCompare, AS WELL AS TYPE INFORMATION PASSED ***
  96          int result = ((int (*)(void *, void *, void *))(void *)Tclass._vTbl[__ecereVMethodID_class_OnCompare])(Tclass,
  97             (Tclass.type == systemClass || Tclass.type == bitClass || Tclass.type == enumClass || Tclass.type == unitClass || Tclass.type == structClass) ? (((byte *)&(uint64)node.key) + __ENDIAN_PAD((Tclass.type == structClass) ? sizeof(void *) : Tclass.typeSize)) : (void *)node.key,
  98             (Tclass.type == systemClass || Tclass.type == bitClass || Tclass.type == enumClass || Tclass.type == unitClass || Tclass.type == structClass) ? (((byte *)&(uint64)key) + __ENDIAN_PAD((Tclass.type == structClass) ? sizeof(void *) : Tclass.typeSize)) : (void *)key);
  99          if(!result)
 100          {
 101             return false;
 102          }
 103          else if(result > 0)
 104          {
 105             if(right)
 106                this = right;
 107             else
 108             {
 109                node.parent = this;
 110                         right = node;
 111                node.depth = 0;
 112                {
 113                   AVLNode<T> n;
 114                   for(n = this; n; n = n.parent)
 115                   {
 116                      int newDepth = Max(n.left ? (n.left.depth+1) : 0, n.right ? (n.right.depth+1) : 0);
 117                      if(newDepth == n.depth)
 118                         break;
 119                      n.depth = newDepth;
 120                   }
 121                }
 122                return true;
 123                 }
 124         }
 125          else
 126          {
 127             if(left)
 128                this = left;
 129             else
 130             {
 131                node.parent = this;
 132                left = node;
 133                node.depth = 0;
 134                {
 135                   AVLNode<T> n;
 136                   for(n = this; n; n = n.parent)
 137                   {
 138                      int newDepth = Max(n.left ? (n.left.depth+1) : 0, n.right ? (n.right.depth+1) : 0);
 139                      if(newDepth == n.depth)
 140                         break;
 141                      n.depth = newDepth;
 142                   }
 143                }
 144                return true;
 145             }
 146         }
 147       }
 148    }
 149
 150    public thisclass Find(Class Tclass, T key)
 151    {
 152       while(this)
 153       {
 154          // *** NEED COMPARISON OPERATOR SUPPORT HERE INVOKING OnCompare, AS WELL AS TYPE INFORMATION PASSED ***
 155          int result = ((int (*)(void *, void *, void *))(void *)Tclass._vTbl[__ecereVMethodID_class_OnCompare])(Tclass,
 156             (Tclass.type == systemClass || Tclass.type == bitClass || Tclass.type == enumClass || Tclass.type == unitClass) ? (((byte *)&(uint64)key) + __ENDIAN_PAD(Tclass.typeSize)) : (void *)key,
 157             (Tclass.type == systemClass || Tclass.type == bitClass || Tclass.type == enumClass || Tclass.type == unitClass || Tclass.type == structClass) ? (((byte *)&(uint64)this.key) + __ENDIAN_PAD((Tclass.type == structClass) ? sizeof(void *) : Tclass.typeSize)) : (void *)this.key);
 158          if(result < 0)
 159             this = left;
 160          else if(result > 0)
 161             this = right;
 162          else
 163             break;
 164       }
 165       return this;
 166    }
 167
 168    thisclass FindAll(T key)
 169    {
 170       AVLNode<T> result = null;
 171       // *** FIND ALL COMPARES KEY FOR EQUALITY, NOT USING OnCompare ***
 172       if(this.key == key) result = this;
 173       if(!result && left) result = left.FindAll(key);
 174       if(!result && right) result = right.FindAll(key);
 175       return result;
 176    }
 177
 178    void RemoveSwap(thisclass swap)
 179    {
 180       if(swap.left)
 181       {
 182          swap.left.parent = swap.parent;
 183          if(swap == swap.parent.left)
 184             swap.parent.left = swap.left;
 185          else if(swap == swap.parent.right)
 186             swap.parent.right = swap.left;
 187          swap.left = null;
 188       }
 189       if(swap.right)
 190       {
 191          swap.right.parent = swap.parent;
 192          if(swap == swap.parent.left)
 193             swap.parent.left = swap.right;
 194          else if(swap == swap.parent.right)
 195             swap.parent.right = swap.right;
 196          swap.right = null;
 197       }
 198
 199       if(swap == swap.parent.left) swap.parent.left = null;
 200       else if(swap == swap.parent.right) swap.parent.right = null;
 201
 202       {
 203          AVLNode<T> n;
 204          for(n = swap.parent; n; n = n.parent)
 205          {
 206             int newDepth = Max(n.left ? (n.left.depth+1) : 0, n.right ? (n.right.depth+1) : 0);
 207             if(newDepth == n.depth)
 208                break;
 209             n.depth = newDepth;
 210             if(n == this) break;
 211          }
 212       }
 213
 214       swap.left = left;
 215       if(left)
 216          left.parent = swap;
 217
 218        swap.right = right;
 219        if (right)
 220             right.parent = swap;
 221
 222       swap.parent = parent;
 223       left = null;
 224       right = null;
 225       if(parent)
 226       {
 227          if(this == parent.left) parent.left = swap;
 228          else if(this == parent.right) parent.right = swap;
 229       }
 230    }
 231
 232    thisclass RemoveSwapLeft()
 233    {
 234       thisclass swap = left ? left.maximum : right;
 235       thisclass swapParent = null;
 236       if(swap) { swapParent = swap.parent; RemoveSwap(swap); }
 237       if(parent)
 238       {
 239          if(this == parent.left) parent.left = null;
 240          else if(this == parent.right) parent.right = null;
 241       }
 242       {
 243          AVLNode<T> n;
 244          for(n = swap ? swap : parent; n; n = n.parent)
 245          {
 246             int newDepth = Max(n.left ? (n.left.depth+1) : 0, n.right ? (n.right.depth+1) : 0);
 247             if(newDepth == n.depth && n != swap)
 248                break;
 249             n.depth = newDepth;
 250          }
 251       }
 252       if(swapParent && swapParent != this)
 253          return swapParent.Rebalance();
 254       else if(swap)
 255          return swap.Rebalance();
 256       else if(parent)
 257          return parent.Rebalance();
 258       else
 259          return null;
 260    }
 261
 262    thisclass RemoveSwapRight()
 263    {
 264       thisclass result;
 265       thisclass swap = right ? right.minimum : left;
 266       thisclass swapParent = null;
 267       if(swap) { swapParent = swap.parent; RemoveSwap(swap); }
 268       if(parent)
 269       {
 270          if(this == parent.left) parent.left = null;
 271          else if(this == parent.right) parent.right = null;
 272       }
 273       {
 274          AVLNode<T> n;
 275          for(n = swap ? swap : parent; n; n = n.parent)
 276          {
 277             int newDepth = Max(n.left ? (n.left.depth+1) : 0, n.right ? (n.right.depth+1) : 0);
 278
 279             if(newDepth == n.depth && n != swap)
 280                break;
 281             n.depth = newDepth;
 282          }
 283       }
 284       if(swapParent && swapParent != this)
 285          result = swapParent.Rebalance();
 286       else if(swap)
 287          result = swap.Rebalance();
 288       else if(parent)
 289          result = parent.Rebalance();
 290       else
 291          result = null;
 292       return result;
 293    }
 294
 295    property int balanceFactor
 296    {
 297       get
 298       {
 299          int leftDepth = left ? (left.depth+1) : 0;
 300          int rightDepth = right ? (right.depth+1) : 0;
 301          return rightDepth - leftDepth;
 302       }
 303    }
 304
 305    thisclass Rebalance()
 306    {
 307       while(true)
 308       {
 309          int factor = balanceFactor;
 310          if (factor < -1)
 311          {
 312             if(left.balanceFactor == 1)
 313                DoubleRotateRight();
 314             else
 315                SingleRotateRight();
 316          }
 317          else if (factor > 1)
 318          {
 319             if(right.balanceFactor == -1)
 320                DoubleRotateLeft();
 321             else
 322                SingleRotateLeft();
 323          }
 324          if(parent)
 325             this = parent;
 326          else
 327             return this;
 328       }
 329    }
 330
 331    void SingleRotateRight()
 332    {
 333       if(parent)
 334       {
 335          if(this == parent.left)
 336             parent.left = left;
 337          else if(this == parent.right)
 338             parent.right = left;
 339       }
 340       left.parent = parent;
 341       parent = left;
 342       left = parent.right;
 343       if(left) left.parent = this;
 344       parent.right = this;
 345
 346       depth = Max(left ? (left.depth+1) : 0, right ? (right.depth+1) : 0);
 347       parent.depth = Max(parent.left ? (parent.left.depth+1) : 0, parent.right ? (parent.right.depth+1) : 0);
 348       {
 349          AVLNode<T> n;
 350          for(n = parent.parent; n; n = n.parent)
 351          {
 352             int newDepth = Max(n.left ? (n.left.depth+1) : 0, n.right ? (n.right.depth+1) : 0);
 353             if(newDepth == n.depth)
 354                break;
 355             n.depth = newDepth;
 356          }
 357       }
 358    }
 359
 360    void SingleRotateLeft()
 361    {
 362       if(parent)
 363       {
 364          if(this == parent.right)
 365             parent.right = right;
 366          else if(this == parent.left)
 367             parent.left = right;
 368       }
 369       right.parent = parent;
 370       parent = right;
 371       right = parent.left;
 372       if(right) right.parent = this;
 373       parent.left = 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 DoubleRotateRight()
 390    {
 391       left.SingleRotateLeft();
 392       SingleRotateRight();
 393    }
 394
 395    void DoubleRotateLeft()
 396    {
 397       right.SingleRotateRight();
 398       SingleRotateLeft();
 399    }
 400 };
 401
 402 public class CustomAVLTree<class BT:AVLNode, class KT = uint64> : Container<BT>
 403 {
 404    class_fixed
 405
 406 public:
 407    BT root;
 408    int count;
 409
 410    IteratorPointer GetFirst() { return (IteratorPointer) (root ? root.minimum : null); }
 411    IteratorPointer GetLast()  { return (IteratorPointer) (root ? root.maximum : null); }
 412    IteratorPointer GetPrev(IteratorPointer node) { return ((BT)node).prev; }
 413    IteratorPointer GetNext(IteratorPointer node) { return ((BT)node).next; }
 414    BT GetData(IteratorPointer node) { return (BT)node; }
 415    bool SetData(IteratorPointer node, BT data)
 416    {
 417       // Not supported for CustomAVLTree
 418       return false;
 419    }
 420
 421    IteratorPointer Add(BT node)
 422    {
 423       if(!root)
 424          root = node;
 425       else
 426       {
 427          Class Tclass = class(BT).templateArgs[0].dataTypeClass;
 428          if(!Tclass)
 429          {
 430             Tclass = class(BT).templateArgs[0].dataTypeClass =
 431                eSystem_FindClass(__thisModule.application, class(BT).templateArgs[0].dataTypeString);
 432          }
 433          if(root.Add(Tclass /*class(BT).templateArgs[0].dataTypeClass*/, node))
 434             root = node.Rebalance();
 435          else
 436             return null;
 437       }
 438       count++;
 439       return (IteratorPointer)node;
 440    }
 441
 442    void Remove(IteratorPointer node)
 443    {
 444       BT parent = ((BT)node).parent;
 445
 446       if(parent || root == (BT)node)
 447       {
 448          root = ((BT)node).RemoveSwapRight();
 449          count--;
 450          ((BT)node).parent = null;
 451       }
 452    }
 453
 454    void Delete(IteratorPointer _item)
 455    {
 456       BT item = (BT)_item;
 457       // THIS SHOULDN'T BE CALLING THE VIRTUAL FUNCTION
 458       CustomAVLTree::Remove(_item);
 459       delete item;
 460    }
 461
 462    void Free()
 463    {
 464       BT item;
 465       while(item = root)
 466       {
 467          // THIS SHOULDN'T BE CALLING THE VIRTUAL FUNCTION
 468          CustomAVLTree::Remove(item);
 469          delete item;
 470       }
 471    }
 472
 473    IteratorPointer Find(BT value)
 474    {
 475       return (IteratorPointer)value;
 476    }
 477 }