CrystalSpace

Public API Reference

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 { Black = 0, Red = 1 }

Protected Member Functions

void DeleteFixup (Node *node, Node *nilParent)
 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.
NodeLocateNode (Node *node, const K &key) const
 Find the node for a key.
void RecursiveCopy (Node *&to, Node *parent, const Node *from)
 Duplicate a subtree.
NodeRecursiveInsert (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'.
NodeSuccessor (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,
CS::Memory::AllocatorAlign< 2 > > 
nodeAlloc
Noderoot

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 47 of file redblacktree.h.


Member Enumeration Documentation

template<typename K>
enum csRedBlackTree::NodeColor [protected]

Enumerator:
Black 
Red 

Definition at line 50 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 447 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 489 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 472 of file redblacktree.h.

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

Delete all keys.

Reimplemented in csRedBlackTreeMap< K, T >.

Definition at line 506 of file redblacktree.h.

Referenced by csRedBlackTree< csRedBlackTreePayload< K, T > >::Empty().

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

Fix up the RB tree after a deletion.

Definition at line 251 of file redblacktree.h.

Referenced by csRedBlackTree< csRedBlackTreePayload< K, T > >::DeleteNode().

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

Delete a node from the tree.

Definition at line 214 of file redblacktree.h.

Referenced by csRedBlackTree< csRedBlackTreePayload< K, T > >::Delete().

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

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

Reimplemented in csRedBlackTreeMap< K, T >.

Definition at line 512 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 494 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 415 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 480 of file redblacktree.h.

Referenced by csRedBlackTree< csRedBlackTreePayload< K, T > >::Contains().

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 460 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 151 of file redblacktree.h.

Referenced by csRedBlackTree< csRedBlackTreePayload< K, T > >::Insert().

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 145 of file redblacktree.h.

Referenced by csRedBlackTree< csRedBlackTreePayload< K, T > >::DeleteFixup().

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

Returns whether this tree has no nodes.

Reimplemented in csRedBlackTreeMap< K, T >.

Definition at line 514 of file redblacktree.h.

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

template<typename K>
Node* csRedBlackTree< K >::LocateNode ( Node node,
const K &  key 
) const [inline, protected]

template<typename K>
void csRedBlackTree< K >::RecursiveCopy ( Node *&  to,
Node parent,
const Node from 
) [inline, protected]

template<typename K>
template<typename K2>
const K* csRedBlackTree< K >::RecursiveFind ( Node node,
const K2 &  other 
) const [inline, protected]

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 82 of file redblacktree.h.

Referenced by csRedBlackTree< csRedBlackTreePayload< K, T > >::Insert(), and csRedBlackTree< csRedBlackTreePayload< K, T > >::RecursiveInsert().

template<typename K>
template<typename CB>
void csRedBlackTree< K >::RecursiveTraverseInOrder ( Node node,
CB &  callback 
) const [inline, protected]

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

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

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 335 of file redblacktree.h.

Referenced by csRedBlackTree< csRedBlackTreePayload< K, T > >::DeleteNode().

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

Traverse tree.

Reimplemented in csRedBlackTreeMap< K, T >.

Definition at line 519 of file redblacktree.h.


The documentation for this class was generated from the following file:
Generated for Crystal Space 1.2.1 by doxygen 1.5.3