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 31 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 183 of file bst.h.

References 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 172 of file bst.h.

References head().

Here is the call graph for this function:

## dir() [1/2]

template<typename Node, typename Get_key, typename Compare>

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 128 of file bst.h.

References dir(), and k().

Here is the call graph for this function:

## dir() [2/2]

template<typename Node, typename Get_key, typename Compare>

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

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 188 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 177 of file bst.h.

## 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 305 of file bst.h.

References _head, dir(), cxx::Bits::Direction::L, cxx::Bits::Direction::N, and 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 269 of file bst.h.

References _head, dir(), cxx::Bits::Direction::N, and cxx::Bits::Bst_node::next().

Here is the call 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 285 of file bst.h.

References _head, dir(), cxx::Bits::Direction::L, cxx::Bits::Direction::N, and cxx::Bits::Bst_node::next().

Here is the call 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 205 of file bst.h.

References 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 194 of file bst.h.

References head().

Here is the call 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 251 of file bst.h.

References _head, head(), and remove_tree().

Referenced by cxx::Avl_tree< Entry, Names_get_key >::~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>

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

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 210 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 199 of file bst.h.

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

- l4/cxx/bits/bst.h