1 // vi:ft=cpp
2 /**
3 * \file
4 * \brief AVL tree
5 */
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
31 /**
32 * \internal
33 * \ingroup cxx_api
34 * \brief Generic iterator for the AVL-tree based set.
35 * \param Cmp the type of the comparison functor.
36 * \param Node the type of a node.
37 * \param Node_op the type used to determine the direction of the iterator.
38 */
39 template< typename Node, typename Node_op >
40 class __Bst_iter_b
41 {
42 protected:
43 typedef Direction Dir;
44 Node const *_n; ///< Current node
45 Node const *_r; ///< Root node of current subtree
46
47 /// Create an invalid iterator, used as end marker.
__Bst_iter_b()48 __Bst_iter_b() : _n(0), _r(0) {}
49
50 /**
51 * \brief Create an iterator for the given AVL tree.
52 * \param t the root node of the tree to iterate.
53 * \param cmp the comparison functor for tree elements.
54 */
__Bst_iter_b(Node const * t)55 __Bst_iter_b(Node const *t)
56 : _n(t), _r(_n)
57 { _downmost(); }
58
__Bst_iter_b(Node const * t,Node const * r)59 __Bst_iter_b(Node const *t, Node const *r)
60 : _n(t), _r(r)
61 {}
62
63 /// traverse the subtree down to the leftmost/rightmost leave.
64 inline void _downmost();
65
66 /// Increment to the next element.
67 inline void inc();
68
69 public:
70 /// Check two iterators for equality.
71 bool operator == (__Bst_iter_b const &o) const { return _n == o._n; }
72 /// Check two iterators for non equality.
73 bool operator != (__Bst_iter_b const &o) const { return _n != o._n; }
74 };
75
76 /**
77 * \internal
78 * \ingroup cxx_api
79 * \brief Generic iterator for the AVL-tree based set.
80 * \param Node the type of a node.
81 * \param Node_type the type of the node to return stored in a node.
82 * \param Node_op the type used to determine the direction of the iterator.
83 */
84 template< typename Node, typename Node_type, typename Node_op >
85 class __Bst_iter : public __Bst_iter_b<Node, Node_op>
86 {
87 private:
88 /// Super-class type
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:
96 /// Create an invalid iterator (end marker)
__Bst_iter()97 __Bst_iter() {}
98
99 /**
100 * \brief Create an iterator for the given tree.
101 * \param t the root node of the tree to iterate.
102 * \param cmp the conmparison functor for tree elements.
103 */
__Bst_iter(Node const * t)104 __Bst_iter(Node const *t) : Base(t) {}
__Bst_iter(Node const * t,Node const * r)105 __Bst_iter(Node const *t, Node const *r) : Base(t, r) {}
106
107 // template<typename Key2>
__Bst_iter(Base const & o)108 __Bst_iter(Base const &o) : Base(o) {}
109
110 /**
111 * \brief Dereference the iterator and get the item out of the tree.
112 * \return A reference to the data stored in the AVL tree.
113 */
114 Node_type &operator * () const { return *const_cast<Node *>(_n); }
115 /**
116 * \brief Member access to the item the iterator points to.
117 * \return A pointer to the item in the node.
118 */
119 Node_type *operator -> () const { return const_cast<Node *>(_n); }
120 /**
121 * \brief Set the iterator to the next element (pre increment).
122 */
123 __Bst_iter &operator ++ () { inc(); return *this; }
124 /**
125 * \brief Set the iterator to the next element (post increment).
126 */
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
_downmost()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>
inc()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 }}
189