fbxsdk/core/base/fbxredblacktree.h Source File

fbxredblacktree.h
Go to the documentation of this file.
1 /****************************************************************************************
2 
3  Copyright (C) 2015 Autodesk, Inc.
4  All rights reserved.
5 
6  Use of this software is subject to the terms of the Autodesk license agreement
7  provided at the time of installation or download, or which otherwise accompanies
8  this software in either electronic or hard copy form.
9 
10 ****************************************************************************************/
11 
13 #ifndef _FBXSDK_CORE_BASE_REDBLACKTREE_H_
14 #define _FBXSDK_CORE_BASE_REDBLACKTREE_H_
15 
16 #include <fbxsdk/fbxsdk_def.h>
17 
18 #include <fbxsdk/core/base/fbxcontainerallocators.h>
19 #include <fbxsdk/core/base/fbxpair.h>
20 
21 #include <fbxsdk/fbxsdk_nsbegin.h>
22 
23 /*****************************************************************************************************************************
24 ** WARNING! Anything beyond these lines is for internal use, may not be documented and is subject to change without notice! **
25 *****************************************************************************************************************************/
26 #ifndef DOXYGEN_SHOULD_SKIP_THIS
27 
28 template <typename RecordType> class FbxRedBlackConstIterator;
29 
30 template <typename RecordType> class FbxRedBlackIterator
31 {
32 public:
33  FbxRedBlackIterator() : mRecord(0) {}
34  FbxRedBlackIterator(RecordType* pRecord) : mRecord(pRecord) {}
35  FbxRedBlackIterator(const FbxRedBlackIterator<RecordType>& pV) : mRecord(pV.mRecord) {}
36 
37  FbxRedBlackIterator& operator++()
38  {
39  FBX_ASSERT( mRecord != NULL );
40  mRecord = mRecord->Successor();
41  return *this;
42  }
43 
44  const FbxRedBlackIterator operator++(int)
45  {
46  FbxRedBlackIterator t(*this);
47  operator++();
48  return t;
49  }
50 
51  FbxRedBlackIterator& operator+=(int pCount)
52  {
53  FBX_ASSERT( mRecord != NULL );
54  for( int i = 0; i < pCount; ++i )
55  {
56  if( !mRecord ) break;
57  mRecord = mRecord->Successor();
58  }
59  return *this;
60  }
61 
62  FbxRedBlackIterator& operator--()
63  {
64  FBX_ASSERT( mRecord );
65  mRecord = mRecord->Predecessor();
66  return *this;
67  }
68 
69  const FbxRedBlackIterator operator--(int)
70  {
71  FbxRedBlackIterator t(*this);
72  operator--();
73  return t;
74  }
75 
76  FbxRedBlackIterator& operator-=(int pCount)
77  {
78  FBX_ASSERT( mRecord != NULL );
79  for( int i = 0; i < pCount; ++i )
80  {
81  if( !mRecord ) break;
82  mRecord = mRecord->Predecessor();
83  }
84  return *this;
85  }
86 
87  const RecordType& operator*() const
88  {
89  FBX_ASSERT( mRecord );
90 
91  return *mRecord;
92  }
93 
94  RecordType& operator*()
95  {
96  FBX_ASSERT( mRecord );
97 
98  return *mRecord;
99  }
100 
101  const RecordType* operator->() const
102  {
103  FBX_ASSERT( mRecord );
104 
105  return mRecord;
106  }
107 
108  RecordType* operator->()
109  {
110  FBX_ASSERT( mRecord );
111 
112  return mRecord;
113  }
114 
115  inline bool operator==(const FbxRedBlackIterator& pOther) const
116  {
117  return mRecord == pOther.mRecord;
118  }
119 
120  inline bool operator !=(const FbxRedBlackIterator& pOther) const
121  {
122  return mRecord != pOther.mRecord;
123  }
124 
125 protected:
126  RecordType* mRecord;
127 
128  friend class FbxRedBlackConstIterator<RecordType>;
129 };
130 
131 template <typename RecordType> class FbxRedBlackConstIterator
132 {
133 public:
134  FbxRedBlackConstIterator() : mRecord(0) {}
135  FbxRedBlackConstIterator(const RecordType* pRecord) : mRecord(pRecord) {}
136  FbxRedBlackConstIterator(const FbxRedBlackIterator<RecordType>& pV) : mRecord(pV.mRecord) {}
137  FbxRedBlackConstIterator(const FbxRedBlackConstIterator<RecordType>& pV) : mRecord(pV.mRecord) {}
138 
139  FbxRedBlackConstIterator & operator++()
140  {
141  FBX_ASSERT( mRecord != NULL );
142  mRecord = mRecord->Successor();
143  return *this;
144  }
145 
146  const FbxRedBlackConstIterator operator++(int)
147  {
148  FbxRedBlackConstIterator t(*this);
149  operator++();
150  return t;
151  }
152 
153  FbxRedBlackConstIterator& operator+=(int pCount)
154  {
155  FBX_ASSERT( mRecord != NULL );
156  for( int i = 0; i < pCount; ++i )
157  {
158  if( !mRecord ) break;
159  mRecord = mRecord->Successor();
160  }
161  return *this;
162  }
163 
164  FbxRedBlackConstIterator & operator--()
165  {
166  FBX_ASSERT( mRecord );
167  mRecord = mRecord->Predecessor();
168  return *this;
169  }
170 
171  const FbxRedBlackConstIterator operator--(int)
172  {
173  FbxRedBlackConstIterator t(*this);
174  operator--();
175  return t;
176  }
177 
178  FbxRedBlackConstIterator& operator-=(int pCount)
179  {
180  FBX_ASSERT( mRecord != NULL );
181  for( int i = 0; i < pCount; ++i )
182  {
183  if( !mRecord ) break;
184  mRecord = mRecord->Predecessor();
185  }
186  return *this;
187  }
188 
189  const RecordType& operator*() const
190  {
191  FBX_ASSERT( mRecord );
192 
193  return *mRecord;
194  }
195 
196  const RecordType& operator*()
197  {
198  FBX_ASSERT( mRecord );
199 
200  return *mRecord;
201  }
202 
203  const RecordType* operator->() const
204  {
205  FBX_ASSERT( mRecord );
206 
207  return mRecord;
208  }
209 
210  const RecordType* operator->()
211  {
212  FBX_ASSERT( mRecord );
213 
214  return mRecord;
215  }
216 
217  inline bool operator==(const FbxRedBlackConstIterator& pOther) const
218  {
219  return mRecord == pOther.mRecord;
220  }
221 
222  inline bool operator !=(const FbxRedBlackConstIterator& pOther) const
223  {
224  return mRecord != pOther.mRecord;
225  }
226 
227 protected:
228  const RecordType* mRecord;
229 
230  friend class FbxRedBlackIterator<RecordType>;
231 };
232 
234 template <typename Type, typename Compare, typename Allocator> class FbxRedBlackTree
235 {
236 public:
237  typedef Type DataType;
238  typedef typename Type::KeyType KeyType;
239  typedef typename Type::ConstKeyType ConstKeyType;
240  typedef typename Type::ValueType ValueType;
241  typedef typename Type::ConstValueType ConstValueType;
242  typedef Allocator AllocatorType;
243 
248  class RecordType
249  {
250  public:
251  inline ConstKeyType& GetKey() const { return mData.GetKey(); }
252  inline ConstValueType& GetValue() const { return mData.GetValue(); }
253  inline ValueType& GetValue() { return mData.GetValue(); }
254 
255  inline const RecordType* Minimum() const
256  {
257  const RecordType* lParent = 0;
258  const RecordType* lNode = this;
259  while (lNode != 0)
260  {
261  lParent = lNode;
262  lNode = lNode->mLeftChild;
263  }
264 
265  return lParent;
266  }
267 
268  inline RecordType* Minimum()
269  {
270  RecordType* lParent = 0;
271  RecordType* lNode = this;
272  while (lNode != 0)
273  {
274  lParent = lNode;
275  lNode = lNode->mLeftChild;
276  }
277 
278  return lParent;
279  }
280 
281  inline const RecordType* Maximum() const
282  {
283  const RecordType* lParent = 0;
284  const RecordType* lNode = this;
285  while (lNode != 0)
286  {
287  lParent = lNode;
288  lNode = lNode->mRightChild;
289  }
290 
291  return lParent;
292  }
293 
294  inline RecordType* Maximum()
295  {
296  RecordType* lParent = 0;
297  RecordType* lNode = this;
298  while (lNode != 0)
299  {
300  lParent = lNode;
301  lNode = lNode->mRightChild;
302  }
303 
304  return lParent;
305  }
306 
307  inline const RecordType* Predecessor() const
308  {
309  if (mLeftChild)
310  {
311  return mLeftChild->Maximum();
312  }
313  else
314  {
315  const RecordType* lParent = mParent;
316  const RecordType* lNode = this;
317 
318  while (lParent && lParent->mLefttChild == lNode)
319  {
320  lNode = lParent;
321  lParent = lParent->mParent;
322  }
323 
324  return lParent;
325  }
326  }
327 
328  inline RecordType* Predecessor()
329  {
330  if (mLeftChild)
331  {
332  return mLeftChild->Maximum();
333  }
334  else
335  {
336  RecordType* lParent = mParent;
337  RecordType* lNode = this;
338 
339  while (lParent && lParent->mLeftChild == lNode)
340  {
341  lNode = lParent;
342  lParent = lParent->mParent;
343  }
344 
345  return lParent;
346  }
347  }
348 
349  inline const RecordType* Successor() const
350  {
351  if (mRightChild)
352  {
353  return mRightChild->Minimum();
354  }
355  else
356  {
357  const RecordType* lParent = mParent;
358  const RecordType* lNode = this;
359 
360  while (lParent && lParent->mRightChild == lNode)
361  {
362  lNode = lParent;
363  lParent = lParent->mParent;
364  }
365 
366  return lParent;
367  }
368  }
369 
370  inline RecordType* Successor()
371  {
372  if (mRightChild)
373  {
374  return mRightChild->Minimum();
375  }
376  else
377  {
378  RecordType* lParent = mParent;
379  RecordType* lNode = this;
380 
381  while (lParent && lParent->mRightChild == lNode)
382  {
383  lNode = lParent;
384  lParent = lParent->mParent;
385  }
386 
387  return lParent;
388  }
389  }
390 
391  inline const int GetBlackDepth() { return mBlackDepth; }
392 
393  private:
394  enum ETreeType {eRed, eBlack};
395 
396  inline RecordType(const DataType& pData)
397  : mData(pData)
398  , mParent(0)
399  , mLeftChild(0)
400  , mRightChild(0)
401  , mColor(eRed)
402  , mBlackDepth(0)
403  {
404  }
405 
406  inline RecordType(const RecordType& pRecordType)
407  : mData(pRecordType.mData)
408  , mParent(0)
409  , mLeftChild(0)
410  , mRightChild(0)
411  , mColor(pRecordType.mColor)
412  , mBlackDepth(pRecordType.mBlackDepth)
413  {
414  }
415 
416  DataType mData;
417 
418  friend class FbxRedBlackTree;
419 
420  RecordType* mParent;
421  RecordType* mLeftChild;
422  RecordType* mRightChild;
423  unsigned int mColor:2;
424  unsigned int mBlackDepth:30;
425  };
426 
427 public:
428  typedef FbxRedBlackConstIterator<RecordType> ConstIteratorType;
429  typedef FbxRedBlackIterator<RecordType> IteratorType;
430 
431  inline FbxRedBlackTree() : mRoot(0), mSize(0), mAllocator(sizeof(RecordType)) {}
432  inline FbxRedBlackTree(const FbxRedBlackTree& pTree) : mRoot(0), mSize(0), mAllocator(sizeof(RecordType)) { operator=(pTree); }
433  inline ~FbxRedBlackTree() { Clear(); }
434 
437  inline FbxRedBlackTree& operator=(const FbxRedBlackTree& pTree)
438  {
439  if( this != &pTree )
440  {
441  Clear();
442 
443  mAllocator = pTree.mAllocator;
444 
445  if( pTree.mRoot )
446  {
447  void* lBuffer = mAllocator.AllocateRecords();
448  mRoot = new(lBuffer) RecordType(*(pTree.mRoot)); //in-place new won't allocate memory, so it is safe
449  mRoot->mLeftChild = DuplicateSubTree(pTree.mRoot->mLeftChild);
450  mRoot->mRightChild = DuplicateSubTree(pTree.mRoot->mRightChild);
451 
452  if (mRoot->mLeftChild)
453  {
454  mRoot->mLeftChild->mParent = mRoot;
455  }
456 
457  if (mRoot->mRightChild)
458  {
459  mRoot->mRightChild->mParent = mRoot;
460  }
461  }
462  else
463  {
464  FBX_ASSERT( pTree.mSize == 0 );
465  FBX_ASSERT( mRoot == 0 );
466  }
467 
468  mSize = pTree.mSize;
469  }
470 
471  return *this;
472  }
473 
474  inline bool operator==(const FbxRedBlackTree& pTree) const
475  {
476  // Check a few quick shortcuts
477  if( this == &pTree )
478  return true;
479 
480  if( GetSize() != pTree.GetSize() )
481  return false;
482 
483  // Iterator through all nodes; if we reach the end of both iterators at the same
484  // time then we have two iterators that match.
485  ConstIteratorType End;
486  ConstIteratorType Iter1(Minimum());
487  ConstIteratorType Iter2(pTree.Minimum());
488 
489  while( (Iter1 != End) && (Iter2 != End) &&
490  (Iter1->GetKey() == Iter2->GetKey()) &&
491  (Iter1->GetValue() == Iter2->GetValue()) )
492  {
493  ++Iter1;
494  ++Iter2;
495  }
496 
497  return Iter1 == End && Iter2 == End;
498  }
499 
503  inline void Reserve(unsigned int pRecordCount)
504  {
505  mAllocator.Reserve(pRecordCount);
506  }
507 
511  inline int GetSize() const { return mSize; }
512 
513  inline bool Empty() const { return mSize == 0; }
514 
520  inline FbxPair<RecordType*, bool> Insert(const DataType& pData)
521  {
522  Compare lCompareKeys;
523  bool lResult = false;
524  RecordType* lParent = 0;
525  RecordType* lNode = mRoot;
526  while (lNode != 0)
527  {
528  const KeyType& lNodeKey = lNode->GetKey();
529  const KeyType& lDataKey = pData.GetKey();
530 
531  if (lCompareKeys(lNodeKey, lDataKey) < 0)
532  {
533  lParent = lNode;
534  lNode = lNode->mRightChild;
535  }
536  else if (lCompareKeys(lNodeKey, lDataKey) > 0)
537  {
538  lParent = lNode;
539  lNode = lNode->mLeftChild;
540  }
541  else
542  {
543  break;
544  }
545  }
546 
547  if (lNode == 0)
548  {
549  void* lBuffer = mAllocator.AllocateRecords();
550  lNode = new(lBuffer) RecordType(pData); //in-place new won't allocate memory, so it is safe
551  mSize++;
552 
553  FBX_ASSERT(lNode == lBuffer);
554 
555  if (lParent)
556  {
557  if (lCompareKeys(lParent->GetKey(), pData.GetKey()) < 0)
558  {
559  FBX_ASSERT(lParent->mRightChild == 0);
560  lParent->mRightChild = lNode;
561  lNode->mParent = lParent;
562  }
563  else
564  {
565  FBX_ASSERT(lParent->mLeftChild == 0);
566  lParent->mLeftChild = lNode;
567  lNode->mParent = lParent;
568  }
569  }
570  else
571  {
572  mRoot = lNode;
573  }
574 
575  // Fix red black tree property
576  FixNodesAfterInsertion(lNode);
577 
578  lResult = true;
579  }
580 
581  return FbxPair<RecordType*, bool>(lNode, lResult);
582  }
583 
587  inline bool Remove(const KeyType& pKey)
588  {
589  Compare lCompareKeys;
590  bool lResult = false;
591  RecordType* lNode = mRoot;
592  while (lNode != 0)
593  {
594  if (lCompareKeys(lNode->GetKey(), pKey) < 0)
595  {
596  lNode = lNode->mRightChild;
597  }
598  else if (lCompareKeys(lNode->GetKey(), pKey) > 0)
599  {
600  lNode = lNode->mLeftChild;
601  }
602  else
603  {
604  break;
605  }
606  }
607 
608  if (lNode)
609  {
610  RemoveNode(lNode);
611  mSize--;
612  lNode->~RecordType();
613  mAllocator.FreeMemory(lNode);
614 
615  lResult = true;
616  }
617 
618  return lResult;
619  }
620 
623  inline void Clear()
624  {
625  if (mRoot)
626  {
627  ClearSubTree(mRoot->mLeftChild);
628  ClearSubTree(mRoot->mRightChild);
629  mRoot->~RecordType();
630  mAllocator.FreeMemory(mRoot);
631  mRoot = 0;
632  mSize = 0;
633  }
634  }
635 
639  inline const RecordType* Minimum() const
640  {
641  if (0 != mRoot)
642  {
643  return mRoot->Minimum();
644  }
645  else
646  {
647  return 0;
648  }
649  }
650 
654  inline RecordType* Minimum()
655  {
656  if (0 != mRoot)
657  {
658  return mRoot->Minimum();
659  }
660  else
661  {
662  return 0;
663  }
664  }
665 
669  inline const RecordType* Maximum() const
670  {
671  if (0 != mRoot)
672  {
673  return mRoot->Maximum();
674  }
675  else
676  {
677  return 0;
678  }
679  }
680 
684  inline RecordType* Maximum()
685  {
686  if (0 != mRoot)
687  {
688  return mRoot->Maximum();
689  }
690  else
691  {
692  return 0;
693  }
694  }
695 
700  inline const RecordType* Find(const KeyType& pKey) const
701  {
702  Compare lCompareKeys;
703  const RecordType* lNode = mRoot;
704  while (lNode != 0)
705  {
706  if (lCompareKeys(lNode->GetKey(), pKey) < 0)
707  {
708  lNode = lNode->mRightChild;
709  }
710  else if (lCompareKeys(lNode->GetKey(), pKey) > 0)
711  {
712  lNode = lNode->mLeftChild;
713  }
714  else
715  {
716  break;
717  }
718  }
719 
720  return lNode;
721  }
722 
727  inline RecordType* Find(const KeyType& pKey)
728  {
729  Compare lCompareKeys;
730  RecordType* lNode = mRoot;
731  while (lNode != 0)
732  {
733  if (lCompareKeys(lNode->GetKey(), pKey) < 0)
734  {
735  lNode = lNode->mRightChild;
736  }
737  else if (lCompareKeys(lNode->GetKey(), pKey) > 0)
738  {
739  lNode = lNode->mLeftChild;
740  }
741  else
742  {
743  break;
744  }
745  }
746 
747  return lNode;
748  }
749 
754  inline const RecordType* UpperBound(const KeyType& pKey) const
755  {
756  Compare lCompareKeys;
757  const RecordType* lNode = mRoot;
758  const RecordType* lCandidate = 0;
759  while (lNode != 0)
760  {
761  if (lCompareKeys(lNode->GetKey(), pKey) <= 0)
762  {
763  lNode = lNode->mRightChild;
764  }
765  else if (lCompareKeys(lNode->GetKey(), pKey) > 0)
766  {
767  lCandidate = lNode;
768  lNode = lNode->mLeftChild;
769  }
770  }
771 
772  return lCandidate;
773  }
774 
779  inline RecordType* UpperBound(const KeyType& pKey)
780  {
781  Compare lCompareKeys;
782  RecordType* lNode = mRoot;
783  RecordType* lCandidate = 0;
784  while (lNode != 0)
785  {
786  if (lCompareKeys(lNode->GetKey(), pKey) <= 0)
787  {
788  lNode = lNode->mRightChild;
789  }
790  else if (lCompareKeys(lNode->GetKey(), pKey) > 0)
791  {
792  lCandidate = lNode;
793  lNode = lNode->mLeftChild;
794  }
795  }
796 
797  return lCandidate;
798  }
799 
800 protected:
801  RecordType* mRoot;
802  int mSize;
803 
804  AllocatorType mAllocator;
805 
806  inline RecordType* DuplicateSubTree(const RecordType* pNode)
807  {
808  RecordType* lNewSubTree = 0;
809 
810  if (pNode)
811  {
812  void* lBuffer = mAllocator.AllocateRecords();
813  lNewSubTree = new(lBuffer) RecordType(*pNode); //in-place new won't allocate memory, so it is safe
814  lNewSubTree->mLeftChild = DuplicateSubTree(pNode->mLeftChild);
815  lNewSubTree->mRightChild = DuplicateSubTree(pNode->mRightChild);
816 
817  if (lNewSubTree->mLeftChild)
818  {
819  lNewSubTree->mLeftChild->mParent = lNewSubTree;
820  }
821 
822  if (lNewSubTree->mRightChild)
823  {
824  lNewSubTree->mRightChild->mParent = lNewSubTree;
825  }
826  }
827 
828  return lNewSubTree;
829  }
830 
831  inline void FixNodesAfterInsertion(RecordType* pNode)
832  {
833  RecordType* lNode = pNode;
834  bool lDone = false;
835 
836  while (!lDone)
837  {
838  lDone = true;
839 
840  if (lNode->mParent == 0)
841  {
842  lNode->mColor = RecordType::eBlack;
843  }
844  else if (lNode->mParent->mColor == RecordType::eRed)
845  {
846  RecordType* lUncle = 0;
847  if (lNode->mParent == lNode->mParent->mParent->mLeftChild)
848  {
849  lUncle = lNode->mParent->mParent->mRightChild;
850  }
851  else if (lNode->mParent == lNode->mParent->mParent->mRightChild)
852  {
853  lUncle = lNode->mParent->mParent->mLeftChild;
854  }
855 
856  // since lNode->mParent is red, lNode->mParent->mParent exists
857 
858  if (lUncle && lUncle->mColor == RecordType::eRed)
859  {
860  lNode->mParent->mColor = RecordType::eBlack;
861  lUncle->mColor = RecordType::eBlack;
862  lNode->mParent->mParent->mColor = RecordType::eRed;
863  lNode = lNode->mParent->mParent;
864 
865  lDone = false;
866  }
867  else
868  {
869  if ((lNode == lNode->mParent->mRightChild) &&
870  (lNode->mParent == lNode->mParent->mParent->mLeftChild))
871  {
872  LeftRotate(lNode->mParent);
873  lNode = lNode->mLeftChild;
874  }
875  else if ((lNode == lNode->mParent->mLeftChild) &&
876  (lNode->mParent == lNode->mParent->mParent->mRightChild))
877  {
878  RightRotate(lNode->mParent);
879  lNode = lNode->mRightChild;
880  }
881 
882  lNode->mParent->mColor = RecordType::eBlack;
883  lNode->mParent->mParent->mColor = RecordType::eRed;
884  if ((lNode == lNode->mParent->mLeftChild) &&
885  (lNode->mParent == lNode->mParent->mParent->mLeftChild))
886  {
887  RightRotate(lNode->mParent->mParent);
888  }
889  else
890  {
891  LeftRotate(lNode->mParent->mParent);
892  }
893  }
894  }
895  }
896 
897  mRoot->mColor = RecordType::eBlack;
898  }
899 
900  inline void LeftRotate(RecordType* pNode)
901  {
902  FBX_ASSERT_RETURN(pNode);
903 
904  RecordType* lNode = pNode->mRightChild;
905  FBX_ASSERT_RETURN(lNode);
906 
907  #ifdef _DEBUG
908  RecordType* A = pNode->mLeftChild;
909  RecordType* B = lNode->mLeftChild;
910  RecordType* C = lNode->mRightChild;
911  RecordType* Z = pNode->mParent;
912  #endif
913 
914  pNode->mRightChild = lNode->mLeftChild;
915  if (pNode->mRightChild)
916  {
917  pNode->mRightChild->mParent = pNode;
918  }
919 
920  lNode->mParent = pNode->mParent;
921  if (pNode->mParent == 0)
922  {
923  FBX_ASSERT(mRoot == pNode);
924  mRoot = lNode;
925  }
926  else if (pNode == pNode->mParent->mLeftChild)
927  {
928  pNode->mParent->mLeftChild = lNode;
929  }
930  else
931  {
932  pNode->mParent->mRightChild = lNode;
933  }
934  pNode->mParent = lNode;
935  lNode->mLeftChild = pNode;
936 
937  FBX_ASSERT(pNode->mLeftChild == A);
938  FBX_ASSERT(pNode->mRightChild == B);
939  FBX_ASSERT(pNode->mParent == lNode);
940 
941  FBX_ASSERT(lNode->mLeftChild == pNode);
942  FBX_ASSERT(lNode->mRightChild == C);
943  FBX_ASSERT(lNode->mParent == Z);
944 
945  FBX_ASSERT(A == 0 || A->mParent == pNode);
946  FBX_ASSERT(B == 0 || B->mParent == pNode);
947  FBX_ASSERT(C == 0 || C->mParent == lNode);
948  FBX_ASSERT(Z == 0 || Z->mLeftChild == lNode || Z->mRightChild == lNode);
949  }
950 
951  inline void RightRotate(RecordType* pNode)
952  {
953  RecordType* lNode = pNode->mLeftChild;
954 
955  #ifdef _DEBUG
956  RecordType* A = lNode->mLeftChild;
957  RecordType* B = lNode->mRightChild;
958  RecordType* C = pNode->mRightChild;
959  RecordType* Z = pNode->mParent;
960  #endif
961 
962  pNode->mLeftChild = lNode->mRightChild;
963  if (pNode->mLeftChild)
964  {
965  pNode->mLeftChild->mParent = pNode;
966  }
967 
968  lNode->mParent = pNode->mParent;
969  if (pNode->mParent == 0)
970  {
971  FBX_ASSERT(mRoot == pNode);
972  mRoot = lNode;
973  }
974  else if (pNode == pNode->mParent->mRightChild)
975  {
976  pNode->mParent->mRightChild = lNode;
977  }
978  else
979  {
980  pNode->mParent->mLeftChild = lNode;
981  }
982  pNode->mParent = lNode;
983  lNode->mRightChild = pNode;
984 
985  FBX_ASSERT(lNode->mLeftChild == A);
986  FBX_ASSERT(lNode->mRightChild == pNode);
987  FBX_ASSERT(lNode->mParent == Z);
988 
989  FBX_ASSERT(pNode->mLeftChild == B);
990  FBX_ASSERT(pNode->mRightChild == C);
991  FBX_ASSERT(pNode->mParent == lNode);
992 
993  FBX_ASSERT(A == 0 || A->mParent == lNode);
994  FBX_ASSERT(B == 0 || B->mParent == pNode);
995  FBX_ASSERT(C == 0 || C->mParent == pNode);
996  FBX_ASSERT(Z == 0 || Z->mLeftChild == lNode || Z->mRightChild == lNode);
997  }
998 
999  inline void RemoveNode(RecordType* pNode)
1000  {
1001  if (pNode->mLeftChild == 0)
1002  {
1003  if (pNode->mRightChild == 0)
1004  {
1005  if (pNode->mParent)
1006  {
1007  if (pNode->mParent->mLeftChild == pNode)
1008  {
1009  pNode->mParent->mLeftChild = 0;
1010  }
1011  else if (pNode->mParent->mRightChild == pNode)
1012  {
1013  pNode->mParent->mRightChild = 0;
1014  }
1015  else
1016  {
1017  FBX_ASSERT_NOW("Node not found in FbxRedBlackTree");
1018  }
1019  }
1020  else
1021  {
1022  FBX_ASSERT(mRoot == pNode);
1023  mRoot = 0;
1024  }
1025 
1026  if (pNode->mColor == RecordType::eBlack)
1027  {
1028  FixNodesAfterRemoval(pNode->mParent, 0);
1029  }
1030  }
1031  else
1032  {
1033  if (pNode->mParent)
1034  {
1035  if (pNode->mParent->mLeftChild == pNode)
1036  {
1037  pNode->mParent->mLeftChild = pNode->mRightChild;
1038  pNode->mRightChild->mParent = pNode->mParent;
1039  }
1040  else if (pNode->mParent->mRightChild == pNode)
1041  {
1042  pNode->mParent->mRightChild = pNode->mRightChild;
1043  pNode->mRightChild->mParent = pNode->mParent;
1044  }
1045  else
1046  {
1047  FBX_ASSERT_NOW("Node not found in FbxRedBlackTree");
1048  }
1049  }
1050  else
1051  {
1052  FBX_ASSERT(mRoot == pNode);
1053  mRoot = pNode->mRightChild;
1054  pNode->mRightChild->mParent = 0;
1055  }
1056 
1057  if (pNode->mColor == RecordType::eBlack)
1058  {
1059  FixNodesAfterRemoval(pNode->mRightChild->mParent, pNode->mRightChild);
1060  }
1061  }
1062  }
1063  else
1064  {
1065  if (pNode->mRightChild == 0)
1066  {
1067  if (pNode->mParent)
1068  {
1069  if (pNode->mParent->mLeftChild == pNode)
1070  {
1071  pNode->mParent->mLeftChild = pNode->mLeftChild;
1072  pNode->mLeftChild->mParent = pNode->mParent;
1073  }
1074  else if (pNode->mParent->mRightChild == pNode)
1075  {
1076  pNode->mParent->mRightChild = pNode->mLeftChild;
1077  pNode->mLeftChild->mParent = pNode->mParent;
1078  }
1079  else
1080  {
1081  FBX_ASSERT_NOW("Node not found in FbxRedBlackTree");
1082  }
1083  }
1084  else
1085  {
1086  FBX_ASSERT(mRoot == pNode);
1087  mRoot = pNode->mLeftChild;
1088  pNode->mLeftChild->mParent = 0;
1089  }
1090 
1091  if (pNode->mColor == RecordType::eBlack)
1092  {
1093  FixNodesAfterRemoval(pNode->mLeftChild->mParent, pNode->mLeftChild);
1094  }
1095  }
1096  else
1097  {
1098  RecordType* lMinRightNode = pNode->mRightChild->Minimum();
1099  RemoveNode(lMinRightNode);
1100 
1101  lMinRightNode->mColor = pNode->mColor;
1102  ReplaceNode(pNode, lMinRightNode);
1103  }
1104  }
1105 
1106  pNode->mParent = 0;
1107  pNode->mLeftChild = 0;
1108  pNode->mRightChild = 0;
1109  }
1110 
1111  inline void ReplaceNode(RecordType* pNodeToReplace, RecordType* pReplacement)
1112  {
1113  pReplacement->mParent = pNodeToReplace->mParent;
1114  if (pNodeToReplace->mParent)
1115  {
1116  if (pNodeToReplace->mParent->mLeftChild == pNodeToReplace)
1117  {
1118  pNodeToReplace->mParent->mLeftChild = pReplacement;
1119  }
1120  else if (pNodeToReplace->mParent->mRightChild == pNodeToReplace)
1121  {
1122  pNodeToReplace->mParent->mRightChild = pReplacement;
1123  }
1124  }
1125  else
1126  {
1127  FBX_ASSERT(mRoot == pNodeToReplace);
1128  mRoot = pReplacement;
1129  }
1130 
1131  pReplacement->mLeftChild = pNodeToReplace->mLeftChild;
1132  if (pReplacement->mLeftChild)
1133  {
1134  pReplacement->mLeftChild->mParent = pReplacement;
1135  }
1136 
1137  pReplacement->mRightChild = pNodeToReplace->mRightChild;
1138  if (pReplacement->mRightChild)
1139  {
1140  pReplacement->mRightChild->mParent = pReplacement;
1141  }
1142  }
1143 
1144  inline RecordType* Sibling(const RecordType* pParent, const RecordType* pNode) const
1145  {
1146  if (pParent)
1147  {
1148  if (pParent->mLeftChild == pNode)
1149  {
1150  return pParent->mRightChild;
1151  }
1152  else if (pParent->mRightChild == pNode)
1153  {
1154  return pParent->mLeftChild;
1155  }
1156  }
1157 
1158  return 0;
1159  }
1160 
1161  inline bool IsBlack(const RecordType* pNode)
1162  {
1163  return ((pNode == 0) || (pNode->mColor == RecordType::eBlack));
1164  }
1165 
1166  inline void FixNodesAfterRemoval(RecordType* pParent, RecordType* pNode)
1167  {
1168  RecordType* lParent = pParent;
1169  RecordType* lNode = pNode;
1170  bool lDone = false;
1171 
1172  while (!lDone)
1173  {
1174  lDone = true;
1175 
1176  if (!IsBlack(lNode))
1177  {
1178  lNode->mColor = RecordType::eBlack;
1179  }
1180  else if (lParent != NULL)
1181  {
1182  RecordType* lSibling = Sibling(lParent, lNode);
1183 
1184  if (!IsBlack(lSibling))
1185  {
1186  lParent->mColor = RecordType::eRed;
1187  lSibling->mColor = RecordType::eBlack;
1188  if (lNode == lParent->mLeftChild)
1189  {
1190  LeftRotate(lParent);
1191  }
1192  else
1193  {
1194  RightRotate(lParent);
1195  }
1196 
1197  // update sibling: it may have change after rotation
1198  // parent was not affected by this rotation
1199  lSibling = Sibling(lParent, lNode);
1200  }
1201 
1202  /* check this for null sibling */
1203  if (lSibling &&
1204  IsBlack(lParent) &&
1205  IsBlack(lSibling) &&
1206  IsBlack(lSibling->mLeftChild) &&
1207  IsBlack(lSibling->mRightChild))
1208  {
1209  lSibling->mColor = RecordType::eRed;
1210  lNode = lParent;
1211  lParent = lParent->mParent;
1212  lDone = false;
1213  }
1214  else
1215  {
1216  if (!IsBlack(lParent) &&
1217  IsBlack(lSibling) &&
1218  ((lSibling == 0) || IsBlack(lSibling->mLeftChild)) &&
1219  ((lSibling == 0) || IsBlack(lSibling->mRightChild)))
1220  {
1221  if (lSibling)
1222  {
1223  lSibling->mColor = RecordType::eRed;
1224  }
1225  lParent->mColor = RecordType::eBlack;
1226  }
1227  else if( lSibling != 0 )
1228  {
1229  if ((lNode == lParent->mLeftChild) &&
1230  IsBlack(lSibling) &&
1231  !IsBlack(lSibling->mLeftChild) &&
1232  IsBlack(lSibling->mRightChild))
1233  {
1234  lSibling->mColor = RecordType::eRed;
1235  lSibling->mLeftChild->mColor = RecordType::eBlack;
1236  RightRotate(lSibling);
1237  }
1238  else if ((lNode == lParent->mRightChild) &&
1239  IsBlack(lSibling) &&
1240  IsBlack(lSibling->mLeftChild) &&
1241  !IsBlack(lSibling->mRightChild))
1242  {
1243  lSibling->mColor = RecordType::eRed;
1244  lSibling->mRightChild->mColor = RecordType::eBlack;
1245  LeftRotate(lSibling);
1246  }
1247 
1248  // update sibling: it may have change after rotation
1249  lSibling = Sibling(lParent, lNode);
1250  FBX_ASSERT(lSibling != 0 && lParent != 0); // lSibling is now
1251  // the former red
1252  // child of the
1253  // former sibling
1254 
1255  if( lSibling != 0 && lParent != 0 )
1256  {
1257  lSibling->mColor = lParent->mColor;
1258  lParent->mColor = RecordType::eBlack;
1259  if (lNode == lParent->mLeftChild)
1260  {
1261  if (lSibling->mRightChild)
1262  {
1263  lSibling->mRightChild->mColor = RecordType::eBlack;
1264  }
1265  LeftRotate(lParent);
1266  }
1267  else
1268  {
1269  if (lSibling->mLeftChild)
1270  {
1271  lSibling->mLeftChild->mColor = RecordType::eBlack;
1272  }
1273  RightRotate(lParent);
1274  }
1275  }
1276  }
1277  }
1278  }
1279  }
1280 
1281  if (mRoot)
1282  {
1283  mRoot->mColor = RecordType::eBlack;
1284  }
1285  }
1286 
1287  inline void ClearSubTree(RecordType* pNode)
1288  {
1289  if (pNode)
1290  {
1291  ClearSubTree(pNode->mLeftChild);
1292  ClearSubTree(pNode->mRightChild);
1293  pNode->~RecordType();
1294  mAllocator.FreeMemory(pNode);
1295  }
1296  }
1297 
1298  inline int GetSubTreeSize(RecordType* pNode) const
1299  {
1300  if (pNode)
1301  {
1302  return GetSubTreeSize(pNode->mLeftChild) + GetSubTreeSize(pNode->mRightChild) + 1;
1303  }
1304  else
1305  {
1306  return 0;
1307  }
1308  }
1309 
1310 #if 0
1311  inline void IsSane()
1312  {
1313  FBX_ASSERT((mRoot == 0) || (mRoot->mColor == RecordType::eBlack));
1314  FBX_ASSERT(((mRoot == 0) && (mSize == 0)) || (mRoot != 0) && (mSize != 0));
1315  IsSubTreeSane(mRoot);
1316 
1317  ComputeBlackDepth(mRoot, 0);
1318 
1319  RecordType* lNode = mRoot;
1320  unsigned int lLeafBlackDepth = 0;
1321  while (lNode)
1322  {
1323  if (lNode->mLeftChild == 0)
1324  {
1325  lLeafBlackDepth = lNode->mBlackDepth + ((lNode->mColor == RecordType::eBlack) ? 1 : 0);
1326  }
1327 
1328  lNode = lNode->mLeftChild;
1329  }
1330 
1331  CheckLeavesBlackDepth(mRoot, lLeafBlackDepth);
1332  }
1333 
1334  inline void IsSubTreeSane(const RecordType* pNode) const
1335  {
1336  Compare lCompareKeys;
1337 
1338  if (pNode)
1339  {
1340  FBX_ASSERT(pNode != pNode->mParent);
1341  FBX_ASSERT(pNode != pNode->mLeftChild);
1342  FBX_ASSERT(pNode != pNode->mRightChild);
1343 
1344  // Check for two consecutive red nodes
1345  FBX_ASSERT((pNode->mColor == RecordType::eBlack) ||
1346  (pNode->mLeftChild == NULL) ||
1347  (pNode->mLeftChild->mColor == RecordType::eBlack));
1348 
1349  FBX_ASSERT((pNode->mColor == RecordType::eBlack) ||
1350  (pNode->mRightChild == NULL) ||
1351  (pNode->mRightChild->mColor == RecordType::eBlack));
1352 
1353  // Check key ordering
1354  FBX_ASSERT((pNode->mLeftChild == 0 ||
1355  lCompareKeys(pNode->GetKey(), pNode->mLeftChild->GetKey()) > 0));
1356 
1357  FBX_ASSERT((pNode->mRightChild == 0 ||
1358  lCompareKeys(pNode->GetKey(), pNode->mRightChild->GetKey()) < 0));
1359 
1360  IsSubTreeSane(pNode->mLeftChild);
1361  IsSubTreeSane(pNode->mRightChild);
1362  }
1363  }
1364 
1365  inline void ComputeBlackDepth(RecordType* pNode, unsigned int pDepth)
1366  {
1367  if( pNode )
1368  {
1369  pNode->mBlackDepth = pDepth;
1370  if( pNode->mColor == RecordType::eBlack )
1371  {
1372  pDepth++;
1373  }
1374  ComputeBlackDepth(pNode->mLeftChild, pDepth);
1375  ComputeBlackDepth(pNode->mRightChild, pDepth);
1376  }
1377  }
1378 
1379  inline void CheckLeavesBlackDepth(RecordType* pNode, unsigned int pBlackDepth)
1380  {
1381  if( pNode )
1382  {
1383  if( pNode->mLeftChild == 0 || pNode->mRightChild == 0 )
1384  {
1385  FBX_ASSERT((pNode->mBlackDepth + ((pNode->mColor == RecordType::eBlack) ? 1 : 0)) == pBlackDepth);
1386  }
1387  CheckLeavesBlackDepth(pNode->mLeftChild, pBlackDepth);
1388  CheckLeavesBlackDepth(pNode->mRightChild, pBlackDepth);
1389  }
1390  }
1391 #endif
1392 };
1393 
1394 #endif /* !DOXYGEN_SHOULD_SKIP_THIS *****************************************************************************************/
1395 
1396 #include <fbxsdk/fbxsdk_nsend.h>
1397 
1398 #endif /*_FBXSDK_CORE_BASE_REDBLACKTREE_H_ */
fbxsdk_def.h
FBX SDK environment definition.
NULL
#define NULL
Definition: fbxarch.h:210
fbxsdk_nsbegin.h
FbxPair
This class template holds a pair of objects.
Definition: fbxpair.h:22
fbxsdk_nsend.h
Please send us your comment about this page