L4Re Operating System Framework
Interface and Usage Documentation
Loading...
Searching...
No Matches
bst_iter.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
25#pragma once
26
27#include "bst_base.h"
28
29namespace cxx { namespace Bits {
30
39template< typename Node, typename Node_op >
40class __Bst_iter_b
41{
42protected:
43 typedef Direction Dir;
44 Node const *_n;
45 Node const *_r;
46
48 __Bst_iter_b() : _n(0), _r(0) {}
49
55 __Bst_iter_b(Node const *t)
56 : _n(t), _r(_n)
57 { _downmost(); }
58
59 __Bst_iter_b(Node const *t, Node const *r)
60 : _n(t), _r(r)
61 {}
62
64 inline void _downmost();
65
67 inline void inc();
68
69public:
71 bool operator == (__Bst_iter_b const &o) const { return _n == o._n; }
73 bool operator != (__Bst_iter_b const &o) const { return _n != o._n; }
74};
75
84template< typename Node, typename Node_type, typename Node_op >
85class __Bst_iter : public __Bst_iter_b<Node, Node_op>
86{
87private:
89 typedef __Bst_iter_b<Node, Node_op> Base;
90
91 using Base::_n;
92 using Base::_r;
93 using Base::inc;
94
95public:
97 __Bst_iter() {}
98
104 __Bst_iter(Node const *t) : Base(t) {}
105 __Bst_iter(Node const *t, Node const *r) : Base(t, r) {}
106
107// template<typename Key2>
108 __Bst_iter(Base const &o) : Base(o) {}
109
114 Node_type &operator * () const { return *const_cast<Node *>(_n); }
119 Node_type *operator -> () const { return const_cast<Node *>(_n); }
123 __Bst_iter &operator ++ () { inc(); return *this; }
127 __Bst_iter &operator ++ (int)
128 { __Bst_iter tmp = *this; inc(); return tmp; }
129};
130
131
132//----------------------------------------------------------------------------
133/* IMPLEMENTATION: __Bst_iter_b */
134
135template< typename Node, typename Node_op>
136inline
137void __Bst_iter_b<Node, Node_op>::_downmost()
138{
139 while (_n)
140 {
141 Node *n = Node_op::child(_n, Dir::L);
142 if (n)
143 _n = n;
144 else
145 return;
146 }
147}
148
149template< typename Node, typename Node_op>
150void __Bst_iter_b<Node, Node_op>::inc()
151{
152 if (!_n)
153 return;
154
155 if (_n == _r)
156 {
157 _r = _n = Node_op::child(_r, Dir::R);
158 _downmost();
159 return;
160 }
161
162 if (Node_op::child(_n, Dir::R))
163 {
164 _n = Node_op::child(_n, Dir::R);
165 _downmost();
166 return;
167 }
168
169 Node const *q = _r;
170 Node const *p = _r;
171 while (1)
172 {
173 if (Node_op::cmp(_n, q))
174 {
175 p = q;
176 q = Node_op::child(q, Dir::L);
177 }
178 else if (_n == q || Node_op::child(q, Dir::R) == _n)
179 {
180 _n = p;
181 return;
182 }
183 else
184 q = Node_op::child(q, Dir::R);
185 }
186}
187
188}}
AVL tree.
Our C++ library.
Definition arith:22