L4Re - L4 Runtime Environment
bst.h
Go to the documentation of this file.
1 // vi:ft=cpp
6 /*
7  * (c) 2008-2009 Alexander Warg <warg@os.inf.tu-dresden.de>,
8  * Carsten Weinhold <weinhold@os.inf.tu-dresden.de>
9  * economic rights: Technische Universit├Ąt Dresden (Germany)
10  *
11  * This file is part of TUD:OS and distributed under the terms of the
12  * GNU General Public License 2.
13  * Please see the COPYING-GPL-2 file for details.
14  *
15  * As a special exception, you may use this file as part of a free software
16  * library without restriction. Specifically, if other files instantiate
17  * templates or use macros or inline functions from this file, or you compile
18  * this file and link it with other files to produce an executable, this
19  * file does not by itself cause the resulting executable to be covered by
20  * the GNU General Public License. This exception does not however
21  * invalidate any other reasons why the executable file might be covered by
22  * the GNU General Public License.
23  */
24 #pragma once
25 
26 #include "../type_traits"
27 #include "bst_base.h"
28 #include "bst_iter.h"
29 
30 namespace cxx { namespace Bits {
31 
39 template< typename Node, typename Get_key, typename Compare >
40 class Bst
41 {
42 private:
43  typedef Direction Dir;
45  struct Fwd
46  {
47  static Node *child(Node const *n, Direction d)
48  { return Bst_node::next<Node>(n, d); }
49 
50  static bool cmp(Node const *l, Node const *r)
51  { return Compare()(Get_key::key_of(l), Get_key::key_of(r)); }
52  };
53 
55  struct Rev
56  {
57  static Node *child(Node const *n, Direction d)
58  { return Bst_node::next<Node>(n, !d); }
59 
60  static bool cmp(Node const *l, Node const *r)
61  { return Compare()(Get_key::key_of(r), Get_key::key_of(l)); }
62  };
63 
64 public:
66  typedef typename Get_key::Key_type Key_type;
68  typedef typename Type_traits<Key_type>::Param_type Key_param_type;
69 
71  typedef Fwd Fwd_iter_ops;
73  typedef Rev Rev_iter_ops;
74 
76 
77  typedef __Bst_iter<Node, Node, Fwd> Iterator;
80  typedef __Bst_iter<Node, Node const, Fwd> Const_iterator;
82  typedef __Bst_iter<Node, Node, Rev> Rev_iterator;
84  typedef __Bst_iter<Node, Node const, Rev> Const_rev_iterator;
86 
87 protected:
96 
99 
101  Bst() : _head(0) {}
102 
104  Node *head() const { return static_cast<Node*>(_head); }
105 
107  static Key_type k(Bst_node const *n)
108  { return Get_key::key_of(static_cast<Node const *>(n)); }
109 
118  static Dir dir(Key_param_type l, Key_param_type r)
119  {
120  Compare cmp;
121  Dir d(cmp(r, l));
122  if (d == Direction::L && !cmp(l, r))
123  return Direction::N;
124  return d;
125  }
126 
135  static Dir dir(Key_param_type l, Bst_node const *r)
136  { return dir(l, k(r)); }
137 
139  static bool greater(Key_param_type l, Key_param_type r)
140  { return Compare()(r, l); }
141 
143  static bool greater(Key_param_type l, Bst_node const *r)
144  { return greater(l, k(r)); }
145 
147  static bool greater(Bst_node const *l, Bst_node const *r)
148  { return greater(k(l), k(r)); }
157  template<typename FUNC>
158  static void remove_tree(Bst_node *head, FUNC &&callback)
159  {
160  if (Bst_node *n = Bst_node::next(head, Dir::L))
161  remove_tree(n, callback);
162 
163  if (Bst_node *n = Bst_node::next(head, Dir::R))
164  remove_tree(n, callback);
165 
166  callback(static_cast<Node *>(head));
167  }
168 
169 public:
170 
179  Const_iterator begin() const { return Const_iterator(head()); }
184  Const_iterator end() const { return Const_iterator(); }
185 
190  Iterator begin() { return Iterator(head()); }
195  Iterator end() { return Iterator(); }
196 
201  Const_rev_iterator rbegin() const { return Const_rev_iterator(head()); }
206  Const_rev_iterator rend() const { return Const_rev_iterator(); }
207 
212  Rev_iterator rbegin() { return Rev_iterator(head()); }
217  Rev_iterator rend() { return Rev_iterator(); }
231  Node *find_node(Key_param_type key) const;
232 
239  Node *lower_bound_node(Key_param_type key) const;
240 
247  Const_iterator find(Key_param_type key) const;
248 
257  template<typename FUNC>
258  void remove_all(FUNC &&callback)
259  {
260  if (!_head)
261  return;
262 
263  Bst_node *head = _head;
264  _head = 0;
265  remove_tree(head, cxx::forward<FUNC>(callback));
266  }
267 
268 
270 };
271 
272 /* find an element */
273 template< typename Node, typename Get_key, class Compare>
274 inline
275 Node *
277 {
278  Dir d;
279 
280  for (Bst_node *q = _head; q; q = Bst_node::next(q, d))
281  {
282  d = dir(key, q);
283  if (d == Dir::N)
284  return static_cast<Node*>(q);
285  }
286  return 0;
287 }
288 
289 template< typename Node, typename Get_key, class Compare>
290 inline
291 Node *
293 {
294  Dir d;
295  Bst_node *r = 0;
296 
297  for (Bst_node *q = _head; q; q = Bst_node::next(q, d))
298  {
299  d = dir(key, q);
300  if (d == Dir::L)
301  r = q; // found a node greater than key
302  else if (d == Dir::N)
303  return static_cast<Node*>(q);
304  }
305  return static_cast<Node*>(r);
306 }
307 
308 /* find an element */
309 template< typename Node, typename Get_key, class Compare>
310 inline
313 {
314  Bst_node *q = _head;
315  Bst_node *r = q;
316 
317  for (Dir d; q; q = Bst_node::next(q, d))
318  {
319  d = dir(key, q);
320  if (d == Dir::N)
321  return Iterator(static_cast<Node*>(q), static_cast<Node *>(r));
322 
323  if (d != Dir::L && q == r)
324  r = Bst_node::next(q, d);
325  }
326  return Iterator();
327 }
328 
329 }}
static void remove_tree(Bst_node *head, FUNC &&callback)
Remove all elements in the subtree of head.
Definition: bst.h:158
Our C++ library.
Definition: arith:22
__Bst_iter< Node, Node, Rev > Rev_iterator
Backward iterator.
Definition: bst.h:82
Const_rev_iterator rbegin() const
Get the constant backward iterator for the last element in the set.
Definition: bst.h:201
Go to the left child.
Definition: bst_base.h:44
__Bst_iter< Node, Node const, Fwd > Const_iterator
Constant forward iterator.
Definition: bst.h:80
Rev Rev_iter_ops
Helper for building reverse iterators for different wrapper classes.
Definition: bst.h:73
Const_rev_iterator rend() const
Get the end marker for the constant backward iterator.
Definition: bst.h:206
Node * head() const
Access the head node as object of type Node.
Definition: bst.h:104
__Bst_iter< Node, Node const, Rev > Const_rev_iterator
Constant backward.
Definition: bst.h:84
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:292
Const_iterator find(Key_param_type key) const
find the node with the given key.
Definition: bst.h:312
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:135
static bool greater(Key_param_type l, Bst_node const *r)
Is l greater than r.
Definition: bst.h:143
The direction to go in a binary search tree.
Definition: bst_base.h:39
Get_key::Key_type Key_type
The type of key values used to generate the total order of the elements.
Definition: bst.h:66
Node * find_node(Key_param_type key) const
find the node with the given key.
Definition: bst.h:276
static Bst_node * next(Bst_node const *p, Direction d)
Get next node in direction d.
Definition: bst_base.h:94
static Key_type k(Bst_node const *n)
Get the key value of n.
Definition: bst.h:107
void remove_all(FUNC &&callback)
Clear the tree.
Definition: bst.h:258
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:118
Type_traits< Key_type >::Param_type Key_param_type
The type for key parameters.
Definition: bst.h:68
AVL tree.
static bool greater(Bst_node const *l, Bst_node const *r)
Is l greater than r.
Definition: bst.h:147
Bst_node * _head
The head pointer of the tree.
Definition: bst.h:98
Const_iterator begin() const
Get the constant forward iterator for the first element in the set.
Definition: bst.h:179
Bst()
Create an empty tree.
Definition: bst.h:101
Basic binary search tree (BST).
Definition: bst.h:40
Const_iterator end() const
Get the end marker for the constant forward iterator.
Definition: bst.h:184
Basic type of a node in a binary search tree (BST).
Definition: bst_base.h:77
static bool greater(Key_param_type l, Key_param_type r)
Is l greater than r.
Definition: bst.h:139
Go to the right child.
Definition: bst_base.h:45
__Bst_iter< Node, Node, Fwd > Iterator
Forward iterator.
Definition: bst.h:78
Iterator begin()
Get the mutable forward iterator for the first element of the set.
Definition: bst.h:190
AVL tree.
Fwd Fwd_iter_ops
Helper for building forward iterators for different wrapper classes.
Definition: bst.h:71
Rev_iterator rbegin()
Get the mutable backward iterator for the last element of the set.
Definition: bst.h:212
Iterator end()
Get the end marker for the mutable forward iterator.
Definition: bst.h:195
Rev_iterator rend()
Get the end marker for the mutable backward iterator.
Definition: bst.h:217