L4Re Operating System Framework
Interface and Usage Documentation
Loading...
Searching...
No Matches
cxx::Bits::Bst< Node, Get_key, Compare > Class Template Reference

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
lis the key to look for.
ris the node at the current position.
Return values
Direction::LFor left.
Direction::RFor right.
Direction::NIf 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
lis the key to look for.
ris the key at the current position.
Return values
Direction::Lfor left
Direction::Rfor right
Direction::Nif 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
keyThe 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
keyThe 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
keyThe 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
callbackOptional 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
headHead of the the subtree to remove
callbackOptional 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: