- Main Page
- Classes
- Files
- Directories
- Examples

- File List
- File Members

# fbxmap.h

Go to the documentation of this file.

    00001 /****************************************************************************************
    00002
    00003    Copyright (C) 2012 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_MAP_H_
    00014 #define _FBXSDK_CORE_BASE_MAP_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 /* Examples of KEY_COMPARE_FUNCTOR class
    00024
    00025    with KEY_TYPE = int
    00026     class IntCompare {
    00027         inline int operator()(int pKeyA, int pKeyB) const
    00028         {
    00029             return (pKeyA < pKeyB) ? -1 : ((pKeyB < pKeyA) ? 1 : 0);
    00030         }
    00031     };
    00032
    00033    with KEY_TYPE = Class
    00034     class ClassCompare {
    00035         inline int operator()(const Class& pKeyA, const Class& pKeyB) const
    00036         {
    00037             return (pKeyA < pKeyB) ? -1 : ((pKeyB < pKeyA) ? 1 : 0);
    00038         }
    00039     };
    00040
    00041    with KEY_TYPE = char*
    00042     class StrCompare {
    00043         inline int operator()(const char* pKeyA, const char* pKeyB) const
    00044         {
    00045             return strcmp(pKeyA, pKeyB);
    00046         }
    00047     };
    00048
    00049 */
    00050
    00051 #ifndef DOXYGEN_SHOULD_SKIP_THIS
    00052
    00053 template <typename RecordType>    class FbxRedBack_ConstIteratorType;
    00054 template <typename RecordType>    class FbxRedBack_IteratorType;
    00055
    00056 template <typename RecordType>
    00057
    00058 class FbxRedBack_IteratorType
    00059 {
    00060 public:
    00061     FbxRedBack_IteratorType() : mRecord(0) {}
    00062     FbxRedBack_IteratorType(RecordType* pRecord) : mRecord(pRecord) {}
    00063     FbxRedBack_IteratorType(const FbxRedBack_IteratorType<RecordType>& pV) : mRecord(pV.mRecord) {}
    00064
    00065     // prefix ++
    00066     FbxRedBack_IteratorType & operator++()
    00067     {
    00068         FBX_ASSERT( mRecord != NULL );
    00069         mRecord = mRecord->Successor();
    00070         return *this;
    00071     }
    00072
    00073     // postfix ++
    00074     const FbxRedBack_IteratorType operator++(int)
    00075     {
    00076         FbxRedBack_IteratorType t(*this);
    00077         operator++();
    00078         return t;
    00079     }
    00080
    00081     // prefix --
    00082     FbxRedBack_IteratorType & operator--()
    00083     {
    00084         FBX_ASSERT( mRecord );
    00085         mRecord = mRecord->Predecessor();
    00086         return *this;
    00087     }
    00088
    00089     // postfix --
    00090     const FbxRedBack_IteratorType operator--(int)
    00091     {
    00092         FbxRedBack_IteratorType t(*this);
    00093         operator--();
    00094         return t;
    00095     }
    00096
    00097     const RecordType& operator*() const
    00098     {
    00099         FBX_ASSERT( mRecord );
    00100
    00101         return *mRecord;
    00102     }
    00103
    00104     RecordType& operator*()
    00105     {
    00106         FBX_ASSERT( mRecord );
    00107
    00108         return *mRecord;
    00109     }
    00110
    00111     const RecordType* operator->() const
    00112     {
    00113         FBX_ASSERT( mRecord );
    00114
    00115         return mRecord;
    00116     }
    00117
    00118     RecordType* operator->()
    00119     {
    00120         FBX_ASSERT( mRecord );
    00121
    00122         return mRecord;
    00123     }
    00124
    00125     inline bool operator==(const FbxRedBack_IteratorType& pOther) const
    00126     {
    00127         return mRecord == pOther.mRecord;
    00128     }
    00129
    00130     inline bool operator !=(const FbxRedBack_IteratorType& pOther) const
    00131     {
    00132         return mRecord != pOther.mRecord;
    00133     }
    00134
    00135 protected:
    00136     friend class FbxRedBack_ConstIteratorType<RecordType>;
    00137
    00138     RecordType* mRecord;
    00139 };
    00140
    00141 template <typename RecordType>
    00142 class FbxRedBack_ConstIteratorType
    00143 {
    00144 public:
    00145     FbxRedBack_ConstIteratorType() : mRecord(0) {}
    00146     FbxRedBack_ConstIteratorType(const RecordType* pRecord) : mRecord(pRecord) {}
    00147     FbxRedBack_ConstIteratorType(const FbxRedBack_IteratorType<RecordType>& pV) : mRecord(pV.mRecord) {}
    00148     FbxRedBack_ConstIteratorType(const FbxRedBack_ConstIteratorType<RecordType>& pV) : mRecord(pV.mRecord) {}
    00149
    00150     // prefix ++
    00151     FbxRedBack_ConstIteratorType & operator++()
    00152     {
    00153         FBX_ASSERT( mRecord != NULL );
    00154         mRecord = mRecord->Successor();
    00155         return *this;
    00156     }
    00157
    00158     // postfix ++
    00159     const FbxRedBack_ConstIteratorType operator++(int)
    00160     {
    00161         FbxRedBack_ConstIteratorType t(*this);
    00162         operator++();
    00163         return t;
    00164     }
    00165
    00166     // prefix --
    00167     FbxRedBack_ConstIteratorType & operator--()
    00168     {
    00169         FBX_ASSERT( mRecord );
    00170         mRecord = mRecord->Predecessor();
    00171         return *this;
    00172     }
    00173
    00174     // postfix --
    00175     const FbxRedBack_ConstIteratorType operator--(int)
    00176     {
    00177         FbxRedBack_ConstIteratorType t(*this);
    00178         operator--();
    00179         return t;
    00180     }
    00181
    00182     const RecordType& operator*() const
    00183     {
    00184         FBX_ASSERT( mRecord );
    00185
    00186         return *mRecord;
    00187     }
    00188
    00189     const RecordType& operator*()
    00190     {
    00191         FBX_ASSERT( mRecord );
    00192
    00193         return *mRecord;
    00194     }
    00195
    00196     const RecordType* operator->() const
    00197     {
    00198         FBX_ASSERT( mRecord );
    00199
    00200         return mRecord;
    00201     }
    00202
    00203     const RecordType* operator->()
    00204     {
    00205         FBX_ASSERT( mRecord );
    00206
    00207         return mRecord;
    00208     }
    00209
    00210     inline bool operator==(const FbxRedBack_ConstIteratorType& pOther) const
    00211     {
    00212         return mRecord == pOther.mRecord;
    00213     }
    00214
    00215     inline bool operator !=(const FbxRedBack_ConstIteratorType& pOther) const
    00216     {
    00217         return mRecord != pOther.mRecord;
    00218     }
    00219
    00220 protected:
    00221     friend class FbxRedBack_IteratorType<RecordType>;
    00222
    00223     const RecordType* mRecord;
    00224 };
    00225
    00228 template <typename DATA_TYPE,
    00229           typename KEY_COMPARE_FUNCTOR,
    00230           typename ALLOCATOR>
    00231 class  FbxRedBlackTree
    00232 {
    00233 public:
    00234     typedef DATA_TYPE DataType;
    00235     typedef typename DATA_TYPE::KeyType         KeyType;
    00236     typedef typename DATA_TYPE::ConstKeyType    ConstKeyType;
    00237     typedef typename DATA_TYPE::ValueType       ValueType;
    00238     typedef typename DATA_TYPE::ConstValueType  ConstValueType;
    00239     typedef ALLOCATOR AllocatorType;
    00240
    00245     class RecordType
    00246     {
    00247     public:
    00248         inline ConstKeyType& GetKey() const { return mData.GetKey(); }
    00249         inline ConstValueType& GetValue() const { return mData.GetValue(); }
    00250         inline ValueType& GetValue() { return mData.GetValue(); }
    00251
    00252         inline const RecordType* Minimum() const
    00253         {
    00254             const RecordType* lParent = 0;
    00255             const RecordType* lNode = this;
    00256             while (lNode != 0)
    00257             {
    00258                 lParent = lNode;
    00259                 lNode = lNode->mLeftChild;
    00260             }
    00261
    00262             return lParent;
    00263         }
    00264
    00265         inline RecordType* Minimum()
    00266         {
    00267             RecordType* lParent = 0;
    00268             RecordType* lNode = this;
    00269             while (lNode != 0)
    00270             {
    00271                 lParent = lNode;
    00272                 lNode = lNode->mLeftChild;
    00273             }
    00274
    00275             return lParent;
    00276         }
    00277
    00278         inline const RecordType* Maximum() const
    00279         {
    00280             const RecordType* lParent = 0;
    00281             const RecordType* lNode = this;
    00282             while (lNode != 0)
    00283             {
    00284                 lParent = lNode;
    00285                 lNode = lNode->mRightChild;
    00286             }
    00287
    00288             return lParent;
    00289         }
    00290
    00291         inline RecordType* Maximum()
    00292         {
    00293             RecordType* lParent = 0;
    00294             RecordType* lNode = this;
    00295             while (lNode != 0)
    00296             {
    00297                 lParent = lNode;
    00298                 lNode = lNode->mRightChild;
    00299             }
    00300
    00301             return lParent;
    00302         }
    00303
    00304         inline const RecordType* Predecessor() const
    00305         {
    00306             if (mLeftChild)
    00307             {
    00308                 return mLeftChild->Maximum();
    00309             }
    00310             else
    00311             {
    00312                 const RecordType* lParent = mParent;
    00313                 const RecordType* lNode = this;
    00314
    00315                 while (lParent && lParent->mLefttChild == lNode)
    00316                 {
    00317                     lNode = lParent;
    00318                     lParent = lParent->mParent;
    00319                 }
    00320
    00321                 return lParent;
    00322             }
    00323         }
    00324
    00325         inline RecordType* Predecessor()
    00326         {
    00327             if (mLeftChild)
    00328             {
    00329                 return mLeftChild->Maximum();
    00330             }
    00331             else
    00332             {
    00333                 RecordType* lParent = mParent;
    00334                 RecordType* lNode = this;
    00335
    00336                 while (lParent && lParent->mLeftChild == lNode)
    00337                 {
    00338                     lNode = lParent;
    00339                     lParent = lParent->mParent;
    00340                 }
    00341
    00342                 return lParent;
    00343             }
    00344         }
    00345
    00346         inline const RecordType* Successor() const
    00347         {
    00348             if (mRightChild)
    00349             {
    00350                 return mRightChild->Minimum();
    00351             }
    00352             else
    00353             {
    00354                 const RecordType* lParent = mParent;
    00355                 const RecordType* lNode = this;
    00356
    00357                 while (lParent && lParent->mRightChild == lNode)
    00358                 {
    00359                     lNode = lParent;
    00360                     lParent = lParent->mParent;
    00361                 }
    00362
    00363                 return lParent;
    00364             }
    00365         }
    00366
    00367         inline RecordType* Successor()
    00368         {
    00369             if (mRightChild)
    00370             {
    00371                 return mRightChild->Minimum();
    00372             }
    00373             else
    00374             {
    00375                 RecordType* lParent = mParent;
    00376                 RecordType* lNode = this;
    00377
    00378                 while (lParent && lParent->mRightChild == lNode)
    00379                 {
    00380                     lNode = lParent;
    00381                     lParent = lParent->mParent;
    00382                 }
    00383
    00384                 return lParent;
    00385             }
    00386         }
    00387
    00388         inline const int GetBlackDepth() { return mBlackDepth; }
    00389
    00390     private:
    00391         enum ETreeType {eRed, eBlack};
    00392
    00393         inline RecordType(const DataType& pData)
    00394             : mData(pData)
    00395             , mParent(0)
    00396             , mLeftChild(0)
    00397             , mRightChild(0)
    00398             , mColor(eRed)
    00399             , mBlackDepth(0)
    00400         {
    00401         }
    00402
    00403         inline RecordType(const RecordType& pRecordType)
    00404             : mData(pRecordType.mData)
    00405             , mParent(0)
    00406             , mLeftChild(0)
    00407             , mRightChild(0)
    00408             , mColor(pRecordType.mColor)
    00409             , mBlackDepth(pRecordType.mBlackDepth)
    00410         {
    00411         }
    00412
    00413         DataType mData;
    00414
    00415         friend class FbxRedBlackTree;
    00416
    00417         RecordType* mParent;
    00418         RecordType* mLeftChild;
    00419         RecordType* mRightChild;
    00420         unsigned int mColor:2;
    00421         unsigned int mBlackDepth:30;
    00422     };
    00423
    00424 public:
    00425     typedef FbxRedBack_ConstIteratorType<RecordType>  ConstIteratorType;
    00426     typedef FbxRedBack_IteratorType<RecordType>       IteratorType;
    00427
    00428 public:
    00429     inline FbxRedBlackTree() : mRoot(0), mSize(0), mAllocator(sizeof(RecordType)) {}
    00430     inline FbxRedBlackTree(const FbxRedBlackTree& pTree) : mRoot(0), mSize(0), mAllocator(sizeof(RecordType)) { operator=(pTree); }
    00431     inline ~FbxRedBlackTree() { Clear(); }
    00432
    00436     inline FbxRedBlackTree& operator=(const FbxRedBlackTree& pTree)
    00437     {
    00438         if( this != &pTree )
    00439         {
    00440             Clear();
    00441
    00442             mAllocator = pTree.mAllocator;
    00443
    00444             if( pTree.mRoot )
    00445             {
    00446                 void* lBuffer = mAllocator.AllocateRecords();
    00447                 mRoot = new(lBuffer) RecordType(*(pTree.mRoot));
    00448                 mRoot->mLeftChild = DuplicateSubTree(pTree.mRoot->mLeftChild);
    00449                 mRoot->mRightChild = DuplicateSubTree(pTree.mRoot->mRightChild);
    00450
    00451                 if (mRoot->mLeftChild)
    00452                 {
    00453                     mRoot->mLeftChild->mParent = mRoot;
    00454                 }
    00455
    00456                 if (mRoot->mRightChild)
    00457                 {
    00458                     mRoot->mRightChild->mParent = mRoot;
    00459                 }
    00460             }
    00461             else
    00462             {
    00463                 FBX_ASSERT( pTree.mSize == 0 );
    00464                 FBX_ASSERT( mRoot == 0 );
    00465             }
    00466
    00467             mSize = pTree.mSize;
    00468         }
    00469
    00470         return *this;
    00471     }
    00472
    00473     inline bool operator==(const FbxRedBlackTree& pTree) const
    00474     {
    00475         // Check a few quick shortcuts
    00476         if( this == &pTree )
    00477             return true;
    00478
    00479         if( GetSize() != pTree.GetSize() )
    00480             return false;
    00481
    00482         // Iterator through all nodes; if we reach the end of both iterators at the same
    00483         // time then we have two iterators that match.
    00484         ConstIteratorType End;
    00485         ConstIteratorType Iter1(Minimum());
    00486         ConstIteratorType Iter2(pTree.Minimum());
    00487
    00488         while( (Iter1 != End) && (Iter2 != End) &&
    00489                (Iter1->GetKey() == Iter2->GetKey()) &&
    00490                (Iter1->GetValue() == Iter2->GetValue()) )
    00491         {
    00492             ++Iter1;
    00493             ++Iter2;
    00494         }
    00495
    00496         return Iter1 == End && Iter2 == End;
    00497     }
    00498
    00502     inline void Reserve(unsigned int pRecordCount)
    00503     {
    00504         mAllocator.Reserve(pRecordCount);
    00505     }
    00506
    00510     inline int GetSize() const { return mSize; }
    00511
    00512     inline bool Empty() const { return mSize == 0; }
    00513
    00519     inline FbxPair<RecordType*, bool> Insert(const DataType& pData)
    00520     {
    00521         KEY_COMPARE_FUNCTOR lCompareKeys;
    00522         bool lResult = false;
    00523         RecordType* lParent = 0;
    00524         RecordType* lNode = mRoot;
    00525         while (lNode != 0)
    00526         {
    00527             const KeyType& lNodeKey = lNode->GetKey();
    00528             const KeyType& lDataKey = pData.GetKey();
    00529
    00530             if (lCompareKeys(lNodeKey, lDataKey) < 0)
    00531             {
    00532                 lParent = lNode;
    00533                 lNode = lNode->mRightChild;
    00534             }
    00535             else if (lCompareKeys(lNodeKey, lDataKey) > 0)
    00536             {
    00537                 lParent = lNode;
    00538                 lNode = lNode->mLeftChild;
    00539             }
    00540             else
    00541             {
    00542                 break;
    00543             }
    00544         }
    00545
    00546         if (lNode == 0)
    00547         {
    00548             void* lBuffer = mAllocator.AllocateRecords();
    00549             lNode = new(lBuffer) RecordType(pData);
    00550             mSize++;
    00551
    00552             FBX_ASSERT(lNode == lBuffer);
    00553
    00554             if (lParent)
    00555             {
    00556                 if (lCompareKeys(lParent->GetKey(), pData.GetKey()) < 0)
    00557                 {
    00558                     FBX_ASSERT(lParent->mRightChild == 0);
    00559                     lParent->mRightChild = lNode;
    00560                     lNode->mParent = lParent;
    00561                 }
    00562                 else
    00563                 {
    00564                     FBX_ASSERT(lParent->mLeftChild == 0);
    00565                     lParent->mLeftChild = lNode;
    00566                     lNode->mParent = lParent;
    00567                 }
    00568             }
    00569             else
    00570             {
    00571                 mRoot = lNode;
    00572             }
    00573
    00574             // Fix red black tree property
    00575             FixNodesAfterInsertion(lNode);
    00576
    00577             lResult = true;
    00578         }
    00579
    00580         return FbxPair<RecordType*, bool>(lNode, lResult);
    00581     }
    00582
    00586     inline bool Remove(const KeyType& pKey)
    00587     {
    00588         KEY_COMPARE_FUNCTOR lCompareKeys;
    00589         bool lResult = false;
    00590         RecordType* lNode = mRoot;
    00591         while (lNode != 0)
    00592         {
    00593             if (lCompareKeys(lNode->GetKey(), pKey) < 0)
    00594             {
    00595                 lNode = lNode->mRightChild;
    00596             }
    00597             else if (lCompareKeys(lNode->GetKey(), pKey) > 0)
    00598             {
    00599                 lNode = lNode->mLeftChild;
    00600             }
    00601             else
    00602             {
    00603                 break;
    00604             }
    00605         }
    00606
    00607         if (lNode)
    00608         {
    00609             RemoveNode(lNode);
    00610             mSize--;
    00611             lNode->~RecordType();
    00612             mAllocator.FreeMemory(lNode);
    00613
    00614             lResult = true;
    00615         }
    00616
    00617         return lResult;
    00618     }
    00619
    00622     inline void Clear()
    00623     {
    00624         if (mRoot)
    00625         {
    00626             ClearSubTree(mRoot->mLeftChild);
    00627             ClearSubTree(mRoot->mRightChild);
    00628             mRoot->~RecordType();
    00629             mAllocator.FreeMemory(mRoot);
    00630             mRoot = 0;
    00631             mSize = 0;
    00632         }
    00633     }
    00634
    00638     inline const RecordType* Minimum() const
    00639     {
    00640         if (0 != mRoot)
    00641         {
    00642             return mRoot->Minimum();
    00643         }
    00644         else
    00645         {
    00646             return 0;
    00647         }
    00648     }
    00649
    00653     inline RecordType* Minimum()
    00654     {
    00655         if (0 != mRoot)
    00656         {
    00657             return mRoot->Minimum();
    00658         }
    00659         else
    00660         {
    00661             return 0;
    00662         }
    00663     }
    00664
    00668     inline const RecordType* Maximum() const
    00669     {
    00670         if (0 != mRoot)
    00671         {
    00672             return mRoot->Maximum();
    00673         }
    00674         else
    00675         {
    00676             return 0;
    00677         }
    00678     }
    00679
    00683     inline RecordType* Maximum()
    00684     {
    00685         if (0 != mRoot)
    00686         {
    00687             return mRoot->Maximum();
    00688         }
    00689         else
    00690         {
    00691             return 0;
    00692         }
    00693     }
    00694
    00699     inline const RecordType* Find(const KeyType& pKey) const
    00700     {
    00701         KEY_COMPARE_FUNCTOR lCompareKeys;
    00702         const RecordType* lNode = mRoot;
    00703         while (lNode != 0)
    00704         {
    00705             if (lCompareKeys(lNode->GetKey(), pKey) < 0)
    00706             {
    00707                 lNode = lNode->mRightChild;
    00708             }
    00709             else if (lCompareKeys(lNode->GetKey(), pKey) > 0)
    00710             {
    00711                 lNode = lNode->mLeftChild;
    00712             }
    00713             else
    00714             {
    00715                 break;
    00716             }
    00717         }
    00718
    00719         return lNode;
    00720     }
    00721
    00726     inline RecordType* Find(const KeyType& pKey)
    00727     {
    00728         KEY_COMPARE_FUNCTOR lCompareKeys;
    00729         RecordType* lNode = mRoot;
    00730         while (lNode != 0)
    00731         {
    00732             if (lCompareKeys(lNode->GetKey(), pKey) < 0)
    00733             {
    00734                 lNode = lNode->mRightChild;
    00735             }
    00736             else if (lCompareKeys(lNode->GetKey(), pKey) > 0)
    00737             {
    00738                 lNode = lNode->mLeftChild;
    00739             }
    00740             else
    00741             {
    00742                 break;
    00743             }
    00744         }
    00745
    00746         return lNode;
    00747     }
    00748
    00753     inline const RecordType* UpperBound(const KeyType& pKey) const
    00754     {
    00755         KEY_COMPARE_FUNCTOR lCompareKeys;
    00756         const RecordType* lNode = mRoot;
    00757         const RecordType* lCandidate = 0;
    00758         while (lNode != 0)
    00759         {
    00760             if (lCompareKeys(lNode->GetKey(), pKey) <= 0)
    00761             {
    00762                 lNode = lNode->mRightChild;
    00763             }
    00764             else if (lCompareKeys(lNode->GetKey(), pKey) > 0)
    00765             {
    00766                 lCandidate = lNode;
    00767                 lNode = lNode->mLeftChild;
    00768             }
    00769         }
    00770
    00771         return lCandidate;
    00772     }
    00773
    00778     inline RecordType* UpperBound(const KeyType& pKey)
    00779     {
    00780         KEY_COMPARE_FUNCTOR lCompareKeys;
    00781         RecordType* lNode = mRoot;
    00782         RecordType* lCandidate = 0;
    00783         while (lNode != 0)
    00784         {
    00785             if (lCompareKeys(lNode->GetKey(), pKey) <= 0)
    00786             {
    00787                 lNode = lNode->mRightChild;
    00788             }
    00789             else if (lCompareKeys(lNode->GetKey(), pKey) > 0)
    00790             {
    00791                 lCandidate = lNode;
    00792                 lNode = lNode->mLeftChild;
    00793             }
    00794         }
    00795
    00796         return lCandidate;
    00797     }
    00798
    00799 protected:
    00800     RecordType* mRoot;
    00801     int mSize;
    00802
    00803     AllocatorType mAllocator;
    00804
    00809     inline void IsSane()
    00810     {
    00811         FBX_ASSERT((mRoot == 0) || (mRoot->mColor == RecordType::eBlack));
    00812         FBX_ASSERT(((mRoot == 0) && (mSize == 0)) || (mRoot != 0) && (mSize != 0));
    00813         IsSubTreeSane(mRoot);
    00814
    00815         ComputeBlackDepth(mRoot, 0);
    00816
    00817         RecordType* lNode = mRoot;
    00818         unsigned int lLeafBlackDepth = 0;
    00819         while (lNode)
    00820         {
    00821             if (lNode->mLeftChild == 0)
    00822             {
    00823                 lLeafBlackDepth = lNode->mBlackDepth + ((lNode->mColor == RecordType::eBlack) ? 1 : 0);
    00824             }
    00825
    00826             lNode = lNode->mLeftChild;
    00827         }
    00828
    00829         CheckLeavesBlackDepth(mRoot, lLeafBlackDepth);
    00830     }
    00831
    00832     inline void IsSubTreeSane(const RecordType* pNode) const
    00833     {
    00834         KEY_COMPARE_FUNCTOR lCompareKeys;
    00835
    00836         if (pNode)
    00837         {
    00838             FBX_ASSERT(pNode != pNode->mParent);
    00839             FBX_ASSERT(pNode != pNode->mLeftChild);
    00840             FBX_ASSERT(pNode != pNode->mRightChild);
    00841
    00842             // Check for two consecutive red nodes
    00843             FBX_ASSERT((pNode->mColor == RecordType::eBlack) ||
    00844                      (pNode->mLeftChild == NULL) ||
    00845                      (pNode->mLeftChild->mColor == RecordType::eBlack));
    00846
    00847             FBX_ASSERT((pNode->mColor == RecordType::eBlack) ||
    00848                      (pNode->mRightChild == NULL) ||
    00849                      (pNode->mRightChild->mColor == RecordType::eBlack));
    00850
    00851             // Check key ordering
    00852             FBX_ASSERT((pNode->mLeftChild == 0 ||
    00853                       lCompareKeys(pNode->GetKey(), pNode->mLeftChild->GetKey()) > 0));
    00854
    00855             FBX_ASSERT((pNode->mRightChild == 0 ||
    00856                       lCompareKeys(pNode->GetKey(), pNode->mRightChild->GetKey()) < 0));
    00857
    00858             IsSubTreeSane(pNode->mLeftChild);
    00859             IsSubTreeSane(pNode->mRightChild);
    00860         }
    00861     }
    00862
    00863     inline void ComputeBlackDepth(RecordType* pNode, unsigned int pDepth)
    00864     {
    00865         if (pNode)
    00866         {
    00867             pNode->mBlackDepth = pDepth;
    00868             if (pNode->mColor == RecordType::eBlack)
    00869             {
    00870                 pDepth++;
    00871             }
    00872
    00873             ComputeBlackDepth(pNode->mLeftChild, pDepth);
    00874             ComputeBlackDepth(pNode->mRightChild, pDepth);
    00875         }
    00876     }
    00877
    00878     inline void CheckLeavesBlackDepth(RecordType* pNode, unsigned int pBlackDepth)
    00879     {
    00880         if (pNode)
    00881         {
    00882             if ((pNode->mLeftChild == 0) || pNode->mRightChild == 0)
    00883             {
    00884                 int lBlackDepth = pNode->mBlackDepth + ((pNode->mColor == RecordType::eBlack) ? 1 : 0);
    00885                 FBX_ASSERT(lBlackDepth == pBlackDepth);
    00886             }
    00887
    00888             CheckLeavesBlackDepth(pNode->mLeftChild, pBlackDepth);
    00889             CheckLeavesBlackDepth(pNode->mRightChild, pBlackDepth);
    00890         }
    00891     }
    00892
    00893     inline RecordType* DuplicateSubTree(const RecordType* pNode)
    00894     {
    00895         RecordType* lNewSubTree = 0;
    00896
    00897         if (pNode)
    00898         {
    00899             void* lBuffer = mAllocator.AllocateRecords();
    00900             lNewSubTree = new(lBuffer) RecordType(*pNode);
    00901             lNewSubTree->mLeftChild = DuplicateSubTree(pNode->mLeftChild);
    00902             lNewSubTree->mRightChild = DuplicateSubTree(pNode->mRightChild);
    00903
    00904             if (lNewSubTree->mLeftChild)
    00905             {
    00906                 lNewSubTree->mLeftChild->mParent = lNewSubTree;
    00907             }
    00908
    00909             if (lNewSubTree->mRightChild)
    00910             {
    00911                 lNewSubTree->mRightChild->mParent = lNewSubTree;
    00912             }
    00913         }
    00914
    00915         return lNewSubTree;
    00916     }
    00917
    00918     inline void FixNodesAfterInsertion(RecordType* pNode)
    00919     {
    00920         RecordType* lNode = pNode;
    00921         bool lDone = false;
    00922
    00923         while (!lDone)
    00924         {
    00925             lDone = true;
    00926
    00927             if (lNode->mParent == 0)
    00928             {
    00929                 lNode->mColor = RecordType::eBlack;
    00930             }
    00931             else if (lNode->mParent->mColor == RecordType::eRed)
    00932             {
    00933                 RecordType* lUncle = 0;
    00934                 if (lNode->mParent == lNode->mParent->mParent->mLeftChild)
    00935                 {
    00936                     lUncle = lNode->mParent->mParent->mRightChild;
    00937                 }
    00938                 else if (lNode->mParent == lNode->mParent->mParent->mRightChild)
    00939                 {
    00940                     lUncle = lNode->mParent->mParent->mLeftChild;
    00941                 }
    00942
    00943                 // since lNode->mParent is red, lNode->mParent->mParent exists
    00944
    00945                 if (lUncle && lUncle->mColor == RecordType::eRed)
    00946                 {
    00947                     lNode->mParent->mColor = RecordType::eBlack;
    00948                     lUncle->mColor = RecordType::eBlack;
    00949                     lNode->mParent->mParent->mColor = RecordType::eRed;
    00950                     lNode = lNode->mParent->mParent;
    00951
    00952                     lDone = false;
    00953                 }
    00954                 else
    00955                 {
    00956                     if ((lNode == lNode->mParent->mRightChild) &&
    00957                         (lNode->mParent == lNode->mParent->mParent->mLeftChild))
    00958                     {
    00959                         LeftRotate(lNode->mParent);
    00960                         lNode = lNode->mLeftChild;
    00961                     }
    00962                     else if ((lNode == lNode->mParent->mLeftChild) &&
    00963                             (lNode->mParent == lNode->mParent->mParent->mRightChild))
    00964                     {
    00965                         RightRotate(lNode->mParent);
    00966                         lNode = lNode->mRightChild;
    00967                     }
    00968
    00969                     lNode->mParent->mColor = RecordType::eBlack;
    00970                     lNode->mParent->mParent->mColor = RecordType::eRed;
    00971                     if ((lNode == lNode->mParent->mLeftChild) &&
    00972                         (lNode->mParent == lNode->mParent->mParent->mLeftChild))
    00973                     {
    00974                         RightRotate(lNode->mParent->mParent);
    00975                     }
    00976                     else
    00977                     {
    00978                         LeftRotate(lNode->mParent->mParent);
    00979                     }
    00980                 }
    00981             }
    00982         }
    00983
    00984         mRoot->mColor = RecordType::eBlack;
    00985     }
    00986
    00987     inline void LeftRotate(RecordType* pNode)
    00988     {
    00989         RecordType* lNode = pNode->mRightChild;
    00990
    00991 #ifdef _DEBUG
    00992         RecordType* A = pNode->mLeftChild;
    00993         RecordType* B = lNode->mLeftChild;
    00994         RecordType* C = lNode->mRightChild;
    00995         RecordType* Z = pNode->mParent;
    00996 #endif
    00997
    00998         pNode->mRightChild = lNode->mLeftChild;
    00999         if (pNode->mRightChild)
    01000         {
    01001             pNode->mRightChild->mParent = pNode;
    01002         }
    01003
    01004         lNode->mParent = pNode->mParent;
    01005         if (pNode->mParent == 0)
    01006         {
    01007             FBX_ASSERT(mRoot == pNode);
    01008             mRoot = lNode;
    01009         }
    01010         else if (pNode == pNode->mParent->mLeftChild)
    01011         {
    01012             pNode->mParent->mLeftChild = lNode;
    01013         }
    01014         else
    01015         {
    01016             pNode->mParent->mRightChild = lNode;
    01017         }
    01018         pNode->mParent = lNode;
    01019         lNode->mLeftChild = pNode;
    01020
    01021         FBX_ASSERT(pNode->mLeftChild == A);
    01022         FBX_ASSERT(pNode->mRightChild == B);
    01023         FBX_ASSERT(pNode->mParent == lNode);
    01024
    01025         FBX_ASSERT(lNode->mLeftChild == pNode);
    01026         FBX_ASSERT(lNode->mRightChild == C);
    01027         FBX_ASSERT(lNode->mParent == Z);
    01028
    01029         FBX_ASSERT(A == 0 || A->mParent == pNode);
    01030         FBX_ASSERT(B == 0 || B->mParent == pNode);
    01031         FBX_ASSERT(C == 0 || C->mParent == lNode);
    01032         FBX_ASSERT(Z == 0 || Z->mLeftChild == lNode || Z->mRightChild == lNode);
    01033     }
    01034
    01035
    01036     inline void RightRotate(RecordType* pNode)
    01037     {
    01038         RecordType* lNode = pNode->mLeftChild;
    01039
    01040 #ifdef _DEBUG
    01041         RecordType* A = lNode->mLeftChild;
    01042         RecordType* B = lNode->mRightChild;
    01043         RecordType* C = pNode->mRightChild;
    01044         RecordType* Z = pNode->mParent;
    01045 #endif
    01046
    01047         pNode->mLeftChild = lNode->mRightChild;
    01048         if (pNode->mLeftChild)
    01049         {
    01050             pNode->mLeftChild->mParent = pNode;
    01051         }
    01052
    01053         lNode->mParent = pNode->mParent;
    01054         if (pNode->mParent == 0)
    01055         {
    01056             FBX_ASSERT(mRoot == pNode);
    01057             mRoot = lNode;
    01058         }
    01059         else if (pNode == pNode->mParent->mRightChild)
    01060         {
    01061             pNode->mParent->mRightChild = lNode;
    01062         }
    01063         else
    01064         {
    01065             pNode->mParent->mLeftChild = lNode;
    01066         }
    01067         pNode->mParent = lNode;
    01068         lNode->mRightChild = pNode;
    01069
    01070         FBX_ASSERT(lNode->mLeftChild == A);
    01071         FBX_ASSERT(lNode->mRightChild == pNode);
    01072         FBX_ASSERT(lNode->mParent == Z);
    01073
    01074         FBX_ASSERT(pNode->mLeftChild == B);
    01075         FBX_ASSERT(pNode->mRightChild == C);
    01076         FBX_ASSERT(pNode->mParent == lNode);
    01077
    01078         FBX_ASSERT(A == 0 || A->mParent == lNode);
    01079         FBX_ASSERT(B == 0 || B->mParent == pNode);
    01080         FBX_ASSERT(C == 0 || C->mParent == pNode);
    01081         FBX_ASSERT(Z == 0 || Z->mLeftChild == lNode || Z->mRightChild == lNode);
    01082     }
    01083
    01084
    01085     inline void RemoveNode(RecordType* pNode)
    01086     {
    01087         if (pNode->mLeftChild == 0)
    01088         {
    01089             if (pNode->mRightChild == 0)
    01090             {
    01091                 if (pNode->mParent)
    01092                 {
    01093                     if (pNode->mParent->mLeftChild == pNode)
    01094                     {
    01095                         pNode->mParent->mLeftChild = 0;
    01096                     }
    01097                     else if (pNode->mParent->mRightChild == pNode)
    01098                     {
    01099                         pNode->mParent->mRightChild = 0;
    01100                     }
    01101                     else
    01102                     {
    01103                         FBX_ASSERT_NOW("Node not found in FbxRedBlackTree");
    01104                     }
    01105                 }
    01106                 else
    01107                 {
    01108                     FBX_ASSERT(mRoot == pNode);
    01109                     mRoot = 0;
    01110                 }
    01111
    01112                 if (pNode->mColor == RecordType::eBlack)
    01113                 {
    01114                     FixNodesAfterRemoval(pNode->mParent, 0);
    01115                 }
    01116             }
    01117             else
    01118             {
    01119                 if (pNode->mParent)
    01120                 {
    01121                     if (pNode->mParent->mLeftChild == pNode)
    01122                     {
    01123                         pNode->mParent->mLeftChild = pNode->mRightChild;
    01124                         pNode->mRightChild->mParent = pNode->mParent;
    01125                     }
    01126                     else if (pNode->mParent->mRightChild == pNode)
    01127                     {
    01128                         pNode->mParent->mRightChild = pNode->mRightChild;
    01129                         pNode->mRightChild->mParent = pNode->mParent;
    01130                     }
    01131                     else
    01132                     {
    01133                         FBX_ASSERT_NOW("Node not found in FbxRedBlackTree");
    01134                     }
    01135                 }
    01136                 else
    01137                 {
    01138                     FBX_ASSERT(mRoot == pNode);
    01139                     mRoot = pNode->mRightChild;
    01140                     pNode->mRightChild->mParent = 0;
    01141                 }
    01142
    01143                 if (pNode->mColor == RecordType::eBlack)
    01144                 {
    01145                     FixNodesAfterRemoval(pNode->mRightChild->mParent, pNode->mRightChild);
    01146                 }
    01147             }
    01148         }
    01149         else
    01150         {
    01151             if (pNode->mRightChild == 0)
    01152             {
    01153                 if (pNode->mParent)
    01154                 {
    01155                     if (pNode->mParent->mLeftChild == pNode)
    01156                     {
    01157                         pNode->mParent->mLeftChild = pNode->mLeftChild;
    01158                         pNode->mLeftChild->mParent = pNode->mParent;
    01159                     }
    01160                     else if (pNode->mParent->mRightChild == pNode)
    01161                     {
    01162                         pNode->mParent->mRightChild = pNode->mLeftChild;
    01163                         pNode->mLeftChild->mParent = pNode->mParent;
    01164                     }
    01165                     else
    01166                     {
    01167                         FBX_ASSERT_NOW("Node not found in FbxRedBlackTree");
    01168                     }
    01169                 }
    01170                 else
    01171                 {
    01172                     FBX_ASSERT(mRoot == pNode);
    01173                     mRoot = pNode->mLeftChild;
    01174                     pNode->mLeftChild->mParent = 0;
    01175                 }
    01176
    01177                 if (pNode->mColor == RecordType::eBlack)
    01178                 {
    01179                     FixNodesAfterRemoval(pNode->mLeftChild->mParent, pNode->mLeftChild);
    01180                 }
    01181             }
    01182             else
    01183             {
    01184                 RecordType* lMinRightNode = pNode->mRightChild->Minimum();
    01185                 RemoveNode(lMinRightNode);
    01186
    01187                 lMinRightNode->mColor = pNode->mColor;
    01188                 ReplaceNode(pNode, lMinRightNode);
    01189             }
    01190         }
    01191
    01192         pNode->mParent = 0;
    01193         pNode->mLeftChild = 0;
    01194         pNode->mRightChild = 0;
    01195     }
    01196
    01197
    01198     inline void ReplaceNode(RecordType* pNodeToReplace, RecordType* pReplacement)
    01199     {
    01200         pReplacement->mParent = pNodeToReplace->mParent;
    01201         if (pNodeToReplace->mParent)
    01202         {
    01203             if (pNodeToReplace->mParent->mLeftChild == pNodeToReplace)
    01204             {
    01205                 pNodeToReplace->mParent->mLeftChild = pReplacement;
    01206             }
    01207             else if (pNodeToReplace->mParent->mRightChild == pNodeToReplace)
    01208             {
    01209                 pNodeToReplace->mParent->mRightChild = pReplacement;
    01210             }
    01211         }
    01212         else
    01213         {
    01214             FBX_ASSERT(mRoot == pNodeToReplace);
    01215             mRoot = pReplacement;
    01216         }
    01217
    01218         pReplacement->mLeftChild = pNodeToReplace->mLeftChild;
    01219         if (pReplacement->mLeftChild)
    01220         {
    01221             pReplacement->mLeftChild->mParent = pReplacement;
    01222         }
    01223
    01224         pReplacement->mRightChild = pNodeToReplace->mRightChild;
    01225         if (pReplacement->mRightChild)
    01226         {
    01227             pReplacement->mRightChild->mParent = pReplacement;
    01228         }
    01229     }
    01230
    01231     inline RecordType* Sibling(const RecordType* pParent, const RecordType* pNode) const
    01232     {
    01233         if (pParent)
    01234         {
    01235             if (pParent->mLeftChild == pNode)
    01236             {
    01237                 return pParent->mRightChild;
    01238             }
    01239             else if (pParent->mRightChild == pNode)
    01240             {
    01241                 return pParent->mLeftChild;
    01242             }
    01243         }
    01244
    01245         return 0;
    01246     }
    01247
    01248     inline bool IsBlack(const RecordType* pNode)
    01249     {
    01250         return ((pNode == 0) || (pNode->mColor == RecordType::eBlack));
    01251     }
    01252
    01253     inline void FixNodesAfterRemoval(RecordType* pParent, RecordType* pNode)
    01254     {
    01255         RecordType* lParent = pParent;
    01256         RecordType* lNode = pNode;
    01257         bool lDone = false;
    01258
    01259         while (!lDone)
    01260         {
    01261             lDone = true;
    01262
    01263             if (!IsBlack(lNode))
    01264             {
    01265                 lNode->mColor = RecordType::eBlack;
    01266             }
    01267             else if (lParent != NULL)
    01268             {
    01269                 RecordType* lSibling = Sibling(lParent, lNode);
    01270
    01271                 if (!IsBlack(lSibling))
    01272                 {
    01273                     lParent->mColor = RecordType::eRed;
    01274                     lSibling->mColor = RecordType::eBlack;
    01275                     if (lNode == lParent->mLeftChild)
    01276                     {
    01277                         LeftRotate(lParent);
    01278                     }
    01279                     else
    01280                     {
    01281                         RightRotate(lParent);
    01282                     }
    01283
    01284                     // update sibling: it may have change after rotation
    01285                     // parent was not affected by this rotation
    01286                     lSibling = Sibling(lParent, lNode);
    01287                 }
    01288
    01289                 /* check this for null sibling */
    01290                 if (lSibling &&
    01291                     IsBlack(lParent) &&
    01292                     IsBlack(lSibling) &&
    01293                     IsBlack(lSibling->mLeftChild) &&
    01294                     IsBlack(lSibling->mRightChild))
    01295                 {
    01296                     lSibling->mColor = RecordType::eRed;
    01297                     lNode = lParent;
    01298                     lParent = lParent->mParent;
    01299                     lDone = false;
    01300                 }
    01301                 else
    01302                 {
    01303                     if (!IsBlack(lParent) &&
    01304                         IsBlack(lSibling) &&
    01305                         ((lSibling == 0) || IsBlack(lSibling->mLeftChild)) &&
    01306                         ((lSibling == 0) || IsBlack(lSibling->mRightChild)))
    01307                     {
    01308                         if (lSibling)
    01309                         {
    01310                             lSibling->mColor = RecordType::eRed;
    01311                         }
    01312                         lParent->mColor = RecordType::eBlack;
    01313                     }
    01314                     else // lSibling != 0
    01315                     {
    01316                         if ((lNode == lParent->mLeftChild) &&
    01317                             IsBlack(lSibling) &&
    01318                             !IsBlack(lSibling->mLeftChild) &&
    01319                             IsBlack(lSibling->mRightChild))
    01320                         {
    01321                             lSibling->mColor = RecordType::eRed;
    01322                             lSibling->mLeftChild->mColor = RecordType::eBlack;
    01323                             RightRotate(lSibling);
    01324                         }
    01325                         else if ((lNode == lParent->mRightChild) &&
    01326                                  IsBlack(lSibling) &&
    01327                                  IsBlack(lSibling->mLeftChild) &&
    01328                                  !IsBlack(lSibling->mRightChild))
    01329                         {
    01330                             lSibling->mColor = RecordType::eRed;
    01331                             lSibling->mRightChild->mColor = RecordType::eBlack;
    01332                             LeftRotate(lSibling);
    01333                         }
    01334
    01335                         // update sibling: it may have change after rotation
    01336                         lSibling = Sibling(lParent, lNode);
    01337                         FBX_ASSERT(lSibling != 0); // lSibling is now
    01338                                                  // the former red
    01339                                                  // child of the
    01340                                                  // former sibling
    01341
    01342                         lSibling->mColor = lParent->mColor;
    01343                         lParent->mColor = RecordType::eBlack;
    01344                         if (lNode == lParent->mLeftChild)
    01345                         {
    01346                             if (lSibling->mRightChild)
    01347                             {
    01348                                 lSibling->mRightChild->mColor = RecordType::eBlack;
    01349                             }
    01350                             LeftRotate(lParent);
    01351                         }
    01352                         else
    01353                         {
    01354                             if (lSibling->mLeftChild)
    01355                             {
    01356                                 lSibling->mLeftChild->mColor = RecordType::eBlack;
    01357                             }
    01358                             RightRotate(lParent);
    01359                         }
    01360                     }
    01361                 }
    01362             }
    01363         }
    01364
    01365         if (mRoot)
    01366         {
    01367             mRoot->mColor = RecordType::eBlack;
    01368         }
    01369     }
    01370
    01371
    01372     inline void ClearSubTree(RecordType* pNode)
    01373     {
    01374         if (pNode)
    01375         {
    01376             ClearSubTree(pNode->mLeftChild);
    01377             ClearSubTree(pNode->mRightChild);
    01378             pNode->~RecordType();
    01379             mAllocator.FreeMemory(pNode);
    01380         }
    01381     }
    01382
    01383     inline int GetSubTreeSize(RecordType* pNode) const
    01384     {
    01385         if (pNode)
    01386         {
    01387             return GetSubTreeSize(pNode->mLeftChild) + GetSubTreeSize(pNode->mRightChild) + 1;
    01388         }
    01389         else
    01390         {
    01391             return 0;
    01392         }
    01393     }
    01394
    01395 };
    01396
    01397 #endif // #ifndef DOXYGEN_SHOULD_SKIP_THIS
    01398
    01401 template <typename T>
    01402 struct FbxLessCompare
    01403 {
    01404     inline int operator()(const T& left, const T& right) const
    01405     {
    01406         return (left < right) ? -1 : ((right < left) ? 1 : 0);
    01407     }
    01408 };
    01409
    01413 template <typename KEY_TYPE,
    01414           typename VALUE_TYPE,
    01415           typename KEY_COMPARE_FUNCTOR = FbxLessCompare<KEY_TYPE>,
    01416           typename ALLOCATOR = FbxBaseAllocator>
    01417 class FbxMap
    01418 {
    01419 #ifndef DOXYGEN_SHOULD_SKIP_THIS
    01420
    01421 protected:
    01423     class FbxKeyValuePair : private FbxPair<const KEY_TYPE, VALUE_TYPE>
    01424     {
    01425     public:
    01426         FbxKeyValuePair(const KEY_TYPE& pFirst, const VALUE_TYPE& pSecond)
    01427             : FbxPair<const KEY_TYPE, VALUE_TYPE>(pFirst, pSecond) {}
    01428
    01429         // Key is always const.
    01430         typedef const KEY_TYPE      KeyType;
    01431         typedef const KEY_TYPE      ConstKeyType;
    01432         typedef VALUE_TYPE          ValueType;
    01433         typedef const VALUE_TYPE    ConstValueType;
    01434
    01435         ConstKeyType & GetKey() const       { return this->mFirst; }
    01436         KeyType & GetKey()                  { return this->mFirst; }
    01437
    01438         ConstValueType& GetValue() const    { return this->mSecond; }
    01439         ValueType& GetValue()               { return this->mSecond; }
    01440     };
    01441
    01442     typedef FbxRedBlackTree<FbxKeyValuePair, KEY_COMPARE_FUNCTOR, ALLOCATOR> StorageType;
    01443     StorageType mTree;
    01444
    01445 #endif // #ifndef DOXYGEN_SHOULD_SKIP_THIS
    01446
    01447 public:
    01448     typedef VALUE_TYPE ValueType;
    01449     typedef KEY_TYPE KeyType;
    01450     typedef typename StorageType::RecordType         RecordType;
    01451     typedef typename StorageType::IteratorType       Iterator;
    01452     typedef typename StorageType::ConstIteratorType  ConstIterator;
    01453
    01455     inline FbxMap() {}
    01459     inline FbxMap(const FbxMap& pMap) : mTree(pMap.mTree) {}
    01461     inline ~FbxMap() {Clear();}
    01462
    01466     inline void Reserve(unsigned int pRecordCount)
    01467     {
    01468         mTree.Reserve(pRecordCount);
    01469     }
    01470
    01472     inline int GetSize() const
    01473     {
    01474         return mTree.GetSize();
    01475     }
    01476
    01483     inline FbxPair<RecordType*, bool> Insert(const KeyType& pKey, const ValueType& pValue)
    01484     {
    01485         return mTree.Insert(FbxKeyValuePair(pKey, pValue));
    01486     }
    01487
    01492     inline int Remove(const KeyType& pKey)
    01493     {
    01494         return mTree.Remove(pKey);
    01495     }
    01496
    01498     inline void Clear()
    01499     {
    01500         mTree.Clear();
    01501     }
    01502
    01504     inline bool Empty() const
    01505     {
    01506         return mTree.Empty();
    01507     }
    01508
    01510     Iterator Begin()
    01511     {
    01512         return Iterator(Minimum());
    01513     }
    01514
    01516     Iterator End()
    01517     {
    01518         return Iterator();
    01519     }
    01520
    01522     ConstIterator Begin() const
    01523     {
    01524         return ConstIterator(Minimum());
    01525     }
    01526
    01528     ConstIterator End() const
    01529     {
    01530         return ConstIterator();
    01531     }
    01532
    01537     inline const RecordType* Find(const KeyType& pKey) const
    01538     {
    01539         return mTree.Find(pKey);
    01540     }
    01541
    01546     inline RecordType* Find(const KeyType& pKey)
    01547     {
    01548         return mTree.Find(pKey);
    01549     }
    01550
    01555     inline const RecordType* UpperBound(const KeyType& pKey) const
    01556     {
    01557         return mTree.UpperBound(pKey);
    01558     }
    01559
    01564     inline RecordType* UpperBound(const KeyType& pKey)
    01565     {
    01566         return mTree.UpperBound(pKey);
    01567     }
    01568
    01574     inline ValueType& operator[](const KeyType& pKey)
    01575     {
    01576         RecordType* lRecord = Find(pKey);
    01577
    01578         if( !lRecord )
    01579         {
    01580             lRecord = Insert(pKey, ValueType()).mFirst;
    01581         }
    01582
    01583         return lRecord->GetValue();
    01584     }
    01585
    01587     inline const RecordType* Minimum() const
    01588     {
    01589         return mTree.Minimum();
    01590     }
    01591
    01593     inline RecordType* Minimum()
    01594     {
    01595         return mTree.Minimum();
    01596     }
    01597
    01599     inline const RecordType* Maximum() const
    01600     {
    01601         return mTree.Maximum();
    01602     }
    01603
    01605     inline RecordType* Maximum()
    01606     {
    01607         return mTree.Maximum();
    01608     }
    01609 };
    01610
    01614 template <typename VALUE_TYPE,
    01615           typename KEY_COMPARE_FUNCTOR = FbxLessCompare<VALUE_TYPE>,
    01616           typename ALLOCATOR = FbxBaseAllocator>
    01617 class FbxSet2
    01618 {
    01619 #ifndef DOXYGEN_SHOULD_SKIP_THIS
    01620 protected:
    01621     class FbxValue
    01622     {
    01623     public:
    01624         inline FbxValue(const VALUE_TYPE& pValue)
    01625             : mValue(pValue) {}
    01626
    01627         // Cannot modify the value in a set, which would change its ordering in the tree
    01628         typedef const VALUE_TYPE KeyType;
    01629         typedef const VALUE_TYPE ConstKeyType;
    01630         typedef const VALUE_TYPE ValueType;
    01631         typedef const VALUE_TYPE ConstValueType;
    01632
    01633         inline KeyType& GetKey() const      { return mValue; }
    01634         inline ConstKeyType& GetKey()       { return mValue; }
    01635
    01636         inline ValueType& GetValue() const  { return mValue; }
    01637         inline ConstValueType& GetValue()   { return mValue; }
    01638
    01639     protected:
    01640         ValueType mValue;
    01641
    01642     private:
    01643         FbxValue& operator=(const FbxValue&);
    01644     };
    01645
    01646     typedef FbxRedBlackTree<FbxValue, KEY_COMPARE_FUNCTOR, ALLOCATOR> StorageType;
    01647     StorageType mTree;
    01648 #endif // #ifndef DOXYGEN_SHOULD_SKIP_THIS
    01649
    01650
    01651 public:
    01652     typedef VALUE_TYPE ValueType;
    01653     typedef typename StorageType::RecordType        RecordType;
    01654     typedef typename StorageType::IteratorType      Iterator;
    01655     typedef typename StorageType::ConstIteratorType ConstIterator;
    01656
    01658     inline FbxSet2() {}
    01660     inline FbxSet2(const FbxSet2& pSet) : mTree(pSet.mTree) {}
    01662     inline ~FbxSet2() {Clear();}
    01663
    01667     inline void Reserve(unsigned int pRecordCount)
    01668     {
    01669         mTree.Reserve(pRecordCount);
    01670     }
    01671
    01673     inline int GetSize() const
    01674     {
    01675         return mTree.GetSize();
    01676     }
    01677
    01683     inline FbxPair<RecordType*, bool> Insert(const ValueType& pValue)
    01684     {
    01685         return mTree.Insert(FbxValue(pValue));
    01686     }
    01687
    01692     inline int Remove(const ValueType& pValue)
    01693     {
    01694         return mTree.Remove(pValue);
    01695     }
    01696
    01698     inline void Clear()
    01699     {
    01700         mTree.Clear();
    01701     }
    01702
    01704     inline bool Empty() const
    01705     {
    01706         return mTree.Empty();
    01707     }
    01708
    01710     Iterator Begin()
    01711     {
    01712         return Iterator(Minimum());
    01713     }
    01714
    01716     Iterator End()
    01717     {
    01718         return Iterator();
    01719     }
    01720
    01722     ConstIterator Begin() const
    01723     {
    01724         return ConstIterator(Minimum());
    01725     }
    01726
    01728     ConstIterator End() const
    01729     {
    01730         return ConstIterator();
    01731     }
    01732
    01737     inline const RecordType* Find(const ValueType& pValue) const
    01738     {
    01739         return mTree.Find(pValue);
    01740     }
    01741
    01746     inline RecordType* Find(const ValueType& pValue)
    01747     {
    01748         return mTree.Find(pValue);
    01749     }
    01750
    01752     inline const RecordType* Minimum() const
    01753     {
    01754         return mTree.Minimum();
    01755     }
    01756
    01758     inline RecordType* Minimum()
    01759     {
    01760         return mTree.Minimum();
    01761     }
    01762
    01764     inline const RecordType* Maximum() const
    01765     {
    01766         return mTree.Maximum();
    01767     }
    01768
    01770     inline RecordType* Maximum()
    01771     {
    01772         return mTree.Maximum();
    01773     }
    01774
    01776     inline bool operator==(const FbxSet2<VALUE_TYPE, KEY_COMPARE_FUNCTOR, ALLOCATOR>& pOther) const
    01777     {
    01778         return (this == &pOther) || (mTree == pOther.mTree);
    01779     }
    01780
    01782     inline bool operator != (const FbxSet2<VALUE_TYPE, KEY_COMPARE_FUNCTOR, ALLOCATOR>& pOther) const
    01783     {
    01784         return !(*this == pOther);
    01785     }
    01786
    01791     inline FbxSet2 Intersect(const FbxSet2& pOther) const
    01792     {
    01793         FbxSet2 lReturn;
    01794         ConstIterator lBegin = Begin();
    01795         for (; lBegin != End(); ++lBegin)
    01796         {
    01797             if (pOther.Find(lBegin->GetValue()) != NULL)
    01798                 lReturn.Insert(lBegin->GetValue());
    01799         }
    01800         return lReturn;
    01801     }
    01802
    01807     inline FbxSet2 Union(const FbxSet2& pOther) const
    01808     {
    01809         FbxSet2 lReturn(*this);
    01810         ConstIterator lBegin = pOther.Begin();
    01811         for (; lBegin != End(); ++lBegin)
    01812         {
    01813             if (Find(lBegin->GetValue()) == NULL)
    01814                 lReturn.Insert(lBegin->GetValue());
    01815         }
    01816         return lReturn;
    01817     }
    01818
    01819 };
    01820
    01821 #include <fbxsdk/fbxsdk_nsend.h>
    01822
    01823 #endif /* _FBXSDK_CORE_BASE_MAP_H_ */