 |
+
+
+
+ Irrlicht 3D Engine
+
+
+
+ |
+
+
+
+
+
+
+
+
+
+
+ 
+
+ |
+
+
+
00001 // Copyright (C) 2006-2012 by Kat'Oun +00002 // This file is part of the "Irrlicht Engine". +00003 // For conditions of distribution and use, see copyright notice in irrlicht.h +00004 +00005 #ifndef __IRR_MAP_H_INCLUDED__ +00006 #define __IRR_MAP_H_INCLUDED__ +00007 +00008 #include "irrTypes.h" +00009 #include "irrMath.h" +00010 +00011 namespace irr +00012 { +00013 namespace core +00014 { +00015 +00017 template <class KeyType, class ValueType> +00018 class map +00019 { +00021 template <class KeyTypeRB, class ValueTypeRB> +00022 class RBTree +00023 { +00024 public: +00025 +00026 RBTree(const KeyTypeRB& k, const ValueTypeRB& v) +00027 : LeftChild(0), RightChild(0), Parent(0), Key(k), +00028 Value(v), IsRed(true) {} +00029 +00030 void setLeftChild(RBTree* p) +00031 { +00032 LeftChild=p; +00033 if (p) +00034 p->setParent(this); +00035 } +00036 +00037 void setRightChild(RBTree* p) +00038 { +00039 RightChild=p; +00040 if (p) +00041 p->setParent(this); +00042 } +00043 +00044 void setParent(RBTree* p) { Parent=p; } +00045 +00046 void setValue(const ValueTypeRB& v) { Value = v; } +00047 +00048 void setRed() { IsRed = true; } +00049 void setBlack() { IsRed = false; } +00050 +00051 RBTree* getLeftChild() const { return LeftChild; } +00052 RBTree* getRightChild() const { return RightChild; } +00053 RBTree* getParent() const { return Parent; } +00054 +00055 const ValueTypeRB& getValue() const +00056 { +00057 _IRR_IMPLEMENT_MANAGED_MARSHALLING_BUGFIX; +00058 return Value; +00059 } +00060 +00061 ValueTypeRB& getValue() +00062 { +00063 _IRR_IMPLEMENT_MANAGED_MARSHALLING_BUGFIX; +00064 return Value; +00065 } +00066 +00067 const KeyTypeRB& getKey() const +00068 { +00069 _IRR_IMPLEMENT_MANAGED_MARSHALLING_BUGFIX; +00070 return Key; +00071 } +00072 +00073 bool isRoot() const +00074 { +00075 _IRR_IMPLEMENT_MANAGED_MARSHALLING_BUGFIX; +00076 return Parent==0; +00077 } +00078 +00079 bool isLeftChild() const +00080 { +00081 _IRR_IMPLEMENT_MANAGED_MARSHALLING_BUGFIX; +00082 return (Parent != 0) && (Parent->getLeftChild()==this); +00083 } +00084 +00085 bool isRightChild() const +00086 { +00087 _IRR_IMPLEMENT_MANAGED_MARSHALLING_BUGFIX; +00088 return (Parent!=0) && (Parent->getRightChild()==this); +00089 } +00090 +00091 bool isLeaf() const +00092 { +00093 _IRR_IMPLEMENT_MANAGED_MARSHALLING_BUGFIX; +00094 return (LeftChild==0) && (RightChild==0); +00095 } +00096 +00097 unsigned int getLevel() const +00098 { +00099 if (isRoot()) +00100 return 1; +00101 else +00102 return getParent()->getLevel() + 1; +00103 } +00104 +00105 +00106 bool isRed() const +00107 { +00108 _IRR_IMPLEMENT_MANAGED_MARSHALLING_BUGFIX; +00109 return IsRed; +00110 } +00111 +00112 bool isBlack() const +00113 { +00114 _IRR_IMPLEMENT_MANAGED_MARSHALLING_BUGFIX; +00115 return !IsRed; +00116 } +00117 +00118 private: +00119 RBTree(); +00120 +00121 RBTree* LeftChild; +00122 RBTree* RightChild; +00123 +00124 RBTree* Parent; +00125 +00126 KeyTypeRB Key; +00127 ValueTypeRB Value; +00128 +00129 bool IsRed; +00130 }; // RBTree +00131 +00132 public: +00133 +00134 typedef RBTree<KeyType,ValueType> Node; +00135 // We need the forwad declaration for the friend declaration +00136 class ConstIterator; +00137 +00139 class Iterator +00140 { +00141 friend class ConstIterator; +00142 public: +00143 +00144 Iterator() : Root(0), Cur(0) {} +00145 +00146 // Constructor(Node*) +00147 Iterator(Node* root) : Root(root) +00148 { +00149 reset(); +00150 } +00151 +00152 // Copy constructor +00153 Iterator(const Iterator& src) : Root(src.Root), Cur(src.Cur) {} +00154 +00155 void reset(bool atLowest=true) +00156 { +00157 if (atLowest) +00158 Cur = getMin(Root); +00159 else +00160 Cur = getMax(Root); +00161 } +00162 +00163 bool atEnd() const +00164 { +00165 _IRR_IMPLEMENT_MANAGED_MARSHALLING_BUGFIX; +00166 return Cur==0; +00167 } +00168 +00169 Node* getNode() const +00170 { +00171 return Cur; +00172 } +00173 +00174 Iterator& operator=(const Iterator& src) +00175 { +00176 Root = src.Root; +00177 Cur = src.Cur; +00178 return (*this); +00179 } +00180 +00181 void operator++(int) +00182 { +00183 inc(); +00184 } +00185 +00186 void operator--(int) +00187 { +00188 dec(); +00189 } +00190 +00191 Node* operator->() +00192 { +00193 return getNode(); +00194 } +00195 +00196 Node& operator*() +00197 { +00198 _IRR_DEBUG_BREAK_IF(atEnd()) // access violation +00199 +00200 return *Cur; +00201 } +00202 +00203 private: +00204 +00205 Node* getMin(Node* n) const +00206 { +00207 while(n && n->getLeftChild()) +00208 n = n->getLeftChild(); +00209 return n; +00210 } +00211 +00212 Node* getMax(Node* n) const +00213 { +00214 while(n && n->getRightChild()) +00215 n = n->getRightChild(); +00216 return n; +00217 } +00218 +00219 void inc() +00220 { +00221 // Already at end? +00222 if (Cur==0) +00223 return; +00224 +00225 if (Cur->getRightChild()) +00226 { +00227 // If current node has a right child, the next higher node is the +00228 // node with lowest key beneath the right child. +00229 Cur = getMin(Cur->getRightChild()); +00230 } +00231 else if (Cur->isLeftChild()) +00232 { +00233 // No right child? Well if current node is a left child then +00234 // the next higher node is the parent +00235 Cur = Cur->getParent(); +00236 } +00237 else +00238 { +00239 // Current node neither is left child nor has a right child. +00240 // Ie it is either right child or root +00241 // The next higher node is the parent of the first non-right +00242 // child (ie either a left child or the root) up in the +00243 // hierarchy. Root's parent is 0. +00244 while(Cur->isRightChild()) +00245 Cur = Cur->getParent(); +00246 Cur = Cur->getParent(); +00247 } +00248 } +00249 +00250 void dec() +00251 { +00252 // Already at end? +00253 if (Cur==0) +00254 return; +00255 +00256 if (Cur->getLeftChild()) +00257 { +00258 // If current node has a left child, the next lower node is the +00259 // node with highest key beneath the left child. +00260 Cur = getMax(Cur->getLeftChild()); +00261 } +00262 else if (Cur->isRightChild()) +00263 { +00264 // No left child? Well if current node is a right child then +00265 // the next lower node is the parent +00266 Cur = Cur->getParent(); +00267 } +00268 else +00269 { +00270 // Current node neither is right child nor has a left child. +00271 // Ie it is either left child or root +00272 // The next higher node is the parent of the first non-left +00273 // child (ie either a right child or the root) up in the +00274 // hierarchy. Root's parent is 0. +00275 +00276 while(Cur->isLeftChild()) +00277 Cur = Cur->getParent(); +00278 Cur = Cur->getParent(); +00279 } +00280 } +00281 +00282 Node* Root; +00283 Node* Cur; +00284 }; // Iterator +00285 +00287 class ConstIterator +00288 { +00289 friend class Iterator; +00290 public: +00291 +00292 ConstIterator() : Root(0), Cur(0) {} +00293 +00294 // Constructor(Node*) +00295 ConstIterator(const Node* root) : Root(root) +00296 { +00297 reset(); +00298 } +00299 +00300 // Copy constructor +00301 ConstIterator(const ConstIterator& src) : Root(src.Root), Cur(src.Cur) {} +00302 ConstIterator(const Iterator& src) : Root(src.Root), Cur(src.Cur) {} +00303 +00304 void reset(bool atLowest=true) +00305 { +00306 if (atLowest) +00307 Cur = getMin(Root); +00308 else +00309 Cur = getMax(Root); +00310 } +00311 +00312 bool atEnd() const +00313 { +00314 _IRR_IMPLEMENT_MANAGED_MARSHALLING_BUGFIX; +00315 return Cur==0; +00316 } +00317 +00318 const Node* getNode() const +00319 { +00320 return Cur; +00321 } +00322 +00323 ConstIterator& operator=(const ConstIterator& src) +00324 { +00325 Root = src.Root; +00326 Cur = src.Cur; +00327 return (*this); +00328 } +00329 +00330 void operator++(int) +00331 { +00332 inc(); +00333 } +00334 +00335 void operator--(int) +00336 { +00337 dec(); +00338 } +00339 +00340 const Node* operator->() +00341 { +00342 return getNode(); +00343 } +00344 +00345 const Node& operator*() +00346 { +00347 _IRR_DEBUG_BREAK_IF(atEnd()) // access violation +00348 +00349 return *Cur; +00350 } +00351 +00352 private: +00353 +00354 const Node* getMin(const Node* n) const +00355 { +00356 while(n && n->getLeftChild()) +00357 n = n->getLeftChild(); +00358 return n; +00359 } +00360 +00361 const Node* getMax(const Node* n) const +00362 { +00363 while(n && n->getRightChild()) +00364 n = n->getRightChild(); +00365 return n; +00366 } +00367 +00368 void inc() +00369 { +00370 // Already at end? +00371 if (Cur==0) +00372 return; +00373 +00374 if (Cur->getRightChild()) +00375 { +00376 // If current node has a right child, the next higher node is the +00377 // node with lowest key beneath the right child. +00378 Cur = getMin(Cur->getRightChild()); +00379 } +00380 else if (Cur->isLeftChild()) +00381 { +00382 // No right child? Well if current node is a left child then +00383 // the next higher node is the parent +00384 Cur = Cur->getParent(); +00385 } +00386 else +00387 { +00388 // Current node neither is left child nor has a right child. +00389 // Ie it is either right child or root +00390 // The next higher node is the parent of the first non-right +00391 // child (ie either a left child or the root) up in the +00392 // hierarchy. Root's parent is 0. +00393 while(Cur->isRightChild()) +00394 Cur = Cur->getParent(); +00395 Cur = Cur->getParent(); +00396 } +00397 } +00398 +00399 void dec() +00400 { +00401 // Already at end? +00402 if (Cur==0) +00403 return; +00404 +00405 if (Cur->getLeftChild()) +00406 { +00407 // If current node has a left child, the next lower node is the +00408 // node with highest key beneath the left child. +00409 Cur = getMax(Cur->getLeftChild()); +00410 } +00411 else if (Cur->isRightChild()) +00412 { +00413 // No left child? Well if current node is a right child then +00414 // the next lower node is the parent +00415 Cur = Cur->getParent(); +00416 } +00417 else +00418 { +00419 // Current node neither is right child nor has a left child. +00420 // Ie it is either left child or root +00421 // The next higher node is the parent of the first non-left +00422 // child (ie either a right child or the root) up in the +00423 // hierarchy. Root's parent is 0. +00424 +00425 while(Cur->isLeftChild()) +00426 Cur = Cur->getParent(); +00427 Cur = Cur->getParent(); +00428 } +00429 } +00430 +00431 const Node* Root; +00432 const Node* Cur; +00433 }; // ConstIterator +00434 +00435 +00437 +00441 class ParentFirstIterator +00442 { +00443 public: +00444 +00445 ParentFirstIterator() : Root(0), Cur(0) {} +00446 +00447 explicit ParentFirstIterator(Node* root) : Root(root), Cur(0) +00448 { +00449 reset(); +00450 } +00451 +00452 void reset() +00453 { +00454 Cur = Root; +00455 } +00456 +00457 bool atEnd() const +00458 { +00459 _IRR_IMPLEMENT_MANAGED_MARSHALLING_BUGFIX; +00460 return Cur==0; +00461 } +00462 +00463 Node* getNode() +00464 { +00465 return Cur; +00466 } +00467 +00468 ParentFirstIterator& operator=(const ParentFirstIterator& src) +00469 { +00470 Root = src.Root; +00471 Cur = src.Cur; +00472 return (*this); +00473 } +00474 +00475 void operator++(int) +00476 { +00477 inc(); +00478 } +00479 +00480 Node* operator -> () +00481 { +00482 return getNode(); +00483 } +00484 +00485 Node& operator* () +00486 { +00487 _IRR_DEBUG_BREAK_IF(atEnd()) // access violation +00488 +00489 return *getNode(); +00490 } +00491 +00492 private: +00493 +00494 void inc() +00495 { +00496 // Already at end? +00497 if (Cur==0) +00498 return; +00499 +00500 // First we try down to the left +00501 if (Cur->getLeftChild()) +00502 { +00503 Cur = Cur->getLeftChild(); +00504 } +00505 else if (Cur->getRightChild()) +00506 { +00507 // No left child? The we go down to the right. +00508 Cur = Cur->getRightChild(); +00509 } +00510 else +00511 { +00512 // No children? Move up in the hierarcy until +00513 // we either reach 0 (and are finished) or +00514 // find a right uncle. +00515 while (Cur!=0) +00516 { +00517 // But if parent is left child and has a right "uncle" the parent +00518 // has already been processed but the uncle hasn't. Move to +00519 // the uncle. +00520 if (Cur->isLeftChild() && Cur->getParent()->getRightChild()) +00521 { +00522 Cur = Cur->getParent()->getRightChild(); +00523 return; +00524 } +00525 Cur = Cur->getParent(); +00526 } +00527 } +00528 } +00529 +00530 Node* Root; +00531 Node* Cur; +00532 +00533 }; // ParentFirstIterator +00534 +00535 +00537 +00541 class ParentLastIterator +00542 { +00543 public: +00544 +00545 ParentLastIterator() : Root(0), Cur(0) {} +00546 +00547 explicit ParentLastIterator(Node* root) : Root(root), Cur(0) +00548 { +00549 reset(); +00550 } +00551 +00552 void reset() +00553 { +00554 Cur = getMin(Root); +00555 } +00556 +00557 bool atEnd() const +00558 { +00559 _IRR_IMPLEMENT_MANAGED_MARSHALLING_BUGFIX; +00560 return Cur==0; +00561 } +00562 +00563 Node* getNode() +00564 { +00565 return Cur; +00566 } +00567 +00568 ParentLastIterator& operator=(const ParentLastIterator& src) +00569 { +00570 Root = src.Root; +00571 Cur = src.Cur; +00572 return (*this); +00573 } +00574 +00575 void operator++(int) +00576 { +00577 inc(); +00578 } +00579 +00580 Node* operator -> () +00581 { +00582 return getNode(); +00583 } +00584 +00585 Node& operator* () +00586 { +00587 _IRR_DEBUG_BREAK_IF(atEnd()) // access violation +00588 +00589 return *getNode(); +00590 } +00591 private: +00592 +00593 Node* getMin(Node* n) +00594 { +00595 while(n!=0 && (n->getLeftChild()!=0 || n->getRightChild()!=0)) +00596 { +00597 if (n->getLeftChild()) +00598 n = n->getLeftChild(); +00599 else +00600 n = n->getRightChild(); +00601 } +00602 return n; +00603 } +00604 +00605 void inc() +00606 { +00607 // Already at end? +00608 if (Cur==0) +00609 return; +00610 +00611 // Note: Starting point is the node as far down to the left as possible. +00612 +00613 // If current node has an uncle to the right, go to the +00614 // node as far down to the left from the uncle as possible +00615 // else just go up a level to the parent. +00616 if (Cur->isLeftChild() && Cur->getParent()->getRightChild()) +00617 { +00618 Cur = getMin(Cur->getParent()->getRightChild()); +00619 } +00620 else +00621 Cur = Cur->getParent(); +00622 } +00623 +00624 Node* Root; +00625 Node* Cur; +00626 }; // ParentLastIterator +00627 +00628 +00629 // AccessClass is a temporary class used with the [] operator. +00630 // It makes it possible to have different behavior in situations like: +00631 // myTree["Foo"] = 32; +00632 // If "Foo" already exists update its value else insert a new element. +00633 // int i = myTree["Foo"] +00634 // If "Foo" exists return its value. +00635 class AccessClass +00636 { +00637 // Let map be the only one who can instantiate this class. +00638 friend class map<KeyType, ValueType>; +00639 +00640 public: +00641 +00642 // Assignment operator. Handles the myTree["Foo"] = 32; situation +00643 void operator=(const ValueType& value) +00644 { +00645 // Just use the Set method, it handles already exist/not exist situation +00646 Tree.set(Key,value); +00647 } +00648 +00649 // ValueType operator +00650 operator ValueType() +00651 { +00652 Node* node = Tree.find(Key); +00653 +00654 // Not found +00655 _IRR_DEBUG_BREAK_IF(node==0) // access violation +00656 +00657 _IRR_IMPLEMENT_MANAGED_MARSHALLING_BUGFIX; +00658 return node->getValue(); +00659 } +00660 +00661 private: +00662 +00663 AccessClass(map& tree, const KeyType& key) : Tree(tree), Key(key) {} +00664 +00665 AccessClass(); +00666 +00667 map& Tree; +00668 const KeyType& Key; +00669 }; // AccessClass +00670 +00671 +00672 // Constructor. +00673 map() : Root(0), Size(0) {} +00674 +00675 // Destructor +00676 ~map() +00677 { +00678 clear(); +00679 } +00680 +00681 //------------------------------ +00682 // Public Commands +00683 //------------------------------ +00684 +00686 +00689 bool insert(const KeyType& keyNew, const ValueType& v) +00690 { +00691 // First insert node the "usual" way (no fancy balance logic yet) +00692 Node* newNode = new Node(keyNew,v); +00693 if (!insert(newNode)) +00694 { +00695 delete newNode; +00696 _IRR_IMPLEMENT_MANAGED_MARSHALLING_BUGFIX; +00697 return false; +00698 } +00699 +00700 // Then attend a balancing party +00701 while (!newNode->isRoot() && (newNode->getParent()->isRed())) +00702 { +00703 if (newNode->getParent()->isLeftChild()) +00704 { +00705 // If newNode is a left child, get its right 'uncle' +00706 Node* newNodesUncle = newNode->getParent()->getParent()->getRightChild(); +00707 if ( newNodesUncle!=0 && newNodesUncle->isRed()) +00708 { +00709 // case 1 - change the colors +00710 newNode->getParent()->setBlack(); +00711 newNodesUncle->setBlack(); +00712 newNode->getParent()->getParent()->setRed(); +00713 // Move newNode up the tree +00714 newNode = newNode->getParent()->getParent(); +00715 } +00716 else +00717 { +00718 // newNodesUncle is a black node +00719 if ( newNode->isRightChild()) +00720 { +00721 // and newNode is to the right +00722 // case 2 - move newNode up and rotate +00723 newNode = newNode->getParent(); +00724 rotateLeft(newNode); +00725 } +00726 // case 3 +00727 newNode->getParent()->setBlack(); +00728 newNode->getParent()->getParent()->setRed(); +00729 rotateRight(newNode->getParent()->getParent()); +00730 } +00731 } +00732 else +00733 { +00734 // If newNode is a right child, get its left 'uncle' +00735 Node* newNodesUncle = newNode->getParent()->getParent()->getLeftChild(); +00736 if ( newNodesUncle!=0 && newNodesUncle->isRed()) +00737 { +00738 // case 1 - change the colors +00739 newNode->getParent()->setBlack(); +00740 newNodesUncle->setBlack(); +00741 newNode->getParent()->getParent()->setRed(); +00742 // Move newNode up the tree +00743 newNode = newNode->getParent()->getParent(); +00744 } +00745 else +00746 { +00747 // newNodesUncle is a black node +00748 if (newNode->isLeftChild()) +00749 { +00750 // and newNode is to the left +00751 // case 2 - move newNode up and rotate +00752 newNode = newNode->getParent(); +00753 rotateRight(newNode); +00754 } +00755 // case 3 +00756 newNode->getParent()->setBlack(); +00757 newNode->getParent()->getParent()->setRed(); +00758 rotateLeft(newNode->getParent()->getParent()); +00759 } +00760 +00761 } +00762 } +00763 // Color the root black +00764 Root->setBlack(); +00765 return true; +00766 } +00767 +00769 +00771 void set(const KeyType& k, const ValueType& v) +00772 { +00773 Node* p = find(k); +00774 if (p) +00775 p->setValue(v); +00776 else +00777 insert(k,v); +00778 } +00779 +00781 +00784 Node* delink(const KeyType& k) +00785 { +00786 Node* p = find(k); +00787 if (p == 0) +00788 return 0; +00789 +00790 // Rotate p down to the left until it has no right child, will get there +00791 // sooner or later. +00792 while(p->getRightChild()) +00793 { +00794 // "Pull up my right child and let it knock me down to the left" +00795 rotateLeft(p); +00796 } +00797 // p now has no right child but might have a left child +00798 Node* left = p->getLeftChild(); +00799 +00800 // Let p's parent point to p's child instead of point to p +00801 if (p->isLeftChild()) +00802 p->getParent()->setLeftChild(left); +00803 +00804 else if (p->isRightChild()) +00805 p->getParent()->setRightChild(left); +00806 +00807 else +00808 { +00809 // p has no parent => p is the root. +00810 // Let the left child be the new root. +00811 setRoot(left); +00812 } +00813 +00814 // p is now gone from the tree in the sense that +00815 // no one is pointing at it, so return it. +00816 +00817 --Size; +00818 return p; +00819 } +00820 +00822 +00823 bool remove(const KeyType& k) +00824 { +00825 Node* p = find(k); +00826 return remove(p); +00827 } +00828 +00830 +00831 bool remove(Node* p) +00832 { +00833 if (p == 0) +00834 { +00835 _IRR_IMPLEMENT_MANAGED_MARSHALLING_BUGFIX; +00836 return false; +00837 } +00838 +00839 // Rotate p down to the left until it has no right child, will get there +00840 // sooner or later. +00841 while(p->getRightChild()) +00842 { +00843 // "Pull up my right child and let it knock me down to the left" +00844 rotateLeft(p); +00845 } +00846 // p now has no right child but might have a left child +00847 Node* left = p->getLeftChild(); +00848 +00849 // Let p's parent point to p's child instead of point to p +00850 if (p->isLeftChild()) +00851 p->getParent()->setLeftChild(left); +00852 +00853 else if (p->isRightChild()) +00854 p->getParent()->setRightChild(left); +00855 +00856 else +00857 { +00858 // p has no parent => p is the root. +00859 // Let the left child be the new root. +00860 setRoot(left); +00861 } +00862 +00863 // p is now gone from the tree in the sense that +00864 // no one is pointing at it. Let's get rid of it. +00865 delete p; +00866 +00867 --Size; +00868 return true; +00869 } +00870 +00872 void clear() +00873 { +00874 ParentLastIterator i(getParentLastIterator()); +00875 +00876 while(!i.atEnd()) +00877 { +00878 Node* p = i.getNode(); +00879 i++; // Increment it before it is deleted +00880 // else iterator will get quite confused. +00881 delete p; +00882 } +00883 Root = 0; +00884 Size= 0; +00885 } +00886 +00889 bool empty() const +00890 { +00891 _IRR_IMPLEMENT_MANAGED_MARSHALLING_BUGFIX; +00892 return Root == 0; +00893 } +00894 +00896 _IRR_DEPRECATED_ bool isEmpty() const +00897 { +00898 return empty(); +00899 } +00900 +00904 Node* find(const KeyType& keyToFind) const +00905 { +00906 Node* pNode = Root; +00907 +00908 while(pNode!=0) +00909 { +00910 const KeyType& key=pNode->getKey(); +00911 +00912 if (keyToFind == key) +00913 return pNode; +00914 else if (keyToFind < key) +00915 pNode = pNode->getLeftChild(); +00916 else //keyToFind > key +00917 pNode = pNode->getRightChild(); +00918 } +00919 +00920 return 0; +00921 } +00922 +00926 Node* getRoot() const +00927 { +00928 return Root; +00929 } +00930 +00932 u32 size() const +00933 { +00934 return Size; +00935 } +00936 +00938 +00942 void swap(map<KeyType, ValueType>& other) +00943 { +00944 core::swap(Root, other.Root); +00945 core::swap(Size, other.Size); +00946 } +00947 +00948 //------------------------------ +00949 // Public Iterators +00950 //------------------------------ +00951 +00953 Iterator getIterator() const +00954 { +00955 Iterator it(getRoot()); +00956 return it; +00957 } +00958 +00960 ConstIterator getConstIterator() const +00961 { +00962 Iterator it(getRoot()); +00963 return it; +00964 } +00965 +00971 ParentFirstIterator getParentFirstIterator() const +00972 { +00973 ParentFirstIterator it(getRoot()); +00974 return it; +00975 } +00976 +00982 ParentLastIterator getParentLastIterator() const +00983 { +00984 ParentLastIterator it(getRoot()); +00985 return it; +00986 } +00987 +00988 //------------------------------ +00989 // Public Operators +00990 //------------------------------ +00991 +00993 +00994 AccessClass operator[](const KeyType& k) +00995 { +00996 return AccessClass(*this, k); +00997 } +00998 private: +00999 +01000 //------------------------------ +01001 // Disabled methods +01002 //------------------------------ +01003 // Copy constructor and assignment operator deliberately +01004 // defined but not implemented. The tree should never be +01005 // copied, pass along references to it instead. +01006 explicit map(const map& src); +01007 map& operator = (const map& src); +01008 +01010 +01014 void setRoot(Node* newRoot) +01015 { +01016 Root = newRoot; +01017 if (Root != 0) +01018 { +01019 Root->setParent(0); +01020 Root->setBlack(); +01021 } +01022 } +01023 +01025 +01026 bool insert(Node* newNode) +01027 { +01028 bool result=true; // Assume success +01029 +01030 if (Root==0) +01031 { +01032 setRoot(newNode); +01033 Size = 1; +01034 } +01035 else +01036 { +01037 Node* pNode = Root; +01038 const KeyType& keyNew = newNode->getKey(); +01039 while (pNode) +01040 { +01041 const KeyType& key=pNode->getKey(); +01042 +01043 if (keyNew == key) +01044 { +01045 result = false; +01046 pNode = 0; +01047 } +01048 else if (keyNew < key) +01049 { +01050 if (pNode->getLeftChild() == 0) +01051 { +01052 pNode->setLeftChild(newNode); +01053 pNode = 0; +01054 } +01055 else +01056 pNode = pNode->getLeftChild(); +01057 } +01058 else // keyNew > key +01059 { +01060 if (pNode->getRightChild()==0) +01061 { +01062 pNode->setRightChild(newNode); +01063 pNode = 0; +01064 } +01065 else +01066 { +01067 pNode = pNode->getRightChild(); +01068 } +01069 } +01070 } +01071 +01072 if (result) +01073 ++Size; +01074 } +01075 +01076 _IRR_IMPLEMENT_MANAGED_MARSHALLING_BUGFIX; +01077 return result; +01078 } +01079 +01082 void rotateLeft(Node* p) +01083 { +01084 Node* right = p->getRightChild(); +01085 +01086 p->setRightChild(right->getLeftChild()); +01087 +01088 if (p->isLeftChild()) +01089 p->getParent()->setLeftChild(right); +01090 else if (p->isRightChild()) +01091 p->getParent()->setRightChild(right); +01092 else +01093 setRoot(right); +01094 +01095 right->setLeftChild(p); +01096 } +01097 +01100 void rotateRight(Node* p) +01101 { +01102 Node* left = p->getLeftChild(); +01103 +01104 p->setLeftChild(left->getRightChild()); +01105 +01106 if (p->isLeftChild()) +01107 p->getParent()->setLeftChild(left); +01108 else if (p->isRightChild()) +01109 p->getParent()->setRightChild(left); +01110 else +01111 setRoot(left); +01112 +01113 left->setRightChild(p); +01114 } +01115 +01116 //------------------------------ +01117 // Private Members +01118 //------------------------------ +01119 Node* Root; // The top node. 0 if empty. +01120 u32 Size; // Number of nodes in the tree +01121 }; +01122 +01123 } // end namespace core +01124 } // end namespace irr +01125 +01126 #endif // __IRR_MAP_H_INCLUDED__ +01127 +