L4Re - L4 Runtime Environment
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 
29 namespace cxx { namespace Bits {
30 
39 template< typename Node, typename Node_op >
40 class __Bst_iter_b
41 {
42 protected:
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 
69 public:
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 
84 template< typename Node, typename Node_type, typename Node_op >
85 class __Bst_iter : public __Bst_iter_b<Node, Node_op>
86 {
87 private:
89  typedef __Bst_iter_b<Node, Node_op> Base;
90 
91  using Base::_n;
92  using Base::_r;
93  using Base::inc;
94 
95 public:
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 
135 template< typename Node, typename Node_op>
136 inline
137 void __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 
149 template< typename Node, typename Node_op>
150 void __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 }}
Our C++ library.
Definition: arith:22
Go to the left child.
Definition: bst_base.h:44
AVL tree.
Go to the right child.
Definition: bst_base.h:45