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