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::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>::
 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::
 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::
 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::
 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::
 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>::
 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>::
 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>::
 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 = compare( *element, *curEl );
 885 #else
 886                 keyRelation = 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>::
 917                 find( const Element *element ) const
 918 {
 919         Element *curEl = root;
 920         long keyRelation;
 921
 922         while (curEl) {
 923                 keyRelation = 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>::
 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 = 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>::
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 = 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>::
1055                 find( const Key &key ) const
1056 {
1057         Element *curEl = root;
1058         long keyRelation;
1059
1060         while (curEl) {
1061                 keyRelation = 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>::
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>::
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>::
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>::
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  */
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  */
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>::
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>::
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>::
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>::
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>::
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>::
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>::
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