26#include "../type_traits"
32namespace cxx {
namespace Bits {
41template<
typename Node,
typename Get_key,
typename Compare >
44 friend struct ::Avl_set_tester;
51 static Node *child(Node
const *n,
Direction d)
52 {
return Bst_node::next<Node>(n, d); }
54 static bool cmp(Node
const *l, Node
const *r)
55 {
return Compare()(Get_key::key_of(l), Get_key::key_of(r)); }
61 static Node *child(Node
const *n,
Direction d)
62 {
return Bst_node::next<Node>(n, !d); }
64 static bool cmp(Node
const *l, Node
const *r)
65 {
return Compare()(Get_key::key_of(r), Get_key::key_of(l)); }
108 Node *
head()
const {
return static_cast<Node*
>(
_head); }
112 {
return Get_key::key_of(
static_cast<Node
const *
>(n)); }
140 {
return dir(l,
k(r)); }
144 {
return Compare()(r, l); }
161 template<
typename FUNC>
170 callback(
static_cast<Node *
>(
head));
261 template<
typename FUNC>
277template<
typename Node,
typename Get_key,
class Compare>
288 return static_cast<Node*
>(q);
293template<
typename Node,
typename Get_key,
class Compare>
306 else if (d == Dir::N)
307 return static_cast<Node*
>(q);
309 return static_cast<Node*
>(r);
313template<
typename Node,
typename Get_key,
class Compare>
325 return Iterator(
static_cast<Node*
>(q),
static_cast<Node *
>(r));
327 if (d != Dir::L && q == r)
Basic type of a node in a binary search tree (BST).
static Bst_node * next(Bst_node const *p, Direction d)
Get next node in direction d.
Basic binary search tree (BST).
__Bst_iter< Node, Node const, Rev > Const_rev_iterator
Constant backward.
Get_key::Key_type Key_type
The type of key values used to generate the total order of the elements.
__Bst_iter< Node, Node, Fwd > Iterator
Forward iterator.
Iterator end()
Get the end marker for the mutable forward iterator.
Node * lower_bound_node(Key_param_type key) const
Find the first node with a key not less than the given key.
Bst()
Create an empty tree.
Rev_iterator rend()
Get the end marker for the mutable backward iterator.
Type_traits< Key_type >::Param_type Key_param_type
The type for key parameters.
static bool greater(Key_param_type l, Bst_node const *r)
Is l greater than r.
Const_rev_iterator rend() const
Get the end marker for the constant backward iterator.
Const_rev_iterator rbegin() const
Get the constant backward iterator for the last element in the set.
Rev Rev_iter_ops
Helper for building reverse iterators for different wrapper classes.
Bst_node * _head
The head pointer of the tree.
Node * find_node(Key_param_type key) const
find the node with the given key.
__Bst_iter< Node, Node const, Fwd > Const_iterator
Constant forward iterator.
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.
Const_iterator find(Key_param_type key) const
find the node with the given key.
Iterator begin()
Get the mutable forward iterator for the first element of the set.
void remove_all(FUNC &&callback)
Clear the tree.
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.
Const_iterator end() const
Get the end marker for the constant forward iterator.
__Bst_iter< Node, Node, Rev > Rev_iterator
Backward iterator.
Fwd Fwd_iter_ops
Helper for building forward iterators for different wrapper classes.
Const_iterator begin() const
Get the constant forward iterator for the first element in the set.
Rev_iterator rbegin()
Get the mutable backward iterator for the last element of the set.
static void remove_tree(Bst_node *head, FUNC &&callback)
Remove all elements in the subtree of head.
static bool greater(Bst_node const *l, Bst_node const *r)
Is l greater than r.
Node * head() const
Access the head node as object of type Node.
The direction to go in a binary search tree.
@ R
Go to the right child.