Basic binary search tree (BST). More...

#include <bst.h>

Inheritance diagram for cxx::Bits::Bst< Node, Get_key, Compare >:

Collaboration diagram for cxx::Bits::Bst< Node, Get_key, Compare >:

Public Types
typedef Get_key::Key_type	Key_type
	The type of key values used to generate the total order of the elements.

typedef Type_traits< Key_type >::Param_type	Key_param_type
	The type for key parameters.

typedef Fwd	Fwd_iter_ops
	Helper for building forward iterators for different wrapper classes.

typedef Rev	Rev_iter_ops
	Helper for building reverse iterators for different wrapper classes.

Iterators
typedef __Bst_iter< Node, Node, Fwd >	Iterator
	Forward iterator.

typedef __Bst_iter< Node, Node const, Fwd >	Const_iterator
	Constant forward iterator.

typedef __Bst_iter< Node, Node, Rev >	Rev_iterator
	Backward iterator.

typedef __Bst_iter< Node, Node const, Rev >	Const_rev_iterator
	Constant backward.

Public Member Functions
Get default iterators for the ordered tree.
Const_iterator	begin () const
	Get the constant forward iterator for the first element in the set.

Const_iterator	end () const
	Get the end marker for the constant forward iterator.

Iterator	begin ()
	Get the mutable forward iterator for the first element of the set.

Iterator	end ()
	Get the end marker for the mutable forward iterator.

Const_rev_iterator	rbegin () const
	Get the constant backward iterator for the last element in the set.

Const_rev_iterator	rend () const
	Get the end marker for the constant backward iterator.

Rev_iterator	rbegin ()
	Get the mutable backward iterator for the last element of the set.

Rev_iterator	rend ()
	Get the end marker for the mutable backward iterator.

Lookup functions.
Node *	find_node (Key_param_type key) const
	find the node with the given key.

Node *	lower_bound_node (Key_param_type key) const
	Find the first node with a key not less than the given `key`.

Const_iterator	find (Key_param_type key) const
	find the node with the given key.

template<typename FUNC >
void	remove_all (FUNC &&callback)
	Clear the tree.

Static Protected Member Functions
template<typename FUNC >
static void	remove_tree (Bst_node *head, FUNC &&callback)
	Remove all elements in the subtree of head.

Interior access for descendants.
As this class is an intended base class we provide protected access to our interior, use 'using' to make this private in concrete implementations.
Bst_node *	_head
	The head pointer of the tree.

	Bst ()
	Create an empty tree.

Node *	head () const
	Access the head node as object of type Node.

static Key_type	k (Bst_node const *n)
	Get the key value of n.

static Dir	dir (Key_param_type l, Key_param_type r)
	Get the direction to go from `l` to search for `r`.

static Dir	dir (Key_param_type l, Bst_node const *r)
	Get the direction to go from `l` to search for `r`.

static bool	greater (Key_param_type l, Key_param_type r)
	Is l greater than r.

static bool	greater (Key_param_type l, Bst_node const *r)
	Is l greater than r.

static bool	greater (Bst_node const l, Bst_node const r)
	Is l greater than r.

Detailed Description

template<typename Node, typename Get_key, typename Compare>
class cxx::Bits::Bst< Node, Get_key, Compare >

Basic binary search tree (BST).

This class is intended as a base class for concrete binary search trees, such as an AVL tree. This class already provides the basic lookup methods and iterator definitions for a BST.

Definition at line 42 of file bst.h.

Member Function Documentation

◆ begin() [1/2]

template<typename Node , typename Get_key , typename Compare >

Iterator cxx::Bits::Bst< Node, Get_key, Compare >::begin ( )

inline

Get the mutable forward iterator for the first element of the set.

Returns: The mutable forward iterator for the first element of the set.

Definition at line 194 of file bst.h.

References cxx::Bits::Bst< Node, Get_key, Compare >::head().

Here is the call graph for this function:

◆ begin() [2/2]

template<typename Node , typename Get_key , typename Compare >

Const_iterator cxx::Bits::Bst< Node, Get_key, Compare >::begin ( ) const

inline

Get the constant forward iterator for the first element in the set.

Returns: Constant forward iterator for the first element in the set.

Definition at line 183 of file bst.h.

References cxx::Bits::Bst< Node, Get_key, Compare >::head().

Referenced by cxx::Bits::Base_avl_set< ITEM_TYPE, COMPARE, ALLOC, GET_KEY >::begin(), and cxx::Bits::Base_avl_set< ITEM_TYPE, COMPARE, ALLOC, GET_KEY >::begin().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ dir() [1/2]

template<typename Node , typename Get_key , typename Compare >

static Dir cxx::Bits::Bst< Node, Get_key, Compare >::dir	(	Key_param_type	l,
		Bst_node const *	r
	)

inlinestaticprotected

Get the direction to go from l to search for r.

Parameters

l	is the key to look for.
r	is the node at the current position.

Return values

Direction::L	For left.
Direction::R	For right.
Direction::N	If `l` is equal to `r`.

Definition at line 139 of file bst.h.

References cxx::Bits::Bst< Node, Get_key, Compare >::dir(), and cxx::Bits::Bst< Node, Get_key, Compare >::k().

Here is the call graph for this function:

◆ dir() [2/2]

template<typename Node , typename Get_key , typename Compare >

static Dir cxx::Bits::Bst< Node, Get_key, Compare >::dir	(	Key_param_type	l,
		Key_param_type	r
	)

inlinestaticprotected

Get the direction to go from l to search for r.

Parameters

l	is the key to look for.
r	is the key at the current position.

Return values

Direction::L	for left
Direction::R	for right
Direction::N	if `l` is equal to `r`.

Definition at line 122 of file bst.h.

References cxx::Bits::Direction::L, and cxx::Bits::Direction::N.

Referenced by cxx::Bits::Bst< Node, Get_key, Compare >::dir().

Here is the caller graph for this function:

◆ end() [1/2]

template<typename Node , typename Get_key , typename Compare >

Iterator cxx::Bits::Bst< Node, Get_key, Compare >::end ( )

inline

Get the end marker for the mutable forward iterator.

Returns: The end marker for mutable forward iterator.

Definition at line 199 of file bst.h.

◆ end() [2/2]

template<typename Node , typename Get_key , typename Compare >

Const_iterator cxx::Bits::Bst< Node, Get_key, Compare >::end ( ) const

inline

Get the end marker for the constant forward iterator.

Returns: The end marker for the constant forward iterator.

Definition at line 188 of file bst.h.

Referenced by cxx::Bits::Base_avl_set< ITEM_TYPE, COMPARE, ALLOC, GET_KEY >::end(), and cxx::Bits::Base_avl_set< ITEM_TYPE, COMPARE, ALLOC, GET_KEY >::end().

Here is the caller graph for this function:

◆ find()

template<typename Node , typename Get_key , class Compare >

Bst< Node, Get_key, Compare >::Const_iterator cxx::Bits::Bst< Node, Get_key, Compare >::find ( Key_param_type key ) const

inline

find the node with the given key.

Parameters

key	The key value of the element to search.

Returns: A valid iterator for the node with the given key, or an invalid iterator if key was not found.

Definition at line 316 of file bst.h.

References cxx::Bits::Bst_node::next().

Here is the call graph for this function:

◆ find_node()

template<typename Node , typename Get_key , class Compare >

Node * cxx::Bits::Bst< Node, Get_key, Compare >::find_node ( Key_param_type key ) const

inline

find the node with the given key.

Parameters

key	The key value of the element to search.

Returns: A pointer to the node with the given key, or NULL if key was not found.

Definition at line 280 of file bst.h.

References cxx::Bits::Bst_node::next().

Referenced by cxx::Bits::Base_avl_set< ITEM_TYPE, COMPARE, ALLOC, GET_KEY >::find_node().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ lower_bound_node()

template<typename Node , typename Get_key , class Compare >

Node * cxx::Bits::Bst< Node, Get_key, Compare >::lower_bound_node ( Key_param_type key ) const

inline

Find the first node with a key not less than the given key.

Parameters

key	The key used for the search.

Returns: A pointer to the found node, or NULL if no node was found.

Definition at line 296 of file bst.h.

References cxx::Bits::Bst_node::next().

Referenced by cxx::Bits::Base_avl_set< ITEM_TYPE, COMPARE, ALLOC, GET_KEY >::lower_bound_node().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ rbegin() [1/2]

template<typename Node , typename Get_key , typename Compare >

Rev_iterator cxx::Bits::Bst< Node, Get_key, Compare >::rbegin ( )

inline

Get the mutable backward iterator for the last element of the set.

Returns: The mutable backward iterator for the last element of the set.

Definition at line 216 of file bst.h.

References cxx::Bits::Bst< Node, Get_key, Compare >::head().

Here is the call graph for this function:

◆ rbegin() [2/2]

template<typename Node , typename Get_key , typename Compare >

Const_rev_iterator cxx::Bits::Bst< Node, Get_key, Compare >::rbegin ( ) const

inline

Get the constant backward iterator for the last element in the set.

Returns: The constant backward iterator for the last element in the set.

Definition at line 205 of file bst.h.

References cxx::Bits::Bst< Node, Get_key, Compare >::head().

Referenced by cxx::Bits::Base_avl_set< ITEM_TYPE, COMPARE, ALLOC, GET_KEY >::rbegin(), and cxx::Bits::Base_avl_set< ITEM_TYPE, COMPARE, ALLOC, GET_KEY >::rbegin().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ remove_all()

template<typename Node , typename Get_key , typename Compare >

template<typename FUNC >

void cxx::Bits::Bst< Node, Get_key, Compare >::remove_all ( FUNC && callback )

inline

Clear the tree.

Parameters

callback Optional function to be called on each removed element.

The callback may delete the elements. The function guarantees that the elements are no longer used after the callback has been called.

Definition at line 262 of file bst.h.

References cxx::Bits::Bst< Node, Get_key, Compare >::_head, cxx::Bits::Bst< Node, Get_key, Compare >::head(), and cxx::Bits::Bst< Node, Get_key, Compare >::remove_tree().

Referenced by cxx::Avl_tree< Node, Get_key, Compare >::~Avl_tree().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ remove_tree()

template<typename Node , typename Get_key , typename Compare >

template<typename FUNC >

static void cxx::Bits::Bst< Node, Get_key, Compare >::remove_tree	(	Bst_node *	head,
		FUNC &&	callback
	)

inlinestaticprotected

Remove all elements in the subtree of head.

Parameters

head	Head of the the subtree to remove
callback	Optional function called on each removed element.

Definition at line 162 of file bst.h.

References cxx::Bits::Bst< Node, Get_key, Compare >::head(), cxx::Bits::Direction::L, cxx::Bits::Bst_node::next(), cxx::Bits::Direction::R, and cxx::Bits::Bst< Node, Get_key, Compare >::remove_tree().

Referenced by cxx::Bits::Bst< Node, Get_key, Compare >::remove_all(), and cxx::Bits::Bst< Node, Get_key, Compare >::remove_tree().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ rend() [1/2]

template<typename Node , typename Get_key , typename Compare >

Rev_iterator cxx::Bits::Bst< Node, Get_key, Compare >::rend ( )

inline

Get the end marker for the mutable backward iterator.

Returns: The end marker for mutable backward iterator.

Definition at line 221 of file bst.h.

◆ rend() [2/2]

template<typename Node , typename Get_key , typename Compare >

Const_rev_iterator cxx::Bits::Bst< Node, Get_key, Compare >::rend ( ) const

inline

Get the end marker for the constant backward iterator.

Returns: The end marker for the constant backward iterator.

Definition at line 210 of file bst.h.

Referenced by cxx::Bits::Base_avl_set< ITEM_TYPE, COMPARE, ALLOC, GET_KEY >::rend(), and cxx::Bits::Base_avl_set< ITEM_TYPE, COMPARE, ALLOC, GET_KEY >::rend().

Here is the caller graph for this function:

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

l4/cxx/bits/bst.h

Public Types

Public Member Functions

Static Protected Member Functions

Interior access for descendants.

Detailed Description

Member Function Documentation

◆ begin() [1/2]

◆ begin() [2/2]

◆ dir() [1/2]

◆ dir() [2/2]

◆ end() [1/2]

◆ end() [2/2]

◆ find()

◆ find_node()

◆ lower_bound_node()

◆ rbegin() [1/2]

◆ rbegin() [2/2]

◆ remove_all()

◆ remove_tree()

◆ rend() [1/2]

◆ rend() [2/2]