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