The Red-Black Tree. More...

#include <rbtree.hpp>

Inheritance diagram for ygg::RBTree< Node, NodeTraits, Options, Tag, Compare >:

Public Types
using	MyClass = RBTree< Node, NodeTraits, Options, Tag, Compare >

using	NB = RBTreeNodeBase< Node, Options, Tag >

using	TB = bst::BinarySearchTree< Node, Options, Tag, Compare, rbtree_internal::ColorParentStorage< Node, Options::compress_color > >

template<bool reverse>
using	iterator = typename TB::template iterator< reverse >

template<bool reverse>
using	const_iterator = typename TB::template const_iterator< reverse >

Public Member Functions
	RBTree () noexcept
	Create a new empty red-black tree.

	RBTree (MyClass &&other) noexcept
	Create a new red-black tree from a different red-black tree. More...

void	insert (Node &node) CMP_NOEXCEPT(node)
	Inserts <node> into the tree. More...

void	insert (Node &node, Node &hint) CMP_NOEXCEPT(node)

void	insert (Node &node, iterator< false > hint) CMP_NOEXCEPT(node)

void	remove (Node &node) CMP_NOEXCEPT(node)
	Removes <node> from the tree. More...

template<class Comparable >
utilities::select_type_t< size_t, Node *, Options::stl_erase >	erase (const Comparable &c) CMP_NOEXCEPT(c)
	Deletes a node that compares equally to `from the tree.` More...

template<bool reverse>
utilities::select_type_t< const iterator< reverse >, Node *, Options::stl_erase >	erase (const iterator< reverse > &it) CMP_NOEXCEPT(*it)
	Deletes a node by iterator. More...

const_iterator< false >	find (const Comparable &query) const CMP_NOEXCEPT(query)
	Finds an element in the tree. More...

iterator< false >	find (const Comparable &query) CMP_NOEXCEPT(query)

iterator< false >	find (const Comparable &query, Callbacks *cbs)

const_iterator< false >	upper_bound (const Comparable &query) const CMP_NOEXCEPT(query)
	Upper-bounds an element. More...

iterator< false >	upper_bound (const Comparable &query) CMP_NOEXCEPT(query)

const_iterator< false >	lower_bound (const Comparable &query) const CMP_NOEXCEPT(query)
	Lower-bounds an element. More...

iterator< false >	lower_bound (const Comparable &query) CMP_NOEXCEPT(query)

void	dump_to_dot (const std::string &filename) const
	Debugging Method: Draw the Tree as a .dot file. More...

const_iterator< false >	cbegin () const noexcept

const_iterator< false >	cend () const noexcept

const_iterator< false >	begin () const noexcept

iterator< false >	begin () noexcept

const_iterator< false >	end () const noexcept

iterator< false >	end () noexcept

const_iterator< true >	crbegin () const noexcept

const_iterator< true >	crend () const noexcept

const_iterator< true >	rbegin () const noexcept

iterator< true >	rbegin () noexcept

const_iterator< true >	rend () const noexcept

iterator< true >	rend () noexcept

const_iterator< false >	iterator_to (const Node &node) const noexcept

iterator< false >	iterator_to (Node &node) noexcept

size_t	size () const noexcept

void	clear () noexcept
	Removes all elements from the tree. More...

bool	empty () const noexcept
	Returns whether the tree is empty. More...

Node *	get_root () const noexcept

Static Public Member Functions
static Node *	get_parent (Node *n) noexcept

static Node *	get_left_child (Node *n) noexcept

static Node *	get_right_child (Node *n) noexcept

Protected Types
using	Path = std::vector< Node * >

Protected Member Functions
void	remove_to_leaf (Node &node) CMP_NOEXCEPT(node)

void	fixup_after_delete (Node *parent, bool deleted_left) noexcept

void	insert_leaf_base (Node &node, Node *start) CMP_NOEXCEPT(node)

void	fixup_after_insert (Node *node) noexcept

void	rotate_left (Node *parent) noexcept

void	rotate_right (Node *parent) noexcept

void	swap_nodes (Node n1, Node n2, bool swap_colors=true) noexcept

void	replace_node (Node to_be_replaced, Node replace_with) noexcept

void	swap_unrelated_nodes (Node n1, Node n2) noexcept

void	swap_neighbors (Node parent, Node child) noexcept

void	verify_black_root () const

void	verify_black_paths (const Node node, unsigned int path_length) const

void	verify_red_black (const Node *node) const

Node *	get_first_equal (Node *n) noexcept

Node *	get_smallest () const noexcept

Node *	get_largest () const noexcept

Node *	get_uncle (Node *node) const noexcept

void	dump_to_dot_base (const std::string &filename, NodeNameGetter name_getter) const

void	output_node_base (const Node *node, std::ofstream &out, NodeNameGetter name_getter) const

Protected Attributes
Node *	root

Compare	cmp

SizeHolder< Options::constant_time_size >	s

Detailed Description

template<class Node, class NodeTraits, class Options = DefaultOptions, class Tag = int, class Compare = ygg::utilities::flexible_less>
class ygg::RBTree< Node, NodeTraits, Options, Tag, Compare >

The Red-Black Tree.

This is the main Red-Black Tree class.

Template Parameters

Node	The node class for this tree. It must be derived from RBTreeNodeBase.
NodeTraits	A class implementing various hooks and functions on your node class. See DOCTODO for details.
Options	The TreeOptions class specifying the parameters of this RBTree. See the TreeOptions and TreeFlags classes for details.
Tag	An class tag that identifies this tree. Can be used to insert the same nodes into multiple trees. See DOCTODO for details. Can be any class, the class can be empty.
Compare	A compare class. The Red-Black Tree follows STL semantics for 'Compare'. Defaults to ygg::utilities::flexible_less. Implement operator<(const Node & lhs, const Node & rhs) if you want to use it.

Constructor & Destructor Documentation

◆ RBTree()

template<class Node, class NodeTraits, class Options = DefaultOptions, class Tag = int, class Compare = ygg::utilities::flexible_less>

ygg::RBTree< Node, NodeTraits, Options, Tag, Compare >::RBTree ( MyClass && other )

noexcept

Create a new red-black tree from a different red-black tree.

The other red-black tree is moved into this one, i.e., using it afterwards is undefined behavior.

Parameters

other The red-black tree that this one is constructed from

Member Function Documentation

◆ begin()

const_iterator<false> ygg::bst::BinarySearchTree< Node, Options, Tag, Compare, rbtree_internal::ColorParentStorage< Node, Options::compress_color > >::begin ( ) const

noexceptinherited

Returns an iterator pointing to the smallest element in the tree.

◆ cbegin()

const_iterator<false> ygg::bst::BinarySearchTree< Node, Options, Tag, Compare, rbtree_internal::ColorParentStorage< Node, Options::compress_color > >::cbegin ( ) const

noexceptinherited

Returns an iterator pointing to the smallest element in the tree.

◆ cend()

const_iterator<false> ygg::bst::BinarySearchTree< Node, Options, Tag, Compare, rbtree_internal::ColorParentStorage< Node, Options::compress_color > >::cend ( ) const

noexceptinherited

Returns an iterator pointing after the largest element in the tree.

◆ clear()

void ygg::bst::BinarySearchTree< Node, Options, Tag, Compare, rbtree_internal::ColorParentStorage< Node, Options::compress_color > >::clear ( )

noexceptinherited

Removes all elements from the tree.

◆ crbegin()

const_iterator<true> ygg::bst::BinarySearchTree< Node, Options, Tag, Compare, rbtree_internal::ColorParentStorage< Node, Options::compress_color > >::crbegin ( ) const

noexceptinherited

Returns an reverse iterator pointing to the largest element in the tree.

◆ crend()

const_iterator<true> ygg::bst::BinarySearchTree< Node, Options, Tag, Compare, rbtree_internal::ColorParentStorage< Node, Options::compress_color > >::crend ( ) const

noexceptinherited

Returns an reverse iterator pointing before the smallest element in the tree.

◆ dump_to_dot()

void ygg::bst::BinarySearchTree< Node, Options, Tag, Compare, rbtree_internal::ColorParentStorage< Node, Options::compress_color > >::dump_to_dot ( const std::string & filename ) const

inherited

Debugging Method: Draw the Tree as a .dot file.

Outputs the current tree as a .dot file which can be drawn using graphviz.

Parameters

filename The file path where to write the .dot file.

◆ empty()

bool ygg::bst::BinarySearchTree< Node, Options, Tag, Compare, rbtree_internal::ColorParentStorage< Node, Options::compress_color > >::empty ( ) const

noexceptinherited

Returns whether the tree is empty.

This method runs in O(1).

Returns: true if the tree is empty, false otherwise

◆ end()

const_iterator<false> ygg::bst::BinarySearchTree< Node, Options, Tag, Compare, rbtree_internal::ColorParentStorage< Node, Options::compress_color > >::end ( ) const

noexceptinherited

Returns an iterator pointing after the largest element in the tree.

◆ erase() [1/2]

template<class Node, class NodeTraits, class Options = DefaultOptions, class Tag = int, class Compare = ygg::utilities::flexible_less>

template<class Comparable >

utilities::select_type_t<size_t, Node *, Options::stl_erase> ygg::RBTree< Node, NodeTraits, Options, Tag, Compare >::erase ( const Comparable & c )

Deletes a node that compares equally to from the tree.

Warning: The behavior of this method strongly depends on whether the STL_ERASE option is set or not!

Removes a node that compares equally to from the tree.

If STL_ERASE is set, this method removes all nodes that compare equally to c from the tree and returns the number of nodes removed.

If STL_ERASE is not set, it removes only one node and returns a pointer to the removed node.

Parameters


  
    c Anything comparable to a node. A node (resp. all nodes, see above) that compares equally will be removed


Returns
If STL_ERASE is unset: A pointer to the node that has been removed, or nullptr if no node was removed. If STL_ERASE is set: The number of erased nodes.

◆ erase() [2/2]

template<class Node, class NodeTraits, class Options = DefaultOptions, class Tag = int, class Compare = ygg::utilities::flexible_less>

template<bool reverse>

utilities::select_type_t<const iterator<reverse>, Node *, Options::stl_erase> ygg::RBTree< Node, NodeTraits, Options, Tag, Compare >::erase ( const iterator< reverse > & it )

Deletes a node by iterator.

Warning: The return type of this method depends on whether the STL_ERASE option is set or not!

Removes a node that is pointed to by an iterator.

Parameters

c	Anything comparable to a node. A node (resp. all nodes, see above) that compares equally will be removed

Returns: If STL_ERASE is unset: A pointer to the node that has been removed. If STL_ERASE is set: An iterator to the node after the removed node (or end()).

◆ find()

const_iterator<false> ygg::bst::BinarySearchTree< Node, Options, Tag, Compare, rbtree_internal::ColorParentStorage< Node, Options::compress_color > >::find ( const Comparable & query ) const

inherited

Finds an element in the tree.

Returns an iterator to the first element that compares equally to <query>. Note that <query> does not have to be a Node, but can be anything that can be compared to a Node, i.e., for which Compare()(const Node &, const Comparable &) and Compare()(const Comparable &, const Node &) are defined and implemented. In the case of using the default ygg::utilities::flexible_less as Compare, that means you have to implement operator<() for both types.

Warning: Not available for explicitly ordered trees

Parameters

query An object comparing equally to the element that should be found.

Returns: An iterator to the first element comparing equally to <query>, or end() if no such element exists

◆ insert()

template<class Node, class NodeTraits, class Options = DefaultOptions, class Tag = int, class Compare = ygg::utilities::flexible_less>

void ygg::RBTree< Node, NodeTraits, Options, Tag, Compare >::insert ( Node & node )

Inserts <node> into the tree.

Warning: Please note that after calling insert() on a node (and before removing that node again), that node may not move in memory. A common pitfall is to store nodes in a std::vector (or other STL container), which reallocates (and thereby moves objecs around).

Warning: Not available for explicitly ordered trees

Parameters

Node	The node to be inserted.

◆ iterator_to()

const_iterator<false> ygg::bst::BinarySearchTree< Node, Options, Tag, Compare, rbtree_internal::ColorParentStorage< Node, Options::compress_color > >::iterator_to ( const Node & node ) const

noexceptinherited

Returns an iterator pointing to the entry held in node.

Parameters

node	The node the iterator should point to.

◆ lower_bound()

const_iterator<false> ygg::bst::BinarySearchTree< Node, Options, Tag, Compare, rbtree_internal::ColorParentStorage< Node, Options::compress_color > >::lower_bound ( const Comparable & query ) const

inherited

Lower-bounds an element.

Returns an iterator to the first element that is not less that <query>, i.e., that does not have to go before <query>.

Note that <query> does not have to be a Node, but can be anything that can be compared to a Node, i.e., for which Compare()(const Node &, const Comparable &) and Compare()(const Comparable &, const Node &) are defined and implemented. In the case of using the default ygg::utilities::flexible_less as Compare, that means you have to implement operator<() for both types.

Warning: Not available for explicitly ordered trees

Parameters

query An object comparable to Node that should be lower-bounded

Returns: An iterator to the first element comparing greater-or-equally to <query>, or end() if no such element exists

◆ rbegin()

const_iterator<true> ygg::bst::BinarySearchTree< Node, Options, Tag, Compare, rbtree_internal::ColorParentStorage< Node, Options::compress_color > >::rbegin ( ) const

noexceptinherited

Returns an reverse iterator pointing to the largest element in the tree.

◆ remove()

template<class Node, class NodeTraits, class Options = DefaultOptions, class Tag = int, class Compare = ygg::utilities::flexible_less>

void ygg::RBTree< Node, NodeTraits, Options, Tag, Compare >::remove ( Node & node )

Removes <node> from the tree.

Parameters

Node	The node to be removed.

◆ rend()

const_iterator<true> ygg::bst::BinarySearchTree< Node, Options, Tag, Compare, rbtree_internal::ColorParentStorage< Node, Options::compress_color > >::rend ( ) const

noexceptinherited

Returns an reverse iterator pointing before the smallest element in the tree.

◆ size()

size_t ygg::bst::BinarySearchTree< Node, Options, Tag, Compare, rbtree_internal::ColorParentStorage< Node, Options::compress_color > >::size ( ) const

noexceptinherited

Return the number of elements in the tree.

This method runs in O(1).

Warning: This method is only available if CONSTANT_TIME_SIZE is set as option!

Returns: The number of elements in the tree.

◆ upper_bound()

const_iterator<false> ygg::bst::BinarySearchTree< Node, Options, Tag, Compare, rbtree_internal::ColorParentStorage< Node, Options::compress_color > >::upper_bound ( const Comparable & query ) const

inherited

Upper-bounds an element.

Returns an iterator to the smallest element to which <query> compares as "less", i.e. the smallest element that is considered go strictly after <query>.

Note that <query> does not have to be a Node, but can be anything that can be compared to a Node, i.e., for which Compare()(const Node &, const Comparable &) and Compare()(const Comparable &, const Node &) are defined and implemented. In the case of using the default ygg::utilities::flexible_less as Compare, that means you have to implement operator<() for both types.

Warning: Not available for explicitly ordered trees

Parameters

query An object comparable to Node that should be upper-bounded

Returns: An iterator to the first element comparing "greater" to <query>, or end() if no such element exists

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

/home/lukas/src/intervaltree/ygg/src/rbtree.hpp

Public Types

Public Member Functions

Static Public Member Functions

Protected Types

Protected Member Functions

Protected Attributes

Detailed Description

template<class Node, class NodeTraits, class Options = DefaultOptions, class Tag = int, class Compare = ygg::utilities::flexible_less> class ygg::RBTree< Node, NodeTraits, Options, Tag, Compare >

Constructor & Destructor Documentation

◆ RBTree()

Member Function Documentation

◆ begin()

◆ cbegin()

◆ cend()

◆ clear()

◆ crbegin()

◆ crend()

◆ dump_to_dot()

◆ empty()

◆ end()

◆ erase() [1/2]

◆ erase() [2/2]

◆ find()

◆ insert()

◆ iterator_to()

◆ lower_bound()

◆ rbegin()

◆ remove()

◆ rend()

◆ size()

◆ upper_bound()

template<class Node, class NodeTraits, class Options = DefaultOptions, class Tag = int, class Compare = ygg::utilities::flexible_less>
class ygg::RBTree< Node, NodeTraits, Options, Tag, Compare >