doc/html/irr_map_8h_source.html

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
-