aapl/avlcommon.h

   1 /*
   2  *  Copyright 2001 Adrian Thurston <thurston@cs.queensu.ca>
   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 {
 106         AvliMapEl(const Key &key)
 107                 : key(key) { }
 108         AvliMapEl(const Key &key, const Value &value)
 109                 : key(key), value(value) { }
 110
 111         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 {
 129         AvlMapEl(const Key &key)
 130                 : key(key) { }
 131         AvlMapEl(const Key &key, const Value &value)
 132                 : key(key), value(value) { }
 133
 134         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 {
 155         AvliSetEl(const Key &key) : key(key) { }
 156
 157         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 {
 171         AvlSetEl(const Key &key) : key(key) { }
 172
 173         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
 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          */
 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          */
 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. */
 314         long length() const         { return treeSize; }
 315
 316         /** \brief Return the number of elements in the tree. */
 317         long size() const           { return treeSize; }
 318
 319         /* Various classes for setting the iterator */
 320         struct Iter;
 321         struct IterFirst { IterFirst( const AvlTree &t ) : t(t) { } const AvlTree &t; };
 322         struct IterLast { IterLast( const AvlTree &t ) : t(t) { } const AvlTree &t; };
 323         struct IterNext { IterNext( const Iter &i ) : i(i) { } const Iter &i; };
 324         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. */
 334                 Iter() : ptr(0) { }
 335
 336                 /* Construct from an avl tree and iterator-setting classes. */
 337                 Iter( const AvlTree &t ) : ptr(t.head) { }
 338                 Iter( const IterFirst &af ) : ptr(af.t.head) { }
 339                 Iter( const IterLast &al ) : ptr(al.t.tail) { }
 340                 Iter( const IterNext &an ) : ptr(findNext(an.i.ptr)) { }
 341                 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? */
 351                 bool lte() const { return ptr != 0; }
 352
 353                 /** \brief At end? */
 354                 bool end() const { return ptr == 0; }
 355
 356                 /** \brief Greater than beginning? */
 357                 bool gtb() const { return ptr != 0; }
 358
 359                 /** \brief At beginning? */
 360                 bool beg() const { return ptr == 0; }
 361
 362                 /** \brief At first element? */
 363                 bool first() const { return ptr && ptr->BASE_EL(prev) == 0; }
 364
 365                 /** \brief At last element? */
 366                 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. */
 396                 IterNext next() const { return IterNext( *this ); }
 397
 398                 /** \brief Return the previous item. Does not modify this. */
 399                 IterPrev prev() const { return IterPrev( *this ); }
 400
 401         private:
 402                 static Element *findPrev( Element *element ) { return element->BASE_EL(prev); }
 403                 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. */
 420                 Iter() : ptr(0), tree(0) { }
 421
 422                 /* Construct from a tree and iterator-setting classes. */
 423                 Iter( const AvlTree &t ) : ptr(t.head), tree(&t) { }
 424                 Iter( const IterFirst &af ) : ptr(af.t.head), tree(&af.t) { }
 425                 Iter( const IterLast &al ) : ptr(al.t.tail), tree(&al.t) { }
 426                 Iter( const IterNext &an ) : ptr(findNext(an.i.ptr)), tree(an.i.tree) { }
 427                 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? */
 442                 bool lte() const { return ptr != 0; }
 443
 444                 /** \brief At end? */
 445                 bool end() const { return ptr == 0; }
 446
 447                 /** \brief Greater than beginning? */
 448                 bool gtb() const { return ptr != 0; }
 449
 450                 /** \brief At beginning? */
 451                 bool beg() const { return ptr == 0; }
 452
 453                 /** \brief At first element? */
 454                 bool first() const { return ptr && ptr == tree->head; }
 455
 456                 /** \brief At last element? */
 457                 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. */
 487                 IterNext next() const { return IterNext( *this ); }
 488
 489                 /** \brief Return the previous item. Does not modify this. */
 490                 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. */
 507         IterFirst first()  { return IterFirst( *this ); }
 508
 509         /** \brief Return last element. */
 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>::
 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>::
 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::shallowCopy( other );
 602 #else
 603         head = other.head;
 604         tail = other.tail;
 605 #endif
 606
 607         other.abandon();
 608 }
 609
 610 #else /* ! AVLTREE_MAP && ! AVLTREE_SET */
 611
 612 /* Assignment does deep copy. This version does not clear the tree first. */
 613 template <AVLMEL_TEMPDEF> AvlTree<AVLMEL_TEMPUSE> &AvlTree<AVLMEL_TEMPUSE>::
 614         operator=( const AvlTree &other )
 615 {
 616         /* Reset the list pointers, the tree copy will fill in the list for us. */
 617 #ifdef WALKABLE
 618         BASELIST::abandon();
 619 #else
 620         head = 0;
 621         tail = 0;
 622 #endif
 623
 624         /* Copy the entire tree. */
 625         treeSize = other.treeSize;
 626         root = other.root;
 627         if ( other.root != 0 )
 628                 root = copyBranch( other.root );
 629         return *this;
 630 }
 631
 632 template <AVLMEL_TEMPDEF> void AvlTree<AVLMEL_TEMPUSE>::
 633                 transfer(AvlTree<AVLMEL_TEMPUSE> &other)
 634 {
 635         treeSize = other.treeSize;
 636         root = other.root;
 637
 638 #ifdef WALKABLE
 639         BASELIST::shallowCopy( other );
 640 #else
 641         head = other.head;
 642         tail = other.tail;
 643 #endif
 644
 645         other.abandon();
 646 }
 647
 648 #endif
 649
 650 /*
 651  * Iterator operators.
 652  */
 653
 654 /* Prefix ++ */
 655 template <AVLMEL_TEMPDEF> Element *AvlTree<AVLMEL_TEMPUSE>::Iter::
 656                 operator++()
 657 {
 658         return ptr = findNext( ptr );
 659 }
 660
 661 /* Postfix ++ */
 662 template <AVLMEL_TEMPDEF> Element *AvlTree<AVLMEL_TEMPUSE>::Iter::
 663                 operator++(int)
 664 {
 665         Element *rtn = ptr;
 666         ptr = findNext( ptr );
 667         return rtn;
 668 }
 669
 670 /* increment */
 671 template <AVLMEL_TEMPDEF> Element *AvlTree<AVLMEL_TEMPUSE>::Iter::
 672                 increment()
 673 {
 674         return ptr = findNext( ptr );
 675 }
 676
 677 /* Prefix -- */
 678 template <AVLMEL_TEMPDEF> Element *AvlTree<AVLMEL_TEMPUSE>::Iter::
 679                 operator--()
 680 {
 681         return ptr = findPrev( ptr );
 682 }
 683
 684 /* Postfix -- */
 685 template <AVLMEL_TEMPDEF> Element *AvlTree<AVLMEL_TEMPUSE>::Iter::
 686                 operator--(int)
 687 {
 688         Element *rtn = ptr;
 689         ptr = findPrev( ptr );
 690         return rtn;
 691 }
 692
 693 /* decrement */
 694 template <AVLMEL_TEMPDEF> Element *AvlTree<AVLMEL_TEMPUSE>::Iter::
 695                 decrement()
 696 {
 697         return ptr = findPrev( ptr );
 698 }
 699
 700 #ifndef WALKABLE
 701
 702 /* Move ahead one. */
 703 template <AVLMEL_TEMPDEF> Element *AvlTree<AVLMEL_TEMPUSE>::Iter::
 704                 findNext( Element *element )
 705 {
 706         /* Try to go right once then infinite left. */
 707         if ( element->BASE_EL(right) != 0 ) {
 708                 element = element->BASE_EL(right);
 709                 while ( element->BASE_EL(left) != 0 )
 710                         element = element->BASE_EL(left);
 711         }
 712         else {
 713                 /* Go up to parent until we were just a left child. */
 714                 while ( true ) {
 715                         Element *last = element;
 716                         element = element->BASE_EL(parent);
 717                         if ( element == 0 || element->BASE_EL(left) == last )
 718                                 break;
 719                 }
 720         }
 721         return element;
 722 }
 723
 724 /* Move back one. */
 725 template <AVLMEL_TEMPDEF> Element *AvlTree<AVLMEL_TEMPUSE>::Iter::
 726                 findPrev( Element *element )
 727 {
 728         /* Try to go left once then infinite right. */
 729         if ( element->BASE_EL(left) != 0 ) {
 730                 element = element->BASE_EL(left);
 731                 while ( element->BASE_EL(right) != 0 )
 732                         element = element->BASE_EL(right);
 733         }
 734         else {
 735                 /* Go up to parent until we were just a left child. */
 736                 while ( true ) {
 737                         Element *last = element;
 738                         element = element->BASE_EL(parent);
 739                         if ( element == 0 || element->BASE_EL(right) == last )
 740                                 break;
 741                 }
 742         }
 743         return element;
 744 }
 745
 746 #endif
 747
 748
 749 /* Recursive worker for tree copying. */
 750 template <AVLMEL_TEMPDEF> Element *AvlTree<AVLMEL_TEMPUSE>::
 751                 copyBranch( Element *element )
 752 {
 753         /* Duplicate element. Either the base element's copy constructor or defaul
 754          * constructor will get called. Both will suffice for initting the
 755          * pointers to null when they need to be. */
 756         Element *retVal = new Element(*element);
 757
 758         /* If the left tree is there, copy it. */
 759         if ( retVal->BASE_EL(left) ) {
 760                 retVal->BASE_EL(left) = copyBranch(retVal->BASE_EL(left));
 761                 retVal->BASE_EL(left)->BASE_EL(parent) = retVal;
 762         }
 763
 764 #ifdef WALKABLE
 765         BASELIST::addAfter( BASELIST::tail, retVal );
 766 #else
 767         if ( head == 0 )
 768                 head = retVal;
 769         tail = retVal;
 770 #endif
 771
 772         /* If the right tree is there, copy it. */
 773         if ( retVal->BASE_EL(right) ) {
 774                 retVal->BASE_EL(right) = copyBranch(retVal->BASE_EL(right));
 775                 retVal->BASE_EL(right)->BASE_EL(parent) = retVal;
 776         }
 777         return retVal;
 778 }
 779
 780 /* Once an insertion position is found, attach a element to the tree. */
 781 template <AVLMEL_TEMPDEF> void AvlTree<AVLMEL_TEMPUSE>::
 782                 attachRebal( Element *element, Element *parentEl, Element *lastLess )
 783 {
 784         /* Increment the number of element in the tree. */
 785         treeSize += 1;
 786
 787         /* Set element's parent. */
 788         element->BASE_EL(parent) = parentEl;
 789
 790         /* New element always starts as a leaf with height 1. */
 791         element->BASE_EL(left) = 0;
 792         element->BASE_EL(right) = 0;
 793         element->BASE_EL(height) = 1;
 794
 795         /* Are we inserting in the tree somewhere? */
 796         if ( parentEl != 0 ) {
 797                 /* We have a parent so we are somewhere in the tree. If the parent
 798                  * equals lastLess, then the last traversal in the insertion went
 799                  * left, otherwise it went right. */
 800                 if ( lastLess == parentEl ) {
 801                         parentEl->BASE_EL(left) = element;
 802 #ifdef WALKABLE
 803                         BASELIST::addBefore( parentEl, element );
 804 #endif
 805                 }
 806                 else {
 807                         parentEl->BASE_EL(right) = element;
 808 #ifdef WALKABLE
 809                         BASELIST::addAfter( parentEl, element );
 810 #endif
 811                 }
 812
 813 #ifndef WALKABLE
 814                 /* Maintain the first and last pointers. */
 815                 if ( head->BASE_EL(left) == element )
 816                         head = element;
 817
 818                 /* Maintain the first and last pointers. */
 819                 if ( tail->BASE_EL(right) == element )
 820                         tail = element;
 821 #endif
 822         }
 823         else {
 824                 /* No parent element so we are inserting the root. */
 825                 root = element;
 826 #ifdef WALKABLE
 827                 BASELIST::addAfter( BASELIST::tail, element );
 828 #else
 829                 head = tail = element;
 830 #endif
 831         }
 832
 833
 834         /* Recalculate the heights. */
 835         recalcHeights(parentEl);
 836
 837         /* Find the first unbalance. */
 838         Element *ub = findFirstUnbalGP(element);
 839
 840         /* rebalance. */
 841         if ( ub != 0 )
 842         {
 843                 /* We assert that after this single rotation the
 844                  * tree is now properly balanced. */
 845                 rebalance(ub);
 846         }
 847 }
 848
 849 #ifndef AVL_KEYLESS
 850
 851 /**
 852  * \brief Insert an existing element into the tree.
 853  *
 854  * If the insert succeeds and lastFound is given then it is set to the element
 855  * inserted. If the insert fails then lastFound is set to the existing element in
 856  * the tree that has the same key as element. If the element's avl pointers are
 857  * already in use then undefined behaviour results.
 858  *
 859  * \returns The element inserted upon success, null upon failure.
 860  */
 861 template <AVLMEL_TEMPDEF> Element *AvlTree<AVLMEL_TEMPUSE>::
 862                 insert( Element *element, Element **lastFound )
 863 {
 864         long keyRelation;
 865         Element *curEl = root, *parentEl = 0;
 866         Element *lastLess = 0;
 867
 868         while (true) {
 869                 if ( curEl == 0 ) {
 870                         /* We are at an external element and did not find the key we were
 871                          * looking for. Attach underneath the leaf and rebalance. */
 872                         attachRebal( element, parentEl, lastLess );
 873
 874                         if ( lastFound != 0 )
 875                                 *lastFound = element;
 876                         return element;
 877                 }
 878
 879 #ifdef AVL_BASIC
 880                 keyRelation = compare( *element, *curEl );
 881 #else
 882                 keyRelation = compare( element->BASEKEY(getKey()),
 883                                 curEl->BASEKEY(getKey()) );
 884 #endif
 885
 886                 /* Do we go left? */
 887                 if ( keyRelation < 0 ) {
 888                         parentEl = lastLess = curEl;
 889                         curEl = curEl->BASE_EL(left);
 890                 }
 891                 /* Do we go right? */
 892                 else if ( keyRelation > 0 ) {
 893                         parentEl = curEl;
 894                         curEl = curEl->BASE_EL(right);
 895                 }
 896                 /* We have hit the target. */
 897                 else {
 898                         if ( lastFound != 0 )
 899                                 *lastFound = curEl;
 900                         return 0;
 901                 }
 902         }
 903 }
 904
 905 #ifdef AVL_BASIC
 906
 907 /**
 908  * \brief Find a element in the tree with the given key.
 909  *
 910  * \returns The element if key exists, null if the key does not exist.
 911  */
 912 template <AVLMEL_TEMPDEF> Element *AvlTree<AVLMEL_TEMPUSE>::
 913                 find( const Element *element ) const
 914 {
 915         Element *curEl = root;
 916         long keyRelation;
 917
 918         while (curEl) {
 919                 keyRelation = compare( *element, *curEl );
 920
 921                 /* Do we go left? */
 922                 if ( keyRelation < 0 )
 923                         curEl = curEl->BASE_EL(left);
 924                 /* Do we go right? */
 925                 else if ( keyRelation > 0 )
 926                         curEl = curEl->BASE_EL(right);
 927                 /* We have hit the target. */
 928                 else {
 929                         return curEl;
 930                 }
 931         }
 932         return 0;
 933 }
 934
 935 #else
 936
 937 /**
 938  * \brief Insert a new element into the tree with given key.
 939  *
 940  * If the key is not already in the tree then a new element is made using the
 941  * Element(const Key &key) constructor and the insert succeeds. If lastFound is
 942  * given then it is set to the element inserted. If the insert fails then
 943  * lastFound is set to the existing element in the tree that has the same key as
 944  * element.
 945  *
 946  * \returns The new element upon success, null upon failure.
 947  */
 948 template <AVLMEL_TEMPDEF> Element *AvlTree<AVLMEL_TEMPUSE>::
 949                 insert( const Key &key, Element **lastFound )
 950 {
 951         long keyRelation;
 952         Element *curEl = root, *parentEl = 0;
 953         Element *lastLess = 0;
 954
 955         while (true) {
 956                 if ( curEl == 0 ) {
 957                         /* We are at an external element and did not find the key we were
 958                          * looking for. Create the new element, attach it underneath the leaf
 959                          * and rebalance. */
 960                         Element *element = new Element( key );
 961                         attachRebal( element, parentEl, lastLess );
 962
 963                         if ( lastFound != 0 )
 964                                 *lastFound = element;
 965                         return element;
 966                 }
 967
 968                 keyRelation = compare( key, curEl->BASEKEY(getKey()) );
 969
 970                 /* Do we go left? */
 971                 if ( keyRelation < 0 ) {
 972                         parentEl = lastLess = curEl;
 973                         curEl = curEl->BASE_EL(left);
 974                 }
 975                 /* Do we go right? */
 976                 else if ( keyRelation > 0 ) {
 977                         parentEl = curEl;
 978                         curEl = curEl->BASE_EL(right);
 979                 }
 980                 /* We have hit the target. */
 981                 else {
 982                         if ( lastFound != 0 )
 983                                 *lastFound = curEl;
 984                         return 0;
 985                 }
 986         }
 987 }
 988
 989 #ifdef AVLTREE_MAP
 990 /**
 991  * \brief Insert a new element into the tree with key and value.
 992  *
 993  * If the key is not already in the tree then a new element is constructed and
 994  * the insert succeeds. If lastFound is given then it is set to the element
 995  * inserted. If the insert fails then lastFound is set to the existing element in
 996  * the tree that has the same key as element. This insert routine is only
 997  * available in AvlMap because it is the only class that knows about a Value
 998  * type.
 999  *
1000  * \returns The new element upon success, null upon failure.
1001  */
1002 template <AVLMEL_TEMPDEF> Element *AvlTree<AVLMEL_TEMPUSE>::
1003                 insert( const Key &key, const Value &val, Element **lastFound )
1004 {
1005         long keyRelation;
1006         Element *curEl = root, *parentEl = 0;
1007         Element *lastLess = 0;
1008
1009         while (true) {
1010                 if ( curEl == 0 ) {
1011                         /* We are at an external element and did not find the key we were
1012                          * looking for. Create the new element, attach it underneath the leaf
1013                          * and rebalance. */
1014                         Element *element = new Element( key, val );
1015                         attachRebal( element, parentEl, lastLess );
1016
1017                         if ( lastFound != 0 )
1018                                 *lastFound = element;
1019                         return element;
1020                 }
1021
1022                 keyRelation = compare(key, curEl->getKey());
1023
1024                 /* Do we go left? */
1025                 if ( keyRelation < 0 ) {
1026                         parentEl = lastLess = curEl;
1027                         curEl = curEl->BASE_EL(left);
1028                 }
1029                 /* Do we go right? */
1030                 else if ( keyRelation > 0 ) {
1031                         parentEl = curEl;
1032                         curEl = curEl->BASE_EL(right);
1033                 }
1034                 /* We have hit the target. */
1035                 else {
1036                         if ( lastFound != 0 )
1037                                 *lastFound = curEl;
1038                         return 0;
1039                 }
1040         }
1041 }
1042 #endif /* AVLTREE_MAP */
1043
1044
1045 /**
1046  * \brief Find a element in the tree with the given key.
1047  *
1048  * \returns The element if key exists, null if the key does not exist.
1049  */
1050 template <AVLMEL_TEMPDEF> Element *AvlTree<AVLMEL_TEMPUSE>::
1051                 find( const Key &key ) const
1052 {
1053         Element *curEl = root;
1054         long keyRelation;
1055
1056         while (curEl) {
1057                 keyRelation = compare( key, curEl->BASEKEY(getKey()) );
1058
1059                 /* Do we go left? */
1060                 if ( keyRelation < 0 )
1061                         curEl = curEl->BASE_EL(left);
1062                 /* Do we go right? */
1063                 else if ( keyRelation > 0 )
1064                         curEl = curEl->BASE_EL(right);
1065                 /* We have hit the target. */
1066                 else {
1067                         return curEl;
1068                 }
1069         }
1070         return 0;
1071 }
1072
1073
1074 /**
1075  * \brief Find a element, then detach it from the tree.
1076  *
1077  * The element is not deleted.
1078  *
1079  * \returns The element detached if the key is found, othewise returns null.
1080  */
1081 template <AVLMEL_TEMPDEF> Element *AvlTree<AVLMEL_TEMPUSE>::
1082                 detach(const Key &key)
1083 {
1084         Element *element = find( key );
1085         if ( element ) {
1086                 detach(element);
1087         }
1088
1089         return element;
1090 }
1091
1092 /**
1093  * \brief Find, detach and delete a element from the tree.
1094  *
1095  * \returns True if the element was found and deleted, false otherwise.
1096  */
1097 template <AVLMEL_TEMPDEF> bool AvlTree<AVLMEL_TEMPUSE>::
1098                 remove(const Key &key)
1099 {
1100         /* Assume not found. */
1101         bool retVal = false;
1102
1103         /* Look for the key. */
1104         Element *element = find( key );
1105         if ( element != 0 ) {
1106                 /* If found, detach the element and delete. */
1107                 detach( element );
1108                 delete element;
1109                 retVal = true;
1110         }
1111
1112         return retVal;
1113 }
1114
1115 #endif /* AVL_BASIC */
1116 #endif /* AVL_KEYLESS */
1117
1118
1119 /**
1120  * \brief Detach and delete a element from the tree.
1121  *
1122  * If the element is not in the tree then undefined behaviour results.
1123  */
1124 template <AVLMEL_TEMPDEF> void AvlTree<AVLMEL_TEMPUSE>::
1125                 remove(Element *element)
1126 {
1127         /* Detach and delete. */
1128         detach(element);
1129         delete element;
1130 }
1131
1132 /**
1133  * \brief Detach a element from the tree.
1134  *
1135  * If the element is not in the tree then undefined behaviour results.
1136  *
1137  * \returns The element given.
1138  */
1139 template <AVLMEL_TEMPDEF> Element *AvlTree<AVLMEL_TEMPUSE>::
1140                 detach(Element *element)
1141 {
1142         Element *replacement, *fixfrom;
1143         long lheight, rheight;
1144
1145 #ifdef WALKABLE
1146         /* Remove the element from the ordered list. */
1147         BASELIST::detach( element );
1148 #endif
1149
1150         /* Update treeSize. */
1151         treeSize--;
1152
1153         /* Find a replacement element. */
1154         if (element->BASE_EL(right))
1155         {
1156                 /* Find the leftmost element of the right subtree. */
1157                 replacement = element->BASE_EL(right);
1158                 while (replacement->BASE_EL(left))
1159                         replacement = replacement->BASE_EL(left);
1160
1161                 /* If replacing the element the with its child then we need to start
1162                  * fixing at the replacement, otherwise we start fixing at the
1163                  * parent of the replacement. */
1164                 if (replacement->BASE_EL(parent) == element)
1165                         fixfrom = replacement;
1166                 else
1167                         fixfrom = replacement->BASE_EL(parent);
1168
1169 #ifndef WALKABLE
1170                 if ( element == head )
1171                         head = replacement;
1172 #endif
1173
1174                 removeEl(replacement, replacement->BASE_EL(right));
1175                 replaceEl(element, replacement);
1176         }
1177         else if (element->BASE_EL(left))
1178         {
1179                 /* Find the rightmost element of the left subtree. */
1180                 replacement = element->BASE_EL(left);
1181                 while (replacement->BASE_EL(right))
1182                         replacement = replacement->BASE_EL(right);
1183
1184                 /* If replacing the element the with its child then we need to start
1185                  * fixing at the replacement, otherwise we start fixing at the
1186                  * parent of the replacement. */
1187                 if (replacement->BASE_EL(parent) == element)
1188                         fixfrom = replacement;
1189                 else
1190                         fixfrom = replacement->BASE_EL(parent);
1191
1192 #ifndef WALKABLE
1193                 if ( element == tail )
1194                         tail = replacement;
1195 #endif
1196
1197                 removeEl(replacement, replacement->BASE_EL(left));
1198                 replaceEl(element, replacement);
1199         }
1200         else
1201         {
1202                 /* We need to start fixing at the parent of the element. */
1203                 fixfrom = element->BASE_EL(parent);
1204
1205 #ifndef WALKABLE
1206                 if ( element == head )
1207                         head = element->BASE_EL(parent);
1208                 if ( element == tail )
1209                         tail = element->BASE_EL(parent);
1210 #endif
1211
1212                 /* The element we are deleting is a leaf element. */
1213                 removeEl(element, 0);
1214         }
1215
1216         /* If fixfrom is null it means we just deleted
1217          * the root of the tree. */
1218         if ( fixfrom == 0 )
1219                 return element;
1220
1221         /* Fix the heights after the deletion. */
1222         recalcHeights(fixfrom);
1223
1224         /* Fix every unbalanced element going up in the tree. */
1225         Element *ub = findFirstUnbalEl(fixfrom);
1226         while ( ub )
1227         {
1228                 /* Find the element to rebalance by moving down from the first unbalanced
1229                  * element 2 levels in the direction of the greatest heights. On the
1230                  * second move down, the heights may be equal ( but not on the first ).
1231                  * In which case go in the direction of the first move. */
1232                 lheight = ub->BASE_EL(left) ? ub->BASE_EL(left)->BASE_EL(height) : 0;
1233                 rheight = ub->BASE_EL(right) ? ub->BASE_EL(right)->BASE_EL(height) : 0;
1234                 assert( lheight != rheight );
1235                 if (rheight > lheight)
1236                 {
1237                         ub = ub->BASE_EL(right);
1238                         lheight = ub->BASE_EL(left) ?
1239                                         ub->BASE_EL(left)->BASE_EL(height) : 0;
1240                         rheight = ub->BASE_EL(right) ?
1241                                         ub->BASE_EL(right)->BASE_EL(height) : 0;
1242                         if (rheight > lheight)
1243                                 ub = ub->BASE_EL(right);
1244                         else if (rheight < lheight)
1245                                 ub = ub->BASE_EL(left);
1246                         else
1247                                 ub = ub->BASE_EL(right);
1248                 }
1249                 else
1250                 {
1251                         ub = ub->BASE_EL(left);
1252                         lheight = ub->BASE_EL(left) ?
1253                                         ub->BASE_EL(left)->BASE_EL(height) : 0;
1254                         rheight = ub->BASE_EL(right) ?
1255                                         ub->BASE_EL(right)->BASE_EL(height) : 0;
1256                         if (rheight > lheight)
1257                                 ub = ub->BASE_EL(right);
1258                         else if (rheight < lheight)
1259                                 ub = ub->BASE_EL(left);
1260                         else
1261                                 ub = ub->BASE_EL(left);
1262                 }
1263
1264
1265                 /* rebalance returns the grandparant of the subtree formed
1266                  * by the element that were rebalanced.
1267                  * We must continue upward from there rebalancing. */
1268                 fixfrom = rebalance(ub);
1269
1270                 /* Find the next unbalaced element. */
1271                 ub = findFirstUnbalEl(fixfrom);
1272         }
1273
1274         return element;
1275 }
1276
1277
1278 /**
1279  * \brief Empty the tree and delete all the element.
1280  *
1281  * Resets the tree to its initial state.
1282  */
1283 template <AVLMEL_TEMPDEF> void AvlTree<AVLMEL_TEMPUSE>::empty()
1284 {
1285         if ( root ) {
1286                 /* Recursively delete from the tree structure. */
1287                 deleteChildrenOf(root);
1288                 delete root;
1289                 root = 0;
1290                 treeSize = 0;
1291
1292 #ifdef WALKABLE
1293                 BASELIST::abandon();
1294 #endif
1295         }
1296 }
1297
1298 /**
1299  * \brief Forget all element in the tree.
1300  *
1301  * Does not delete element. Resets the the tree to it's initial state.
1302  */
1303 template <AVLMEL_TEMPDEF> void AvlTree<AVLMEL_TEMPUSE>::abandon()
1304 {
1305         root = 0;
1306         treeSize = 0;
1307
1308 #ifdef WALKABLE
1309         BASELIST::abandon();
1310 #endif
1311 }
1312
1313 /* Recursively delete all the children of a element. */
1314 template <AVLMEL_TEMPDEF> void AvlTree<AVLMEL_TEMPUSE>::
1315                 deleteChildrenOf( Element *element )
1316 {
1317         /* Recurse left. */
1318         if (element->BASE_EL(left)) {
1319                 deleteChildrenOf(element->BASE_EL(left));
1320
1321                 /* Delete left element. */
1322                 delete element->BASE_EL(left);
1323                 element->BASE_EL(left) = 0;
1324         }
1325
1326         /* Recurse right. */
1327         if (element->BASE_EL(right)) {
1328                 deleteChildrenOf(element->BASE_EL(right));
1329
1330                 /* Delete right element. */
1331                 delete element->BASE_EL(right);
1332                 element->BASE_EL(left) = 0;
1333         }
1334 }
1335
1336 /* rebalance from a element whose gradparent is unbalanced. Only
1337  * call on a element that has a grandparent. */
1338 template <AVLMEL_TEMPDEF> Element *AvlTree<AVLMEL_TEMPUSE>::
1339                 rebalance(Element *n)
1340 {
1341         long lheight, rheight;
1342         Element *a, *b, *c;
1343         Element *t1, *t2, *t3, *t4;
1344
1345         Element *p = n->BASE_EL(parent);      /* parent (Non-NUL). L*/
1346         Element *gp = p->BASE_EL(parent);     /* Grand-parent (Non-NULL). */
1347         Element *ggp = gp->BASE_EL(parent);   /* Great grand-parent (may be NULL). */
1348
1349         if (gp->BASE_EL(right) == p)
1350         {
1351                 /*  gp
1352                  *   \
1353                  *    p
1354                  */
1355                 if (p->BASE_EL(right) == n)
1356                 {
1357                         /*  gp
1358                          *   \
1359                          *    p
1360                          *     \
1361                          *      n
1362                          */
1363                         a = gp;
1364                         b = p;
1365                         c = n;
1366                         t1 = gp->BASE_EL(left);
1367                         t2 = p->BASE_EL(left);
1368                         t3 = n->BASE_EL(left);
1369                         t4 = n->BASE_EL(right);
1370                 }
1371                 else
1372                 {
1373                         /*  gp
1374                          *     \
1375                          *       p
1376                          *      /
1377                          *     n
1378                          */
1379                         a = gp;
1380                         b = n;
1381                         c = p;
1382                         t1 = gp->BASE_EL(left);
1383                         t2 = n->BASE_EL(left);
1384                         t3 = n->BASE_EL(right);
1385                         t4 = p->BASE_EL(right);
1386                 }
1387         }
1388         else
1389         {
1390                 /*    gp
1391                  *   /
1392                  *  p
1393                  */
1394                 if (p->BASE_EL(right) == n)
1395                 {
1396                         /*      gp
1397                          *    /
1398                          *  p
1399                          *   \
1400                          *    n
1401                          */
1402                         a = p;
1403                         b = n;
1404                         c = gp;
1405                         t1 = p->BASE_EL(left);
1406                         t2 = n->BASE_EL(left);
1407                         t3 = n->BASE_EL(right);
1408                         t4 = gp->BASE_EL(right);
1409                 }
1410                 else
1411                 {
1412                         /*      gp
1413                          *     /
1414                          *    p
1415                          *   /
1416                          *  n
1417                          */
1418                         a = n;
1419                         b = p;
1420                         c = gp;
1421                         t1 = n->BASE_EL(left);
1422                         t2 = n->BASE_EL(right);
1423                         t3 = p->BASE_EL(right);
1424                         t4 = gp->BASE_EL(right);
1425                 }
1426         }
1427
1428         /* Perform rotation.
1429          */
1430
1431         /* Tie b to the great grandparent. */
1432         if ( ggp == 0 )
1433                 root = b;
1434         else if ( ggp->BASE_EL(left) == gp )
1435                 ggp->BASE_EL(left) = b;
1436         else
1437                 ggp->BASE_EL(right) = b;
1438         b->BASE_EL(parent) = ggp;
1439
1440         /* Tie a as a leftchild of b. */
1441         b->BASE_EL(left) = a;
1442         a->BASE_EL(parent) = b;
1443
1444         /* Tie c as a rightchild of b. */
1445         b->BASE_EL(right) = c;
1446         c->BASE_EL(parent) = b;
1447
1448         /* Tie t1 as a leftchild of a. */
1449         a->BASE_EL(left) = t1;
1450         if ( t1 != 0 ) t1->BASE_EL(parent) = a;
1451
1452         /* Tie t2 as a rightchild of a. */
1453         a->BASE_EL(right) = t2;
1454         if ( t2 != 0 ) t2->BASE_EL(parent) = a;
1455
1456         /* Tie t3 as a leftchild of c. */
1457         c->BASE_EL(left) = t3;
1458         if ( t3 != 0 ) t3->BASE_EL(parent) = c;
1459
1460         /* Tie t4 as a rightchild of c. */
1461         c->BASE_EL(right) = t4;
1462         if ( t4 != 0 ) t4->BASE_EL(parent) = c;
1463
1464         /* The heights are all recalculated manualy and the great
1465          * grand-parent is passed to recalcHeights() to ensure
1466          * the heights are correct up the tree.
1467          *
1468          * Note that recalcHeights() cuts out when it comes across
1469          * a height that hasn't changed.
1470          */
1471
1472         /* Fix height of a. */
1473         lheight = a->BASE_EL(left) ? a->BASE_EL(left)->BASE_EL(height) : 0;
1474         rheight = a->BASE_EL(right) ? a->BASE_EL(right)->BASE_EL(height) : 0;
1475         a->BASE_EL(height) = (lheight > rheight ? lheight : rheight) + 1;
1476
1477         /* Fix height of c. */
1478         lheight = c->BASE_EL(left) ? c->BASE_EL(left)->BASE_EL(height) : 0;
1479         rheight = c->BASE_EL(right) ? c->BASE_EL(right)->BASE_EL(height) : 0;
1480         c->BASE_EL(height) = (lheight > rheight ? lheight : rheight) + 1;
1481
1482         /* Fix height of b. */
1483         lheight = a->BASE_EL(height);
1484         rheight = c->BASE_EL(height);
1485         b->BASE_EL(height) = (lheight > rheight ? lheight : rheight) + 1;
1486
1487         /* Fix height of b's parents. */
1488         recalcHeights(ggp);
1489         return ggp;
1490 }
1491
1492 /* Recalculates the heights of all the ancestors of element. */
1493 template <AVLMEL_TEMPDEF> void AvlTree<AVLMEL_TEMPUSE>::
1494                 recalcHeights(Element *element)
1495 {
1496         long lheight, rheight, new_height;
1497         while ( element != 0 )
1498         {
1499                 lheight = element->BASE_EL(left) ? element->BASE_EL(left)->BASE_EL(height) : 0;
1500                 rheight = element->BASE_EL(right) ? element->BASE_EL(right)->BASE_EL(height) : 0;
1501
1502                 new_height = (lheight > rheight ? lheight : rheight) + 1;
1503
1504                 /* If there is no chage in the height, then there will be no
1505                  * change in any of the ancestor's height. We can stop going up.
1506                  * If there was a change, continue upward. */
1507                 if (new_height == element->BASE_EL(height))
1508                         return;
1509                 else
1510                         element->BASE_EL(height) = new_height;
1511
1512                 element = element->BASE_EL(parent);
1513         }
1514 }
1515
1516 /* Finds the first element whose grandparent is unbalanced. */
1517 template <AVLMEL_TEMPDEF> Element *AvlTree<AVLMEL_TEMPUSE>::
1518                 findFirstUnbalGP(Element *element)
1519 {
1520         long lheight, rheight, balanceProp;
1521         Element *gp;
1522
1523         if ( element == 0 || element->BASE_EL(parent) == 0 ||
1524                         element->BASE_EL(parent)->BASE_EL(parent) == 0 )
1525                 return 0;
1526
1527         /* Don't do anything if we we have no grandparent. */
1528         gp = element->BASE_EL(parent)->BASE_EL(parent);
1529         while ( gp != 0 )
1530         {
1531                 lheight = gp->BASE_EL(left) ? gp->BASE_EL(left)->BASE_EL(height) : 0;
1532                 rheight = gp->BASE_EL(right) ? gp->BASE_EL(right)->BASE_EL(height) : 0;
1533                 balanceProp = lheight - rheight;
1534
1535                 if ( balanceProp < -1 || balanceProp > 1 )
1536                         return element;
1537
1538                 element = element->BASE_EL(parent);
1539                 gp = gp->BASE_EL(parent);
1540         }
1541         return 0;
1542 }
1543
1544
1545 /* Finds the first element that is unbalanced. */
1546 template <AVLMEL_TEMPDEF> Element *AvlTree<AVLMEL_TEMPUSE>::
1547                 findFirstUnbalEl(Element *element)
1548 {
1549         if ( element == 0 )
1550                 return 0;
1551
1552         while ( element != 0 )
1553         {
1554                 long lheight = element->BASE_EL(left) ?
1555                                 element->BASE_EL(left)->BASE_EL(height) : 0;
1556                 long rheight = element->BASE_EL(right) ?
1557                                 element->BASE_EL(right)->BASE_EL(height) : 0;
1558                 long balanceProp = lheight - rheight;
1559
1560                 if ( balanceProp < -1 || balanceProp > 1 )
1561                         return element;
1562
1563                 element = element->BASE_EL(parent);
1564         }
1565         return 0;
1566 }
1567
1568 /* Replace a element in the tree with another element not in the tree. */
1569 template <AVLMEL_TEMPDEF> void AvlTree<AVLMEL_TEMPUSE>::
1570                 replaceEl(Element *element, Element *replacement)
1571 {
1572         Element *parent = element->BASE_EL(parent),
1573                 *left = element->BASE_EL(left),
1574                 *right = element->BASE_EL(right);
1575
1576         replacement->BASE_EL(left) = left;
1577         if (left)
1578                 left->BASE_EL(parent) = replacement;
1579         replacement->BASE_EL(right) = right;
1580         if (right)
1581                 right->BASE_EL(parent) = replacement;
1582
1583         replacement->BASE_EL(parent) = parent;
1584         if (parent)
1585         {
1586                 if (parent->BASE_EL(left) == element)
1587                         parent->BASE_EL(left) = replacement;
1588                 else
1589                         parent->BASE_EL(right) = replacement;
1590         }
1591         else
1592                 root = replacement;
1593
1594         replacement->BASE_EL(height) = element->BASE_EL(height);
1595 }
1596
1597 /* Removes a element from a tree and puts filler in it's place.
1598  * Filler should be null or a child of element. */
1599 template <AVLMEL_TEMPDEF> void AvlTree<AVLMEL_TEMPUSE>::
1600                 removeEl(Element *element, Element *filler)
1601 {
1602         Element *parent = element->BASE_EL(parent);
1603
1604         if (parent)
1605         {
1606                 if (parent->BASE_EL(left) == element)
1607                         parent->BASE_EL(left) = filler;
1608                 else
1609                         parent->BASE_EL(right) = filler;
1610         }
1611         else
1612                 root = filler;
1613
1614         if (filler)
1615                 filler->BASE_EL(parent) = parent;
1616
1617         return;
1618 }
1619
1620 #ifdef AAPL_NAMESPACE
1621 }
1622 #endif