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
30namespace cxx { namespace Bits {
31
39template< typename Node, typename Get_key, typename Compare >
40class Bst
41{
42private:
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
64public:
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
78 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;
87protected:
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
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
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 {
161 remove_tree(n, callback);
162
164 remove_tree(n, callback);
165
166 callback(static_cast<Node *>(head));
167 }
168
169public:
170
184 Const_iterator end() const { return Const_iterator(); }
185
190 Iterator begin() { return Iterator(head()); }
195 Iterator end() { return Iterator(); }
196
207
225
231 Node *find_node(Key_param_type key) const;
232
240
248
257 template<typename FUNC>
258 void remove_all(FUNC &&callback)
259 {
260 if (!_head)
261 return;
262
264 _head = 0;
265 remove_tree(head, cxx::forward<FUNC>(callback));
266 }
267
268
270};
271
272/* find an element */
273template< typename Node, typename Get_key, class Compare>
274inline
275Node *
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
289template< typename Node, typename Get_key, class Compare>
290inline
291Node *
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 */
309template< typename Node, typename Get_key, class Compare>
310inline
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}}
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:41
__Bst_iter< Node, Node const, Rev > Const_rev_iterator
Constant backward.
Definition bst.h:84
Get_key::Key_type Key_type
The type of key values used to generate the total order of the elements.
Definition bst.h:66
__Bst_iter< Node, Node, Fwd > Iterator
Forward iterator.
Definition bst.h:78
Iterator end()
Get the end marker for the mutable forward iterator.
Definition bst.h:195
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
Bst()
Create an empty tree.
Definition bst.h:101
Rev_iterator rend()
Get the end marker for the mutable backward iterator.
Definition bst.h:217
Type_traits< Key_type >::Param_type Key_param_type
The type for key parameters.
Definition bst.h:68
static bool greater(Key_param_type l, Bst_node const *r)
Is l greater than r.
Definition bst.h:143
Const_rev_iterator rend() const
Get the end marker for the constant backward iterator.
Definition bst.h:206
Const_rev_iterator rbegin() const
Get the constant backward iterator for the last element in the set.
Definition bst.h:201
Rev Rev_iter_ops
Helper for building reverse iterators for different wrapper classes.
Definition bst.h:73
Bst_node * _head
The head pointer of the tree.
Definition bst.h:98
Node * find_node(Key_param_type key) const
find the node with the given key.
Definition bst.h:276
__Bst_iter< Node, Node const, Fwd > Const_iterator
Constant forward iterator.
Definition bst.h:80
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, Key_param_type r)
Is l greater than r.
Definition bst.h:139
Const_iterator find(Key_param_type key) const
find the node with the given key.
Definition bst.h:312
Iterator begin()
Get the mutable forward iterator for the first element of the set.
Definition bst.h:190
void remove_all(FUNC &&callback)
Clear the tree.
Definition bst.h:258
static Key_type k(Bst_node const *n)
Get the key value of n.
Definition bst.h:107
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
Const_iterator end() const
Get the end marker for the constant forward iterator.
Definition bst.h:184
__Bst_iter< Node, Node, Rev > Rev_iterator
Backward iterator.
Definition bst.h:82
Fwd Fwd_iter_ops
Helper for building forward iterators for different wrapper classes.
Definition bst.h:71
Const_iterator begin() const
Get the constant forward iterator for the first element in the set.
Definition bst.h:179
Rev_iterator rbegin()
Get the mutable backward iterator for the last element of the set.
Definition bst.h:212
static void remove_tree(Bst_node *head, FUNC &&callback)
Remove all elements in the subtree of head.
Definition bst.h:158
static bool greater(Bst_node const *l, Bst_node const *r)
Is l greater than r.
Definition bst.h:147
Node * head() const
Access the head node as object of type Node.
Definition bst.h:104
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