Loading...
Searching...
No Matches
bst.h
Go to the documentation of this file.
// vi:ft=cpp
/*
* (c) 2008-2009 Alexander Warg <warg@os.inf.tu-dresden.de>,
* Carsten Weinhold <weinhold@os.inf.tu-dresden.de>
* economic rights: Technische Universität Dresden (Germany)
*
* License: see LICENSE.spdx (in this directory or the directories above)
*/
#pragma once
#include "../type_traits"
#include "bst_base.h"
#include "bst_iter.h"
struct Avl_set_tester;
namespace cxx { namespace Bits {
template< typename Node, typename Get_key, typename Compare >
class Bst
{
friend struct ::Avl_set_tester;
private:
typedef Direction Dir;
struct Fwd
{
static Node *child(Node const *n, Direction d)
{ return Bst_node::next<Node>(n, d); }
static bool cmp(Node const *l, Node const *r)
{ return Compare()(Get_key::key_of(l), Get_key::key_of(r)); }
};
struct Rev
{
static Node *child(Node const *n, Direction d)
{ return Bst_node::next<Node>(n, !d); }
static bool cmp(Node const *l, Node const *r)
{ return Compare()(Get_key::key_of(r), Get_key::key_of(l)); }
};
public:
typedef typename Get_key::Key_type Key_type;
typedef typename Type_traits<Key_type>::Param_type Key_param_type;
typedef Fwd Fwd_iter_ops;
typedef Rev Rev_iter_ops;
typedef __Bst_iter<Node, Node, Fwd> Iterator;
typedef __Bst_iter<Node, Node const, Fwd> Const_iterator;
typedef __Bst_iter<Node, Node, Rev> Rev_iterator;
typedef __Bst_iter<Node, Node const, Rev> Const_rev_iterator;
protected:
Bst_node *_head;
Bst() : _head(0) {}
Node *head() const { return static_cast<Node*>(_head); }
static Key_type k(Bst_node const *n)
{ return Get_key::key_of(static_cast<Node const *>(n)); }
static Dir dir(Key_param_type l, Key_param_type r)
{
Compare cmp;
Dir d(cmp(r, l));
if (d == Direction::L && !cmp(l, r))
return Direction::N;
return d;
}
static Dir dir(Key_param_type l, Bst_node const *r)
{ return dir(l, k(r)); }
static bool greater(Key_param_type l, Key_param_type r)
{ return Compare()(r, l); }
static bool greater(Key_param_type l, Bst_node const *r)
{ return greater(l, k(r)); }
static bool greater(Bst_node const *l, Bst_node const *r)
{ return greater(k(l), k(r)); }
template<typename FUNC>
static void remove_tree(Bst_node *head, FUNC &&callback)
{
if (Bst_node *n = Bst_node::next(head, Dir::L))
remove_tree(n, callback);
if (Bst_node *n = Bst_node::next(head, Dir::R))
remove_tree(n, callback);
callback(static_cast<Node *>(head));
}
public:
Const_iterator begin() const { return Const_iterator(head()); }
Const_iterator end() const { return Const_iterator(); }
Iterator begin() { return Iterator(head()); }
Iterator end() { return Iterator(); }
Const_rev_iterator rbegin() const { return Const_rev_iterator(head()); }
Const_rev_iterator rend() const { return Const_rev_iterator(); }
Rev_iterator rbegin() { return Rev_iterator(head()); }
Rev_iterator rend() { return Rev_iterator(); }
Node *find_node(Key_param_type key) const;
Node *lower_bound_node(Key_param_type key) const;
Const_iterator find(Key_param_type key) const;
template<typename FUNC>
void remove_all(FUNC &&callback)
{
if (!_head)
return;
Bst_node *head = _head;
_head = 0;
remove_tree(head, cxx::forward<FUNC>(callback));
}
};
/* find an element */
template< typename Node, typename Get_key, class Compare>
inline
Node *
Bst<Node, Get_key, Compare>::find_node(Key_param_type key) const
{
Dir d;
for (Bst_node *q = _head; q; q = Bst_node::next(q, d))
{
d = dir(key, q);
if (d == Dir::N)
return static_cast<Node*>(q);
}
return 0;
}
template< typename Node, typename Get_key, class Compare>
inline
Node *
Bst<Node, Get_key, Compare>::lower_bound_node(Key_param_type key) const
{
Dir d;
Bst_node *r = 0;
for (Bst_node *q = _head; q; q = Bst_node::next(q, d))
{
d = dir(key, q);
if (d == Dir::L)
r = q; // found a node greater than key
else if (d == Dir::N)
return static_cast<Node*>(q);
}
return static_cast<Node*>(r);
}
/* find an element */
template< typename Node, typename Get_key, class Compare>
inline
typename Bst<Node, Get_key, Compare>::Const_iterator
Bst<Node, Get_key, Compare>::find(Key_param_type key) const
{
Bst_node *q = _head;
Bst_node *r = q;
for (Dir d; q; q = Bst_node::next(q, d))
{
d = dir(key, q);
if (d == Dir::N)
return Iterator(static_cast<Node*>(q), static_cast<Node *>(r));
if (d != Dir::L && q == r)
r = Bst_node::next(q, d);
}
return Iterator();
}
}}
bst_base.h
AVL tree.
bst_iter.h
AVL tree.
cxx::Bits::Bst_node
Basic type of a node in a binary search tree (BST).
Definition bst_base.h:71
cxx::Bits::Bst_node::next
static Bst_node * next(Bst_node const *p, Direction d)
Get next node in direction d.
Definition bst_base.h:87
cxx::Bits::Bst::Const_rev_iterator
__Bst_iter< Node, Node const, Rev > Const_rev_iterator
Constant backward.
Definition bst.h:77
cxx::Bits::Bst::Key_type
Get_key::Key_type Key_type
The type of key values used to generate the total order of the elements.
Definition bst.h:59
cxx::Bits::Bst::Iterator
__Bst_iter< Node, Node, Fwd > Iterator
Forward iterator.
Definition bst.h:71
cxx::Bits::Bst::end
Iterator end()
Get the end marker for the mutable forward iterator.
Definition bst.h:188
cxx::Bits::Bst::lower_bound_node
Node * lower_bound_node(Key_param_type key) const
Find the first node with a key not less than the given key.
Definition bst.h:285
cxx::Bits::Bst::Bst
Bst()
Create an empty tree.
Definition bst.h:94
cxx::Bits::Bst::rend
Rev_iterator rend()
Get the end marker for the mutable backward iterator.
Definition bst.h:210
cxx::Bits::Bst::Key_param_type
Type_traits< Key_type >::Param_type Key_param_type
The type for key parameters.
Definition bst.h:61
cxx::Bits::Bst::greater
static bool greater(Key_param_type l, Bst_node const *r)
Is l greater than r.
Definition bst.h:136
cxx::Bits::Bst::rend
Const_rev_iterator rend() const
Get the end marker for the constant backward iterator.
Definition bst.h:199
cxx::Bits::Bst::rbegin
Const_rev_iterator rbegin() const
Get the constant backward iterator for the last element in the set.
Definition bst.h:194
cxx::Bits::Bst::Rev_iter_ops
Rev Rev_iter_ops
Helper for building reverse iterators for different wrapper classes.
Definition bst.h:66
cxx::Bits::Bst::_head
Bst_node * _head
The head pointer of the tree.
Definition bst.h:91
cxx::Bits::Bst::find_node
Node * find_node(Key_param_type key) const
find the node with the given key.
Definition bst.h:269
cxx::Bits::Bst::Const_iterator
__Bst_iter< Node, Node const, Fwd > Const_iterator
Constant forward iterator.
Definition bst.h:73
cxx::Bits::Bst::dir
static Dir dir(Key_param_type l, Bst_node const *r)
Get the direction to go from l to search for r.
Definition bst.h:128
cxx::Bits::Bst::greater
static bool greater(Key_param_type l, Key_param_type r)
Is l greater than r.
Definition bst.h:132
cxx::Bits::Bst::find
Const_iterator find(Key_param_type key) const
find the node with the given key.
Definition bst.h:305
cxx::Bits::Bst::begin
Iterator begin()
Get the mutable forward iterator for the first element of the set.
Definition bst.h:183
cxx::Bits::Bst::remove_all
void remove_all(FUNC &&callback)
Clear the tree.
Definition bst.h:251
cxx::Bits::Bst::k
static Key_type k(Bst_node const *n)
Get the key value of n.
Definition bst.h:100
cxx::Bits::Bst::dir
static Dir dir(Key_param_type l, Key_param_type r)
Get the direction to go from l to search for r.
Definition bst.h:111
cxx::Bits::Bst::end
Const_iterator end() const
Get the end marker for the constant forward iterator.
Definition bst.h:177
cxx::Bits::Bst::Rev_iterator
__Bst_iter< Node, Node, Rev > Rev_iterator
Backward iterator.
Definition bst.h:75
cxx::Bits::Bst::Fwd_iter_ops
Fwd Fwd_iter_ops
Helper for building forward iterators for different wrapper classes.
Definition bst.h:64
cxx::Bits::Bst::begin
Const_iterator begin() const
Get the constant forward iterator for the first element in the set.
Definition bst.h:172
cxx::Bits::Bst::rbegin
Rev_iterator rbegin()
Get the mutable backward iterator for the last element of the set.
Definition bst.h:205
cxx::Bits::Bst::remove_tree
static void remove_tree(Bst_node *head, FUNC &&callback)
Remove all elements in the subtree of head.
Definition bst.h:151
cxx::Bits::Bst::greater
static bool greater(Bst_node const *l, Bst_node const *r)
Is l greater than r.
Definition bst.h:140
cxx::Bits::Bst::head
Node * head() const
Access the head node as object of type Node.
Definition bst.h:97
cxx::Bits
Internal helpers for the cxx package.
Definition avl_map:21
cxx
Our C++ library.
Definition arith:11
cxx::Bits::Direction
The direction to go in a binary search tree.
Definition bst_base.h:29
cxx::Bits::Direction::L
@ L
Go to the left child.
Definition bst_base.h:33
cxx::Bits::Direction::N
@ N
Stop.
Definition bst_base.h:35
cxx::Bits::Direction::R
@ R
Go to the right child.
Definition bst_base.h:34