1 /*
2 * Copyright 2001 Adrian Thurston <thurston@complang.org>
3 */
4
5 /* This file is part of Aapl.
6 *
7 * Aapl is free software; you can redistribute it and/or modify it under the
8 * terms of the GNU Lesser General Public License as published by the Free
9 * Software Foundation; either version 2.1 of the License, or (at your option)
10 * any later version.
11 *
12 * Aapl is distributed in the hope that it will be useful, but WITHOUT ANY
13 * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
14 * FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for
15 * more details.
16 *
17 * You should have received a copy of the GNU Lesser General Public License
18 * along with Aapl; if not, write to the Free Software Foundation, Inc., 59
19 * Temple Place, Suite 330, Boston, MA 02111-1307 USA
20 */
21
22 /* This header is not wrapped in ifndef becuase it is not intended to
23 * be included by the user. */
24
25 #include <assert.h>
26
27 #ifdef AAPL_NAMESPACE
28 namespace Aapl {
29 #endif
30
31 #ifdef WALKABLE
32 /* This is used by AvlTree, AvlMel and AvlMelKey so it
33 * must be protected by global ifdefs. */
34 #ifndef __AAPL_AVLI_EL__
35 #define __AAPL_AVLI_EL__
36
37 /**
38 * \brief Tree element properties for linked AVL trees.
39 *
40 * AvliTreeEl needs to be inherited by classes that intend to be element in an
41 * AvliTree.
42 */
43 template<class SubClassEl> struct AvliTreeEl
44 {
45 /**
46 * \brief Tree pointers connecting element in a tree.
47 */
48 SubClassEl *left, *right, *parent;
49
50 /**
51 * \brief Linked list pointers.
52 */
53 SubClassEl *prev, *next;
54
55 /**
56 * \brief Height of the tree rooted at this element.
57 *
58 * Height is required by the AVL balancing algorithm.
59 */
60 long height;
61 };
62 #endif /* __AAPL_AVLI_EL__ */
63
64 #else /* not WALKABLE */
65
66 /* This is used by All the non walkable trees so it must be
67 * protected by a global ifdef. */
68 #ifndef __AAPL_AVL_EL__
69 #define __AAPL_AVL_EL__
70 /**
71 * \brief Tree element properties for linked AVL trees.
72 *
73 * AvlTreeEl needs to be inherited by classes that intend to be element in an
74 * AvlTree.
75 */
76 template<class SubClassEl> struct AvlTreeEl
77 {
78 /**
79 * \brief Tree pointers connecting element in a tree.
80 */
81 SubClassEl *left, *right, *parent;
82
83 /**
84 * \brief Height of the tree rooted at this element.
85 *
86 * Height is required by the AVL balancing algorithm.
87 */
88 long height;
89 };
90 #endif /* __AAPL_AVL_EL__ */
91 #endif /* def WALKABLE */
92
93
94 #if defined( AVLTREE_MAP )
95
96 #ifdef WALKABLE
97
98 /**
99 * \brief Tree element for AvliMap
100 *
101 * Stores the key and value pair.
102 */
103 template <class Key, class Value> struct AvliMapEl :
104 public AvliTreeEl< AvliMapEl<Key, Value> >
105 {
AvliMapElAvliMapEl106 AvliMapEl(const Key &key)
107 : key(key) { }
AvliMapElAvliMapEl108 AvliMapEl(const Key &key, const Value &value)
109 : key(key), value(value) { }
110
getKeyAvliMapEl111 const Key &getKey() const { return key; }
112
113 /** \brief The key. */
114 Key key;
115
116 /** \brief The value. */
117 Value value;
118 };
119 #else /* not WALKABLE */
120
121 /**
122 * \brief Tree element for AvlMap
123 *
124 * Stores the key and value pair.
125 */
126 template <class Key, class Value> struct AvlMapEl :
127 public AvlTreeEl< AvlMapEl<Key, Value> >
128 {
AvlMapElAvlMapEl129 AvlMapEl(const Key &key)
130 : key(key) { }
AvlMapElAvlMapEl131 AvlMapEl(const Key &key, const Value &value)
132 : key(key), value(value) { }
133
getKeyAvlMapEl134 const Key &getKey() const { return key; }
135
136 /** \brief The key. */
137 Key key;
138
139 /** \brief The value. */
140 Value value;
141 };
142 #endif /* def WALKABLE */
143
144 #elif defined( AVLTREE_SET )
145
146 #ifdef WALKABLE
147 /**
148 * \brief Tree element for AvliSet
149 *
150 * Stores the key.
151 */
152 template <class Key> struct AvliSetEl :
153 public AvliTreeEl< AvliSetEl<Key> >
154 {
AvliSetElAvliSetEl155 AvliSetEl(const Key &key) : key(key) { }
156
getKeyAvliSetEl157 const Key &getKey() const { return key; }
158
159 /** \brief The key. */
160 Key key;
161 };
162 #else /* not WALKABLE */
163 /**
164 * \brief Tree element for AvlSet
165 *
166 * Stores the key.
167 */
168 template <class Key> struct AvlSetEl :
169 public AvlTreeEl< AvlSetEl<Key> >
170 {
AvlSetElAvlSetEl171 AvlSetEl(const Key &key) : key(key) { }
172
getKeyAvlSetEl173 const Key &getKey() const { return key; }
174
175 /** \brief The key. */
176 Key key;
177 };
178 #endif /* def WALKABLE */
179
180 #endif /* AVLTREE_SET */
181
182 /* Common AvlTree Class */
183 template < AVLMEL_CLASSDEF > class AvlTree
184 #if !defined( AVL_KEYLESS ) && defined ( WALKABLE )
185 : public Compare, public BASELIST
186 #elif !defined( AVL_KEYLESS )
187 : public Compare
188 #elif defined( WALKABLE )
189 : public BASELIST
190 #endif
191 {
192 public:
193 /**
194 * \brief Create an empty tree.
195 */
196 #ifdef WALKABLE
AvlTree()197 AvlTree() : root(0), treeSize(0) { }
198 #else
199 AvlTree() : root(0), head(0), tail(0), treeSize(0) { }
200 #endif
201
202 /**
203 * \brief Perform a deep copy of the tree.
204 *
205 * Each element is duplicated for the new tree. Copy constructors are used
206 * to create the new elements.
207 */
208 AvlTree(const AvlTree &other);
209
210 #if defined( AVLTREE_MAP ) || defined( AVLTREE_SET )
211 /**
212 * \brief Clear the contents of the tree.
213 *
214 * All element are deleted.
215 */
~AvlTree()216 ~AvlTree() { empty(); }
217
218 /**
219 * \brief Perform a deep copy of the tree.
220 *
221 * Each element is duplicated for the new tree. Copy constructors are used
222 * to create the new element. If this tree contains items, they are first
223 * deleted.
224 *
225 * \returns A reference to this.
226 */
227 AvlTree &operator=( const AvlTree &tree );
228
229 /**
230 * \brief Transfer the elements of another tree into this.
231 *
232 * First deletes all elements in this tree.
233 */
234 void transfer( AvlTree &tree );
235 #else
236 /**
237 * \brief Abandon all elements in the tree.
238 *
239 * Tree elements are not deleted.
240 */
~AvlTree()241 ~AvlTree() {}
242
243 /**
244 * \brief Perform a deep copy of the tree.
245 *
246 * Each element is duplicated for the new tree. Copy constructors are used
247 * to create the new element. If this tree contains items, they are
248 * abandoned.
249 *
250 * \returns A reference to this.
251 */
252 AvlTree &operator=( const AvlTree &tree );
253
254 /**
255 * \brief Transfer the elements of another tree into this.
256 *
257 * All elements in this tree are abandoned first.
258 */
259 void transfer( AvlTree &tree );
260 #endif
261
262 #ifndef AVL_KEYLESS
263 /* Insert a element into the tree. */
264 Element *insert( Element *element, Element **lastFound = 0 );
265
266 #ifdef AVL_BASIC
267 /* Find a element in the tree. Returns the element if
268 * element exists, false otherwise. */
269 Element *find( const Element *element ) const;
270
271 #else
272 Element *insert( const Key &key, Element **lastFound = 0 );
273
274 #ifdef AVLTREE_MAP
275 Element *insert( const Key &key, const Value &val,
276 Element **lastFound = 0 );
277 #endif
278
279 /* Find a element in the tree. Returns the element if
280 * key exists, false otherwise. */
281 Element *find( const Key &key ) const;
282
283 /* Detach a element from the tree. */
284 Element *detach( const Key &key );
285
286 /* Detach and delete a element from the tree. */
287 bool remove( const Key &key );
288 #endif /* AVL_BASIC */
289 #endif /* AVL_KEYLESS */
290
291 /* Detach a element from the tree. */
292 Element *detach( Element *element );
293
294 /* Detach and delete a element from the tree. */
295 void remove( Element *element );
296
297 /* Free all memory used by tree. */
298 void empty();
299
300 /* Abandon all element in the tree. Does not delete element. */
301 void abandon();
302
303 /** Root element of the tree. */
304 Element *root;
305
306 #ifndef WALKABLE
307 Element *head, *tail;
308 #endif
309
310 /** The number of element in the tree. */
311 long treeSize;
312
313 /** \brief Return the number of elements in the tree. */
length()314 long length() const { return treeSize; }
315
316 /** \brief Return the number of elements in the tree. */
size()317 long size() const { return treeSize; }
318
319 /* Various classes for setting the iterator */
320 struct Iter;
IterFirstIterFirst321 struct IterFirst { IterFirst( const AvlTree &t ) : t(t) { } const AvlTree &t; };
IterLastIterLast322 struct IterLast { IterLast( const AvlTree &t ) : t(t) { } const AvlTree &t; };
IterNextIterNext323 struct IterNext { IterNext( const Iter &i ) : i(i) { } const Iter &i; };
IterPrevIterPrev324 struct IterPrev { IterPrev( const Iter &i ) : i(i) { } const Iter &i; };
325
326 #ifdef WALKABLE
327 /**
328 * \brief Avl Tree Iterator.
329 * \ingroup iterators
330 */
331 struct Iter
332 {
333 /* Default construct. */
IterIter334 Iter() : ptr(0) { }
335
336 /* Construct from an avl tree and iterator-setting classes. */
IterIter337 Iter( const AvlTree &t ) : ptr(t.head) { }
IterIter338 Iter( const IterFirst &af ) : ptr(af.t.head) { }
IterIter339 Iter( const IterLast &al ) : ptr(al.t.tail) { }
IterIter340 Iter( const IterNext &an ) : ptr(findNext(an.i.ptr)) { }
IterIter341 Iter( const IterPrev &ap ) : ptr(findPrev(ap.i.ptr)) { }
342
343 /* Assign from a tree and iterator-setting classes. */
344 Iter &operator=( const AvlTree &tree ) { ptr = tree.head; return *this; }
345 Iter &operator=( const IterFirst &af ) { ptr = af.t.head; return *this; }
346 Iter &operator=( const IterLast &al ) { ptr = al.t.tail; return *this; }
347 Iter &operator=( const IterNext &an ) { ptr = findNext(an.i.ptr); return *this; }
348 Iter &operator=( const IterPrev &ap ) { ptr = findPrev(ap.i.ptr); return *this; }
349
350 /** \brief Less than end? */
lteIter351 bool lte() const { return ptr != 0; }
352
353 /** \brief At end? */
endIter354 bool end() const { return ptr == 0; }
355
356 /** \brief Greater than beginning? */
gtbIter357 bool gtb() const { return ptr != 0; }
358
359 /** \brief At beginning? */
begIter360 bool beg() const { return ptr == 0; }
361
362 /** \brief At first element? */
firstIter363 bool first() const { return ptr && ptr->BASE_EL(prev) == 0; }
364
365 /** \brief At last element? */
lastIter366 bool last() const { return ptr && ptr->BASE_EL(next) == 0; }
367
368 /** \brief Implicit cast to Element*. */
369 operator Element*() const { return ptr; }
370
371 /** \brief Dereference operator returns Element&. */
372 Element &operator *() const { return *ptr; }
373
374 /** \brief Arrow operator returns Element*. */
375 Element *operator->() const { return ptr; }
376
377 /** \brief Move to next item. */
378 inline Element *operator++();
379
380 /** \brief Move to next item. */
381 inline Element *operator++(int);
382
383 /** \brief Move to next item. */
384 inline Element *increment();
385
386 /** \brief Move to previous item. */
387 inline Element *operator--();
388
389 /** \brief Move to previous item. */
390 inline Element *operator--(int);
391
392 /** \brief Move to previous item. */
393 inline Element *decrement();
394
395 /** \brief Return the next item. Does not modify this. */
nextIter396 IterNext next() const { return IterNext( *this ); }
397
398 /** \brief Return the previous item. Does not modify this. */
prevIter399 IterPrev prev() const { return IterPrev( *this ); }
400
401 private:
findPrevIter402 static Element *findPrev( Element *element ) { return element->BASE_EL(prev); }
findNextIter403 static Element *findNext( Element *element ) { return element->BASE_EL(next); }
404
405 public:
406
407 /** \brief The iterator is simply a pointer. */
408 Element *ptr;
409 };
410
411 #else
412
413 /**
414 * \brief Avl Tree Iterator.
415 * \ingroup iterators
416 */
417 struct Iter
418 {
419 /* Default construct. */
IterIter420 Iter() : ptr(0), tree(0) { }
421
422 /* Construct from a tree and iterator-setting classes. */
IterIter423 Iter( const AvlTree &t ) : ptr(t.head), tree(&t) { }
IterIter424 Iter( const IterFirst &af ) : ptr(af.t.head), tree(&af.t) { }
IterIter425 Iter( const IterLast &al ) : ptr(al.t.tail), tree(&al.t) { }
IterIter426 Iter( const IterNext &an ) : ptr(findNext(an.i.ptr)), tree(an.i.tree) { }
IterIter427 Iter( const IterPrev &ap ) : ptr(findPrev(ap.i.ptr)), tree(ap.i.tree) { }
428
429 /* Assign from a tree and iterator-setting classes. */
430 Iter &operator=( const AvlTree &t )
431 { ptr = t.head; tree = &t; return *this; }
432 Iter &operator=( const IterFirst &af )
433 { ptr = af.t.head; tree = &af.t; return *this; }
434 Iter &operator=( const IterLast &al )
435 { ptr = al.t.tail; tree = &al.t; return *this; }
436 Iter &operator=( const IterNext &an )
437 { ptr = findNext(an.i.ptr); tree = an.i.tree; return *this; }
438 Iter &operator=( const IterPrev &ap )
439 { ptr = findPrev(ap.i.ptr); tree = ap.i.tree; return *this; }
440
441 /** \brief Less than end? */
lteIter442 bool lte() const { return ptr != 0; }
443
444 /** \brief At end? */
endIter445 bool end() const { return ptr == 0; }
446
447 /** \brief Greater than beginning? */
gtbIter448 bool gtb() const { return ptr != 0; }
449
450 /** \brief At beginning? */
begIter451 bool beg() const { return ptr == 0; }
452
453 /** \brief At first element? */
firstIter454 bool first() const { return ptr && ptr == tree->head; }
455
456 /** \brief At last element? */
lastIter457 bool last() const { return ptr && ptr == tree->tail; }
458
459 /** \brief Implicit cast to Element*. */
460 operator Element*() const { return ptr; }
461
462 /** \brief Dereference operator returns Element&. */
463 Element &operator *() const { return *ptr; }
464
465 /** \brief Arrow operator returns Element*. */
466 Element *operator->() const { return ptr; }
467
468 /** \brief Move to next item. */
469 inline Element *operator++();
470
471 /** \brief Move to next item. */
472 inline Element *operator++(int);
473
474 /** \brief Move to next item. */
475 inline Element *increment();
476
477 /** \brief Move to previous item. */
478 inline Element *operator--();
479
480 /** \brief Move to previous item. */
481 inline Element *operator--(int);
482
483 /** \brief Move to previous item. */
484 inline Element *decrement();
485
486 /** \brief Return the next item. Does not modify this. */
nextIter487 IterNext next() const { return IterNext( *this ); }
488
489 /** \brief Return the previous item. Does not modify this. */
prevIter490 IterPrev prev() const { return IterPrev( *this ); }
491
492 private:
493 static Element *findPrev( Element *element );
494 static Element *findNext( Element *element );
495
496 public:
497 /** \brief The iterator is simply a pointer. */
498 Element *ptr;
499
500 /* The list is not walkable so we need to keep a pointerto the tree
501 * so we can test against head and tail in O(1) time. */
502 const AvlTree *tree;
503 };
504 #endif
505
506 /** \brief Return first element. */
first()507 IterFirst first() { return IterFirst( *this ); }
508
509 /** \brief Return last element. */
last()510 IterLast last() { return IterLast( *this ); }
511
512 protected:
513 /* Recursive worker for the copy constructor. */
514 Element *copyBranch( Element *element );
515
516 /* Recursively delete element in the tree. */
517 void deleteChildrenOf(Element *n);
518
519 /* rebalance the tree beginning at the leaf whose
520 * grandparent is unbalanced. */
521 Element *rebalance(Element *start);
522
523 /* Move up the tree from a given element, recalculating the heights. */
524 void recalcHeights(Element *start);
525
526 /* Move up the tree and find the first element whose
527 * grand-parent is unbalanced. */
528 Element *findFirstUnbalGP(Element *start);
529
530 /* Move up the tree and find the first element which is unbalanced. */
531 Element *findFirstUnbalEl(Element *start);
532
533 /* Replace a element in the tree with another element not in the tree. */
534 void replaceEl(Element *element, Element *replacement);
535
536 /* Remove a element from the tree and put another (normally a child of element)
537 * in its place. */
538 void removeEl(Element *element, Element *filler);
539
540 /* Once an insertion point is found at a leaf then do the insert. */
541 void attachRebal( Element *element, Element *parentEl, Element *lastLess );
542 };
543
544 /* Copy constructor. New up each item. */
545 template <AVLMEL_TEMPDEF> AvlTree<AVLMEL_TEMPUSE>::
AvlTree(const AvlTree<AVLMEL_TEMPUSE> & other)546 AvlTree(const AvlTree<AVLMEL_TEMPUSE> &other)
547 #ifdef WALKABLE
548 :
549 /* Make an empty list, copyBranch will fill in the details for us. */
550 BASELIST()
551 #endif
552 {
553 treeSize = other.treeSize;
554 root = other.root;
555
556 #ifndef WALKABLE
557 head = 0;
558 tail = 0;
559 #endif
560
561 /* If there is a root, copy the tree. */
562 if ( other.root != 0 )
563 root = copyBranch( other.root );
564 }
565
566 #if defined( AVLTREE_MAP ) || defined( AVLTREE_SET )
567
568 /* Assignment does deep copy. */
569 template <AVLMEL_TEMPDEF> AvlTree<AVLMEL_TEMPUSE> &AvlTree<AVLMEL_TEMPUSE>::
570 operator=( const AvlTree &other )
571 {
572 /* Clear the tree first. */
573 empty();
574
575 /* Reset the list pointers, the tree copy will fill in the list for us. */
576 #ifdef WALKABLE
577 BASELIST::abandon();
578 #else
579 head = 0;
580 tail = 0;
581 #endif
582
583 /* Copy the entire tree. */
584 treeSize = other.treeSize;
585 root = other.root;
586 if ( other.root != 0 )
587 root = copyBranch( other.root );
588 return *this;
589 }
590
591 template <AVLMEL_TEMPDEF> void AvlTree<AVLMEL_TEMPUSE>::
transfer(AvlTree<AVLMEL_TEMPUSE> & other)592 transfer(AvlTree<AVLMEL_TEMPUSE> &other)
593 {
594 /* Clear the tree first. */
595 empty();
596
597 treeSize = other.treeSize;
598 root = other.root;
599
600 #ifdef WALKABLE
601 BASELIST::head = other.BASELIST::head;
602 BASELIST::tail = other.BASELIST::tail;
603 BASELIST::listLen = other.BASELIST::listLen;
604 #else
605 head = other.head;
606 tail = other.tail;
607 #endif
608
609 other.abandon();
610 }
611
612 #else /* ! AVLTREE_MAP && ! AVLTREE_SET */
613
614 /* Assignment does deep copy. This version does not clear the tree first. */
615 template <AVLMEL_TEMPDEF> AvlTree<AVLMEL_TEMPUSE> &AvlTree<AVLMEL_TEMPUSE>::
616 operator=( const AvlTree &other )
617 {
618 /* Reset the list pointers, the tree copy will fill in the list for us. */
619 #ifdef WALKABLE
620 BASELIST::abandon();
621 #else
622 head = 0;
623 tail = 0;
624 #endif
625
626 /* Copy the entire tree. */
627 treeSize = other.treeSize;
628 root = other.root;
629 if ( other.root != 0 )
630 root = copyBranch( other.root );
631 return *this;
632 }
633
634 template <AVLMEL_TEMPDEF> void AvlTree<AVLMEL_TEMPUSE>::
transfer(AvlTree<AVLMEL_TEMPUSE> & other)635 transfer(AvlTree<AVLMEL_TEMPUSE> &other)
636 {
637 treeSize = other.treeSize;
638 root = other.root;
639
640 #ifdef WALKABLE
641 BASELIST::head = other.BASELIST::head;
642 BASELIST::tail = other.BASELIST::tail;
643 BASELIST::listLen = other.BASELIST::listLen;
644 #else
645 head = other.head;
646 tail = other.tail;
647 #endif
648
649 other.abandon();
650 }
651
652 #endif
653
654 /*
655 * Iterator operators.
656 */
657
658 /* Prefix ++ */
659 template <AVLMEL_TEMPDEF> Element *AvlTree<AVLMEL_TEMPUSE>::Iter::
660 operator++()
661 {
662 return ptr = findNext( ptr );
663 }
664
665 /* Postfix ++ */
666 template <AVLMEL_TEMPDEF> Element *AvlTree<AVLMEL_TEMPUSE>::Iter::
667 operator++(int)
668 {
669 Element *rtn = ptr;
670 ptr = findNext( ptr );
671 return rtn;
672 }
673
674 /* increment */
675 template <AVLMEL_TEMPDEF> Element *AvlTree<AVLMEL_TEMPUSE>::Iter::
increment()676 increment()
677 {
678 return ptr = findNext( ptr );
679 }
680
681 /* Prefix -- */
682 template <AVLMEL_TEMPDEF> Element *AvlTree<AVLMEL_TEMPUSE>::Iter::
683 operator--()
684 {
685 return ptr = findPrev( ptr );
686 }
687
688 /* Postfix -- */
689 template <AVLMEL_TEMPDEF> Element *AvlTree<AVLMEL_TEMPUSE>::Iter::
690 operator--(int)
691 {
692 Element *rtn = ptr;
693 ptr = findPrev( ptr );
694 return rtn;
695 }
696
697 /* decrement */
698 template <AVLMEL_TEMPDEF> Element *AvlTree<AVLMEL_TEMPUSE>::Iter::
decrement()699 decrement()
700 {
701 return ptr = findPrev( ptr );
702 }
703
704 #ifndef WALKABLE
705
706 /* Move ahead one. */
707 template <AVLMEL_TEMPDEF> Element *AvlTree<AVLMEL_TEMPUSE>::Iter::
findNext(Element * element)708 findNext( Element *element )
709 {
710 /* Try to go right once then infinite left. */
711 if ( element->BASE_EL(right) != 0 ) {
712 element = element->BASE_EL(right);
713 while ( element->BASE_EL(left) != 0 )
714 element = element->BASE_EL(left);
715 }
716 else {
717 /* Go up to parent until we were just a left child. */
718 while ( true ) {
719 Element *last = element;
720 element = element->BASE_EL(parent);
721 if ( element == 0 || element->BASE_EL(left) == last )
722 break;
723 }
724 }
725 return element;
726 }
727
728 /* Move back one. */
729 template <AVLMEL_TEMPDEF> Element *AvlTree<AVLMEL_TEMPUSE>::Iter::
findPrev(Element * element)730 findPrev( Element *element )
731 {
732 /* Try to go left once then infinite right. */
733 if ( element->BASE_EL(left) != 0 ) {
734 element = element->BASE_EL(left);
735 while ( element->BASE_EL(right) != 0 )
736 element = element->BASE_EL(right);
737 }
738 else {
739 /* Go up to parent until we were just a left child. */
740 while ( true ) {
741 Element *last = element;
742 element = element->BASE_EL(parent);
743 if ( element == 0 || element->BASE_EL(right) == last )
744 break;
745 }
746 }
747 return element;
748 }
749
750 #endif
751
752
753 /* Recursive worker for tree copying. */
754 template <AVLMEL_TEMPDEF> Element *AvlTree<AVLMEL_TEMPUSE>::
copyBranch(Element * element)755 copyBranch( Element *element )
756 {
757 /* Duplicate element. Either the base element's copy constructor or defaul
758 * constructor will get called. Both will suffice for initting the
759 * pointers to null when they need to be. */
760 Element *retVal = new Element(*element);
761
762 /* If the left tree is there, copy it. */
763 if ( retVal->BASE_EL(left) ) {
764 retVal->BASE_EL(left) = copyBranch(retVal->BASE_EL(left));
765 retVal->BASE_EL(left)->BASE_EL(parent) = retVal;
766 }
767
768 #ifdef WALKABLE
769 BASELIST::addAfter( BASELIST::tail, retVal );
770 #else
771 if ( head == 0 )
772 head = retVal;
773 tail = retVal;
774 #endif
775
776 /* If the right tree is there, copy it. */
777 if ( retVal->BASE_EL(right) ) {
778 retVal->BASE_EL(right) = copyBranch(retVal->BASE_EL(right));
779 retVal->BASE_EL(right)->BASE_EL(parent) = retVal;
780 }
781 return retVal;
782 }
783
784 /* Once an insertion position is found, attach a element to the tree. */
785 template <AVLMEL_TEMPDEF> void AvlTree<AVLMEL_TEMPUSE>::
attachRebal(Element * element,Element * parentEl,Element * lastLess)786 attachRebal( Element *element, Element *parentEl, Element *lastLess )
787 {
788 /* Increment the number of element in the tree. */
789 treeSize += 1;
790
791 /* Set element's parent. */
792 element->BASE_EL(parent) = parentEl;
793
794 /* New element always starts as a leaf with height 1. */
795 element->BASE_EL(left) = 0;
796 element->BASE_EL(right) = 0;
797 element->BASE_EL(height) = 1;
798
799 /* Are we inserting in the tree somewhere? */
800 if ( parentEl != 0 ) {
801 /* We have a parent so we are somewhere in the tree. If the parent
802 * equals lastLess, then the last traversal in the insertion went
803 * left, otherwise it went right. */
804 if ( lastLess == parentEl ) {
805 parentEl->BASE_EL(left) = element;
806 #ifdef WALKABLE
807 BASELIST::addBefore( parentEl, element );
808 #endif
809 }
810 else {
811 parentEl->BASE_EL(right) = element;
812 #ifdef WALKABLE
813 BASELIST::addAfter( parentEl, element );
814 #endif
815 }
816
817 #ifndef WALKABLE
818 /* Maintain the first and last pointers. */
819 if ( head->BASE_EL(left) == element )
820 head = element;
821
822 /* Maintain the first and last pointers. */
823 if ( tail->BASE_EL(right) == element )
824 tail = element;
825 #endif
826 }
827 else {
828 /* No parent element so we are inserting the root. */
829 root = element;
830 #ifdef WALKABLE
831 BASELIST::addAfter( BASELIST::tail, element );
832 #else
833 head = tail = element;
834 #endif
835 }
836
837
838 /* Recalculate the heights. */
839 recalcHeights(parentEl);
840
841 /* Find the first unbalance. */
842 Element *ub = findFirstUnbalGP(element);
843
844 /* rebalance. */
845 if ( ub != 0 )
846 {
847 /* We assert that after this single rotation the
848 * tree is now properly balanced. */
849 rebalance(ub);
850 }
851 }
852
853 #ifndef AVL_KEYLESS
854
855 /**
856 * \brief Insert an existing element into the tree.
857 *
858 * If the insert succeeds and lastFound is given then it is set to the element
859 * inserted. If the insert fails then lastFound is set to the existing element in
860 * the tree that has the same key as element. If the element's avl pointers are
861 * already in use then undefined behaviour results.
862 *
863 * \returns The element inserted upon success, null upon failure.
864 */
865 template <AVLMEL_TEMPDEF> Element *AvlTree<AVLMEL_TEMPUSE>::
insert(Element * element,Element ** lastFound)866 insert( Element *element, Element **lastFound )
867 {
868 long keyRelation;
869 Element *curEl = root, *parentEl = 0;
870 Element *lastLess = 0;
871
872 while (true) {
873 if ( curEl == 0 ) {
874 /* We are at an external element and did not find the key we were
875 * looking for. Attach underneath the leaf and rebalance. */
876 attachRebal( element, parentEl, lastLess );
877
878 if ( lastFound != 0 )
879 *lastFound = element;
880 return element;
881 }
882
883 #ifdef AVL_BASIC
884 keyRelation = this->compare( *element, *curEl );
885 #else
886 keyRelation = this->compare( element->BASEKEY(getKey()),
887 curEl->BASEKEY(getKey()) );
888 #endif
889
890 /* Do we go left? */
891 if ( keyRelation < 0 ) {
892 parentEl = lastLess = curEl;
893 curEl = curEl->BASE_EL(left);
894 }
895 /* Do we go right? */
896 else if ( keyRelation > 0 ) {
897 parentEl = curEl;
898 curEl = curEl->BASE_EL(right);
899 }
900 /* We have hit the target. */
901 else {
902 if ( lastFound != 0 )
903 *lastFound = curEl;
904 return 0;
905 }
906 }
907 }
908
909 #ifdef AVL_BASIC
910
911 /**
912 * \brief Find a element in the tree with the given key.
913 *
914 * \returns The element if key exists, null if the key does not exist.
915 */
916 template <AVLMEL_TEMPDEF> Element *AvlTree<AVLMEL_TEMPUSE>::
find(const Element * element)917 find( const Element *element ) const
918 {
919 Element *curEl = root;
920 long keyRelation;
921
922 while (curEl) {
923 keyRelation = this->compare( *element, *curEl );
924
925 /* Do we go left? */
926 if ( keyRelation < 0 )
927 curEl = curEl->BASE_EL(left);
928 /* Do we go right? */
929 else if ( keyRelation > 0 )
930 curEl = curEl->BASE_EL(right);
931 /* We have hit the target. */
932 else {
933 return curEl;
934 }
935 }
936 return 0;
937 }
938
939 #else
940
941 /**
942 * \brief Insert a new element into the tree with given key.
943 *
944 * If the key is not already in the tree then a new element is made using the
945 * Element(const Key &key) constructor and the insert succeeds. If lastFound is
946 * given then it is set to the element inserted. If the insert fails then
947 * lastFound is set to the existing element in the tree that has the same key as
948 * element.
949 *
950 * \returns The new element upon success, null upon failure.
951 */
952 template <AVLMEL_TEMPDEF> Element *AvlTree<AVLMEL_TEMPUSE>::
insert(const Key & key,Element ** lastFound)953 insert( const Key &key, Element **lastFound )
954 {
955 long keyRelation;
956 Element *curEl = root, *parentEl = 0;
957 Element *lastLess = 0;
958
959 while (true) {
960 if ( curEl == 0 ) {
961 /* We are at an external element and did not find the key we were
962 * looking for. Create the new element, attach it underneath the leaf
963 * and rebalance. */
964 Element *element = new Element( key );
965 attachRebal( element, parentEl, lastLess );
966
967 if ( lastFound != 0 )
968 *lastFound = element;
969 return element;
970 }
971
972 keyRelation = this->compare( key, curEl->BASEKEY(getKey()) );
973
974 /* Do we go left? */
975 if ( keyRelation < 0 ) {
976 parentEl = lastLess = curEl;
977 curEl = curEl->BASE_EL(left);
978 }
979 /* Do we go right? */
980 else if ( keyRelation > 0 ) {
981 parentEl = curEl;
982 curEl = curEl->BASE_EL(right);
983 }
984 /* We have hit the target. */
985 else {
986 if ( lastFound != 0 )
987 *lastFound = curEl;
988 return 0;
989 }
990 }
991 }
992
993 #ifdef AVLTREE_MAP
994 /**
995 * \brief Insert a new element into the tree with key and value.
996 *
997 * If the key is not already in the tree then a new element is constructed and
998 * the insert succeeds. If lastFound is given then it is set to the element
999 * inserted. If the insert fails then lastFound is set to the existing element in
1000 * the tree that has the same key as element. This insert routine is only
1001 * available in AvlMap because it is the only class that knows about a Value
1002 * type.
1003 *
1004 * \returns The new element upon success, null upon failure.
1005 */
1006 template <AVLMEL_TEMPDEF> Element *AvlTree<AVLMEL_TEMPUSE>::
insert(const Key & key,const Value & val,Element ** lastFound)1007 insert( const Key &key, const Value &val, Element **lastFound )
1008 {
1009 long keyRelation;
1010 Element *curEl = root, *parentEl = 0;
1011 Element *lastLess = 0;
1012
1013 while (true) {
1014 if ( curEl == 0 ) {
1015 /* We are at an external element and did not find the key we were
1016 * looking for. Create the new element, attach it underneath the leaf
1017 * and rebalance. */
1018 Element *element = new Element( key, val );
1019 attachRebal( element, parentEl, lastLess );
1020
1021 if ( lastFound != 0 )
1022 *lastFound = element;
1023 return element;
1024 }
1025
1026 keyRelation = this->compare(key, curEl->getKey());
1027
1028 /* Do we go left? */
1029 if ( keyRelation < 0 ) {
1030 parentEl = lastLess = curEl;
1031 curEl = curEl->BASE_EL(left);
1032 }
1033 /* Do we go right? */
1034 else if ( keyRelation > 0 ) {
1035 parentEl = curEl;
1036 curEl = curEl->BASE_EL(right);
1037 }
1038 /* We have hit the target. */
1039 else {
1040 if ( lastFound != 0 )
1041 *lastFound = curEl;
1042 return 0;
1043 }
1044 }
1045 }
1046 #endif /* AVLTREE_MAP */
1047
1048
1049 /**
1050 * \brief Find a element in the tree with the given key.
1051 *
1052 * \returns The element if key exists, null if the key does not exist.
1053 */
1054 template <AVLMEL_TEMPDEF> Element *AvlTree<AVLMEL_TEMPUSE>::
find(const Key & key)1055 find( const Key &key ) const
1056 {
1057 Element *curEl = root;
1058 long keyRelation;
1059
1060 while (curEl) {
1061 keyRelation = this->compare( key, curEl->BASEKEY(getKey()) );
1062
1063 /* Do we go left? */
1064 if ( keyRelation < 0 )
1065 curEl = curEl->BASE_EL(left);
1066 /* Do we go right? */
1067 else if ( keyRelation > 0 )
1068 curEl = curEl->BASE_EL(right);
1069 /* We have hit the target. */
1070 else {
1071 return curEl;
1072 }
1073 }
1074 return 0;
1075 }
1076
1077
1078 /**
1079 * \brief Find a element, then detach it from the tree.
1080 *
1081 * The element is not deleted.
1082 *
1083 * \returns The element detached if the key is found, othewise returns null.
1084 */
1085 template <AVLMEL_TEMPDEF> Element *AvlTree<AVLMEL_TEMPUSE>::
detach(const Key & key)1086 detach(const Key &key)
1087 {
1088 Element *element = find( key );
1089 if ( element ) {
1090 detach(element);
1091 }
1092
1093 return element;
1094 }
1095
1096 /**
1097 * \brief Find, detach and delete a element from the tree.
1098 *
1099 * \returns True if the element was found and deleted, false otherwise.
1100 */
1101 template <AVLMEL_TEMPDEF> bool AvlTree<AVLMEL_TEMPUSE>::
remove(const Key & key)1102 remove(const Key &key)
1103 {
1104 /* Assume not found. */
1105 bool retVal = false;
1106
1107 /* Look for the key. */
1108 Element *element = find( key );
1109 if ( element != 0 ) {
1110 /* If found, detach the element and delete. */
1111 detach( element );
1112 delete element;
1113 retVal = true;
1114 }
1115
1116 return retVal;
1117 }
1118
1119 #endif /* AVL_BASIC */
1120 #endif /* AVL_KEYLESS */
1121
1122
1123 /**
1124 * \brief Detach and delete a element from the tree.
1125 *
1126 * If the element is not in the tree then undefined behaviour results.
1127 */
1128 template <AVLMEL_TEMPDEF> void AvlTree<AVLMEL_TEMPUSE>::
remove(Element * element)1129 remove(Element *element)
1130 {
1131 /* Detach and delete. */
1132 detach(element);
1133 delete element;
1134 }
1135
1136 /**
1137 * \brief Detach a element from the tree.
1138 *
1139 * If the element is not in the tree then undefined behaviour results.
1140 *
1141 * \returns The element given.
1142 */
1143 template <AVLMEL_TEMPDEF> Element *AvlTree<AVLMEL_TEMPUSE>::
detach(Element * element)1144 detach(Element *element)
1145 {
1146 Element *replacement, *fixfrom;
1147 long lheight, rheight;
1148
1149 #ifdef WALKABLE
1150 /* Remove the element from the ordered list. */
1151 BASELIST::detach( element );
1152 #endif
1153
1154 /* Update treeSize. */
1155 treeSize--;
1156
1157 /* Find a replacement element. */
1158 if (element->BASE_EL(right))
1159 {
1160 /* Find the leftmost element of the right subtree. */
1161 replacement = element->BASE_EL(right);
1162 while (replacement->BASE_EL(left))
1163 replacement = replacement->BASE_EL(left);
1164
1165 /* If replacing the element the with its child then we need to start
1166 * fixing at the replacement, otherwise we start fixing at the
1167 * parent of the replacement. */
1168 if (replacement->BASE_EL(parent) == element)
1169 fixfrom = replacement;
1170 else
1171 fixfrom = replacement->BASE_EL(parent);
1172
1173 #ifndef WALKABLE
1174 if ( element == head )
1175 head = replacement;
1176 #endif
1177
1178 removeEl(replacement, replacement->BASE_EL(right));
1179 replaceEl(element, replacement);
1180 }
1181 else if (element->BASE_EL(left))
1182 {
1183 /* Find the rightmost element of the left subtree. */
1184 replacement = element->BASE_EL(left);
1185 while (replacement->BASE_EL(right))
1186 replacement = replacement->BASE_EL(right);
1187
1188 /* If replacing the element the with its child then we need to start
1189 * fixing at the replacement, otherwise we start fixing at the
1190 * parent of the replacement. */
1191 if (replacement->BASE_EL(parent) == element)
1192 fixfrom = replacement;
1193 else
1194 fixfrom = replacement->BASE_EL(parent);
1195
1196 #ifndef WALKABLE
1197 if ( element == tail )
1198 tail = replacement;
1199 #endif
1200
1201 removeEl(replacement, replacement->BASE_EL(left));
1202 replaceEl(element, replacement);
1203 }
1204 else
1205 {
1206 /* We need to start fixing at the parent of the element. */
1207 fixfrom = element->BASE_EL(parent);
1208
1209 #ifndef WALKABLE
1210 if ( element == head )
1211 head = element->BASE_EL(parent);
1212 if ( element == tail )
1213 tail = element->BASE_EL(parent);
1214 #endif
1215
1216 /* The element we are deleting is a leaf element. */
1217 removeEl(element, 0);
1218 }
1219
1220 /* If fixfrom is null it means we just deleted
1221 * the root of the tree. */
1222 if ( fixfrom == 0 )
1223 return element;
1224
1225 /* Fix the heights after the deletion. */
1226 recalcHeights(fixfrom);
1227
1228 /* Fix every unbalanced element going up in the tree. */
1229 Element *ub = findFirstUnbalEl(fixfrom);
1230 while ( ub )
1231 {
1232 /* Find the element to rebalance by moving down from the first unbalanced
1233 * element 2 levels in the direction of the greatest heights. On the
1234 * second move down, the heights may be equal ( but not on the first ).
1235 * In which case go in the direction of the first move. */
1236 lheight = ub->BASE_EL(left) ? ub->BASE_EL(left)->BASE_EL(height) : 0;
1237 rheight = ub->BASE_EL(right) ? ub->BASE_EL(right)->BASE_EL(height) : 0;
1238 assert( lheight != rheight );
1239 if (rheight > lheight)
1240 {
1241 ub = ub->BASE_EL(right);
1242 lheight = ub->BASE_EL(left) ?
1243 ub->BASE_EL(left)->BASE_EL(height) : 0;
1244 rheight = ub->BASE_EL(right) ?
1245 ub->BASE_EL(right)->BASE_EL(height) : 0;
1246 if (rheight > lheight)
1247 ub = ub->BASE_EL(right);
1248 else if (rheight < lheight)
1249 ub = ub->BASE_EL(left);
1250 else
1251 ub = ub->BASE_EL(right);
1252 }
1253 else
1254 {
1255 ub = ub->BASE_EL(left);
1256 lheight = ub->BASE_EL(left) ?
1257 ub->BASE_EL(left)->BASE_EL(height) : 0;
1258 rheight = ub->BASE_EL(right) ?
1259 ub->BASE_EL(right)->BASE_EL(height) : 0;
1260 if (rheight > lheight)
1261 ub = ub->BASE_EL(right);
1262 else if (rheight < lheight)
1263 ub = ub->BASE_EL(left);
1264 else
1265 ub = ub->BASE_EL(left);
1266 }
1267
1268
1269 /* rebalance returns the grandparant of the subtree formed
1270 * by the element that were rebalanced.
1271 * We must continue upward from there rebalancing. */
1272 fixfrom = rebalance(ub);
1273
1274 /* Find the next unbalaced element. */
1275 ub = findFirstUnbalEl(fixfrom);
1276 }
1277
1278 return element;
1279 }
1280
1281
1282 /**
1283 * \brief Empty the tree and delete all the element.
1284 *
1285 * Resets the tree to its initial state.
1286 */
empty()1287 template <AVLMEL_TEMPDEF> void AvlTree<AVLMEL_TEMPUSE>::empty()
1288 {
1289 if ( root ) {
1290 /* Recursively delete from the tree structure. */
1291 deleteChildrenOf(root);
1292 delete root;
1293 root = 0;
1294 treeSize = 0;
1295
1296 #ifdef WALKABLE
1297 BASELIST::abandon();
1298 #endif
1299 }
1300 }
1301
1302 /**
1303 * \brief Forget all element in the tree.
1304 *
1305 * Does not delete element. Resets the the tree to it's initial state.
1306 */
abandon()1307 template <AVLMEL_TEMPDEF> void AvlTree<AVLMEL_TEMPUSE>::abandon()
1308 {
1309 root = 0;
1310 treeSize = 0;
1311
1312 #ifdef WALKABLE
1313 BASELIST::abandon();
1314 #endif
1315 }
1316
1317 /* Recursively delete all the children of a element. */
1318 template <AVLMEL_TEMPDEF> void AvlTree<AVLMEL_TEMPUSE>::
deleteChildrenOf(Element * element)1319 deleteChildrenOf( Element *element )
1320 {
1321 /* Recurse left. */
1322 if (element->BASE_EL(left)) {
1323 deleteChildrenOf(element->BASE_EL(left));
1324
1325 /* Delete left element. */
1326 delete element->BASE_EL(left);
1327 element->BASE_EL(left) = 0;
1328 }
1329
1330 /* Recurse right. */
1331 if (element->BASE_EL(right)) {
1332 deleteChildrenOf(element->BASE_EL(right));
1333
1334 /* Delete right element. */
1335 delete element->BASE_EL(right);
1336 element->BASE_EL(left) = 0;
1337 }
1338 }
1339
1340 /* rebalance from a element whose gradparent is unbalanced. Only
1341 * call on a element that has a grandparent. */
1342 template <AVLMEL_TEMPDEF> Element *AvlTree<AVLMEL_TEMPUSE>::
rebalance(Element * n)1343 rebalance(Element *n)
1344 {
1345 long lheight, rheight;
1346 Element *a, *b, *c;
1347 Element *t1, *t2, *t3, *t4;
1348
1349 Element *p = n->BASE_EL(parent); /* parent (Non-NUL). L*/
1350 Element *gp = p->BASE_EL(parent); /* Grand-parent (Non-NULL). */
1351 Element *ggp = gp->BASE_EL(parent); /* Great grand-parent (may be NULL). */
1352
1353 if (gp->BASE_EL(right) == p)
1354 {
1355 /* gp
1356 * \
1357 * p
1358 */
1359 if (p->BASE_EL(right) == n)
1360 {
1361 /* gp
1362 * \
1363 * p
1364 * \
1365 * n
1366 */
1367 a = gp;
1368 b = p;
1369 c = n;
1370 t1 = gp->BASE_EL(left);
1371 t2 = p->BASE_EL(left);
1372 t3 = n->BASE_EL(left);
1373 t4 = n->BASE_EL(right);
1374 }
1375 else
1376 {
1377 /* gp
1378 * \
1379 * p
1380 * /
1381 * n
1382 */
1383 a = gp;
1384 b = n;
1385 c = p;
1386 t1 = gp->BASE_EL(left);
1387 t2 = n->BASE_EL(left);
1388 t3 = n->BASE_EL(right);
1389 t4 = p->BASE_EL(right);
1390 }
1391 }
1392 else
1393 {
1394 /* gp
1395 * /
1396 * p
1397 */
1398 if (p->BASE_EL(right) == n)
1399 {
1400 /* gp
1401 * /
1402 * p
1403 * \
1404 * n
1405 */
1406 a = p;
1407 b = n;
1408 c = gp;
1409 t1 = p->BASE_EL(left);
1410 t2 = n->BASE_EL(left);
1411 t3 = n->BASE_EL(right);
1412 t4 = gp->BASE_EL(right);
1413 }
1414 else
1415 {
1416 /* gp
1417 * /
1418 * p
1419 * /
1420 * n
1421 */
1422 a = n;
1423 b = p;
1424 c = gp;
1425 t1 = n->BASE_EL(left);
1426 t2 = n->BASE_EL(right);
1427 t3 = p->BASE_EL(right);
1428 t4 = gp->BASE_EL(right);
1429 }
1430 }
1431
1432 /* Perform rotation.
1433 */
1434
1435 /* Tie b to the great grandparent. */
1436 if ( ggp == 0 )
1437 root = b;
1438 else if ( ggp->BASE_EL(left) == gp )
1439 ggp->BASE_EL(left) = b;
1440 else
1441 ggp->BASE_EL(right) = b;
1442 b->BASE_EL(parent) = ggp;
1443
1444 /* Tie a as a leftchild of b. */
1445 b->BASE_EL(left) = a;
1446 a->BASE_EL(parent) = b;
1447
1448 /* Tie c as a rightchild of b. */
1449 b->BASE_EL(right) = c;
1450 c->BASE_EL(parent) = b;
1451
1452 /* Tie t1 as a leftchild of a. */
1453 a->BASE_EL(left) = t1;
1454 if ( t1 != 0 ) t1->BASE_EL(parent) = a;
1455
1456 /* Tie t2 as a rightchild of a. */
1457 a->BASE_EL(right) = t2;
1458 if ( t2 != 0 ) t2->BASE_EL(parent) = a;
1459
1460 /* Tie t3 as a leftchild of c. */
1461 c->BASE_EL(left) = t3;
1462 if ( t3 != 0 ) t3->BASE_EL(parent) = c;
1463
1464 /* Tie t4 as a rightchild of c. */
1465 c->BASE_EL(right) = t4;
1466 if ( t4 != 0 ) t4->BASE_EL(parent) = c;
1467
1468 /* The heights are all recalculated manualy and the great
1469 * grand-parent is passed to recalcHeights() to ensure
1470 * the heights are correct up the tree.
1471 *
1472 * Note that recalcHeights() cuts out when it comes across
1473 * a height that hasn't changed.
1474 */
1475
1476 /* Fix height of a. */
1477 lheight = a->BASE_EL(left) ? a->BASE_EL(left)->BASE_EL(height) : 0;
1478 rheight = a->BASE_EL(right) ? a->BASE_EL(right)->BASE_EL(height) : 0;
1479 a->BASE_EL(height) = (lheight > rheight ? lheight : rheight) + 1;
1480
1481 /* Fix height of c. */
1482 lheight = c->BASE_EL(left) ? c->BASE_EL(left)->BASE_EL(height) : 0;
1483 rheight = c->BASE_EL(right) ? c->BASE_EL(right)->BASE_EL(height) : 0;
1484 c->BASE_EL(height) = (lheight > rheight ? lheight : rheight) + 1;
1485
1486 /* Fix height of b. */
1487 lheight = a->BASE_EL(height);
1488 rheight = c->BASE_EL(height);
1489 b->BASE_EL(height) = (lheight > rheight ? lheight : rheight) + 1;
1490
1491 /* Fix height of b's parents. */
1492 recalcHeights(ggp);
1493 return ggp;
1494 }
1495
1496 /* Recalculates the heights of all the ancestors of element. */
1497 template <AVLMEL_TEMPDEF> void AvlTree<AVLMEL_TEMPUSE>::
recalcHeights(Element * element)1498 recalcHeights(Element *element)
1499 {
1500 long lheight, rheight, new_height;
1501 while ( element != 0 )
1502 {
1503 lheight = element->BASE_EL(left) ? element->BASE_EL(left)->BASE_EL(height) : 0;
1504 rheight = element->BASE_EL(right) ? element->BASE_EL(right)->BASE_EL(height) : 0;
1505
1506 new_height = (lheight > rheight ? lheight : rheight) + 1;
1507
1508 /* If there is no chage in the height, then there will be no
1509 * change in any of the ancestor's height. We can stop going up.
1510 * If there was a change, continue upward. */
1511 if (new_height == element->BASE_EL(height))
1512 return;
1513 else
1514 element->BASE_EL(height) = new_height;
1515
1516 element = element->BASE_EL(parent);
1517 }
1518 }
1519
1520 /* Finds the first element whose grandparent is unbalanced. */
1521 template <AVLMEL_TEMPDEF> Element *AvlTree<AVLMEL_TEMPUSE>::
findFirstUnbalGP(Element * element)1522 findFirstUnbalGP(Element *element)
1523 {
1524 long lheight, rheight, balanceProp;
1525 Element *gp;
1526
1527 if ( element == 0 || element->BASE_EL(parent) == 0 ||
1528 element->BASE_EL(parent)->BASE_EL(parent) == 0 )
1529 return 0;
1530
1531 /* Don't do anything if we we have no grandparent. */
1532 gp = element->BASE_EL(parent)->BASE_EL(parent);
1533 while ( gp != 0 )
1534 {
1535 lheight = gp->BASE_EL(left) ? gp->BASE_EL(left)->BASE_EL(height) : 0;
1536 rheight = gp->BASE_EL(right) ? gp->BASE_EL(right)->BASE_EL(height) : 0;
1537 balanceProp = lheight - rheight;
1538
1539 if ( balanceProp < -1 || balanceProp > 1 )
1540 return element;
1541
1542 element = element->BASE_EL(parent);
1543 gp = gp->BASE_EL(parent);
1544 }
1545 return 0;
1546 }
1547
1548
1549 /* Finds the first element that is unbalanced. */
1550 template <AVLMEL_TEMPDEF> Element *AvlTree<AVLMEL_TEMPUSE>::
findFirstUnbalEl(Element * element)1551 findFirstUnbalEl(Element *element)
1552 {
1553 if ( element == 0 )
1554 return 0;
1555
1556 while ( element != 0 )
1557 {
1558 long lheight = element->BASE_EL(left) ?
1559 element->BASE_EL(left)->BASE_EL(height) : 0;
1560 long rheight = element->BASE_EL(right) ?
1561 element->BASE_EL(right)->BASE_EL(height) : 0;
1562 long balanceProp = lheight - rheight;
1563
1564 if ( balanceProp < -1 || balanceProp > 1 )
1565 return element;
1566
1567 element = element->BASE_EL(parent);
1568 }
1569 return 0;
1570 }
1571
1572 /* Replace a element in the tree with another element not in the tree. */
1573 template <AVLMEL_TEMPDEF> void AvlTree<AVLMEL_TEMPUSE>::
replaceEl(Element * element,Element * replacement)1574 replaceEl(Element *element, Element *replacement)
1575 {
1576 Element *parent = element->BASE_EL(parent),
1577 *left = element->BASE_EL(left),
1578 *right = element->BASE_EL(right);
1579
1580 replacement->BASE_EL(left) = left;
1581 if (left)
1582 left->BASE_EL(parent) = replacement;
1583 replacement->BASE_EL(right) = right;
1584 if (right)
1585 right->BASE_EL(parent) = replacement;
1586
1587 replacement->BASE_EL(parent) = parent;
1588 if (parent)
1589 {
1590 if (parent->BASE_EL(left) == element)
1591 parent->BASE_EL(left) = replacement;
1592 else
1593 parent->BASE_EL(right) = replacement;
1594 }
1595 else
1596 root = replacement;
1597
1598 replacement->BASE_EL(height) = element->BASE_EL(height);
1599 }
1600
1601 /* Removes a element from a tree and puts filler in it's place.
1602 * Filler should be null or a child of element. */
1603 template <AVLMEL_TEMPDEF> void AvlTree<AVLMEL_TEMPUSE>::
removeEl(Element * element,Element * filler)1604 removeEl(Element *element, Element *filler)
1605 {
1606 Element *parent = element->BASE_EL(parent);
1607
1608 if (parent)
1609 {
1610 if (parent->BASE_EL(left) == element)
1611 parent->BASE_EL(left) = filler;
1612 else
1613 parent->BASE_EL(right) = filler;
1614 }
1615 else
1616 root = filler;
1617
1618 if (filler)
1619 filler->BASE_EL(parent) = parent;
1620
1621 return;
1622 }
1623
1624 #ifdef AAPL_NAMESPACE
1625 }
1626 #endif
1627