| /* |
| * 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 <wtf/Assertions.h> |
| #include <wtf/FixedArray.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: |
| FixedArray<bool, maxDepth> m_data; |
| }; |
| |
| // 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 |