KRedBlackTree Class Template Reference

#include <kmap.h>

List of all members.

---

Detailed Description

template<typename DATA_TYPE, typename KEY_COMPARE_FUNCTOR, typename ALLOCATOR>
class KRedBlackTree< DATA_TYPE, KEY_COMPARE_FUNCTOR, ALLOCATOR >

Implements an efficient ordered data storage.

Definition at line 267 of file kmap.h.

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
Classes
class	RecordType
	This class represents a node in the tree. More...

---

Member Typedef Documentation

typedef DATA_TYPE DataType

Definition at line 270 of file kmap.h.

typedef DATA_TYPE::KeyType KeyType

Definition at line 271 of file kmap.h.

typedef DATA_TYPE::ConstKeyType ConstKeyType

Definition at line 272 of file kmap.h.

typedef DATA_TYPE::ValueType ValueType

Definition at line 273 of file kmap.h.

typedef DATA_TYPE::ConstValueType ConstValueType

Definition at line 274 of file kmap.h.

typedef ALLOCATOR AllocatorType

Definition at line 275 of file kmap.h.

typedef RedBack_ConstIteratorType<RecordType> ConstIteratorType

Definition at line 467 of file kmap.h.

typedef RedBack_IteratorType<RecordType> IteratorType

Definition at line 468 of file kmap.h.

---

Constructor & Destructor Documentation

KRedBlackTree

(

)

[inline]

Definition at line 471 of file kmap.h.

KRedBlackTree

(

KRedBlackTree< DATA_TYPE, KEY_COMPARE_FUNCTOR, ALLOCATOR > const &

pTree

)

[inline]

Definition at line 472 of file kmap.h.

~KRedBlackTree

(

)

[inline]

Definition at line 473 of file kmap.h.

---

Member Function Documentation

KRedBlackTree& operator=

(

KRedBlackTree< DATA_TYPE, KEY_COMPARE_FUNCTOR, ALLOCATOR > const &

pTree

)

[inline]

Deep copy pTree in this.

Parameters:

pTree

Definition at line 478 of file kmap.h.

Referenced by KRedBlackTree< KKeyValuePair, KFbxMapKStringCompare, KBaseAllocator >::KRedBlackTree().

bool operator==

(

KRedBlackTree< DATA_TYPE, KEY_COMPARE_FUNCTOR, ALLOCATOR > const &

pTree

)

const [inline]

Definition at line 522 of file kmap.h.

void Reserve

(

unsigned int

pRecordCount

)

[inline]

Ask ALLOCATOR to reserve space to hold pRecordCount elements.

Parameters:

pRecordCount

Definition at line 551 of file kmap.h.

Referenced by KMap< K, T, Compare >::Reserve().

int GetSize

(

)

const [inline]

Get the number of elements in the tree.

Takes O(1) time.

Returns:

The number of elements in the tree.

Definition at line 559 of file kmap.h.

Referenced by KMap< K, T, Compare >::GetSize(), and KRedBlackTree< KKeyValuePair, KFbxMapKStringCompare, KBaseAllocator >::operator==().

bool Empty

(

)

const [inline]

Definition at line 561 of file kmap.h.

Referenced by KMap< K, T, Compare >::Empty().

KPair<RecordType*, bool> Insert

(

DataType const &

pData

)

[inline]

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 568 of file kmap.h.

Referenced by KMap< K, T, Compare >::Insert().

bool Remove

(

KeyType const &

pKey

)

[inline]

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 648 of file kmap.h.

Referenced by KMap< K, T, Compare >::Remove().

void Clear

(

)

[inline]

Remove all elements from the tree.

Takes O(n) time. Recursive.

Definition at line 688 of file kmap.h.

Referenced by KMap< K, T, Compare >::Clear(), KRedBlackTree< KKeyValuePair, KFbxMapKStringCompare, KBaseAllocator >::operator=(), and KRedBlackTree< KKeyValuePair, KFbxMapKStringCompare, KBaseAllocator >::~KRedBlackTree().

RecordType const* Minimum

(

)

const [inline]

Find the smallest element in the tree.

Takes O(log n) time.

Definition at line 704 of file kmap.h.

Referenced by KMap< K, T, Compare >::Minimum(), and KRedBlackTree< KKeyValuePair, KFbxMapKStringCompare, KBaseAllocator >::operator==().

RecordType* Minimum

(

)

[inline]

Find the smallest element in the tree.

Takes O(log n) time.

Definition at line 719 of file kmap.h.

RecordType const* Maximum

(

)

const [inline]

Find the largest element in the tree.

Takes O(log n) time.

Definition at line 734 of file kmap.h.

Referenced by KMap< K, T, Compare >::Maximum().

RecordType* Maximum

(

)

[inline]

Find the largest element in the tree.

Takes O(log n) time.

Definition at line 749 of file kmap.h.

RecordType const* Find

(

KeyType const &

pKey

)

const [inline]

Find the key-value pair with key pKey.

Takes O(log n) time.

Parameters:

pKey

The key to look for.

Definition at line 765 of file kmap.h.

Referenced by KMap< K, T, Compare >::Find().

RecordType* Find

(

KeyType const &

pKey

)

[inline]

Find the key-value pair with key pKey.

Takes O(log n) time.

Parameters:

pKey

The key to look for.

Definition at line 792 of file kmap.h.

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.

Parameters:

pKey

The key to look for.

Definition at line 819 of file kmap.h.

Referenced by KMap< K, T, Compare >::UpperBound().

RecordType* UpperBound

(

KeyType const &

pKey

)

[inline]

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 844 of file kmap.h.

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 875 of file kmap.h.

Referenced by KRedBlackTree< KKeyValuePair, KFbxMapKStringCompare, KBaseAllocator >::Insert(), and KRedBlackTree< KKeyValuePair, KFbxMapKStringCompare, KBaseAllocator >::Remove().

void IsSubTreeSane

(

RecordType const *

pNode

)

const [inline, protected]

Definition at line 898 of file kmap.h.

Referenced by KRedBlackTree< KKeyValuePair, KFbxMapKStringCompare, KBaseAllocator >::IsSane(), and KRedBlackTree< KKeyValuePair, KFbxMapKStringCompare, KBaseAllocator >::IsSubTreeSane().

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

Definition at line 929 of file kmap.h.

Referenced by KRedBlackTree< KKeyValuePair, KFbxMapKStringCompare, KBaseAllocator >::ComputeBlackDepth(), and KRedBlackTree< KKeyValuePair, KFbxMapKStringCompare, KBaseAllocator >::IsSane().

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

Definition at line 944 of file kmap.h.

Referenced by KRedBlackTree< KKeyValuePair, KFbxMapKStringCompare, KBaseAllocator >::CheckLeavesBlackDepth(), and KRedBlackTree< KKeyValuePair, KFbxMapKStringCompare, KBaseAllocator >::IsSane().

RecordType* DuplicateSubTree

(

RecordType const *

pNode

)

[inline, protected]

Definition at line 959 of file kmap.h.

Referenced by KRedBlackTree< KKeyValuePair, KFbxMapKStringCompare, KBaseAllocator >::DuplicateSubTree(), and KRedBlackTree< KKeyValuePair, KFbxMapKStringCompare, KBaseAllocator >::operator=().

void FixNodesAfterInsertion

(

RecordType *

pNode

)

[inline, protected]

Definition at line 991 of file kmap.h.

Referenced by KRedBlackTree< KKeyValuePair, KFbxMapKStringCompare, KBaseAllocator >::Insert().

void LeftRotate

(

RecordType *

pNode

)

[inline, protected]

Definition at line 1060 of file kmap.h.

Referenced by KRedBlackTree< KKeyValuePair, KFbxMapKStringCompare, KBaseAllocator >::FixNodesAfterInsertion(), and KRedBlackTree< KKeyValuePair, KFbxMapKStringCompare, KBaseAllocator >::FixNodesAfterRemoval().

void RightRotate

(

RecordType *

pNode

)

[inline, protected]

Definition at line 1109 of file kmap.h.

Referenced by KRedBlackTree< KKeyValuePair, KFbxMapKStringCompare, KBaseAllocator >::FixNodesAfterInsertion(), and KRedBlackTree< KKeyValuePair, KFbxMapKStringCompare, KBaseAllocator >::FixNodesAfterRemoval().

void RemoveNode

(

RecordType *

pNode

)

[inline, protected]

Definition at line 1158 of file kmap.h.

Referenced by KRedBlackTree< KKeyValuePair, KFbxMapKStringCompare, KBaseAllocator >::Remove(), and KRedBlackTree< KKeyValuePair, KFbxMapKStringCompare, KBaseAllocator >::RemoveNode().

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

Definition at line 1271 of file kmap.h.

Referenced by KRedBlackTree< KKeyValuePair, KFbxMapKStringCompare, KBaseAllocator >::RemoveNode().

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

Definition at line 1304 of file kmap.h.

Referenced by KRedBlackTree< KKeyValuePair, KFbxMapKStringCompare, KBaseAllocator >::FixNodesAfterRemoval().

bool IsBlack

(

RecordType const *

pNode

)

[inline, protected]

Definition at line 1321 of file kmap.h.

Referenced by KRedBlackTree< KKeyValuePair, KFbxMapKStringCompare, KBaseAllocator >::FixNodesAfterRemoval().

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

Definition at line 1326 of file kmap.h.

Referenced by KRedBlackTree< KKeyValuePair, KFbxMapKStringCompare, KBaseAllocator >::RemoveNode().

void ClearSubTree

(

RecordType *

pNode

)

[inline, protected]

Definition at line 1445 of file kmap.h.

Referenced by KRedBlackTree< KKeyValuePair, KFbxMapKStringCompare, KBaseAllocator >::Clear(), and KRedBlackTree< KKeyValuePair, KFbxMapKStringCompare, KBaseAllocator >::ClearSubTree().

int GetSubTreeSize

(

RecordType *

pNode

)

const [inline, protected]

Definition at line 1456 of file kmap.h.

Referenced by KRedBlackTree< KKeyValuePair, KFbxMapKStringCompare, KBaseAllocator >::GetSubTreeSize().

---

Member Data Documentation

RecordType* mRoot [protected]

Definition at line 866 of file kmap.h.

Referenced by KRedBlackTree< KKeyValuePair, KFbxMapKStringCompare, KBaseAllocator >::Clear(), KRedBlackTree< KKeyValuePair, KFbxMapKStringCompare, KBaseAllocator >::Find(), KRedBlackTree< KKeyValuePair, KFbxMapKStringCompare, KBaseAllocator >::FixNodesAfterInsertion(), KRedBlackTree< KKeyValuePair, KFbxMapKStringCompare, KBaseAllocator >::FixNodesAfterRemoval(), KRedBlackTree< KKeyValuePair, KFbxMapKStringCompare, KBaseAllocator >::Insert(), KRedBlackTree< KKeyValuePair, KFbxMapKStringCompare, KBaseAllocator >::IsSane(), KRedBlackTree< KKeyValuePair, KFbxMapKStringCompare, KBaseAllocator >::LeftRotate(), KRedBlackTree< KKeyValuePair, KFbxMapKStringCompare, KBaseAllocator >::Maximum(), KRedBlackTree< KKeyValuePair, KFbxMapKStringCompare, KBaseAllocator >::Minimum(), KRedBlackTree< KKeyValuePair, KFbxMapKStringCompare, KBaseAllocator >::operator=(), KRedBlackTree< KKeyValuePair, KFbxMapKStringCompare, KBaseAllocator >::Remove(), KRedBlackTree< KKeyValuePair, KFbxMapKStringCompare, KBaseAllocator >::RemoveNode(), KRedBlackTree< KKeyValuePair, KFbxMapKStringCompare, KBaseAllocator >::ReplaceNode(), KRedBlackTree< KKeyValuePair, KFbxMapKStringCompare, KBaseAllocator >::RightRotate(), and KRedBlackTree< KKeyValuePair, KFbxMapKStringCompare, KBaseAllocator >::UpperBound().

int mSize [protected]

Definition at line 867 of file kmap.h.

Referenced by KRedBlackTree< KKeyValuePair, KFbxMapKStringCompare, KBaseAllocator >::Clear(), KRedBlackTree< KKeyValuePair, KFbxMapKStringCompare, KBaseAllocator >::Empty(), KRedBlackTree< KKeyValuePair, KFbxMapKStringCompare, KBaseAllocator >::GetSize(), KRedBlackTree< KKeyValuePair, KFbxMapKStringCompare, KBaseAllocator >::Insert(), KRedBlackTree< KKeyValuePair, KFbxMapKStringCompare, KBaseAllocator >::IsSane(), KRedBlackTree< KKeyValuePair, KFbxMapKStringCompare, KBaseAllocator >::operator=(), and KRedBlackTree< KKeyValuePair, KFbxMapKStringCompare, KBaseAllocator >::Remove().

AllocatorType mAllocator [protected]

Definition at line 869 of file kmap.h.

Referenced by KRedBlackTree< KKeyValuePair, KFbxMapKStringCompare, KBaseAllocator >::Clear(), KRedBlackTree< KKeyValuePair, KFbxMapKStringCompare, KBaseAllocator >::ClearSubTree(), KRedBlackTree< KKeyValuePair, KFbxMapKStringCompare, KBaseAllocator >::DuplicateSubTree(), KRedBlackTree< KKeyValuePair, KFbxMapKStringCompare, KBaseAllocator >::Insert(), KRedBlackTree< KKeyValuePair, KFbxMapKStringCompare, KBaseAllocator >::operator=(), KRedBlackTree< KKeyValuePair, KFbxMapKStringCompare, KBaseAllocator >::Remove(), and KRedBlackTree< KKeyValuePair, KFbxMapKStringCompare, KBaseAllocator >::Reserve().