wtf/AVLTree.h

   1 /*
   2  * Copyright (C) 2008 Apple Inc. All rights reserved.
   3  *
   4  * Based on Abstract AVL Tree Template v1.5 by Walt Karas
   5  * <http://geocities.com/wkaras/gen_cpp/avl_tree.html>.
   6  *
   7  * Redistribution and use in source and binary forms, with or without
   8  * modification, are permitted provided that the following conditions
   9  * are met:
  10  *
  11  * 1.  Redistributions of source code must retain the above copyright
  12  *     notice, this list of conditions and the following disclaimer.
  13  * 2.  Redistributions in binary form must reproduce the above copyright
  14  *     notice, this list of conditions and the following disclaimer in the
  15  *     documentation and/or other materials provided with the distribution.
  16  * 3.  Neither the name of Apple Computer, Inc. ("Apple") nor the names of
  17  *     its contributors may be used to endorse or promote products derived
  18  *     from this software without specific prior written permission.
  19  *
  20  * THIS SOFTWARE IS PROVIDED BY APPLE AND ITS CONTRIBUTORS "AS IS" AND ANY
  21  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
  22  * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
  23  * DISCLAIMED. IN NO EVENT SHALL APPLE OR ITS CONTRIBUTORS BE LIABLE FOR ANY
  24  * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
  25  * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
  26  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
  27  * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  28  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
  29  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  30  */
  31
  32 #ifndef AVL_TREE_H_
  33 #define AVL_TREE_H_
  34
  35 #include "Assertions.h"
  36 #include <wtf/FixedArray.h>
  37
  38 namespace WTF {
  39
  40 // Here is the reference class for BSet.
  41 //
  42 // class BSet
  43 //   {
  44 //   public:
  45 //
  46 //     class ANY_bitref
  47 //       {
  48 //       public:
  49 //         operator bool ();
  50 //         void operator = (bool b);
  51 //       };
  52 //
  53 //     // Does not have to initialize bits.
  54 //     BSet();
  55 //
  56 //     // Must return a valid value for index when 0 <= index < maxDepth
  57 //     ANY_bitref operator [] (unsigned index);
  58 //
  59 //     // Set all bits to 1.
  60 //     void set();
  61 //
  62 //     // Set all bits to 0.
  63 //     void reset();
  64 //   };
  65
  66 template<unsigned maxDepth>
  67 class AVLTreeDefaultBSet {
  68 public:
  69     bool& operator[](unsigned i) { ASSERT(i < maxDepth); return m_data[i]; }
  70     void set() { for (unsigned i = 0; i < maxDepth; ++i) m_data[i] = true; }
  71     void reset() { for (unsigned i = 0; i < maxDepth; ++i) m_data[i] = false; }
  72
  73 private:
  74     FixedArray<bool, maxDepth> m_data;
  75 };
  76
  77 // How to determine maxDepth:
  78 // d  Minimum number of nodes
  79 // 2  2
  80 // 3  4
  81 // 4  7
  82 // 5  12
  83 // 6  20
  84 // 7  33
  85 // 8  54
  86 // 9  88
  87 // 10 143
  88 // 11 232
  89 // 12 376
  90 // 13 609
  91 // 14 986
  92 // 15 1,596
  93 // 16 2,583
  94 // 17 4,180
  95 // 18 6,764
  96 // 19 10,945
  97 // 20 17,710
  98 // 21 28,656
  99 // 22 46,367
 100 // 23 75,024
 101 // 24 121,392
 102 // 25 196,417
 103 // 26 317,810
 104 // 27 514,228
 105 // 28 832,039
 106 // 29 1,346,268
 107 // 30 2,178,308
 108 // 31 3,524,577
 109 // 32 5,702,886
 110 // 33 9,227,464
 111 // 34 14,930,351
 112 // 35 24,157,816
 113 // 36 39,088,168
 114 // 37 63,245,985
 115 // 38 102,334,154
 116 // 39 165,580,140
 117 // 40 267,914,295
 118 // 41 433,494,436
 119 // 42 701,408,732
 120 // 43 1,134,903,169
 121 // 44 1,836,311,902
 122 // 45 2,971,215,072
 123 //
 124 // E.g., if, in a particular instantiation, the maximum number of nodes in a tree instance is 1,000,000, the maximum depth should be 28.
 125 // You pick 28 because MN(28) is 832,039, which is less than or equal to 1,000,000, and MN(29) is 1,346,268, which is strictly greater than 1,000,000.
 126
 127 template <class Abstractor, unsigned maxDepth = 32, class BSet = AVLTreeDefaultBSet<maxDepth> >
 128 class AVLTree {
 129 public:
 130
 131     typedef typename Abstractor::key key;
 132     typedef typename Abstractor::handle handle;
 133     typedef typename Abstractor::size size;
 134
 135     enum SearchType {
 136         EQUAL = 1,
 137         LESS = 2,
 138         GREATER = 4,
 139         LESS_EQUAL = EQUAL | LESS,
 140         GREATER_EQUAL = EQUAL | GREATER
 141     };
 142
 143
 144     Abstractor& abstractor() { return abs; }
 145
 146     inline handle insert(handle h);
 147
 148     inline handle search(key k, SearchType st = EQUAL);
 149     inline handle search_least();
 150     inline handle search_greatest();
 151
 152     inline handle remove(key k);
 153
 154     inline handle subst(handle new_node);
 155
 156     void purge() { abs.root = null(); }
 157
 158     bool is_empty() { return abs.root == null(); }
 159
 160     AVLTree() { abs.root = null(); }
 161
 162     class Iterator {
 163     public:
 164
 165         // Initialize depth to invalid value, to indicate iterator is
 166         // invalid.   (Depth is zero-base.)
 167         Iterator() { depth = ~0U; }
 168
 169         void start_iter(AVLTree &tree, key k, SearchType st = EQUAL)
 170         {
 171             // Mask of high bit in an int.
 172             const int MASK_HIGH_BIT = (int) ~ ((~ (unsigned) 0) >> 1);
 173
 174             // Save the tree that we're going to iterate through in a
 175             // member variable.
 176             tree_ = &tree;
 177
 178             int cmp, target_cmp;
 179             handle h = tree_->abs.root;
 180             unsigned d = 0;
 181
 182             depth = ~0U;
 183
 184             if (h == null())
 185               // Tree is empty.
 186               return;
 187
 188             if (st & LESS)
 189               // Key can be greater than key of starting node.
 190               target_cmp = 1;
 191             else if (st & GREATER)
 192               // Key can be less than key of starting node.
 193               target_cmp = -1;
 194             else
 195               // Key must be same as key of starting node.
 196               target_cmp = 0;
 197
 198             for (;;) {
 199                 cmp = cmp_k_n(k, h);
 200                 if (cmp == 0) {
 201                     if (st & EQUAL) {
 202                         // Equal node was sought and found as starting node.
 203                         depth = d;
 204                         break;
 205                     }
 206                     cmp = -target_cmp;
 207                 } else if (target_cmp != 0) {
 208                     if (!((cmp ^ target_cmp) & MASK_HIGH_BIT)) {
 209                         // cmp and target_cmp are both negative or both positive.
 210                         depth = d;
 211                     }
 212                 }
 213                 h = cmp < 0 ? get_lt(h) : get_gt(h);
 214                 if (h == null())
 215                     break;
 216                 branch[d] = cmp > 0;
 217                 path_h[d++] = h;
 218             }
 219         }
 220
 221         void start_iter_least(AVLTree &tree)
 222         {
 223             tree_ = &tree;
 224
 225             handle h = tree_->abs.root;
 226
 227             depth = ~0U;
 228
 229             branch.reset();
 230
 231             while (h != null()) {
 232                 if (depth != ~0U)
 233                     path_h[depth] = h;
 234                 depth++;
 235                 h = get_lt(h);
 236             }
 237         }
 238
 239         void start_iter_greatest(AVLTree &tree)
 240         {
 241             tree_ = &tree;
 242
 243             handle h = tree_->abs.root;
 244
 245             depth = ~0U;
 246
 247             branch.set();
 248
 249             while (h != null()) {
 250                 if (depth != ~0U)
 251                     path_h[depth] = h;
 252                 depth++;
 253                 h = get_gt(h);
 254             }
 255         }
 256
 257         handle operator*()
 258         {
 259             if (depth == ~0U)
 260                 return null();
 261
 262             return depth == 0 ? tree_->abs.root : path_h[depth - 1];
 263         }
 264
 265         void operator++()
 266         {
 267             if (depth != ~0U) {
 268                 handle h = get_gt(**this);
 269                 if (h == null()) {
 270                     do {
 271                         if (depth == 0) {
 272                             depth = ~0U;
 273                             break;
 274                         }
 275                         depth--;
 276                     } while (branch[depth]);
 277                 } else {
 278                     branch[depth] = true;
 279                     path_h[depth++] = h;
 280                     for (;;) {
 281                         h = get_lt(h);
 282                         if (h == null())
 283                             break;
 284                         branch[depth] = false;
 285                         path_h[depth++] = h;
 286                     }
 287                 }
 288             }
 289         }
 290
 291         void operator--()
 292         {
 293             if (depth != ~0U) {
 294                 handle h = get_lt(**this);
 295                 if (h == null())
 296                     do {
 297                         if (depth == 0) {
 298                             depth = ~0U;
 299                             break;
 300                         }
 301                         depth--;
 302                     } while (!branch[depth]);
 303                 else {
 304                     branch[depth] = false;
 305                     path_h[depth++] = h;
 306                     for (;;) {
 307                         h = get_gt(h);
 308                         if (h == null())
 309                             break;
 310                         branch[depth] = true;
 311                         path_h[depth++] = h;
 312                     }
 313                 }
 314             }
 315         }
 316
 317         void operator++(int) { ++(*this); }
 318         void operator--(int) { --(*this); }
 319
 320     protected:
 321
 322         // Tree being iterated over.
 323         AVLTree *tree_;
 324
 325         // Records a path into the tree.  If branch[n] is true, indicates
 326         // take greater branch from the nth node in the path, otherwise
 327         // take the less branch.  branch[0] gives branch from root, and
 328         // so on.
 329         BSet branch;
 330
 331         // Zero-based depth of path into tree.
 332         unsigned depth;
 333
 334         // Handles of nodes in path from root to current node (returned by *).
 335         handle path_h[maxDepth - 1];
 336
 337         int cmp_k_n(key k, handle h) { return tree_->abs.compare_key_node(k, h); }
 338         int cmp_n_n(handle h1, handle h2) { return tree_->abs.compare_node_node(h1, h2); }
 339         handle get_lt(handle h) { return tree_->abs.get_less(h); }
 340         handle get_gt(handle h) { return tree_->abs.get_greater(h); }
 341         handle null() { return tree_->abs.null(); }
 342     };
 343
 344     template<typename fwd_iter>
 345     bool build(fwd_iter p, size num_nodes)
 346     {
 347         if (num_nodes == 0) {
 348             abs.root = null();
 349             return true;
 350         }
 351
 352         // Gives path to subtree being built.  If branch[N] is false, branch
 353         // less from the node at depth N, if true branch greater.
 354         BSet branch;
 355
 356         // If rem[N] is true, then for the current subtree at depth N, it's
 357         // greater subtree has one more node than it's less subtree.
 358         BSet rem;
 359
 360             // Depth of root node of current subtree.
 361         unsigned depth = 0;
 362
 363             // Number of nodes in current subtree.
 364         size num_sub = num_nodes;
 365
 366         // The algorithm relies on a stack of nodes whose less subtree has
 367         // been built, but whose right subtree has not yet been built.  The
 368         // stack is implemented as linked list.  The nodes are linked
 369         // together by having the "greater" handle of a node set to the
 370         // next node in the list.  "less_parent" is the handle of the first
 371         // node in the list.
 372         handle less_parent = null();
 373
 374         // h is root of current subtree, child is one of its children.
 375         handle h, child;
 376
 377         for (;;) {
 378             while (num_sub > 2) {
 379                 // Subtract one for root of subtree.
 380                 num_sub--;
 381                 rem[depth] = !!(num_sub & 1);
 382                 branch[depth++] = false;
 383                 num_sub >>= 1;
 384             }
 385
 386             if (num_sub == 2) {
 387                 // Build a subtree with two nodes, slanting to greater.
 388                 // I arbitrarily chose to always have the extra node in the
 389                 // greater subtree when there is an odd number of nodes to
 390                 // split between the two subtrees.
 391
 392                 h = *p;
 393                 p++;
 394                 child = *p;
 395                 p++;
 396                 set_lt(child, null());
 397                 set_gt(child, null());
 398                 set_bf(child, 0);
 399                 set_gt(h, child);
 400                 set_lt(h, null());
 401                 set_bf(h, 1);
 402             } else { // num_sub == 1
 403                 // Build a subtree with one node.
 404
 405                 h = *p;
 406                 p++;
 407                 set_lt(h, null());
 408                 set_gt(h, null());
 409                 set_bf(h, 0);
 410             }
 411
 412             while (depth) {
 413                 depth--;
 414                 if (!branch[depth])
 415                     // We've completed a less subtree.
 416                     break;
 417
 418                 // We've completed a greater subtree, so attach it to
 419                 // its parent (that is less than it).  We pop the parent
 420                 // off the stack of less parents.
 421                 child = h;
 422                 h = less_parent;
 423                 less_parent = get_gt(h);
 424                 set_gt(h, child);
 425                 // num_sub = 2 * (num_sub - rem[depth]) + rem[depth] + 1
 426                 num_sub <<= 1;
 427                 num_sub += 1 - rem[depth];
 428                 if (num_sub & (num_sub - 1))
 429                     // num_sub is not a power of 2
 430                     set_bf(h, 0);
 431                 else
 432                     // num_sub is a power of 2
 433                     set_bf(h, 1);
 434             }
 435
 436             if (num_sub == num_nodes)
 437                 // We've completed the full tree.
 438                 break;
 439
 440             // The subtree we've completed is the less subtree of the
 441             // next node in the sequence.
 442
 443             child = h;
 444             h = *p;
 445             p++;
 446             set_lt(h, child);
 447
 448             // Put h into stack of less parents.
 449             set_gt(h, less_parent);
 450             less_parent = h;
 451
 452             // Proceed to creating greater than subtree of h.
 453             branch[depth] = true;
 454             num_sub += rem[depth++];
 455
 456         } // end for (;;)
 457
 458         abs.root = h;
 459
 460         return true;
 461     }
 462
 463 protected:
 464
 465     friend class Iterator;
 466
 467     // Create a class whose sole purpose is to take advantage of
 468     // the "empty member" optimization.
 469     struct abs_plus_root : public Abstractor {
 470         // The handle of the root element in the AVL tree.
 471         handle root;
 472     };
 473
 474     abs_plus_root abs;
 475
 476
 477     handle get_lt(handle h) { return abs.get_less(h); }
 478     void set_lt(handle h, handle lh) { abs.set_less(h, lh); }
 479
 480     handle get_gt(handle h) { return abs.get_greater(h); }
 481     void set_gt(handle h, handle gh) { abs.set_greater(h, gh); }
 482
 483     int get_bf(handle h) { return abs.get_balance_factor(h); }
 484     void set_bf(handle h, int bf) { abs.set_balance_factor(h, bf); }
 485
 486     int cmp_k_n(key k, handle h) { return abs.compare_key_node(k, h); }
 487     int cmp_n_n(handle h1, handle h2) { return abs.compare_node_node(h1, h2); }
 488
 489     handle null() { return abs.null(); }
 490
 491 private:
 492
 493     // Balances subtree, returns handle of root node of subtree
 494     // after balancing.
 495     handle balance(handle bal_h)
 496     {
 497         handle deep_h;
 498
 499         // Either the "greater than" or the "less than" subtree of
 500         // this node has to be 2 levels deeper (or else it wouldn't
 501         // need balancing).
 502
 503         if (get_bf(bal_h) > 0) {
 504             // "Greater than" subtree is deeper.
 505
 506             deep_h = get_gt(bal_h);
 507
 508             if (get_bf(deep_h) < 0) {
 509                 handle old_h = bal_h;
 510                 bal_h = get_lt(deep_h);
 511
 512                 set_gt(old_h, get_lt(bal_h));
 513                 set_lt(deep_h, get_gt(bal_h));
 514                 set_lt(bal_h, old_h);
 515                 set_gt(bal_h, deep_h);
 516
 517                 int bf = get_bf(bal_h);
 518                 if (bf != 0) {
 519                     if (bf > 0) {
 520                         set_bf(old_h, -1);
 521                         set_bf(deep_h, 0);
 522                     } else {
 523                         set_bf(deep_h, 1);
 524                         set_bf(old_h, 0);
 525                     }
 526                     set_bf(bal_h, 0);
 527                 } else {
 528                     set_bf(old_h, 0);
 529                     set_bf(deep_h, 0);
 530                 }
 531             } else {
 532                 set_gt(bal_h, get_lt(deep_h));
 533                 set_lt(deep_h, bal_h);
 534                 if (get_bf(deep_h) == 0) {
 535                     set_bf(deep_h, -1);
 536                     set_bf(bal_h, 1);
 537                 } else {
 538                     set_bf(deep_h, 0);
 539                     set_bf(bal_h, 0);
 540                 }
 541                 bal_h = deep_h;
 542             }
 543         } else {
 544             // "Less than" subtree is deeper.
 545
 546             deep_h = get_lt(bal_h);
 547
 548             if (get_bf(deep_h) > 0) {
 549                 handle old_h = bal_h;
 550                 bal_h = get_gt(deep_h);
 551                 set_lt(old_h, get_gt(bal_h));
 552                 set_gt(deep_h, get_lt(bal_h));
 553                 set_gt(bal_h, old_h);
 554                 set_lt(bal_h, deep_h);
 555
 556                 int bf = get_bf(bal_h);
 557                 if (bf != 0) {
 558                     if (bf < 0) {
 559                         set_bf(old_h, 1);
 560                         set_bf(deep_h, 0);
 561                     } else {
 562                         set_bf(deep_h, -1);
 563                         set_bf(old_h, 0);
 564                     }
 565                     set_bf(bal_h, 0);
 566                 } else {
 567                     set_bf(old_h, 0);
 568                     set_bf(deep_h, 0);
 569                 }
 570             } else {
 571                 set_lt(bal_h, get_gt(deep_h));
 572                 set_gt(deep_h, bal_h);
 573                 if (get_bf(deep_h) == 0) {
 574                     set_bf(deep_h, 1);
 575                     set_bf(bal_h, -1);
 576                 } else {
 577                     set_bf(deep_h, 0);
 578                     set_bf(bal_h, 0);
 579                 }
 580                 bal_h = deep_h;
 581             }
 582         }
 583
 584         return bal_h;
 585     }
 586
 587 };
 588
 589 template <class Abstractor, unsigned maxDepth, class BSet>
 590 inline typename AVLTree<Abstractor, maxDepth, BSet>::handle
 591 AVLTree<Abstractor, maxDepth, BSet>::insert(handle h)
 592 {
 593     set_lt(h, null());
 594     set_gt(h, null());
 595     set_bf(h, 0);
 596
 597     if (abs.root == null())
 598         abs.root = h;
 599     else {
 600         // Last unbalanced node encountered in search for insertion point.
 601         handle unbal = null();
 602         // Parent of last unbalanced node.
 603         handle parent_unbal = null();
 604         // Balance factor of last unbalanced node.
 605         int unbal_bf;
 606
 607         // Zero-based depth in tree.
 608         unsigned depth = 0, unbal_depth = 0;
 609
 610         // Records a path into the tree.  If branch[n] is true, indicates
 611         // take greater branch from the nth node in the path, otherwise
 612         // take the less branch.  branch[0] gives branch from root, and
 613         // so on.
 614         BSet branch;
 615
 616         handle hh = abs.root;
 617         handle parent = null();
 618         int cmp;
 619
 620         do {
 621             if (get_bf(hh) != 0) {
 622                 unbal = hh;
 623                 parent_unbal = parent;
 624                 unbal_depth = depth;
 625             }
 626             cmp = cmp_n_n(h, hh);
 627             if (cmp == 0)
 628                 // Duplicate key.
 629                 return hh;
 630             parent = hh;
 631             hh = cmp < 0 ? get_lt(hh) : get_gt(hh);
 632             branch[depth++] = cmp > 0;
 633         } while (hh != null());
 634
 635         //  Add node to insert as leaf of tree.
 636         if (cmp < 0)
 637             set_lt(parent, h);
 638         else
 639             set_gt(parent, h);
 640
 641         depth = unbal_depth;
 642
 643         if (unbal == null())
 644             hh = abs.root;
 645         else {
 646             cmp = branch[depth++] ? 1 : -1;
 647             unbal_bf = get_bf(unbal);
 648             if (cmp < 0)
 649                 unbal_bf--;
 650             else  // cmp > 0
 651                 unbal_bf++;
 652             hh = cmp < 0 ? get_lt(unbal) : get_gt(unbal);
 653             if ((unbal_bf != -2) && (unbal_bf != 2)) {
 654                 // No rebalancing of tree is necessary.
 655                 set_bf(unbal, unbal_bf);
 656                 unbal = null();
 657             }
 658         }
 659
 660         if (hh != null())
 661             while (h != hh) {
 662                 cmp = branch[depth++] ? 1 : -1;
 663                 if (cmp < 0) {
 664                     set_bf(hh, -1);
 665                     hh = get_lt(hh);
 666                 } else { // cmp > 0
 667                     set_bf(hh, 1);
 668                     hh = get_gt(hh);
 669                 }
 670             }
 671
 672         if (unbal != null()) {
 673             unbal = balance(unbal);
 674             if (parent_unbal == null())
 675                 abs.root = unbal;
 676             else {
 677                 depth = unbal_depth - 1;
 678                 cmp = branch[depth] ? 1 : -1;
 679                 if (cmp < 0)
 680                     set_lt(parent_unbal, unbal);
 681                 else  // cmp > 0
 682                     set_gt(parent_unbal, unbal);
 683             }
 684         }
 685     }
 686
 687     return h;
 688 }
 689
 690 template <class Abstractor, unsigned maxDepth, class BSet>
 691 inline typename AVLTree<Abstractor, maxDepth, BSet>::handle
 692 AVLTree<Abstractor, maxDepth, BSet>::search(key k, typename AVLTree<Abstractor, maxDepth, BSet>::SearchType st)
 693 {
 694     const int MASK_HIGH_BIT = (int) ~ ((~ (unsigned) 0) >> 1);
 695
 696     int cmp, target_cmp;
 697     handle match_h = null();
 698     handle h = abs.root;
 699
 700     if (st & LESS)
 701         target_cmp = 1;
 702     else if (st & GREATER)
 703         target_cmp = -1;
 704     else
 705         target_cmp = 0;
 706
 707     while (h != null()) {
 708         cmp = cmp_k_n(k, h);
 709         if (cmp == 0) {
 710             if (st & EQUAL) {
 711                 match_h = h;
 712                 break;
 713             }
 714             cmp = -target_cmp;
 715         } else if (target_cmp != 0)
 716             if (!((cmp ^ target_cmp) & MASK_HIGH_BIT))
 717                 // cmp and target_cmp are both positive or both negative.
 718                 match_h = h;
 719         h = cmp < 0 ? get_lt(h) : get_gt(h);
 720     }
 721
 722     return match_h;
 723 }
 724
 725 template <class Abstractor, unsigned maxDepth, class BSet>
 726 inline typename AVLTree<Abstractor, maxDepth, BSet>::handle
 727 AVLTree<Abstractor, maxDepth, BSet>::search_least()
 728 {
 729     handle h = abs.root, parent = null();
 730
 731     while (h != null()) {
 732         parent = h;
 733         h = get_lt(h);
 734     }
 735
 736     return parent;
 737 }
 738
 739 template <class Abstractor, unsigned maxDepth, class BSet>
 740 inline typename AVLTree<Abstractor, maxDepth, BSet>::handle
 741 AVLTree<Abstractor, maxDepth, BSet>::search_greatest()
 742 {
 743     handle h = abs.root, parent = null();
 744
 745     while (h != null()) {
 746         parent = h;
 747         h = get_gt(h);
 748     }
 749
 750     return parent;
 751 }
 752
 753 template <class Abstractor, unsigned maxDepth, class BSet>
 754 inline typename AVLTree<Abstractor, maxDepth, BSet>::handle
 755 AVLTree<Abstractor, maxDepth, BSet>::remove(key k)
 756 {
 757     // Zero-based depth in tree.
 758     unsigned depth = 0, rm_depth;
 759
 760     // Records a path into the tree.  If branch[n] is true, indicates
 761     // take greater branch from the nth node in the path, otherwise
 762     // take the less branch.  branch[0] gives branch from root, and
 763     // so on.
 764     BSet branch;
 765
 766     handle h = abs.root;
 767     handle parent = null(), child;
 768     int cmp, cmp_shortened_sub_with_path = 0;
 769
 770     for (;;) {
 771         if (h == null())
 772             // No node in tree with given key.
 773             return null();
 774         cmp = cmp_k_n(k, h);
 775         if (cmp == 0)
 776             // Found node to remove.
 777             break;
 778         parent = h;
 779         h = cmp < 0 ? get_lt(h) : get_gt(h);
 780         branch[depth++] = cmp > 0;
 781         cmp_shortened_sub_with_path = cmp;
 782     }
 783     handle rm = h;
 784     handle parent_rm = parent;
 785     rm_depth = depth;
 786
 787     // If the node to remove is not a leaf node, we need to get a
 788     // leaf node, or a node with a single leaf as its child, to put
 789     // in the place of the node to remove.  We will get the greatest
 790     // node in the less subtree (of the node to remove), or the least
 791     // node in the greater subtree.  We take the leaf node from the
 792     // deeper subtree, if there is one.
 793
 794     if (get_bf(h) < 0) {
 795         child = get_lt(h);
 796         branch[depth] = false;
 797         cmp = -1;
 798     } else {
 799         child = get_gt(h);
 800         branch[depth] = true;
 801         cmp = 1;
 802     }
 803     depth++;
 804
 805     if (child != null()) {
 806         cmp = -cmp;
 807         do {
 808             parent = h;
 809             h = child;
 810             if (cmp < 0) {
 811                 child = get_lt(h);
 812                 branch[depth] = false;
 813             } else {
 814                 child = get_gt(h);
 815                 branch[depth] = true;
 816             }
 817             depth++;
 818         } while (child != null());
 819
 820         if (parent == rm)
 821             // Only went through do loop once.  Deleted node will be replaced
 822             // in the tree structure by one of its immediate children.
 823             cmp_shortened_sub_with_path = -cmp;
 824         else
 825             cmp_shortened_sub_with_path = cmp;
 826
 827         // Get the handle of the opposite child, which may not be null.
 828         child = cmp > 0 ? get_lt(h) : get_gt(h);
 829     }
 830
 831     if (parent == null())
 832         // There were only 1 or 2 nodes in this tree.
 833         abs.root = child;
 834     else if (cmp_shortened_sub_with_path < 0)
 835         set_lt(parent, child);
 836     else
 837         set_gt(parent, child);
 838
 839     // "path" is the parent of the subtree being eliminated or reduced
 840     // from a depth of 2 to 1.  If "path" is the node to be removed, we
 841     // set path to the node we're about to poke into the position of the
 842     // node to be removed.
 843     handle path = parent == rm ? h : parent;
 844
 845     if (h != rm) {
 846         // Poke in the replacement for the node to be removed.
 847         set_lt(h, get_lt(rm));
 848         set_gt(h, get_gt(rm));
 849         set_bf(h, get_bf(rm));
 850         if (parent_rm == null())
 851             abs.root = h;
 852         else {
 853             depth = rm_depth - 1;
 854             if (branch[depth])
 855                 set_gt(parent_rm, h);
 856             else
 857                 set_lt(parent_rm, h);
 858         }
 859     }
 860
 861     if (path != null()) {
 862         // Create a temporary linked list from the parent of the path node
 863         // to the root node.
 864         h = abs.root;
 865         parent = null();
 866         depth = 0;
 867         while (h != path) {
 868             if (branch[depth++]) {
 869                 child = get_gt(h);
 870                 set_gt(h, parent);
 871             } else {
 872                 child = get_lt(h);
 873                 set_lt(h, parent);
 874             }
 875             parent = h;
 876             h = child;
 877         }
 878
 879         // Climb from the path node to the root node using the linked
 880         // list, restoring the tree structure and rebalancing as necessary.
 881         bool reduced_depth = true;
 882         int bf;
 883         cmp = cmp_shortened_sub_with_path;
 884         for (;;) {
 885             if (reduced_depth) {
 886                 bf = get_bf(h);
 887                 if (cmp < 0)
 888                     bf++;
 889                 else  // cmp > 0
 890                     bf--;
 891                 if ((bf == -2) || (bf == 2)) {
 892                     h = balance(h);
 893                     bf = get_bf(h);
 894                 } else
 895                     set_bf(h, bf);
 896                 reduced_depth = (bf == 0);
 897             }
 898             if (parent == null())
 899                 break;
 900             child = h;
 901             h = parent;
 902             cmp = branch[--depth] ? 1 : -1;
 903             if (cmp < 0)    {
 904                 parent = get_lt(h);
 905                 set_lt(h, child);
 906             } else {
 907                 parent = get_gt(h);
 908                 set_gt(h, child);
 909             }
 910         }
 911         abs.root = h;
 912     }
 913
 914     return rm;
 915 }
 916
 917 template <class Abstractor, unsigned maxDepth, class BSet>
 918 inline typename AVLTree<Abstractor, maxDepth, BSet>::handle
 919 AVLTree<Abstractor, maxDepth, BSet>::subst(handle new_node)
 920 {
 921     handle h = abs.root;
 922     handle parent = null();
 923     int cmp, last_cmp;
 924
 925     /* Search for node already in tree with same key. */
 926     for (;;) {
 927         if (h == null())
 928             /* No node in tree with same key as new node. */
 929             return null();
 930         cmp = cmp_n_n(new_node, h);
 931         if (cmp == 0)
 932             /* Found the node to substitute new one for. */
 933             break;
 934         last_cmp = cmp;
 935         parent = h;
 936         h = cmp < 0 ? get_lt(h) : get_gt(h);
 937     }
 938
 939     /* Copy tree housekeeping fields from node in tree to new node. */
 940     set_lt(new_node, get_lt(h));
 941     set_gt(new_node, get_gt(h));
 942     set_bf(new_node, get_bf(h));
 943
 944     if (parent == null())
 945         /* New node is also new root. */
 946         abs.root = new_node;
 947     else {
 948         /* Make parent point to new node. */
 949         if (last_cmp < 0)
 950             set_lt(parent, new_node);
 951         else
 952             set_gt(parent, new_node);
 953     }
 954
 955     return h;
 956 }
 957
 958 }
 959
 960 #endif