FBX SDK Reference Guide: kmap.h Source File
00001 #ifndef _FBXSDK_KMAP_H_
00002 #define _FBXSDK_KMAP_H_
00003 
00004 
00005 /**************************************************************************************
00006 
00007  Copyright © 2001 - 2008 Autodesk, Inc. and/or its licensors.
00008  All Rights Reserved.
00009 
00010  The coded instructions, statements, computer programs, and/or related material 
00011  (collectively the "Data") in these files contain unpublished information 
00012  proprietary to Autodesk, Inc. and/or its licensors, which is protected by 
00013  Canada and United States of America federal copyright law and by international 
00014  treaties. 
00015  
00016  The Data may not be disclosed or distributed to third parties, in whole or in
00017  part, without the prior written consent of Autodesk, Inc. ("Autodesk").
00018 
00019  THE DATA IS PROVIDED "AS IS" AND WITHOUT WARRANTY.
00020  ALL WARRANTIES ARE EXPRESSLY EXCLUDED AND DISCLAIMED. AUTODESK MAKES NO
00021  WARRANTY OF ANY KIND WITH RESPECT TO THE DATA, EXPRESS, IMPLIED OR ARISING
00022  BY CUSTOM OR TRADE USAGE, AND DISCLAIMS ANY IMPLIED WARRANTIES OF TITLE, 
00023  NON-INFRINGEMENT, MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE OR USE. 
00024  WITHOUT LIMITING THE FOREGOING, AUTODESK DOES NOT WARRANT THAT THE OPERATION
00025  OF THE DATA WILL BE UNINTERRUPTED OR ERROR FREE. 
00026  
00027  IN NO EVENT SHALL AUTODESK, ITS AFFILIATES, PARENT COMPANIES, LICENSORS
00028  OR SUPPLIERS ("AUTODESK GROUP") BE LIABLE FOR ANY LOSSES, DAMAGES OR EXPENSES
00029  OF ANY KIND (INCLUDING WITHOUT LIMITATION PUNITIVE OR MULTIPLE DAMAGES OR OTHER
00030  SPECIAL, DIRECT, INDIRECT, EXEMPLARY, INCIDENTAL, LOSS OF PROFITS, REVENUE
00031  OR DATA, COST OF COVER OR CONSEQUENTIAL LOSSES OR DAMAGES OF ANY KIND),
00032  HOWEVER CAUSED, AND REGARDLESS OF THE THEORY OF LIABILITY, WHETHER DERIVED
00033  FROM CONTRACT, TORT (INCLUDING, BUT NOT LIMITED TO, NEGLIGENCE), OR OTHERWISE,
00034  ARISING OUT OF OR RELATING TO THE DATA OR ITS USE OR ANY OTHER PERFORMANCE,
00035  WHETHER OR NOT AUTODESK HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH LOSS
00036  OR DAMAGE. 
00037 
00038 **************************************************************************************/
00039 #include <kaydaradef.h>
00040 #ifndef KBASELIB_DLL
00041     #define KBASELIB_DLL K_DLLEXPORT
00042 #endif
00043 #include <kbaselib_h.h>
00044 
00045 #include <klib/kpair.h>
00046 #include <klib/kcontainerallocators.h>
00047 #include <klib/kdebug.h>
00048 
00049 #include <new>
00050 
00051 #include <kbaselib_nsbegin.h>
00052 /*************************************************************************
00053  * class KRedBlackTree
00054  *
00055  * Implements an efficient ordered data storage.
00056  *
00057  *************************************************************************/
00058 
00059 /* Examples of KEY_COMPARE_FUNCTOR class
00060 
00061    with KEY_TYPE = int
00062     class IntCompare {
00063         inline int operator()(int pKeyA, int pKeyB) const
00064         {
00065             return (pKeyA < pKeyB) ? -1 : ((pKeyB < pKeyA) ? 1 : 0);
00066         }
00067     };
00068 
00069    with KEY_TYPE = Class
00070     class ClassCompare {
00071         inline int operator()(Class const& pKeyA, Class const& pKeyB) const
00072         {
00073             return (pKeyA < pKeyB) ? -1 : ((pKeyB < pKeyA) ? 1 : 0);
00074         }
00075     };
00076 
00077    with KEY_TYPE = char*
00078     class StrCompare {
00079         inline int operator()(char const* pKeyA, char const* pKeyB) const
00080         {
00081             return strcmp(pKeyA, pKeyB);
00082         }
00083     };
00084 
00085 */
00086 
00087 template <typename RecordType>    class RedBack_ConstIteratorType;
00088 template <typename RecordType>    class RedBack_IteratorType;
00089 
00090 template <typename RecordType>
00091 class RedBack_IteratorType
00092 {
00093 public:
00094     RedBack_IteratorType() : mRecord(0) {}
00095     RedBack_IteratorType(RecordType* pRecord) : mRecord(pRecord) {}
00096     RedBack_IteratorType(RedBack_IteratorType<RecordType> const& pV) : mRecord(pV.mRecord) {}
00097 
00098     // prefix ++
00099     RedBack_IteratorType const& operator++()
00100     {
00101         K_ASSERT( mRecord != NULL );
00102 
00103         mRecord = mRecord->Successor();
00104 
00105         return *this;
00106     }
00107 
00108     // postfix ++
00109     RedBack_IteratorType operator++(int)
00110     {
00111         RedBack_IteratorType t(*this);
00112         operator++();
00113         return t;
00114     }
00115 
00116     // prefix --
00117     RedBack_IteratorType const& operator--()
00118     {
00119         K_ASSERT( mRecord );
00120 
00121         RecordType* lRecord = mRecord->Predecessor();
00122         mRecord = lRecord;
00123         return *this;
00124     }
00125 
00126     // postfix --
00127     RedBack_IteratorType operator--(int)
00128     {
00129         RedBack_IteratorType t(*this);
00130         operator--();
00131         return t;
00132     }
00133 
00134     RecordType const& operator*() const
00135     {
00136         K_ASSERT( mRecord );
00137 
00138         return *mRecord;
00139     }
00140 
00141     RecordType & operator*()
00142     {
00143         K_ASSERT( mRecord );
00144 
00145         return *mRecord;
00146     }
00147 
00148     RecordType const* operator->() const
00149     {
00150         K_ASSERT( mRecord );
00151 
00152         return mRecord;
00153     }
00154 
00155     RecordType* operator->()
00156     {
00157         K_ASSERT( mRecord );
00158 
00159         return mRecord;
00160     }
00161 
00162     inline bool operator==(const RedBack_IteratorType& pOther) const
00163     {
00164         return mRecord == pOther.mRecord;
00165     }
00166 
00167     inline bool operator !=(const RedBack_IteratorType& pOther) const
00168     {
00169         return mRecord != pOther.mRecord;
00170     }
00171 
00172 protected:
00173     friend class RedBack_ConstIteratorType<RecordType>;
00174 
00175     RecordType* mRecord;
00176 };
00177 
00178 template <typename RecordType>
00179 class RedBack_ConstIteratorType
00180 {
00181 public:
00182     RedBack_ConstIteratorType() : mRecord(0) {}
00183     RedBack_ConstIteratorType(const RecordType* pRecord) : mRecord(pRecord) {}
00184     RedBack_ConstIteratorType(RedBack_IteratorType<RecordType> const& pV) : mRecord(pV.mRecord) {}
00185     RedBack_ConstIteratorType(RedBack_ConstIteratorType<RecordType> const& pV) : mRecord(pV.mRecord) {}
00186 
00187     // prefix ++
00188     RedBack_ConstIteratorType const& operator++()
00189     {
00190         K_ASSERT( mRecord != NULL );
00191 
00192         mRecord = mRecord->Successor();
00193 
00194         return *this;
00195     }
00196 
00197     // postfix ++
00198     RedBack_ConstIteratorType operator++(int)
00199     {
00200         RedBack_ConstIteratorType t(*this);
00201         operator++();
00202         return t;
00203     }
00204 
00205     // prefix --
00206     RedBack_ConstIteratorType const& operator--()
00207     {
00208         K_ASSERT( mRecord );
00209 
00210         RecordType const* lRecord = mRecord->Predecessor();
00211         mRecord = lRecord;
00212         return *this;
00213     }
00214 
00215     // postfix --
00216     RedBack_ConstIteratorType operator--(int)
00217     {
00218         RedBack_ConstIteratorType t(*this);
00219         operator--();
00220         return t;
00221     }
00222 
00223     RecordType const& operator*() const
00224     {
00225         K_ASSERT( mRecord );
00226 
00227         return *mRecord;
00228     }
00229 
00230     RecordType const& operator*()
00231     {
00232         K_ASSERT( mRecord );
00233 
00234         return *mRecord;
00235     }
00236 
00237     RecordType const* operator->() const
00238     {
00239         K_ASSERT( mRecord );
00240 
00241         return mRecord;
00242     }
00243 
00244     RecordType const* operator->()
00245     {
00246         K_ASSERT( mRecord );
00247 
00248         return mRecord;
00249     }
00250 
00251     inline bool operator==(const RedBack_ConstIteratorType& pOther) const
00252     {
00253         return mRecord == pOther.mRecord;
00254     }
00255 
00256     inline bool operator !=(const RedBack_ConstIteratorType& pOther) const
00257     {
00258         return mRecord != pOther.mRecord;
00259     }
00260 
00261 protected:
00262     friend class RedBack_IteratorType<RecordType>;
00263 
00264     RecordType const* mRecord;
00265 };
00266 
00267 template <typename DATA_TYPE,
00268           typename KEY_COMPARE_FUNCTOR,
00269           typename ALLOCATOR>
00270 class  KRedBlackTree
00271 {
00272 public:
00273     typedef DATA_TYPE DataType;
00274     typedef typename DATA_TYPE::KeyType         KeyType;
00275     typedef typename DATA_TYPE::ConstKeyType    ConstKeyType;
00276     typedef typename DATA_TYPE::ValueType       ValueType;
00277     typedef typename DATA_TYPE::ConstValueType  ConstValueType;
00278     typedef ALLOCATOR AllocatorType;
00279 
00284     class RecordType
00285     {
00286     public:
00287         inline ConstKeyType& GetKey() const { return mData.GetKey(); }
00288         inline ConstValueType& GetValue() const { return mData.GetValue(); }
00289         inline ValueType& GetValue() { return mData.GetValue(); }
00290 
00291         inline RecordType const* Minimum() const
00292         {
00293             RecordType const* lParent = 0;
00294             RecordType const* lNode = this;
00295             while (lNode != 0)
00296             {
00297                 lParent = lNode;
00298                 lNode = lNode->mLeftChild;
00299             }
00300 
00301             return lParent;
00302         }
00303 
00304         inline RecordType* Minimum()
00305         {
00306             RecordType* lParent = 0;
00307             RecordType* lNode = this;
00308             while (lNode != 0)
00309             {
00310                 lParent = lNode;
00311                 lNode = lNode->mLeftChild;
00312             }
00313 
00314             return lParent;
00315         }
00316 
00317         inline RecordType const* Maximum() const
00318         {
00319             RecordType const* lParent = 0;
00320             RecordType const* lNode = this;
00321             while (lNode != 0)
00322             {
00323                 lParent = lNode;
00324                 lNode = lNode->mRightChild;
00325             }
00326 
00327             return lParent;
00328         }
00329 
00330         inline RecordType* Maximum()
00331         {
00332             RecordType* lParent = 0;
00333             RecordType* lNode = this;
00334             while (lNode != 0)
00335             {
00336                 lParent = lNode;
00337                 lNode = lNode->mRightChild;
00338             }
00339 
00340             return lParent;
00341         }
00342 
00343         inline RecordType const* Predecessor() const
00344         {
00345             if (mLeftChild)
00346             {
00347                 return mLeftChild->Maximum();
00348             }
00349             else
00350             {
00351                 RecordType const* lParent = mParent;
00352                 RecordType const* lNode = this;
00353 
00354                 while (lParent && lParent->mLefttChild == lNode)
00355                 {
00356                     lNode = lParent;
00357                     lParent = lParent->mParent;
00358                 }
00359 
00360                 return lParent;
00361             }
00362         }
00363 
00364         inline RecordType* Predecessor()
00365         {
00366             if (mLeftChild)
00367             {
00368                 return mLeftChild->Maximum();
00369             }
00370             else
00371             {
00372                 RecordType* lParent = mParent;
00373                 RecordType* lNode = this;
00374 
00375                 while (lParent && lParent->mLeftChild == lNode)
00376                 {
00377                     lNode = lParent;
00378                     lParent = lParent->mParent;
00379                 }
00380 
00381                 return lParent;
00382             }
00383         }
00384 
00385         inline RecordType const* Successor() const
00386         {
00387             if (mRightChild)
00388             {
00389                 return mRightChild->Minimum();
00390             }
00391             else
00392             {
00393                 RecordType const* lParent = mParent;
00394                 RecordType const* lNode = this;
00395 
00396                 while (lParent && lParent->mRightChild == lNode)
00397                 {
00398                     lNode = lParent;
00399                     lParent = lParent->mParent;
00400                 }
00401 
00402                 return lParent;
00403             }
00404         }
00405 
00406         inline RecordType* Successor()
00407         {
00408             if (mRightChild)
00409             {
00410                 return mRightChild->Minimum();
00411             }
00412             else
00413             {
00414                 RecordType* lParent = mParent;
00415                 RecordType* lNode = this;
00416 
00417                 while (lParent && lParent->mRightChild == lNode)
00418                 {
00419                     lNode = lParent;
00420                     lParent = lParent->mParent;
00421                 }
00422 
00423                 return lParent;
00424             }
00425         }
00426 
00427         inline int GetBlackDepth() const { return mBlackDepth; }
00428 
00429     private:
00430         enum { eRed, eBlack };
00431 
00432         inline RecordType(DataType const& pData)
00433             : mData(pData)
00434             , mParent(0)
00435             , mLeftChild(0)
00436             , mRightChild(0)
00437             , mColor(eRed)
00438             , mBlackDepth(0)
00439         {
00440         }
00441 
00442         inline RecordType(RecordType const& pRecordType)
00443             : mData(pRecordType.mData)
00444             , mParent(0)
00445             , mLeftChild(0)
00446             , mRightChild(0)
00447             , mColor(pRecordType.mColor)
00448             , mBlackDepth(pRecordType.mBlackDepth)
00449         {
00450         }
00451 
00452         DataType mData;
00453 
00454         friend class KRedBlackTree;
00455 
00456         RecordType* mParent;
00457         RecordType* mLeftChild;
00458         RecordType* mRightChild;
00459         unsigned int mColor:2;
00460         unsigned int mBlackDepth:30;
00461 
00462 #if defined(KARCH_DEV_MSC) // Microsoft compiler
00463     #if (_MSC_VER <= 1200) // VC6
00464         friend  KRedBlackTree<DATA_TYPE, KEY_COMPARE_FUNCTOR, ALLOCATOR>;
00465     #endif
00466 #endif
00467     };
00468 
00469 public:
00470     typedef RedBack_ConstIteratorType<RecordType>  ConstIteratorType;
00471     typedef RedBack_IteratorType<RecordType>       IteratorType;
00472 
00473 public:
00474     inline KRedBlackTree() : mRoot(0), mSize(0), mAllocator(sizeof(RecordType)) {}
00475     inline KRedBlackTree(KRedBlackTree const& pTree) : mRoot(0), mSize(0), mAllocator(sizeof(RecordType)) { operator=(pTree); }
00476     inline ~KRedBlackTree() { Clear(); }
00477 
00480     inline KRedBlackTree& operator=(KRedBlackTree const& pTree)
00481     {
00482         if( this != &pTree )
00483         {
00484             Clear();
00485 
00486             mAllocator = pTree.mAllocator;
00487 
00488             if( pTree.mRoot )
00489             {
00490                 void* lBuffer = mAllocator.AllocateRecords();
00491                 #if ( defined(MEMORY_DEBUG) && defined(_DEBUG) && defined(KARCH_ENV_WIN32))
00492                     #pragma push_macro("new")
00493                     #undef new
00494                 #endif
00495                 mRoot = new(lBuffer) RecordType(*(pTree.mRoot));
00496                 #if ( defined(MEMORY_DEBUG) && defined(_DEBUG) && defined(KARCH_ENV_WIN32))
00497                     #pragma pop_macro("new")
00498                 #endif
00499                 mRoot->mLeftChild = DuplicateSubTree(pTree.mRoot->mLeftChild);
00500                 mRoot->mRightChild = DuplicateSubTree(pTree.mRoot->mRightChild);
00501 
00502                 if (mRoot->mLeftChild)
00503                 {
00504                     mRoot->mLeftChild->mParent = mRoot;
00505                 }
00506 
00507                 if (mRoot->mRightChild)
00508                 {
00509                     mRoot->mRightChild->mParent = mRoot;
00510                 }
00511             }
00512             else
00513             {
00514                 K_ASSERT( pTree.mSize == 0 );
00515                 K_ASSERT( mRoot == 0 );
00516             }
00517 
00518             mSize = pTree.mSize;
00519         }
00520 
00521         return *this;
00522     }
00523 
00524     inline bool operator==(KRedBlackTree const& pTree) const
00525     {
00526         // Check a few quick shortcuts
00527         if( this == &pTree )
00528             return true;
00529 
00530         if( GetSize() != pTree.GetSize() )
00531             return false;
00532 
00533         // Iterator through all nodes; if we reach the end of both iterators at the same
00534         // time then we have two iterators that match.
00535         ConstIteratorType End;
00536         ConstIteratorType Iter1(Minimum());
00537         ConstIteratorType Iter2(pTree.Minimum());
00538 
00539         while( (Iter1 != End) && (Iter2 != End) &&
00540                (Iter1->GetKey() == Iter2->GetKey()) &&
00541                (Iter1->GetValue() == Iter2->GetValue()) )
00542         {
00543             ++Iter1;
00544             ++Iter2;
00545         }
00546 
00547         return Iter1 == End && Iter2 == End;
00548     }
00549 
00552     inline void Reserve(unsigned int pRecordCount)
00553     {
00554         mAllocator.Reserve(pRecordCount);
00555     }
00556 
00560     inline int GetSize() const { return mSize; }
00561 
00562     inline bool Empty() const { return mSize == 0; }
00563 
00569     inline KPair<RecordType*, bool> Insert(DataType const& pData)
00570     {
00571         KEY_COMPARE_FUNCTOR lCompareKeys;
00572         bool lResult = false;
00573         RecordType* lParent = 0;
00574         RecordType* lNode = mRoot;
00575         while (lNode != 0)
00576         {
00577             KeyType const& lNodeKey = lNode->GetKey();
00578             KeyType const& lDataKey = pData.GetKey();
00579 
00580             if (lCompareKeys(lNodeKey, lDataKey) < 0)
00581             {
00582                 lParent = lNode;
00583                 lNode = lNode->mRightChild;
00584             }
00585             else if (lCompareKeys(lNodeKey, lDataKey) > 0)
00586             {
00587                 lParent = lNode;
00588                 lNode = lNode->mLeftChild;
00589             }
00590             else
00591             {
00592                 break;
00593             }
00594         }
00595 
00596         if (lNode == 0)
00597         {
00598             void* lBuffer = mAllocator.AllocateRecords();
00599             #if ( defined(MEMORY_DEBUG) && defined(_DEBUG) && defined(KARCH_ENV_WIN32))
00600                 #pragma push_macro("new")
00601                 #undef new
00602             #endif
00603             lNode = new(lBuffer) RecordType(pData);
00604             #if ( defined(MEMORY_DEBUG) && defined(_DEBUG) && defined(KARCH_ENV_WIN32))
00605                 #pragma pop_macro("new")
00606             #endif
00607             mSize++;
00608 
00609             #if ( !defined(MEMORY_DEBUG) && defined(_DEBUG) && defined(KARCH_ENV_WIN32))
00610                 K_ASSERT(lNode == lBuffer);
00611             #endif
00612 
00613             if (lParent)
00614             {
00615                 if (lCompareKeys(lParent->GetKey(), pData.GetKey()) < 0)
00616                 {
00617                     K_ASSERT(lParent->mRightChild == 0);
00618                     lParent->mRightChild = lNode;
00619                     lNode->mParent = lParent;
00620                 }
00621                 else
00622                 {
00623                     K_ASSERT(lParent->mLeftChild == 0);
00624                     lParent->mLeftChild = lNode;
00625                     lNode->mParent = lParent;
00626                 }
00627             }
00628             else
00629             {
00630                 mRoot = lNode;
00631             }
00632 
00633             // Fix red black tree property
00634             FixNodesAfterInsertion(lNode);
00635 
00636             lResult = true;
00637         }
00638 
00639 #ifdef SANITY_CHECK
00640         IsSane();
00641 #endif
00642 
00643         return KPair<RecordType*, bool>(lNode, lResult);
00644     }
00645 
00649     inline bool Remove(KeyType const& pKey)
00650     {
00651         KEY_COMPARE_FUNCTOR lCompareKeys;
00652         bool lResult = false;
00653         RecordType* lNode = mRoot;
00654         while (lNode != 0)
00655         {
00656             if (lCompareKeys(lNode->GetKey(), pKey) < 0)
00657             {
00658                 lNode = lNode->mRightChild;
00659             }
00660             else if (lCompareKeys(lNode->GetKey(), pKey) > 0)
00661             {
00662                 lNode = lNode->mLeftChild;
00663             }
00664             else
00665             {
00666                 break;
00667             }
00668         }
00669 
00670         if (lNode)
00671         {
00672             RemoveNode(lNode);
00673             mSize--;
00674             lNode->~RecordType();
00675             mAllocator.FreeMemory(lNode);
00676 
00677             lResult = true;
00678         }
00679 
00680 #ifdef SANITY_CHECK
00681         IsSane();
00682 #endif
00683 
00684         return lResult;
00685     }
00686 
00689     inline void Clear()
00690     {
00691         if (mRoot)
00692         {
00693             ClearSubTree(mRoot->mLeftChild);
00694             ClearSubTree(mRoot->mRightChild);
00695             mRoot->~RecordType();
00696             mAllocator.FreeMemory(mRoot);
00697             mRoot = 0;
00698             mSize = 0;
00699         }
00700     }
00701 
00705     inline RecordType const* Minimum() const
00706     {
00707         if (0 != mRoot)
00708         {
00709             return mRoot->Minimum();
00710         }
00711         else
00712         {
00713             return 0;
00714         }
00715     }
00716 
00720     inline RecordType* Minimum()
00721     {
00722         if (0 != mRoot)
00723         {
00724             return mRoot->Minimum();
00725         }
00726         else
00727         {
00728             return 0;
00729         }
00730     }
00731 
00735     inline RecordType const* Maximum() const
00736     {
00737         if (0 != mRoot)
00738         {
00739             return mRoot->Maximum();
00740         }
00741         else
00742         {
00743             return 0;
00744         }
00745     }
00746 
00750     inline RecordType* Maximum()
00751     {
00752         if (0 != mRoot)
00753         {
00754             return mRoot->Maximum();
00755         }
00756         else
00757         {
00758             return 0;
00759         }
00760     }
00761 
00766     inline RecordType const* Find(KeyType const& pKey) const
00767     {
00768         KEY_COMPARE_FUNCTOR lCompareKeys;
00769         RecordType const* lNode = mRoot;
00770         while (lNode != 0)
00771         {
00772             if (lCompareKeys(lNode->GetKey(), pKey) < 0)
00773             {
00774                 lNode = lNode->mRightChild;
00775             }
00776             else if (lCompareKeys(lNode->GetKey(), pKey) > 0)
00777             {
00778                 lNode = lNode->mLeftChild;
00779             }
00780             else
00781             {
00782                 break;
00783             }
00784         }
00785 
00786         return lNode;
00787     }
00788 
00793     inline RecordType* Find(KeyType const& pKey)
00794     {
00795         KEY_COMPARE_FUNCTOR lCompareKeys;
00796         RecordType* lNode = mRoot;
00797         while (lNode != 0)
00798         {
00799             if (lCompareKeys(lNode->GetKey(), pKey) < 0)
00800             {
00801                 lNode = lNode->mRightChild;
00802             }
00803             else if (lCompareKeys(lNode->GetKey(), pKey) > 0)
00804             {
00805                 lNode = lNode->mLeftChild;
00806             }
00807             else
00808             {
00809                 break;
00810             }
00811         }
00812 
00813         return lNode;
00814     }
00815 
00820     inline RecordType const* UpperBound(KeyType const& pKey) const
00821     {
00822         KEY_COMPARE_FUNCTOR lCompareKeys;
00823         RecordType const* lNode = mRoot;
00824         RecordType const* lCandidate = 0;
00825         while (lNode != 0)
00826         {
00827             if (lCompareKeys(lNode->GetKey(), pKey) <= 0)
00828             {
00829                 lNode = lNode->mRightChild;
00830             }
00831             else if (lCompareKeys(lNode->GetKey(), pKey) > 0)
00832             {
00833                 lCandidate = lNode;
00834                 lNode = lNode->mLeftChild;
00835             }
00836         }
00837         
00838         return lCandidate;
00839     }
00840 
00845     inline RecordType* UpperBound(KeyType const& pKey)
00846     {
00847         KEY_COMPARE_FUNCTOR lCompareKeys;
00848         RecordType* lNode = mRoot;
00849         RecordType* lCandidate = 0;
00850         while (lNode != 0)
00851         {
00852             if (lCompareKeys(lNode->GetKey(), pKey) <= 0)
00853             {
00854                 lNode = lNode->mRightChild;
00855             }
00856             else if (lCompareKeys(lNode->GetKey(), pKey) > 0)
00857             {
00858                 lCandidate = lNode;
00859                 lNode = lNode->mLeftChild;
00860             }
00861         }
00862         
00863         return lCandidate;
00864     }
00865 
00866 protected:
00867     RecordType* mRoot;
00868     int mSize;
00869 
00870     AllocatorType mAllocator;
00871 
00876     inline void IsSane()
00877     {
00878         K_ASSERT((mRoot == 0) || (mRoot->mColor == RecordType::eBlack));
00879         K_ASSERT(((mRoot == 0) && (mSize == 0)) || (mRoot != 0) && (mSize != 0));
00880         IsSubTreeSane(mRoot);
00881 
00882         ComputeBlackDepth(mRoot, 0);
00883 
00884         RecordType* lNode = mRoot;
00885         unsigned int lLeafBlackDepth = 0;
00886         while (lNode)
00887         {
00888             if (lNode->mLeftChild == 0)
00889             {
00890                 lLeafBlackDepth = lNode->mBlackDepth + ((lNode->mColor == RecordType::eBlack) ? 1 : 0);
00891             }
00892 
00893             lNode = lNode->mLeftChild;
00894         }
00895 
00896         CheckLeavesBlackDepth(mRoot, lLeafBlackDepth);
00897     }
00898 
00899     inline void IsSubTreeSane(RecordType const* pNode) const
00900     {
00901         KEY_COMPARE_FUNCTOR lCompareKeys;
00902 
00903         if (pNode)
00904         {
00905             K_ASSERT(pNode != pNode->mParent);
00906             K_ASSERT(pNode != pNode->mLeftChild);
00907             K_ASSERT(pNode != pNode->mRightChild);
00908 
00909             // Check for two consecutive red nodes
00910             K_ASSERT((pNode->mColor == RecordType::eBlack) ||
00911                      (pNode->mLeftChild == NULL) ||
00912                      (pNode->mLeftChild->mColor == RecordType::eBlack));
00913 
00914             K_ASSERT((pNode->mColor == RecordType::eBlack) ||
00915                      (pNode->mRightChild == NULL) ||
00916                      (pNode->mRightChild->mColor == RecordType::eBlack));
00917 
00918             // Check key ordering
00919             K_ASSERT((pNode->mLeftChild == 0 ||
00920                       lCompareKeys(pNode->GetKey(), pNode->mLeftChild->GetKey()) > 0));
00921 
00922             K_ASSERT((pNode->mRightChild == 0 ||
00923                       lCompareKeys(pNode->GetKey(), pNode->mRightChild->GetKey()) < 0));
00924 
00925             IsSubTreeSane(pNode->mLeftChild);
00926             IsSubTreeSane(pNode->mRightChild);
00927         }
00928     }
00929 
00930     inline void ComputeBlackDepth(RecordType* pNode, unsigned int pDepth)
00931     {
00932         if (pNode)
00933         {
00934             pNode->mBlackDepth = pDepth;
00935             if (pNode->mColor == RecordType::eBlack)
00936             {
00937                 pDepth++;
00938             }
00939 
00940             ComputeBlackDepth(pNode->mLeftChild, pDepth);
00941             ComputeBlackDepth(pNode->mRightChild, pDepth);
00942         }
00943     }
00944 
00945     inline void CheckLeavesBlackDepth(RecordType* pNode, unsigned int pBlackDepth)
00946     {
00947         if (pNode)
00948         {
00949             if ((pNode->mLeftChild == 0) || pNode->mRightChild == 0)
00950             {
00951                 int lBlackDepth = pNode->mBlackDepth + ((pNode->mColor == RecordType::eBlack) ? 1 : 0);
00952                 K_ASSERT(lBlackDepth == pBlackDepth);
00953             }
00954 
00955             CheckLeavesBlackDepth(pNode->mLeftChild, pBlackDepth);
00956             CheckLeavesBlackDepth(pNode->mRightChild, pBlackDepth);
00957         }
00958     }
00959 
00960     inline RecordType* DuplicateSubTree(RecordType const* pNode)
00961     {
00962         RecordType* lNewSubTree = 0;
00963 
00964         if (pNode)
00965         {
00966             void* lBuffer = mAllocator.AllocateRecords();
00967             #if ( defined(MEMORY_DEBUG) && defined(_DEBUG) && defined(KARCH_ENV_WIN32))
00968                 #pragma push_macro("new")
00969                 #undef new
00970             #endif
00971             lNewSubTree = new(lBuffer) RecordType(*pNode);
00972             #if ( defined(MEMORY_DEBUG) && defined(_DEBUG) && defined(KARCH_ENV_WIN32))
00973                 #pragma pop_macro("new")
00974             #endif
00975             lNewSubTree->mLeftChild = DuplicateSubTree(pNode->mLeftChild);
00976             lNewSubTree->mRightChild = DuplicateSubTree(pNode->mRightChild);
00977 
00978             if (lNewSubTree->mLeftChild)
00979             {
00980                 lNewSubTree->mLeftChild->mParent = lNewSubTree;
00981             }
00982 
00983             if (lNewSubTree->mRightChild)
00984             {
00985                 lNewSubTree->mRightChild->mParent = lNewSubTree;
00986             }
00987         }
00988 
00989         return lNewSubTree;
00990     }
00991 
00992     inline void FixNodesAfterInsertion(RecordType* pNode)
00993     {
00994         RecordType* lNode = pNode;
00995         bool lDone = false;
00996 
00997         while (!lDone)
00998         {
00999             lDone = true;
01000 
01001             if (lNode->mParent == 0)
01002             {
01003                 lNode->mColor = RecordType::eBlack;
01004             }
01005             else if (lNode->mParent->mColor == RecordType::eRed)
01006             {
01007                 RecordType* lUncle = 0;
01008                 if (lNode->mParent == lNode->mParent->mParent->mLeftChild)
01009                 {
01010                     lUncle = lNode->mParent->mParent->mRightChild;
01011                 }
01012                 else if (lNode->mParent == lNode->mParent->mParent->mRightChild)
01013                 {
01014                     lUncle = lNode->mParent->mParent->mLeftChild;
01015                 }
01016 
01017                 // since lNode->mParent is red, lNode->mParent->mParent exists
01018 
01019                 if (lUncle && lUncle->mColor == RecordType::eRed)
01020                 {
01021                     lNode->mParent->mColor = RecordType::eBlack;
01022                     lUncle->mColor = RecordType::eBlack;
01023                     lNode->mParent->mParent->mColor = RecordType::eRed;
01024                     lNode = lNode->mParent->mParent;
01025 
01026                     lDone = false;
01027                 }
01028                 else
01029                 {
01030                     if ((lNode == lNode->mParent->mRightChild) &&
01031                         (lNode->mParent == lNode->mParent->mParent->mLeftChild))
01032                     {
01033                         LeftRotate(lNode->mParent);
01034                         lNode = lNode->mLeftChild;
01035                     }
01036                     else if ((lNode == lNode->mParent->mLeftChild) &&
01037                             (lNode->mParent == lNode->mParent->mParent->mRightChild))
01038                     {
01039                         RightRotate(lNode->mParent);
01040                         lNode = lNode->mRightChild;
01041                     }
01042 
01043                     lNode->mParent->mColor = RecordType::eBlack;
01044                     lNode->mParent->mParent->mColor = RecordType::eRed;
01045                     if ((lNode == lNode->mParent->mLeftChild) &&
01046                         (lNode->mParent == lNode->mParent->mParent->mLeftChild))
01047                     {
01048                         RightRotate(lNode->mParent->mParent);
01049                     }
01050                     else
01051                     {
01052                         LeftRotate(lNode->mParent->mParent);
01053                     }
01054                 }
01055             }
01056         }
01057 
01058         mRoot->mColor = RecordType::eBlack;
01059     }
01060 
01061     inline void LeftRotate(RecordType* pNode)
01062     {
01063         RecordType* lNode = pNode->mRightChild;
01064 
01065 #ifdef _DEBUG
01066         RecordType* A = pNode->mLeftChild;
01067         RecordType* B = lNode->mLeftChild;
01068         RecordType* C = lNode->mRightChild;
01069         RecordType* Z = pNode->mParent;
01070 #endif
01071 
01072         pNode->mRightChild = lNode->mLeftChild;
01073         if (pNode->mRightChild)
01074         {
01075             pNode->mRightChild->mParent = pNode;
01076         }
01077 
01078         lNode->mParent = pNode->mParent;
01079         if (pNode->mParent == 0)
01080         {
01081             K_ASSERT(mRoot == pNode);
01082             mRoot = lNode;
01083         }
01084         else if (pNode == pNode->mParent->mLeftChild)
01085         {
01086             pNode->mParent->mLeftChild = lNode;
01087         }
01088         else
01089         {
01090             pNode->mParent->mRightChild = lNode;
01091         }
01092         pNode->mParent = lNode;
01093         lNode->mLeftChild = pNode;
01094 
01095         K_ASSERT(pNode->mLeftChild == A);
01096         K_ASSERT(pNode->mRightChild == B);
01097         K_ASSERT(pNode->mParent == lNode);
01098 
01099         K_ASSERT(lNode->mLeftChild == pNode);
01100         K_ASSERT(lNode->mRightChild == C);
01101         K_ASSERT(lNode->mParent == Z);
01102 
01103         K_ASSERT(A == 0 || A->mParent == pNode);
01104         K_ASSERT(B == 0 || B->mParent == pNode);
01105         K_ASSERT(C == 0 || C->mParent == lNode);
01106         K_ASSERT(Z == 0 || Z->mLeftChild == lNode || Z->mRightChild == lNode);
01107     }
01108 
01109 
01110     inline void RightRotate(RecordType* pNode)
01111     {
01112         RecordType* lNode = pNode->mLeftChild;
01113 
01114 #ifdef _DEBUG
01115         RecordType* A = lNode->mLeftChild;
01116         RecordType* B = lNode->mRightChild;
01117         RecordType* C = pNode->mRightChild;
01118         RecordType* Z = pNode->mParent;
01119 #endif
01120 
01121         pNode->mLeftChild = lNode->mRightChild;
01122         if (pNode->mLeftChild)
01123         {
01124             pNode->mLeftChild->mParent = pNode;
01125         }
01126 
01127         lNode->mParent = pNode->mParent;
01128         if (pNode->mParent == 0)
01129         {
01130             K_ASSERT(mRoot == pNode);
01131             mRoot = lNode;
01132         }
01133         else if (pNode == pNode->mParent->mRightChild)
01134         {
01135             pNode->mParent->mRightChild = lNode;
01136         }
01137         else
01138         {
01139             pNode->mParent->mLeftChild = lNode;
01140         }
01141         pNode->mParent = lNode;
01142         lNode->mRightChild = pNode;
01143 
01144         K_ASSERT(lNode->mLeftChild == A);
01145         K_ASSERT(lNode->mRightChild == pNode);
01146         K_ASSERT(lNode->mParent == Z);
01147 
01148         K_ASSERT(pNode->mLeftChild == B);
01149         K_ASSERT(pNode->mRightChild == C);
01150         K_ASSERT(pNode->mParent == lNode);
01151 
01152         K_ASSERT(A == 0 || A->mParent == lNode);
01153         K_ASSERT(B == 0 || B->mParent == pNode);
01154         K_ASSERT(C == 0 || C->mParent == pNode);
01155         K_ASSERT(Z == 0 || Z->mLeftChild == lNode || Z->mRightChild == lNode);
01156     }
01157 
01158 
01159     inline void RemoveNode(RecordType* pNode)
01160     {
01161         if (pNode->mLeftChild == 0)
01162         {
01163             if (pNode->mRightChild == 0)
01164             {
01165                 if (pNode->mParent)
01166                 {
01167                     if (pNode->mParent->mLeftChild == pNode)
01168                     {
01169                         pNode->mParent->mLeftChild = 0;
01170                     }
01171                     else if (pNode->mParent->mRightChild == pNode)
01172                     {
01173                         pNode->mParent->mRightChild = 0;
01174                     }
01175                     else
01176                     {
01177                         K_ASSERT(false);
01178                     }
01179                 }
01180                 else
01181                 {
01182                     K_ASSERT(mRoot == pNode);
01183                     mRoot = 0;
01184                 }
01185 
01186                 if (pNode->mColor == RecordType::eBlack)
01187                 {
01188                     FixNodesAfterRemoval(pNode->mParent, 0);
01189                 }
01190             }
01191             else
01192             {
01193                 if (pNode->mParent)
01194                 {
01195                     if (pNode->mParent->mLeftChild == pNode)
01196                     {
01197                         pNode->mParent->mLeftChild = pNode->mRightChild;
01198                         pNode->mRightChild->mParent = pNode->mParent;
01199                     }
01200                     else if (pNode->mParent->mRightChild == pNode)
01201                     {
01202                         pNode->mParent->mRightChild = pNode->mRightChild;
01203                         pNode->mRightChild->mParent = pNode->mParent;
01204                     }
01205                     else
01206                     {
01207                         K_ASSERT(false);
01208                     }
01209                 }
01210                 else
01211                 {
01212                     K_ASSERT(mRoot == pNode);
01213                     mRoot = pNode->mRightChild;
01214                     pNode->mRightChild->mParent = 0;
01215                 }
01216 
01217                 if (pNode->mColor == RecordType::eBlack)
01218                 {
01219                     FixNodesAfterRemoval(pNode->mRightChild->mParent, pNode->mRightChild);
01220                 }
01221             }
01222         }
01223         else
01224         {
01225             if (pNode->mRightChild == 0)
01226             {
01227                 if (pNode->mParent)
01228                 {
01229                     if (pNode->mParent->mLeftChild == pNode)
01230                     {
01231                         pNode->mParent->mLeftChild = pNode->mLeftChild;
01232                         pNode->mLeftChild->mParent = pNode->mParent;
01233                     }
01234                     else if (pNode->mParent->mRightChild == pNode)
01235                     {
01236                         pNode->mParent->mRightChild = pNode->mLeftChild;
01237                         pNode->mLeftChild->mParent = pNode->mParent;
01238                     }
01239                     else
01240                     {
01241                         K_ASSERT(false);
01242                     }
01243                 }
01244                 else
01245                 {
01246                     K_ASSERT(mRoot == pNode);
01247                     mRoot = pNode->mLeftChild;
01248                     pNode->mLeftChild->mParent = 0;
01249                 }
01250 
01251                 if (pNode->mColor == RecordType::eBlack)
01252                 {
01253                     FixNodesAfterRemoval(pNode->mLeftChild->mParent, pNode->mLeftChild);
01254                 }
01255             }
01256             else
01257             {
01258                 RecordType* lMinRightNode = pNode->mRightChild->Minimum();
01259                 RemoveNode(lMinRightNode);
01260 
01261                 lMinRightNode->mColor = pNode->mColor;
01262                 ReplaceNode(pNode, lMinRightNode);
01263             }
01264         }
01265 
01266         pNode->mParent = 0;
01267         pNode->mLeftChild = 0;
01268         pNode->mRightChild = 0;
01269     }
01270 
01271 
01272     inline void ReplaceNode(RecordType* pNodeToReplace, RecordType* pReplacement)
01273     {
01274         pReplacement->mParent = pNodeToReplace->mParent;
01275         if (pNodeToReplace->mParent)
01276         {
01277             if (pNodeToReplace->mParent->mLeftChild == pNodeToReplace)
01278             {
01279                 pNodeToReplace->mParent->mLeftChild = pReplacement;
01280             }
01281             else if (pNodeToReplace->mParent->mRightChild == pNodeToReplace)
01282             {
01283                 pNodeToReplace->mParent->mRightChild = pReplacement;
01284             }
01285         }
01286         else
01287         {
01288             K_ASSERT(mRoot == pNodeToReplace);
01289             mRoot = pReplacement;
01290         }
01291 
01292         pReplacement->mLeftChild = pNodeToReplace->mLeftChild;
01293         if (pReplacement->mLeftChild)
01294         {
01295             pReplacement->mLeftChild->mParent = pReplacement;
01296         }
01297 
01298         pReplacement->mRightChild = pNodeToReplace->mRightChild;
01299         if (pReplacement->mRightChild)
01300         {
01301             pReplacement->mRightChild->mParent = pReplacement;
01302         }
01303     }
01304 
01305     inline RecordType* Sibling(RecordType const* pParent, RecordType const* pNode) const
01306     {
01307         if (pParent)
01308         {
01309             if (pParent->mLeftChild == pNode)
01310             {
01311                 return pParent->mRightChild;
01312             }
01313             else if (pParent->mRightChild == pNode)
01314             {
01315                 return pParent->mLeftChild;
01316             }
01317         }
01318 
01319         return 0;
01320     }
01321 
01322     inline bool IsBlack(RecordType const* pNode)
01323     {
01324         return ((pNode == 0) || (pNode->mColor == RecordType::eBlack));
01325     }
01326 
01327     inline void FixNodesAfterRemoval(RecordType* pParent, RecordType* pNode)
01328     {
01329         RecordType* lParent = pParent;
01330         RecordType* lNode = pNode;
01331         bool lDone = false;
01332 
01333         while (!lDone)
01334         {
01335             lDone = true;
01336 
01337             if (!IsBlack(lNode))
01338             {
01339                 lNode->mColor = RecordType::eBlack;
01340             }
01341             else if (lParent != NULL)
01342             {
01343                 RecordType* lSibling = Sibling(lParent, lNode);
01344 
01345                 if (!IsBlack(lSibling))
01346                 {
01347                     lParent->mColor = RecordType::eRed;
01348                     lSibling->mColor = RecordType::eBlack;
01349                     if (lNode == lParent->mLeftChild)
01350                     {
01351                         LeftRotate(lParent);
01352                     }
01353                     else
01354                     {
01355                         RightRotate(lParent);
01356                     }
01357 
01358                     // update sibling: it may have change after rotation
01359                     // parent was not affected by this rotation
01360                     lSibling = Sibling(lParent, lNode);
01361                 }
01362 
01363                 /* check this for null sibling */
01364                 if (lSibling &&
01365                     IsBlack(lParent) &&
01366                     IsBlack(lSibling) &&
01367                     IsBlack(lSibling->mLeftChild) &&
01368                     IsBlack(lSibling->mRightChild))
01369                 {
01370                     lSibling->mColor = RecordType::eRed;
01371                     lNode = lParent;
01372                     lParent = lParent->mParent;
01373                     lDone = false;
01374                 }
01375                 else
01376                 {
01377                     if (!IsBlack(lParent) &&
01378                         IsBlack(lSibling) &&
01379                         ((lSibling == 0) || IsBlack(lSibling->mLeftChild)) &&
01380                         ((lSibling == 0) || IsBlack(lSibling->mRightChild)))
01381                     {
01382                         if (lSibling)
01383                         {
01384                             lSibling->mColor = RecordType::eRed;
01385                         }
01386                         lParent->mColor = RecordType::eBlack;
01387                     }
01388                     else // lSibling != 0
01389                     {
01390                         if ((lNode == lParent->mLeftChild) &&
01391                             IsBlack(lSibling) &&
01392                             !IsBlack(lSibling->mLeftChild) &&
01393                             IsBlack(lSibling->mRightChild))
01394                         {
01395                             lSibling->mColor = RecordType::eRed;
01396                             lSibling->mLeftChild->mColor = RecordType::eBlack;
01397                             RightRotate(lSibling);
01398                         }
01399                         else if ((lNode == lParent->mRightChild) &&
01400                                  IsBlack(lSibling) &&
01401                                  IsBlack(lSibling->mLeftChild) &&
01402                                  !IsBlack(lSibling->mRightChild))
01403                         {
01404                             lSibling->mColor = RecordType::eRed;
01405                             lSibling->mRightChild->mColor = RecordType::eBlack;
01406                             LeftRotate(lSibling);
01407                         }
01408 
01409                         // update sibling: it may have change after rotation
01410                         lSibling = Sibling(lParent, lNode);
01411                         K_ASSERT(lSibling != 0); // lSibling is now
01412                                                  // the former red
01413                                                  // child of the
01414                                                  // former sibling
01415 
01416                         lSibling->mColor = lParent->mColor;
01417                         lParent->mColor = RecordType::eBlack;
01418                         if (lNode == lParent->mLeftChild)
01419                         {
01420                             if (lSibling->mRightChild)
01421                             {
01422                                 lSibling->mRightChild->mColor = RecordType::eBlack;
01423                             }
01424                             LeftRotate(lParent);
01425                         }
01426                         else
01427                         {
01428                             if (lSibling->mLeftChild)
01429                             {
01430                                 lSibling->mLeftChild->mColor = RecordType::eBlack;
01431                             }
01432                             RightRotate(lParent);
01433                         }
01434                     }
01435                 }
01436             }
01437         }
01438 
01439         if (mRoot)
01440         {
01441             mRoot->mColor = RecordType::eBlack;
01442         }
01443     }
01444 
01445 
01446     inline void ClearSubTree(RecordType* pNode)
01447     {
01448         if (pNode)
01449         {
01450             ClearSubTree(pNode->mLeftChild);
01451             ClearSubTree(pNode->mRightChild);
01452             pNode->~RecordType();
01453             mAllocator.FreeMemory(pNode);
01454         }
01455     }
01456 
01457     inline int GetSubTreeSize(RecordType* pNode) const
01458     {
01459         if (pNode)
01460         {
01461             return GetSubTreeSize(pNode->mLeftChild) + GetSubTreeSize(pNode->mRightChild) + 1;
01462         }
01463         else
01464         {
01465             return 0;
01466         }
01467     }
01468 
01469 };
01470 
01471 /*************************************************************************
01472  *
01473  * Default comparator for maps.  Assumes operator < is defined.
01474  *
01475  *************************************************************************/
01476 
01477 template <typename T>
01478 struct KFbxLessCompare
01479 {
01480     inline int operator()(const T& left, const T& right) const
01481     {
01482         return (left < right) ? -1 : ((right < left) ? 1 : 0);
01483     }
01484 };
01485 
01486 /*************************************************************************
01487  * class KMap
01488  *
01489  * Implements an efficient dictionnary.
01490  *
01491  *************************************************************************/
01492 
01493 
01494 template <typename KEY_TYPE,
01495           typename VALUE_TYPE,
01496           typename KEY_COMPARE_FUNCTOR = KFbxLessCompare<KEY_TYPE>,
01497           typename ALLOCATOR = KBaseAllocator>
01498 class KMap
01499 {
01500 protected:
01501     class KKeyValuePair : private KPair<const KEY_TYPE, VALUE_TYPE>
01502     {
01503     public:
01504         KKeyValuePair(KEY_TYPE const& pFirst, VALUE_TYPE const& pSecond)
01505             : KPair<const KEY_TYPE, VALUE_TYPE>(pFirst, pSecond) {}
01506 
01507         // Key is always const.
01508         typedef const KEY_TYPE      KeyType;
01509         typedef const KEY_TYPE      ConstKeyType;
01510         typedef VALUE_TYPE          ValueType;
01511         typedef const VALUE_TYPE    ConstValueType;
01512 
01513         ConstKeyType & GetKey() const       { return this->mFirst; }
01514         KeyType & GetKey()                  { return this->mFirst; }
01515 
01516         ConstValueType& GetValue() const    { return this->mSecond; }
01517         ValueType& GetValue()               { return this->mSecond; }
01518     };
01519 
01520     typedef KRedBlackTree<KKeyValuePair, KEY_COMPARE_FUNCTOR, ALLOCATOR> StorageType;
01521     StorageType mTree;
01522 
01523 
01524 public:
01525     typedef VALUE_TYPE ValueType;
01526     typedef KEY_TYPE KeyType;
01527     typedef typename StorageType::RecordType         RecordType;
01528     typedef typename StorageType::IteratorType       Iterator;
01529     typedef typename StorageType::ConstIteratorType  ConstIterator;
01530 
01531     inline KMap() {}
01532     inline KMap(KMap const& pMap) : mTree(pMap.mTree) {}
01533     inline ~KMap() {Clear();}
01534 
01535     inline void Reserve(unsigned int pRecordCount)
01536     {
01537         mTree.Reserve(pRecordCount);
01538     }
01539 
01540     inline int GetSize() const
01541     {
01542         return mTree.GetSize();
01543     }
01544 
01545     inline KPair<RecordType*, bool> Insert(KeyType const& pKey, ValueType const& pValue)
01546     {
01547         return mTree.Insert(KKeyValuePair(pKey, pValue));
01548     }
01549 
01550     inline int Remove(KeyType const& pKey)
01551     {
01552         return mTree.Remove(pKey);
01553     }
01554 
01555     inline void Clear()
01556     {
01557         mTree.Clear();
01558     }
01559 
01560     inline bool Empty() const
01561     {
01562         return mTree.Empty();
01563     }
01564 
01565     Iterator Begin()
01566     {
01567         return Iterator(Minimum());
01568     }
01569 
01570     Iterator End()
01571     {
01572         return Iterator();
01573     }
01574 
01575     ConstIterator Begin() const
01576     {
01577         return ConstIterator(Minimum());
01578     }
01579 
01580     ConstIterator End() const
01581     {
01582         return ConstIterator();
01583     }
01584 
01585     inline RecordType const* Find(KeyType const& pKey) const
01586     {
01587         return mTree.Find(pKey);
01588     }
01589 
01590     inline RecordType* Find(KeyType const& pKey)
01591     {
01592         return mTree.Find(pKey);
01593     }
01594 
01595     inline RecordType const* UpperBound(KeyType const& pKey) const
01596     {
01597         return mTree.UpperBound(pKey);
01598     }
01599 
01600     inline RecordType* UpperBound(KeyType const& pKey)
01601     {
01602         return mTree.UpperBound(pKey);
01603     }
01604 
01605     inline ValueType& operator[](KeyType const& pKey)
01606     {
01607         RecordType* lRecord = Find(pKey);
01608 
01609         if( !lRecord )
01610         {
01611             lRecord = Insert(pKey, ValueType()).mFirst;
01612         }
01613 
01614         return lRecord->GetValue();
01615     }
01616 
01617     inline RecordType const* Minimum() const
01618     {
01619         return mTree.Minimum();
01620     }
01621 
01622     inline RecordType* Minimum()
01623     {
01624         return mTree.Minimum();
01625     }
01626 
01627     inline RecordType const* Maximum() const
01628     {
01629         return mTree.Maximum();
01630     }
01631 
01632     inline RecordType* Maximum()
01633     {
01634         return mTree.Maximum();
01635     }
01636 };
01637 
01638 /*************************************************************************
01639  * class KSet2
01640  *
01641  * Implements a data storage with efficient Find.
01642  *
01643  *************************************************************************/
01644 
01645 
01646 template <typename VALUE_TYPE,
01647           typename KEY_COMPARE_FUNCTOR = KFbxLessCompare<VALUE_TYPE>,
01648           typename ALLOCATOR = KBaseAllocator>
01649 class KSet2
01650 {
01651 protected:
01652     class KValue
01653     {
01654     public:
01655         inline KValue(VALUE_TYPE const& pValue)
01656             : mValue(pValue) {}
01657 
01658         // Cannot modify the value in a set, which would change its ordering in the tree
01659         typedef const VALUE_TYPE KeyType;
01660         typedef const VALUE_TYPE ConstKeyType;
01661         typedef const VALUE_TYPE ValueType;
01662         typedef const VALUE_TYPE ConstValueType;
01663 
01664         inline KeyType& GetKey() const      { return mValue; }
01665         inline ConstKeyType& GetKey()       { return mValue; }
01666 
01667         inline ValueType& GetValue() const  { return mValue; }
01668         inline ConstValueType& GetValue()   { return mValue; }
01669 
01670     protected:
01671         ValueType mValue;
01672     };
01673 
01674     typedef KRedBlackTree<KValue, KEY_COMPARE_FUNCTOR, ALLOCATOR> StorageType;
01675     StorageType mTree;
01676 
01677 
01678 public:
01679     typedef VALUE_TYPE ValueType;
01680     typedef typename StorageType::RecordType        RecordType;
01681     typedef typename StorageType::IteratorType      Iterator;
01682     typedef typename StorageType::ConstIteratorType ConstIterator;
01683 
01684     inline KSet2() {}
01685     inline KSet2(KSet2 const& pSet) : mTree(pSet.mTree) {}
01686     inline ~KSet2() {Clear();}
01687 
01688     inline void Reserve(unsigned int pRecordCount)
01689     {
01690         mTree.Reserve(pRecordCount);
01691     }
01692 
01693     inline int GetSize() const
01694     {
01695         return mTree.GetSize();
01696     }
01697 
01698     inline KPair<RecordType*, bool> Insert(ValueType const& pValue)
01699     {
01700         return mTree.Insert(KValue(pValue));
01701     }
01702 
01703     inline int Remove(ValueType const& pValue)
01704     {
01705         return mTree.Remove(pValue);
01706     }
01707 
01708     inline void Clear()
01709     {
01710         mTree.Clear();
01711     }
01712 
01713     inline bool Empty() const
01714     {
01715         return mTree.Empty();
01716     }
01717 
01718     Iterator Begin()
01719     {
01720         return Iterator(Minimum());
01721     }
01722 
01723     Iterator End()
01724     {
01725         return Iterator();
01726     }
01727 
01728     ConstIterator Begin() const
01729     {
01730         return ConstIterator(Minimum());
01731     }
01732 
01733     ConstIterator End() const
01734     {
01735         return ConstIterator();
01736     }
01737 
01738     inline RecordType const* Find(ValueType const& pValue) const
01739     {
01740         return mTree.Find(pValue);
01741     }
01742 
01743     inline RecordType* Find(ValueType const& pValue)
01744     {
01745         return mTree.Find(pValue);
01746     }
01747 
01748     inline RecordType const* Minimum() const
01749     {
01750         return mTree.Minimum();
01751     }
01752 
01753     inline RecordType* Minimum()
01754     {
01755         return mTree.Minimum();
01756     }
01757 
01758     inline RecordType const* Maximum() const
01759     {
01760         return mTree.Maximum();
01761     }
01762 
01763     inline RecordType* Maximum()
01764     {
01765         return mTree.Maximum();
01766     }
01767 
01768     inline bool operator==(const KSet2<VALUE_TYPE, KEY_COMPARE_FUNCTOR, ALLOCATOR>& pOther) const
01769     {
01770         return (this == &pOther) || (mTree == pOther.mTree);
01771     }
01772 
01773     inline bool operator != (const KSet2<VALUE_TYPE, KEY_COMPARE_FUNCTOR, ALLOCATOR>& pOther) const
01774     {
01775         return !(*this == pOther);
01776     }
01777 };
01778 #include <kbaselib_nsend.h>
01779 
01780 #endif // _FBXSDK_KMAP_H_
01781