- Main Page
- Classes
- Files
- Directories

- File List
- File Members

# fbxredblacktree.h

Go to the documentation of this file.

    00001 /****************************************************************************************
    00002
    00003    Copyright (C) 2013 Autodesk, Inc.
    00004    All rights reserved.
    00005
    00006    Use of this software is subject to the terms of the Autodesk license agreement
    00007    provided at the time of installation or download, or which otherwise accompanies
    00008    this software in either electronic or hard copy form.
    00009
    00010 ****************************************************************************************/
    00011
    00013 #ifndef _FBXSDK_CORE_BASE_REDBLACKTREE_H_
    00014 #define _FBXSDK_CORE_BASE_REDBLACKTREE_H_
    00015
    00016 #include <fbxsdk/fbxsdk_def.h>
    00017
    00018 #include <fbxsdk/core/base/fbxcontainerallocators.h>
    00019 #include <fbxsdk/core/base/fbxpair.h>
    00020
    00021 #include <fbxsdk/fbxsdk_nsbegin.h>
    00022
    00023 /*****************************************************************************************************************************
    00024 ** WARNING! Anything beyond these lines is for internal use, may not be documented and is subject to change without notice! **
    00025 *****************************************************************************************************************************/
    00026 #ifndef DOXYGEN_SHOULD_SKIP_THIS
    00027
    00028 template <typename RecordType> class FbxRedBlackConstIterator;
    00029
    00030 template <typename RecordType> class FbxRedBlackIterator
    00031 {
    00032 public:
    00033     FbxRedBlackIterator() : mRecord(0) {}
    00034     FbxRedBlackIterator(RecordType* pRecord) : mRecord(pRecord) {}
    00035     FbxRedBlackIterator(const FbxRedBlackIterator<RecordType>& pV) : mRecord(pV.mRecord) {}
    00036
    00037     FbxRedBlackIterator & operator++()
    00038     {
    00039         FBX_ASSERT( mRecord != NULL );
    00040         mRecord = mRecord->Successor();
    00041         return *this;
    00042     }
    00043
    00044     const FbxRedBlackIterator operator++(int)
    00045     {
    00046         FbxRedBlackIterator t(*this);
    00047         operator++();
    00048         return t;
    00049     }
    00050
    00051     FbxRedBlackIterator & operator--()
    00052     {
    00053         FBX_ASSERT( mRecord );
    00054         mRecord = mRecord->Predecessor();
    00055         return *this;
    00056     }
    00057
    00058     const FbxRedBlackIterator operator--(int)
    00059     {
    00060         FbxRedBlackIterator t(*this);
    00061         operator--();
    00062         return t;
    00063     }
    00064
    00065     const RecordType& operator*() const
    00066     {
    00067         FBX_ASSERT( mRecord );
    00068
    00069         return *mRecord;
    00070     }
    00071
    00072     RecordType& operator*()
    00073     {
    00074         FBX_ASSERT( mRecord );
    00075
    00076         return *mRecord;
    00077     }
    00078
    00079     const RecordType* operator->() const
    00080     {
    00081         FBX_ASSERT( mRecord );
    00082
    00083         return mRecord;
    00084     }
    00085
    00086     RecordType* operator->()
    00087     {
    00088         FBX_ASSERT( mRecord );
    00089
    00090         return mRecord;
    00091     }
    00092
    00093     inline bool operator==(const FbxRedBlackIterator& pOther) const
    00094     {
    00095         return mRecord == pOther.mRecord;
    00096     }
    00097
    00098     inline bool operator !=(const FbxRedBlackIterator& pOther) const
    00099     {
    00100         return mRecord != pOther.mRecord;
    00101     }
    00102
    00103 protected:
    00104     RecordType* mRecord;
    00105
    00106     friend class FbxRedBlackConstIterator<RecordType>;
    00107 };
    00108
    00109 template <typename RecordType> class FbxRedBlackConstIterator
    00110 {
    00111 public:
    00112     FbxRedBlackConstIterator() : mRecord(0) {}
    00113     FbxRedBlackConstIterator(const RecordType* pRecord) : mRecord(pRecord) {}
    00114     FbxRedBlackConstIterator(const FbxRedBlackIterator<RecordType>& pV) : mRecord(pV.mRecord) {}
    00115     FbxRedBlackConstIterator(const FbxRedBlackConstIterator<RecordType>& pV) : mRecord(pV.mRecord) {}
    00116
    00117     FbxRedBlackConstIterator & operator++()
    00118     {
    00119         FBX_ASSERT( mRecord != NULL );
    00120         mRecord = mRecord->Successor();
    00121         return *this;
    00122     }
    00123
    00124     const FbxRedBlackConstIterator operator++(int)
    00125     {
    00126         FbxRedBlackConstIterator t(*this);
    00127         operator++();
    00128         return t;
    00129     }
    00130
    00131     FbxRedBlackConstIterator & operator--()
    00132     {
    00133         FBX_ASSERT( mRecord );
    00134         mRecord = mRecord->Predecessor();
    00135         return *this;
    00136     }
    00137
    00138     const FbxRedBlackConstIterator operator--(int)
    00139     {
    00140         FbxRedBlackConstIterator t(*this);
    00141         operator--();
    00142         return t;
    00143     }
    00144
    00145     const RecordType& operator*() const
    00146     {
    00147         FBX_ASSERT( mRecord );
    00148
    00149         return *mRecord;
    00150     }
    00151
    00152     const RecordType& operator*()
    00153     {
    00154         FBX_ASSERT( mRecord );
    00155
    00156         return *mRecord;
    00157     }
    00158
    00159     const RecordType* operator->() const
    00160     {
    00161         FBX_ASSERT( mRecord );
    00162
    00163         return mRecord;
    00164     }
    00165
    00166     const RecordType* operator->()
    00167     {
    00168         FBX_ASSERT( mRecord );
    00169
    00170         return mRecord;
    00171     }
    00172
    00173     inline bool operator==(const FbxRedBlackConstIterator& pOther) const
    00174     {
    00175         return mRecord == pOther.mRecord;
    00176     }
    00177
    00178     inline bool operator !=(const FbxRedBlackConstIterator& pOther) const
    00179     {
    00180         return mRecord != pOther.mRecord;
    00181     }
    00182
    00183 protected:
    00184     const RecordType* mRecord;
    00185
    00186     friend class FbxRedBlackIterator<RecordType>;
    00187 };
    00188
    00190 template <typename Type, typename Compare, typename Allocator> class FbxRedBlackTree
    00191 {
    00192 public:
    00193     typedef Type DataType;
    00194     typedef typename Type::KeyType         KeyType;
    00195     typedef typename Type::ConstKeyType    ConstKeyType;
    00196     typedef typename Type::ValueType       ValueType;
    00197     typedef typename Type::ConstValueType  ConstValueType;
    00198     typedef Allocator AllocatorType;
    00199
    00204     class RecordType
    00205     {
    00206     public:
    00207         inline ConstKeyType& GetKey() const { return mData.GetKey(); }
    00208         inline ConstValueType& GetValue() const { return mData.GetValue(); }
    00209         inline ValueType& GetValue() { return mData.GetValue(); }
    00210
    00211         inline const RecordType* Minimum() const
    00212         {
    00213             const RecordType* lParent = 0;
    00214             const RecordType* lNode = this;
    00215             while (lNode != 0)
    00216             {
    00217                 lParent = lNode;
    00218                 lNode = lNode->mLeftChild;
    00219             }
    00220
    00221             return lParent;
    00222         }
    00223
    00224         inline RecordType* Minimum()
    00225         {
    00226             RecordType* lParent = 0;
    00227             RecordType* lNode = this;
    00228             while (lNode != 0)
    00229             {
    00230                 lParent = lNode;
    00231                 lNode = lNode->mLeftChild;
    00232             }
    00233
    00234             return lParent;
    00235         }
    00236
    00237         inline const RecordType* Maximum() const
    00238         {
    00239             const RecordType* lParent = 0;
    00240             const RecordType* lNode = this;
    00241             while (lNode != 0)
    00242             {
    00243                 lParent = lNode;
    00244                 lNode = lNode->mRightChild;
    00245             }
    00246
    00247             return lParent;
    00248         }
    00249
    00250         inline RecordType* Maximum()
    00251         {
    00252             RecordType* lParent = 0;
    00253             RecordType* lNode = this;
    00254             while (lNode != 0)
    00255             {
    00256                 lParent = lNode;
    00257                 lNode = lNode->mRightChild;
    00258             }
    00259
    00260             return lParent;
    00261         }
    00262
    00263         inline const RecordType* Predecessor() const
    00264         {
    00265             if (mLeftChild)
    00266             {
    00267                 return mLeftChild->Maximum();
    00268             }
    00269             else
    00270             {
    00271                 const RecordType* lParent = mParent;
    00272                 const RecordType* lNode = this;
    00273
    00274                 while (lParent && lParent->mLefttChild == lNode)
    00275                 {
    00276                     lNode = lParent;
    00277                     lParent = lParent->mParent;
    00278                 }
    00279
    00280                 return lParent;
    00281             }
    00282         }
    00283
    00284         inline RecordType* Predecessor()
    00285         {
    00286             if (mLeftChild)
    00287             {
    00288                 return mLeftChild->Maximum();
    00289             }
    00290             else
    00291             {
    00292                 RecordType* lParent = mParent;
    00293                 RecordType* lNode = this;
    00294
    00295                 while (lParent && lParent->mLeftChild == lNode)
    00296                 {
    00297                     lNode = lParent;
    00298                     lParent = lParent->mParent;
    00299                 }
    00300
    00301                 return lParent;
    00302             }
    00303         }
    00304
    00305         inline const RecordType* Successor() const
    00306         {
    00307             if (mRightChild)
    00308             {
    00309                 return mRightChild->Minimum();
    00310             }
    00311             else
    00312             {
    00313                 const RecordType* lParent = mParent;
    00314                 const RecordType* lNode = this;
    00315
    00316                 while (lParent && lParent->mRightChild == lNode)
    00317                 {
    00318                     lNode = lParent;
    00319                     lParent = lParent->mParent;
    00320                 }
    00321
    00322                 return lParent;
    00323             }
    00324         }
    00325
    00326         inline RecordType* Successor()
    00327         {
    00328             if (mRightChild)
    00329             {
    00330                 return mRightChild->Minimum();
    00331             }
    00332             else
    00333             {
    00334                 RecordType* lParent = mParent;
    00335                 RecordType* lNode = this;
    00336
    00337                 while (lParent && lParent->mRightChild == lNode)
    00338                 {
    00339                     lNode = lParent;
    00340                     lParent = lParent->mParent;
    00341                 }
    00342
    00343                 return lParent;
    00344             }
    00345         }
    00346
    00347         inline const int GetBlackDepth() { return mBlackDepth; }
    00348
    00349     private:
    00350         enum ETreeType {eRed, eBlack};
    00351
    00352         inline RecordType(const DataType& pData)
    00353             : mData(pData)
    00354             , mParent(0)
    00355             , mLeftChild(0)
    00356             , mRightChild(0)
    00357             , mColor(eRed)
    00358             , mBlackDepth(0)
    00359         {
    00360         }
    00361
    00362         inline RecordType(const RecordType& pRecordType)
    00363             : mData(pRecordType.mData)
    00364             , mParent(0)
    00365             , mLeftChild(0)
    00366             , mRightChild(0)
    00367             , mColor(pRecordType.mColor)
    00368             , mBlackDepth(pRecordType.mBlackDepth)
    00369         {
    00370         }
    00371
    00372         DataType mData;
    00373
    00374         friend class FbxRedBlackTree;
    00375
    00376         RecordType* mParent;
    00377         RecordType* mLeftChild;
    00378         RecordType* mRightChild;
    00379         unsigned int mColor:2;
    00380         unsigned int mBlackDepth:30;
    00381     };
    00382
    00383 public:
    00384     typedef FbxRedBlackConstIterator<RecordType>  ConstIteratorType;
    00385     typedef FbxRedBlackIterator<RecordType>       IteratorType;
    00386
    00387     inline FbxRedBlackTree() : mRoot(0), mSize(0), mAllocator(sizeof(RecordType)) {}
    00388     inline FbxRedBlackTree(const FbxRedBlackTree& pTree) : mRoot(0), mSize(0), mAllocator(sizeof(RecordType)) { operator=(pTree); }
    00389     inline ~FbxRedBlackTree() { Clear(); }
    00390
    00393     inline FbxRedBlackTree& operator=(const FbxRedBlackTree& pTree)
    00394     {
    00395         if( this != &pTree )
    00396         {
    00397             Clear();
    00398
    00399             mAllocator = pTree.mAllocator;
    00400
    00401             if( pTree.mRoot )
    00402             {
    00403                 void* lBuffer = mAllocator.AllocateRecords();
    00404                 mRoot = new(lBuffer) RecordType(*(pTree.mRoot));    //in-place new won't allocate memory, so it is safe
    00405                 mRoot->mLeftChild = DuplicateSubTree(pTree.mRoot->mLeftChild);
    00406                 mRoot->mRightChild = DuplicateSubTree(pTree.mRoot->mRightChild);
    00407
    00408                 if (mRoot->mLeftChild)
    00409                 {
    00410                     mRoot->mLeftChild->mParent = mRoot;
    00411                 }
    00412
    00413                 if (mRoot->mRightChild)
    00414                 {
    00415                     mRoot->mRightChild->mParent = mRoot;
    00416                 }
    00417             }
    00418             else
    00419             {
    00420                 FBX_ASSERT( pTree.mSize == 0 );
    00421                 FBX_ASSERT( mRoot == 0 );
    00422             }
    00423
    00424             mSize = pTree.mSize;
    00425         }
    00426
    00427         return *this;
    00428     }
    00429
    00430     inline bool operator==(const FbxRedBlackTree& pTree) const
    00431     {
    00432         // Check a few quick shortcuts
    00433         if( this == &pTree )
    00434             return true;
    00435
    00436         if( GetSize() != pTree.GetSize() )
    00437             return false;
    00438
    00439         // Iterator through all nodes; if we reach the end of both iterators at the same
    00440         // time then we have two iterators that match.
    00441         ConstIteratorType End;
    00442         ConstIteratorType Iter1(Minimum());
    00443         ConstIteratorType Iter2(pTree.Minimum());
    00444
    00445         while( (Iter1 != End) && (Iter2 != End) &&
    00446                (Iter1->GetKey() == Iter2->GetKey()) &&
    00447                (Iter1->GetValue() == Iter2->GetValue()) )
    00448         {
    00449             ++Iter1;
    00450             ++Iter2;
    00451         }
    00452
    00453         return Iter1 == End && Iter2 == End;
    00454     }
    00455
    00459     inline void Reserve(unsigned int pRecordCount)
    00460     {
    00461         mAllocator.Reserve(pRecordCount);
    00462     }
    00463
    00467     inline int GetSize() const { return mSize; }
    00468
    00469     inline bool Empty() const { return mSize == 0; }
    00470
    00476     inline FbxPair<RecordType*, bool> Insert(const DataType& pData)
    00477     {
    00478         Compare lCompareKeys;
    00479         bool lResult = false;
    00480         RecordType* lParent = 0;
    00481         RecordType* lNode = mRoot;
    00482         while (lNode != 0)
    00483         {
    00484             const KeyType& lNodeKey = lNode->GetKey();
    00485             const KeyType& lDataKey = pData.GetKey();
    00486
    00487             if (lCompareKeys(lNodeKey, lDataKey) < 0)
    00488             {
    00489                 lParent = lNode;
    00490                 lNode = lNode->mRightChild;
    00491             }
    00492             else if (lCompareKeys(lNodeKey, lDataKey) > 0)
    00493             {
    00494                 lParent = lNode;
    00495                 lNode = lNode->mLeftChild;
    00496             }
    00497             else
    00498             {
    00499                 break;
    00500             }
    00501         }
    00502
    00503         if (lNode == 0)
    00504         {
    00505             void* lBuffer = mAllocator.AllocateRecords();
    00506             lNode = new(lBuffer) RecordType(pData); //in-place new won't allocate memory, so it is safe
    00507             mSize++;
    00508
    00509             FBX_ASSERT(lNode == lBuffer);
    00510
    00511             if (lParent)
    00512             {
    00513                 if (lCompareKeys(lParent->GetKey(), pData.GetKey()) < 0)
    00514                 {
    00515                     FBX_ASSERT(lParent->mRightChild == 0);
    00516                     lParent->mRightChild = lNode;
    00517                     lNode->mParent = lParent;
    00518                 }
    00519                 else
    00520                 {
    00521                     FBX_ASSERT(lParent->mLeftChild == 0);
    00522                     lParent->mLeftChild = lNode;
    00523                     lNode->mParent = lParent;
    00524                 }
    00525             }
    00526             else
    00527             {
    00528                 mRoot = lNode;
    00529             }
    00530
    00531             // Fix red black tree property
    00532             FixNodesAfterInsertion(lNode);
    00533
    00534             lResult = true;
    00535         }
    00536
    00537         return FbxPair<RecordType*, bool>(lNode, lResult);
    00538     }
    00539
    00543     inline bool Remove(const KeyType& pKey)
    00544     {
    00545         Compare lCompareKeys;
    00546         bool lResult = false;
    00547         RecordType* lNode = mRoot;
    00548         while (lNode != 0)
    00549         {
    00550             if (lCompareKeys(lNode->GetKey(), pKey) < 0)
    00551             {
    00552                 lNode = lNode->mRightChild;
    00553             }
    00554             else if (lCompareKeys(lNode->GetKey(), pKey) > 0)
    00555             {
    00556                 lNode = lNode->mLeftChild;
    00557             }
    00558             else
    00559             {
    00560                 break;
    00561             }
    00562         }
    00563
    00564         if (lNode)
    00565         {
    00566             RemoveNode(lNode);
    00567             mSize--;
    00568             lNode->~RecordType();
    00569             mAllocator.FreeMemory(lNode);
    00570
    00571             lResult = true;
    00572         }
    00573
    00574         return lResult;
    00575     }
    00576
    00579     inline void Clear()
    00580     {
    00581         if (mRoot)
    00582         {
    00583             ClearSubTree(mRoot->mLeftChild);
    00584             ClearSubTree(mRoot->mRightChild);
    00585             mRoot->~RecordType();
    00586             mAllocator.FreeMemory(mRoot);
    00587             mRoot = 0;
    00588             mSize = 0;
    00589         }
    00590     }
    00591
    00595     inline const RecordType* Minimum() const
    00596     {
    00597         if (0 != mRoot)
    00598         {
    00599             return mRoot->Minimum();
    00600         }
    00601         else
    00602         {
    00603             return 0;
    00604         }
    00605     }
    00606
    00610     inline RecordType* Minimum()
    00611     {
    00612         if (0 != mRoot)
    00613         {
    00614             return mRoot->Minimum();
    00615         }
    00616         else
    00617         {
    00618             return 0;
    00619         }
    00620     }
    00621
    00625     inline const RecordType* Maximum() const
    00626     {
    00627         if (0 != mRoot)
    00628         {
    00629             return mRoot->Maximum();
    00630         }
    00631         else
    00632         {
    00633             return 0;
    00634         }
    00635     }
    00636
    00640     inline RecordType* Maximum()
    00641     {
    00642         if (0 != mRoot)
    00643         {
    00644             return mRoot->Maximum();
    00645         }
    00646         else
    00647         {
    00648             return 0;
    00649         }
    00650     }
    00651
    00656     inline const RecordType* Find(const KeyType& pKey) const
    00657     {
    00658         Compare lCompareKeys;
    00659         const RecordType* lNode = mRoot;
    00660         while (lNode != 0)
    00661         {
    00662             if (lCompareKeys(lNode->GetKey(), pKey) < 0)
    00663             {
    00664                 lNode = lNode->mRightChild;
    00665             }
    00666             else if (lCompareKeys(lNode->GetKey(), pKey) > 0)
    00667             {
    00668                 lNode = lNode->mLeftChild;
    00669             }
    00670             else
    00671             {
    00672                 break;
    00673             }
    00674         }
    00675
    00676         return lNode;
    00677     }
    00678
    00683     inline RecordType* Find(const KeyType& pKey)
    00684     {
    00685         Compare lCompareKeys;
    00686         RecordType* lNode = mRoot;
    00687         while (lNode != 0)
    00688         {
    00689             if (lCompareKeys(lNode->GetKey(), pKey) < 0)
    00690             {
    00691                 lNode = lNode->mRightChild;
    00692             }
    00693             else if (lCompareKeys(lNode->GetKey(), pKey) > 0)
    00694             {
    00695                 lNode = lNode->mLeftChild;
    00696             }
    00697             else
    00698             {
    00699                 break;
    00700             }
    00701         }
    00702
    00703         return lNode;
    00704     }
    00705
    00710     inline const RecordType* UpperBound(const KeyType& pKey) const
    00711     {
    00712         Compare lCompareKeys;
    00713         const RecordType* lNode = mRoot;
    00714         const RecordType* lCandidate = 0;
    00715         while (lNode != 0)
    00716         {
    00717             if (lCompareKeys(lNode->GetKey(), pKey) <= 0)
    00718             {
    00719                 lNode = lNode->mRightChild;
    00720             }
    00721             else if (lCompareKeys(lNode->GetKey(), pKey) > 0)
    00722             {
    00723                 lCandidate = lNode;
    00724                 lNode = lNode->mLeftChild;
    00725             }
    00726         }
    00727
    00728         return lCandidate;
    00729     }
    00730
    00735     inline RecordType* UpperBound(const KeyType& pKey)
    00736     {
    00737         Compare lCompareKeys;
    00738         RecordType* lNode = mRoot;
    00739         RecordType* lCandidate = 0;
    00740         while (lNode != 0)
    00741         {
    00742             if (lCompareKeys(lNode->GetKey(), pKey) <= 0)
    00743             {
    00744                 lNode = lNode->mRightChild;
    00745             }
    00746             else if (lCompareKeys(lNode->GetKey(), pKey) > 0)
    00747             {
    00748                 lCandidate = lNode;
    00749                 lNode = lNode->mLeftChild;
    00750             }
    00751         }
    00752
    00753         return lCandidate;
    00754     }
    00755
    00756 protected:
    00757     RecordType* mRoot;
    00758     int mSize;
    00759
    00760     AllocatorType mAllocator;
    00761
    00766     inline void IsSane()
    00767     {
    00768         FBX_ASSERT((mRoot == 0) || (mRoot->mColor == RecordType::eBlack));
    00769         FBX_ASSERT(((mRoot == 0) && (mSize == 0)) || (mRoot != 0) && (mSize != 0));
    00770         IsSubTreeSane(mRoot);
    00771
    00772         ComputeBlackDepth(mRoot, 0);
    00773
    00774         RecordType* lNode = mRoot;
    00775         unsigned int lLeafBlackDepth = 0;
    00776         while (lNode)
    00777         {
    00778             if (lNode->mLeftChild == 0)
    00779             {
    00780                 lLeafBlackDepth = lNode->mBlackDepth + ((lNode->mColor == RecordType::eBlack) ? 1 : 0);
    00781             }
    00782
    00783             lNode = lNode->mLeftChild;
    00784         }
    00785
    00786         CheckLeavesBlackDepth(mRoot, lLeafBlackDepth);
    00787     }
    00788
    00789     inline void IsSubTreeSane(const RecordType* pNode) const
    00790     {
    00791         Compare lCompareKeys;
    00792
    00793         if (pNode)
    00794         {
    00795             FBX_ASSERT(pNode != pNode->mParent);
    00796             FBX_ASSERT(pNode != pNode->mLeftChild);
    00797             FBX_ASSERT(pNode != pNode->mRightChild);
    00798
    00799             // Check for two consecutive red nodes
    00800             FBX_ASSERT((pNode->mColor == RecordType::eBlack) ||
    00801                      (pNode->mLeftChild == NULL) ||
    00802                      (pNode->mLeftChild->mColor == RecordType::eBlack));
    00803
    00804             FBX_ASSERT((pNode->mColor == RecordType::eBlack) ||
    00805                      (pNode->mRightChild == NULL) ||
    00806                      (pNode->mRightChild->mColor == RecordType::eBlack));
    00807
    00808             // Check key ordering
    00809             FBX_ASSERT((pNode->mLeftChild == 0 ||
    00810                       lCompareKeys(pNode->GetKey(), pNode->mLeftChild->GetKey()) > 0));
    00811
    00812             FBX_ASSERT((pNode->mRightChild == 0 ||
    00813                       lCompareKeys(pNode->GetKey(), pNode->mRightChild->GetKey()) < 0));
    00814
    00815             IsSubTreeSane(pNode->mLeftChild);
    00816             IsSubTreeSane(pNode->mRightChild);
    00817         }
    00818     }
    00819
    00820     inline void ComputeBlackDepth(RecordType* pNode, unsigned int pDepth)
    00821     {
    00822         if (pNode)
    00823         {
    00824             pNode->mBlackDepth = pDepth;
    00825             if (pNode->mColor == RecordType::eBlack)
    00826             {
    00827                 pDepth++;
    00828             }
    00829
    00830             ComputeBlackDepth(pNode->mLeftChild, pDepth);
    00831             ComputeBlackDepth(pNode->mRightChild, pDepth);
    00832         }
    00833     }
    00834
    00835     inline void CheckLeavesBlackDepth(RecordType* pNode, unsigned int pBlackDepth)
    00836     {
    00837         if (pNode)
    00838         {
    00839             if ((pNode->mLeftChild == 0) || pNode->mRightChild == 0)
    00840             {
    00841                 int lBlackDepth = pNode->mBlackDepth + ((pNode->mColor == RecordType::eBlack) ? 1 : 0);
    00842                 FBX_ASSERT(lBlackDepth == pBlackDepth);
    00843             }
    00844
    00845             CheckLeavesBlackDepth(pNode->mLeftChild, pBlackDepth);
    00846             CheckLeavesBlackDepth(pNode->mRightChild, pBlackDepth);
    00847         }
    00848     }
    00849
    00850     inline RecordType* DuplicateSubTree(const RecordType* pNode)
    00851     {
    00852         RecordType* lNewSubTree = 0;
    00853
    00854         if (pNode)
    00855         {
    00856             void* lBuffer = mAllocator.AllocateRecords();
    00857             lNewSubTree = new(lBuffer) RecordType(*pNode);  //in-place new won't allocate memory, so it is safe
    00858             lNewSubTree->mLeftChild = DuplicateSubTree(pNode->mLeftChild);
    00859             lNewSubTree->mRightChild = DuplicateSubTree(pNode->mRightChild);
    00860
    00861             if (lNewSubTree->mLeftChild)
    00862             {
    00863                 lNewSubTree->mLeftChild->mParent = lNewSubTree;
    00864             }
    00865
    00866             if (lNewSubTree->mRightChild)
    00867             {
    00868                 lNewSubTree->mRightChild->mParent = lNewSubTree;
    00869             }
    00870         }
    00871
    00872         return lNewSubTree;
    00873     }
    00874
    00875     inline void FixNodesAfterInsertion(RecordType* pNode)
    00876     {
    00877         RecordType* lNode = pNode;
    00878         bool lDone = false;
    00879
    00880         while (!lDone)
    00881         {
    00882             lDone = true;
    00883
    00884             if (lNode->mParent == 0)
    00885             {
    00886                 lNode->mColor = RecordType::eBlack;
    00887             }
    00888             else if (lNode->mParent->mColor == RecordType::eRed)
    00889             {
    00890                 RecordType* lUncle = 0;
    00891                 if (lNode->mParent == lNode->mParent->mParent->mLeftChild)
    00892                 {
    00893                     lUncle = lNode->mParent->mParent->mRightChild;
    00894                 }
    00895                 else if (lNode->mParent == lNode->mParent->mParent->mRightChild)
    00896                 {
    00897                     lUncle = lNode->mParent->mParent->mLeftChild;
    00898                 }
    00899
    00900                 // since lNode->mParent is red, lNode->mParent->mParent exists
    00901
    00902                 if (lUncle && lUncle->mColor == RecordType::eRed)
    00903                 {
    00904                     lNode->mParent->mColor = RecordType::eBlack;
    00905                     lUncle->mColor = RecordType::eBlack;
    00906                     lNode->mParent->mParent->mColor = RecordType::eRed;
    00907                     lNode = lNode->mParent->mParent;
    00908
    00909                     lDone = false;
    00910                 }
    00911                 else
    00912                 {
    00913                     if ((lNode == lNode->mParent->mRightChild) &&
    00914                         (lNode->mParent == lNode->mParent->mParent->mLeftChild))
    00915                     {
    00916                         LeftRotate(lNode->mParent);
    00917                         lNode = lNode->mLeftChild;
    00918                     }
    00919                     else if ((lNode == lNode->mParent->mLeftChild) &&
    00920                             (lNode->mParent == lNode->mParent->mParent->mRightChild))
    00921                     {
    00922                         RightRotate(lNode->mParent);
    00923                         lNode = lNode->mRightChild;
    00924                     }
    00925
    00926                     lNode->mParent->mColor = RecordType::eBlack;
    00927                     lNode->mParent->mParent->mColor = RecordType::eRed;
    00928                     if ((lNode == lNode->mParent->mLeftChild) &&
    00929                         (lNode->mParent == lNode->mParent->mParent->mLeftChild))
    00930                     {
    00931                         RightRotate(lNode->mParent->mParent);
    00932                     }
    00933                     else
    00934                     {
    00935                         LeftRotate(lNode->mParent->mParent);
    00936                     }
    00937                 }
    00938             }
    00939         }
    00940
    00941         mRoot->mColor = RecordType::eBlack;
    00942     }
    00943
    00944     inline void LeftRotate(RecordType* pNode)
    00945     {
    00946         RecordType* lNode = pNode->mRightChild;
    00947
    00948     #ifdef _DEBUG
    00949         RecordType* A = pNode->mLeftChild;
    00950         RecordType* B = lNode->mLeftChild;
    00951         RecordType* C = lNode->mRightChild;
    00952         RecordType* Z = pNode->mParent;
    00953     #endif
    00954
    00955         pNode->mRightChild = lNode->mLeftChild;
    00956         if (pNode->mRightChild)
    00957         {
    00958             pNode->mRightChild->mParent = pNode;
    00959         }
    00960
    00961         lNode->mParent = pNode->mParent;
    00962         if (pNode->mParent == 0)
    00963         {
    00964             FBX_ASSERT(mRoot == pNode);
    00965             mRoot = lNode;
    00966         }
    00967         else if (pNode == pNode->mParent->mLeftChild)
    00968         {
    00969             pNode->mParent->mLeftChild = lNode;
    00970         }
    00971         else
    00972         {
    00973             pNode->mParent->mRightChild = lNode;
    00974         }
    00975         pNode->mParent = lNode;
    00976         lNode->mLeftChild = pNode;
    00977
    00978         FBX_ASSERT(pNode->mLeftChild == A);
    00979         FBX_ASSERT(pNode->mRightChild == B);
    00980         FBX_ASSERT(pNode->mParent == lNode);
    00981
    00982         FBX_ASSERT(lNode->mLeftChild == pNode);
    00983         FBX_ASSERT(lNode->mRightChild == C);
    00984         FBX_ASSERT(lNode->mParent == Z);
    00985
    00986         FBX_ASSERT(A == 0 || A->mParent == pNode);
    00987         FBX_ASSERT(B == 0 || B->mParent == pNode);
    00988         FBX_ASSERT(C == 0 || C->mParent == lNode);
    00989         FBX_ASSERT(Z == 0 || Z->mLeftChild == lNode || Z->mRightChild == lNode);
    00990     }
    00991
    00992     inline void RightRotate(RecordType* pNode)
    00993     {
    00994         RecordType* lNode = pNode->mLeftChild;
    00995
    00996     #ifdef _DEBUG
    00997         RecordType* A = lNode->mLeftChild;
    00998         RecordType* B = lNode->mRightChild;
    00999         RecordType* C = pNode->mRightChild;
    01000         RecordType* Z = pNode->mParent;
    01001     #endif
    01002
    01003         pNode->mLeftChild = lNode->mRightChild;
    01004         if (pNode->mLeftChild)
    01005         {
    01006             pNode->mLeftChild->mParent = pNode;
    01007         }
    01008
    01009         lNode->mParent = pNode->mParent;
    01010         if (pNode->mParent == 0)
    01011         {
    01012             FBX_ASSERT(mRoot == pNode);
    01013             mRoot = lNode;
    01014         }
    01015         else if (pNode == pNode->mParent->mRightChild)
    01016         {
    01017             pNode->mParent->mRightChild = lNode;
    01018         }
    01019         else
    01020         {
    01021             pNode->mParent->mLeftChild = lNode;
    01022         }
    01023         pNode->mParent = lNode;
    01024         lNode->mRightChild = pNode;
    01025
    01026         FBX_ASSERT(lNode->mLeftChild == A);
    01027         FBX_ASSERT(lNode->mRightChild == pNode);
    01028         FBX_ASSERT(lNode->mParent == Z);
    01029
    01030         FBX_ASSERT(pNode->mLeftChild == B);
    01031         FBX_ASSERT(pNode->mRightChild == C);
    01032         FBX_ASSERT(pNode->mParent == lNode);
    01033
    01034         FBX_ASSERT(A == 0 || A->mParent == lNode);
    01035         FBX_ASSERT(B == 0 || B->mParent == pNode);
    01036         FBX_ASSERT(C == 0 || C->mParent == pNode);
    01037         FBX_ASSERT(Z == 0 || Z->mLeftChild == lNode || Z->mRightChild == lNode);
    01038     }
    01039
    01040     inline void RemoveNode(RecordType* pNode)
    01041     {
    01042         if (pNode->mLeftChild == 0)
    01043         {
    01044             if (pNode->mRightChild == 0)
    01045             {
    01046                 if (pNode->mParent)
    01047                 {
    01048                     if (pNode->mParent->mLeftChild == pNode)
    01049                     {
    01050                         pNode->mParent->mLeftChild = 0;
    01051                     }
    01052                     else if (pNode->mParent->mRightChild == pNode)
    01053                     {
    01054                         pNode->mParent->mRightChild = 0;
    01055                     }
    01056                     else
    01057                     {
    01058                         FBX_ASSERT_NOW("Node not found in FbxRedBlackTree");
    01059                     }
    01060                 }
    01061                 else
    01062                 {
    01063                     FBX_ASSERT(mRoot == pNode);
    01064                     mRoot = 0;
    01065                 }
    01066
    01067                 if (pNode->mColor == RecordType::eBlack)
    01068                 {
    01069                     FixNodesAfterRemoval(pNode->mParent, 0);
    01070                 }
    01071             }
    01072             else
    01073             {
    01074                 if (pNode->mParent)
    01075                 {
    01076                     if (pNode->mParent->mLeftChild == pNode)
    01077                     {
    01078                         pNode->mParent->mLeftChild = pNode->mRightChild;
    01079                         pNode->mRightChild->mParent = pNode->mParent;
    01080                     }
    01081                     else if (pNode->mParent->mRightChild == pNode)
    01082                     {
    01083                         pNode->mParent->mRightChild = pNode->mRightChild;
    01084                         pNode->mRightChild->mParent = pNode->mParent;
    01085                     }
    01086                     else
    01087                     {
    01088                         FBX_ASSERT_NOW("Node not found in FbxRedBlackTree");
    01089                     }
    01090                 }
    01091                 else
    01092                 {
    01093                     FBX_ASSERT(mRoot == pNode);
    01094                     mRoot = pNode->mRightChild;
    01095                     pNode->mRightChild->mParent = 0;
    01096                 }
    01097
    01098                 if (pNode->mColor == RecordType::eBlack)
    01099                 {
    01100                     FixNodesAfterRemoval(pNode->mRightChild->mParent, pNode->mRightChild);
    01101                 }
    01102             }
    01103         }
    01104         else
    01105         {
    01106             if (pNode->mRightChild == 0)
    01107             {
    01108                 if (pNode->mParent)
    01109                 {
    01110                     if (pNode->mParent->mLeftChild == pNode)
    01111                     {
    01112                         pNode->mParent->mLeftChild = pNode->mLeftChild;
    01113                         pNode->mLeftChild->mParent = pNode->mParent;
    01114                     }
    01115                     else if (pNode->mParent->mRightChild == pNode)
    01116                     {
    01117                         pNode->mParent->mRightChild = pNode->mLeftChild;
    01118                         pNode->mLeftChild->mParent = pNode->mParent;
    01119                     }
    01120                     else
    01121                     {
    01122                         FBX_ASSERT_NOW("Node not found in FbxRedBlackTree");
    01123                     }
    01124                 }
    01125                 else
    01126                 {
    01127                     FBX_ASSERT(mRoot == pNode);
    01128                     mRoot = pNode->mLeftChild;
    01129                     pNode->mLeftChild->mParent = 0;
    01130                 }
    01131
    01132                 if (pNode->mColor == RecordType::eBlack)
    01133                 {
    01134                     FixNodesAfterRemoval(pNode->mLeftChild->mParent, pNode->mLeftChild);
    01135                 }
    01136             }
    01137             else
    01138             {
    01139                 RecordType* lMinRightNode = pNode->mRightChild->Minimum();
    01140                 RemoveNode(lMinRightNode);
    01141
    01142                 lMinRightNode->mColor = pNode->mColor;
    01143                 ReplaceNode(pNode, lMinRightNode);
    01144             }
    01145         }
    01146
    01147         pNode->mParent = 0;
    01148         pNode->mLeftChild = 0;
    01149         pNode->mRightChild = 0;
    01150     }
    01151
    01152     inline void ReplaceNode(RecordType* pNodeToReplace, RecordType* pReplacement)
    01153     {
    01154         pReplacement->mParent = pNodeToReplace->mParent;
    01155         if (pNodeToReplace->mParent)
    01156         {
    01157             if (pNodeToReplace->mParent->mLeftChild == pNodeToReplace)
    01158             {
    01159                 pNodeToReplace->mParent->mLeftChild = pReplacement;
    01160             }
    01161             else if (pNodeToReplace->mParent->mRightChild == pNodeToReplace)
    01162             {
    01163                 pNodeToReplace->mParent->mRightChild = pReplacement;
    01164             }
    01165         }
    01166         else
    01167         {
    01168             FBX_ASSERT(mRoot == pNodeToReplace);
    01169             mRoot = pReplacement;
    01170         }
    01171
    01172         pReplacement->mLeftChild = pNodeToReplace->mLeftChild;
    01173         if (pReplacement->mLeftChild)
    01174         {
    01175             pReplacement->mLeftChild->mParent = pReplacement;
    01176         }
    01177
    01178         pReplacement->mRightChild = pNodeToReplace->mRightChild;
    01179         if (pReplacement->mRightChild)
    01180         {
    01181             pReplacement->mRightChild->mParent = pReplacement;
    01182         }
    01183     }
    01184
    01185     inline RecordType* Sibling(const RecordType* pParent, const RecordType* pNode) const
    01186     {
    01187         if (pParent)
    01188         {
    01189             if (pParent->mLeftChild == pNode)
    01190             {
    01191                 return pParent->mRightChild;
    01192             }
    01193             else if (pParent->mRightChild == pNode)
    01194             {
    01195                 return pParent->mLeftChild;
    01196             }
    01197         }
    01198
    01199         return 0;
    01200     }
    01201
    01202     inline bool IsBlack(const RecordType* pNode)
    01203     {
    01204         return ((pNode == 0) || (pNode->mColor == RecordType::eBlack));
    01205     }
    01206
    01207     inline void FixNodesAfterRemoval(RecordType* pParent, RecordType* pNode)
    01208     {
    01209         RecordType* lParent = pParent;
    01210         RecordType* lNode = pNode;
    01211         bool lDone = false;
    01212
    01213         while (!lDone)
    01214         {
    01215             lDone = true;
    01216
    01217             if (!IsBlack(lNode))
    01218             {
    01219                 lNode->mColor = RecordType::eBlack;
    01220             }
    01221             else if (lParent != NULL)
    01222             {
    01223                 RecordType* lSibling = Sibling(lParent, lNode);
    01224
    01225                 if (!IsBlack(lSibling))
    01226                 {
    01227                     lParent->mColor = RecordType::eRed;
    01228                     lSibling->mColor = RecordType::eBlack;
    01229                     if (lNode == lParent->mLeftChild)
    01230                     {
    01231                         LeftRotate(lParent);
    01232                     }
    01233                     else
    01234                     {
    01235                         RightRotate(lParent);
    01236                     }
    01237
    01238                     // update sibling: it may have change after rotation
    01239                     // parent was not affected by this rotation
    01240                     lSibling = Sibling(lParent, lNode);
    01241                 }
    01242
    01243                 /* check this for null sibling */
    01244                 if (lSibling &&
    01245                     IsBlack(lParent) &&
    01246                     IsBlack(lSibling) &&
    01247                     IsBlack(lSibling->mLeftChild) &&
    01248                     IsBlack(lSibling->mRightChild))
    01249                 {
    01250                     lSibling->mColor = RecordType::eRed;
    01251                     lNode = lParent;
    01252                     lParent = lParent->mParent;
    01253                     lDone = false;
    01254                 }
    01255                 else
    01256                 {
    01257                     if (!IsBlack(lParent) &&
    01258                         IsBlack(lSibling) &&
    01259                         ((lSibling == 0) || IsBlack(lSibling->mLeftChild)) &&
    01260                         ((lSibling == 0) || IsBlack(lSibling->mRightChild)))
    01261                     {
    01262                         if (lSibling)
    01263                         {
    01264                             lSibling->mColor = RecordType::eRed;
    01265                         }
    01266                         lParent->mColor = RecordType::eBlack;
    01267                     }
    01268                     else // lSibling != 0
    01269                     {
    01270                         if ((lNode == lParent->mLeftChild) &&
    01271                             IsBlack(lSibling) &&
    01272                             !IsBlack(lSibling->mLeftChild) &&
    01273                             IsBlack(lSibling->mRightChild))
    01274                         {
    01275                             lSibling->mColor = RecordType::eRed;
    01276                             lSibling->mLeftChild->mColor = RecordType::eBlack;
    01277                             RightRotate(lSibling);
    01278                         }
    01279                         else if ((lNode == lParent->mRightChild) &&
    01280                                  IsBlack(lSibling) &&
    01281                                  IsBlack(lSibling->mLeftChild) &&
    01282                                  !IsBlack(lSibling->mRightChild))
    01283                         {
    01284                             lSibling->mColor = RecordType::eRed;
    01285                             lSibling->mRightChild->mColor = RecordType::eBlack;
    01286                             LeftRotate(lSibling);
    01287                         }
    01288
    01289                         // update sibling: it may have change after rotation
    01290                         lSibling = Sibling(lParent, lNode);
    01291                         FBX_ASSERT(lSibling != 0); // lSibling is now
    01292                                                  // the former red
    01293                                                  // child of the
    01294                                                  // former sibling
    01295
    01296                         lSibling->mColor = lParent->mColor;
    01297                         lParent->mColor = RecordType::eBlack;
    01298                         if (lNode == lParent->mLeftChild)
    01299                         {
    01300                             if (lSibling->mRightChild)
    01301                             {
    01302                                 lSibling->mRightChild->mColor = RecordType::eBlack;
    01303                             }
    01304                             LeftRotate(lParent);
    01305                         }
    01306                         else
    01307                         {
    01308                             if (lSibling->mLeftChild)
    01309                             {
    01310                                 lSibling->mLeftChild->mColor = RecordType::eBlack;
    01311                             }
    01312                             RightRotate(lParent);
    01313                         }
    01314                     }
    01315                 }
    01316             }
    01317         }
    01318
    01319         if (mRoot)
    01320         {
    01321             mRoot->mColor = RecordType::eBlack;
    01322         }
    01323     }
    01324
    01325     inline void ClearSubTree(RecordType* pNode)
    01326     {
    01327         if (pNode)
    01328         {
    01329             ClearSubTree(pNode->mLeftChild);
    01330             ClearSubTree(pNode->mRightChild);
    01331             pNode->~RecordType();
    01332             mAllocator.FreeMemory(pNode);
    01333         }
    01334     }
    01335
    01336     inline int GetSubTreeSize(RecordType* pNode) const
    01337     {
    01338         if (pNode)
    01339         {
    01340             return GetSubTreeSize(pNode->mLeftChild) + GetSubTreeSize(pNode->mRightChild) + 1;
    01341         }
    01342         else
    01343         {
    01344             return 0;
    01345         }
    01346     }
    01347 };
    01348
    01349 #endif /* !DOXYGEN_SHOULD_SKIP_THIS *****************************************************************************************/
    01350
    01351 #include <fbxsdk/fbxsdk_nsend.h>
    01352
    01353 #endif /*_FBXSDK_CORE_BASE_REDBLACKTREE_H_ */