- Main Page
- Classes
- Files
- Directories

- Class List
- Class Hierarchy
- Class Members

Classes | Public Types | Public Member Functions | Protected Member Functions | Protected Attributes

# FbxRedBlackTree< Type, Compare, Allocator > Class Template Reference

Search for all occurrences

## Detailed Description

### template<typename Type, typename Compare, typename Allocator>
class FbxRedBlackTree< Type, Compare, Allocator >

Implements an efficient ordered data storage.

Definition at line 190 of file fbxredblacktree.h.

`#include <fbxredblacktree.h>`

List of all members.

## Classes
class | RecordType
| This class represents a node in the tree. More...
## Public Types
typedef Type | DataType
typedef Type::KeyType | KeyType
typedef Type::ConstKeyType | ConstKeyType
typedef Type::ValueType | ValueType
typedef Type::ConstValueType | ConstValueType
typedef Allocator | AllocatorType
typedef FbxRedBlackConstIterator < RecordType > | ConstIteratorType
typedef FbxRedBlackIterator < RecordType > | IteratorType
## Public Member Functions
| FbxRedBlackTree ()
| FbxRedBlackTree (const FbxRedBlackTree &pTree)
| ~FbxRedBlackTree ()
FbxRedBlackTree & | operator= (const FbxRedBlackTree &pTree)
| Deep copy pTree in this.
bool | operator== (const FbxRedBlackTree &pTree) const
void | Reserve (unsigned int pRecordCount)
| Ask Allocator to reserve space to hold pRecordCount elements.
int | GetSize () const
| Get the number of elements in the tree.
bool | Empty () const
FbxPair< RecordType *, bool > | Insert (const DataType &pData)
| Insert a new element in the tree.
bool | Remove (const KeyType &pKey)
| Remove an element identified by a key from the tree.
void | Clear ()
| Remove all elements from the tree.
const RecordType * | Minimum () const
| Find the smallest element in the tree.
RecordType * | Minimum ()
| Find the smallest element in the tree.
const RecordType * | Maximum () const
| Find the largest element in the tree.
RecordType * | Maximum ()
| Find the largest element in the tree.
const RecordType * | Find (const KeyType &pKey) const
| Find the key-value pair with key pKey.
RecordType * | Find (const KeyType &pKey)
| Find the key-value pair with key pKey.
const RecordType * | UpperBound (const KeyType &pKey) const
| Find the key-value pair with the smallest key greater than pKey.
RecordType * | UpperBound (const KeyType &pKey)
| Find the key-value pair with the smallest key greater than pKey.
## Protected Member Functions
void | IsSane ()
| Sanity check on the tree.
void | IsSubTreeSane (const RecordType *pNode) const
void | ComputeBlackDepth (RecordType *pNode, unsigned int pDepth)
void | CheckLeavesBlackDepth (RecordType *pNode, unsigned int pBlackDepth)
RecordType * | DuplicateSubTree (const RecordType *pNode)
void | FixNodesAfterInsertion (RecordType *pNode)
void | LeftRotate (RecordType *pNode)
void | RightRotate (RecordType *pNode)
void | RemoveNode (RecordType *pNode)
void | ReplaceNode (RecordType *pNodeToReplace, RecordType *pReplacement)
RecordType * | Sibling (const RecordType *pParent, const RecordType *pNode) const
bool | IsBlack (const RecordType *pNode)
void | FixNodesAfterRemoval (RecordType *pParent, RecordType *pNode)
void | ClearSubTree (RecordType *pNode)
int | GetSubTreeSize (RecordType *pNode) const
## Protected Attributes
RecordType * | mRoot
int | mSize
AllocatorType | mAllocator

## Member Typedef Documentation

typedef Type DataType

Search for all occurrences

Definition at line 193 of file fbxredblacktree.h.

typedef Type::KeyType KeyType

Search for all occurrences

Definition at line 194 of file fbxredblacktree.h.

typedef Type::ConstKeyType ConstKeyType

Search for all occurrences

Definition at line 195 of file fbxredblacktree.h.

typedef Type::ValueType ValueType

Search for all occurrences

Definition at line 196 of file fbxredblacktree.h.

typedef Type::ConstValueType ConstValueType

Search for all occurrences

Definition at line 197 of file fbxredblacktree.h.

typedef Allocator AllocatorType

Search for all occurrences

Definition at line 198 of file fbxredblacktree.h.

typedef FbxRedBlackConstIterator<RecordType> ConstIteratorType

Search for all occurrences

Definition at line 384 of file fbxredblacktree.h.

typedef FbxRedBlackIterator<RecordType> IteratorType

Search for all occurrences

Definition at line 385 of file fbxredblacktree.h.

## Constructor & Destructor Documentation

FbxRedBlackTree | ( |  | ) | `[inline]`

Definition at line 387 of file fbxredblacktree.h.

    : mRoot(0), mSize(0), mAllocator(sizeof(RecordType)) {}

FbxRedBlackTree | ( | const FbxRedBlackTree< Type, Compare, Allocator > & | pTree | ) | `[inline]`

Definition at line 388 of file fbxredblacktree.h.

    : mRoot(0), mSize(0), mAllocator(sizeof(RecordType)) { operator=(pTree); }

~FbxRedBlackTree | ( |  | ) | `[inline]`

Definition at line 389 of file fbxredblacktree.h.

    { Clear(); }

## Member Function Documentation

FbxRedBlackTree& operator= | ( | const FbxRedBlackTree< Type, Compare, Allocator > & | pTree | ) | `[inline]`

Deep copy pTree in this.

Parameters:

  pTree | The tree to copy in this tree.

Definition at line 393 of file fbxredblacktree.h.

        {
            if( this != &pTree )
            {
                Clear();

                mAllocator = pTree.mAllocator;

                if( pTree.mRoot )
                {
                    void* lBuffer = mAllocator.AllocateRecords();
                    mRoot = new(lBuffer) RecordType(*(pTree.mRoot));    //in-place new won't allocate memory, so it is safe
                    mRoot->mLeftChild = DuplicateSubTree(pTree.mRoot->mLeftChild);
                    mRoot->mRightChild = DuplicateSubTree(pTree.mRoot->mRightChild);

                    if (mRoot->mLeftChild)
                    {
                        mRoot->mLeftChild->mParent = mRoot;
                    }

                    if (mRoot->mRightChild)
                    {
                        mRoot->mRightChild->mParent = mRoot;
                    }
                }
                else
                {
                    FBX_ASSERT( pTree.mSize == 0 );
                    FBX_ASSERT( mRoot == 0 );
                }

                mSize = pTree.mSize;
            }

            return *this;
        }

bool operator== | ( | const FbxRedBlackTree< Type, Compare, Allocator > & | pTree | ) | const`[inline]`

Definition at line 430 of file fbxredblacktree.h.

        {
            // Check a few quick shortcuts
            if( this == &pTree )
                return true;

            if( GetSize() != pTree.GetSize() )
                return false;

            // Iterator through all nodes; if we reach the end of both iterators at the same
            // time then we have two iterators that match.
            ConstIteratorType End;
            ConstIteratorType Iter1(Minimum());
            ConstIteratorType Iter2(pTree.Minimum());

            while( (Iter1 != End) && (Iter2 != End) &&
                   (Iter1->GetKey() == Iter2->GetKey()) &&
                   (Iter1->GetValue() == Iter2->GetValue()) )
            {
                ++Iter1;
                ++Iter2;
            }

            return Iter1 == End && Iter2 == End;
        }

void Reserve | ( | unsigned int | pRecordCount | ) | `[inline]`

Search for all occurrences

Ask Allocator to reserve space to hold pRecordCount elements.

Parameters:

  pRecordCount |

Definition at line 459 of file fbxredblacktree.h.

        {
            mAllocator.Reserve(pRecordCount);
        }

int GetSize | ( |  | ) | const`[inline]`

Search for all occurrences

Get the number of elements in the tree.

Takes O(1) time.

Returns:
  The number of elements in the tree.

Definition at line 467 of file fbxredblacktree.h.

    { return mSize; }

bool Empty | ( |  | ) | const`[inline]`

Search for all occurrences

Definition at line 469 of file fbxredblacktree.h.

    { return mSize == 0; }

FbxPair<RecordType*, bool> Insert | ( | const DataType & | pData | ) | `[inline]`

Search for all occurrences

Insert a new element in the tree.

Takes O(log n) time.

Parameters:

  pData | The element to insert.

Returns:
  If pData.GetKey() is already present in the tree, returns the existing record and false; else returns the new record and true.

Definition at line 476 of file fbxredblacktree.h.

        {
            Compare lCompareKeys;
            bool lResult = false;
            RecordType* lParent = 0;
            RecordType* lNode = mRoot;
            while (lNode != 0)
            {
                const KeyType& lNodeKey = lNode->GetKey();
                const KeyType& lDataKey = pData.GetKey();

                if (lCompareKeys(lNodeKey, lDataKey) < 0)
                {
                    lParent = lNode;
                    lNode = lNode->mRightChild;
                }
                else if (lCompareKeys(lNodeKey, lDataKey) > 0)
                {
                    lParent = lNode;
                    lNode = lNode->mLeftChild;
                }
                else
                {
                    break;
                }
            }

            if (lNode == 0)
            {
                void* lBuffer = mAllocator.AllocateRecords();
                lNode = new(lBuffer) RecordType(pData); //in-place new won't allocate memory, so it is safe
                mSize++;

                FBX_ASSERT(lNode == lBuffer);

                if (lParent)
                {
                    if (lCompareKeys(lParent->GetKey(), pData.GetKey()) < 0)
                    {
                        FBX_ASSERT(lParent->mRightChild == 0);
                        lParent->mRightChild = lNode;
                        lNode->mParent = lParent;
                    }
                    else
                    {
                        FBX_ASSERT(lParent->mLeftChild == 0);
                        lParent->mLeftChild = lNode;
                        lNode->mParent = lParent;
                    }
                }
                else
                {
                    mRoot = lNode;
                }

                // Fix red black tree property
                FixNodesAfterInsertion(lNode);

                lResult = true;
            }

            return FbxPair<RecordType*, bool>(lNode, lResult);
        }

bool Remove | ( | const KeyType & | pKey | ) | `[inline]`

Search for all occurrences

Remove an element identified by a key from the tree.

Takes O(log n) time.

Parameters:

  pKey | The key identifying the element to remove.

Definition at line 543 of file fbxredblacktree.h.

        {
            Compare lCompareKeys;
            bool lResult = false;
            RecordType* lNode = mRoot;
            while (lNode != 0)
            {
                if (lCompareKeys(lNode->GetKey(), pKey) < 0)
                {
                    lNode = lNode->mRightChild;
                }
                else if (lCompareKeys(lNode->GetKey(), pKey) > 0)
                {
                    lNode = lNode->mLeftChild;
                }
                else
                {
                    break;
                }
            }

            if (lNode)
            {
                RemoveNode(lNode);
                mSize--;
                lNode->~RecordType();
                mAllocator.FreeMemory(lNode);

                lResult = true;
            }

            return lResult;
        }

void Clear | ( |  | ) | `[inline]`

Search for all occurrences

Remove all elements from the tree.

Takes O(n) time. Recursive.

Definition at line 579 of file fbxredblacktree.h.

        {
            if (mRoot)
            {
                ClearSubTree(mRoot->mLeftChild);
                ClearSubTree(mRoot->mRightChild);
                mRoot->~RecordType();
                mAllocator.FreeMemory(mRoot);
                mRoot = 0;
                mSize = 0;
            }
        }

const RecordType* Minimum | ( |  | ) | const`[inline]`

Search for all occurrences

Find the smallest element in the tree.

Takes O(log n) time.

Definition at line 595 of file fbxredblacktree.h.

        {
            if (0 != mRoot)
            {
                return mRoot->Minimum();
            }
            else
            {
                return 0;
            }
        }

RecordType* Minimum | ( |  | ) | `[inline]`

Search for all occurrences

Find the smallest element in the tree.

Takes O(log n) time.

Definition at line 610 of file fbxredblacktree.h.

        {
            if (0 != mRoot)
            {
                return mRoot->Minimum();
            }
            else
            {
                return 0;
            }
        }

const RecordType* Maximum | ( |  | ) | const`[inline]`

Search for all occurrences

Find the largest element in the tree.

Takes O(log n) time.

Definition at line 625 of file fbxredblacktree.h.

        {
            if (0 != mRoot)
            {
                return mRoot->Maximum();
            }
            else
            {
                return 0;
            }
        }

RecordType* Maximum | ( |  | ) | `[inline]`

Search for all occurrences

Find the largest element in the tree.

Takes O(log n) time.

Definition at line 640 of file fbxredblacktree.h.

        {
            if (0 != mRoot)
            {
                return mRoot->Maximum();
            }
            else
            {
                return 0;
            }
        }

const RecordType* Find | ( | const KeyType & | pKey | ) | const`[inline]`

Search for all occurrences

Find the key-value pair with key pKey.

Takes O(log n) time.

Parameters:

  pKey | The key to look for.

Definition at line 656 of file fbxredblacktree.h.

        {
            Compare lCompareKeys;
            const RecordType* lNode = mRoot;
            while (lNode != 0)
            {
                if (lCompareKeys(lNode->GetKey(), pKey) < 0)
                {
                    lNode = lNode->mRightChild;
                }
                else if (lCompareKeys(lNode->GetKey(), pKey) > 0)
                {
                    lNode = lNode->mLeftChild;
                }
                else
                {
                    break;
                }
            }

            return lNode;
        }

RecordType* Find | ( | const KeyType & | pKey | ) | `[inline]`

Search for all occurrences

Find the key-value pair with key pKey.

Takes O(log n) time.

Parameters:

  pKey | The key to look for.

Definition at line 683 of file fbxredblacktree.h.

        {
            Compare lCompareKeys;
            RecordType* lNode = mRoot;
            while (lNode != 0)
            {
                if (lCompareKeys(lNode->GetKey(), pKey) < 0)
                {
                    lNode = lNode->mRightChild;
                }
                else if (lCompareKeys(lNode->GetKey(), pKey) > 0)
                {
                    lNode = lNode->mLeftChild;
                }
                else
                {
                    break;
                }
            }

            return lNode;
        }

const RecordType* UpperBound | ( | const KeyType & | pKey | ) | const`[inline]`

Search for all occurrences

Find the key-value pair with the smallest key greater than pKey.

Takes O(log n) time.

Parameters:

  pKey | The key to look for.

Definition at line 710 of file fbxredblacktree.h.

        {
            Compare lCompareKeys;
            const RecordType* lNode = mRoot;
            const RecordType* lCandidate = 0;
            while (lNode != 0)
            {
                if (lCompareKeys(lNode->GetKey(), pKey) <= 0)
                {
                    lNode = lNode->mRightChild;
                }
                else if (lCompareKeys(lNode->GetKey(), pKey) > 0)
                {
                    lCandidate = lNode;
                    lNode = lNode->mLeftChild;
                }
            }

            return lCandidate;
        }

RecordType* UpperBound | ( | const KeyType & | pKey | ) | `[inline]`

Search for all occurrences

Find the key-value pair with the smallest key greater than pKey.

Takes O(log n) time.

Parameters:

  pKey | The key to look for.

Definition at line 735 of file fbxredblacktree.h.

        {
            Compare lCompareKeys;
            RecordType* lNode = mRoot;
            RecordType* lCandidate = 0;
            while (lNode != 0)
            {
                if (lCompareKeys(lNode->GetKey(), pKey) <= 0)
                {
                    lNode = lNode->mRightChild;
                }
                else if (lCompareKeys(lNode->GetKey(), pKey) > 0)
                {
                    lCandidate = lNode;
                    lNode = lNode->mLeftChild;
                }
            }

            return lCandidate;
        }

void IsSane | ( |  | ) | `[inline, protected]`

Search for all occurrences

Sanity check on the tree.

Check if all red-black tree properties hold. Also check if all key-values pairs are ordered properly.

Definition at line 766 of file fbxredblacktree.h.

        {
            FBX_ASSERT((mRoot == 0) || (mRoot->mColor == RecordType::eBlack));
            FBX_ASSERT(((mRoot == 0) && (mSize == 0)) || (mRoot != 0) && (mSize != 0));
            IsSubTreeSane(mRoot);

            ComputeBlackDepth(mRoot, 0);

            RecordType* lNode = mRoot;
            unsigned int lLeafBlackDepth = 0;
            while (lNode)
            {
                if (lNode->mLeftChild == 0)
                {
                    lLeafBlackDepth = lNode->mBlackDepth + ((lNode->mColor == RecordType::eBlack) ? 1 : 0);
                }

                lNode = lNode->mLeftChild;
            }

            CheckLeavesBlackDepth(mRoot, lLeafBlackDepth);
        }

void IsSubTreeSane | ( | const RecordType * | pNode | ) | const`[inline, protected]`

Search for all occurrences

Definition at line 789 of file fbxredblacktree.h.

        {
            Compare lCompareKeys;

            if (pNode)
            {
                FBX_ASSERT(pNode != pNode->mParent);
                FBX_ASSERT(pNode != pNode->mLeftChild);
                FBX_ASSERT(pNode != pNode->mRightChild);

                // Check for two consecutive red nodes
                FBX_ASSERT((pNode->mColor == RecordType::eBlack) ||
                         (pNode->mLeftChild == NULL) ||
                         (pNode->mLeftChild->mColor == RecordType::eBlack));

                FBX_ASSERT((pNode->mColor == RecordType::eBlack) ||
                         (pNode->mRightChild == NULL) ||
                         (pNode->mRightChild->mColor == RecordType::eBlack));

                // Check key ordering
                FBX_ASSERT((pNode->mLeftChild == 0 ||
                          lCompareKeys(pNode->GetKey(), pNode->mLeftChild->GetKey()) > 0));

                FBX_ASSERT((pNode->mRightChild == 0 ||
                          lCompareKeys(pNode->GetKey(), pNode->mRightChild->GetKey()) < 0));

                IsSubTreeSane(pNode->mLeftChild);
                IsSubTreeSane(pNode->mRightChild);
            }
        }

void ComputeBlackDepth | ( | RecordType * | pNode,
|  | unsigned int | pDepth
| ) |  | `[inline, protected]`

Search for all occurrences

Definition at line 820 of file fbxredblacktree.h.

        {
            if (pNode)
            {
                pNode->mBlackDepth = pDepth;
                if (pNode->mColor == RecordType::eBlack)
                {
                    pDepth++;
                }

                ComputeBlackDepth(pNode->mLeftChild, pDepth);
                ComputeBlackDepth(pNode->mRightChild, pDepth);
            }
        }

void CheckLeavesBlackDepth | ( | RecordType * | pNode,
|  | unsigned int | pBlackDepth
| ) |  | `[inline, protected]`

Search for all occurrences

Definition at line 835 of file fbxredblacktree.h.

        {
            if (pNode)
            {
                if ((pNode->mLeftChild == 0) || pNode->mRightChild == 0)
                {
                    int lBlackDepth = pNode->mBlackDepth + ((pNode->mColor == RecordType::eBlack) ? 1 : 0);
                    FBX_ASSERT(lBlackDepth == pBlackDepth);
                }

                CheckLeavesBlackDepth(pNode->mLeftChild, pBlackDepth);
                CheckLeavesBlackDepth(pNode->mRightChild, pBlackDepth);
            }
        }

RecordType* DuplicateSubTree | ( | const RecordType * | pNode | ) | `[inline, protected]`

Search for all occurrences

Definition at line 850 of file fbxredblacktree.h.

        {
            RecordType* lNewSubTree = 0;

            if (pNode)
            {
                void* lBuffer = mAllocator.AllocateRecords();
                lNewSubTree = new(lBuffer) RecordType(*pNode);  //in-place new won't allocate memory, so it is safe
                lNewSubTree->mLeftChild = DuplicateSubTree(pNode->mLeftChild);
                lNewSubTree->mRightChild = DuplicateSubTree(pNode->mRightChild);

                if (lNewSubTree->mLeftChild)
                {
                    lNewSubTree->mLeftChild->mParent = lNewSubTree;
                }

                if (lNewSubTree->mRightChild)
                {
                    lNewSubTree->mRightChild->mParent = lNewSubTree;
                }
            }

            return lNewSubTree;
        }

void FixNodesAfterInsertion | ( | RecordType * | pNode | ) | `[inline, protected]`

Search for all occurrences

Definition at line 875 of file fbxredblacktree.h.

        {
            RecordType* lNode = pNode;
            bool lDone = false;

            while (!lDone)
            {
                lDone = true;

                if (lNode->mParent == 0)
                {
                    lNode->mColor = RecordType::eBlack;
                }
                else if (lNode->mParent->mColor == RecordType::eRed)
                {
                    RecordType* lUncle = 0;
                    if (lNode->mParent == lNode->mParent->mParent->mLeftChild)
                    {
                        lUncle = lNode->mParent->mParent->mRightChild;
                    }
                    else if (lNode->mParent == lNode->mParent->mParent->mRightChild)
                    {
                        lUncle = lNode->mParent->mParent->mLeftChild;
                    }

                    // since lNode->mParent is red, lNode->mParent->mParent exists

                    if (lUncle && lUncle->mColor == RecordType::eRed)
                    {
                        lNode->mParent->mColor = RecordType::eBlack;
                        lUncle->mColor = RecordType::eBlack;
                        lNode->mParent->mParent->mColor = RecordType::eRed;
                        lNode = lNode->mParent->mParent;

                        lDone = false;
                    }
                    else
                    {
                        if ((lNode == lNode->mParent->mRightChild) &&
                            (lNode->mParent == lNode->mParent->mParent->mLeftChild))
                        {
                            LeftRotate(lNode->mParent);
                            lNode = lNode->mLeftChild;
                        }
                        else if ((lNode == lNode->mParent->mLeftChild) &&
                                (lNode->mParent == lNode->mParent->mParent->mRightChild))
                        {
                            RightRotate(lNode->mParent);
                            lNode = lNode->mRightChild;
                        }

                        lNode->mParent->mColor = RecordType::eBlack;
                        lNode->mParent->mParent->mColor = RecordType::eRed;
                        if ((lNode == lNode->mParent->mLeftChild) &&
                            (lNode->mParent == lNode->mParent->mParent->mLeftChild))
                        {
                            RightRotate(lNode->mParent->mParent);
                        }
                        else
                        {
                            LeftRotate(lNode->mParent->mParent);
                        }
                    }
                }
            }

            mRoot->mColor = RecordType::eBlack;
        }

void LeftRotate | ( | RecordType * | pNode | ) | `[inline, protected]`

Search for all occurrences

Definition at line 944 of file fbxredblacktree.h.

        {
            RecordType* lNode = pNode->mRightChild;

        #ifdef _DEBUG
            RecordType* A = pNode->mLeftChild;
            RecordType* B = lNode->mLeftChild;
            RecordType* C = lNode->mRightChild;
            RecordType* Z = pNode->mParent;
        #endif

            pNode->mRightChild = lNode->mLeftChild;
            if (pNode->mRightChild)
            {
                pNode->mRightChild->mParent = pNode;
            }

            lNode->mParent = pNode->mParent;
            if (pNode->mParent == 0)
            {
                FBX_ASSERT(mRoot == pNode);
                mRoot = lNode;
            }
            else if (pNode == pNode->mParent->mLeftChild)
            {
                pNode->mParent->mLeftChild = lNode;
            }
            else
            {
                pNode->mParent->mRightChild = lNode;
            }
            pNode->mParent = lNode;
            lNode->mLeftChild = pNode;

            FBX_ASSERT(pNode->mLeftChild == A);
            FBX_ASSERT(pNode->mRightChild == B);
            FBX_ASSERT(pNode->mParent == lNode);

            FBX_ASSERT(lNode->mLeftChild == pNode);
            FBX_ASSERT(lNode->mRightChild == C);
            FBX_ASSERT(lNode->mParent == Z);

            FBX_ASSERT(A == 0 || A->mParent == pNode);
            FBX_ASSERT(B == 0 || B->mParent == pNode);
            FBX_ASSERT(C == 0 || C->mParent == lNode);
            FBX_ASSERT(Z == 0 || Z->mLeftChild == lNode || Z->mRightChild == lNode);
        }

void RightRotate | ( | RecordType * | pNode | ) | `[inline, protected]`

Search for all occurrences

Definition at line 992 of file fbxredblacktree.h.

        {
            RecordType* lNode = pNode->mLeftChild;

        #ifdef _DEBUG
            RecordType* A = lNode->mLeftChild;
            RecordType* B = lNode->mRightChild;
            RecordType* C = pNode->mRightChild;
            RecordType* Z = pNode->mParent;
        #endif

            pNode->mLeftChild = lNode->mRightChild;
            if (pNode->mLeftChild)
            {
                pNode->mLeftChild->mParent = pNode;
            }

            lNode->mParent = pNode->mParent;
            if (pNode->mParent == 0)
            {
                FBX_ASSERT(mRoot == pNode);
                mRoot = lNode;
            }
            else if (pNode == pNode->mParent->mRightChild)
            {
                pNode->mParent->mRightChild = lNode;
            }
            else
            {
                pNode->mParent->mLeftChild = lNode;
            }
            pNode->mParent = lNode;
            lNode->mRightChild = pNode;

            FBX_ASSERT(lNode->mLeftChild == A);
            FBX_ASSERT(lNode->mRightChild == pNode);
            FBX_ASSERT(lNode->mParent == Z);

            FBX_ASSERT(pNode->mLeftChild == B);
            FBX_ASSERT(pNode->mRightChild == C);
            FBX_ASSERT(pNode->mParent == lNode);

            FBX_ASSERT(A == 0 || A->mParent == lNode);
            FBX_ASSERT(B == 0 || B->mParent == pNode);
            FBX_ASSERT(C == 0 || C->mParent == pNode);
            FBX_ASSERT(Z == 0 || Z->mLeftChild == lNode || Z->mRightChild == lNode);
        }

void RemoveNode | ( | RecordType * | pNode | ) | `[inline, protected]`

Search for all occurrences

Definition at line 1040 of file fbxredblacktree.h.

        {
            if (pNode->mLeftChild == 0)
            {
                if (pNode->mRightChild == 0)
                {
                    if (pNode->mParent)
                    {
                        if (pNode->mParent->mLeftChild == pNode)
                        {
                            pNode->mParent->mLeftChild = 0;
                        }
                        else if (pNode->mParent->mRightChild == pNode)
                        {
                            pNode->mParent->mRightChild = 0;
                        }
                        else
                        {
                            FBX_ASSERT_NOW("Node not found in FbxRedBlackTree");
                        }
                    }
                    else
                    {
                        FBX_ASSERT(mRoot == pNode);
                        mRoot = 0;
                    }

                    if (pNode->mColor == RecordType::eBlack)
                    {
                        FixNodesAfterRemoval(pNode->mParent, 0);
                    }
                }
                else
                {
                    if (pNode->mParent)
                    {
                        if (pNode->mParent->mLeftChild == pNode)
                        {
                            pNode->mParent->mLeftChild = pNode->mRightChild;
                            pNode->mRightChild->mParent = pNode->mParent;
                        }
                        else if (pNode->mParent->mRightChild == pNode)
                        {
                            pNode->mParent->mRightChild = pNode->mRightChild;
                            pNode->mRightChild->mParent = pNode->mParent;
                        }
                        else
                        {
                            FBX_ASSERT_NOW("Node not found in FbxRedBlackTree");
                        }
                    }
                    else
                    {
                        FBX_ASSERT(mRoot == pNode);
                        mRoot = pNode->mRightChild;
                        pNode->mRightChild->mParent = 0;
                    }

                    if (pNode->mColor == RecordType::eBlack)
                    {
                        FixNodesAfterRemoval(pNode->mRightChild->mParent, pNode->mRightChild);
                    }
                }
            }
            else
            {
                if (pNode->mRightChild == 0)
                {
                    if (pNode->mParent)
                    {
                        if (pNode->mParent->mLeftChild == pNode)
                        {
                            pNode->mParent->mLeftChild = pNode->mLeftChild;
                            pNode->mLeftChild->mParent = pNode->mParent;
                        }
                        else if (pNode->mParent->mRightChild == pNode)
                        {
                            pNode->mParent->mRightChild = pNode->mLeftChild;
                            pNode->mLeftChild->mParent = pNode->mParent;
                        }
                        else
                        {
                            FBX_ASSERT_NOW("Node not found in FbxRedBlackTree");
                        }
                    }
                    else
                    {
                        FBX_ASSERT(mRoot == pNode);
                        mRoot = pNode->mLeftChild;
                        pNode->mLeftChild->mParent = 0;
                    }

                    if (pNode->mColor == RecordType::eBlack)
                    {
                        FixNodesAfterRemoval(pNode->mLeftChild->mParent, pNode->mLeftChild);
                    }
                }
                else
                {
                    RecordType* lMinRightNode = pNode->mRightChild->Minimum();
                    RemoveNode(lMinRightNode);

                    lMinRightNode->mColor = pNode->mColor;
                    ReplaceNode(pNode, lMinRightNode);
                }
            }

            pNode->mParent = 0;
            pNode->mLeftChild = 0;
            pNode->mRightChild = 0;
        }

void ReplaceNode | ( | RecordType * | pNodeToReplace,
|  | RecordType * | pReplacement
| ) |  | `[inline, protected]`

Search for all occurrences

Definition at line 1152 of file fbxredblacktree.h.

        {
            pReplacement->mParent = pNodeToReplace->mParent;
            if (pNodeToReplace->mParent)
            {
                if (pNodeToReplace->mParent->mLeftChild == pNodeToReplace)
                {
                    pNodeToReplace->mParent->mLeftChild = pReplacement;
                }
                else if (pNodeToReplace->mParent->mRightChild == pNodeToReplace)
                {
                    pNodeToReplace->mParent->mRightChild = pReplacement;
                }
            }
            else
            {
                FBX_ASSERT(mRoot == pNodeToReplace);
                mRoot = pReplacement;
            }

            pReplacement->mLeftChild = pNodeToReplace->mLeftChild;
            if (pReplacement->mLeftChild)
            {
                pReplacement->mLeftChild->mParent = pReplacement;
            }

            pReplacement->mRightChild = pNodeToReplace->mRightChild;
            if (pReplacement->mRightChild)
            {
                pReplacement->mRightChild->mParent = pReplacement;
            }
        }

RecordType* Sibling | ( | const RecordType * | pParent,
|  | const RecordType * | pNode
| ) |  | const`[inline, protected]`

Search for all occurrences

Definition at line 1185 of file fbxredblacktree.h.

        {
            if (pParent)
            {
                if (pParent->mLeftChild == pNode)
                {
                    return pParent->mRightChild;
                }
                else if (pParent->mRightChild == pNode)
                {
                    return pParent->mLeftChild;
                }
            }

            return 0;
        }

bool IsBlack | ( | const RecordType * | pNode | ) | `[inline, protected]`

Search for all occurrences

Definition at line 1202 of file fbxredblacktree.h.

        {
            return ((pNode == 0) || (pNode->mColor == RecordType::eBlack));
        }

void FixNodesAfterRemoval | ( | RecordType * | pParent,
|  | RecordType * | pNode
| ) |  | `[inline, protected]`

Search for all occurrences

Definition at line 1207 of file fbxredblacktree.h.

        {
            RecordType* lParent = pParent;
            RecordType* lNode = pNode;
            bool lDone = false;

            while (!lDone)
            {
                lDone = true;

                if (!IsBlack(lNode))
                {
                    lNode->mColor = RecordType::eBlack;
                }
                else if (lParent != NULL)
                {
                    RecordType* lSibling = Sibling(lParent, lNode);

                    if (!IsBlack(lSibling))
                    {
                        lParent->mColor = RecordType::eRed;
                        lSibling->mColor = RecordType::eBlack;
                        if (lNode == lParent->mLeftChild)
                        {
                            LeftRotate(lParent);
                        }
                        else
                        {
                            RightRotate(lParent);
                        }

                        // update sibling: it may have change after rotation
                        // parent was not affected by this rotation
                        lSibling = Sibling(lParent, lNode);
                    }

                    /* check this for null sibling */
                    if (lSibling &&
                        IsBlack(lParent) &&
                        IsBlack(lSibling) &&
                        IsBlack(lSibling->mLeftChild) &&
                        IsBlack(lSibling->mRightChild))
                    {
                        lSibling->mColor = RecordType::eRed;
                        lNode = lParent;
                        lParent = lParent->mParent;
                        lDone = false;
                    }
                    else
                    {
                        if (!IsBlack(lParent) &&
                            IsBlack(lSibling) &&
                            ((lSibling == 0) || IsBlack(lSibling->mLeftChild)) &&
                            ((lSibling == 0) || IsBlack(lSibling->mRightChild)))
                        {
                            if (lSibling)
                            {
                                lSibling->mColor = RecordType::eRed;
                            }
                            lParent->mColor = RecordType::eBlack;
                        }
                        else // lSibling != 0
                        {
                            if ((lNode == lParent->mLeftChild) &&
                                IsBlack(lSibling) &&
                                !IsBlack(lSibling->mLeftChild) &&
                                IsBlack(lSibling->mRightChild))
                            {
                                lSibling->mColor = RecordType::eRed;
                                lSibling->mLeftChild->mColor = RecordType::eBlack;
                                RightRotate(lSibling);
                            }
                            else if ((lNode == lParent->mRightChild) &&
                                     IsBlack(lSibling) &&
                                     IsBlack(lSibling->mLeftChild) &&
                                     !IsBlack(lSibling->mRightChild))
                            {
                                lSibling->mColor = RecordType::eRed;
                                lSibling->mRightChild->mColor = RecordType::eBlack;
                                LeftRotate(lSibling);
                            }

                            // update sibling: it may have change after rotation
                            lSibling = Sibling(lParent, lNode);
                            FBX_ASSERT(lSibling != 0); // lSibling is now
                                                     // the former red
                                                     // child of the
                                                     // former sibling

                            lSibling->mColor = lParent->mColor;
                            lParent->mColor = RecordType::eBlack;
                            if (lNode == lParent->mLeftChild)
                            {
                                if (lSibling->mRightChild)
                                {
                                    lSibling->mRightChild->mColor = RecordType::eBlack;
                                }
                                LeftRotate(lParent);
                            }
                            else
                            {
                                if (lSibling->mLeftChild)
                                {
                                    lSibling->mLeftChild->mColor = RecordType::eBlack;
                                }
                                RightRotate(lParent);
                            }
                        }
                    }
                }
            }

            if (mRoot)
            {
                mRoot->mColor = RecordType::eBlack;
            }
        }

void ClearSubTree | ( | RecordType * | pNode | ) | `[inline, protected]`

Search for all occurrences

Definition at line 1325 of file fbxredblacktree.h.

        {
            if (pNode)
            {
                ClearSubTree(pNode->mLeftChild);
                ClearSubTree(pNode->mRightChild);
                pNode->~RecordType();
                mAllocator.FreeMemory(pNode);
            }
        }

int GetSubTreeSize | ( | RecordType * | pNode | ) | const`[inline, protected]`

Search for all occurrences

Definition at line 1336 of file fbxredblacktree.h.

        {
            if (pNode)
            {
                return GetSubTreeSize(pNode->mLeftChild) + GetSubTreeSize(pNode->mRightChild) + 1;
            }
            else
            {
                return 0;
            }
        }

## Member Data Documentation

RecordType* mRoot`[protected]`

Search for all occurrences

Definition at line 757 of file fbxredblacktree.h.

int mSize`[protected]`

Search for all occurrences

Definition at line 758 of file fbxredblacktree.h.

AllocatorType mAllocator`[protected]`

Search for all occurrences

Definition at line 760 of file fbxredblacktree.h.

The documentation for this class was generated from the following file:

- fbxsdk/core/base/fbxredblacktree.h