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