fbxredblacktree.h

Go to the documentation of this file.

/****************************************************************************************
 
   Copyright (C) 2015 Autodesk, Inc.
   All rights reserved.
 
   Use of this software is subject to the terms of the Autodesk license agreement
   provided at the time of installation or download, or which otherwise accompanies
   this software in either electronic or hard copy form.
 
****************************************************************************************/

#ifndef _FBXSDK_CORE_BASE_REDBLACKTREE_H_
#define _FBXSDK_CORE_BASE_REDBLACKTREE_H_

#include <fbxsdk/fbxsdk_def.h>

#include <fbxsdk/core/base/fbxcontainerallocators.h>
#include <fbxsdk/core/base/fbxpair.h>

#include <fbxsdk/fbxsdk_nsbegin.h>

/*****************************************************************************************************************************
** WARNING! Anything beyond these lines is for internal use, may not be documented and is subject to change without notice! **
*****************************************************************************************************************************/
#ifndef DOXYGEN_SHOULD_SKIP_THIS

template <typename RecordType> class FbxRedBlackConstIterator;

template <typename RecordType> class FbxRedBlackIterator
{
public:
    FbxRedBlackIterator() : mRecord(0) {}
    FbxRedBlackIterator(RecordType* pRecord) : mRecord(pRecord) {}
    FbxRedBlackIterator(const FbxRedBlackIterator<RecordType>& pV) : mRecord(pV.mRecord) {}

    FbxRedBlackIterator& operator++()
    {
        FBX_ASSERT( mRecord != NULL );
        mRecord = mRecord->Successor();
        return *this;
    }

    const FbxRedBlackIterator operator++(int)
    {
        FbxRedBlackIterator t(*this);
        operator++();
        return t;
    }

    FbxRedBlackIterator& operator+=(int pCount)
    {
        FBX_ASSERT( mRecord != NULL );
        for( int i = 0; i < pCount; ++i )
        {
            if( !mRecord ) break;
            mRecord = mRecord->Successor();
        }
        return *this;
    }

    FbxRedBlackIterator& operator--()
    {
        FBX_ASSERT( mRecord );
        mRecord = mRecord->Predecessor();
        return *this;
    }

    const FbxRedBlackIterator operator--(int)
    {
        FbxRedBlackIterator t(*this);
        operator--();
        return t;
    }

    FbxRedBlackIterator& operator-=(int pCount)
    {
        FBX_ASSERT( mRecord != NULL );
        for( int i = 0; i < pCount; ++i )
        {
            if( !mRecord ) break;
            mRecord = mRecord->Predecessor();
        }
        return *this;
    }

    const RecordType& operator*() const
    {
        FBX_ASSERT( mRecord );

        return *mRecord;
    }

    RecordType& operator*()
    {
        FBX_ASSERT( mRecord );

        return *mRecord;
    }

    const RecordType* operator->() const
    {
        FBX_ASSERT( mRecord );

        return mRecord;
    }

    RecordType* operator->()
    {
        FBX_ASSERT( mRecord );

        return mRecord;
    }

    inline bool operator==(const FbxRedBlackIterator& pOther) const
    {
        return mRecord == pOther.mRecord;
    }

    inline bool operator !=(const FbxRedBlackIterator& pOther) const
    {
        return mRecord != pOther.mRecord;
    }

protected:
    RecordType* mRecord;

    friend class FbxRedBlackConstIterator<RecordType>;
};

template <typename RecordType> class FbxRedBlackConstIterator
{
public:
    FbxRedBlackConstIterator() : mRecord(0) {}
    FbxRedBlackConstIterator(const RecordType* pRecord) : mRecord(pRecord) {}
    FbxRedBlackConstIterator(const FbxRedBlackIterator<RecordType>& pV) : mRecord(pV.mRecord) {}
    FbxRedBlackConstIterator(const FbxRedBlackConstIterator<RecordType>& pV) : mRecord(pV.mRecord) {}

    FbxRedBlackConstIterator & operator++()
    {
        FBX_ASSERT( mRecord != NULL );
        mRecord = mRecord->Successor();
        return *this;
    }

    const FbxRedBlackConstIterator operator++(int)
    {
        FbxRedBlackConstIterator t(*this);
        operator++();
        return t;
    }

    FbxRedBlackConstIterator& operator+=(int pCount)
    {
        FBX_ASSERT( mRecord != NULL );
        for( int i = 0; i < pCount; ++i )
        {
            if( !mRecord ) break;
            mRecord = mRecord->Successor();
        }
        return *this;
    }

    FbxRedBlackConstIterator & operator--()
    {
        FBX_ASSERT( mRecord );
        mRecord = mRecord->Predecessor();
        return *this;
    }

    const FbxRedBlackConstIterator operator--(int)
    {
        FbxRedBlackConstIterator t(*this);
        operator--();
        return t;
    }

    FbxRedBlackConstIterator& operator-=(int pCount)
    {
        FBX_ASSERT( mRecord != NULL );
        for( int i = 0; i < pCount; ++i )
        {
            if( !mRecord ) break;
            mRecord = mRecord->Predecessor();
        }
        return *this;
    }

    const RecordType& operator*() const
    {
        FBX_ASSERT( mRecord );

        return *mRecord;
    }

    const RecordType& operator*()
    {
        FBX_ASSERT( mRecord );

        return *mRecord;
    }

    const RecordType* operator->() const
    {
        FBX_ASSERT( mRecord );

        return mRecord;
    }

    const RecordType* operator->()
    {
        FBX_ASSERT( mRecord );

        return mRecord;
    }

    inline bool operator==(const FbxRedBlackConstIterator& pOther) const
    {
        return mRecord == pOther.mRecord;
    }

    inline bool operator !=(const FbxRedBlackConstIterator& pOther) const
    {
        return mRecord != pOther.mRecord;
    }

protected:
    const RecordType* mRecord;

    friend class FbxRedBlackIterator<RecordType>;
};

template <typename Type, typename Compare, typename Allocator> class FbxRedBlackTree
{
public:
    typedef Type DataType;
    typedef typename Type::KeyType         KeyType;
    typedef typename Type::ConstKeyType    ConstKeyType;
    typedef typename Type::ValueType       ValueType;
    typedef typename Type::ConstValueType  ConstValueType;
    typedef Allocator AllocatorType;

    class RecordType
    {
    public:
        inline ConstKeyType& GetKey() const { return mData.GetKey(); }
        inline ConstValueType& GetValue() const { return mData.GetValue(); }
        inline ValueType& GetValue() { return mData.GetValue(); }

        inline const RecordType* Minimum() const
        {
            const RecordType* lParent = 0;
            const RecordType* lNode = this;
            while (lNode != 0)
            {
                lParent = lNode;
                lNode = lNode->mLeftChild;
            }

            return lParent;
        }

        inline RecordType* Minimum()
        {
            RecordType* lParent = 0;
            RecordType* lNode = this;
            while (lNode != 0)
            {
                lParent = lNode;
                lNode = lNode->mLeftChild;
            }

            return lParent;
        }

        inline const RecordType* Maximum() const
        {
            const RecordType* lParent = 0;
            const RecordType* lNode = this;
            while (lNode != 0)
            {
                lParent = lNode;
                lNode = lNode->mRightChild;
            }

            return lParent;
        }

        inline RecordType* Maximum()
        {
            RecordType* lParent = 0;
            RecordType* lNode = this;
            while (lNode != 0)
            {
                lParent = lNode;
                lNode = lNode->mRightChild;
            }

            return lParent;
        }

        inline const RecordType* Predecessor() const
        {
            if (mLeftChild)
            {
                return mLeftChild->Maximum();
            }
            else
            {
                const RecordType* lParent = mParent;
                const RecordType* lNode = this;

                while (lParent && lParent->mLefttChild == lNode)
                {
                    lNode = lParent;
                    lParent = lParent->mParent;
                }

                return lParent;
            }
        }

        inline RecordType* Predecessor()
        {
            if (mLeftChild)
            {
                return mLeftChild->Maximum();
            }
            else
            {
                RecordType* lParent = mParent;
                RecordType* lNode = this;

                while (lParent && lParent->mLeftChild == lNode)
                {
                    lNode = lParent;
                    lParent = lParent->mParent;
                }

                return lParent;
            }
        }

        inline const RecordType* Successor() const
        {
            if (mRightChild)
            {
                return mRightChild->Minimum();
            }
            else
            {
                const RecordType* lParent = mParent;
                const RecordType* lNode = this;

                while (lParent && lParent->mRightChild == lNode)
                {
                    lNode = lParent;
                    lParent = lParent->mParent;
                }

                return lParent;
            }
        }

        inline RecordType* Successor()
        {
            if (mRightChild)
            {
                return mRightChild->Minimum();
            }
            else
            {
                RecordType* lParent = mParent;
                RecordType* lNode = this;

                while (lParent && lParent->mRightChild == lNode)
                {
                    lNode = lParent;
                    lParent = lParent->mParent;
                }

                return lParent;
            }
        }

        inline int GetBlackDepth() { return mBlackDepth; }

    private:
        enum ETreeType {eRed, eBlack};

        inline RecordType(const DataType& pData)
            : mData(pData)
            , mParent(0)
            , mLeftChild(0)
            , mRightChild(0)
            , mColor(eRed)
            , mBlackDepth(0)
        {
        }

        inline RecordType(const RecordType& pRecordType)
            : mData(pRecordType.mData)
            , mParent(0)
            , mLeftChild(0)
            , mRightChild(0)
            , mColor(pRecordType.mColor)
            , mBlackDepth(pRecordType.mBlackDepth)
        {
        }

        DataType mData;

        friend class FbxRedBlackTree;

        RecordType* mParent;
        RecordType* mLeftChild;
        RecordType* mRightChild;
        unsigned int mColor:2;
        unsigned int mBlackDepth:30;
    };

public:
    typedef FbxRedBlackConstIterator<RecordType>  ConstIteratorType;
    typedef FbxRedBlackIterator<RecordType>       IteratorType;

    inline FbxRedBlackTree() : mRoot(0), mAllocator(sizeof(RecordType)), mSize(0) {}
    inline FbxRedBlackTree(const FbxRedBlackTree& pTree) : mRoot(0), mAllocator(sizeof(RecordType)), mSize(0) { operator=(pTree); }
    inline ~FbxRedBlackTree() { Clear(); }

    inline FbxRedBlackTree& operator=(const FbxRedBlackTree& pTree)
    {
        if( this != &pTree )
        {
            Clear();

            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;
    }

    inline bool operator==(const FbxRedBlackTree& pTree) const
    {
        // 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;
    }

    inline void Reserve(unsigned int pRecordCount)
    {
        mAllocator.Reserve(pRecordCount);
    }

    inline int GetSize() const { return mSize; }

    inline bool Empty() const { return mSize == 0; }

    inline FbxPair<RecordType*, bool> Insert(const DataType& pData)
    {
        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);
    }

    inline bool Remove(const KeyType& pKey)
    {
        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;
    }

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

    inline const RecordType* Minimum() const
    {
        if (0 != mRoot)
        {
            return mRoot->Minimum();
        }
        else
        {
            return 0;
        }
    }

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

    inline const RecordType* Maximum() const
    {
        if (0 != mRoot)
        {
            return mRoot->Maximum();
        }
        else
        {
            return 0;
        }
    }

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

    inline const RecordType* Find(const KeyType& pKey) const
    {
        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;
    }

    inline RecordType* Find(const KeyType& pKey)
    {
        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;
    }

    inline const RecordType* UpperBound(const KeyType& pKey) const
    {
        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;
    }

    inline RecordType* UpperBound(const KeyType& pKey)
    {
        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;
    }

protected:
    RecordType* mRoot;
    AllocatorType mAllocator;
    int mSize;

    inline RecordType* DuplicateSubTree(const RecordType* pNode)
    {
        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;
    }

    inline void FixNodesAfterInsertion(RecordType* pNode)
    {
        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 != NULL) && (lNode->mParent->mParent != NULL))
                {
                    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 ((lNode->mParent != NULL) && (lNode->mParent->mParent != NULL))
                {
                    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;
    }

    inline void LeftRotate(RecordType* pNode)
    {
        FBX_ASSERT_RETURN(pNode);

        RecordType* lNode = pNode->mRightChild;
        FBX_ASSERT_RETURN(lNode);

    #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);
    }

    inline void RightRotate(RecordType* pNode)
    {
        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);
    }

    inline void RemoveNode(RecordType* pNode)
    {
        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;
    }

    inline void ReplaceNode(RecordType* pNodeToReplace, RecordType* pReplacement)
    {
        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;
        }
    }

    inline RecordType* Sibling(const RecordType* pParent, const RecordType* pNode) const
    {
        if (pParent)
        {
            if (pParent->mLeftChild == pNode)
            {
                return pParent->mRightChild;
            }
            else if (pParent->mRightChild == pNode)
            {
                return pParent->mLeftChild;
            }
        }

        return 0;
    }

    inline bool IsBlack(const RecordType* pNode)
    {
        return ((pNode == 0) || (pNode->mColor == RecordType::eBlack));
    }

    inline void FixNodesAfterRemoval(RecordType* pParent, RecordType* pNode)
    {
        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 if( 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 && lParent != 0); // lSibling is now
                                                 // the former red
                                                 // child of the
                                                 // former sibling

                        if( lSibling != 0 && lParent != 0 )
                        {
                            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;
        }
    }

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

    inline int GetSubTreeSize(RecordType* pNode) const
    {
        if (pNode)
        {
            return GetSubTreeSize(pNode->mLeftChild) + GetSubTreeSize(pNode->mRightChild) + 1;
        }
        else
        {
            return 0;
        }
    }

#if 0
    inline void IsSane()
    {
        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);
    }

    inline void IsSubTreeSane(const RecordType* pNode) const
    {
        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);
        }
    }

    inline void ComputeBlackDepth(RecordType* pNode, unsigned int pDepth)
    {
        if( pNode )
        {
            pNode->mBlackDepth = pDepth;
            if( pNode->mColor == RecordType::eBlack )
            {
                pDepth++;
            }
            ComputeBlackDepth(pNode->mLeftChild, pDepth);
            ComputeBlackDepth(pNode->mRightChild, pDepth);
        }
    }

    inline void CheckLeavesBlackDepth(RecordType* pNode, unsigned int pBlackDepth)
    {
        if( pNode )
        {
            if( pNode->mLeftChild == 0 || pNode->mRightChild == 0 )
            {
                FBX_ASSERT((pNode->mBlackDepth + ((pNode->mColor == RecordType::eBlack) ? 1 : 0)) == pBlackDepth);
            }
            CheckLeavesBlackDepth(pNode->mLeftChild, pBlackDepth);
            CheckLeavesBlackDepth(pNode->mRightChild, pBlackDepth);
        }
    }
#endif
};

#endif /* !DOXYGEN_SHOULD_SKIP_THIS *****************************************************************************************/

#include <fbxsdk/fbxsdk_nsend.h>

#endif /*_FBXSDK_CORE_BASE_REDBLACKTREE_H_ */