Simple Application Framework  1
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines
Classes | Public Member Functions | Protected Types | Protected Member Functions | Static Protected Member Functions
Saf::Algo::Struct::RedBlackTree< KeyType, RecType, KeySelectorType, CompType > Class Template Reference

Generic red/black tree implementation. More...

#include <RedBlackTree.h>

Inherited by Saf::Collection::TreeMap< Text::String, Text::String >.

List of all members.

Classes

class  ConstIterator
 Bidirectional non-mutable RedBlackTree iterator. More...
class  Iterator
 Bidirectional mutable RedBlackTree iterator. More...
class  Node
 Tree node. More...

Public Member Functions

 RedBlackTree ()
 Constructor.
 RedBlackTree (const MyType &rbt)
 Copy constructor.
 ~RedBlackTree ()
 Destructor.
Iterator Back ()
 Iterator to the right-most element.
ConstIterator Back () const
 Iterator to the right-most element.
Iterator Begin ()
 Iterator to the left-most element.
ConstIterator Begin () const
 Iterator to the left-most element.
bool Contains (const KeyType &key) const
 Check if the tree contains an element whose key has equivalent ordering to key.
Size Elements () const
 Get the number of elements in the tree.
Iterator End ()
 Iterator one behind the last element.
ConstIterator End () const
 Iterator one behind the last element.
Iterator Erase (Iterator iter)
 Remove an element from the tree.
Iterator Find (const KeyType &key)
 Find an element with a key that has equivalent ordering with key.
ConstIterator Find (const KeyType &key) const
 Find an element with a key that has equivalent ordering with key.
MyType & Free ()
 Free the memory occupied by the tree.
Iterator Front ()
 Iterator to the left-most element.
ConstIterator Front () const
 Iterator to the left-most element.
Collection::Pair< Iterator, bool > Insert (const RecType &val)
 Insert a new value into the tree.
bool IsEmpty () const
 Returns true if the tree is empty.
Iterator LowerBound (const KeyType &key)
 Find the left-most element in the tree whose key does not compare less than key (using the tree tree's comparison predicate).
ConstIterator LowerBound (const KeyType &key) const
 Find the left-most element in the tree whose key does not compare less than key (using the tree tree's comparison predicate).
MyType & operator= (const MyType &rbt)
 Assignment operator.
MyType & Swap (MyType &rbt)
 Swap the contents of two red/black trees.
Iterator UpperBound (const KeyType &key)
 Find the left-most element in the tree whose key compares greater than key (using the tree tree's comparison predicate).
ConstIterator UpperBound (const KeyType &key) const
 Find the left-most element in the tree whose key compares greater than key (using the tree tree's comparison predicate).

Protected Types

typedef RedBlackTree< KeyType,
RecType, KeySelectorType,
CompType > 		MyType

Protected Member Functions

Node * AllocNode (const RecType &val, Node *parent, Uint8 flags)
 Create a new tree node with a given value.
Node * Head () const
 Get the head node of the tree.
bool IsLeftChild (Node *n) const
 Check whether a node is a left child of its parent.
Node *& Leftmost () const
 Get the left-most element.
Node *& Rightmost () const
 Get the right-most element.
Node *& Root () const
 Get the root node of the tree.
void Rotate (Node *root, Int32 dir)
 Perform single rotation of a subtree.
Node * TreeLowerBound (const KeyType &key) const
 Find the left-most element with a key that does not compare less than key.
Node * TreeUpperBound (const KeyType &key) const
 Find the left-most element with a key that compares larger than key.

Static Protected Member Functions

static Node * TreeMax (Node *root)
 Find an element with the largest key in a subtree.
static Node * TreeMin (Node *root)
 Find an element with the smallest key in a subtree.
static Node * TreeNext (Node *node)
 Find the successor of a node.
static Node * TreePrev (Node *node)
 Find the predecessor of a node.

Detailed Description

template<class KeyType, class RecType, class KeySelectorType, class CompType>
class Saf::Algo::Struct::RedBlackTree< KeyType, RecType, KeySelectorType, CompType >

Generic red/black tree implementation.

This class implements a classic red/black tree data structure that stores its elements in a sorted order and allows fast insertion and removal of values in guaranteed logarithmic time.

Each element in the tree consists of a key and a mapped value. The keys are used to sort the elements from lower to higher key values according to a supplied strict weak ordering and have to be unique. The keys can also be used to look-up the mapped value in logarithmic time.

The class can be exploited to implement efficient associative or set containers. In the latter case, the key and the mapped value may refer to the same object.

Iterator category: Bidirectional.

Template Parameters:
KeyTypeKey data type.
RecTypeThe data type of records stored in the tree nodes. The RecType will be typically a pair containing the key and the mapped value.
KeySelectorTypeUnary functor that takes a value of RecType and extracts the associated key.
CompTypeA binary predicate on KeyType inducing a strict weak ordering on the keys.
See also:
Collection::Map, Collection::Set, HashTable.

Member Typedef Documentation

template<class KeyType, class RecType, class KeySelectorType, class CompType>
typedef RedBlackTree<KeyType,RecType,KeySelectorType,CompType> Saf::Algo::Struct::RedBlackTree< KeyType, RecType, KeySelectorType, CompType >::MyType [protected]

Reimplemented in Saf::Collection::TreeMap< KeyType, ValType, CompType >, Saf::Collection::TreeMap< Text::String, Text::String >, and Saf::Collection::TreeSet< ValType, CompType >.

Constructor & Destructor Documentation

template<class KeyType, class RecType, class KeySelectorType, class CompType>
Saf::Algo::Struct::RedBlackTree< KeyType, RecType, KeySelectorType, CompType >::RedBlackTree ( ) [inline]

Constructor.

Creates an empty tree.

template<class KeyType, class RecType, class KeySelectorType, class CompType>
Saf::Algo::Struct::RedBlackTree< KeyType, RecType, KeySelectorType, CompType >::RedBlackTree ( const MyType &  rbt) [inline]

Copy constructor.

template<class KeyType, class RecType, class KeySelectorType, class CompType>
Saf::Algo::Struct::RedBlackTree< KeyType, RecType, KeySelectorType, CompType >::~RedBlackTree ( ) [inline]

Destructor.

Member Function Documentation

template<class KeyType, class RecType, class KeySelectorType, class CompType>
Node* Saf::Algo::Struct::RedBlackTree< KeyType, RecType, KeySelectorType, CompType >::AllocNode ( const RecType &  val,
Node *  parent,
Uint8  flags 
) [inline, protected]

Create a new tree node with a given value.

template<class KeyType, class RecType, class KeySelectorType, class CompType>
Iterator Saf::Algo::Struct::RedBlackTree< KeyType, RecType, KeySelectorType, CompType >::Back ( ) [inline]

Iterator to the right-most element.

template<class KeyType, class RecType, class KeySelectorType, class CompType>
ConstIterator Saf::Algo::Struct::RedBlackTree< KeyType, RecType, KeySelectorType, CompType >::Back ( ) const [inline]

Iterator to the right-most element.

template<class KeyType, class RecType, class KeySelectorType, class CompType>
Iterator Saf::Algo::Struct::RedBlackTree< KeyType, RecType, KeySelectorType, CompType >::Begin ( ) [inline]

Iterator to the left-most element.

template<class KeyType, class RecType, class KeySelectorType, class CompType>
ConstIterator Saf::Algo::Struct::RedBlackTree< KeyType, RecType, KeySelectorType, CompType >::Begin ( ) const [inline]

Iterator to the left-most element.

template<class KeyType, class RecType, class KeySelectorType, class CompType>
bool Saf::Algo::Struct::RedBlackTree< KeyType, RecType, KeySelectorType, CompType >::Contains ( const KeyType &  key) const [inline]

Check if the tree contains an element whose key has equivalent ordering to key.

Properties:

  • Worst-case time complexity: $ \mathcal{O}(\log \mathrm{Elements()}) $.
template<class KeyType, class RecType, class KeySelectorType, class CompType>
Size Saf::Algo::Struct::RedBlackTree< KeyType, RecType, KeySelectorType, CompType >::Elements ( ) const [inline]

Get the number of elements in the tree.

Properties:

  • Worst-case time complexity: $ \mathcal{O}(1) $.
template<class KeyType, class RecType, class KeySelectorType, class CompType>
Iterator Saf::Algo::Struct::RedBlackTree< KeyType, RecType, KeySelectorType, CompType >::End ( ) [inline]

Iterator one behind the last element.

template<class KeyType, class RecType, class KeySelectorType, class CompType>
ConstIterator Saf::Algo::Struct::RedBlackTree< KeyType, RecType, KeySelectorType, CompType >::End ( ) const [inline]

Iterator one behind the last element.

template<class KeyType, class RecType, class KeySelectorType, class CompType>
Iterator Saf::Algo::Struct::RedBlackTree< KeyType, RecType, KeySelectorType, CompType >::Erase ( Iterator  iter) [inline]

Remove an element from the tree.

Properties:

  • Worst-case time complexity: $ \mathcal{O}(\log \mathrm{Elements()}) $.
  • Iterator invalidation: Does not invalidate any iterators except for the deleted one.
Returns:
Iterator to the successor of the erased element.
template<class KeyType, class RecType, class KeySelectorType, class CompType>
Iterator Saf::Algo::Struct::RedBlackTree< KeyType, RecType, KeySelectorType, CompType >::Find ( const KeyType &  key) [inline]

Find an element with a key that has equivalent ordering with key.

Returns End() if no such element appears in the tree.

Properties:

  • Worst-case time complexity: $ \mathcal{O}(\log \mathrm{Elements()}) $.
template<class KeyType, class RecType, class KeySelectorType, class CompType>
ConstIterator Saf::Algo::Struct::RedBlackTree< KeyType, RecType, KeySelectorType, CompType >::Find ( const KeyType &  key) const [inline]

Find an element with a key that has equivalent ordering with key.

Returns End() if no such element appears in the tree.

Properties:

  • Worst-case time complexity: $ \mathcal{O}(\log \mathrm{Elements()}) $.
template<class KeyType, class RecType, class KeySelectorType, class CompType>
MyType& Saf::Algo::Struct::RedBlackTree< KeyType, RecType, KeySelectorType, CompType >::Free ( ) [inline]

Free the memory occupied by the tree.

Warning:
The destructor of RecType should never throw. Otherwise the tree will end up in an inconsistent state in case of an exception.
template<class KeyType, class RecType, class KeySelectorType, class CompType>
Iterator Saf::Algo::Struct::RedBlackTree< KeyType, RecType, KeySelectorType, CompType >::Front ( ) [inline]

Iterator to the left-most element.

template<class KeyType, class RecType, class KeySelectorType, class CompType>
ConstIterator Saf::Algo::Struct::RedBlackTree< KeyType, RecType, KeySelectorType, CompType >::Front ( ) const [inline]

Iterator to the left-most element.

template<class KeyType, class RecType, class KeySelectorType, class CompType>
Node* Saf::Algo::Struct::RedBlackTree< KeyType, RecType, KeySelectorType, CompType >::Head ( ) const [inline, protected]

Get the head node of the tree.

template<class KeyType, class RecType, class KeySelectorType, class CompType>
Collection::Pair<Iterator,bool> Saf::Algo::Struct::RedBlackTree< KeyType, RecType, KeySelectorType, CompType >::Insert ( const RecType &  val) [inline]

Insert a new value into the tree.

The first member of the returned pair is either an iterator to the newly created element or to an existing element with equivalent ordering that already appears in the tree (the mapped value is not changed in this case). The second member is set to true in the former situation and false in the latter.

Properties:

  • Worst-case time complexity: $ \mathcal{O}(\log \mathrm{Elements()}) $.
  • Iterator invalidation: Does not invalidate any iterators.
template<class KeyType, class RecType, class KeySelectorType, class CompType>
bool Saf::Algo::Struct::RedBlackTree< KeyType, RecType, KeySelectorType, CompType >::IsEmpty ( ) const [inline]

Returns true if the tree is empty.

Properties:

  • Worst-case time complexity: $ \mathcal{O}(1) $.
template<class KeyType, class RecType, class KeySelectorType, class CompType>
bool Saf::Algo::Struct::RedBlackTree< KeyType, RecType, KeySelectorType, CompType >::IsLeftChild ( Node *  n) const [inline, protected]

Check whether a node is a left child of its parent.

template<class KeyType, class RecType, class KeySelectorType, class CompType>
Node*& Saf::Algo::Struct::RedBlackTree< KeyType, RecType, KeySelectorType, CompType >::Leftmost ( ) const [inline, protected]

Get the left-most element.

template<class KeyType, class RecType, class KeySelectorType, class CompType>
Iterator Saf::Algo::Struct::RedBlackTree< KeyType, RecType, KeySelectorType, CompType >::LowerBound ( const KeyType &  key) [inline]

Find the left-most element in the tree whose key does not compare less than key (using the tree tree's comparison predicate).

Properties:

  • Worst-case time complexity: $ \mathcal{O}(\log \mathrm{Elements()}) $.
template<class KeyType, class RecType, class KeySelectorType, class CompType>
ConstIterator Saf::Algo::Struct::RedBlackTree< KeyType, RecType, KeySelectorType, CompType >::LowerBound ( const KeyType &  key) const [inline]

Find the left-most element in the tree whose key does not compare less than key (using the tree tree's comparison predicate).

Properties:

  • Worst-case time complexity: $ \mathcal{O}(\log \mathrm{Elements()}) $.
template<class KeyType, class RecType, class KeySelectorType, class CompType>
MyType& Saf::Algo::Struct::RedBlackTree< KeyType, RecType, KeySelectorType, CompType >::operator= ( const MyType &  rbt) [inline]

Assignment operator.

The current tree is deallocated (using the Free() method) before the copy operation to save memory. If any exception is thrown during copy the tree remains empty (i.e., all nodes that were already copied are deallocated).

Warning:
The destructor of RecType should never throw. Otherwise the tree may end up in an inconsistent state in case of an exception.

Reimplemented in Saf::Collection::TreeMap< Text::String, Text::String >.

template<class KeyType, class RecType, class KeySelectorType, class CompType>
Node*& Saf::Algo::Struct::RedBlackTree< KeyType, RecType, KeySelectorType, CompType >::Rightmost ( ) const [inline, protected]

Get the right-most element.

template<class KeyType, class RecType, class KeySelectorType, class CompType>
Node*& Saf::Algo::Struct::RedBlackTree< KeyType, RecType, KeySelectorType, CompType >::Root ( ) const [inline, protected]

Get the root node of the tree.

template<class KeyType, class RecType, class KeySelectorType, class CompType>
void Saf::Algo::Struct::RedBlackTree< KeyType, RecType, KeySelectorType, CompType >::Rotate ( Node *  root,
Int32  dir 
) [inline, protected]

Perform single rotation of a subtree.

template<class KeyType, class RecType, class KeySelectorType, class CompType>
MyType& Saf::Algo::Struct::RedBlackTree< KeyType, RecType, KeySelectorType, CompType >::Swap ( MyType &  rbt) [inline]

Swap the contents of two red/black trees.

Properties:

  • Worst-case time complexity: $ \mathcal{O}(1) $.

Reimplemented in Saf::Collection::TreeMap< Text::String, Text::String >.

template<class KeyType, class RecType, class KeySelectorType, class CompType>
Node* Saf::Algo::Struct::RedBlackTree< KeyType, RecType, KeySelectorType, CompType >::TreeLowerBound ( const KeyType &  key) const [inline, protected]

Find the left-most element with a key that does not compare less than key.

template<class KeyType, class RecType, class KeySelectorType, class CompType>
static Node* Saf::Algo::Struct::RedBlackTree< KeyType, RecType, KeySelectorType, CompType >::TreeMax ( Node *  root) [inline, static, protected]

Find an element with the largest key in a subtree.

template<class KeyType, class RecType, class KeySelectorType, class CompType>
static Node* Saf::Algo::Struct::RedBlackTree< KeyType, RecType, KeySelectorType, CompType >::TreeMin ( Node *  root) [inline, static, protected]

Find an element with the smallest key in a subtree.

template<class KeyType, class RecType, class KeySelectorType, class CompType>
static Node* Saf::Algo::Struct::RedBlackTree< KeyType, RecType, KeySelectorType, CompType >::TreeNext ( Node *  node) [inline, static, protected]

Find the successor of a node.

template<class KeyType, class RecType, class KeySelectorType, class CompType>
static Node* Saf::Algo::Struct::RedBlackTree< KeyType, RecType, KeySelectorType, CompType >::TreePrev ( Node *  node) [inline, static, protected]

Find the predecessor of a node.

template<class KeyType, class RecType, class KeySelectorType, class CompType>
Node* Saf::Algo::Struct::RedBlackTree< KeyType, RecType, KeySelectorType, CompType >::TreeUpperBound ( const KeyType &  key) const [inline, protected]

Find the left-most element with a key that compares larger than key.

template<class KeyType, class RecType, class KeySelectorType, class CompType>
Iterator Saf::Algo::Struct::RedBlackTree< KeyType, RecType, KeySelectorType, CompType >::UpperBound ( const KeyType &  key) [inline]

Find the left-most element in the tree whose key compares greater than key (using the tree tree's comparison predicate).

Properties:

  • Worst-case time complexity: $ \mathcal{O}(\log \mathrm{Elements()}) $.
template<class KeyType, class RecType, class KeySelectorType, class CompType>
ConstIterator Saf::Algo::Struct::RedBlackTree< KeyType, RecType, KeySelectorType, CompType >::UpperBound ( const KeyType &  key) const [inline]

Find the left-most element in the tree whose key compares greater than key (using the tree tree's comparison predicate).

Properties:

  • Worst-case time complexity: $ \mathcal{O}(\log \mathrm{Elements()}) $.
The documentation for this class was generated from the following file:
Generated on Tue May 8 2012 18:51:21 for Simple Application Framework by   doxygen 1.8.0