CrystalSpace

Public API Reference

csRedBlackTree< K > Class Template Reference
[Containers]

A red-black-tree. More...

#include <csutil/redblacktree.h>

List of all members.

Classes

class  ConstIterator
 Const iterator for tree. More...
class  ConstReverseIterator
 Const reverse iterator for tree. More...
class  Iterator
 Const iterator for tree. More...
struct  Node
 A node in the tree. More...

Public Member Functions

bool Contains (const K &key) const
 Check whether a key is in the tree.
 csRedBlackTree (size_t allocatorBlockSize=4096)
 Construct a new tree.
bool Delete (const K &key)
 Delete a key.
void DeleteAll ()
 Delete all keys.
bool DeleteExact (const K *key)
 Delete a specific instance of a key.
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
 Locate key that is equal to other.
template<typename K2 >
const K & Find (const K2 &other, const K &fallback) const
 Locate key that is equal to other.

template<typename K2 >
const K * FindSmallestGreaterEqual (const K2 &other) const
 Locate smallest key greater or equal to other.
template<typename K2 >
const K & FindSmallestGreaterEqual (const K2 &other, const K &fallback) const
 Locate smallest key greater or equal to other.

template<typename CB >
void TraverseInOrder (CB &callback) const
 Traverse tree.

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.
NodeLocateNodeExact (Node *node, const K *key) const
 Find the node which has a given instance of 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'.

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

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

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

Static Protected Member Functions

static NodePredecessor (const Node *node)
 Return largest node with a key smaller than 'node's.
static NodeSuccessor (const Node *node)
 Return smallest node with a key greater than 'node's.



class ConstIterator
 Get an iterator for iterating over the entire tree.
class ConstReverseIterator
 Get an iterator for iterating over the entire tree.
class Iterator
 Get an iterator for iterating over the entire tree.
ConstIterator GetIterator () const
 Get an iterator for iterating over the entire tree.
ConstReverseIterator GetReverseIterator ()
 Get an iterator for iterating over the entire tree.
Iterator GetIterator ()
 Get an iterator for iterating over the entire tree.
void Delete (Iterator &it)
 Delete the 'next' element pointed at by the iterator.

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 48 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 530 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 584 of file redblacktree.h.

template<typename K>
void csRedBlackTree< K >::Delete ( Iterator it  )  [inline]

Delete the 'next' element pointed at by the iterator.

Remarks:
Will repoint the iterator to the following element.

Definition at line 767 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 555 of file redblacktree.h.

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

Delete all keys.

Reimplemented in csRedBlackTreeMap< K, T >.

Definition at line 616 of file redblacktree.h.

template<typename K>
bool csRedBlackTree< K >::DeleteExact ( const K *  key  )  [inline]

Delete a specific instance of a key.

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

Definition at line 567 of file redblacktree.h.

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

Fix up the RB tree after a deletion.

Definition at line 252 of file redblacktree.h.

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

Delete a node from the tree.

Definition at line 216 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 622 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 498 of file redblacktree.h.

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

Locate key that is equal to 'other'.

Definition at line 503 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 589 of file redblacktree.h.

template<typename K>
template<typename K2 >
const K& csRedBlackTree< K >::Find ( const K2 &  other,
const K &  fallback 
) const [inline]

Locate key that is equal to other.

Definition at line 594 of file redblacktree.h.

template<typename K>
template<typename K2 >
const K& csRedBlackTree< K >::FindSmallestGreaterEqual ( const K2 &  other,
const K &  fallback 
) const [inline]

Locate smallest key greater or equal to other.

Definition at line 608 of file redblacktree.h.

template<typename K>
template<typename K2 >
const K* csRedBlackTree< K >::FindSmallestGreaterEqual ( const K2 &  other  )  const [inline]

Locate smallest key greater or equal to other.

Definition at line 603 of file redblacktree.h.

template<typename K>
Iterator csRedBlackTree< K >::GetIterator (  )  [inline]

Get an iterator for iterating over the entire tree.

Reimplemented in csRedBlackTreeMap< K, T >.

Definition at line 758 of file redblacktree.h.

template<typename K>
ConstIterator csRedBlackTree< K >::GetIterator (  )  const [inline]

Get an iterator for iterating over the entire tree.

Reimplemented in csRedBlackTreeMap< K, T >.

Definition at line 703 of file redblacktree.h.

template<typename K>
ConstReverseIterator csRedBlackTree< K >::GetReverseIterator (  )  [inline]

Get an iterator for iterating over the entire tree.

Reimplemented in csRedBlackTreeMap< K, T >.

Definition at line 711 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 575 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 543 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 150 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 144 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 624 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 147 of file redblacktree.h.

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

Find the node for a key.

Definition at line 327 of file redblacktree.h.

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

Find the node which has a given instance of a key.

Definition at line 340 of file redblacktree.h.

template<typename K>
static Node* csRedBlackTree< K >::Predecessor ( const Node node  )  [inline, static, protected]

Return largest node with a key smaller than 'node's.

Definition at line 377 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 510 of file redblacktree.h.

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

Locate key that is equal to 'other'.

Definition at line 433 of file redblacktree.h.

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

Locate key that is equal to 'other'.

Definition at line 421 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 397 of file redblacktree.h.

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

Locate key that is equal to 'other'.

Definition at line 409 of file redblacktree.h.

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

Locate key that is equal to 'other'.

Definition at line 449 of file redblacktree.h.

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

Locate key that is equal to 'other'.

Definition at line 467 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 83 of file redblacktree.h.

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

Traverse tree.

Definition at line 488 of file redblacktree.h.

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

Left-rotate subtree around 'pivot'.

Definition at line 104 of file redblacktree.h.

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

Right-rotate subtree around 'pivot'.

Definition at line 124 of file redblacktree.h.

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

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

Definition at line 359 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 629 of file redblacktree.h.


Friends And Related Function Documentation

template<typename K>
friend class ConstIterator [friend]

Get an iterator for iterating over the entire tree.

Reimplemented in csRedBlackTreeMap< K, T >.

Definition at line 666 of file redblacktree.h.

template<typename K>
friend class ConstReverseIterator [friend]

Get an iterator for iterating over the entire tree.

Reimplemented in csRedBlackTreeMap< K, T >.

Definition at line 698 of file redblacktree.h.

template<typename K>
friend class Iterator [friend]

Get an iterator for iterating over the entire tree.

Reimplemented in csRedBlackTreeMap< K, T >.

Definition at line 753 of file redblacktree.h.


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

Generated for Crystal Space 1.4.1 by doxygen 1.7.1