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