JavaScriptCore/wtf/AVLTree.h - WebKit - Git at Google

 /*
  * Copyright (C) 2008 Apple Inc. All rights reserved.
  *
  * Based on Abstract AVL Tree Template v1.5 by Walt Karas
  * <http://geocities.com/wkaras/gen_cpp/avl_tree.html>.
  *
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions
  * are met:
  *
  * 1.  Redistributions of source code must retain the above copyright
  *     notice, this list of conditions and the following disclaimer.
  * 2.  Redistributions in binary form must reproduce the above copyright
  *     notice, this list of conditions and the following disclaimer in the
  *     documentation and/or other materials provided with the distribution.
  * 3.  Neither the name of Apple Computer, Inc. ("Apple") nor the names of
  *     its contributors may be used to endorse or promote products derived
  *     from this software without specific prior written permission.
  *
  * THIS SOFTWARE IS PROVIDED BY APPLE AND ITS CONTRIBUTORS "AS IS" AND ANY
  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
  * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
  * DISCLAIMED. IN NO EVENT SHALL APPLE OR ITS CONTRIBUTORS BE LIABLE FOR ANY
  * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
  * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
  * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  */

 #ifndef AVL_TREE_H_
 #define AVL_TREE_H_

 #include "Assertions.h"

 namespace WTF {

 // Here is the reference class for BSet.
 //
 // class BSet
 //   {
 //   public:
 //
 //     class ANY_bitref
 //       {
 //       public:
 //         operator bool ();
 //         void operator = (bool b);
 //       };
 //
 //     // Does not have to initialize bits.
 //     BSet();
 //
 //     // Must return a valid value for index when 0 <= index < maxDepth
 //     ANY_bitref operator [] (unsigned index);
 //
 //     // Set all bits to 1.
 //     void set();
 //
 //     // Set all bits to 0.
 //     void reset();
 //   };

 template<unsigned maxDepth>
 class AVLTreeDefaultBSet {
 public:
     bool& operator[](unsigned i) { ASSERT(i < maxDepth); return m_data[i]; }
     void set() { for (unsigned i = 0; i < maxDepth; ++i) m_data[i] = true; }
     void reset() { for (unsigned i = 0; i < maxDepth; ++i) m_data[i] = false; }

 private:
     bool m_data[maxDepth];
 };

 // How to determine maxDepth:
 // d  Minimum number of nodes
 // 2  2
 // 3  4
 // 4  7
 // 5  12
 // 6  20
 // 7  33
 // 8  54
 // 9  88
 // 10 143
 // 11 232
 // 12 376
 // 13 609
 // 14 986
 // 15 1,596
 // 16 2,583
 // 17 4,180
 // 18 6,764
 // 19 10,945
 // 20 17,710
 // 21 28,656
 // 22 46,367
 // 23 75,024
 // 24 121,392
 // 25 196,417
 // 26 317,810
 // 27 514,228
 // 28 832,039
 // 29 1,346,268
 // 30 2,178,308
 // 31 3,524,577
 // 32 5,702,886
 // 33 9,227,464
 // 34 14,930,351
 // 35 24,157,816
 // 36 39,088,168
 // 37 63,245,985
 // 38 102,334,154
 // 39 165,580,140
 // 40 267,914,295
 // 41 433,494,436
 // 42 701,408,732
 // 43 1,134,903,169
 // 44 1,836,311,902
 // 45 2,971,215,072
 //
 // 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.
 // 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.

 template <class Abstractor, unsigned maxDepth = 32, class BSet = AVLTreeDefaultBSet<maxDepth> >
 class AVLTree {
 public:

     typedef typename Abstractor::key key;
     typedef typename Abstractor::handle handle;
     typedef typename Abstractor::size size;

     enum SearchType {
         EQUAL = 1,
         LESS = 2,
         GREATER = 4,
         LESS_EQUAL = EQUAL | LESS,
         GREATER_EQUAL = EQUAL | GREATER
     };


     Abstractor& abstractor() { return abs; }

     inline handle insert(handle h);

     inline handle search(key k, SearchType st = EQUAL);
     inline handle search_least();
     inline handle search_greatest();

     inline handle remove(key k);

     inline handle subst(handle new_node);

     void purge() { abs.root = null(); }

     bool is_empty() { return abs.root == null(); }

     AVLTree() { abs.root = null(); }

     class Iterator {
     public:

         // Initialize depth to invalid value, to indicate iterator is
         // invalid.   (Depth is zero-base.)
         Iterator() { depth = ~0U; }

         void start_iter(AVLTree &tree, key k, SearchType st = EQUAL)
         {
             // Mask of high bit in an int.
             const int MASK_HIGH_BIT = (int) ~ ((~ (unsigned) 0) >> 1);

             // Save the tree that we're going to iterate through in a
             // member variable.
             tree_ = &tree;

             int cmp, target_cmp;
             handle h = tree_->abs.root;
             unsigned d = 0;

             depth = ~0U;

             if (h == null())
               // Tree is empty.
               return;

             if (st & LESS)
               // Key can be greater than key of starting node.
               target_cmp = 1;
             else if (st & GREATER)
               // Key can be less than key of starting node.
               target_cmp = -1;
             else
               // Key must be same as key of starting node.
               target_cmp = 0;

             for (;;) {
                 cmp = cmp_k_n(k, h);
                 if (cmp == 0) {
                     if (st & EQUAL) {
                         // Equal node was sought and found as starting node.
                         depth = d;
                         break;
                     }
                     cmp = -target_cmp;
                 } else if (target_cmp != 0) {
                     if (!((cmp ^ target_cmp) & MASK_HIGH_BIT)) {
                         // cmp and target_cmp are both negative or both positive.
                         depth = d;
                     }
                 }
                 h = cmp < 0 ? get_lt(h) : get_gt(h);
                 if (h == null())
                     break;
                 branch[d] = cmp > 0;
                 path_h[d++] = h;
             }
         }

         void start_iter_least(AVLTree &tree)
         {
             tree_ = &tree;

             handle h = tree_->abs.root;

             depth = ~0U;

             branch.reset();

             while (h != null()) {
                 if (depth != ~0U)
                     path_h[depth] = h;
                 depth++;
                 h = get_lt(h);
             }
         }

         void start_iter_greatest(AVLTree &tree)
         {
             tree_ = &tree;

             handle h = tree_->abs.root;

             depth = ~0U;

             branch.set();

             while (h != null()) {
                 if (depth != ~0U)
                     path_h[depth] = h;
                 depth++;
                 h = get_gt(h);
             }
         }

         handle operator*()
         {
             if (depth == ~0U)
                 return null();

             return depth == 0 ? tree_->abs.root : path_h[depth - 1];
         }

         void operator++()
         {
             if (depth != ~0U) {
                 handle h = get_gt(**this);
                 if (h == null()) {
                     do {
                         if (depth == 0) {
                             depth = ~0U;
                             break;
                         }
                         depth--;
                     } while (branch[depth]);
                 } else {
                     branch[depth] = true;
                     path_h[depth++] = h;
                     for (;;) {
                         h = get_lt(h);
                         if (h == null())
                             break;
                         branch[depth] = false;
                         path_h[depth++] = h;
                     }
                 }
             }
         }

         void operator--()
         {
             if (depth != ~0U) {
                 handle h = get_lt(**this);
                 if (h == null())
                     do {
                         if (depth == 0) {
                             depth = ~0U;
                             break;
                         }
                         depth--;
                     } while (!branch[depth]);
                 else {
                     branch[depth] = false;
                     path_h[depth++] = h;
                     for (;;) {
                         h = get_gt(h);
                         if (h == null())
                             break;
                         branch[depth] = true;
                         path_h[depth++] = h;
                     }
                 }
             }
         }

         void operator++(int) { ++(*this); }
         void operator--(int) { --(*this); }

     protected:

         // Tree being iterated over.
         AVLTree *tree_;

         // Records a path into the tree.  If branch[n] is true, indicates
         // take greater branch from the nth node in the path, otherwise
         // take the less branch.  branch[0] gives branch from root, and
         // so on.
         BSet branch;

         // Zero-based depth of path into tree.
         unsigned depth;

         // Handles of nodes in path from root to current node (returned by *).
         handle path_h[maxDepth - 1];

         int cmp_k_n(key k, handle h) { return tree_->abs.compare_key_node(k, h); }
         int cmp_n_n(handle h1, handle h2) { return tree_->abs.compare_node_node(h1, h2); }
         handle get_lt(handle h) { return tree_->abs.get_less(h); }
         handle get_gt(handle h) { return tree_->abs.get_greater(h); }
         handle null() { return tree_->abs.null(); }
     };

     template<typename fwd_iter>
     bool build(fwd_iter p, size num_nodes)
     {
         if (num_nodes == 0) {
             abs.root = null();
             return true;
         }

         // Gives path to subtree being built.  If branch[N] is false, branch
         // less from the node at depth N, if true branch greater.
         BSet branch;

         // If rem[N] is true, then for the current subtree at depth N, it's
         // greater subtree has one more node than it's less subtree.
         BSet rem;

             // Depth of root node of current subtree.
         unsigned depth = 0;

             // Number of nodes in current subtree.
         size num_sub = num_nodes;

         // The algorithm relies on a stack of nodes whose less subtree has
         // been built, but whose right subtree has not yet been built.  The
         // stack is implemented as linked list.  The nodes are linked
         // together by having the "greater" handle of a node set to the
         // next node in the list.  "less_parent" is the handle of the first
         // node in the list.
         handle less_parent = null();

         // h is root of current subtree, child is one of its children.
         handle h, child;

         for (;;) {
             while (num_sub > 2) {
                 // Subtract one for root of subtree.
                 num_sub--;
                 rem[depth] = !!(num_sub & 1);
                 branch[depth++] = false;
                 num_sub >>= 1;
             }

             if (num_sub == 2) {
                 // Build a subtree with two nodes, slanting to greater.
                 // I arbitrarily chose to always have the extra node in the
                 // greater subtree when there is an odd number of nodes to
                 // split between the two subtrees.

                 h = *p;
                 p++;
                 child = *p;
                 p++;
                 set_lt(child, null());
                 set_gt(child, null());
                 set_bf(child, 0);
                 set_gt(h, child);
                 set_lt(h, null());
                 set_bf(h, 1);
             } else { // num_sub == 1
                 // Build a subtree with one node.

                 h = *p;
                 p++;
                 set_lt(h, null());
                 set_gt(h, null());
                 set_bf(h, 0);
             }

             while (depth) {
                 depth--;
                 if (!branch[depth])
                     // We've completed a less subtree.
                     break;

                 // We've completed a greater subtree, so attach it to
                 // its parent (that is less than it).  We pop the parent
                 // off the stack of less parents.
                 child = h;
                 h = less_parent;
                 less_parent = get_gt(h);
                 set_gt(h, child);
                 // num_sub = 2 * (num_sub - rem[depth]) + rem[depth] + 1
                 num_sub <<= 1;
                 num_sub += 1 - rem[depth];
                 if (num_sub & (num_sub - 1))
                     // num_sub is not a power of 2
                     set_bf(h, 0);
                 else
                     // num_sub is a power of 2
                     set_bf(h, 1);
             }

             if (num_sub == num_nodes)
                 // We've completed the full tree.
                 break;

             // The subtree we've completed is the less subtree of the
             // next node in the sequence.

             child = h;
             h = *p;
             p++;
             set_lt(h, child);

             // Put h into stack of less parents.
             set_gt(h, less_parent);
             less_parent = h;

             // Proceed to creating greater than subtree of h.
             branch[depth] = true;
             num_sub += rem[depth++];

         } // end for (;;)

         abs.root = h;

         return true;
     }

 protected:

     friend class Iterator;

     // Create a class whose sole purpose is to take advantage of
     // the "empty member" optimization.
     struct abs_plus_root : public Abstractor {
         // The handle of the root element in the AVL tree.
         handle root;
     };

     abs_plus_root abs;


     handle get_lt(handle h) { return abs.get_less(h); }
     void set_lt(handle h, handle lh) { abs.set_less(h, lh); }

     handle get_gt(handle h) { return abs.get_greater(h); }
     void set_gt(handle h, handle gh) { abs.set_greater(h, gh); }

     int get_bf(handle h) { return abs.get_balance_factor(h); }
     void set_bf(handle h, int bf) { abs.set_balance_factor(h, bf); }

     int cmp_k_n(key k, handle h) { return abs.compare_key_node(k, h); }
     int cmp_n_n(handle h1, handle h2) { return abs.compare_node_node(h1, h2); }

     handle null() { return abs.null(); }

 private:

     // Balances subtree, returns handle of root node of subtree
     // after balancing.
     handle balance(handle bal_h)
     {
         handle deep_h;

         // Either the "greater than" or the "less than" subtree of
         // this node has to be 2 levels deeper (or else it wouldn't
         // need balancing).

         if (get_bf(bal_h) > 0) {
             // "Greater than" subtree is deeper.

             deep_h = get_gt(bal_h);

             if (get_bf(deep_h) < 0) {
                 handle old_h = bal_h;
                 bal_h = get_lt(deep_h);

                 set_gt(old_h, get_lt(bal_h));
                 set_lt(deep_h, get_gt(bal_h));
                 set_lt(bal_h, old_h);
                 set_gt(bal_h, deep_h);

                 int bf = get_bf(bal_h);
                 if (bf != 0) {
                     if (bf > 0) {
                         set_bf(old_h, -1);
                         set_bf(deep_h, 0);
                     } else {
                         set_bf(deep_h, 1);
                         set_bf(old_h, 0);
                     }
                     set_bf(bal_h, 0);
                 } else {
                     set_bf(old_h, 0);
                     set_bf(deep_h, 0);
                 }
             } else {
                 set_gt(bal_h, get_lt(deep_h));
                 set_lt(deep_h, bal_h);
                 if (get_bf(deep_h) == 0) {
                     set_bf(deep_h, -1);
                     set_bf(bal_h, 1);
                 } else {
                     set_bf(deep_h, 0);
                     set_bf(bal_h, 0);
                 }
                 bal_h = deep_h;
             }
         } else {
             // "Less than" subtree is deeper.

             deep_h = get_lt(bal_h);

             if (get_bf(deep_h) > 0) {
                 handle old_h = bal_h;
                 bal_h = get_gt(deep_h);
                 set_lt(old_h, get_gt(bal_h));
                 set_gt(deep_h, get_lt(bal_h));
                 set_gt(bal_h, old_h);
                 set_lt(bal_h, deep_h);

                 int bf = get_bf(bal_h);
                 if (bf != 0) {
                     if (bf < 0) {
                         set_bf(old_h, 1);
                         set_bf(deep_h, 0);
                     } else {
                         set_bf(deep_h, -1);
                         set_bf(old_h, 0);
                     }
                     set_bf(bal_h, 0);
                 } else {
                     set_bf(old_h, 0);
                     set_bf(deep_h, 0);
                 }
             } else {
                 set_lt(bal_h, get_gt(deep_h));
                 set_gt(deep_h, bal_h);
                 if (get_bf(deep_h) == 0) {
                     set_bf(deep_h, 1);
                     set_bf(bal_h, -1);
                 } else {
                     set_bf(deep_h, 0);
                     set_bf(bal_h, 0);
                 }
                 bal_h = deep_h;
             }
         }

         return bal_h;
     }

 };

 template <class Abstractor, unsigned maxDepth, class BSet>
 inline typename AVLTree<Abstractor, maxDepth, BSet>::handle
 AVLTree<Abstractor, maxDepth, BSet>::insert(handle h)
 {
     set_lt(h, null());
     set_gt(h, null());
     set_bf(h, 0);

     if (abs.root == null())
         abs.root = h;
     else {
         // Last unbalanced node encountered in search for insertion point.
         handle unbal = null();
         // Parent of last unbalanced node.
         handle parent_unbal = null();
         // Balance factor of last unbalanced node.
         int unbal_bf;

         // Zero-based depth in tree.
         unsigned depth = 0, unbal_depth = 0;

         // Records a path into the tree.  If branch[n] is true, indicates
         // take greater branch from the nth node in the path, otherwise
         // take the less branch.  branch[0] gives branch from root, and
         // so on.
         BSet branch;

         handle hh = abs.root;
         handle parent = null();
         int cmp;

         do {
             if (get_bf(hh) != 0) {
                 unbal = hh;
                 parent_unbal = parent;
                 unbal_depth = depth;
             }
             cmp = cmp_n_n(h, hh);
             if (cmp == 0)
                 // Duplicate key.
                 return hh;
             parent = hh;
             hh = cmp < 0 ? get_lt(hh) : get_gt(hh);
             branch[depth++] = cmp > 0;
         } while (hh != null());

         //  Add node to insert as leaf of tree.
         if (cmp < 0)
             set_lt(parent, h);
         else
             set_gt(parent, h);

         depth = unbal_depth;

         if (unbal == null())
             hh = abs.root;
         else {
             cmp = branch[depth++] ? 1 : -1;
             unbal_bf = get_bf(unbal);
             if (cmp < 0)
                 unbal_bf--;
             else  // cmp > 0
                 unbal_bf++;
             hh = cmp < 0 ? get_lt(unbal) : get_gt(unbal);
             if ((unbal_bf != -2) && (unbal_bf != 2)) {
                 // No rebalancing of tree is necessary.
                 set_bf(unbal, unbal_bf);
                 unbal = null();
             }
         }

         if (hh != null())
             while (h != hh) {
                 cmp = branch[depth++] ? 1 : -1;
                 if (cmp < 0) {
                     set_bf(hh, -1);
                     hh = get_lt(hh);
                 } else { // cmp > 0
                     set_bf(hh, 1);
                     hh = get_gt(hh);
                 }
             }

         if (unbal != null()) {
             unbal = balance(unbal);
             if (parent_unbal == null())
                 abs.root = unbal;
             else {
                 depth = unbal_depth - 1;
                 cmp = branch[depth] ? 1 : -1;
                 if (cmp < 0)
                     set_lt(parent_unbal, unbal);
                 else  // cmp > 0
                     set_gt(parent_unbal, unbal);
             }
         }
     }

     return h;
 }

 template <class Abstractor, unsigned maxDepth, class BSet>
 inline typename AVLTree<Abstractor, maxDepth, BSet>::handle
 AVLTree<Abstractor, maxDepth, BSet>::search(key k, typename AVLTree<Abstractor, maxDepth, BSet>::SearchType st)
 {
     const int MASK_HIGH_BIT = (int) ~ ((~ (unsigned) 0) >> 1);

     int cmp, target_cmp;
     handle match_h = null();
     handle h = abs.root;

     if (st & LESS)
         target_cmp = 1;
     else if (st & GREATER)
         target_cmp = -1;
     else
         target_cmp = 0;

     while (h != null()) {
         cmp = cmp_k_n(k, h);
         if (cmp == 0) {
             if (st & EQUAL) {
                 match_h = h;
                 break;
             }
             cmp = -target_cmp;
         } else if (target_cmp != 0)
             if (!((cmp ^ target_cmp) & MASK_HIGH_BIT))
                 // cmp and target_cmp are both positive or both negative.
                 match_h = h;
         h = cmp < 0 ? get_lt(h) : get_gt(h);
     }

     return match_h;
 }

 template <class Abstractor, unsigned maxDepth, class BSet>
 inline typename AVLTree<Abstractor, maxDepth, BSet>::handle
 AVLTree<Abstractor, maxDepth, BSet>::search_least()
 {
     handle h = abs.root, parent = null();

     while (h != null()) {
         parent = h;
         h = get_lt(h);
     }

     return parent;
 }

 template <class Abstractor, unsigned maxDepth, class BSet>
 inline typename AVLTree<Abstractor, maxDepth, BSet>::handle
 AVLTree<Abstractor, maxDepth, BSet>::search_greatest()
 {
     handle h = abs.root, parent = null();

     while (h != null()) {
         parent = h;
         h = get_gt(h);
     }

     return parent;
 }

 template <class Abstractor, unsigned maxDepth, class BSet>
 inline typename AVLTree<Abstractor, maxDepth, BSet>::handle
 AVLTree<Abstractor, maxDepth, BSet>::remove(key k)
 {
     // Zero-based depth in tree.
     unsigned depth = 0, rm_depth;

     // Records a path into the tree.  If branch[n] is true, indicates
     // take greater branch from the nth node in the path, otherwise
     // take the less branch.  branch[0] gives branch from root, and
     // so on.
     BSet branch;

     handle h = abs.root;
     handle parent = null(), child;
     int cmp, cmp_shortened_sub_with_path = 0;

     for (;;) {
         if (h == null())
             // No node in tree with given key.
             return null();
         cmp = cmp_k_n(k, h);
         if (cmp == 0)
             // Found node to remove.
             break;
         parent = h;
         h = cmp < 0 ? get_lt(h) : get_gt(h);
         branch[depth++] = cmp > 0;
         cmp_shortened_sub_with_path = cmp;
     }
     handle rm = h;
     handle parent_rm = parent;
     rm_depth = depth;

     // If the node to remove is not a leaf node, we need to get a
     // leaf node, or a node with a single leaf as its child, to put
     // in the place of the node to remove.  We will get the greatest
     // node in the less subtree (of the node to remove), or the least
     // node in the greater subtree.  We take the leaf node from the
     // deeper subtree, if there is one.

     if (get_bf(h) < 0) {
         child = get_lt(h);
         branch[depth] = false;
         cmp = -1;
     } else {
         child = get_gt(h);
         branch[depth] = true;
         cmp = 1;
     }
     depth++;

     if (child != null()) {
         cmp = -cmp;
         do {
             parent = h;
             h = child;
             if (cmp < 0) {
                 child = get_lt(h);
                 branch[depth] = false;
             } else {
                 child = get_gt(h);
                 branch[depth] = true;
             }
             depth++;
         } while (child != null());

         if (parent == rm)
             // Only went through do loop once.  Deleted node will be replaced
             // in the tree structure by one of its immediate children.
             cmp_shortened_sub_with_path = -cmp;
         else
             cmp_shortened_sub_with_path = cmp;

         // Get the handle of the opposite child, which may not be null.
         child = cmp > 0 ? get_lt(h) : get_gt(h);
     }

     if (parent == null())
         // There were only 1 or 2 nodes in this tree.
         abs.root = child;
     else if (cmp_shortened_sub_with_path < 0)
         set_lt(parent, child);
     else
         set_gt(parent, child);

     // "path" is the parent of the subtree being eliminated or reduced
     // from a depth of 2 to 1.  If "path" is the node to be removed, we
     // set path to the node we're about to poke into the position of the
     // node to be removed.
     handle path = parent == rm ? h : parent;

     if (h != rm) {
         // Poke in the replacement for the node to be removed.
         set_lt(h, get_lt(rm));
         set_gt(h, get_gt(rm));
         set_bf(h, get_bf(rm));
         if (parent_rm == null())
             abs.root = h;
         else {
             depth = rm_depth - 1;
             if (branch[depth])
                 set_gt(parent_rm, h);
             else
                 set_lt(parent_rm, h);
         }
     }

     if (path != null()) {
         // Create a temporary linked list from the parent of the path node
         // to the root node.
         h = abs.root;
         parent = null();
         depth = 0;
         while (h != path) {
             if (branch[depth++]) {
                 child = get_gt(h);
                 set_gt(h, parent);
             } else {
                 child = get_lt(h);
                 set_lt(h, parent);
             }
             parent = h;
             h = child;
         }

         // Climb from the path node to the root node using the linked
         // list, restoring the tree structure and rebalancing as necessary.
         bool reduced_depth = true;
         int bf;
         cmp = cmp_shortened_sub_with_path;
         for (;;) {
             if (reduced_depth) {
                 bf = get_bf(h);
                 if (cmp < 0)
                     bf++;
                 else  // cmp > 0
                     bf--;
                 if ((bf == -2) || (bf == 2)) {
                     h = balance(h);
                     bf = get_bf(h);
                 } else
                     set_bf(h, bf);
                 reduced_depth = (bf == 0);
             }
             if (parent == null())
                 break;
             child = h;
             h = parent;
             cmp = branch[--depth] ? 1 : -1;
             if (cmp < 0)    {
                 parent = get_lt(h);
                 set_lt(h, child);
             } else {
                 parent = get_gt(h);
                 set_gt(h, child);
             }
         }
         abs.root = h;
     }

     return rm;
 }

 template <class Abstractor, unsigned maxDepth, class BSet>
 inline typename AVLTree<Abstractor, maxDepth, BSet>::handle
 AVLTree<Abstractor, maxDepth, BSet>::subst(handle new_node)
 {
     handle h = abs.root;
     handle parent = null();
     int cmp, last_cmp;

     /* Search for node already in tree with same key. */
     for (;;) {
         if (h == null())
             /* No node in tree with same key as new node. */
             return null();
         cmp = cmp_n_n(new_node, h);
         if (cmp == 0)
             /* Found the node to substitute new one for. */
             break;
         last_cmp = cmp;
         parent = h;
         h = cmp < 0 ? get_lt(h) : get_gt(h);
     }

     /* Copy tree housekeeping fields from node in tree to new node. */
     set_lt(new_node, get_lt(h));
     set_gt(new_node, get_gt(h));
     set_bf(new_node, get_bf(h));

     if (parent == null())
         /* New node is also new root. */
         abs.root = new_node;
     else {
         /* Make parent point to new node. */
         if (last_cmp < 0)
             set_lt(parent, new_node);
         else
             set_gt(parent, new_node);
     }

     return h;
 }

 }

 #endif
	/*
	* Copyright (C) 2008 Apple Inc. All rights reserved.
	*
	* Based on Abstract AVL Tree Template v1.5 by Walt Karas
	* <http://geocities.com/wkaras/gen_cpp/avl_tree.html>.
	*
	* Redistribution and use in source and binary forms, with or without
	* modification, are permitted provided that the following conditions
	* are met:
	*
	* 1. Redistributions of source code must retain the above copyright
	* notice, this list of conditions and the following disclaimer.
	* 2. Redistributions in binary form must reproduce the above copyright
	* notice, this list of conditions and the following disclaimer in the
	* documentation and/or other materials provided with the distribution.
	* 3. Neither the name of Apple Computer, Inc. ("Apple") nor the names of
	* its contributors may be used to endorse or promote products derived
	* from this software without specific prior written permission.
	*
	* THIS SOFTWARE IS PROVIDED BY APPLE AND ITS CONTRIBUTORS "AS IS" AND ANY
	* EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
	* WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
	* DISCLAIMED. IN NO EVENT SHALL APPLE OR ITS CONTRIBUTORS BE LIABLE FOR ANY
	* DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
	* (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
	* LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
	* ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
	* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
	* THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
	*/

	#ifndef AVL_TREE_H_
	#define AVL_TREE_H_

	#include "Assertions.h"

	namespace WTF {

	// Here is the reference class for BSet.
	//
	// class BSet
	// {
	// public:
	//
	// class ANY_bitref
	// {
	// public:
	// operator bool ();
	// void operator = (bool b);
	// };
	//
	// // Does not have to initialize bits.
	// BSet();
	//
	// // Must return a valid value for index when 0 <= index < maxDepth
	// ANY_bitref operator [] (unsigned index);
	//
	// // Set all bits to 1.
	// void set();
	//
	// // Set all bits to 0.
	// void reset();
	// };

	template<unsigned maxDepth>
	class AVLTreeDefaultBSet {
	public:
	bool& operator[](unsigned i) { ASSERT(i < maxDepth); return m_data[i]; }
	void set() { for (unsigned i = 0; i < maxDepth; ++i) m_data[i] = true; }
	void reset() { for (unsigned i = 0; i < maxDepth; ++i) m_data[i] = false; }

	private:
	bool m_data[maxDepth];
	};

	// How to determine maxDepth:
	// d Minimum number of nodes
	// 2 2
	// 3 4
	// 4 7
	// 5 12
	// 6 20
	// 7 33
	// 8 54
	// 9 88
	// 10 143
	// 11 232
	// 12 376
	// 13 609
	// 14 986
	// 15 1,596
	// 16 2,583
	// 17 4,180
	// 18 6,764
	// 19 10,945
	// 20 17,710
	// 21 28,656
	// 22 46,367
	// 23 75,024
	// 24 121,392
	// 25 196,417
	// 26 317,810
	// 27 514,228
	// 28 832,039
	// 29 1,346,268
	// 30 2,178,308
	// 31 3,524,577
	// 32 5,702,886
	// 33 9,227,464
	// 34 14,930,351
	// 35 24,157,816
	// 36 39,088,168
	// 37 63,245,985
	// 38 102,334,154
	// 39 165,580,140
	// 40 267,914,295
	// 41 433,494,436
	// 42 701,408,732
	// 43 1,134,903,169
	// 44 1,836,311,902
	// 45 2,971,215,072
	//
	// 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.
	// 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.

	template <class Abstractor, unsigned maxDepth = 32, class BSet = AVLTreeDefaultBSet<maxDepth> >
	class AVLTree {
	public:

	typedef typename Abstractor::key key;
	typedef typename Abstractor::handle handle;
	typedef typename Abstractor::size size;

	enum SearchType {
	EQUAL = 1,
	LESS = 2,
	GREATER = 4,
	LESS_EQUAL = EQUAL \| LESS,
	GREATER_EQUAL = EQUAL \| GREATER
	};


	Abstractor& abstractor() { return abs; }

	inline handle insert(handle h);

	inline handle search(key k, SearchType st = EQUAL);
	inline handle search_least();
	inline handle search_greatest();

	inline handle remove(key k);

	inline handle subst(handle new_node);

	void purge() { abs.root = null(); }

	bool is_empty() { return abs.root == null(); }

	AVLTree() { abs.root = null(); }

	class Iterator {
	public:

	// Initialize depth to invalid value, to indicate iterator is
	// invalid. (Depth is zero-base.)
	Iterator() { depth = ~0U; }

	void start_iter(AVLTree &tree, key k, SearchType st = EQUAL)
	{
	// Mask of high bit in an int.
	const int MASK_HIGH_BIT = (int) ~ ((~ (unsigned) 0) >> 1);

	// Save the tree that we're going to iterate through in a
	// member variable.
	tree_ = &tree;

	int cmp, target_cmp;
	handle h = tree_->abs.root;
	unsigned d = 0;

	depth = ~0U;

	if (h == null())
	// Tree is empty.
	return;

	if (st & LESS)
	// Key can be greater than key of starting node.
	target_cmp = 1;
	else if (st & GREATER)
	// Key can be less than key of starting node.
	target_cmp = -1;
	else
	// Key must be same as key of starting node.
	target_cmp = 0;

	for (;;) {
	cmp = cmp_k_n(k, h);
	if (cmp == 0) {
	if (st & EQUAL) {
	// Equal node was sought and found as starting node.
	depth = d;
	break;
	}
	cmp = -target_cmp;
	} else if (target_cmp != 0) {
	if (!((cmp ^ target_cmp) & MASK_HIGH_BIT)) {
	// cmp and target_cmp are both negative or both positive.
	depth = d;
	}
	}
	h = cmp < 0 ? get_lt(h) : get_gt(h);
	if (h == null())
	break;
	branch[d] = cmp > 0;
	path_h[d++] = h;
	}
	}

	void start_iter_least(AVLTree &tree)
	{
	tree_ = &tree;

	handle h = tree_->abs.root;

	depth = ~0U;

	branch.reset();

	while (h != null()) {
	if (depth != ~0U)
	path_h[depth] = h;
	depth++;
	h = get_lt(h);
	}
	}

	void start_iter_greatest(AVLTree &tree)
	{
	tree_ = &tree;

	handle h = tree_->abs.root;

	depth = ~0U;

	branch.set();

	while (h != null()) {
	if (depth != ~0U)
	path_h[depth] = h;
	depth++;
	h = get_gt(h);
	}
	}

	handle operator*()
	{
	if (depth == ~0U)
	return null();

	return depth == 0 ? tree_->abs.root : path_h[depth - 1];
	}

	void operator++()
	{
	if (depth != ~0U) {
	handle h = get_gt(**this);
	if (h == null()) {
	do {
	if (depth == 0) {
	depth = ~0U;
	break;
	}
	depth--;
	} while (branch[depth]);
	} else {
	branch[depth] = true;
	path_h[depth++] = h;
	for (;;) {
	h = get_lt(h);
	if (h == null())
	break;
	branch[depth] = false;
	path_h[depth++] = h;
	}
	}
	}
	}

	void operator--()
	{
	if (depth != ~0U) {
	handle h = get_lt(**this);
	if (h == null())
	do {
	if (depth == 0) {
	depth = ~0U;
	break;
	}
	depth--;
	} while (!branch[depth]);
	else {
	branch[depth] = false;
	path_h[depth++] = h;
	for (;;) {
	h = get_gt(h);
	if (h == null())
	break;
	branch[depth] = true;
	path_h[depth++] = h;
	}
	}
	}
	}

	void operator++(int) { ++(*this); }
	void operator--(int) { --(*this); }

	protected:

	// Tree being iterated over.
	AVLTree *tree_;

	// Records a path into the tree. If branch[n] is true, indicates
	// take greater branch from the nth node in the path, otherwise
	// take the less branch. branch[0] gives branch from root, and
	// so on.
	BSet branch;

	// Zero-based depth of path into tree.
	unsigned depth;

	// Handles of nodes in path from root to current node (returned by *).
	handle path_h[maxDepth - 1];

	int cmp_k_n(key k, handle h) { return tree_->abs.compare_key_node(k, h); }
	int cmp_n_n(handle h1, handle h2) { return tree_->abs.compare_node_node(h1, h2); }
	handle get_lt(handle h) { return tree_->abs.get_less(h); }
	handle get_gt(handle h) { return tree_->abs.get_greater(h); }
	handle null() { return tree_->abs.null(); }
	};

	template<typename fwd_iter>
	bool build(fwd_iter p, size num_nodes)
	{
	if (num_nodes == 0) {
	abs.root = null();
	return true;
	}

	// Gives path to subtree being built. If branch[N] is false, branch
	// less from the node at depth N, if true branch greater.
	BSet branch;

	// If rem[N] is true, then for the current subtree at depth N, it's
	// greater subtree has one more node than it's less subtree.
	BSet rem;

	// Depth of root node of current subtree.
	unsigned depth = 0;

	// Number of nodes in current subtree.
	size num_sub = num_nodes;

	// The algorithm relies on a stack of nodes whose less subtree has
	// been built, but whose right subtree has not yet been built. The
	// stack is implemented as linked list. The nodes are linked
	// together by having the "greater" handle of a node set to the
	// next node in the list. "less_parent" is the handle of the first
	// node in the list.
	handle less_parent = null();

	// h is root of current subtree, child is one of its children.
	handle h, child;

	for (;;) {
	while (num_sub > 2) {
	// Subtract one for root of subtree.
	num_sub--;
	rem[depth] = !!(num_sub & 1);
	branch[depth++] = false;
	num_sub >>= 1;
	}

	if (num_sub == 2) {
	// Build a subtree with two nodes, slanting to greater.
	// I arbitrarily chose to always have the extra node in the
	// greater subtree when there is an odd number of nodes to
	// split between the two subtrees.

	h = *p;
	p++;
	child = *p;
	p++;
	set_lt(child, null());
	set_gt(child, null());
	set_bf(child, 0);
	set_gt(h, child);
	set_lt(h, null());
	set_bf(h, 1);
	} else { // num_sub == 1
	// Build a subtree with one node.

	h = *p;
	p++;
	set_lt(h, null());
	set_gt(h, null());
	set_bf(h, 0);
	}

	while (depth) {
	depth--;
	if (!branch[depth])
	// We've completed a less subtree.
	break;

	// We've completed a greater subtree, so attach it to
	// its parent (that is less than it). We pop the parent
	// off the stack of less parents.
	child = h;
	h = less_parent;
	less_parent = get_gt(h);
	set_gt(h, child);
	// num_sub = 2 * (num_sub - rem[depth]) + rem[depth] + 1
	num_sub <<= 1;
	num_sub += 1 - rem[depth];
	if (num_sub & (num_sub - 1))
	// num_sub is not a power of 2
	set_bf(h, 0);
	else
	// num_sub is a power of 2
	set_bf(h, 1);
	}

	if (num_sub == num_nodes)
	// We've completed the full tree.
	break;

	// The subtree we've completed is the less subtree of the
	// next node in the sequence.

	child = h;
	h = *p;
	p++;
	set_lt(h, child);

	// Put h into stack of less parents.
	set_gt(h, less_parent);
	less_parent = h;

	// Proceed to creating greater than subtree of h.
	branch[depth] = true;
	num_sub += rem[depth++];

	} // end for (;;)

	abs.root = h;

	return true;
	}

	protected:

	friend class Iterator;

	// Create a class whose sole purpose is to take advantage of
	// the "empty member" optimization.
	struct abs_plus_root : public Abstractor {
	// The handle of the root element in the AVL tree.
	handle root;
	};

	abs_plus_root abs;


	handle get_lt(handle h) { return abs.get_less(h); }
	void set_lt(handle h, handle lh) { abs.set_less(h, lh); }

	handle get_gt(handle h) { return abs.get_greater(h); }
	void set_gt(handle h, handle gh) { abs.set_greater(h, gh); }

	int get_bf(handle h) { return abs.get_balance_factor(h); }
	void set_bf(handle h, int bf) { abs.set_balance_factor(h, bf); }

	int cmp_k_n(key k, handle h) { return abs.compare_key_node(k, h); }
	int cmp_n_n(handle h1, handle h2) { return abs.compare_node_node(h1, h2); }

	handle null() { return abs.null(); }

	private:

	// Balances subtree, returns handle of root node of subtree
	// after balancing.
	handle balance(handle bal_h)
	{
	handle deep_h;

	// Either the "greater than" or the "less than" subtree of
	// this node has to be 2 levels deeper (or else it wouldn't
	// need balancing).

	if (get_bf(bal_h) > 0) {
	// "Greater than" subtree is deeper.

	deep_h = get_gt(bal_h);

	if (get_bf(deep_h) < 0) {
	handle old_h = bal_h;
	bal_h = get_lt(deep_h);

	set_gt(old_h, get_lt(bal_h));
	set_lt(deep_h, get_gt(bal_h));
	set_lt(bal_h, old_h);
	set_gt(bal_h, deep_h);

	int bf = get_bf(bal_h);
	if (bf != 0) {
	if (bf > 0) {
	set_bf(old_h, -1);
	set_bf(deep_h, 0);
	} else {
	set_bf(deep_h, 1);
	set_bf(old_h, 0);
	}
	set_bf(bal_h, 0);
	} else {
	set_bf(old_h, 0);
	set_bf(deep_h, 0);
	}
	} else {
	set_gt(bal_h, get_lt(deep_h));
	set_lt(deep_h, bal_h);
	if (get_bf(deep_h) == 0) {
	set_bf(deep_h, -1);
	set_bf(bal_h, 1);
	} else {
	set_bf(deep_h, 0);
	set_bf(bal_h, 0);
	}
	bal_h = deep_h;
	}
	} else {
	// "Less than" subtree is deeper.

	deep_h = get_lt(bal_h);

	if (get_bf(deep_h) > 0) {
	handle old_h = bal_h;
	bal_h = get_gt(deep_h);
	set_lt(old_h, get_gt(bal_h));
	set_gt(deep_h, get_lt(bal_h));
	set_gt(bal_h, old_h);
	set_lt(bal_h, deep_h);

	int bf = get_bf(bal_h);
	if (bf != 0) {
	if (bf < 0) {
	set_bf(old_h, 1);
	set_bf(deep_h, 0);
	} else {
	set_bf(deep_h, -1);
	set_bf(old_h, 0);
	}
	set_bf(bal_h, 0);
	} else {
	set_bf(old_h, 0);
	set_bf(deep_h, 0);
	}
	} else {
	set_lt(bal_h, get_gt(deep_h));
	set_gt(deep_h, bal_h);
	if (get_bf(deep_h) == 0) {
	set_bf(deep_h, 1);
	set_bf(bal_h, -1);
	} else {
	set_bf(deep_h, 0);
	set_bf(bal_h, 0);
	}
	bal_h = deep_h;
	}
	}

	return bal_h;
	}

	};

	template <class Abstractor, unsigned maxDepth, class BSet>
	inline typename AVLTree<Abstractor, maxDepth, BSet>::handle
	AVLTree<Abstractor, maxDepth, BSet>::insert(handle h)
	{
	set_lt(h, null());
	set_gt(h, null());
	set_bf(h, 0);

	if (abs.root == null())
	abs.root = h;
	else {
	// Last unbalanced node encountered in search for insertion point.
	handle unbal = null();
	// Parent of last unbalanced node.
	handle parent_unbal = null();
	// Balance factor of last unbalanced node.
	int unbal_bf;

	// Zero-based depth in tree.
	unsigned depth = 0, unbal_depth = 0;

	// Records a path into the tree. If branch[n] is true, indicates
	// take greater branch from the nth node in the path, otherwise
	// take the less branch. branch[0] gives branch from root, and
	// so on.
	BSet branch;

	handle hh = abs.root;
	handle parent = null();
	int cmp;

	do {
	if (get_bf(hh) != 0) {
	unbal = hh;
	parent_unbal = parent;
	unbal_depth = depth;
	}
	cmp = cmp_n_n(h, hh);
	if (cmp == 0)
	// Duplicate key.
	return hh;
	parent = hh;
	hh = cmp < 0 ? get_lt(hh) : get_gt(hh);
	branch[depth++] = cmp > 0;
	} while (hh != null());

	// Add node to insert as leaf of tree.
	if (cmp < 0)
	set_lt(parent, h);
	else
	set_gt(parent, h);

	depth = unbal_depth;

	if (unbal == null())
	hh = abs.root;
	else {
	cmp = branch[depth++] ? 1 : -1;
	unbal_bf = get_bf(unbal);
	if (cmp < 0)
	unbal_bf--;
	else // cmp > 0
	unbal_bf++;
	hh = cmp < 0 ? get_lt(unbal) : get_gt(unbal);
	if ((unbal_bf != -2) && (unbal_bf != 2)) {
	// No rebalancing of tree is necessary.
	set_bf(unbal, unbal_bf);
	unbal = null();
	}
	}

	if (hh != null())
	while (h != hh) {
	cmp = branch[depth++] ? 1 : -1;
	if (cmp < 0) {
	set_bf(hh, -1);
	hh = get_lt(hh);
	} else { // cmp > 0
	set_bf(hh, 1);
	hh = get_gt(hh);
	}
	}

	if (unbal != null()) {
	unbal = balance(unbal);
	if (parent_unbal == null())
	abs.root = unbal;
	else {
	depth = unbal_depth - 1;
	cmp = branch[depth] ? 1 : -1;
	if (cmp < 0)
	set_lt(parent_unbal, unbal);
	else // cmp > 0
	set_gt(parent_unbal, unbal);
	}
	}
	}

	return h;
	}

	template <class Abstractor, unsigned maxDepth, class BSet>
	inline typename AVLTree<Abstractor, maxDepth, BSet>::handle
	AVLTree<Abstractor, maxDepth, BSet>::search(key k, typename AVLTree<Abstractor, maxDepth, BSet>::SearchType st)
	{
	const int MASK_HIGH_BIT = (int) ~ ((~ (unsigned) 0) >> 1);

	int cmp, target_cmp;
	handle match_h = null();
	handle h = abs.root;

	if (st & LESS)
	target_cmp = 1;
	else if (st & GREATER)
	target_cmp = -1;
	else
	target_cmp = 0;

	while (h != null()) {
	cmp = cmp_k_n(k, h);
	if (cmp == 0) {
	if (st & EQUAL) {
	match_h = h;
	break;
	}
	cmp = -target_cmp;
	} else if (target_cmp != 0)
	if (!((cmp ^ target_cmp) & MASK_HIGH_BIT))
	// cmp and target_cmp are both positive or both negative.
	match_h = h;
	h = cmp < 0 ? get_lt(h) : get_gt(h);
	}

	return match_h;
	}

	template <class Abstractor, unsigned maxDepth, class BSet>
	inline typename AVLTree<Abstractor, maxDepth, BSet>::handle
	AVLTree<Abstractor, maxDepth, BSet>::search_least()
	{
	handle h = abs.root, parent = null();

	while (h != null()) {
	parent = h;
	h = get_lt(h);
	}

	return parent;
	}

	template <class Abstractor, unsigned maxDepth, class BSet>
	inline typename AVLTree<Abstractor, maxDepth, BSet>::handle
	AVLTree<Abstractor, maxDepth, BSet>::search_greatest()
	{
	handle h = abs.root, parent = null();

	while (h != null()) {
	parent = h;
	h = get_gt(h);
	}

	return parent;
	}

	template <class Abstractor, unsigned maxDepth, class BSet>
	inline typename AVLTree<Abstractor, maxDepth, BSet>::handle
	AVLTree<Abstractor, maxDepth, BSet>::remove(key k)
	{
	// Zero-based depth in tree.
	unsigned depth = 0, rm_depth;

	// Records a path into the tree. If branch[n] is true, indicates
	// take greater branch from the nth node in the path, otherwise
	// take the less branch. branch[0] gives branch from root, and
	// so on.
	BSet branch;

	handle h = abs.root;
	handle parent = null(), child;
	int cmp, cmp_shortened_sub_with_path = 0;

	for (;;) {
	if (h == null())
	// No node in tree with given key.
	return null();
	cmp = cmp_k_n(k, h);
	if (cmp == 0)
	// Found node to remove.
	break;
	parent = h;
	h = cmp < 0 ? get_lt(h) : get_gt(h);
	branch[depth++] = cmp > 0;
	cmp_shortened_sub_with_path = cmp;
	}
	handle rm = h;
	handle parent_rm = parent;
	rm_depth = depth;

	// If the node to remove is not a leaf node, we need to get a
	// leaf node, or a node with a single leaf as its child, to put
	// in the place of the node to remove. We will get the greatest
	// node in the less subtree (of the node to remove), or the least
	// node in the greater subtree. We take the leaf node from the
	// deeper subtree, if there is one.

	if (get_bf(h) < 0) {
	child = get_lt(h);
	branch[depth] = false;
	cmp = -1;
	} else {
	child = get_gt(h);
	branch[depth] = true;
	cmp = 1;
	}
	depth++;

	if (child != null()) {
	cmp = -cmp;
	do {
	parent = h;
	h = child;
	if (cmp < 0) {
	child = get_lt(h);
	branch[depth] = false;
	} else {
	child = get_gt(h);
	branch[depth] = true;
	}
	depth++;
	} while (child != null());

	if (parent == rm)
	// Only went through do loop once. Deleted node will be replaced
	// in the tree structure by one of its immediate children.
	cmp_shortened_sub_with_path = -cmp;
	else
	cmp_shortened_sub_with_path = cmp;

	// Get the handle of the opposite child, which may not be null.
	child = cmp > 0 ? get_lt(h) : get_gt(h);
	}

	if (parent == null())
	// There were only 1 or 2 nodes in this tree.
	abs.root = child;
	else if (cmp_shortened_sub_with_path < 0)
	set_lt(parent, child);
	else
	set_gt(parent, child);

	// "path" is the parent of the subtree being eliminated or reduced
	// from a depth of 2 to 1. If "path" is the node to be removed, we
	// set path to the node we're about to poke into the position of the
	// node to be removed.
	handle path = parent == rm ? h : parent;

	if (h != rm) {
	// Poke in the replacement for the node to be removed.
	set_lt(h, get_lt(rm));
	set_gt(h, get_gt(rm));
	set_bf(h, get_bf(rm));
	if (parent_rm == null())
	abs.root = h;
	else {
	depth = rm_depth - 1;
	if (branch[depth])
	set_gt(parent_rm, h);
	else
	set_lt(parent_rm, h);
	}
	}

	if (path != null()) {
	// Create a temporary linked list from the parent of the path node
	// to the root node.
	h = abs.root;
	parent = null();
	depth = 0;
	while (h != path) {
	if (branch[depth++]) {
	child = get_gt(h);
	set_gt(h, parent);
	} else {
	child = get_lt(h);
	set_lt(h, parent);
	}
	parent = h;
	h = child;
	}

	// Climb from the path node to the root node using the linked
	// list, restoring the tree structure and rebalancing as necessary.
	bool reduced_depth = true;
	int bf;
	cmp = cmp_shortened_sub_with_path;
	for (;;) {
	if (reduced_depth) {
	bf = get_bf(h);
	if (cmp < 0)
	bf++;
	else // cmp > 0
	bf--;
	if ((bf == -2) \|\| (bf == 2)) {
	h = balance(h);
	bf = get_bf(h);
	} else
	set_bf(h, bf);
	reduced_depth = (bf == 0);
	}
	if (parent == null())
	break;
	child = h;
	h = parent;
	cmp = branch[--depth] ? 1 : -1;
	if (cmp < 0) {
	parent = get_lt(h);
	set_lt(h, child);
	} else {
	parent = get_gt(h);
	set_gt(h, child);
	}
	}
	abs.root = h;
	}

	return rm;
	}

	template <class Abstractor, unsigned maxDepth, class BSet>
	inline typename AVLTree<Abstractor, maxDepth, BSet>::handle
	AVLTree<Abstractor, maxDepth, BSet>::subst(handle new_node)
	{
	handle h = abs.root;
	handle parent = null();
	int cmp, last_cmp;

	/* Search for node already in tree with same key. */
	for (;;) {
	if (h == null())
	/* No node in tree with same key as new node. */
	return null();
	cmp = cmp_n_n(new_node, h);
	if (cmp == 0)
	/* Found the node to substitute new one for. */
	break;
	last_cmp = cmp;
	parent = h;
	h = cmp < 0 ? get_lt(h) : get_gt(h);
	}

	/* Copy tree housekeeping fields from node in tree to new node. */
	set_lt(new_node, get_lt(h));
	set_gt(new_node, get_gt(h));
	set_bf(new_node, get_bf(h));

	if (parent == null())
	/* New node is also new root. */
	abs.root = new_node;
	else {
	/* Make parent point to new node. */
	if (last_cmp < 0)
	set_lt(parent, new_node);
	else
	set_gt(parent, new_node);
	}

	return h;
	}

	}

	#endif