Public Types | Public Member Functions | Static Public Attributes | Protected Member Functions | Private Member Functions | Private Attributes | Static Private Attributes | List of all members
mn::container::base_rb_tree< TTreeTraits, TAllocator > Class Template Reference

#include <mn_rb_tree.hpp>

+ Collaboration diagram for mn::container::base_rb_tree< TTreeTraits, TAllocator >:

Public Types

using key_type = typename TTreeTraits::key_type
 
using value_type = typename TTreeTraits::value_type
 
using allocator_type = TAllocator
 
using self_type = base_rb_tree< TTreeTraits, TAllocator >
 
using size_type = mn::size_t
 
using node_type = rb_tree_node< value_type >
 
typedef void(* TravFunc) (node_type *n, size_type left, size_type depth)
 

Public Member Functions

 base_rb_tree (const allocator_type &allocator=allocator_type())
 
 ~base_rb_tree ()
 
node_type * insert (const value_type &v)
 
node_type * find_node (const key_type &key)
 
size_type erase (const key_type &key)
 
void erase (node_type *n)
 
void clear ()
 
void swap (base_rb_tree &other)
 
bool empty () const
 
size_type size () const
 
const node_type * begin ()
 
const node_type * find_next (node_type *n) const
 
size_type size (const node_type *n)
 
void validate ()
 
void validate (node_type *n)
 
void rotate_left (node_type *n)
 
void rotate_right (node_type *n)
 
void free_node (node_type *n, bool recursive)
 
 base_rb_tree (const base_rb_tree &)=delete
 
base_rb_tree & operator= (const base_rb_tree &)=delete
 
void traverse_node (node_type *n, TravFunc func, int depth)
 
void traverse (TravFunc func)
 

Static Public Attributes

static const size_type NodeSize = sizeof(node_type)
 

Protected Member Functions

void rebalance (node_type *new_node)
 
void rebalance_after_erase (node_type *n)
 

Private Member Functions

node_type * construct_node ()
 
void destruct_node (node_type *n)
 

Private Attributes

node_type * m_root
 
size_type m_size
 
allocator_type m_allocator
 

Static Private Attributes

static node_type ms_sentinel
 

Member Typedef Documentation

◆ allocator_type

template<class TTreeTraits , class TAllocator >
using mn::container::base_rb_tree< TTreeTraits, TAllocator >::allocator_type = TAllocator

◆ key_type

template<class TTreeTraits , class TAllocator >
using mn::container::base_rb_tree< TTreeTraits, TAllocator >::key_type = typename TTreeTraits::key_type

◆ node_type

template<class TTreeTraits , class TAllocator >
using mn::container::base_rb_tree< TTreeTraits, TAllocator >::node_type = rb_tree_node<value_type>

◆ self_type

template<class TTreeTraits , class TAllocator >
using mn::container::base_rb_tree< TTreeTraits, TAllocator >::self_type = base_rb_tree<TTreeTraits, TAllocator>

◆ size_type

template<class TTreeTraits , class TAllocator >
using mn::container::base_rb_tree< TTreeTraits, TAllocator >::size_type = mn::size_t

◆ TravFunc

template<class TTreeTraits , class TAllocator >
typedef void(* mn::container::base_rb_tree< TTreeTraits, TAllocator >::TravFunc) (node_type *n, size_type left, size_type depth)

◆ value_type

template<class TTreeTraits , class TAllocator >
using mn::container::base_rb_tree< TTreeTraits, TAllocator >::value_type = typename TTreeTraits::value_type

Constructor & Destructor Documentation

◆ base_rb_tree() [1/2]

template<class TTreeTraits , class TAllocator >
mn::container::base_rb_tree< TTreeTraits, TAllocator >::base_rb_tree ( const allocator_type &  allocator = allocator_type())
inlineexplicit

◆ ~base_rb_tree()

template<class TTreeTraits , class TAllocator >
mn::container::base_rb_tree< TTreeTraits, TAllocator >::~base_rb_tree ( )
inline

◆ base_rb_tree() [2/2]

template<class TTreeTraits , class TAllocator >
mn::container::base_rb_tree< TTreeTraits, TAllocator >::base_rb_tree ( const base_rb_tree< TTreeTraits, TAllocator > &  )
delete

Member Function Documentation

◆ begin()

template<class TTreeTraits , class TAllocator >
const node_type* mn::container::base_rb_tree< TTreeTraits, TAllocator >::begin ( )
inline

◆ clear()

template<class TTreeTraits , class TAllocator >
void mn::container::base_rb_tree< TTreeTraits, TAllocator >::clear ( )
inline

◆ construct_node()

template<class TTreeTraits , class TAllocator >
node_type* mn::container::base_rb_tree< TTreeTraits, TAllocator >::construct_node ( )
inlineprivate

◆ destruct_node()

template<class TTreeTraits , class TAllocator >
void mn::container::base_rb_tree< TTreeTraits, TAllocator >::destruct_node ( node_type *  n)
inlineprivate

◆ empty()

template<class TTreeTraits , class TAllocator >
bool mn::container::base_rb_tree< TTreeTraits, TAllocator >::empty ( ) const
inline

◆ erase() [1/2]

template<class TTreeTraits , class TAllocator >
size_type mn::container::base_rb_tree< TTreeTraits, TAllocator >::erase ( const key_type &  key)
inline

◆ erase() [2/2]

template<class TTreeTraits , class TAllocator >
void mn::container::base_rb_tree< TTreeTraits, TAllocator >::erase ( node_type *  n)
inline

◆ find_next()

template<class TTreeTraits , class TAllocator >
const node_type* mn::container::base_rb_tree< TTreeTraits, TAllocator >::find_next ( node_type *  n) const
inline

◆ find_node()

template<class TTreeTraits , class TAllocator >
node_type* mn::container::base_rb_tree< TTreeTraits, TAllocator >::find_node ( const key_type &  key)
inline

◆ free_node()

template<class TTreeTraits , class TAllocator >
void mn::container::base_rb_tree< TTreeTraits, TAllocator >::free_node ( node_type *  n,
bool  recursive 
)
inline

◆ insert()

template<class TTreeTraits , class TAllocator >
node_type* mn::container::base_rb_tree< TTreeTraits, TAllocator >::insert ( const value_type &  v)
inline

◆ operator=()

template<class TTreeTraits , class TAllocator >
base_rb_tree& mn::container::base_rb_tree< TTreeTraits, TAllocator >::operator= ( const base_rb_tree< TTreeTraits, TAllocator > &  )
delete

◆ rebalance()

template<class TTreeTraits , class TAllocator >
void mn::container::base_rb_tree< TTreeTraits, TAllocator >::rebalance ( node_type *  new_node)
inlineprotected

◆ rebalance_after_erase()

template<class TTreeTraits , class TAllocator >
void mn::container::base_rb_tree< TTreeTraits, TAllocator >::rebalance_after_erase ( node_type *  n)
inlineprotected

◆ rotate_left()

template<class TTreeTraits , class TAllocator >
void mn::container::base_rb_tree< TTreeTraits, TAllocator >::rotate_left ( node_type *  n)
inline

◆ rotate_right()

template<class TTreeTraits , class TAllocator >
void mn::container::base_rb_tree< TTreeTraits, TAllocator >::rotate_right ( node_type *  n)
inline

◆ size() [1/2]

template<class TTreeTraits , class TAllocator >
size_type mn::container::base_rb_tree< TTreeTraits, TAllocator >::size ( ) const
inline

◆ size() [2/2]

template<class TTreeTraits , class TAllocator >
size_type mn::container::base_rb_tree< TTreeTraits, TAllocator >::size ( const node_type *  n)
inline

◆ swap()

template<class TTreeTraits , class TAllocator >
void mn::container::base_rb_tree< TTreeTraits, TAllocator >::swap ( base_rb_tree< TTreeTraits, TAllocator > &  other)
inline

◆ traverse()

template<class TTreeTraits , class TAllocator >
void mn::container::base_rb_tree< TTreeTraits, TAllocator >::traverse ( TravFunc  func)
inline

◆ traverse_node()

template<class TTreeTraits , class TAllocator >
void mn::container::base_rb_tree< TTreeTraits, TAllocator >::traverse_node ( node_type *  n,
TravFunc  func,
int  depth 
)
inline

◆ validate() [1/2]

template<class TTreeTraits , class TAllocator >
void mn::container::base_rb_tree< TTreeTraits, TAllocator >::validate ( )
inline

◆ validate() [2/2]

template<class TTreeTraits , class TAllocator >
void mn::container::base_rb_tree< TTreeTraits, TAllocator >::validate ( node_type *  n)
inline

Member Data Documentation

◆ m_allocator

template<class TTreeTraits , class TAllocator >
allocator_type mn::container::base_rb_tree< TTreeTraits, TAllocator >::m_allocator
private

◆ m_root

template<class TTreeTraits , class TAllocator >
node_type* mn::container::base_rb_tree< TTreeTraits, TAllocator >::m_root
private

◆ m_size

template<class TTreeTraits , class TAllocator >
size_type mn::container::base_rb_tree< TTreeTraits, TAllocator >::m_size
private

◆ ms_sentinel

template<class TTreeTraits , class TAllocator >
node_type mn::container::base_rb_tree< TTreeTraits, TAllocator >::ms_sentinel
staticprivate

◆ NodeSize

template<class TTreeTraits , class TAllocator >
const size_type mn::container::base_rb_tree< TTreeTraits, TAllocator >::NodeSize = sizeof(node_type)
static
The documentation for this class was generated from the following file: