source: mainline/uspace/lib/cpp/include/internal/rbtree_iterators.hpp@ 4f22d0c3

lfn serial ticket/834-toolchain-update topic/msim-upgrade topic/simplify-dev-export
Last change on this file since 4f22d0c3 was 73e3791, checked in by Dzejrou <dzejrou@…>, 7 years ago

cpp: revamped rbtree so that it now stores equivalent keys in a list
  • Property mode set to 100644
File size: 10.4 KB
Line 
1/*
2 * Copyright (c) 2018 Jaroslav Jindrak
3 * All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
7 * are met:
8 *
9 * - Redistributions of source code must retain the above copyright
10 * notice, this list of conditions and the following disclaimer.
11 * - Redistributions in binary form must reproduce the above copyright
12 * notice, this list of conditions and the following disclaimer in the
13 * documentation and/or other materials provided with the distribution.
14 * - The name of the author may not be used to endorse or promote products
15 * derived from this software without specific prior written permission.
16 *
17 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
18 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
19 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
20 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
21 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
22 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
23 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
24 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
26 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27 */
28
29#ifndef LIBCPP_INTERNAL_RBTREE_ITERATORS
30#define LIBCPP_INTERNAL_RBTREE_ITERATORS
31
32#include <internal/iterator.hpp>
33#include <internal/rbtree_node.hpp>
34#include <iterator>
35
36namespace std::aux
37{
38 /**
39 * Note: In order for these iterators to be reversible,
40 * the end state of an iterator is represented by a flag
41 * which can be set from true to false in operator--
42 * (i.e. decrementing end iterator) or set from false to
43 * true in operator++ (i.e. incrementing last before end
44 * iterator).
45 */
46
47 template<class Value, class Reference, class Pointer, class Size, class Node>
48 class rbtree_iterator
49 {
50 public:
51 using value_type = Value;
52 using size_type = Size;
53 using reference = Reference;
54 using pointer = Pointer;
55 using difference_type = ptrdiff_t;
56
57 using iterator_category = bidirectional_iterator_tag;
58
59 using node_type = Node;
60
61 rbtree_iterator(node_type* current = nullptr, bool end = true)
62 : current_{current}, end_{end}
63 { /* DUMMY BODY */ }
64
65 rbtree_iterator(const rbtree_iterator&) = default;
66 rbtree_iterator& operator=(const rbtree_iterator&) = default;
67
68 reference operator*() const
69 {
70 return current_->value;
71 }
72
73 pointer operator->() const
74 {
75 return &current_->value;
76 }
77
78 rbtree_iterator& operator++()
79 {
80 if (current_)
81 {
82 auto next = current_->successor();
83 if (next)
84 current_ = next;
85 else
86 end_ = true;
87 }
88
89 return *this;
90 }
91
92 rbtree_iterator operator++(int)
93 {
94 auto tmp = *this;
95 ++(*this);
96
97 return tmp;
98 }
99
100 rbtree_iterator& operator--()
101 {
102 if (end_)
103 {
104 try_undo_end_();
105
106 return *this;
107 }
108
109 if (current_)
110 {
111 auto next = current_->predecessor();
112 if (next)
113 current_ = next;
114 else
115 end_ = true;
116 }
117
118 return *this;
119 }
120
121 rbtree_iterator operator--(int)
122 {
123 auto tmp = *this;
124 --(*this);
125
126 return tmp;
127 }
128
129 const node_type* node() const
130 {
131 return current_;
132 }
133
134 node_type* node()
135 {
136 return current_;
137 }
138
139 bool end() const
140 {
141 return end_;
142 }
143
144 private:
145 node_type* current_;
146 bool end_;
147
148 void try_undo_end_()
149 {
150 if (!current_)
151 return;
152
153 /**
154 * We can do this if we are past end().
155 * This means we are the largest.
156 */
157 if (current_->find_largest() == current_)
158 end_ = false;
159 }
160 };
161
162 template<class Val, class Ref, class Ptr, class Sz, class N>
163 bool operator==(const rbtree_iterator<Val, Ref, Ptr, Sz, N>& lhs,
164 const rbtree_iterator<Val, Ref, Ptr, Sz, N>& rhs)
165 {
166 return (lhs.node() == rhs.node()) && (lhs.end() == rhs.end());
167 }
168
169 template<class Val, class Ref, class Ptr, class Sz, class N>
170 bool operator!=(const rbtree_iterator<Val, Ref, Ptr, Sz, N>& lhs,
171 const rbtree_iterator<Val, Ref, Ptr, Sz, N>& rhs)
172 {
173 return !(lhs == rhs);
174 }
175
176 template<class Value, class ConstReference, class ConstPointer, class Size, class Node>
177 class rbtree_const_iterator
178 {
179 using non_const_iterator_type = rbtree_iterator<
180 Value, get_non_const_ref_t<ConstReference>,
181 get_non_const_ptr_t<ConstPointer>, Size, Node
182 >;
183
184 public:
185 using value_type = Value;
186 using size_type = Size;
187 using const_reference = ConstReference;
188 using const_pointer = ConstPointer;
189 using difference_type = ptrdiff_t;
190
191 using iterator_category = bidirectional_iterator_tag;
192
193 using node_type = Node;
194
195 rbtree_const_iterator(const node_type* current = nullptr, bool end = true)
196 : current_{current}, end_{end}
197 { /* DUMMY BODY */ }
198
199 rbtree_const_iterator(const rbtree_const_iterator&) = default;
200 rbtree_const_iterator& operator=(const rbtree_const_iterator&) = default;
201
202 rbtree_const_iterator(const non_const_iterator_type& other)
203 : current_{other.node()}, end_{other.end()}
204 { /* DUMMY BODY */ }
205
206 rbtree_const_iterator& operator=(const non_const_iterator_type& other)
207 {
208 current_ = other.node();
209 end_ = other.end();
210
211 return *this;
212 }
213
214 const_reference operator*() const
215 {
216 return current_->value;
217 }
218
219 const_pointer operator->() const
220 {
221 return &current_->value;
222 }
223
224 rbtree_const_iterator& operator++()
225 {
226 if (current_)
227 {
228 auto next = current_->successor();
229 if (next)
230 current_ = next;
231 else
232 end_ = true;
233 }
234
235 return *this;
236 }
237
238 rbtree_const_iterator operator++(int)
239 {
240 auto tmp = *this;
241 ++(*this);
242
243 return tmp;
244 }
245
246 rbtree_const_iterator& operator--()
247 {
248 if (end_)
249 {
250 try_undo_end_();
251
252 return *this;
253 }
254
255 if (current_)
256 {
257 auto next = current_->predecessor();
258 if (next)
259 current_ = next;
260 else
261 end_ = true;
262 }
263
264 return *this;
265 }
266
267 rbtree_const_iterator operator--(int)
268 {
269 auto tmp = *this;
270 --(*this);
271
272 return tmp;
273 }
274
275 const node_type* node() const
276 {
277 return current_;
278 }
279
280 bool end() const
281 {
282 return end_;
283 }
284
285 private:
286 const node_type* current_;
287 bool end_;
288
289 void try_undo_end_()
290 {
291 if (!current_)
292 return;
293
294 /**
295 * We can do this if we are past end().
296 * This means we are the largest.
297 */
298 if (current_->find_largest() == current_)
299 end_ = false;
300 }
301 };
302
303 template<class Val, class CRef, class CPtr, class Sz, class N>
304 bool operator==(const rbtree_const_iterator<Val, CRef, CPtr, Sz, N>& lhs,
305 const rbtree_const_iterator<Val, CRef, CPtr, Sz, N>& rhs)
306 {
307 return (lhs.node() == rhs.node()) && (lhs.end() == rhs.end());
308 }
309
310 template<class Val, class CRef, class CPtr, class Sz, class N>
311 bool operator!=(const rbtree_const_iterator<Val, CRef, CPtr, Sz, N>& lhs,
312 const rbtree_const_iterator<Val, CRef, CPtr, Sz, N>& rhs)
313 {
314 return !(lhs == rhs);
315 }
316
317 template<class Val, class Ref, class Ptr, class CRef, class CPtr, class Sz, class N>
318 bool operator==(const rbtree_iterator<Val, Ref, Ptr, Sz, N>& lhs,
319 const rbtree_const_iterator<Val, CRef, CPtr, Sz, N>& rhs)
320 {
321 return (lhs.node() == rhs.node()) && (lhs.end() == rhs.end());
322 }
323
324 template<class Val, class Ref, class Ptr, class CRef, class CPtr, class Sz, class N>
325 bool operator!=(const rbtree_iterator<Val, Ref, Ptr, Sz, N>& lhs,
326 const rbtree_const_iterator<Val, CRef, CPtr, Sz, N>& rhs)
327 {
328 return !(lhs == rhs);
329 }
330
331 template<class Val, class CRef, class CPtr, class Ref, class Ptr, class Sz, class N>
332 bool operator==(const rbtree_const_iterator<Val, CRef, CPtr, Sz, N>& lhs,
333 const rbtree_iterator<Val, Ref, Ptr, Sz, N>& rhs)
334 {
335 return (lhs.node() == rhs.node()) && (lhs.end() == rhs.end());
336 }
337
338 template<class Val, class CRef, class CPtr, class Ref, class Ptr, class Sz, class N>
339 bool operator!=(const rbtree_const_iterator<Val, CRef, CPtr, Sz, N>& lhs,
340 const rbtree_iterator<Val, Ref, Ptr, Sz, N>& rhs)
341 {
342 return !(lhs == rhs);
343 }
344}
345
346#endif
Note: See TracBrowser for help on using the repository browser.