CrystalSpace

Public API Reference

csRedBlackTree< K, Allocator, Ordering > 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
 Iterator for tree. More...
class  ReverseIterator
 Reverse iterator for tree. More...

Public Member Functions

bool Contains (const K &key) const
 Check whether a key is in the tree.
 csRedBlackTree (const Allocator &alloc=Allocator())
 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().).
ReverseIterator GetReverseIterator ()
 Get an iterator for iterating over the entire tree.
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.
 ~csRedBlackTree ()
 Destroy the tree.

Protected Member Functions

Node * CreateNode (Node *parent, const K &key)
 Create a new tree node.
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.
template<typename K2 >
Node * LocateNode (Node *node, const K2 &other) const
 Find a node for a key.
Node * LocateNodeExact (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.
void RecursiveDelete (Node *node)
 Recursively delete a subtree.
Node * RecursiveFindInsertCandidate (Node *parent, Node *&node, const K &key, uint depth, InsertCandidate &candidate)
 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'.

Static Protected Member Functions

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



class ConstIterator
 Locate key that is equal to other.
class ConstReverseIterator
 Locate key that is equal to other.
class Iterator
 Locate key that is equal to other.
template<typename K2 >
K & FindInternal (const K2 &other, K &fallback)
 Locate key that is equal to other.
template<typename K2 >
K * FindInternal (const K2 &other)
 Locate key that is equal to other.
template<typename K2 >
Node * RecursiveFindGSE (Node *node, const K2 &other) const
 Locate greatest key that is smaller or equal to 'other'.
template<typename K2 >
Node * RecursiveFindSGE (Node *node, const K2 &other) const
 Locate smallest key that is greater or equal to 'other'.
void Delete (Iterator &it)
 Delete the 'next' element pointed at by the iterator.
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 * Find (const K2 &other) const
 Locate key that is equal to other.
template<typename K2 >
const K & FindGreatestSmallerEqual (const K2 &other, const K &fallback) const
 Locate key that is equal to other.
template<typename K2 >
const K * FindGreatestSmallerEqual (const K2 &other) const
 Locate greatest key smaller or equal to other.
template<typename K2 >
const K & FindSmallestGreaterEqual (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.
Iterator GetIterator ()
 Get an iterator for iterating over the entire tree.
ConstIterator GetIterator () const
 Get an iterator for iterating over the entire tree.
ConstReverseIterator GetReverseIterator () const
 Get an iterator for iterating over the entire tree.
template<typename CB >
void TraverseInOrder (CB &callback) const
 Traverse tree.

Detailed Description

template<typename K, typename Allocator = CS::Container::DefaultRedBlackTreeAllocator<K>, template< typename _K, typename K2 > class Ordering = CS::Container::RedBlackTreeOrderingTotal>
class csRedBlackTree< K, Allocator, Ordering >

A red-black-tree.

Uniqueness of keys
Keys do not need to be unique. However, searching for a non-unique key Find() will return an equivalent key, not necessarily the identical key.
The ordering of the key is controlled by changing the Ordering template parameter which defaults to total ordering. Total ordering is selected by CS::Container::RedBlackTreeOrderingTotal. Partial ordering is selected by CS::Container::RedBlackTreeOrderingPartial. Strict Weak ordering is selected by CS::Container::RedBlackTreeOrderingStrictWeak.
The various "Find" methods can take keys of an alternative type (designated K2). Operators available must cover the comparisons of the ordering parameter. The ordering of K2 should, sensibly, be the same as that of K.
Remarks:
The key has to fullfill the requirements made by the Ordering class.
Only stores keys. If you need a key-value-map, look at csRedBlackTreeMap.
The allocator has to return memory blocks at least aligned to two byte boundaries. (This is usually already the case.)
Allocation requests to the allocator have a size of csRedBlackTree<K>::allocationUnitSize.

Definition at line 242 of file redblacktree.h.


Constructor & Destructor Documentation

template<typename K, typename Allocator = CS::Container::DefaultRedBlackTreeAllocator<K>, template< typename _K, typename K2 > class Ordering = CS::Container::RedBlackTreeOrderingTotal>
csRedBlackTree< K, Allocator, Ordering >::csRedBlackTree ( const Allocator &  alloc = Allocator()  )  [inline]

Construct a new tree.

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

Definition at line 765 of file redblacktree.h.

template<typename K, typename Allocator = CS::Container::DefaultRedBlackTreeAllocator<K>, template< typename _K, typename K2 > class Ordering = CS::Container::RedBlackTreeOrderingTotal>
csRedBlackTree< K, Allocator, Ordering >::~csRedBlackTree (  )  [inline]

Destroy the tree.

Definition at line 771 of file redblacktree.h.


Member Function Documentation

template<typename K, typename Allocator = CS::Container::DefaultRedBlackTreeAllocator<K>, template< typename _K, typename K2 > class Ordering = CS::Container::RedBlackTreeOrderingTotal>
bool csRedBlackTree< K, Allocator, Ordering >::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 820 of file redblacktree.h.

template<typename K, typename Allocator = CS::Container::DefaultRedBlackTreeAllocator<K>, template< typename _K, typename K2 > class Ordering = CS::Container::RedBlackTreeOrderingTotal>
Node* csRedBlackTree< K, Allocator, Ordering >::CreateNode ( Node *  parent,
const K &  key 
) [inline, protected]

Create a new tree node.

Definition at line 267 of file redblacktree.h.

template<typename K, typename Allocator = CS::Container::DefaultRedBlackTreeAllocator<K>, template< typename _K, typename K2 > class Ordering = CS::Container::RedBlackTreeOrderingTotal>
void csRedBlackTree< K, Allocator, Ordering >::Delete ( Iterator it  )  [inline]

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

Remarks:
Will repoint the iterator to the following element.

Reimplemented in csRedBlackTreeMap< typename TreeTraitsType::MeshNodeKeyType, MeshNode *, MeshNodeTreeBlockRefAlloc >.

Definition at line 1027 of file redblacktree.h.

template<typename K, typename Allocator = CS::Container::DefaultRedBlackTreeAllocator<K>, template< typename _K, typename K2 > class Ordering = CS::Container::RedBlackTreeOrderingTotal>
bool csRedBlackTree< K, Allocator, Ordering >::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 791 of file redblacktree.h.

template<typename K, typename Allocator = CS::Container::DefaultRedBlackTreeAllocator<K>, template< typename _K, typename K2 > class Ordering = CS::Container::RedBlackTreeOrderingTotal>
void csRedBlackTree< K, Allocator, Ordering >::DeleteAll (  )  [inline]
template<typename K, typename Allocator = CS::Container::DefaultRedBlackTreeAllocator<K>, template< typename _K, typename K2 > class Ordering = CS::Container::RedBlackTreeOrderingTotal>
bool csRedBlackTree< K, Allocator, Ordering >::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 803 of file redblacktree.h.

template<typename K, typename Allocator = CS::Container::DefaultRedBlackTreeAllocator<K>, template< typename _K, typename K2 > class Ordering = CS::Container::RedBlackTreeOrderingTotal>
void csRedBlackTree< K, Allocator, Ordering >::DeleteFixup ( Node *  node,
Node *  nilParent 
) [inline, protected]

Fix up the RB tree after a deletion.

Definition at line 490 of file redblacktree.h.

template<typename K, typename Allocator = CS::Container::DefaultRedBlackTreeAllocator<K>, template< typename _K, typename K2 > class Ordering = CS::Container::RedBlackTreeOrderingTotal>
void csRedBlackTree< K, Allocator, Ordering >::DeleteNode ( Node *  node  )  [inline, protected]

Delete a node from the tree.

Definition at line 454 of file redblacktree.h.

template<typename K, typename Allocator = CS::Container::DefaultRedBlackTreeAllocator<K>, template< typename _K, typename K2 > class Ordering = CS::Container::RedBlackTreeOrderingTotal>
void csRedBlackTree< K, Allocator, Ordering >::Empty (  )  [inline]
template<typename K, typename Allocator = CS::Container::DefaultRedBlackTreeAllocator<K>, template< typename _K, typename K2 > class Ordering = CS::Container::RedBlackTreeOrderingTotal>
template<typename K2 >
const K& csRedBlackTree< K, Allocator, Ordering >::Find ( const K2 &  other,
const K &  fallback 
) const [inline]

Locate key that is equal to other.

Definition at line 831 of file redblacktree.h.

template<typename K, typename Allocator = CS::Container::DefaultRedBlackTreeAllocator<K>, template< typename _K, typename K2 > class Ordering = CS::Container::RedBlackTreeOrderingTotal>
template<typename K2 >
const K* csRedBlackTree< K, Allocator, Ordering >::Find ( const K2 &  other  )  const [inline]

Locate key that is equal to other.

Definition at line 825 of file redblacktree.h.

template<typename K, typename Allocator = CS::Container::DefaultRedBlackTreeAllocator<K>, template< typename _K, typename K2 > class Ordering = CS::Container::RedBlackTreeOrderingTotal>
template<typename K2 >
const K& csRedBlackTree< K, Allocator, Ordering >::FindGreatestSmallerEqual ( const K2 &  other,
const K &  fallback 
) const [inline]

Locate key that is equal to other.

Definition at line 867 of file redblacktree.h.

template<typename K, typename Allocator = CS::Container::DefaultRedBlackTreeAllocator<K>, template< typename _K, typename K2 > class Ordering = CS::Container::RedBlackTreeOrderingTotal>
template<typename K2 >
const K* csRedBlackTree< K, Allocator, Ordering >::FindGreatestSmallerEqual ( const K2 &  other  )  const [inline]

Locate greatest key smaller or equal to other.

Definition at line 861 of file redblacktree.h.

template<typename K, typename Allocator = CS::Container::DefaultRedBlackTreeAllocator<K>, template< typename _K, typename K2 > class Ordering = CS::Container::RedBlackTreeOrderingTotal>
template<typename K2 >
K& csRedBlackTree< K, Allocator, Ordering >::FindInternal ( const K2 &  other,
K &  fallback 
) [inline, protected]

Locate key that is equal to other.

Definition at line 749 of file redblacktree.h.

template<typename K, typename Allocator = CS::Container::DefaultRedBlackTreeAllocator<K>, template< typename _K, typename K2 > class Ordering = CS::Container::RedBlackTreeOrderingTotal>
template<typename K2 >
K* csRedBlackTree< K, Allocator, Ordering >::FindInternal ( const K2 &  other  )  [inline, protected]

Locate key that is equal to other.

Definition at line 743 of file redblacktree.h.

template<typename K, typename Allocator = CS::Container::DefaultRedBlackTreeAllocator<K>, template< typename _K, typename K2 > class Ordering = CS::Container::RedBlackTreeOrderingTotal>
template<typename K2 >
const K& csRedBlackTree< K, Allocator, Ordering >::FindSmallestGreaterEqual ( const K2 &  other,
const K &  fallback 
) const [inline]

Locate key that is equal to other.

Definition at line 850 of file redblacktree.h.

template<typename K, typename Allocator = CS::Container::DefaultRedBlackTreeAllocator<K>, template< typename _K, typename K2 > class Ordering = CS::Container::RedBlackTreeOrderingTotal>
template<typename K2 >
const K* csRedBlackTree< K, Allocator, Ordering >::FindSmallestGreaterEqual ( const K2 &  other  )  const [inline]

Locate smallest key greater or equal to other.

Definition at line 844 of file redblacktree.h.

template<typename K, typename Allocator = CS::Container::DefaultRedBlackTreeAllocator<K>, template< typename _K, typename K2 > class Ordering = CS::Container::RedBlackTreeOrderingTotal>
Iterator csRedBlackTree< K, Allocator, Ordering >::GetIterator (  )  [inline]
template<typename K, typename Allocator = CS::Container::DefaultRedBlackTreeAllocator<K>, template< typename _K, typename K2 > class Ordering = CS::Container::RedBlackTreeOrderingTotal>
ConstIterator csRedBlackTree< K, Allocator, Ordering >::GetIterator (  )  const [inline]
template<typename K, typename Allocator = CS::Container::DefaultRedBlackTreeAllocator<K>, template< typename _K, typename K2 > class Ordering = CS::Container::RedBlackTreeOrderingTotal>
ReverseIterator csRedBlackTree< K, Allocator, Ordering >::GetReverseIterator (  )  [inline]
template<typename K, typename Allocator = CS::Container::DefaultRedBlackTreeAllocator<K>, template< typename _K, typename K2 > class Ordering = CS::Container::RedBlackTreeOrderingTotal>
ConstReverseIterator csRedBlackTree< K, Allocator, Ordering >::GetReverseIterator (  )  const [inline]
template<typename K, typename Allocator = CS::Container::DefaultRedBlackTreeAllocator<K>, template< typename _K, typename K2 > class Ordering = CS::Container::RedBlackTreeOrderingTotal>
bool csRedBlackTree< K, Allocator, Ordering >::In ( const K &  key  )  const [inline]

Check whether a key is in the tree.

Definition at line 811 of file redblacktree.h.

template<typename K, typename Allocator = CS::Container::DefaultRedBlackTreeAllocator<K>, template< typename _K, typename K2 > class Ordering = CS::Container::RedBlackTreeOrderingTotal>
const K* csRedBlackTree< K, Allocator, Ordering >::Insert ( const K &  key  )  [inline]

Insert a key.

Returns:
A pointer to the copy of the key stored in the tree.

Definition at line 777 of file redblacktree.h.

template<typename K, typename Allocator = CS::Container::DefaultRedBlackTreeAllocator<K>, template< typename _K, typename K2 > class Ordering = CS::Container::RedBlackTreeOrderingTotal>
void csRedBlackTree< K, Allocator, Ordering >::InsertFixup ( Node *  node  )  [inline, protected]

Fix up the RB tree after an insert.

Definition at line 388 of file redblacktree.h.

template<typename K, typename Allocator = CS::Container::DefaultRedBlackTreeAllocator<K>, template< typename _K, typename K2 > class Ordering = CS::Container::RedBlackTreeOrderingTotal>
bool csRedBlackTree< K, Allocator, Ordering >::IsBlack ( Node *  node  )  const [inline, protected]

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

Definition at line 382 of file redblacktree.h.

template<typename K, typename Allocator = CS::Container::DefaultRedBlackTreeAllocator<K>, template< typename _K, typename K2 > class Ordering = CS::Container::RedBlackTreeOrderingTotal>
bool csRedBlackTree< K, Allocator, Ordering >::IsEmpty (  )  const [inline]
template<typename K, typename Allocator = CS::Container::DefaultRedBlackTreeAllocator<K>, template< typename _K, typename K2 > class Ordering = CS::Container::RedBlackTreeOrderingTotal>
bool csRedBlackTree< K, Allocator, Ordering >::IsRed ( Node *  node  )  const [inline, protected]

Check whether a node is red.

Definition at line 385 of file redblacktree.h.

template<typename K, typename Allocator = CS::Container::DefaultRedBlackTreeAllocator<K>, template< typename _K, typename K2 > class Ordering = CS::Container::RedBlackTreeOrderingTotal>
template<typename K2 >
Node* csRedBlackTree< K, Allocator, Ordering >::LocateNode ( Node *  node,
const K2 &  other 
) const [inline, protected]

Find a node for a key.

Definition at line 566 of file redblacktree.h.

template<typename K, typename Allocator = CS::Container::DefaultRedBlackTreeAllocator<K>, template< typename _K, typename K2 > class Ordering = CS::Container::RedBlackTreeOrderingTotal>
Node* csRedBlackTree< K, Allocator, Ordering >::LocateNodeExact ( Node *  node,
const K *  key 
) const [inline, protected]

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

Definition at line 586 of file redblacktree.h.

template<typename K, typename Allocator = CS::Container::DefaultRedBlackTreeAllocator<K>, template< typename _K, typename K2 > class Ordering = CS::Container::RedBlackTreeOrderingTotal>
static Node* csRedBlackTree< K, Allocator, Ordering >::Predecessor ( const Node *  node  )  [inline, static, protected]

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

Definition at line 626 of file redblacktree.h.

template<typename K, typename Allocator = CS::Container::DefaultRedBlackTreeAllocator<K>, template< typename _K, typename K2 > class Ordering = CS::Container::RedBlackTreeOrderingTotal>
void csRedBlackTree< K, Allocator, Ordering >::RecursiveCopy ( Node *&  to,
Node *  parent,
const Node *  from 
) [inline, protected]

Duplicate a subtree.

Definition at line 716 of file redblacktree.h.

template<typename K, typename Allocator = CS::Container::DefaultRedBlackTreeAllocator<K>, template< typename _K, typename K2 > class Ordering = CS::Container::RedBlackTreeOrderingTotal>
void csRedBlackTree< K, Allocator, Ordering >::RecursiveDelete ( Node *  node  )  [inline, protected]

Recursively delete a subtree.

Definition at line 732 of file redblacktree.h.

template<typename K, typename Allocator = CS::Container::DefaultRedBlackTreeAllocator<K>, template< typename _K, typename K2 > class Ordering = CS::Container::RedBlackTreeOrderingTotal>
template<typename K2 >
Node* csRedBlackTree< K, Allocator, Ordering >::RecursiveFindGSE ( Node *  node,
const K2 &  other 
) const [inline, protected]

Locate greatest key that is smaller or equal to 'other'.

Definition at line 647 of file redblacktree.h.

template<typename K, typename Allocator = CS::Container::DefaultRedBlackTreeAllocator<K>, template< typename _K, typename K2 > class Ordering = CS::Container::RedBlackTreeOrderingTotal>
Node* csRedBlackTree< K, Allocator, Ordering >::RecursiveFindInsertCandidate ( Node *  parent,
Node *&  node,
const K &  key,
uint  depth,
InsertCandidate &  candidate 
) [inline, protected]

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

Definition at line 287 of file redblacktree.h.

template<typename K, typename Allocator = CS::Container::DefaultRedBlackTreeAllocator<K>, template< typename _K, typename K2 > class Ordering = CS::Container::RedBlackTreeOrderingTotal>
template<typename K2 >
Node* csRedBlackTree< K, Allocator, Ordering >::RecursiveFindSGE ( Node *  node,
const K2 &  other 
) const [inline, protected]

Locate smallest key that is greater or equal to 'other'.

Definition at line 678 of file redblacktree.h.

template<typename K, typename Allocator = CS::Container::DefaultRedBlackTreeAllocator<K>, template< typename _K, typename K2 > class Ordering = CS::Container::RedBlackTreeOrderingTotal>
template<typename CB >
void csRedBlackTree< K, Allocator, Ordering >::RecursiveTraverseInOrder ( Node *  node,
CB &  callback 
) const [inline, protected]

Traverse tree.

Definition at line 708 of file redblacktree.h.

template<typename K, typename Allocator = CS::Container::DefaultRedBlackTreeAllocator<K>, template< typename _K, typename K2 > class Ordering = CS::Container::RedBlackTreeOrderingTotal>
void csRedBlackTree< K, Allocator, Ordering >::RotateLeft ( Node *  pivot  )  [inline, protected]

Left-rotate subtree around 'pivot'.

Definition at line 342 of file redblacktree.h.

template<typename K, typename Allocator = CS::Container::DefaultRedBlackTreeAllocator<K>, template< typename _K, typename K2 > class Ordering = CS::Container::RedBlackTreeOrderingTotal>
void csRedBlackTree< K, Allocator, Ordering >::RotateRight ( Node *  pivot  )  [inline, protected]

Right-rotate subtree around 'pivot'.

Definition at line 362 of file redblacktree.h.

template<typename K, typename Allocator = CS::Container::DefaultRedBlackTreeAllocator<K>, template< typename _K, typename K2 > class Ordering = CS::Container::RedBlackTreeOrderingTotal>
static Node* csRedBlackTree< K, Allocator, Ordering >::Successor ( const Node *  node  )  [inline, static, protected]

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

Definition at line 608 of file redblacktree.h.

template<typename K, typename Allocator = CS::Container::DefaultRedBlackTreeAllocator<K>, template< typename _K, typename K2 > class Ordering = CS::Container::RedBlackTreeOrderingTotal>
template<typename CB >
void csRedBlackTree< K, Allocator, Ordering >::TraverseInOrder ( CB &  callback  )  const [inline]

Friends And Related Function Documentation

template<typename K, typename Allocator = CS::Container::DefaultRedBlackTreeAllocator<K>, template< typename _K, typename K2 > class Ordering = CS::Container::RedBlackTreeOrderingTotal>
friend class ConstIterator [friend]
template<typename K, typename Allocator = CS::Container::DefaultRedBlackTreeAllocator<K>, template< typename _K, typename K2 > class Ordering = CS::Container::RedBlackTreeOrderingTotal>
friend class ConstReverseIterator [friend]
template<typename K, typename Allocator = CS::Container::DefaultRedBlackTreeAllocator<K>, template< typename _K, typename K2 > class Ordering = CS::Container::RedBlackTreeOrderingTotal>
friend class Iterator [friend]

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

Generated for Crystal Space 2.1 by doxygen 1.6.1