cheshirekow  v0.1.0
Public Types | Public Member Functions | Static Public Attributes | Private Member Functions | Private Attributes | List of all members
mpblocks::redblack::Tree< Traits > Class Template Reference

implements red black trees from CLRS More...

#include <mpblocks/redblack/iterator.h>

Public Types

typedef Traits::Key Key
 
typedef Traits::NodeOps NodeOps
 
typedef Traits::NodeRef NodeRef
 

Public Member Functions

Iterator< Traits > begin ()
 
void clear ()
 
Iterator< Traits > end ()
 
void insert (NodeRef z)
 
void insertFixup (NodeRef z)
 
auto key (NodeRef N) -> decltype(m_ops.key(N))
 
void leftRotate (NodeRef x)
 
NodeRef remove (NodeRef z)
 
void removeFixup (NodeRef x)
 
void rightRotate (NodeRef x)
 
size_t size ()
 
 Tree (NodeRef Nil)
 
NodeRef treeMaximum (NodeRef x)
 CLRS 12.2 page 258. More...
 
NodeRef treeMinimum (NodeRef x)
 CLRS 12.2 page 258. More...
 
NodeRef treePredecessor (NodeRef x)
 CLRS 12.2 page 259. More...
 
NodeRef treeSuccessor (NodeRef x)
 CLRS 12.2 page 259. More...
 

Static Public Attributes

static const Color BLACK = Color::BLACK
 
static const Color RED = Color::RED
 

Private Member Functions

Color & color (NodeRef N)
 
NodeRef & left (NodeRef N)
 
NodeRef & p (NodeRef N)
 
NodeRef & right (NodeRef N)
 
void swapKey (NodeRef a, NodeRef b)
 

Private Attributes

NodeOps m_ops
 
size_t m_size
 
NodeRef Nil
 
NodeRef root
 

Detailed Description

template<class Traits>
class mpblocks::redblack::Tree< Traits >

implements red black trees from CLRS

Definition at line 34 of file iterator.h.

Member Typedef Documentation

template<class Traits >
typedef Traits::Key mpblocks::redblack::Tree< Traits >::Key

Definition at line 40 of file tree.h.

template<class Traits >
typedef Traits::NodeOps mpblocks::redblack::Tree< Traits >::NodeOps

Definition at line 39 of file tree.h.

template<class Traits >
typedef Traits::NodeRef mpblocks::redblack::Tree< Traits >::NodeRef

Definition at line 38 of file tree.h.

Constructor & Destructor Documentation

template<class Traits >
mpblocks::redblack::Tree< Traits >::Tree ( NodeRef  Nil)
inline

Definition at line 60 of file tree.h.

Member Function Documentation

template<class Traits >
Iterator<Traits> mpblocks::redblack::Tree< Traits >::begin ( )
inline

Definition at line 289 of file tree.h.

template<class Traits >
void mpblocks::redblack::Tree< Traits >::clear ( )
inline

Definition at line 62 of file tree.h.

template<class Traits >
Color& mpblocks::redblack::Tree< Traits >::color ( NodeRef  N)
inlineprivate

Definition at line 52 of file tree.h.

template<class Traits >
Iterator<Traits> mpblocks::redblack::Tree< Traits >::end ( )
inline

Definition at line 291 of file tree.h.

template<class Traits >
void mpblocks::redblack::Tree< Traits >::insert ( NodeRef  z)
inline

Definition at line 144 of file tree.h.

template<class Traits >
void mpblocks::redblack::Tree< Traits >::insertFixup ( NodeRef  z)
inline

Definition at line 105 of file tree.h.

template<class Traits >
auto mpblocks::redblack::Tree< Traits >::key ( NodeRef  N) -> decltype(m_ops.key(N))
inline

Definition at line 67 of file tree.h.

template<class Traits >
NodeRef& mpblocks::redblack::Tree< Traits >::left ( NodeRef  N)
inlineprivate

Definition at line 54 of file tree.h.

template<class Traits >
void mpblocks::redblack::Tree< Traits >::leftRotate ( NodeRef  x)
inline

Definition at line 69 of file tree.h.

template<class Traits >
NodeRef& mpblocks::redblack::Tree< Traits >::p ( NodeRef  N)
inlineprivate

Definition at line 53 of file tree.h.

template<class Traits >
NodeRef mpblocks::redblack::Tree< Traits >::remove ( NodeRef  z)
inline

Definition at line 261 of file tree.h.

template<class Traits >
void mpblocks::redblack::Tree< Traits >::removeFixup ( NodeRef  x)
inline

Definition at line 170 of file tree.h.

template<class Traits >
NodeRef& mpblocks::redblack::Tree< Traits >::right ( NodeRef  N)
inlineprivate

Definition at line 55 of file tree.h.

template<class Traits >
void mpblocks::redblack::Tree< Traits >::rightRotate ( NodeRef  x)
inline

Definition at line 87 of file tree.h.

template<class Traits >
size_t mpblocks::redblack::Tree< Traits >::size ( )
inline

Definition at line 293 of file tree.h.

template<class Traits >
void mpblocks::redblack::Tree< Traits >::swapKey ( NodeRef  a,
NodeRef  b 
)
inlineprivate

Definition at line 57 of file tree.h.

template<class Traits >
NodeRef mpblocks::redblack::Tree< Traits >::treeMaximum ( NodeRef  x)
inline

CLRS 12.2 page 258.

Definition at line 234 of file tree.h.

template<class Traits >
NodeRef mpblocks::redblack::Tree< Traits >::treeMinimum ( NodeRef  x)
inline

CLRS 12.2 page 258.

Definition at line 228 of file tree.h.

template<class Traits >
NodeRef mpblocks::redblack::Tree< Traits >::treePredecessor ( NodeRef  x)
inline

CLRS 12.2 page 259.

Definition at line 251 of file tree.h.

template<class Traits >
NodeRef mpblocks::redblack::Tree< Traits >::treeSuccessor ( NodeRef  x)
inline

CLRS 12.2 page 259.

Definition at line 240 of file tree.h.

Member Data Documentation

template<class Traits >
const Color mpblocks::redblack::Tree< Traits >::BLACK = Color::BLACK
static

Definition at line 43 of file tree.h.

template<class Traits >
NodeOps mpblocks::redblack::Tree< Traits >::m_ops
private

Definition at line 50 of file tree.h.

template<class Traits >
size_t mpblocks::redblack::Tree< Traits >::m_size
private

Definition at line 49 of file tree.h.

template<class Traits >
NodeRef mpblocks::redblack::Tree< Traits >::Nil
private

Definition at line 46 of file tree.h.

template<class Traits >
const Color mpblocks::redblack::Tree< Traits >::RED = Color::RED
static

Definition at line 42 of file tree.h.

template<class Traits >
NodeRef mpblocks::redblack::Tree< Traits >::root
private

Definition at line 47 of file tree.h.

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