00001
00002
00003
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 ValueTypeRB getValue() const
00056 {
00057 _IRR_IMPLEMENT_MANAGED_MARSHALLING_BUGFIX;
00058 return Value;
00059 }
00060
00061 KeyTypeRB getKey() const
00062 {
00063 _IRR_IMPLEMENT_MANAGED_MARSHALLING_BUGFIX;
00064 return Key;
00065 }
00066
00067 bool isRoot() const
00068 {
00069 _IRR_IMPLEMENT_MANAGED_MARSHALLING_BUGFIX;
00070 return Parent==0;
00071 }
00072
00073 bool isLeftChild() const
00074 {
00075 _IRR_IMPLEMENT_MANAGED_MARSHALLING_BUGFIX;
00076 return (Parent != 0) && (Parent->getLeftChild()==this);
00077 }
00078
00079 bool isRightChild() const
00080 {
00081 _IRR_IMPLEMENT_MANAGED_MARSHALLING_BUGFIX;
00082 return (Parent!=0) && (Parent->getRightChild()==this);
00083 }
00084
00085 bool isLeaf() const
00086 {
00087 _IRR_IMPLEMENT_MANAGED_MARSHALLING_BUGFIX;
00088 return (LeftChild==0) && (RightChild==0);
00089 }
00090
00091 unsigned int getLevel() const
00092 {
00093 if (isRoot())
00094 return 1;
00095 else
00096 return getParent()->getLevel() + 1;
00097 }
00098
00099
00100 bool isRed() const
00101 {
00102 _IRR_IMPLEMENT_MANAGED_MARSHALLING_BUGFIX;
00103 return IsRed;
00104 }
00105
00106 bool isBlack() const
00107 {
00108 _IRR_IMPLEMENT_MANAGED_MARSHALLING_BUGFIX;
00109 return !IsRed;
00110 }
00111
00112 private:
00113 RBTree();
00114
00115 RBTree* LeftChild;
00116 RBTree* RightChild;
00117
00118 RBTree* Parent;
00119
00120 KeyTypeRB Key;
00121 ValueTypeRB Value;
00122
00123 bool IsRed;
00124 };
00125
00126 public:
00127
00128 typedef RBTree<KeyType,ValueType> Node;
00129
00131 class Iterator
00132 {
00133 public:
00134
00135 Iterator() : Root(0), Cur(0) {}
00136
00137
00138 Iterator(Node* root) : Root(root)
00139 {
00140 reset();
00141 }
00142
00143
00144 Iterator(const Iterator& src) : Root(src.Root), Cur(src.Cur) {}
00145
00146 void reset(bool atLowest=true)
00147 {
00148 if (atLowest)
00149 Cur = getMin(Root);
00150 else
00151 Cur = getMax(Root);
00152 }
00153
00154 bool atEnd() const
00155 {
00156 _IRR_IMPLEMENT_MANAGED_MARSHALLING_BUGFIX;
00157 return Cur==0;
00158 }
00159
00160 Node* getNode()
00161 {
00162 return Cur;
00163 }
00164
00165 Iterator& operator=(const Iterator& src)
00166 {
00167 Root = src.Root;
00168 Cur = src.Cur;
00169 return (*this);
00170 }
00171
00172 void operator++(int)
00173 {
00174 inc();
00175 }
00176
00177 void operator--(int)
00178 {
00179 dec();
00180 }
00181
00182
00183 Node* operator -> ()
00184 {
00185 return getNode();
00186 }
00187
00188 Node& operator* ()
00189 {
00190 _IRR_DEBUG_BREAK_IF(atEnd())
00191
00192 return *Cur;
00193 }
00194
00195 private:
00196
00197 Node* getMin(Node* n)
00198 {
00199 while(n && n->getLeftChild())
00200 n = n->getLeftChild();
00201 return n;
00202 }
00203
00204 Node* getMax(Node* n)
00205 {
00206 while(n && n->getRightChild())
00207 n = n->getRightChild();
00208 return n;
00209 }
00210
00211 void inc()
00212 {
00213
00214 if (Cur==0)
00215 return;
00216
00217 if (Cur->getRightChild())
00218 {
00219
00220
00221 Cur = getMin(Cur->getRightChild());
00222 }
00223 else if (Cur->isLeftChild())
00224 {
00225
00226
00227 Cur = Cur->getParent();
00228 }
00229 else
00230 {
00231
00232
00233
00234
00235
00236 while(Cur->isRightChild())
00237 Cur = Cur->getParent();
00238 Cur = Cur->getParent();
00239 }
00240 }
00241
00242 void dec()
00243 {
00244
00245 if (Cur==0)
00246 return;
00247
00248 if (Cur->getLeftChild())
00249 {
00250
00251
00252 Cur = getMax(Cur->getLeftChild());
00253 }
00254 else if (Cur->isRightChild())
00255 {
00256
00257
00258 Cur = Cur->getParent();
00259 }
00260 else
00261 {
00262
00263
00264
00265
00266
00267
00268 while(Cur->isLeftChild())
00269 Cur = Cur->getParent();
00270 Cur = Cur->getParent();
00271 }
00272 }
00273
00274 Node* Root;
00275 Node* Cur;
00276 };
00277
00278
00279
00281
00285 class ParentFirstIterator
00286 {
00287 public:
00288
00289
00290 ParentFirstIterator() : Root(0), Cur(0)
00291 {
00292 }
00293
00294
00295 explicit ParentFirstIterator(Node* root) : Root(root), Cur(0)
00296 {
00297 reset();
00298 }
00299
00300 void reset()
00301 {
00302 Cur = Root;
00303 }
00304
00305
00306 bool atEnd() const
00307 {
00308 _IRR_IMPLEMENT_MANAGED_MARSHALLING_BUGFIX;
00309 return Cur==0;
00310 }
00311
00312 Node* getNode()
00313 {
00314 return Cur;
00315 }
00316
00317
00318 ParentFirstIterator& operator=(const ParentFirstIterator& src)
00319 {
00320 Root = src.Root;
00321 Cur = src.Cur;
00322 return (*this);
00323 }
00324
00325
00326 void operator++(int)
00327 {
00328 inc();
00329 }
00330
00331
00332 Node* operator -> ()
00333 {
00334 return getNode();
00335 }
00336
00337 Node& operator* ()
00338 {
00339 _IRR_DEBUG_BREAK_IF(atEnd())
00340
00341 return *getNode();
00342 }
00343
00344 private:
00345
00346 void inc()
00347 {
00348
00349 if (Cur==0)
00350 return;
00351
00352
00353 if (Cur->getLeftChild())
00354 {
00355 Cur = Cur->getLeftChild();
00356 }
00357 else if (Cur->getRightChild())
00358 {
00359
00360 Cur = Cur->getRightChild();
00361 }
00362 else
00363 {
00364
00365
00366
00367 while (Cur!=0)
00368 {
00369
00370
00371
00372 if (Cur->isLeftChild() && Cur->getParent()->getRightChild())
00373 {
00374 Cur = Cur->getParent()->getRightChild();
00375 return;
00376 }
00377 Cur = Cur->getParent();
00378 }
00379 }
00380 }
00381
00382 Node* Root;
00383 Node* Cur;
00384
00385 };
00386
00387
00389
00393 class ParentLastIterator
00394 {
00395 public:
00396
00397 ParentLastIterator() : Root(0), Cur(0) {}
00398
00399 explicit ParentLastIterator(Node* root) : Root(root), Cur(0)
00400 {
00401 reset();
00402 }
00403
00404 void reset()
00405 {
00406 Cur = getMin(Root);
00407 }
00408
00409 bool atEnd() const
00410 {
00411 _IRR_IMPLEMENT_MANAGED_MARSHALLING_BUGFIX;
00412 return Cur==0;
00413 }
00414
00415 Node* getNode()
00416 {
00417 return Cur;
00418 }
00419
00420 ParentLastIterator& operator=(const ParentLastIterator& src)
00421 {
00422 Root = src.Root;
00423 Cur = src.Cur;
00424 return (*this);
00425 }
00426
00427 void operator++(int)
00428 {
00429 inc();
00430 }
00431
00432 Node* operator -> ()
00433 {
00434 return getNode();
00435 }
00436
00437 Node& operator* ()
00438 {
00439 _IRR_DEBUG_BREAK_IF(atEnd())
00440
00441 return *getNode();
00442 }
00443 private:
00444
00445 Node* getMin(Node* n)
00446 {
00447 while(n!=0 && (n->getLeftChild()!=0 || n->getRightChild()!=0))
00448 {
00449 if (n->getLeftChild())
00450 n = n->getLeftChild();
00451 else
00452 n = n->getRightChild();
00453 }
00454 return n;
00455 }
00456
00457 void inc()
00458 {
00459
00460 if (Cur==0)
00461 return;
00462
00463
00464
00465
00466
00467
00468 if (Cur->isLeftChild() && Cur->getParent()->getRightChild())
00469 {
00470 Cur = getMin(Cur->getParent()->getRightChild());
00471 }
00472 else
00473 Cur = Cur->getParent();
00474 }
00475
00476 Node* Root;
00477 Node* Cur;
00478 };
00479
00480
00481
00482
00483
00484
00485
00486
00487 class AccessClass
00488 {
00489
00490 friend class map<KeyType, ValueType>;
00491
00492 public:
00493
00494
00495 void operator=(const ValueType& value)
00496 {
00497
00498 Tree.set(Key,value);
00499 }
00500
00501
00502 operator ValueType()
00503 {
00504 Node* node = Tree.find(Key);
00505
00506
00507 _IRR_DEBUG_BREAK_IF(node==0)
00508
00509 _IRR_IMPLEMENT_MANAGED_MARSHALLING_BUGFIX;
00510 return node->getValue();
00511 }
00512
00513 private:
00514
00515 AccessClass(map& tree, const KeyType& key) : Tree(tree), Key(key) {}
00516
00517 AccessClass();
00518
00519 map& Tree;
00520 const KeyType& Key;
00521 };
00522
00523
00524
00525 map() : Root(0), Size(0) {}
00526
00527
00528 ~map()
00529 {
00530 clear();
00531 }
00532
00533
00534
00535
00536
00538
00541 bool insert(const KeyType& keyNew, const ValueType& v)
00542 {
00543
00544 Node* newNode = new Node(keyNew,v);
00545 if (!insert(newNode))
00546 {
00547 delete newNode;
00548 _IRR_IMPLEMENT_MANAGED_MARSHALLING_BUGFIX;
00549 return false;
00550 }
00551
00552
00553 while (!newNode->isRoot() && (newNode->getParent()->isRed()))
00554 {
00555 if (newNode->getParent()->isLeftChild())
00556 {
00557
00558 Node* newNodesUncle = newNode->getParent()->getParent()->getRightChild();
00559 if ( newNodesUncle!=0 && newNodesUncle->isRed())
00560 {
00561
00562 newNode->getParent()->setBlack();
00563 newNodesUncle->setBlack();
00564 newNode->getParent()->getParent()->setRed();
00565
00566 newNode = newNode->getParent()->getParent();
00567 }
00568 else
00569 {
00570
00571 if ( newNode->isRightChild())
00572 {
00573
00574
00575 newNode = newNode->getParent();
00576 rotateLeft(newNode);
00577 }
00578
00579 newNode->getParent()->setBlack();
00580 newNode->getParent()->getParent()->setRed();
00581 rotateRight(newNode->getParent()->getParent());
00582 }
00583 }
00584 else
00585 {
00586
00587 Node* newNodesUncle = newNode->getParent()->getParent()->getLeftChild();
00588 if ( newNodesUncle!=0 && newNodesUncle->isRed())
00589 {
00590
00591 newNode->getParent()->setBlack();
00592 newNodesUncle->setBlack();
00593 newNode->getParent()->getParent()->setRed();
00594
00595 newNode = newNode->getParent()->getParent();
00596 }
00597 else
00598 {
00599
00600 if (newNode->isLeftChild())
00601 {
00602
00603
00604 newNode = newNode->getParent();
00605 rotateRight(newNode);
00606 }
00607
00608 newNode->getParent()->setBlack();
00609 newNode->getParent()->getParent()->setRed();
00610 rotateLeft(newNode->getParent()->getParent());
00611 }
00612
00613 }
00614 }
00615
00616 Root->setBlack();
00617 return true;
00618 }
00619
00621
00623 void set(const KeyType& k, const ValueType& v)
00624 {
00625 Node* p = find(k);
00626 if (p)
00627 p->setValue(v);
00628 else
00629 insert(k,v);
00630 }
00631
00633
00636 Node* delink(const KeyType& k)
00637 {
00638 Node* p = find(k);
00639 if (p == 0)
00640 return 0;
00641
00642
00643
00644 while(p->getRightChild())
00645 {
00646
00647 rotateLeft(p);
00648 }
00649
00650 Node* left = p->getLeftChild();
00651
00652
00653 if (p->isLeftChild())
00654 p->getParent()->setLeftChild(left);
00655
00656 else if (p->isRightChild())
00657 p->getParent()->setRightChild(left);
00658
00659 else
00660 {
00661
00662
00663 setRoot(left);
00664 }
00665
00666
00667
00668
00669 --Size;
00670 return p;
00671 }
00672
00674
00675 bool remove(const KeyType& k)
00676 {
00677 Node* p = find(k);
00678 if (p == 0)
00679 {
00680 _IRR_IMPLEMENT_MANAGED_MARSHALLING_BUGFIX;
00681 return false;
00682 }
00683
00684
00685
00686 while(p->getRightChild())
00687 {
00688
00689 rotateLeft(p);
00690 }
00691
00692 Node* left = p->getLeftChild();
00693
00694
00695 if (p->isLeftChild())
00696 p->getParent()->setLeftChild(left);
00697
00698 else if (p->isRightChild())
00699 p->getParent()->setRightChild(left);
00700
00701 else
00702 {
00703
00704
00705 setRoot(left);
00706 }
00707
00708
00709
00710 delete p;
00711
00712 --Size;
00713 return true;
00714 }
00715
00717 void clear()
00718 {
00719 ParentLastIterator i(getParentLastIterator());
00720
00721 while(!i.atEnd())
00722 {
00723 Node* p = i.getNode();
00724 i++;
00725
00726 delete p;
00727 }
00728 Root = 0;
00729 Size= 0;
00730 }
00731
00734 bool empty() const
00735 {
00736 _IRR_IMPLEMENT_MANAGED_MARSHALLING_BUGFIX;
00737 return Root == 0;
00738 }
00739
00741 _IRR_DEPRECATED_ bool isEmpty() const
00742 {
00743 return empty();
00744 }
00745
00749 Node* find(const KeyType& keyToFind) const
00750 {
00751 Node* pNode = Root;
00752
00753 while(pNode!=0)
00754 {
00755 KeyType key(pNode->getKey());
00756
00757 if (keyToFind == key)
00758 return pNode;
00759 else if (keyToFind < key)
00760 pNode = pNode->getLeftChild();
00761 else
00762 pNode = pNode->getRightChild();
00763 }
00764
00765 return 0;
00766 }
00767
00771 Node* getRoot() const
00772 {
00773 return Root;
00774 }
00775
00777 u32 size() const
00778 {
00779 return Size;
00780 }
00781
00783
00787 void swap(map<KeyType, ValueType>& other)
00788 {
00789 core::swap(Root, other.Root);
00790 core::swap(Size, other.Size);
00791 }
00792
00793
00794
00795
00796
00798 Iterator getIterator()
00799 {
00800 Iterator it(getRoot());
00801 return it;
00802 }
00808 ParentFirstIterator getParentFirstIterator()
00809 {
00810 ParentFirstIterator it(getRoot());
00811 return it;
00812 }
00818 ParentLastIterator getParentLastIterator()
00819 {
00820 ParentLastIterator it(getRoot());
00821 return it;
00822 }
00823
00824
00825
00826
00827
00829
00830 AccessClass operator[](const KeyType& k)
00831 {
00832 return AccessClass(*this, k);
00833 }
00834 private:
00835
00836
00837
00838
00839
00840
00841
00842 explicit map(const map& src);
00843 map& operator = (const map& src);
00844
00846
00850 void setRoot(Node* newRoot)
00851 {
00852 Root = newRoot;
00853 if (Root != 0)
00854 {
00855 Root->setParent(0);
00856 Root->setBlack();
00857 }
00858 }
00859
00861
00862 bool insert(Node* newNode)
00863 {
00864 bool result=true;
00865
00866 if (Root==0)
00867 {
00868 setRoot(newNode);
00869 Size = 1;
00870 }
00871 else
00872 {
00873 Node* pNode = Root;
00874 KeyType keyNew = newNode->getKey();
00875 while (pNode)
00876 {
00877 KeyType key(pNode->getKey());
00878
00879 if (keyNew == key)
00880 {
00881 result = false;
00882 pNode = 0;
00883 }
00884 else if (keyNew < key)
00885 {
00886 if (pNode->getLeftChild() == 0)
00887 {
00888 pNode->setLeftChild(newNode);
00889 pNode = 0;
00890 }
00891 else
00892 pNode = pNode->getLeftChild();
00893 }
00894 else
00895 {
00896 if (pNode->getRightChild()==0)
00897 {
00898 pNode->setRightChild(newNode);
00899 pNode = 0;
00900 }
00901 else
00902 {
00903 pNode = pNode->getRightChild();
00904 }
00905 }
00906 }
00907
00908 if (result)
00909 ++Size;
00910 }
00911
00912 _IRR_IMPLEMENT_MANAGED_MARSHALLING_BUGFIX;
00913 return result;
00914 }
00915
00918 void rotateLeft(Node* p)
00919 {
00920 Node* right = p->getRightChild();
00921
00922 p->setRightChild(right->getLeftChild());
00923
00924 if (p->isLeftChild())
00925 p->getParent()->setLeftChild(right);
00926 else if (p->isRightChild())
00927 p->getParent()->setRightChild(right);
00928 else
00929 setRoot(right);
00930
00931 right->setLeftChild(p);
00932 }
00933
00936 void rotateRight(Node* p)
00937 {
00938 Node* left = p->getLeftChild();
00939
00940 p->setLeftChild(left->getRightChild());
00941
00942 if (p->isLeftChild())
00943 p->getParent()->setLeftChild(left);
00944 else if (p->isRightChild())
00945 p->getParent()->setRightChild(left);
00946 else
00947 setRoot(left);
00948
00949 left->setRightChild(p);
00950 }
00951
00952
00953
00954
00955 Node* Root;
00956 u32 Size;
00957 };
00958
00959 }
00960 }
00961
00962 #endif // __IRR_MAP_H_INCLUDED__
00963