ygg::bst::BinarySearchTree< Node, Options, Tag, Compare, ParentContainer > Class Template Reference

Classes
class	const_iterator
class	iterator

Public Types
using	MyClass = BinarySearchTree< Node, Options, Tag, Compare, ParentContainer >
using	NB = BSTNodeBase< Node, Tag, ParentContainer >

Public Member Functions
	BinarySearchTree () noexcept
	Create a new empty red-black tree.
	BinarySearchTree (MyClass &&other) noexcept
	Create a new red-black tree from a different red-black tree. More...
MyClass &	operator= (MyClass &&other) noexcept
	Move-assign an other red-black tree to this one. More...
template<class Comparable , bool ensure_first = false>
const_iterator< false >	find (const Comparable &query) const CMP_NOEXCEPT(query)
	Finds an element in the tree. More...
template<class Comparable , bool ensure_first = false>
iterator< false >	find (const Comparable &query) CMP_NOEXCEPT(query)
template<class Comparable , class Callbacks = DefaultFindCallbacks<Node>>
iterator< false >	find (const Comparable &query, Callbacks *cbs)
template<class Comparable >
const_iterator< false >	upper_bound (const Comparable &query) const CMP_NOEXCEPT(query)
	Upper-bounds an element. More...
template<class Comparable >
iterator< false >	upper_bound (const Comparable &query) CMP_NOEXCEPT(query)
template<class Comparable >
const_iterator< false >	lower_bound (const Comparable &query) const CMP_NOEXCEPT(query)
	Lower-bounds an element. More...
template<class Comparable >
iterator< false >	lower_bound (const Comparable &query) CMP_NOEXCEPT(query)
template<class NodeTraits >
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 Member Functions
Node *	get_first_equal (Node *n) noexcept
Node *	get_smallest () const noexcept
Node *	get_largest () const noexcept
Node *	get_uncle (Node *node) const noexcept
template<class NodeNameGetter >
void	dump_to_dot_base (const std::string &filename, NodeNameGetter name_getter) const
template<class NodeNameGetter >
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

Constructor & Destructor Documentation

BinarySearchTree()

template<class Node, class Options, class Tag = int, class Compare = ygg::utilities::flexible_less, class ParentContainer = DefaultParentContainer<Node>>

ygg::bst::BinarySearchTree< Node, Options, Tag, Compare, ParentContainer >::BinarySearchTree ( 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()

template<class Node, class Options, class Tag = int, class Compare = ygg::utilities::flexible_less, class ParentContainer = DefaultParentContainer<Node>>

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

noexcept

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

cbegin()

template<class Node, class Options, class Tag = int, class Compare = ygg::utilities::flexible_less, class ParentContainer = DefaultParentContainer<Node>>

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

noexcept

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

cend()

template<class Node, class Options, class Tag = int, class Compare = ygg::utilities::flexible_less, class ParentContainer = DefaultParentContainer<Node>>

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

noexcept

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

clear()

template<class Node, class Options, class Tag = int, class Compare = ygg::utilities::flexible_less, class ParentContainer = DefaultParentContainer<Node>>

void ygg::bst::BinarySearchTree< Node, Options, Tag, Compare, ParentContainer >::clear ( )

noexcept

Removes all elements from the tree.

Removes all elements from the tree.

crbegin()

template<class Node, class Options, class Tag = int, class Compare = ygg::utilities::flexible_less, class ParentContainer = DefaultParentContainer<Node>>

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

noexcept

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

crend()

template<class Node, class Options, class Tag = int, class Compare = ygg::utilities::flexible_less, class ParentContainer = DefaultParentContainer<Node>>

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

noexcept

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

dump_to_dot()

template<class Node, class Options, class Tag = int, class Compare = ygg::utilities::flexible_less, class ParentContainer = DefaultParentContainer<Node>>

template<class NodeTraits >

void ygg::bst::BinarySearchTree< Node, Options, Tag, Compare, ParentContainer >::dump_to_dot

(

const std::string &

filename

)

const

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()

template<class Node, class Options, class Tag = int, class Compare = ygg::utilities::flexible_less, class ParentContainer = DefaultParentContainer<Node>>

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

noexcept

Returns whether the tree is empty.

This method runs in O(1).

Returns

true if the tree is empty, false otherwise

end()

template<class Node, class Options, class Tag = int, class Compare = ygg::utilities::flexible_less, class ParentContainer = DefaultParentContainer<Node>>

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

noexcept

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

find()

template<class Node, class Options, class Tag = int, class Compare = ygg::utilities::flexible_less, class ParentContainer = DefaultParentContainer<Node>>

template<class Comparable , bool ensure_first = false>

const_iterator<false> ygg::bst::BinarySearchTree< Node, Options, Tag, Compare, ParentContainer >::find

(

const Comparable &

query

)

const

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

iterator_to()

template<class Node, class Options, class Tag = int, class Compare = ygg::utilities::flexible_less, class ParentContainer = DefaultParentContainer<Node>>

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

noexcept

Returns an iterator pointing to the entry held in node.

Parameters

node	The node the iterator should point to.

lower_bound()

template<class Node, class Options, class Tag = int, class Compare = ygg::utilities::flexible_less, class ParentContainer = DefaultParentContainer<Node>>

template<class Comparable >

const_iterator<false> ygg::bst::BinarySearchTree< Node, Options, Tag, Compare, ParentContainer >::lower_bound

(

const Comparable &

query

)

const

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

operator=()

template<class Node, class Options, class Tag = int, class Compare = ygg::utilities::flexible_less, class ParentContainer = DefaultParentContainer<Node>>

MyClass& ygg::bst::BinarySearchTree< Node, Options, Tag, Compare, ParentContainer >::operator= ( MyClass &&  other )

noexcept

Move-assign an other red-black tree to this one.

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

rbegin()

template<class Node, class Options, class Tag = int, class Compare = ygg::utilities::flexible_less, class ParentContainer = DefaultParentContainer<Node>>

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

noexcept

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

rend()

template<class Node, class Options, class Tag = int, class Compare = ygg::utilities::flexible_less, class ParentContainer = DefaultParentContainer<Node>>

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

noexcept

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

size()

template<class Node, class Options, class Tag = int, class Compare = ygg::utilities::flexible_less, class ParentContainer = DefaultParentContainer<Node>>

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

noexcept

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()

template<class Node, class Options, class Tag = int, class Compare = ygg::utilities::flexible_less, class ParentContainer = DefaultParentContainer<Node>>

template<class Comparable >

const_iterator<false> ygg::bst::BinarySearchTree< Node, Options, Tag, Compare, ParentContainer >::upper_bound

(

const Comparable &

query

)

const

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/bst.hpp