Home | Namespaces | Hierarchy | Alphabetical List | Class list | Files | Namespace Members | Class members | File members | Tutorials

# irrMap.h

Go to the documentation of this file.

    00001 // Copyright (C) 2006-2009 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
    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         }; // RBTree
    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                 // Constructor(Node*)
    00137                 Iterator(Node* root) : Root(root)
    00138                 {
    00139                         reset();
    00140                 }
    00141
    00142                 // Copy constructor
    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()) // access violation
    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                         // Already at end?
    00213                         if (Cur==0)
    00214                                 return;
    00215
    00216                         if (Cur->getRightChild())
    00217                         {
    00218                                 // If current node has a right child, the next higher node is the
    00219                                 // node with lowest key beneath the right child.
    00220                                 Cur = getMin(Cur->getRightChild());
    00221                         }
    00222                         else if (Cur->isLeftChild())
    00223                         {
    00224                                 // No right child? Well if current node is a left child then
    00225                                 // the next higher node is the parent
    00226                                 Cur = Cur->getParent();
    00227                         }
    00228                         else
    00229                         {
    00230                                 // Current node neither is left child nor has a right child.
    00231                                 // Ie it is either right child or root
    00232                                 // The next higher node is the parent of the first non-right
    00233                                 // child (ie either a left child or the root) up in the
    00234                                 // hierarchy. Root's parent is 0.
    00235                                 while(Cur->isRightChild())
    00236                                         Cur = Cur->getParent();
    00237                                 Cur = Cur->getParent();
    00238                         }
    00239                 }
    00240
    00241                 void dec()
    00242                 {
    00243                         // Already at end?
    00244                         if (Cur==0)
    00245                                 return;
    00246
    00247                         if (Cur->getLeftChild())
    00248                         {
    00249                                 // If current node has a left child, the next lower node is the
    00250                                 // node with highest key beneath the left child.
    00251                                 Cur = getMax(Cur->getLeftChild());
    00252                         }
    00253                         else if (Cur->isRightChild())
    00254                         {
    00255                                 // No left child? Well if current node is a right child then
    00256                                 // the next lower node is the parent
    00257                                 Cur = Cur->getParent();
    00258                         }
    00259                         else
    00260                         {
    00261                                 // Current node neither is right child nor has a left child.
    00262                                 // Ie it is either left child or root
    00263                                 // The next higher node is the parent of the first non-left
    00264                                 // child (ie either a right child or the root) up in the
    00265                                 // hierarchy. Root's parent is 0.
    00266
    00267                                 while(Cur->isLeftChild())
    00268                                         Cur = Cur->getParent();
    00269                                 Cur = Cur->getParent();
    00270                         }
    00271                 }
    00272
    00273                 Node* Root;
    00274                 Node* Cur;
    00275         }; // Iterator
    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()) // access violation
    00339
    00340                 return *getNode();
    00341         }
    00342
    00343         private:
    00344
    00345         void inc()
    00346         {
    00347                 // Already at end?
    00348                 if (Cur==0)
    00349                         return;
    00350
    00351                 // First we try down to the left
    00352                 if (Cur->getLeftChild())
    00353                 {
    00354                         Cur = Cur->getLeftChild();
    00355                 }
    00356                 else if (Cur->getRightChild())
    00357                 {
    00358                         // No left child? The we go down to the right.
    00359                         Cur = Cur->getRightChild();
    00360                 }
    00361                 else
    00362                 {
    00363                         // No children? Move up in the hierarcy until
    00364                         // we either reach 0 (and are finished) or
    00365                         // find a right uncle.
    00366                         while (Cur!=0)
    00367                         {
    00368                                 // But if parent is left child and has a right "uncle" the parent
    00369                                 // has already been processed but the uncle hasn't. Move to
    00370                                 // the uncle.
    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         }; // ParentFirstIterator
    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()) // access violation
    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                         // Already at end?
    00459                         if (Cur==0)
    00460                                 return;
    00461
    00462                         // Note: Starting point is the node as far down to the left as possible.
    00463
    00464                         // If current node has an uncle to the right, go to the
    00465                         // node as far down to the left from the uncle as possible
    00466                         // else just go up a level to the parent.
    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         }; // ParentLastIterator
    00478
    00479
    00480         // AccessClass is a temporary class used with the [] operator.
    00481         // It makes it possible to have different behavior in situations like:
    00482         // myTree["Foo"] = 32;
    00483         // If "Foo" already exists update its value else insert a new element.
    00484         // int i = myTree["Foo"]
    00485         // If "Foo" exists return its value.
    00486         class AccessClass
    00487         {
    00488                 // Let map be the only one who can instantiate this class.
    00489                 friend class map<KeyType, ValueType>;
    00490
    00491         public:
    00492
    00493                 // Assignment operator. Handles the myTree["Foo"] = 32; situation
    00494                 void operator=(const ValueType& value)
    00495                 {
    00496                         // Just use the Set method, it handles already exist/not exist situation
    00497                         Tree.set(Key,value);
    00498                 }
    00499
    00500                 // ValueType operator
    00501                 operator ValueType()
    00502                 {
    00503                         Node* node = Tree.find(Key);
    00504
    00505                         // Not found
    00506                         _IRR_DEBUG_BREAK_IF(node==0) // access violation
    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         }; // AccessClass
    00521
    00522
    00523         // Constructor.
    00524         map() : Root(0), Size(0) {}
    00525
    00526         // Destructor
    00527         ~map()
    00528         {
    00529                 clear();
    00530         }
    00531
    00532         //------------------------------
    00533         // Public Commands
    00534         //------------------------------
    00535
    00537
    00540         bool insert(const KeyType& keyNew, const ValueType& v)
    00541         {
    00542                 // First insert node the "usual" way (no fancy balance logic yet)
    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                 // Then attend a balancing party
    00552                 while (!newNode->isRoot() && (newNode->getParent()->isRed()))
    00553                 {
    00554                         if (newNode->getParent()->isLeftChild())
    00555                         {
    00556                                 // If newNode is a left child, get its right 'uncle'
    00557                                 Node* newNodesUncle = newNode->getParent()->getParent()->getRightChild();
    00558                                 if ( newNodesUncle!=0 && newNodesUncle->isRed())
    00559                                 {
    00560                                         // case 1 - change the colours
    00561                                         newNode->getParent()->setBlack();
    00562                                         newNodesUncle->setBlack();
    00563                                         newNode->getParent()->getParent()->setRed();
    00564                                         // Move newNode up the tree
    00565                                         newNode = newNode->getParent()->getParent();
    00566                                 }
    00567                                 else
    00568                                 {
    00569                                         // newNodesUncle is a black node
    00570                                         if ( newNode->isRightChild())
    00571                                         {
    00572                                                 // and newNode is to the right
    00573                                                 // case 2 - move newNode up and rotate
    00574                                                 newNode = newNode->getParent();
    00575                                                 rotateLeft(newNode);
    00576                                         }
    00577                                         // case 3
    00578                                         newNode->getParent()->setBlack();
    00579                                         newNode->getParent()->getParent()->setRed();
    00580                                         rotateRight(newNode->getParent()->getParent());
    00581                                 }
    00582                         }
    00583                         else
    00584                         {
    00585                                 // If newNode is a right child, get its left 'uncle'
    00586                                 Node* newNodesUncle = newNode->getParent()->getParent()->getLeftChild();
    00587                                 if ( newNodesUncle!=0 && newNodesUncle->isRed())
    00588                                 {
    00589                                         // case 1 - change the colours
    00590                                         newNode->getParent()->setBlack();
    00591                                         newNodesUncle->setBlack();
    00592                                         newNode->getParent()->getParent()->setRed();
    00593                                         // Move newNode up the tree
    00594                                         newNode = newNode->getParent()->getParent();
    00595                                 }
    00596                                 else
    00597                                 {
    00598                                         // newNodesUncle is a black node
    00599                                         if (newNode->isLeftChild())
    00600                                         {
    00601                                                 // and newNode is to the left
    00602                                                 // case 2 - move newNode up and rotate
    00603                                                 newNode = newNode->getParent();
    00604                                                 rotateRight(newNode);
    00605                                         }
    00606                                         // case 3
    00607                                         newNode->getParent()->setBlack();
    00608                                         newNode->getParent()->getParent()->setRed();
    00609                                         rotateLeft(newNode->getParent()->getParent());
    00610                                 }
    00611
    00612                         }
    00613                 }
    00614                 // Color the root black
    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                 // Rotate p down to the left until it has no right child, will get there
    00642                 // sooner or later.
    00643                 while(p->getRightChild())
    00644                 {
    00645                         // "Pull up my right child and let it knock me down to the left"
    00646                         rotateLeft(p);
    00647                 }
    00648                 // p now has no right child but might have a left child
    00649                 Node* left = p->getLeftChild();
    00650
    00651                 // Let p's parent point to p's child instead of point to p
    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                         // p has no parent => p is the root.
    00661                         // Let the left child be the new root.
    00662                         setRoot(left);
    00663                 }
    00664
    00665                 // p is now gone from the tree in the sense that
    00666                 // no one is pointing at it, so return it.
    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                 // Rotate p down to the left until it has no right child, will get there
    00684                 // sooner or later.
    00685                 while(p->getRightChild())
    00686                 {
    00687                         // "Pull up my right child and let it knock me down to the left"
    00688                         rotateLeft(p);
    00689                 }
    00690                 // p now has no right child but might have a left child
    00691                 Node* left = p->getLeftChild();
    00692
    00693                 // Let p's parent point to p's child instead of point to p
    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                         // p has no parent => p is the root.
    00703                         // Let the left child be the new root.
    00704                         setRoot(left);
    00705                 }
    00706
    00707                 // p is now gone from the tree in the sense that
    00708                 // no one is pointing at it. Let's get rid of it.
    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++; // Increment it before it is deleted
    00724                                 // else iterator will get quite confused.
    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 //keyToFind > key
    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         // Public Iterators
    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         // Public Operators
    00808         //------------------------------
    00809
    00811
    00812         AccessClass operator[](const KeyType& k)
    00813         {
    00814                 return AccessClass(*this, k);
    00815         }
    00816         private:
    00817
    00818         //------------------------------
    00819         // Disabled methods
    00820         //------------------------------
    00821         // Copy constructor and assignment operator deliberately
    00822         // defined but not implemented. The tree should never be
    00823         // copied, pass along references to it instead.
    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; // Assume success
    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 // keyNew > key
    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         // Private Members
    00936         //------------------------------
    00937         Node* Root; // The top node. 0 if empty.
    00938         u32 Size; // Number of nodes in the tree
    00939 };
    00940
    00941 } // end namespace core
    00942 } // end namespace irr
    00943
    00944 #endif // __IRR_MAP_H_INCLUDED__
    00945

| The Irrlicht Engine Documentation © 2003-2009 by Nikolaus Gebhardt. Generated on Sun Jan 10 09:24:04 2010 by Doxygen (1.5.6)