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