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

The Irrlicht Engine
The Irrlicht Engine Documentation © 2003-2010 by Nikolaus Gebhardt. Generated on Sun Oct 24 12:41:57 2010 by Doxygen (1.6.2)