1.7.3Please send us your comment about this page
Implements an efficient ordered data storage.
#include <kmap.h>
Classes | |
| class | RecordType |
| This class represents a node in the tree. More... | |
Public Types | |
| typedef DATA_TYPE | DataType |
| typedef DATA_TYPE::KeyType | KeyType |
| typedef DATA_TYPE::ConstKeyType | ConstKeyType |
| typedef DATA_TYPE::ValueType | ValueType |
| typedef DATA_TYPE::ConstValueType | ConstValueType |
| typedef ALLOCATOR | AllocatorType |
| typedef RedBack_ConstIteratorType < RecordType > | ConstIteratorType |
| typedef RedBack_IteratorType < RecordType > | IteratorType |
Public Member Functions | |
| KRedBlackTree () | |
| KRedBlackTree (KRedBlackTree const &pTree) | |
| ~KRedBlackTree () | |
| KRedBlackTree & | operator= (KRedBlackTree const &pTree) |
| Deep copy pTree in this. | |
| bool | operator== (KRedBlackTree const &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 |
| KPair< RecordType *, bool > | Insert (DataType const &pData) |
| Insert a new element in the tree. | |
| bool | Remove (KeyType const &pKey) |
| Remove an element identified by a key from the tree. | |
| void | Clear () |
| Remove all elements from the tree. | |
| RecordType const * | Minimum () const |
| Find the smallest element in the tree. | |
| RecordType * | Minimum () |
| Find the smallest element in the tree. | |
| RecordType const * | Maximum () const |
| Find the largest element in the tree. | |
| RecordType * | Maximum () |
| Find the largest element in the tree. | |
| RecordType const * | Find (KeyType const &pKey) const |
| Find the key-value pair with key pKey. | |
| RecordType * | Find (KeyType const &pKey) |
| Find the key-value pair with key pKey. | |
| RecordType const * | UpperBound (KeyType const &pKey) const |
| Find the key-value pair with the smallest key greater than pKey. | |
| RecordType * | UpperBound (KeyType const &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 (RecordType const *pNode) const |
| void | ComputeBlackDepth (RecordType *pNode, unsigned int pDepth) |
| void | CheckLeavesBlackDepth (RecordType *pNode, unsigned int pBlackDepth) |
| RecordType * | DuplicateSubTree (RecordType const *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 (RecordType const *pParent, RecordType const *pNode) const |
| bool | IsBlack (RecordType const *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 DATA_TYPE DataType |
| typedef DATA_TYPE::KeyType KeyType |
| typedef DATA_TYPE::ConstKeyType ConstKeyType |
| typedef DATA_TYPE::ValueType ValueType |
| typedef DATA_TYPE::ConstValueType ConstValueType |
| typedef ALLOCATOR AllocatorType |
| typedef RedBack_IteratorType<RecordType> IteratorType |
| KRedBlackTree | ( | ) | [inline] |
Definition at line 457 of file kmap.h.
: mRoot(0), mSize(0), mAllocator(sizeof(RecordType)) {}
| KRedBlackTree | ( | KRedBlackTree< DATA_TYPE, KEY_COMPARE_FUNCTOR, ALLOCATOR > const & | pTree | ) | [inline] |
| ~KRedBlackTree | ( | ) | [inline] |
| KRedBlackTree& operator= | ( | KRedBlackTree< DATA_TYPE, KEY_COMPARE_FUNCTOR, ALLOCATOR > const & | pTree | ) | [inline] |
Deep copy pTree in this.
| pTree |
Definition at line 464 of file kmap.h.
{
if( this != &pTree )
{
Clear();
mAllocator = pTree.mAllocator;
if( pTree.mRoot )
{
void* lBuffer = mAllocator.AllocateRecords();
#if ( defined(MEMORY_DEBUG) && defined(_DEBUG) && defined(KARCH_ENV_WIN32))
#pragma push_macro("new")
#undef new
#endif
mRoot = new(lBuffer) RecordType(*(pTree.mRoot));
#if ( defined(MEMORY_DEBUG) && defined(_DEBUG) && defined(KARCH_ENV_WIN32))
#pragma pop_macro("new")
#endif
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
{
K_ASSERT( pTree.mSize == 0 );
K_ASSERT( mRoot == 0 );
}
mSize = pTree.mSize;
}
return *this;
}
| bool operator== | ( | KRedBlackTree< DATA_TYPE, KEY_COMPARE_FUNCTOR, ALLOCATOR > const & | pTree | ) | const [inline] |
Definition at line 508 of file kmap.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 537 of file kmap.h.
{
mAllocator.Reserve(pRecordCount);
}
| int GetSize | ( | ) | const [inline] |
| bool Empty | ( | ) | const [inline] |
| KPair<RecordType*, bool> Insert | ( | DataType const & | pData | ) | [inline] |
Insert a new element in the tree.
Takes O(log n) time.
| pData | The element to insert. |
Definition at line 554 of file kmap.h.
{
KEY_COMPARE_FUNCTOR lCompareKeys;
bool lResult = false;
RecordType* lParent = 0;
RecordType* lNode = mRoot;
while (lNode != 0)
{
KeyType const& lNodeKey = lNode->GetKey();
KeyType const& 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();
#if ( defined(MEMORY_DEBUG) && defined(_DEBUG) && defined(KARCH_ENV_WIN32))
#pragma push_macro("new")
#undef new
#endif
lNode = new(lBuffer) RecordType(pData);
#if ( defined(MEMORY_DEBUG) && defined(_DEBUG) && defined(KARCH_ENV_WIN32))
#pragma pop_macro("new")
#endif
mSize++;
#if ( !defined(MEMORY_DEBUG) && defined(_DEBUG) && defined(KARCH_ENV_WIN32))
K_ASSERT(lNode == lBuffer);
#endif
if (lParent)
{
if (lCompareKeys(lParent->GetKey(), pData.GetKey()) < 0)
{
K_ASSERT(lParent->mRightChild == 0);
lParent->mRightChild = lNode;
lNode->mParent = lParent;
}
else
{
K_ASSERT(lParent->mLeftChild == 0);
lParent->mLeftChild = lNode;
lNode->mParent = lParent;
}
}
else
{
mRoot = lNode;
}
// Fix red black tree property
FixNodesAfterInsertion(lNode);
lResult = true;
}
#ifdef SANITY_CHECK
IsSane();
#endif
return KPair<RecordType*, bool>(lNode, lResult);
}
| bool Remove | ( | KeyType const & | 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 634 of file kmap.h.
{
KEY_COMPARE_FUNCTOR 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;
}
#ifdef SANITY_CHECK
IsSane();
#endif
return lResult;
}
| void Clear | ( | ) | [inline] |
Remove all elements from the tree.
Takes O(n) time. Recursive.
Definition at line 674 of file kmap.h.
{
if (mRoot)
{
ClearSubTree(mRoot->mLeftChild);
ClearSubTree(mRoot->mRightChild);
mRoot->~RecordType();
mAllocator.FreeMemory(mRoot);
mRoot = 0;
mSize = 0;
}
}
| RecordType const* Minimum | ( | ) | const [inline] |
| RecordType* Minimum | ( | ) | [inline] |
| RecordType const* Maximum | ( | ) | const [inline] |
| RecordType* Maximum | ( | ) | [inline] |
| RecordType const* Find | ( | KeyType const & | 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 751 of file kmap.h.
{
KEY_COMPARE_FUNCTOR lCompareKeys;
RecordType const* 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 | ( | KeyType const & | pKey | ) | [inline] |
Find the key-value pair with key pKey.
Takes O(log n) time.
| pKey | The key to look for. |
Definition at line 778 of file kmap.h.
{
KEY_COMPARE_FUNCTOR 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;
}
| RecordType const* UpperBound | ( | KeyType const & | 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 805 of file kmap.h.
{
KEY_COMPARE_FUNCTOR lCompareKeys;
RecordType const* lNode = mRoot;
RecordType const* 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 | ( | KeyType const & | 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 830 of file kmap.h.
{
KEY_COMPARE_FUNCTOR 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 861 of file kmap.h.
{
K_ASSERT((mRoot == 0) || (mRoot->mColor == RecordType::eBlack));
K_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 | ( | RecordType const * | pNode | ) | const [inline, protected] |
Definition at line 884 of file kmap.h.
{
KEY_COMPARE_FUNCTOR lCompareKeys;
if (pNode)
{
K_ASSERT(pNode != pNode->mParent);
K_ASSERT(pNode != pNode->mLeftChild);
K_ASSERT(pNode != pNode->mRightChild);
// Check for two consecutive red nodes
K_ASSERT((pNode->mColor == RecordType::eBlack) ||
(pNode->mLeftChild == NULL) ||
(pNode->mLeftChild->mColor == RecordType::eBlack));
K_ASSERT((pNode->mColor == RecordType::eBlack) ||
(pNode->mRightChild == NULL) ||
(pNode->mRightChild->mColor == RecordType::eBlack));
// Check key ordering
K_ASSERT((pNode->mLeftChild == 0 ||
lCompareKeys(pNode->GetKey(), pNode->mLeftChild->GetKey()) > 0));
K_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 915 of file kmap.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 930 of file kmap.h.
{
if (pNode)
{
if ((pNode->mLeftChild == 0) || pNode->mRightChild == 0)
{
int lBlackDepth = pNode->mBlackDepth + ((pNode->mColor == RecordType::eBlack) ? 1 : 0);
K_ASSERT(lBlackDepth == pBlackDepth);
}
CheckLeavesBlackDepth(pNode->mLeftChild, pBlackDepth);
CheckLeavesBlackDepth(pNode->mRightChild, pBlackDepth);
}
}
| RecordType* DuplicateSubTree | ( | RecordType const * | pNode | ) | [inline, protected] |
Definition at line 945 of file kmap.h.
{
RecordType* lNewSubTree = 0;
if (pNode)
{
void* lBuffer = mAllocator.AllocateRecords();
#if ( defined(MEMORY_DEBUG) && defined(_DEBUG) && defined(KARCH_ENV_WIN32))
#pragma push_macro("new")
#undef new
#endif
lNewSubTree = new(lBuffer) RecordType(*pNode);
#if ( defined(MEMORY_DEBUG) && defined(_DEBUG) && defined(KARCH_ENV_WIN32))
#pragma pop_macro("new")
#endif
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 977 of file kmap.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 1046 of file kmap.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)
{
K_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;
K_ASSERT(pNode->mLeftChild == A);
K_ASSERT(pNode->mRightChild == B);
K_ASSERT(pNode->mParent == lNode);
K_ASSERT(lNode->mLeftChild == pNode);
K_ASSERT(lNode->mRightChild == C);
K_ASSERT(lNode->mParent == Z);
K_ASSERT(A == 0 || A->mParent == pNode);
K_ASSERT(B == 0 || B->mParent == pNode);
K_ASSERT(C == 0 || C->mParent == lNode);
K_ASSERT(Z == 0 || Z->mLeftChild == lNode || Z->mRightChild == lNode);
}
| void RightRotate | ( | RecordType * | pNode | ) | [inline, protected] |
Definition at line 1095 of file kmap.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)
{
K_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;
K_ASSERT(lNode->mLeftChild == A);
K_ASSERT(lNode->mRightChild == pNode);
K_ASSERT(lNode->mParent == Z);
K_ASSERT(pNode->mLeftChild == B);
K_ASSERT(pNode->mRightChild == C);
K_ASSERT(pNode->mParent == lNode);
K_ASSERT(A == 0 || A->mParent == lNode);
K_ASSERT(B == 0 || B->mParent == pNode);
K_ASSERT(C == 0 || C->mParent == pNode);
K_ASSERT(Z == 0 || Z->mLeftChild == lNode || Z->mRightChild == lNode);
}
| void RemoveNode | ( | RecordType * | pNode | ) | [inline, protected] |
Definition at line 1144 of file kmap.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
{
K_ASSERT_MSG_NOW("Node not found in KRedBlackTree");
}
}
else
{
K_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
{
K_ASSERT_MSG_NOW("Node not found in KRedBlackTree");
}
}
else
{
K_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
{
K_ASSERT_MSG_NOW("Node not found in KRedBlackTree");
}
}
else
{
K_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 1257 of file kmap.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
{
K_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 | ( | RecordType const * | pParent, |
| RecordType const * | pNode | ||
| ) | const [inline, protected] |
| bool IsBlack | ( | RecordType const * | pNode | ) | [inline, protected] |
| void FixNodesAfterRemoval | ( | RecordType * | pParent, |
| RecordType * | pNode | ||
| ) | [inline, protected] |
Definition at line 1312 of file kmap.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);
K_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 1431 of file kmap.h.
{
if (pNode)
{
ClearSubTree(pNode->mLeftChild);
ClearSubTree(pNode->mRightChild);
pNode->~RecordType();
mAllocator.FreeMemory(pNode);
}
}
| int GetSubTreeSize | ( | RecordType * | pNode | ) | const [inline, protected] |
Definition at line 1442 of file kmap.h.
{
if (pNode)
{
return GetSubTreeSize(pNode->mLeftChild) + GetSubTreeSize(pNode->mRightChild) + 1;
}
else
{
return 0;
}
}
RecordType* mRoot [protected] |
int mSize [protected] |
AllocatorType mAllocator [protected] |