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