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
12//! \file fbxredblacktree.h
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
28template <typename RecordType> class FbxRedBlackConstIterator;
29
30template <typename RecordType> class FbxRedBlackIterator
31{
32public:
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
125protected:
126 RecordType* mRecord;
127
128 friend class FbxRedBlackConstIterator<RecordType>;
129};
130
131template <typename RecordType> class FbxRedBlackConstIterator
132{
133public:
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
227protected:
228 const RecordType* mRecord;
229
230 friend class FbxRedBlackIterator<RecordType>;
231};
232
233//! Implements an efficient ordered data storage.
234template <typename Type, typename Compare, typename Allocator> class FbxRedBlackTree
235{
236public:
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
244 /**
245 This class represents a node in the tree. It contains the key,
246 the value, and internal tree management data.
247 */
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
427public:
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
435 /** Deep copy pTree in this.
436 * \param pTree The tree to copy in this tree. */
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
500 /** Ask Allocator to reserve space to hold pRecordCount elements.
501 * \param pRecordCount
502 */
503 inline void Reserve(unsigned int pRecordCount)
504 {
505 mAllocator.Reserve(pRecordCount);
506 }
507
508 /** Get the number of elements in the tree. Takes O(1) time.
509 * \return The number of elements in the tree.
510 */
511 inline int GetSize() const { return mSize; }
512
513 inline bool Empty() const { return mSize == 0; }
514
515 /** Insert a new element in the tree. Takes O(log n) time.
516 * \param pData The element to insert.
517 * \return If pData.GetKey() is already present in the tree, returns the
518 * existing record and false; else returns the new record and true.
519 */
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
584 /** Remove an element identified by a key from the tree. Takes O(log n) time.
585 * \param pKey The key identifying the element to remove.
586 */
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
621 /** Remove all elements from the tree. Takes O(n) time. Recursive.
622 */
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
636 /** Find the smallest element in the tree.
637 * Takes O(log n) time.
638 */
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
651 /** Find the smallest element in the tree.
652 * Takes O(log n) time.
653 */
654 inline RecordType* Minimum()
655 {
656 if (0 != mRoot)
657 {
658 return mRoot->Minimum();
659 }
660 else
661 {
662 return 0;
663 }
664 }
665
666 /** Find the largest element in the tree.
667 * Takes O(log n) time.
668 */
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
681 /** Find the largest element in the tree.
682 * Takes O(log n) time.
683 */
684 inline RecordType* Maximum()
685 {
686 if (0 != mRoot)
687 {
688 return mRoot->Maximum();
689 }
690 else
691 {
692 return 0;
693 }
694 }
695
696 /** Find the key-value pair with key pKey.
697 * Takes O(log n) time.
698 * \param pKey The key to look for.
699 */
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
723 /** Find the key-value pair with key pKey.
724 * Takes O(log n) time.
725 * \param pKey The key to look for.
726 */
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
750 /** Find the key-value pair with the smallest key greater than pKey.
751 * Takes O(log n) time.
752 * \param pKey The key to look for.
753 */
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
775 /** Find the key-value pair with the smallest key greater than pKey.
776 * Takes O(log n) time.
777 * \param pKey The key to look for.
778 */
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
800protected:
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_ */
1399