csRedBlackTree< K > Class Template Reference
[Containers]

A red-black-tree. More...

#include <csutil/redblacktree.h>

List of all members.

Public Member Functions

bool Contains (const K &key) const

Check whether a key is in the tree.

csRedBlackTree (const csRedBlackTree &other)

csRedBlackTree (size_t allocatorBlockSize=4096)

Construct a new tree.

bool Delete (const K &key)

Delete a key.

void DeleteAll ()

Delete all keys.

void Empty ()

Delete all the keys. (Idiomatic alias for DeleteAll().).

bool In (const K &key) const

Check whether a key is in the tree.

const K * Insert (const K &key)

Insert a key.

bool IsEmpty () const

Returns whether this tree has no nodes.

template<typename K2>

const K & Find (const K2 &other, const K &fallback) const

template<typename K2>

const K * Find (const K2 &other) const

Locate key that is equal to 'other'.

template<typename CB>

void TraverseInOrder (CB &callback) const

Traverse tree.

Protected Types

enum NodeColor

Protected Member Functions

void DeleteFixup (Node *node)

Fix up the RB tree after a deletion.

void DeleteNode (Node *node)

Delete a node from the tree.

void InsertFixup (Node *node)

Fix up the RB tree after an insert.

bool IsBlack (Node *node) const

Check whether a node is black. Note that 0 nodes are by definition black.

bool IsRed (Node *node) const

Check whether a node is red.

Node * LocateNode (Node *node, const K &key) const

Find the node for a key.

void RecursiveCopy (Node *&to, Node *parent, const Node *from)

Duplicate a subtree.

Node * RecursiveInsert (Node *parent, Node *&node, const K &key)

Locate the place where a new node needs to be inserted.

template<typename CB>

void RecursiveTraverseInOrder (Node *node, CB &callback) const

Traverse tree.

void RotateLeft (Node *pivot)

Left-rotate subtree around 'pivot'.

void RotateRight (Node *pivot)

Right-rotate subtree around 'pivot'.

Node * Successor (Node *node) const

Return smallest node with a key greater than 'node's.

template<typename K2>

K & Find (const K2 &other, K &fallback)

template<typename K2>

K * Find (const K2 &other)

Locate key that is equal to 'other'.

template<typename K2>

K & RecursiveFind (Node *node, const K2 &other, K &fallback)

template<typename K2>

const K & RecursiveFind (Node *node, const K2 &other, const K &fallback) const

template<typename K2>

K * RecursiveFind (Node *node, const K2 &other)

template<typename K2>

const K * RecursiveFind (Node *node, const K2 &other) const

Locate key that is equal to 'other'.

Protected Attributes

csBlockAllocator< Node, csBlockAllocatorAlignPolicy< 2 > > nodeAlloc

Node * root

Classes

struct Node

A node in the tree. More...

Detailed Description

template<typename K>
class csRedBlackTree< K >

A red-black-tree.

Remarks:

Does not allow duplicate keys.

Uses csComparator<> for key comparisons.

Only stores keys. If you need a key-value-map, look at csRedBlackTreeMap.

Definition at line 41 of file redblacktree.h.

Constructor & Destructor Documentation

template<typename K>

csRedBlackTree< K >::csRedBlackTree ( size_t allocatorBlockSize = 4096 ) [inline]

Construct a new tree.

Parameters:

allocatorBlockSize Block size in bytes used by the internal block allocator for nodes.

Definition at line 433 of file redblacktree.h.

Member Function Documentation

template<typename K>

bool csRedBlackTree< K >::Contains ( const K & key ) const [inline]

Check whether a key is in the tree.

Remarks:
This is rigidly equivalent to Contains(key), but may be considered more idiomatic by some.

Definition at line 475 of file redblacktree.h.

template<typename K>

bool csRedBlackTree< K >::Delete ( const K & key ) [inline]

Delete a key.

Returns:
Whether the deletion was successful. Fails if the key is not in the tree.

Definition at line 458 of file redblacktree.h.

template<typename K>

void csRedBlackTree< K >::DeleteAll ( ) [inline]

Delete all keys.

Reimplemented in csRedBlackTreeMap< K, T >.
Definition at line 492 of file redblacktree.h.

template<typename K>

void csRedBlackTree< K >::DeleteFixup ( Node * node ) [inline, protected]

Fix up the RB tree after a deletion.

Definition at line 237 of file redblacktree.h.

template<typename K>

void csRedBlackTree< K >::DeleteNode ( Node * node ) [inline, protected]

Delete a node from the tree.

Definition at line 204 of file redblacktree.h.

template<typename K>

void csRedBlackTree< K >::Empty ( ) [inline]

Delete all the keys. (Idiomatic alias for DeleteAll().).

Reimplemented in csRedBlackTreeMap< K, T >.
Definition at line 498 of file redblacktree.h.

template<typename K>

template<typename K2>

const K* csRedBlackTree< K >::Find ( const K2 & other ) const [inline]

Locate key that is equal to 'other'.

Definition at line 480 of file redblacktree.h.

template<typename K>

template<typename K2>

K* csRedBlackTree< K >::Find ( const K2 & other ) [inline, protected]

Locate key that is equal to 'other'.

Definition at line 401 of file redblacktree.h.

template<typename K>

bool csRedBlackTree< K >::In ( const K & key ) const [inline]

Check whether a key is in the tree.

Definition at line 466 of file redblacktree.h.

template<typename K>

const K* csRedBlackTree< K >::Insert ( const K & key ) [inline]

Insert a key.

Returns:
A pointer to the copy of the key stored in the tree, or 0 if the key already exists.

Definition at line 446 of file redblacktree.h.

template<typename K>

void csRedBlackTree< K >::InsertFixup ( Node * node ) [inline, protected]

Fix up the RB tree after an insert.

Definition at line 143 of file redblacktree.h.

template<typename K>

bool csRedBlackTree< K >::IsBlack ( Node * node ) const [inline, protected]

Check whether a node is black. Note that 0 nodes are by definition black.

Definition at line 137 of file redblacktree.h.

template<typename K>

bool csRedBlackTree< K >::IsEmpty ( ) const [inline]

Returns whether this tree has no nodes.

Reimplemented in csRedBlackTreeMap< K, T >.
Definition at line 500 of file redblacktree.h.

template<typename K>

bool csRedBlackTree< K >::IsRed ( Node * node ) const [inline, protected]

Check whether a node is red.

Definition at line 140 of file redblacktree.h.
Referenced by csRedBlackTree< csRedBlackTreePayload< K, T > >::InsertFixup().

template<typename K>

Node* csRedBlackTree< K >::LocateNode ( Node * node,

const K & key

) const [inline, protected]

Find the node for a key.

Definition at line 308 of file redblacktree.h.

template<typename K>

void csRedBlackTree< K >::RecursiveCopy ( Node *& to,

Node * parent,

const Node * from

) [inline, protected]

Duplicate a subtree.

Definition at line 413 of file redblacktree.h.

template<typename K>

template<typename K2>

const K* csRedBlackTree< K >::RecursiveFind ( Node * node,

const K2 & other

) const [inline, protected]

Locate key that is equal to 'other'.

Definition at line 341 of file redblacktree.h.

template<typename K>

Node* csRedBlackTree< K >::RecursiveInsert ( Node * parent,

Node *& node,

const K & key

) [inline, protected]

Locate the place where a new node needs to be inserted.

Definition at line 76 of file redblacktree.h.
Referenced by csRedBlackTree< csRedBlackTreePayload< K, T > >::RecursiveInsert().

template<typename K>

template<typename CB>

void csRedBlackTree< K >::RecursiveTraverseInOrder ( Node * node,

CB & callback

) const [inline, protected]

Traverse tree.

Definition at line 391 of file redblacktree.h.

template<typename K>

void csRedBlackTree< K >::RotateLeft ( Node * pivot ) [inline, protected]

Left-rotate subtree around 'pivot'.

Definition at line 99 of file redblacktree.h.
Referenced by csRedBlackTree< csRedBlackTreePayload< K, T > >::InsertFixup().

template<typename K>

void csRedBlackTree< K >::RotateRight ( Node * pivot ) [inline, protected]

Right-rotate subtree around 'pivot'.

Definition at line 118 of file redblacktree.h.
Referenced by csRedBlackTree< csRedBlackTreePayload< K, T > >::InsertFixup().

template<typename K>

Node* csRedBlackTree< K >::Successor ( Node * node ) const [inline, protected]

Return smallest node with a key greater than 'node's.

Definition at line 321 of file redblacktree.h.

template<typename K>

template<typename CB>

void csRedBlackTree< K >::TraverseInOrder ( CB & callback ) const [inline]

Traverse tree.

Reimplemented in csRedBlackTreeMap< K, T >.
Definition at line 505 of file redblacktree.h.

The documentation for this class was generated from the following file:

csutil/redblacktree.h

Generated for Crystal Space by doxygen 1.4.6


Public Member Functions
bool	Contains (const K &key) const
	Check whether a key is in the tree.
	csRedBlackTree (const csRedBlackTree &other)
	csRedBlackTree (size_t allocatorBlockSize=4096)
	Construct a new tree.
bool	Delete (const K &key)
	Delete a key.
void	DeleteAll ()
	Delete all keys.
void	Empty ()
	Delete all the keys. (Idiomatic alias for DeleteAll().).
bool	In (const K &key) const
	Check whether a key is in the tree.
const K *	Insert (const K &key)
	Insert a key.
bool	IsEmpty () const
	Returns whether this tree has no nodes.

template<typename K2>
const K &	Find (const K2 &other, const K &fallback) const
template<typename K2>
const K *	Find (const K2 &other) const
	Locate key that is equal to 'other'.

template<typename CB>
void	TraverseInOrder (CB &callback) const
	Traverse tree.
Protected Types
enum	NodeColor
Protected Member Functions
void	DeleteFixup (Node *node)
	Fix up the RB tree after a deletion.
void	DeleteNode (Node *node)
	Delete a node from the tree.
void	InsertFixup (Node *node)
	Fix up the RB tree after an insert.
bool	IsBlack (Node *node) const
	Check whether a node is black. Note that 0 nodes are by definition black.
bool	IsRed (Node *node) const
	Check whether a node is red.
Node *	LocateNode (Node *node, const K &key) const
	Find the node for a key.
void	RecursiveCopy (Node &to, Node parent, const Node *from)
	Duplicate a subtree.
Node *	RecursiveInsert (Node parent, Node &node, const K &key)
	Locate the place where a new node needs to be inserted.
template<typename CB>
void	RecursiveTraverseInOrder (Node *node, CB &callback) const
	Traverse tree.
void	RotateLeft (Node *pivot)
	Left-rotate subtree around 'pivot'.
void	RotateRight (Node *pivot)
	Right-rotate subtree around 'pivot'.
Node *	Successor (Node *node) const
	Return smallest node with a key greater than 'node's.

template<typename K2>
K &	Find (const K2 &other, K &fallback)
template<typename K2>
K *	Find (const K2 &other)
	Locate key that is equal to 'other'.

template<typename K2>
K &	RecursiveFind (Node *node, const K2 &other, K &fallback)
template<typename K2>
const K &	RecursiveFind (Node *node, const K2 &other, const K &fallback) const
template<typename K2>
K *	RecursiveFind (Node *node, const K2 &other)
template<typename K2>
const K *	RecursiveFind (Node *node, const K2 &other) const
	Locate key that is equal to 'other'.
Protected Attributes
csBlockAllocator< Node, csBlockAllocatorAlignPolicy< 2 > >	nodeAlloc
Node *	root
Classes
struct	Node
	A node in the tree. More...

Public API Reference

csRedBlackTree< K > Class Template Reference [Containers]

Public Member Functions

Protected Types

Protected Member Functions

Protected Attributes

Classes

Detailed Description

template<typename K> class csRedBlackTree< K >

Constructor & Destructor Documentation

Member Function Documentation

csRedBlackTree< K > Class Template Reference
[Containers]

template<typename K>
class csRedBlackTree< K >