![]() |
L4Re Operating System Framework
Interface and Usage Documentation
|
Basic binary search tree (BST). More...
#include <bst.h>
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. |
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.
|
inline |
|
inline |
|
inlinestaticprotected |
Get the direction to go from l to search for r.
l | is the key to look for. |
r | is the node at the current position. |
Direction::L | For left. |
Direction::R | For right. |
Direction::N | If l is equal to r. |
Definition at line 128 of file bst.h.
|
inlinestaticprotected |
Get the direction to go from l to search for r.
l | is the key to look for. |
r | is the key at the current position. |
Direction::L | for left |
Direction::R | for right |
Direction::N | if l is equal to r. |
Definition at line 111 of file bst.h.
References cxx::Bits::Direction::L, and cxx::Bits::Direction::N.
Referenced by dir(), find(), find_node(), cxx::Avl_tree< Node, Get_key, Compare >::insert(), lower_bound_node(), and cxx::Avl_tree< Node, Get_key, Compare >::remove().
|
inline |
|
inline |
|
inline |
find the node with the given key.
key | The key value of the element to search. |
Definition at line 305 of file bst.h.
References _head, dir(), cxx::Bits::Direction::L, cxx::Bits::Direction::N, and cxx::Bits::Bst_node::next().
|
inline |
find the node with the given key.
key | The key value of the element to search. |
Definition at line 269 of file bst.h.
References _head, dir(), cxx::Bits::Direction::N, and cxx::Bits::Bst_node::next().
|
inline |
Find the first node with a key not less than the given key.
key | The key used for the search. |
Definition at line 285 of file bst.h.
References _head, dir(), cxx::Bits::Direction::L, cxx::Bits::Direction::N, and cxx::Bits::Bst_node::next().
|
inline |
|
inline |
|
inline |
Clear the tree.
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 251 of file bst.h.
References _head, head(), and remove_tree().
Referenced by cxx::Avl_tree< Entry, Names_get_key >::~Avl_tree().
|
inlinestaticprotected |
Remove all elements in the subtree of head.
head | Head of the the subtree to remove |
callback | Optional function called on each removed element. |
Definition at line 151 of file bst.h.
References head(), cxx::Bits::Direction::L, cxx::Bits::Bst_node::next(), cxx::Bits::Direction::R, and remove_tree().
Referenced by remove_all(), and remove_tree().
|
inline |
|
inline |