L4Re Operating System Framework
Interface and Usage Documentation
Loading...
Searching...
No Matches
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
30struct Avl_set_tester;
31
32namespace cxx { namespace Bits {
33
41template< typename Node, typename Get_key, typename Compare >
42class Bst
43{
44 friend struct ::Avl_set_tester;
45
46private:
47 typedef Direction Dir;
49 struct Fwd
50 {
51 static Node *child(Node const *n, Direction d)
52 { return Bst_node::next<Node>(n, d); }
53
54 static bool cmp(Node const *l, Node const *r)
55 { return Compare()(Get_key::key_of(l), Get_key::key_of(r)); }
56 };
57
59 struct Rev
60 {
61 static Node *child(Node const *n, Direction d)
62 { return Bst_node::next<Node>(n, !d); }
63
64 static bool cmp(Node const *l, Node const *r)
65 { return Compare()(Get_key::key_of(r), Get_key::key_of(l)); }
66 };
67
68public:
70 typedef typename Get_key::Key_type Key_type;
72 typedef typename Type_traits<Key_type>::Param_type Key_param_type;
73
75 typedef Fwd Fwd_iter_ops;
77 typedef Rev Rev_iter_ops;
78
80
82 typedef __Bst_iter<Node, Node, Fwd> Iterator;
84 typedef __Bst_iter<Node, Node const, Fwd> Const_iterator;
86 typedef __Bst_iter<Node, Node, Rev> Rev_iterator;
88 typedef __Bst_iter<Node, Node const, Rev> Const_rev_iterator;
91protected:
103
105 Bst() : _head(0) {}
106
108 Node *head() const { return static_cast<Node*>(_head); }
109
111 static Key_type k(Bst_node const *n)
112 { return Get_key::key_of(static_cast<Node const *>(n)); }
113
123 {
124 Compare cmp;
125 Dir d(cmp(r, l));
126 if (d == Direction::L && !cmp(l, r))
127 return Direction::N;
128 return d;
129 }
130
139 static Dir dir(Key_param_type l, Bst_node const *r)
140 { return dir(l, k(r)); }
141
144 { return Compare()(r, l); }
145
147 static bool greater(Key_param_type l, Bst_node const *r)
148 { return greater(l, k(r)); }
149
151 static bool greater(Bst_node const *l, Bst_node const *r)
152 { return greater(k(l), k(r)); }
161 template<typename FUNC>
162 static void remove_tree(Bst_node *head, FUNC &&callback)
163 {
165 remove_tree(n, callback);
166
168 remove_tree(n, callback);
169
170 callback(static_cast<Node *>(head));
171 }
172
173public:
174
188 Const_iterator end() const { return Const_iterator(); }
189
194 Iterator begin() { return Iterator(head()); }
199 Iterator end() { return Iterator(); }
200
211
229
235 Node *find_node(Key_param_type key) const;
236
244
252
261 template<typename FUNC>
262 void remove_all(FUNC &&callback)
263 {
264 if (!_head)
265 return;
266
268 _head = 0;
269 remove_tree(head, cxx::forward<FUNC>(callback));
270 }
271
272
274};
275
276/* find an element */
277template< typename Node, typename Get_key, class Compare>
278inline
279Node *
281{
282 Dir d;
283
284 for (Bst_node *q = _head; q; q = Bst_node::next(q, d))
285 {
286 d = dir(key, q);
287 if (d == Dir::N)
288 return static_cast<Node*>(q);
289 }
290 return 0;
291}
292
293template< typename Node, typename Get_key, class Compare>
294inline
295Node *
297{
298 Dir d;
299 Bst_node *r = 0;
300
301 for (Bst_node *q = _head; q; q = Bst_node::next(q, d))
302 {
303 d = dir(key, q);
304 if (d == Dir::L)
305 r = q; // found a node greater than key
306 else if (d == Dir::N)
307 return static_cast<Node*>(q);
308 }
309 return static_cast<Node*>(r);
310}
311
312/* find an element */
313template< typename Node, typename Get_key, class Compare>
314inline
317{
318 Bst_node *q = _head;
319 Bst_node *r = q;
320
321 for (Dir d; q; q = Bst_node::next(q, d))
322 {
323 d = dir(key, q);
324 if (d == Dir::N)
325 return Iterator(static_cast<Node*>(q), static_cast<Node *>(r));
326
327 if (d != Dir::L && q == r)
328 r = Bst_node::next(q, d);
329 }
330 return Iterator();
331}
332
333}}
AVL tree.
AVL tree.
Basic type of a node in a binary search tree (BST).
Definition bst_base.h:82
static Bst_node * next(Bst_node const *p, Direction d)
Get next node in direction d.
Definition bst_base.h:98
Basic binary search tree (BST).
Definition bst.h:43
__Bst_iter< Node, Node const, Rev > Const_rev_iterator
Constant backward.
Definition bst.h:88
Get_key::Key_type Key_type
The type of key values used to generate the total order of the elements.
Definition bst.h:70
__Bst_iter< Node, Node, Fwd > Iterator
Forward iterator.
Definition bst.h:82
Iterator end()
Get the end marker for the mutable forward iterator.
Definition bst.h:199
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:296
Bst()
Create an empty tree.
Definition bst.h:105
Rev_iterator rend()
Get the end marker for the mutable backward iterator.
Definition bst.h:221
Type_traits< Key_type >::Param_type Key_param_type
The type for key parameters.
Definition bst.h:72
static bool greater(Key_param_type l, Bst_node const *r)
Is l greater than r.
Definition bst.h:147
Const_rev_iterator rend() const
Get the end marker for the constant backward iterator.
Definition bst.h:210
Const_rev_iterator rbegin() const
Get the constant backward iterator for the last element in the set.
Definition bst.h:205
Rev Rev_iter_ops
Helper for building reverse iterators for different wrapper classes.
Definition bst.h:77
Bst_node * _head
The head pointer of the tree.
Definition bst.h:102
Node * find_node(Key_param_type key) const
find the node with the given key.
Definition bst.h:280
__Bst_iter< Node, Node const, Fwd > Const_iterator
Constant forward iterator.
Definition bst.h:84
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:139
static bool greater(Key_param_type l, Key_param_type r)
Is l greater than r.
Definition bst.h:143
Const_iterator find(Key_param_type key) const
find the node with the given key.
Definition bst.h:316
Iterator begin()
Get the mutable forward iterator for the first element of the set.
Definition bst.h:194
void remove_all(FUNC &&callback)
Clear the tree.
Definition bst.h:262
static Key_type k(Bst_node const *n)
Get the key value of n.
Definition bst.h:111
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:122
Const_iterator end() const
Get the end marker for the constant forward iterator.
Definition bst.h:188
__Bst_iter< Node, Node, Rev > Rev_iterator
Backward iterator.
Definition bst.h:86
Fwd Fwd_iter_ops
Helper for building forward iterators for different wrapper classes.
Definition bst.h:75
Const_iterator begin() const
Get the constant forward iterator for the first element in the set.
Definition bst.h:183
Rev_iterator rbegin()
Get the mutable backward iterator for the last element of the set.
Definition bst.h:216
static void remove_tree(Bst_node *head, FUNC &&callback)
Remove all elements in the subtree of head.
Definition bst.h:162
static bool greater(Bst_node const *l, Bst_node const *r)
Is l greater than r.
Definition bst.h:151
Node * head() const
Access the head node as object of type Node.
Definition bst.h:108
Our C++ library.
Definition arith:22
The direction to go in a binary search tree.
Definition bst_base.h:40
@ L
Go to the left child.
Definition bst_base.h:44
@ R
Go to the right child.
Definition bst_base.h:45