1.7.3Please send us your comment about this page
Implements an efficient ordered data storage.
Definition at line 190 of file fbxredblacktree.h.
#include <fbxredblacktree.h>
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 |
| typedef Type DataType |
Definition at line 193 of file fbxredblacktree.h.
| typedef Type::KeyType KeyType |
Definition at line 194 of file fbxredblacktree.h.
| typedef Type::ConstKeyType ConstKeyType |
Definition at line 195 of file fbxredblacktree.h.
| typedef Type::ValueType ValueType |
Definition at line 196 of file fbxredblacktree.h.
| typedef Type::ConstValueType ConstValueType |
Definition at line 197 of file fbxredblacktree.h.
| typedef Allocator AllocatorType |
Definition at line 198 of file fbxredblacktree.h.
Definition at line 384 of file fbxredblacktree.h.
| typedef FbxRedBlackIterator<RecordType> IteratorType |
Definition at line 385 of file fbxredblacktree.h.
| 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(); }
| FbxRedBlackTree& operator= | ( | const FbxRedBlackTree< Type, Compare, Allocator > & | pTree | ) | [inline] |
Deep copy pTree in this.
| 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] |
Ask Allocator to reserve space to hold pRecordCount elements.
| pRecordCount |
Definition at line 459 of file fbxredblacktree.h.
{
mAllocator.Reserve(pRecordCount);
}
| int GetSize | ( | ) | const [inline] |
Get the number of elements in the tree.
Takes O(1) time.
Definition at line 467 of file fbxredblacktree.h.
{ return mSize; }
| bool Empty | ( | ) | const [inline] |
| FbxPair<RecordType*, bool> Insert | ( | const DataType & | pData | ) | [inline] |
Insert a new element in the tree.
Takes O(log n) time.
| pData | The element to insert. |
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] |
Remove an element identified by a key from the tree.
Takes O(log n) time.
| 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] |
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] |
Find the smallest element in the tree.
Takes O(log n) time.
Definition at line 595 of file fbxredblacktree.h.
| RecordType* Minimum | ( | ) | [inline] |
Find the smallest element in the tree.
Takes O(log n) time.
Definition at line 610 of file fbxredblacktree.h.
| const RecordType* Maximum | ( | ) | const [inline] |
Find the largest element in the tree.
Takes O(log n) time.
Definition at line 625 of file fbxredblacktree.h.
| RecordType* Maximum | ( | ) | [inline] |
Find the largest element in the tree.
Takes O(log n) time.
Definition at line 640 of file fbxredblacktree.h.
| const RecordType* Find | ( | const KeyType & | pKey | ) | const [inline] |
Find the key-value pair with key pKey.
Takes O(log n) time.
| 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] |
Find the key-value pair with key pKey.
Takes O(log n) time.
| 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] |
Find the key-value pair with the smallest key greater than pKey.
Takes O(log n) time.
| 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] |
Find the key-value pair with the smallest key greater than pKey.
Takes O(log n) time.
| 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] |
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] |
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] |
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] |
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] |
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] |
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] |
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] |
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] |
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] |
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] |
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] |
Definition at line 1202 of file fbxredblacktree.h.
{
return ((pNode == 0) || (pNode->mColor == RecordType::eBlack));
}
| void FixNodesAfterRemoval | ( | RecordType * | pParent, |
| RecordType * | pNode | ||
| ) | [inline, protected] |
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] |
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] |
Definition at line 1336 of file fbxredblacktree.h.
{
if (pNode)
{
return GetSubTreeSize(pNode->mLeftChild) + GetSubTreeSize(pNode->mRightChild) + 1;
}
else
{
return 0;
}
}
RecordType* mRoot [protected] |
Definition at line 757 of file fbxredblacktree.h.
int mSize [protected] |
Definition at line 758 of file fbxredblacktree.h.
AllocatorType mAllocator [protected] |
Definition at line 760 of file fbxredblacktree.h.