Iros
 
Loading...
Searching...
No Matches
Classes | Public Member Functions | Protected Member Functions | Protected Attributes | Friends | List of all members
di::container::RBTree< Value, Comp, Tag, Interface, is_multi, Self > Class Template Reference

General implementation of the Red-Black self-balancing binary tree. More...

#include <di/container/tree/rb_tree.h>

Inheritance diagram for di::container::RBTree< Value, Comp, Tag, Interface, is_multi, Self >:
[legend]

Classes

struct  InsertPosition
 

Public Member Functions

 RBTree ()=default
 
 RBTree (RBTree const &)=delete
 
auto operator= (RBTree const &) -> RBTree &=delete
 
constexpr RBTree (Comp comparator)
 
constexpr RBTree (RBTree &&other)
 
constexpr auto operator= (RBTree &&other) -> RBTree &
 
constexpr ~RBTree ()
 
constexpr auto size () const -> usize
 
constexpr auto empty () const -> bool
 
constexpr auto begin () -> Iterator
 
constexpr auto begin () const -> ConstIterator
 
constexpr auto end () -> Iterator
 
constexpr auto end () const -> ConstIterator
 
constexpr auto unconst_iterator (ConstIterator it) -> Iterator
 
constexpr auto insert_node (Node &node)
 
constexpr auto insert_node (ConstIterator, Node &node)
 
constexpr auto erase_impl (ConstIterator position) -> Iterator
 
template<typename U>
requires (concepts::StrictWeakOrder<Comp&, Value, U>)
constexpr auto equal_range_impl (U &&needle) const
 
template<typename U>
requires (concepts::StrictWeakOrder<Comp&, Value, U>)
constexpr auto lower_bound_impl (U &&needle) const -> ConstIterator
 
template<typename U>
requires (concepts::StrictWeakOrder<Comp&, Value, U>)
constexpr auto upper_bound_impl (U &&needle) const -> ConstIterator
 
template<typename U>
requires (concepts::StrictWeakOrder<Comp&, Value, U>)
constexpr auto find_impl (U &&needle) const -> ConstIterator
 
constexpr void merge_impl (RBTree &&other)
 

Protected Member Functions

constexpr auto node_value (Node &node) const -> Value &
 
constexpr auto node_value (Node const &node) const -> Value const &
 
constexpr auto node_color (Node *node) const -> Node::Color
 
constexpr void rotate_left (Node &x)
 
constexpr void rotate_right (Node &y)
 
template<typename U>
requires (concepts::StrictWeakOrder<Comp&, Value, U>)
constexpr auto insert_position (U &&needle) const -> InsertPosition
 
constexpr void insert_node (InsertPosition position, Node &to_insert)
 
constexpr void do_insert_node (InsertPosition position, Node &to_insert)
 
constexpr void do_insert_rebalancing (Node *node)
 
constexpr void transplant (Node &u, Node *v)
 
constexpr void erase_node (Node &to_delete)
 
constexpr void do_erase_rebalancing (Node *x)
 
constexpr auto compare (Node const &a, Node const &b) const
 
template<typename T, typename U>
requires (concepts::StrictWeakOrder<Comp&, T, U>)
constexpr auto compare (T const &a, U &&b) const
 

Protected Attributes

Node * m_root { nullptr }
 
Node * m_minimum { nullptr }
 
Node * m_maximum { nullptr }
 
usize m_size { 0 }
 
Comp m_comparator
 

Friends

constexpr friend auto operator== (ConcreteSelf const &a, ConcreteSelf const &b) -> bool requires(concepts::EqualityComparable< Value >)
 
constexpr friend auto operator<=> (ConcreteSelf const &a, ConcreteSelf const &b)
 

Detailed Description

template<typename Value, typename Comp, typename Tag, typename Interface, bool is_multi, typename Self = Void>
class di::container::RBTree< Value, Comp, Tag, Interface, is_multi, Self >

General implementation of the Red-Black self-balancing binary tree.

The book Introduction to Algorithms, Third Edition (by Thomas H. Cormen, et al.) was heavily referenced in this class's implementation of a Red-Black tree. See here.

Constructor & Destructor Documentation

◆ RBTree() [1/4]

template<typename Value, typename Comp, typename Tag, typename Interface, bool is_multi, typename Self = Void>
di::container::RBTree< Value, Comp, Tag, Interface, is_multi, Self >::RBTree ( )
default

◆ RBTree() [2/4]

template<typename Value, typename Comp, typename Tag, typename Interface, bool is_multi, typename Self = Void>
di::container::RBTree< Value, Comp, Tag, Interface, is_multi, Self >::RBTree ( RBTree< Value, Comp, Tag, Interface, is_multi, Self > const & )
delete

◆ RBTree() [3/4]

template<typename Value, typename Comp, typename Tag, typename Interface, bool is_multi, typename Self = Void>
di::container::RBTree< Value, Comp, Tag, Interface, is_multi, Self >::RBTree ( Comp comparator)
inlineexplicitconstexpr

◆ RBTree() [4/4]

template<typename Value, typename Comp, typename Tag, typename Interface, bool is_multi, typename Self = Void>
di::container::RBTree< Value, Comp, Tag, Interface, is_multi, Self >::RBTree ( RBTree< Value, Comp, Tag, Interface, is_multi, Self > && other)
inlineconstexpr

◆ ~RBTree()

template<typename Value, typename Comp, typename Tag, typename Interface, bool is_multi, typename Self = Void>
di::container::RBTree< Value, Comp, Tag, Interface, is_multi, Self >::~RBTree ( )
inlineconstexpr

Member Function Documentation

◆ begin() [1/2]

template<typename Value, typename Comp, typename Tag, typename Interface, bool is_multi, typename Self = Void>
auto di::container::RBTree< Value, Comp, Tag, Interface, is_multi, Self >::begin ( ) -> Iterator
inlineconstexpr

◆ begin() [2/2]

template<typename Value, typename Comp, typename Tag, typename Interface, bool is_multi, typename Self = Void>
auto di::container::RBTree< Value, Comp, Tag, Interface, is_multi, Self >::begin ( ) const -> ConstIterator
inlineconstexpr

◆ compare() [1/2]

template<typename Value, typename Comp, typename Tag, typename Interface, bool is_multi, typename Self = Void>
auto di::container::RBTree< Value, Comp, Tag, Interface, is_multi, Self >::compare ( Node const & a,
Node const & b ) const
inlineconstexprprotected

◆ compare() [2/2]

template<typename Value, typename Comp, typename Tag, typename Interface, bool is_multi, typename Self = Void>
template<typename T, typename U>
requires (concepts::StrictWeakOrder<Comp&, T, U>)
auto di::container::RBTree< Value, Comp, Tag, Interface, is_multi, Self >::compare ( T const & a,
U && b ) const
inlineconstexprprotected

◆ do_erase_rebalancing()

template<typename Value, typename Comp, typename Tag, typename Interface, bool is_multi, typename Self = Void>
void di::container::RBTree< Value, Comp, Tag, Interface, is_multi, Self >::do_erase_rebalancing ( Node * x)
inlineconstexprprotected

◆ do_insert_node()

template<typename Value, typename Comp, typename Tag, typename Interface, bool is_multi, typename Self = Void>
void di::container::RBTree< Value, Comp, Tag, Interface, is_multi, Self >::do_insert_node ( InsertPosition position,
Node & to_insert )
inlineconstexprprotected

◆ do_insert_rebalancing()

template<typename Value, typename Comp, typename Tag, typename Interface, bool is_multi, typename Self = Void>
void di::container::RBTree< Value, Comp, Tag, Interface, is_multi, Self >::do_insert_rebalancing ( Node * node)
inlineconstexprprotected

◆ empty()

template<typename Value, typename Comp, typename Tag, typename Interface, bool is_multi, typename Self = Void>
auto di::container::RBTree< Value, Comp, Tag, Interface, is_multi, Self >::empty ( ) const -> bool
inlineconstexpr

◆ end() [1/2]

template<typename Value, typename Comp, typename Tag, typename Interface, bool is_multi, typename Self = Void>
auto di::container::RBTree< Value, Comp, Tag, Interface, is_multi, Self >::end ( ) -> Iterator
inlineconstexpr

◆ end() [2/2]

template<typename Value, typename Comp, typename Tag, typename Interface, bool is_multi, typename Self = Void>
auto di::container::RBTree< Value, Comp, Tag, Interface, is_multi, Self >::end ( ) const -> ConstIterator
inlineconstexpr

◆ equal_range_impl()

template<typename Value, typename Comp, typename Tag, typename Interface, bool is_multi, typename Self = Void>
template<typename U>
requires (concepts::StrictWeakOrder<Comp&, Value, U>)
auto di::container::RBTree< Value, Comp, Tag, Interface, is_multi, Self >::equal_range_impl ( U && needle) const
inlineconstexpr

◆ erase_impl()

template<typename Value, typename Comp, typename Tag, typename Interface, bool is_multi, typename Self = Void>
auto di::container::RBTree< Value, Comp, Tag, Interface, is_multi, Self >::erase_impl ( ConstIterator position) -> Iterator
inlineconstexpr

◆ erase_node()

template<typename Value, typename Comp, typename Tag, typename Interface, bool is_multi, typename Self = Void>
void di::container::RBTree< Value, Comp, Tag, Interface, is_multi, Self >::erase_node ( Node & to_delete)
inlineconstexprprotected

◆ find_impl()

template<typename Value, typename Comp, typename Tag, typename Interface, bool is_multi, typename Self = Void>
template<typename U>
requires (concepts::StrictWeakOrder<Comp&, Value, U>)
auto di::container::RBTree< Value, Comp, Tag, Interface, is_multi, Self >::find_impl ( U && needle) const -> ConstIterator
inlineconstexpr

◆ insert_node() [1/3]

template<typename Value, typename Comp, typename Tag, typename Interface, bool is_multi, typename Self = Void>
auto di::container::RBTree< Value, Comp, Tag, Interface, is_multi, Self >::insert_node ( ConstIterator ,
Node & node )
inlineconstexpr

◆ insert_node() [2/3]

template<typename Value, typename Comp, typename Tag, typename Interface, bool is_multi, typename Self = Void>
void di::container::RBTree< Value, Comp, Tag, Interface, is_multi, Self >::insert_node ( InsertPosition position,
Node & to_insert )
inlineconstexprprotected

◆ insert_node() [3/3]

template<typename Value, typename Comp, typename Tag, typename Interface, bool is_multi, typename Self = Void>
auto di::container::RBTree< Value, Comp, Tag, Interface, is_multi, Self >::insert_node ( Node & node)
inlineconstexpr

◆ insert_position()

template<typename Value, typename Comp, typename Tag, typename Interface, bool is_multi, typename Self = Void>
template<typename U>
requires (concepts::StrictWeakOrder<Comp&, Value, U>)
auto di::container::RBTree< Value, Comp, Tag, Interface, is_multi, Self >::insert_position ( U && needle) const -> InsertPosition
inlineconstexprprotected

◆ lower_bound_impl()

template<typename Value, typename Comp, typename Tag, typename Interface, bool is_multi, typename Self = Void>
template<typename U>
requires (concepts::StrictWeakOrder<Comp&, Value, U>)
auto di::container::RBTree< Value, Comp, Tag, Interface, is_multi, Self >::lower_bound_impl ( U && needle) const -> ConstIterator
inlineconstexpr

◆ merge_impl()

template<typename Value, typename Comp, typename Tag, typename Interface, bool is_multi, typename Self = Void>
void di::container::RBTree< Value, Comp, Tag, Interface, is_multi, Self >::merge_impl ( RBTree< Value, Comp, Tag, Interface, is_multi, Self > && other)
inlineconstexpr

◆ node_color()

template<typename Value, typename Comp, typename Tag, typename Interface, bool is_multi, typename Self = Void>
auto di::container::RBTree< Value, Comp, Tag, Interface, is_multi, Self >::node_color ( Node * node) const -> Node::Color
inlineconstexprprotected

◆ node_value() [1/2]

template<typename Value, typename Comp, typename Tag, typename Interface, bool is_multi, typename Self = Void>
auto di::container::RBTree< Value, Comp, Tag, Interface, is_multi, Self >::node_value ( Node & node) const -> Value&
inlineconstexprprotected

◆ node_value() [2/2]

template<typename Value, typename Comp, typename Tag, typename Interface, bool is_multi, typename Self = Void>
auto di::container::RBTree< Value, Comp, Tag, Interface, is_multi, Self >::node_value ( Node const & node) const -> Value const&
inlineconstexprprotected

◆ operator=() [1/2]

template<typename Value, typename Comp, typename Tag, typename Interface, bool is_multi, typename Self = Void>
auto di::container::RBTree< Value, Comp, Tag, Interface, is_multi, Self >::operator= ( RBTree< Value, Comp, Tag, Interface, is_multi, Self > && other) -> RBTree&
inlineconstexpr

◆ operator=() [2/2]

template<typename Value, typename Comp, typename Tag, typename Interface, bool is_multi, typename Self = Void>
auto di::container::RBTree< Value, Comp, Tag, Interface, is_multi, Self >::operator= ( RBTree< Value, Comp, Tag, Interface, is_multi, Self > const & ) -> RBTree &=delete
delete

◆ rotate_left()

template<typename Value, typename Comp, typename Tag, typename Interface, bool is_multi, typename Self = Void>
void di::container::RBTree< Value, Comp, Tag, Interface, is_multi, Self >::rotate_left ( Node & x)
inlineconstexprprotected

◆ rotate_right()

template<typename Value, typename Comp, typename Tag, typename Interface, bool is_multi, typename Self = Void>
void di::container::RBTree< Value, Comp, Tag, Interface, is_multi, Self >::rotate_right ( Node & y)
inlineconstexprprotected

◆ size()

template<typename Value, typename Comp, typename Tag, typename Interface, bool is_multi, typename Self = Void>
auto di::container::RBTree< Value, Comp, Tag, Interface, is_multi, Self >::size ( ) const -> usize
inlineconstexpr

◆ transplant()

template<typename Value, typename Comp, typename Tag, typename Interface, bool is_multi, typename Self = Void>
void di::container::RBTree< Value, Comp, Tag, Interface, is_multi, Self >::transplant ( Node & u,
Node * v )
inlineconstexprprotected

◆ unconst_iterator()

template<typename Value, typename Comp, typename Tag, typename Interface, bool is_multi, typename Self = Void>
auto di::container::RBTree< Value, Comp, Tag, Interface, is_multi, Self >::unconst_iterator ( ConstIterator it) -> Iterator
inlineconstexpr

◆ upper_bound_impl()

template<typename Value, typename Comp, typename Tag, typename Interface, bool is_multi, typename Self = Void>
template<typename U>
requires (concepts::StrictWeakOrder<Comp&, Value, U>)
auto di::container::RBTree< Value, Comp, Tag, Interface, is_multi, Self >::upper_bound_impl ( U && needle) const -> ConstIterator
inlineconstexpr

Friends And Related Symbol Documentation

◆ operator<=>

template<typename Value, typename Comp, typename Tag, typename Interface, bool is_multi, typename Self = Void>
friend auto operator<=> ( ConcreteSelf const & a,
ConcreteSelf const & b )
friend

◆ operator==

template<typename Value, typename Comp, typename Tag, typename Interface, bool is_multi, typename Self = Void>
friend auto operator== ( ConcreteSelf const & a,
ConcreteSelf const & b ) -> bool requires(concepts::EqualityComparable<Value>)
friend

Member Data Documentation

◆ m_comparator

template<typename Value, typename Comp, typename Tag, typename Interface, bool is_multi, typename Self = Void>
Comp di::container::RBTree< Value, Comp, Tag, Interface, is_multi, Self >::m_comparator
protected

◆ m_maximum

template<typename Value, typename Comp, typename Tag, typename Interface, bool is_multi, typename Self = Void>
Node* di::container::RBTree< Value, Comp, Tag, Interface, is_multi, Self >::m_maximum { nullptr }
protected

◆ m_minimum

template<typename Value, typename Comp, typename Tag, typename Interface, bool is_multi, typename Self = Void>
Node* di::container::RBTree< Value, Comp, Tag, Interface, is_multi, Self >::m_minimum { nullptr }
protected

◆ m_root

template<typename Value, typename Comp, typename Tag, typename Interface, bool is_multi, typename Self = Void>
Node* di::container::RBTree< Value, Comp, Tag, Interface, is_multi, Self >::m_root { nullptr }
protected

◆ m_size

template<typename Value, typename Comp, typename Tag, typename Interface, bool is_multi, typename Self = Void>
usize di::container::RBTree< Value, Comp, Tag, Interface, is_multi, Self >::m_size { 0 }
protected
The documentation for this class was generated from the following file: