7 extern int __ecereVMethodID_class_OnCompare;
8 extern int __ecereVMethodID_class_OnCopy;
9 extern int __ecereVMethodID_class_OnFree;
12 enum AddSide : int { compare = 0, left = -1, right = 1};
14 public class AVLNode<class T> : IteratorPointer
18 thisclass parent, left, right;
23 property thisclass prev
31 if(parent && this == parent.right)
40 property thisclass next
44 thisclass right = this.right;
49 thisclass parent = this.parent;
50 if(parent && this == parent.left)
59 property thisclass minimum
61 get { while(left) this = left; return this; }
64 property thisclass maximum
66 get { while(right) this = right; return this; }
71 get { return 1 + (left ? left.count : 0) + (right ? right.count : 0); }
73 property int depthProp
77 int leftDepth = left ? (left.depthProp+1) : 0;
78 int rightDepth = right ? (right.depthProp+1) : 0;
79 return Max(leftDepth, rightDepth);
86 if (left) left.Free();
87 if (right) right.Free();
91 bool Add(Class Tclass, thisclass node, AddSide addSide)
94 int (* onCompare)(void *, void *, void *);
96 bool reference = false;
100 Tclass = class(uint64);
102 onCompare = (void *)Tclass._vTbl[__ecereVMethodID_class_OnCompare];
103 if((t == systemClass && !Tclass.byValueSystemClass) || t == bitClass || t == enumClass || t == unitClass || t == structClass)
106 offset = __ENDIAN_PAD((t == structClass) ? sizeof(void *) : Tclass.typeSize);
108 a = reference ? ((byte *)&node.key + offset) : ((byte *)(uintptr)node.key);
117 byte * b = reference ? ((byte *)&key + offset) : (byte *)(uintptr)key;
118 result = onCompare(Tclass, a, b);
147 for(n = this; n; n = n.parent)
149 int newDepth = Max(n.left ? (n.left.depth+1) : 0, n.right ? (n.right.depth+1) : 0);
150 if(newDepth == n.depth)
158 public thisclass Find(Class Tclass, const T key)
161 bool reference = false;
163 ClassType t = Tclass.type;
164 int (* onCompare)(void *, void *, void *) = (void *)Tclass._vTbl[__ecereVMethodID_class_OnCompare];
166 reference = (t == systemClass && !Tclass.byValueSystemClass) || t == bitClass || t == enumClass || t == unitClass;
167 offset = __ENDIAN_PAD(Tclass.typeSize);
168 a = reference ? ((byte *)&(uint64)key) + offset : (byte *)(uintptr)key;
172 offset = __ENDIAN_PAD(sizeof(void *));
177 // *** NEED COMPARISON OPERATOR SUPPORT HERE INVOKING OnCompare, AS WELL AS TYPE INFORMATION PASSED ***
178 byte * b = reference ? ((byte *)&this.key) + offset : (byte *)(uintptr)this.key;
179 int result = onCompare(Tclass, a, b);
190 thisclass FindEx(Class Tclass, const T key, AVLNode */*thisclass **/ addTo, AddSide * addSide)
193 bool reference = false;
195 ClassType t = Tclass.type;
196 int (* onCompare)(void *, void *, void *) = (void *)Tclass._vTbl[__ecereVMethodID_class_OnCompare];
197 bool isInt64 = onCompare == (void *)class(int64).OnCompare;
199 reference = (t == systemClass && !Tclass.byValueSystemClass) || t == bitClass || t == enumClass || t == unitClass;
200 offset = __ENDIAN_PAD(Tclass.typeSize);
201 a = reference ? ((byte *)&(uint64)key) + offset : (byte *)(uintptr)key;
205 offset = __ENDIAN_PAD(sizeof(void *));
208 if(Tclass == class(uint))
210 uint ia = *(uint *)a;
213 uint ib = *(uint *)(reference ? ((byte *)&this.key) + offset : (byte *)(uintptr)this.key);
214 int result = ia > ib ? 1 : ia < ib ? -1 : 0;
217 thisclass node = result < 0 ? left : right;
220 if(addTo) *addTo = this;
221 if(addSide) *addSide = (AddSide)result;
236 byte * b = reference ? ((byte *)&this.key) + offset : (byte *)(uintptr)this.key;
240 int64 b64 = *(int64 *)b;
241 if(a64 > b64) result = 1;
242 else if(a64 < b64) result = -1;
246 result = onCompare(Tclass, a, b);
249 thisclass node = result < 0 ? left : right;
252 if(addTo) *addTo = this;
253 if(addSide) *addSide = (AddSide)result;
264 thisclass FindAll(const T key)
266 AVLNode<T> result = null;
267 // *** FIND ALL COMPARES KEY FOR EQUALITY, NOT USING OnCompare ***
268 if(this.key == key) result = this;
269 if(!result && left) result = left.FindAll(key);
270 if(!result && right) result = right.FindAll(key);
274 void RemoveSwap(thisclass swap)
278 swap.left.parent = swap.parent;
279 if(swap == swap.parent.left)
280 swap.parent.left = swap.left;
281 else if(swap == swap.parent.right)
282 swap.parent.right = swap.left;
287 swap.right.parent = swap.parent;
288 if(swap == swap.parent.left)
289 swap.parent.left = swap.right;
290 else if(swap == swap.parent.right)
291 swap.parent.right = swap.right;
295 if(swap == swap.parent.left) swap.parent.left = null;
296 else if(swap == swap.parent.right) swap.parent.right = null;
300 for(n = swap.parent; n; n = n.parent)
302 int newDepth = Max(n.left ? (n.left.depth+1) : 0, n.right ? (n.right.depth+1) : 0);
303 if(newDepth == n.depth)
318 swap.parent = parent;
323 if(this == parent.left) parent.left = swap;
324 else if(this == parent.right) parent.right = swap;
328 thisclass RemoveSwapLeft()
330 thisclass swap = left ? left.maximum : right;
331 thisclass swapParent = null;
332 if(swap) { swapParent = swap.parent; RemoveSwap(swap); }
335 if(this == parent.left) parent.left = null;
336 else if(this == parent.right) parent.right = null;
340 for(n = swap ? swap : parent; n; n = n.parent)
342 int newDepth = Max(n.left ? (n.left.depth+1) : 0, n.right ? (n.right.depth+1) : 0);
343 if(newDepth == n.depth && n != swap)
348 if(swapParent && swapParent != this)
349 return swapParent.Rebalance();
351 return swap.Rebalance();
353 return parent.Rebalance();
358 thisclass RemoveSwapRight()
361 thisclass swap = right ? right.minimum : left;
362 thisclass swapParent = null;
363 if(swap) { swapParent = swap.parent; RemoveSwap(swap); }
366 if(this == parent.left) parent.left = null;
367 else if(this == parent.right) parent.right = null;
371 for(n = swap ? swap : parent; n; n = n.parent)
373 int newDepth = Max(n.left ? (n.left.depth+1) : 0, n.right ? (n.right.depth+1) : 0);
375 if(newDepth == n.depth && n != swap)
380 if(swapParent && swapParent != this)
381 result = swapParent.Rebalance();
383 result = swap.Rebalance();
385 result = parent.Rebalance();
391 property int balanceFactor
395 int leftDepth = left ? (left.depth+1) : 0;
396 int rightDepth = right ? (right.depth+1) : 0;
397 return rightDepth - leftDepth;
401 thisclass Rebalance()
405 int factor = balanceFactor;
408 if(left.balanceFactor == 1)
415 if(right.balanceFactor == -1)
427 void SingleRotateRight()
431 if(this == parent.left)
433 else if(this == parent.right)
436 left.parent = parent;
439 if(left) left.parent = this;
442 depth = Max(left ? (left.depth+1) : 0, right ? (right.depth+1) : 0);
443 parent.depth = Max(parent.left ? (parent.left.depth+1) : 0, parent.right ? (parent.right.depth+1) : 0);
446 for(n = parent.parent; n; n = n.parent)
448 int newDepth = Max(n.left ? (n.left.depth+1) : 0, n.right ? (n.right.depth+1) : 0);
449 if(newDepth == n.depth)
456 void SingleRotateLeft()
460 if(this == parent.right)
461 parent.right = right;
462 else if(this == parent.left)
465 right.parent = parent;
468 if(right) right.parent = this;
471 depth = Max(left ? (left.depth+1) : 0, right ? (right.depth+1) : 0);
472 parent.depth = Max(parent.left ? (parent.left.depth+1) : 0, parent.right ? (parent.right.depth+1) : 0);
475 for(n = parent.parent; n; n = n.parent)
477 int newDepth = Max(n.left ? (n.left.depth+1) : 0, n.right ? (n.right.depth+1) : 0);
478 if(newDepth == n.depth)
485 void DoubleRotateRight()
487 left.SingleRotateLeft();
491 void DoubleRotateLeft()
493 right.SingleRotateRight();
498 public class CustomAVLTree<class BT:AVLNode<KT>, class KT = uint64> : Container<BT, I = KT>
506 IteratorPointer GetFirst() { return (IteratorPointer) (root ? root.minimum : null); }
507 IteratorPointer GetLast() { return (IteratorPointer) (root ? root.maximum : null); }
508 IteratorPointer GetPrev(IteratorPointer node) { return ((BT)node).prev; }
509 IteratorPointer GetNext(IteratorPointer node) { return ((BT)node).next; }
510 BT GetData(IteratorPointer node) { return (BT)node; }
511 bool SetData(IteratorPointer node, BT data)
513 // Not supported for CustomAVLTree
517 IteratorPointer Add(BT node)
523 Class btClass = class(BT);
524 Class Tclass = btClass.templateArgs[0].dataTypeClass;
527 Tclass = btClass.templateArgs[0].dataTypeClass =
528 eSystem_FindClass(__thisModule.application, btClass.templateArgs[0].dataTypeString);
530 if(root.Add(Tclass, node, 0))
531 root = node.Rebalance();
536 return (IteratorPointer)node;
539 private IteratorPointer AddEx(BT node, BT addNode, AddSide addSide)
545 Class Tclass = class(BT).templateArgs[0].dataTypeClass;
548 Tclass = class(BT).templateArgs[0].dataTypeClass =
549 eSystem_FindClass(__thisModule.application, class(BT).templateArgs[0].dataTypeString);
551 if(addNode.Add(Tclass, node, addSide))
552 root = node.Rebalance();
557 return (IteratorPointer)node;
560 void Remove(IteratorPointer node)
562 BT parent = ((BT)node).parent;
564 if(parent || root == (BT)node)
566 root = ((BT)node).RemoveSwapRight();
568 ((BT)node).parent = null;
572 void Delete(IteratorPointer _item)
575 // THIS SHOULDN'T BE CALLING THE VIRTUAL FUNCTION
576 CustomAVLTree::Remove(_item);
581 void FreeKey(AVLNode<KT> item)
583 if(class(BT).type == structClass)
585 // TODO: Make this easier...
586 Class Tclass = class(BT);
587 ((void (*)(void *, void *))(void *)Tclass._vTbl[__ecereVMethodID_class_OnFree])(Tclass, (((byte *)&item.key) + __ENDIAN_PAD(sizeof(void *))));
607 BT right = item.right;
613 BT parent = item.parent;
623 IteratorPointer Find(BT value)
625 return (IteratorPointer)value;
628 BT GetAtPosition(const KT pos, bool create, bool * justAdded)
630 // TODO: FindEx / AddEx & create nodes if create is true?
631 return root ? root.Find(class(KT), pos) : null;