1 // AVLTreeMap.h 2 // 3 // Copyright (c) 2003, Ingo Weinhold (bonefish@cs.tu-berlin.de) 4 // 5 // Permission is hereby granted, free of charge, to any person obtaining a 6 // copy of this software and associated documentation files (the "Software"), 7 // to deal in the Software without restriction, including without limitation 8 // the rights to use, copy, modify, merge, publish, distribute, sublicense, 9 // and/or sell copies of the Software, and to permit persons to whom the 10 // Software is furnished to do so, subject to the following conditions: 11 // 12 // The above copyright notice and this permission notice shall be included in 13 // all copies or substantial portions of the Software. 14 // 15 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 16 // IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 17 // FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL 18 // THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER 19 // LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING 20 // FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER 21 // DEALINGS IN THE SOFTWARE. 22 // 23 // Except as contained in this notice, the name of a copyright holder shall 24 // not be used in advertising or otherwise to promote the sale, use or other 25 // dealings in this Software without prior written authorization of the 26 // copyright holder. 27 28 #ifndef _AVL_TREE_MAP_H 29 #define _AVL_TREE_MAP_H 30 31 #include <new> 32 33 #include <OS.h> 34 35 #include "MallocFreeAllocator.h" 36 37 // maximal height of a tree 38 static const int kMaxAVLTreeHeight = 32; 39 40 // strategies 41 namespace AVLTreeMapStrategy { 42 // key orders 43 template<typename Value> class Ascending; 44 template<typename Value> class Descending; 45 46 //! Automatic node strategy (works like STL containers do) 47 template <typename Key, typename Value, 48 typename KeyOrder = Ascending<Key>, 49 template <typename> class Allocator = MallocFreeAllocator> 50 class Auto; 51 52 //! User managed node strategy (user is responsible for node allocation/deallocation) 53 // template <class Node, Node* Node::* NextMember = &Node::next> 54 // class User; 55 56 // NodeStrategy::Node must implement this interface. 57 // struct Node { 58 // Node *parent; 59 // Node *left; 60 // Node *right; 61 // int balance_factor; 62 // }; 63 } 64 65 template<typename Parent> class AVLTreeMapIterator; 66 template<typename Parent> class AVLTreeMapEntry; 67 template<typename Parent> class AVLTreeMapEntryPointer; 68 69 // for convenience 70 #define _AVL_TREE_MAP_TEMPLATE_LIST template<typename Key, typename Value, \ 71 typename NodeStrategy> 72 #define _AVL_TREE_MAP_CLASS_NAME AVLTreeMap<Key, Value, NodeStrategy> 73 74 // AVLTreeMap 75 template<typename Key, typename Value, 76 typename NodeStrategy = AVLTreeMapStrategy::Auto<Key, Value> > 77 class AVLTreeMap { 78 private: 79 typedef typename NodeStrategy::Node Node; 80 typedef _AVL_TREE_MAP_CLASS_NAME Class; 81 typedef AVLTreeMapEntry<Class> Entry; 82 83 public: 84 class Entry; 85 class Iterator; 86 class ConstIterator; 87 88 public: 89 AVLTreeMap(); 90 ~AVLTreeMap(); 91 92 inline int Count() const { return fNodeCount; } 93 inline bool IsEmpty() const { return (fNodeCount == 0); } 94 void MakeEmpty(); 95 96 inline Iterator Begin() { return ++Iterator(this, NULL); } 97 inline ConstIterator Begin() const { return ++ConstIterator(this, NULL); } 98 inline Iterator End() { return Iterator(this, NULL); } 99 inline ConstIterator End() const { return ConstIterator(this, NULL); } 100 inline Iterator Null() { return Iterator(this, NULL); } 101 inline ConstIterator Null() const { return ConstIterator(this, NULL); } 102 103 Iterator Find(const Key &key); 104 Iterator FindClose(const Key &key, bool less); 105 106 status_t Insert(const Key &key, const Value &value, Iterator &iterator); 107 status_t Remove(const Key &key); 108 Iterator Erase(const Iterator &iterator); 109 110 // debugging 111 int Check(Node *node = NULL, int level = 0, bool levelsOnly = false) const; 112 113 protected: 114 enum { 115 NOT_FOUND = -3, 116 DUPLICATE = -2, 117 NO_MEMORY = -1, 118 OK = 0, 119 HEIGHT_CHANGED = 1, 120 121 LEFT = -1, 122 BALANCED = 0, 123 RIGHT = 1, 124 }; 125 126 // rotations 127 void _RotateRight(Node **nodeP); 128 void _RotateLeft(Node **nodeP); 129 130 // insert 131 int _BalanceInsertLeft(Node **node); 132 int _BalanceInsertRight(Node **node); 133 int _Insert(const Key &key, const Value &value, Node **node, 134 Iterator *iterator); 135 136 // remove 137 int _BalanceRemoveLeft(Node **node); 138 int _BalanceRemoveRight(Node **node); 139 int _RemoveRightMostChild(Node **node, Node **foundNode); 140 int _Remove(const Key &key, Node **node); 141 int _Remove(Node *node); 142 143 void _FreeTree(Node *node); 144 145 // debugging 146 void _DumpNode(Node *node) const; 147 148 // strategy shortcuts 149 inline Node *Allocate(const Key &key, const Value &value); 150 inline void Free(Node *node); 151 inline Key &GetKey(Node *node) const; 152 inline Value &GetValue(Node *node) const; 153 inline int Compare(const Key &a, const Key &b); 154 155 protected: 156 friend class Entry; 157 friend class Iterator; 158 friend class ConstIterator; 159 friend AVLTreeMapIterator<Class>; 160 friend AVLTreeMapIterator<const Class>; 161 162 Node *fRoot; 163 int fNodeCount; 164 NodeStrategy fStrategy; 165 166 // Iterator 167 class Iterator : public AVLTreeMapIterator<_AVL_TREE_MAP_CLASS_NAME> { 168 private: 169 typedef AVLTreeMapIterator<_AVL_TREE_MAP_CLASS_NAME> SuperClass; 170 171 public: 172 inline Iterator(); 173 inline Iterator(const Iterator &other); 174 175 inline Iterator &operator++(); 176 inline Iterator operator++(int); 177 inline Iterator &operator--(); 178 inline Iterator operator--(int); 179 inline Iterator &operator=(Iterator &other); 180 181 private: 182 inline Iterator(_AVL_TREE_MAP_CLASS_NAME *parent, Node *node = NULL); 183 184 friend class _AVL_TREE_MAP_CLASS_NAME; 185 }; 186 187 // ConstIterator 188 class ConstIterator 189 : public AVLTreeMapIterator<const _AVL_TREE_MAP_CLASS_NAME> { 190 private: 191 typedef AVLTreeMapIterator<const _AVL_TREE_MAP_CLASS_NAME> SuperClass; 192 193 public: 194 inline ConstIterator(); 195 inline ConstIterator(const ConstIterator &other); 196 inline ConstIterator(const Iterator &other); 197 198 inline ConstIterator &operator++(); 199 inline ConstIterator operator++(int); 200 inline ConstIterator &operator--(); 201 inline ConstIterator operator--(int); 202 inline ConstIterator &operator=(ConstIterator &other); 203 inline ConstIterator &operator=(Iterator &other); 204 205 private: 206 inline ConstIterator(const _AVL_TREE_MAP_CLASS_NAME *parent, 207 Node *node = NULL); 208 209 friend class _AVL_TREE_MAP_CLASS_NAME; 210 }; 211 }; 212 213 214 // AVLTreeMapEntry 215 template<typename Parent> 216 class AVLTreeMapEntry { 217 public: 218 AVLTreeMapEntry() 219 : fParent(NULL), fNode(NULL) {} 220 AVLTreeMapEntry(const AVLTreeMapEntry &other) 221 : fParent(other.fParent), fNode(other.fNode) {} 222 223 inline const Parent::Key &Key() const 224 { return fParent->GetKey(fNode); } 225 inline const Parent::Value &Value() const 226 { return fParent->GetValue(fNode); } 227 228 private: 229 AVLTreeMapEntry(const Parent *parent, Parent::Node *node) 230 : fParent(parent), fNode(node) {} 231 232 private: 233 friend class AVLTreeMapEntryPointer<Parent>; 234 friend class AVLTreeMapIterator<Parent>; 235 friend class AVLTreeMapIterator<const Parent>; 236 237 const Parent *fParent; 238 Parent::Node *fNode; 239 }; 240 241 // AVLTreeMapEntryPointer 242 template<typename Parent> 243 class AVLTreeMapEntryPointer { 244 public: 245 inline const Entry *operator->() const 246 { 247 return &fEntry; 248 } 249 250 private: 251 AVLTreeMapEntryPointer(const Parent *parent, Parent::Node *node) 252 : fEntry(parent, node) {} 253 254 AVLTreeMapEntryPointer(const AVLTreeMapEntryPointer &); 255 AVLTreeMapEntryPointer &operator=(const AVLTreeMapEntryPointer &); 256 257 private: 258 friend class AVLTreeMapIterator<Parent>; 259 friend class AVLTreeMapIterator<const Parent>; 260 261 AVLTreeMapEntry<Parent> fEntry; 262 }; 263 264 // AVLTreeMapIterator 265 template<typename Parent> 266 class AVLTreeMapIterator { 267 private: 268 typedef AVLTreeMapIterator<Value, Parent> Iterator; 269 typedef typename Parent::Node Node; 270 typedef typename Parent::Entry Entry; 271 typedef AVLTreeMapEntryPointer<Parent::Class> EntryPointer; 272 273 public: 274 inline bool operator==(const Iterator &other) const 275 { 276 return (fParent == other.fParent && fCurrent == other.fCurrent); 277 } 278 279 inline bool operator!=(const Iterator &other) const 280 { 281 return !(*this == other); 282 } 283 284 inline const Entry operator*() const 285 { 286 return Entry(fParent, fCurrent); 287 } 288 289 inline const EntryPointer operator->() const 290 { 291 return EntryPointer(fParent, fCurrent); 292 } 293 294 protected: 295 inline AVLTreeMapIterator() 296 : fParent(NULL), 297 fCurrent(NULL) 298 { 299 } 300 301 inline AVLTreeMapIterator(const Iterator &other) 302 : fParent(other.fParent), 303 fCurrent(other.fCurrent) 304 { 305 } 306 307 inline AVLTreeMapIterator(Parent *parent, Node *node = NULL) 308 : fParent(parent), 309 fCurrent(node) 310 { 311 } 312 313 inline Iterator &operator++() 314 { 315 if (fCurrent) 316 fCurrent = _GetNextNode(fCurrent); 317 else if (fParent) 318 fCurrent = _GetLeftMostNode(fParent->fRoot); 319 return *this; 320 } 321 322 inline Iterator operator++(int) 323 { 324 Iterator it(*this); 325 ++*this; 326 return it; 327 } 328 329 inline Iterator &operator--() 330 { 331 if (fCurrent) 332 fCurrent = _GetPreviousNode(fCurrent); 333 else if (fParent) 334 fCurrent = _GetRightMostNode(fParent->fRoot); 335 return *this; 336 } 337 338 inline Iterator operator--(int) 339 { 340 Iterator it(*this); 341 --*this; 342 return it; 343 } 344 345 inline Iterator &operator=(const Iterator &other) 346 { 347 fParent = other.fParent; 348 fCurrent = other.fCurrent; 349 return *this; 350 } 351 352 inline operator bool() const 353 { 354 return fCurrent; 355 } 356 357 private: 358 static inline Node *_GetPreviousNode(Node *node) 359 { 360 if (node) { 361 // The previous node cannot be in the right subtree. 362 if (node->left) { 363 // We have a left subtree, so go to the right-most node. 364 node = node->left; 365 while (node->right) 366 node = node->right; 367 } else { 368 // No left subtree: Backtrack our path and stop, where we 369 // took the right branch. 370 Node *previous; 371 do { 372 previous = node; 373 node = node->parent; 374 } while (node && previous == node->left); 375 } 376 } 377 return node; 378 } 379 380 static inline Node *_GetNextNode(Node *node) 381 { 382 if (node) { 383 // The next node cannot be in the left subtree. 384 if (node->right) { 385 // We have a right subtree, so go to the left-most node. 386 node = node->right; 387 while (node->left) 388 node = node->left; 389 } else { 390 // No right subtree: Backtrack our path and stop, where we 391 // took the left branch. 392 Node *previous; 393 do { 394 previous = node; 395 node = node->parent; 396 } while (node && previous == node->right); 397 } 398 } 399 return node; 400 } 401 402 static inline Node *_GetLeftMostNode(Node *node) 403 { 404 if (node) { 405 while (node->left) 406 node = node->left; 407 } 408 return node; 409 } 410 411 static inline Node *_GetRightMostNode(Node *node) 412 { 413 if (node) { 414 while (node->right) 415 node = node->right; 416 } 417 return node; 418 } 419 420 protected: 421 Parent *fParent; 422 Node *fCurrent; 423 }; 424 425 // Iterator 426 427 _AVL_TREE_MAP_TEMPLATE_LIST 428 inline 429 _AVL_TREE_MAP_CLASS_NAME::Iterator::Iterator() 430 : SuperClass() 431 { 432 } 433 434 _AVL_TREE_MAP_TEMPLATE_LIST 435 inline 436 _AVL_TREE_MAP_CLASS_NAME::Iterator::Iterator(const Iterator &other) 437 : SuperClass(other) 438 { 439 } 440 441 _AVL_TREE_MAP_TEMPLATE_LIST 442 inline 443 _AVL_TREE_MAP_CLASS_NAME::Iterator & 444 _AVL_TREE_MAP_CLASS_NAME::Iterator::operator++() 445 { 446 SuperClass::operator++(); 447 return *this; 448 } 449 450 _AVL_TREE_MAP_TEMPLATE_LIST 451 inline 452 _AVL_TREE_MAP_CLASS_NAME::Iterator 453 _AVL_TREE_MAP_CLASS_NAME::Iterator::operator++(int) 454 { 455 Iterator it(*this); 456 ++*this; 457 return it; 458 } 459 460 _AVL_TREE_MAP_TEMPLATE_LIST 461 inline 462 _AVL_TREE_MAP_CLASS_NAME::Iterator & 463 _AVL_TREE_MAP_CLASS_NAME::Iterator::operator--() 464 { 465 SuperClass::operator--(); 466 return *this; 467 } 468 469 _AVL_TREE_MAP_TEMPLATE_LIST 470 inline 471 _AVL_TREE_MAP_CLASS_NAME::Iterator 472 _AVL_TREE_MAP_CLASS_NAME::Iterator::operator--(int) 473 { 474 Iterator it(*this); 475 --*this; 476 return it; 477 } 478 479 _AVL_TREE_MAP_TEMPLATE_LIST 480 inline 481 _AVL_TREE_MAP_CLASS_NAME::Iterator & 482 _AVL_TREE_MAP_CLASS_NAME::Iterator::operator=(Iterator &other) 483 { 484 *(SuperClass*)this = other; 485 return *this; 486 } 487 488 _AVL_TREE_MAP_TEMPLATE_LIST 489 inline 490 _AVL_TREE_MAP_CLASS_NAME::Iterator::Iterator(_AVL_TREE_MAP_CLASS_NAME *parent, 491 Node *node) 492 : SuperClass(parent, node) 493 { 494 } 495 496 // ConstIterator 497 498 _AVL_TREE_MAP_TEMPLATE_LIST 499 inline 500 _AVL_TREE_MAP_CLASS_NAME::ConstIterator::ConstIterator() 501 : SuperClass() 502 { 503 } 504 505 _AVL_TREE_MAP_TEMPLATE_LIST 506 inline 507 _AVL_TREE_MAP_CLASS_NAME::ConstIterator::ConstIterator( 508 const ConstIterator &other) 509 : SuperClass(other) 510 { 511 } 512 513 _AVL_TREE_MAP_TEMPLATE_LIST 514 inline 515 _AVL_TREE_MAP_CLASS_NAME::ConstIterator::ConstIterator(const Iterator &other) 516 : SuperClass(other.fParent, other.fCurrent) 517 { 518 } 519 520 _AVL_TREE_MAP_TEMPLATE_LIST 521 inline 522 _AVL_TREE_MAP_CLASS_NAME::ConstIterator & 523 _AVL_TREE_MAP_CLASS_NAME::ConstIterator::operator++() 524 { 525 SuperClass::operator++(); 526 return *this; 527 } 528 529 _AVL_TREE_MAP_TEMPLATE_LIST 530 inline 531 _AVL_TREE_MAP_CLASS_NAME::ConstIterator 532 _AVL_TREE_MAP_CLASS_NAME::ConstIterator::operator++(int) 533 { 534 ConstIterator it(*this); 535 ++*this; 536 return it; 537 } 538 539 _AVL_TREE_MAP_TEMPLATE_LIST 540 inline 541 _AVL_TREE_MAP_CLASS_NAME::ConstIterator & 542 _AVL_TREE_MAP_CLASS_NAME::ConstIterator::operator--() 543 { 544 SuperClass::operator--(); 545 return *this; 546 } 547 548 _AVL_TREE_MAP_TEMPLATE_LIST 549 inline 550 _AVL_TREE_MAP_CLASS_NAME::ConstIterator 551 _AVL_TREE_MAP_CLASS_NAME::ConstIterator::operator--(int) 552 { 553 Iterator it(*this); 554 --*this; 555 return it; 556 } 557 558 _AVL_TREE_MAP_TEMPLATE_LIST 559 inline 560 _AVL_TREE_MAP_CLASS_NAME::ConstIterator & 561 _AVL_TREE_MAP_CLASS_NAME::ConstIterator::operator=(ConstIterator &other) 562 { 563 *(SuperClass*)this = other; 564 return *this; 565 } 566 567 _AVL_TREE_MAP_TEMPLATE_LIST 568 inline 569 _AVL_TREE_MAP_CLASS_NAME::ConstIterator & 570 _AVL_TREE_MAP_CLASS_NAME::ConstIterator::operator=(Iterator &other) 571 { 572 fParent = other.fParent; 573 fCurrent = other.fCurrent; 574 return *this; 575 } 576 577 _AVL_TREE_MAP_TEMPLATE_LIST 578 inline 579 _AVL_TREE_MAP_CLASS_NAME::ConstIterator::ConstIterator( 580 const _AVL_TREE_MAP_CLASS_NAME *parent, Node *node) 581 : SuperClass(parent, node) 582 { 583 } 584 585 586 // AVLTreeMap 587 588 // constructor 589 _AVL_TREE_MAP_TEMPLATE_LIST 590 _AVL_TREE_MAP_CLASS_NAME::AVLTreeMap() 591 : fRoot(NULL), 592 fNodeCount(0) 593 { 594 } 595 596 // destructor 597 _AVL_TREE_MAP_TEMPLATE_LIST 598 _AVL_TREE_MAP_CLASS_NAME::~AVLTreeMap() 599 { 600 _FreeTree(fRoot); 601 fRoot = NULL; 602 } 603 604 // MakeEmpty 605 _AVL_TREE_MAP_TEMPLATE_LIST 606 void 607 _AVL_TREE_MAP_CLASS_NAME::MakeEmpty() 608 { 609 _FreeTree(fRoot); 610 fRoot = NULL; 611 fNodeCount = 0; 612 } 613 614 // Find 615 _AVL_TREE_MAP_TEMPLATE_LIST 616 _AVL_TREE_MAP_CLASS_NAME::Iterator 617 _AVL_TREE_MAP_CLASS_NAME::Find(const Key &key) 618 { 619 Node *node = fRoot; 620 while (node) { 621 int cmp = Compare(key, GetKey(node)); 622 if (cmp == 0) 623 return Iterator(this, node); 624 if (cmp < 0) 625 node = node->left; 626 else 627 node = node->right; 628 } 629 return End(); 630 } 631 632 // FindClose 633 _AVL_TREE_MAP_TEMPLATE_LIST 634 _AVL_TREE_MAP_CLASS_NAME::Iterator 635 _AVL_TREE_MAP_CLASS_NAME::FindClose(const Key &key, bool less) 636 { 637 Node *node = fRoot; 638 Node *parent = NULL; 639 while (node) { 640 int cmp = Compare(key, GetKey(node)); 641 if (cmp == 0) 642 break; 643 parent = node; 644 if (cmp < 0) 645 node = node->left; 646 else 647 node = node->right; 648 } 649 // not found: try to get close 650 if (!node && parent) { 651 node = parent; 652 int expectedCmp = (less ? -1 : 1); 653 int cmp = Compare(GetKey(node), key); 654 if (cmp != expectedCmp) { 655 // The node's value is less although for a greater value was asked, 656 // or the other way around. We need to iterate to the next node in 657 // the right directory. If there is no node, we fail. 658 if (less) 659 return ++Iterator(this, node); 660 return --Iterator(this, node); 661 } 662 } 663 return Iterator(this, node); 664 } 665 666 // Insert 667 _AVL_TREE_MAP_TEMPLATE_LIST 668 status_t 669 _AVL_TREE_MAP_CLASS_NAME::Insert(const Key &key, const Value &value, 670 Iterator &iterator) 671 { 672 int result = _Insert(key, value, &fRoot, &iterator); 673 switch (result) { 674 case OK: 675 case HEIGHT_CHANGED: 676 return B_OK; 677 case NO_MEMORY: 678 return B_NO_MEMORY; 679 case DUPLICATE: 680 default: 681 return B_BAD_VALUE; 682 } 683 } 684 685 // Remove 686 _AVL_TREE_MAP_TEMPLATE_LIST 687 ssize_t 688 _AVL_TREE_MAP_CLASS_NAME::Remove(const Key &key) 689 { 690 // find node 691 Node *node = fRoot; 692 while (node) { 693 int cmp = Compare(key, GetKey(node)); 694 if (cmp == 0) 695 break; 696 else { 697 if (cmp < 0) 698 node = node->left; 699 else 700 node = node->right; 701 } 702 } 703 // remove it 704 int result = _Remove(node); 705 // set result 706 switch (result) { 707 case OK: 708 case HEIGHT_CHANGED: 709 return 1; 710 case NOT_FOUND: 711 default: 712 return 0; 713 } 714 } 715 716 // Erase 717 _AVL_TREE_MAP_TEMPLATE_LIST 718 _AVL_TREE_MAP_CLASS_NAME::Iterator 719 _AVL_TREE_MAP_CLASS_NAME::Erase(const Iterator &iterator) 720 { 721 Iterator it(iterator); 722 if (Node *node = it._GetCurrentNode()) { 723 it.GetNext(); 724 _Remove(node); 725 return it; 726 } 727 return End(); 728 } 729 730 // Check 731 _AVL_TREE_MAP_TEMPLATE_LIST 732 int 733 _AVL_TREE_MAP_CLASS_NAME::Check(Node *node, int level, bool levelsOnly) const 734 { 735 int height = 0; 736 if (node) { 737 // check root node parent 738 if (node == fRoot && node->parent != NULL) { 739 printf("Root node has parent: %p\n", node->parent); 740 debugger("Root node has parent."); 741 } 742 // check children's parents 743 if (node->left && node->left->parent != node) { 744 printf("Left child of node has has wrong parent: %p, should be: " 745 "%p\n", node->left->parent, node); 746 _DumpNode(node); 747 debugger("Left child node has wrong parent."); 748 } 749 if (node->right && node->right->parent != node) { 750 printf("Right child of node has has wrong parent: %p, should be: " 751 "%p\n", node->right->parent, node); 752 _DumpNode(node); 753 debugger("Right child node has wrong parent."); 754 } 755 // check heights 756 int leftHeight = Check(node->left, level + 1); 757 int rightHeight = Check(node->right, level + 1); 758 if (node->balance_factor != rightHeight - leftHeight) { 759 printf("Subtree %p at level %d has wrong balance factor: left " 760 "height: %d, right height: %d, balance factor: %d\n", 761 node, level, leftHeight, rightHeight, node->balance_factor); 762 _DumpNode(node); 763 debugger("Node has wrong balance factor."); 764 } 765 // check AVL property 766 if (!levelsOnly && (leftHeight - rightHeight > 1 767 || leftHeight - rightHeight < -1)) { 768 printf("Subtree %p at level %d violates the AVL property: left " 769 "height: %d, right height: %d\n", node, level, leftHeight, 770 rightHeight); 771 _DumpNode(node); 772 debugger("Node violates AVL property."); 773 } 774 height = (leftHeight > rightHeight ? leftHeight : rightHeight) + 1; 775 } 776 return height; 777 } 778 779 // _RotateRight 780 _AVL_TREE_MAP_TEMPLATE_LIST 781 void 782 _AVL_TREE_MAP_CLASS_NAME::_RotateRight(Node **nodeP) 783 { 784 // rotate the nodes 785 Node *node = *nodeP; 786 Node *left = node->left; 787 //printf("_RotateRight(): balance: node: %d, left: %d\n", 788 //node->balance_factor, left->balance_factor); 789 *nodeP = left; 790 left->parent = node->parent; 791 node->left = left->right; 792 if (left->right) 793 left->right->parent = node; 794 left->right = node; 795 node->parent = left; 796 // adjust the balance factors 797 // former pivot 798 if (left->balance_factor >= 0) 799 node->balance_factor++; 800 else 801 node->balance_factor += 1 - left->balance_factor; 802 // former left 803 if (node->balance_factor <= 0) 804 left->balance_factor++; 805 else 806 left->balance_factor += node->balance_factor + 1; 807 //printf("_RotateRight() end: balance: node: %d, left: %d\n", 808 //node->balance_factor, left->balance_factor); 809 } 810 811 // _RotateLeft 812 _AVL_TREE_MAP_TEMPLATE_LIST 813 void 814 _AVL_TREE_MAP_CLASS_NAME::_RotateLeft(Node **nodeP) 815 { 816 // rotate the nodes 817 Node *node = *nodeP; 818 Node *right = node->right; 819 //printf("_RotateLeft(): balance: node: %d, right: %d\n", 820 //node->balance_factor, right->balance_factor); 821 *nodeP = right; 822 right->parent = node->parent; 823 node->right = right->left; 824 if (right->left) 825 right->left->parent = node; 826 right->left = node; 827 node->parent = right; 828 // adjust the balance factors 829 // former pivot 830 if (right->balance_factor <= 0) 831 node->balance_factor--; 832 else 833 node->balance_factor -= right->balance_factor + 1; 834 // former right 835 if (node->balance_factor >= 0) 836 right->balance_factor--; 837 else 838 right->balance_factor += node->balance_factor - 1; 839 //printf("_RotateLeft() end: balance: node: %d, right: %d\n", 840 //node->balance_factor, right->balance_factor); 841 } 842 843 // _BalanceInsertLeft 844 _AVL_TREE_MAP_TEMPLATE_LIST 845 int 846 _AVL_TREE_MAP_CLASS_NAME::_BalanceInsertLeft(Node **node) 847 { 848 //printf("_BalanceInsertLeft()\n"); 849 //_DumpNode(*node); 850 //Check(*node, 0, true); 851 int result = HEIGHT_CHANGED; 852 if ((*node)->balance_factor < LEFT) { 853 // tree is left heavy 854 Node **left = &(*node)->left; 855 if ((*left)->balance_factor == LEFT) { 856 // left left heavy 857 _RotateRight(node); 858 } else { 859 // left right heavy 860 _RotateLeft(left); 861 _RotateRight(node); 862 } 863 result = OK; 864 } else if ((*node)->balance_factor == BALANCED) 865 result = OK; 866 //printf("_BalanceInsertLeft() done: %d\n", result); 867 return result; 868 } 869 870 // _BalanceInsertRight 871 _AVL_TREE_MAP_TEMPLATE_LIST 872 int 873 _AVL_TREE_MAP_CLASS_NAME::_BalanceInsertRight(Node **node) 874 { 875 //printf("_BalanceInsertRight()\n"); 876 //_DumpNode(*node); 877 //Check(*node, 0, true); 878 int result = HEIGHT_CHANGED; 879 if ((*node)->balance_factor > RIGHT) { 880 // tree is right heavy 881 Node **right = &(*node)->right; 882 if ((*right)->balance_factor == RIGHT) { 883 // right right heavy 884 _RotateLeft(node); 885 } else { 886 // right left heavy 887 _RotateRight(right); 888 _RotateLeft(node); 889 } 890 result = OK; 891 } else if ((*node)->balance_factor == BALANCED) 892 result = OK; 893 //printf("_BalanceInsertRight() done: %d\n", result); 894 return result; 895 } 896 897 // _Insert 898 _AVL_TREE_MAP_TEMPLATE_LIST 899 int 900 _AVL_TREE_MAP_CLASS_NAME::_Insert(const Key &key, const Value &value, 901 Node **node, Iterator *iterator) 902 { 903 struct node_info { 904 Node **node; 905 bool left; 906 }; 907 node_info stack[kMaxAVLTreeHeight]; 908 node_info *top = stack; 909 const node_info *const bottom = stack; 910 // find insertion point 911 while (*node) { 912 int cmp = Compare(key, GetKey(*node)); 913 if (cmp == 0) // duplicate node 914 return DUPLICATE; 915 else { 916 top->node = node; 917 if (cmp < 0) { 918 top->left = true; 919 node = &(*node)->left; 920 } else { 921 top->left = false; 922 node = &(*node)->right; 923 } 924 top++; 925 } 926 } 927 // allocate and insert node 928 *node = Allocate(key, value); 929 if (*node) { 930 (*node)->balance_factor = BALANCED; 931 fNodeCount++; 932 } else 933 return NO_MEMORY; 934 if (top != bottom) 935 (*node)->parent = *top[-1].node; 936 // init the iterator 937 if (iterator) 938 *iterator = Iterator(this, *node); 939 // do the balancing 940 int result = HEIGHT_CHANGED; 941 while (result == HEIGHT_CHANGED && top != bottom) { 942 top--; 943 node = top->node; 944 if (top->left) { 945 // left 946 (*node)->balance_factor--; 947 result = _BalanceInsertLeft(node); 948 } else { 949 // right 950 (*node)->balance_factor++; 951 result = _BalanceInsertRight(node); 952 } 953 } 954 //Check(*node); 955 return result; 956 } 957 958 // _BalanceRemoveLeft 959 _AVL_TREE_MAP_TEMPLATE_LIST 960 int 961 _AVL_TREE_MAP_CLASS_NAME::_BalanceRemoveLeft(Node **node) 962 { 963 //printf("_BalanceRemoveLeft()\n"); 964 //_DumpNode(*node); 965 //Check(*node, 0, true); 966 int result = HEIGHT_CHANGED; 967 if ((*node)->balance_factor > RIGHT) { 968 // tree is right heavy 969 Node **right = &(*node)->right; 970 if ((*right)->balance_factor == RIGHT) { 971 // right right heavy 972 _RotateLeft(node); 973 } else if ((*right)->balance_factor == BALANCED) { 974 // right none heavy 975 _RotateLeft(node); 976 result = OK; 977 } else { 978 // right left heavy 979 _RotateRight(right); 980 _RotateLeft(node); 981 } 982 } else if ((*node)->balance_factor == RIGHT) 983 result = OK; 984 //printf("_BalanceRemoveLeft() done: %d\n", result); 985 return result; 986 } 987 988 // _BalanceRemoveRight 989 _AVL_TREE_MAP_TEMPLATE_LIST 990 int 991 _AVL_TREE_MAP_CLASS_NAME::_BalanceRemoveRight(Node **node) 992 { 993 //printf("_BalanceRemoveRight()\n"); 994 //_DumpNode(*node); 995 //Check(*node, 0, true); 996 int result = HEIGHT_CHANGED; 997 if ((*node)->balance_factor < LEFT) { 998 // tree is left heavy 999 Node **left = &(*node)->left; 1000 if ((*left)->balance_factor == LEFT) { 1001 // left left heavy 1002 _RotateRight(node); 1003 } else if ((*left)->balance_factor == BALANCED) { 1004 // left none heavy 1005 _RotateRight(node); 1006 result = OK; 1007 } else { 1008 // left right heavy 1009 _RotateLeft(left); 1010 _RotateRight(node); 1011 } 1012 } else if ((*node)->balance_factor == LEFT) 1013 result = OK; 1014 //printf("_BalanceRemoveRight() done: %d\n", result); 1015 return result; 1016 } 1017 1018 // _RemoveRightMostChild 1019 _AVL_TREE_MAP_TEMPLATE_LIST 1020 int 1021 _AVL_TREE_MAP_CLASS_NAME::_RemoveRightMostChild(Node **node, Node **foundNode) 1022 { 1023 Node **stack[kMaxAVLTreeHeight]; 1024 Node ***top = stack; 1025 const Node *const *const *const bottom = stack; 1026 // find the child 1027 while ((*node)->right) { 1028 *top = node; 1029 top++; 1030 node = &(*node)->right; 1031 } 1032 // found the rightmost child: remove it 1033 // the found node might have a left child: replace the node with the 1034 // child 1035 *foundNode = *node; 1036 Node *left = (*node)->left; 1037 if (left) 1038 left->parent = (*node)->parent; 1039 *node = left; 1040 (*foundNode)->left = NULL; 1041 (*foundNode)->parent = NULL; 1042 // balancing 1043 int result = HEIGHT_CHANGED; 1044 while (result == HEIGHT_CHANGED && top != bottom) { 1045 top--; 1046 node = *top; 1047 (*node)->balance_factor--; 1048 result = _BalanceRemoveRight(node); 1049 } 1050 return result; 1051 } 1052 1053 // _Remove 1054 _AVL_TREE_MAP_TEMPLATE_LIST 1055 int 1056 _AVL_TREE_MAP_CLASS_NAME::_Remove(const Key &key, Node **node) 1057 { 1058 struct node_info { 1059 Node **node; 1060 bool left; 1061 }; 1062 node_info stack[kMaxAVLTreeHeight]; 1063 node_info *top = stack; 1064 const node_info *const bottom = stack; 1065 // find node 1066 while (*node) { 1067 int cmp = Compare(key, GetKey(*node)); 1068 if (cmp == 0) 1069 break; 1070 else { 1071 top->node = node; 1072 if (cmp < 0) { 1073 top->left = true; 1074 node = &(*node)->left; 1075 } else { 1076 top->left = false; 1077 node = &(*node)->right; 1078 } 1079 top++; 1080 } 1081 } 1082 if (!*node) 1083 return NOT_FOUND; 1084 // remove and free node 1085 int result = HEIGHT_CHANGED; 1086 Node *oldNode = *node; 1087 Node *replace = NULL; 1088 if ((*node)->left && (*node)->right) { 1089 // node has two children 1090 result = _RemoveRightMostChild(&(*node)->left, &replace); 1091 replace->parent = (*node)->parent; 1092 replace->left = (*node)->left; 1093 replace->right = (*node)->right; 1094 if ((*node)->left) // check necessary, if (*node)->left == replace 1095 (*node)->left->parent = replace; 1096 (*node)->right->parent = replace; 1097 replace->balance_factor = (*node)->balance_factor; 1098 *node = replace; 1099 if (result == HEIGHT_CHANGED) { 1100 replace->balance_factor++; 1101 result = _BalanceRemoveLeft(node); 1102 } 1103 } else if ((*node)->left) { 1104 // node has only left child 1105 replace = (*node)->left; 1106 replace->parent = (*node)->parent; 1107 replace->balance_factor = (*node)->balance_factor + 1; 1108 *node = replace; 1109 } else if ((*node)->right) { 1110 // node has only right child 1111 replace = (*node)->right; 1112 replace->parent = (*node)->parent; 1113 replace->balance_factor = (*node)->balance_factor - 1; 1114 *node = replace; 1115 } else { 1116 // node has no child 1117 *node = NULL; 1118 } 1119 Free(oldNode); 1120 fNodeCount--; 1121 // do the balancing 1122 while (result == HEIGHT_CHANGED && top != bottom) { 1123 top--; 1124 node = top->node; 1125 if (top->left) { 1126 // left 1127 (*node)->balance_factor++; 1128 result = _BalanceRemoveLeft(node); 1129 } else { 1130 // right 1131 (*node)->balance_factor--; 1132 result = _BalanceRemoveRight(node); 1133 } 1134 } 1135 //Check(*node); 1136 return result; 1137 } 1138 1139 // _Remove 1140 _AVL_TREE_MAP_TEMPLATE_LIST 1141 int 1142 _AVL_TREE_MAP_CLASS_NAME::_Remove(Node *node) 1143 { 1144 if (!node) 1145 return NOT_FOUND; 1146 // remove and free node 1147 Node *parent = node->parent; 1148 bool isLeft = (parent && parent->left == node); 1149 Node **nodeP 1150 = (parent ? (isLeft ? &parent->left : &parent->right) : &fRoot); 1151 int result = HEIGHT_CHANGED; 1152 Node *replace = NULL; 1153 if (node->left && node->right) { 1154 // node has two children 1155 result = _RemoveRightMostChild(&node->left, &replace); 1156 replace->parent = parent; 1157 replace->left = node->left; 1158 replace->right = node->right; 1159 if (node->left) // check necessary, if node->left == replace 1160 node->left->parent = replace; 1161 node->right->parent = replace; 1162 replace->balance_factor = node->balance_factor; 1163 *nodeP = replace; 1164 if (result == HEIGHT_CHANGED) { 1165 replace->balance_factor++; 1166 result = _BalanceRemoveLeft(nodeP); 1167 } 1168 } else if (node->left) { 1169 // node has only left child 1170 replace = node->left; 1171 replace->parent = parent; 1172 replace->balance_factor = node->balance_factor + 1; 1173 *nodeP = replace; 1174 } else if (node->right) { 1175 // node has only right child 1176 replace = node->right; 1177 replace->parent = node->parent; 1178 replace->balance_factor = node->balance_factor - 1; 1179 *nodeP = replace; 1180 } else { 1181 // node has no child 1182 *nodeP = NULL; 1183 } 1184 Free(node); 1185 fNodeCount--; 1186 // do the balancing 1187 while (result == HEIGHT_CHANGED && parent) { 1188 node = parent; 1189 parent = node->parent; 1190 bool oldIsLeft = isLeft; 1191 isLeft = (parent && parent->left == node); 1192 nodeP = (parent ? (isLeft ? &parent->left : &parent->right) : &fRoot); 1193 if (oldIsLeft) { 1194 // left 1195 node->balance_factor++; 1196 result = _BalanceRemoveLeft(nodeP); 1197 } else { 1198 // right 1199 node->balance_factor--; 1200 result = _BalanceRemoveRight(nodeP); 1201 } 1202 } 1203 //Check(node); 1204 return result; 1205 } 1206 1207 // _FreeTree 1208 _AVL_TREE_MAP_TEMPLATE_LIST 1209 void 1210 _AVL_TREE_MAP_CLASS_NAME::_FreeTree(Node *node) 1211 { 1212 if (node) { 1213 _FreeTree(node->left); 1214 _FreeTree(node->right); 1215 fAllocator.Free(node); 1216 } 1217 } 1218 1219 // _DumpNode 1220 _AVL_TREE_MAP_TEMPLATE_LIST 1221 void 1222 _AVL_TREE_MAP_CLASS_NAME::_DumpNode(Node *node) const 1223 { 1224 if (!node) 1225 return; 1226 1227 enum node_type { 1228 ROOT, 1229 LEFT, 1230 RIGHT, 1231 }; 1232 struct node_info { 1233 Node *node; 1234 int id; 1235 int parent; 1236 int level; 1237 int type; 1238 }; 1239 1240 node_info *queue = new(nothrow) node_info[fNodeCount]; 1241 if (!queue) { 1242 printf("_Dump(): Insufficient memory for allocating queue.\n"); 1243 } 1244 node_info *front = queue; 1245 node_info *back = queue; 1246 back->node = node; 1247 back->id = 0; 1248 back->level = 0; 1249 back->type = ROOT; 1250 back++; 1251 int level = 0; 1252 int nextID = 1; 1253 while (front != back) { 1254 // pop front 1255 node_info *current = front; 1256 front++; 1257 // get to the correct level 1258 node = current->node; 1259 if (level < current->level) { 1260 printf("\n"); 1261 level++; 1262 } 1263 // print node 1264 switch (current->type) { 1265 case ROOT: 1266 printf("[%d:%d]", current->id, node->balance_factor); 1267 break; 1268 case LEFT: 1269 printf("[%d:L:%d:%d]", current->id, current->parent, 1270 node->balance_factor); 1271 break; 1272 case RIGHT: 1273 printf("[%d:R:%d:%d]", current->id, current->parent, 1274 node->balance_factor); 1275 break; 1276 } 1277 // add child nodes 1278 if (node->left) { 1279 back->node = node->left; 1280 back->id = nextID++; 1281 back->parent = current->id; 1282 back->level = current->level + 1; 1283 back->type = LEFT; 1284 back++; 1285 } 1286 if (node->right) { 1287 back->node = node->right; 1288 back->id = nextID++; 1289 back->parent = current->id; 1290 back->level = current->level + 1; 1291 back->type = RIGHT; 1292 back++; 1293 } 1294 } 1295 printf("\n\n"); 1296 delete[] queue; 1297 } 1298 1299 // Allocate 1300 _AVL_TREE_MAP_TEMPLATE_LIST 1301 inline 1302 _AVL_TREE_MAP_CLASS_NAME::Node * 1303 _AVL_TREE_MAP_CLASS_NAME::Allocate(const Key &key, const Value &value) 1304 { 1305 return fStrategy.Allocate(key, value); 1306 } 1307 1308 // Free 1309 _AVL_TREE_MAP_TEMPLATE_LIST 1310 inline 1311 void 1312 _AVL_TREE_MAP_CLASS_NAME::Free(Node *node) 1313 { 1314 return fStrategy.Free(node); 1315 } 1316 1317 // GetKey 1318 _AVL_TREE_MAP_TEMPLATE_LIST 1319 inline 1320 Key & 1321 _AVL_TREE_MAP_CLASS_NAME::GetKey(Node *node) const 1322 { 1323 return fStrategy.GetKey(node); 1324 } 1325 1326 // GetValue 1327 _AVL_TREE_MAP_TEMPLATE_LIST 1328 inline 1329 Value & 1330 _AVL_TREE_MAP_CLASS_NAME::GetValue(Node *node) const 1331 { 1332 return fStrategy.GetValue(node); 1333 } 1334 1335 // Compare 1336 _AVL_TREE_MAP_TEMPLATE_LIST 1337 inline 1338 int 1339 _AVL_TREE_MAP_CLASS_NAME::Compare(const Key &a, const Key &b) 1340 { 1341 return fStrategy.Compare(a, b); 1342 } 1343 1344 1345 // strategy parameters 1346 1347 // Ascending 1348 namespace AVLTreeMapStrategy { 1349 template<typename Value> 1350 class Ascending { 1351 inline int operator()(const Value &a, const Value &b) const 1352 { 1353 if (a < b) 1354 return -1; 1355 else if (a > b) 1356 return 1; 1357 return 0; 1358 } 1359 }; 1360 } 1361 1362 // Descending 1363 namespace AVLTreeMapStrategy { 1364 template<typename Value> 1365 class Descending { 1366 inline int operator()(const Value &a, const Value &b) const 1367 { 1368 if (a < b) 1369 return -1; 1370 else if (a > b) 1371 return 1; 1372 return 0; 1373 } 1374 }; 1375 } 1376 1377 // strategies 1378 1379 // Auto 1380 namespace AVLTreeMapStrategy { 1381 template <typename Key, typename Value, typename KeyOrder, 1382 template <typename> class Allocator> 1383 class Auto { 1384 public: 1385 class Node 1386 { 1387 public: 1388 Node(const Key &key, const Value &value) 1389 : key(key), 1390 value(value), 1391 parent(NULL), 1392 left(NULL), 1393 right(NULL), 1394 balance_factor(0) 1395 { 1396 } 1397 1398 Key key; 1399 Value value; 1400 Node *parent; 1401 Node *left; 1402 Node *right; 1403 int balance_factor; 1404 }; 1405 1406 inline Node *Allocate(const Key &key, const Value &value) 1407 { 1408 Node *result = fAllocator.Allocate(); 1409 if (result) 1410 fAllocator.Construct(result, key, value); 1411 return result; 1412 } 1413 1414 inline void Free(Node *node) 1415 { 1416 fAllocator.Destruct(node); 1417 fAllocator.Deallocate(node); 1418 } 1419 1420 inline Key &GetKey(Node *node) const 1421 { 1422 return node->key; 1423 } 1424 1425 inline Value &GetValue(Node *node) const 1426 { 1427 return node->value; 1428 } 1429 1430 inline int Compare(const Key &a, const Key &b) 1431 { 1432 return fCompare(a, b); 1433 } 1434 1435 private: 1436 KeyOrder fCompare; 1437 Allocator<Node> fAllocator; 1438 }; 1439 } 1440 1441 #endif // _AVL_TREE_MAP_H 1442