00001 #ifndef _FBXSDK_KMAP_H_
00002 #define _FBXSDK_KMAP_H_
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
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
00054
00055
00056
00057
00058
00059
00060
00061
00062
00063
00064
00065
00066
00067
00068
00069
00070
00071
00072
00073
00074
00075
00076
00077
00078
00079
00080
00081
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
00099 RedBack_IteratorType const& operator++()
00100 {
00101 K_ASSERT( mRecord != NULL );
00102
00103 mRecord = mRecord->Successor();
00104
00105 return *this;
00106 }
00107
00108
00109 RedBack_IteratorType operator++(int)
00110 {
00111 RedBack_IteratorType t(*this);
00112 operator++();
00113 return t;
00114 }
00115
00116
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
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
00188 RedBack_ConstIteratorType const& operator++()
00189 {
00190 K_ASSERT( mRecord != NULL );
00191
00192 mRecord = mRecord->Successor();
00193
00194 return *this;
00195 }
00196
00197
00198 RedBack_ConstIteratorType operator++(int)
00199 {
00200 RedBack_ConstIteratorType t(*this);
00201 operator++();
00202 return t;
00203 }
00204
00205
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
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
00527 if( this == &pTree )
00528 return true;
00529
00530 if( GetSize() != pTree.GetSize() )
00531 return false;
00532
00533
00534
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
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
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
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
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
01359
01360 lSibling = Sibling(lParent, lNode);
01361 }
01362
01363
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
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
01410 lSibling = Sibling(lParent, lNode);
01411 K_ASSERT(lSibling != 0);
01412
01413
01414
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
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
01488
01489
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
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
01640
01641
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
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