KRedBlackTree Class Template Reference

#include <kmap.h>

Inheritance diagram for KRedBlackTree:

[legend]

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

Public Member Functions
KRedBlackTree &	operator= (KRedBlackTree const &pTree)
	Deep copy pTree in this.
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.
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.
Classes
class	RecordType
	This class represents a node in the tree. More...

---

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

void Reserve

(

unsigned int

pRecordCount

)

[inline]

Ask ALLOCATOR to reserve space to hold pRecordCount elements.

Parameters:

pRecordCount

Definition at line 552 of file kmap.h.

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

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

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

void Clear

(

)

[inline]

Remove all elements from the tree.

Takes O(n) time. Recursive.

Definition at line 689 of file kmap.h.

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

RecordType const* Minimum

(

)

const [inline]

Find the smallest element in the tree.

Takes O(log n) time.

Definition at line 705 of file kmap.h.

RecordType* Minimum

(

)

[inline]

Find the smallest element in the tree.

Takes O(log n) time.

Definition at line 720 of file kmap.h.

RecordType const* Maximum

(

)

const [inline]

Find the largest element in the tree.

Takes O(log n) time.

Definition at line 735 of file kmap.h.

RecordType* Maximum

(

)

[inline]

Find the largest element in the tree.

Takes O(log n) time.

Definition at line 750 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 766 of file kmap.h.

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

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

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