L4Re Operating System Framework
Interface and Usage Documentation
•All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Modules Pages
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 * License: see LICENSE.spdx (in this directory or the directories above)
12 */
13
14#pragma once
15
16#include "bst_base.h"
17
18namespace cxx { namespace Bits {
19
28template< typename Node, typename Node_op >
29class __Bst_iter_b
30{
31protected:
32 typedef Direction Dir;
33 Node const *_n;
34 Node const *_r;
35
37 __Bst_iter_b() : _n(0), _r(0) {}
38
44 __Bst_iter_b(Node const *t)
45 : _n(t), _r(_n)
46 { _downmost(); }
47
48 __Bst_iter_b(Node const *t, Node const *r)
49 : _n(t), _r(r)
50 {}
51
53 inline void _downmost();
54
56 inline void inc();
57
58public:
60 bool operator == (__Bst_iter_b const &o) const { return _n == o._n; }
62 bool operator != (__Bst_iter_b const &o) const { return _n != o._n; }
63};
64
73template< typename Node, typename Node_type, typename Node_op >
74class __Bst_iter : public __Bst_iter_b<Node, Node_op>
75{
76private:
78 typedef __Bst_iter_b<Node, Node_op> Base;
79
80 using Base::_n;
81 using Base::_r;
82 using Base::inc;
83
84public:
86 __Bst_iter() {}
87
93 __Bst_iter(Node const *t) : Base(t) {}
94 __Bst_iter(Node const *t, Node const *r) : Base(t, r) {}
95
96// template<typename Key2>
97 __Bst_iter(Base const &o) : Base(o) {}
98
103 Node_type &operator * () const { return *const_cast<Node *>(_n); }
108 Node_type *operator -> () const { return const_cast<Node *>(_n); }
112 __Bst_iter &operator ++ () { inc(); return *this; }
116 __Bst_iter &operator ++ (int)
117 { __Bst_iter tmp = *this; inc(); return tmp; }
118};
119
120
121//----------------------------------------------------------------------------
122/* IMPLEMENTATION: __Bst_iter_b */
123
124template< typename Node, typename Node_op>
125inline
126void __Bst_iter_b<Node, Node_op>::_downmost()
127{
128 while (_n)
129 {
130 Node *n = Node_op::child(_n, Dir::L);
131 if (n)
132 _n = n;
133 else
134 return;
135 }
136}
137
138template< typename Node, typename Node_op>
139void __Bst_iter_b<Node, Node_op>::inc()
140{
141 if (!_n)
142 return;
143
144 if (_n == _r)
145 {
146 _r = _n = Node_op::child(_r, Dir::R);
147 _downmost();
148 return;
149 }
150
151 if (Node_op::child(_n, Dir::R))
152 {
153 _n = Node_op::child(_n, Dir::R);
154 _downmost();
155 return;
156 }
157
158 Node const *q = _r;
159 Node const *p = _r;
160 while (1)
161 {
162 if (Node_op::cmp(_n, q))
163 {
164 p = q;
165 q = Node_op::child(q, Dir::L);
166 }
167 else if (_n == q || Node_op::child(q, Dir::R) == _n)
168 {
169 _n = p;
170 return;
171 }
172 else
173 q = Node_op::child(q, Dir::R);
174 }
175}
176
177}}
AVL tree.
Our C++ library.
Definition arith:11