Debian Codegraph @

include/deal.II/base/iterator_range.h

raw
1 // ------------------------------------------------------------------------
2 //
3 // SPDX-License-Identifier: LGPL-2.1-or-later
4 // Copyright (C) 2014 - 2025 by the deal.II authors
5 //
6 // This file is part of the deal.II library.
7 //
8 // Part of the source code is dual licensed under Apache-2.0 WITH
9 // LLVM-exception OR LGPL-2.1-or-later. Detailed license information
10 // governing the source code and code contributions can be found in
11 // LICENSE.md and CONTRIBUTING.md at the top level directory of deal.II.
12 //
13 // ------------------------------------------------------------------------
14
15 #ifndef dealii_iterator_range_h
16 #define dealii_iterator_range_h
17
18
19 #include <deal.II/base/config.h>
20
21 #include <deal.II/base/std_cxx20/type_traits.h>
22 #include <deal.II/base/template_constraints.h>
23
24 #include <iterator>
25
26 DEAL_II_NAMESPACE_OPEN
27
28
29 // Forward declaration
30 #ifndef DOXYGEN
31 template <typename Iterator>
32 class IteratorOverIterators;
33 #endif
34
35
36 /**
37 * A class that is used to denote a collection of iterators that can be
38 * expressed in terms of a range of iterators characterized by a begin and an
39 * end iterator. As is common in C++, these ranges are specified as half open
40 * intervals defined by a begin iterator and a one-past-the-end iterator.
41 *
42 * The purpose of this class is so that classes such as Triangulation and
43 * DoFHandler can return ranges of cell iterators using an object of the
44 * current type from functions such as
45 * Triangulation::cell_iterators() and that such an
46 * object can then be used in a range-based for loop as supported by C++11,
47 * see also
48 * @ref CPP11 "C++11 standard".
49 *
50 * For example, such a loop could look like this if the goal is to set the
51 * user flag on every active cell:
52 * @code
53 * Triangulation<dim> triangulation;
54 * ...
55 * for (auto &cell : triangulation.active_cell_iterators())
56 * cell->set_user_flag();
57 * @endcode
58 * In other words, the <code>cell</code> objects are iterators, and the range
59 * object returned by Triangulation::active_cell_iterators() and similar
60 * functions are conceptually thought of as <i>collections of iterators</i>.
61 *
62 * Of course, the class may also be used to denote other iterator ranges using
63 * different kinds of iterators into other containers.
64 *
65 *
66 * <h3>Class design: Motivation</h3>
67 *
68 * Informally, the way the C++11 standard describes <a
69 * href="http://en.wikipedia.org/wiki/C%2B%2B11#Range-based_for_loop">range-based
70 * for loops</a> works as follows: A <i>range-based for loop</i> of the
71 * form
72 * @code
73 * Container c;
74 * for (auto v : c)
75 * statement;
76 * @endcode
77 * where <code>c</code> is a container or collection, is equivalent to the
78 * following loop:
79 * @code
80 * Container c;
81 * for (auto tmp=c.begin(); tmp!=c.end(); ++tmp)
82 * {
83 * auto v = *tmp;
84 * statement;
85 * }
86 * @endcode
87 * (The precise definition can be found here:
88 * https://en.cppreference.com/w/cpp/language/range-for .)
89 * In other words, the compiler introduces a temporary variable that
90 * <i>iterates</i> over the elements of the container or collection, and the
91 * original variable <code>v</code> that appeared in the range-based for loop
92 * represents the <i>dereferenced</i> state of these iterators -- namely,
93 * the <i>elements</i> of the collection.
94 *
95 * In the context of loops over cells, we typically want to retain the fact
96 * that the loop variable is an iterator, not a value. This is because in
97 * deal.II, we never actually use the <i>dereferenced state</i> of a cell
98 * iterator: conceptually, it would represent a cell, and technically it is
99 * implemented by classes such as CellAccessor and DoFCellAccessor, but these
100 * classes are never used explicitly. Consequently, what we would like is that
101 * a call such as Triangulation::active_cell_iterators() returns an object
102 * that represents a <i>collection of iterators</i> of the kind <code>{begin,
103 * begin+1, ..., end-1}</code>. This is conveniently expressed as the half
104 * open interval <code>[begin,end)</code>. The loop variable in the
105 * range-based for loop would then take on each of these iterators in turn.
106 *
107 *
108 * <h3>Class design: Implementation</h3>
109 *
110 * To represent the desired semantics as outlined above, this class stores a
111 * half-open range of iterators <code>[b,e)</code> of the given template type.
112 * Secondly, the class needs to provide begin() and end() functions in such a
113 * way that if you <i>dereference</i> the result of IteratorRange::begin(),
114 * you get the <code>b</code> iterator. Furthermore, you must be able to
115 * increment the object returned by IteratorRange::begin() so that
116 * <code>*(std::next(begin())) == b+1</code>. In other words,
117 * IteratorRange::begin() must return an iterator that when dereferenced returns
118 * an iterator of the template type <code>Iterator</code>: It is an iterator
119 * over iterators in the same sense as if you had a pointer into an array of
120 * pointers.
121 *
122 * This is implemented in the form of the IteratorRange::IteratorOverIterators
123 * class.
124 *
125 * @ingroup CPP11
126 */
127 template <typename Iterator>
128 class IteratorRange
129 {
130 public:
131 /**
132 * Typedef for the iterator type that iterates over other iterators.
133 */
134 using IteratorOverIterators = dealii::IteratorOverIterators<Iterator>;
135
136
137 /**
138 * Typedef for the iterator type represent by this class.
139 */
140 using iterator = Iterator;
141
142 /**
143 * Default constructor. Create a range represented by two default
144 * constructed iterators. This range is likely (depending on the type of the
145 * iterators) empty.
146 */
147 IteratorRange();
148
149 /**
150 * Constructor. Constructs a range given the begin and end iterators.
151 *
152 * @param[in] begin An iterator pointing to the first element of the range
153 * @param[in] end An iterator pointing past the last element represented
154 * by this range.
155 */
156 IteratorRange(const iterator begin, const iterator end);
157
158 /**
159 * Return the iterator pointing to the first element of this range.
160 */
161 IteratorOverIterators
162 begin();
163
164 /**
165 * Return the iterator pointing to the first element of this range.
166 */
167 IteratorOverIterators
168 begin() const;
169
170 /**
171 * Return the iterator pointing to the element past the last element of this
172 * range.
173 */
174 IteratorOverIterators
175 end() const;
176
177 /**
178 * Return the iterator pointing to the element past the last element of this
179 * range.
180 */
181 IteratorOverIterators
182 end();
183
184 private:
185 /**
186 * Iterators characterizing the begin and end of the range.
187 */
188 const IteratorOverIterators it_begin;
189 const IteratorOverIterators it_end;
190 };
191
192
193
194 /**
195 * A class that implements the semantics of iterators over iterators as
196 * discussed in the design sections of the IteratorRange class.
197 */
198 template <typename Iterator>
199 class IteratorOverIterators
200 {
201 public:
202 /**
203 * Typedef the elements of the collection to give them a name that is more
204 * distinct.
205 */
206 using BaseIterator = Iterator;
207
208 /**
209 * Constructor. Initialize this iterator-over-iterator in such a way that
210 * it points to the given argument.
211 *
212 * @param iterator An iterator to which this object is supposed to point.
213 */
214 explicit IteratorOverIterators(const BaseIterator &iterator);
215
216 /**
217 * Dereferencing operator.
218 * @return The iterator within the collection currently pointed to.
219 */
220 const BaseIterator &
221 operator*() const;
222
223 /**
224 * Dereferencing operator.
225 * @return The iterator within the collection currently pointed to.
226 */
227 const BaseIterator *
228 operator->() const;
229
230 /**
231 * Prefix increment operator. Move the current iterator to the next
232 * element of the collection and return the new value.
233 */
234 IteratorOverIterators &
235 operator++();
236
237 /**
238 * Postfix increment operator. Move the current iterator to the next
239 * element of the collection, but return the previous value of the
240 * iterator.
241 */
242 IteratorOverIterators
243 operator++(int);
244
245 /**
246 * Comparison operator
247 * @param i_o_i Another iterator over iterators.
248 * @return Returns whether the current iterator points to a different
249 * object than the iterator represented by the argument.
250 */
251 bool
252 operator!=(const IteratorOverIterators &i_o_i) const;
253
254 /**
255 * Implicit conversion operator.
256 *
257 * @warning When you call this conversion operator (i.e., you convert this
258 * iterator-over-iterators to the iterator we are currently pointing to),
259 * you obtain a `const` reference to this underlying iterator. The only
260 * thing you can really do with this result is dereferencing itself: it
261 * presumably points to something useful, but since you don't know where
262 * the pointed to object lives, you shouldn't increment or decrement the
263 * iterator you get from this operator. As a consequence, the returned
264 * iterator is marked as `const`, as this should prevent you from doing
265 * anything other than dereference it.
266 */
267 operator const BaseIterator &() const;
268
269 /**
270 * Mark the class as forward iterator and declare some alias which are
271 * standard for iterators and are used by algorithms to enquire about the
272 * specifics of the iterators they work on.
273 */
274 using iterator_category = std::forward_iterator_tag;
275 using value_type = Iterator;
276 using difference_type = typename Iterator::difference_type;
277 using pointer = Iterator *;
278 using reference = Iterator &;
279
280 private:
281 /**
282 * The object this iterator currently points to.
283 */
284 BaseIterator element_of_iterator_collection;
285 };
286
287
288
289 /**
290 * Create an object of type IteratorRange given the beginning and
291 * end iterator.
292 */
293 template <typename BaseIterator>
294 IteratorRange<BaseIterator>
295 make_iterator_range(const BaseIterator &begin,
296 const std_cxx20::type_identity_t<BaseIterator> &end)
297 {
298 IteratorRange<BaseIterator> ir(begin, end);
299 return ir;
300 }
301
302
303 // ------------------- template member functions
304
305
306 template <typename Iterator>
307 inline IteratorOverIterators<Iterator>::IteratorOverIterators(
308 const BaseIterator &iterator)
309 : element_of_iterator_collection(iterator)
310 {}
311
312
313
314 template <typename Iterator>
315 inline const typename IteratorOverIterators<Iterator>::BaseIterator &
316 IteratorOverIterators<Iterator>::operator*() const
317 {
318 return element_of_iterator_collection;
319 }
320
321
322
323 template <typename Iterator>
324 inline const typename IteratorOverIterators<Iterator>::BaseIterator *
325 IteratorOverIterators<Iterator>::operator->() const
326 {
327 return &element_of_iterator_collection;
328 }
329
330
331
332 template <typename Iterator>
333 inline IteratorOverIterators<Iterator> &
334 IteratorOverIterators<Iterator>::operator++()
335 {
336 ++element_of_iterator_collection;
337 return *this;
338 }
339
340
341
342 template <typename Iterator>
343 inline IteratorOverIterators<Iterator>
344 IteratorOverIterators<Iterator>::operator++(int)
345 {
346 const IteratorOverIterators old_value = *this;
347 ++element_of_iterator_collection;
348 return *old_value;
349 }
350
351
352
353 template <typename Iterator>
354 inline bool
355 IteratorOverIterators<Iterator>::operator!=(
356 const IteratorOverIterators &i_o_i) const
357 {
358 return element_of_iterator_collection != i_o_i.element_of_iterator_collection;
359 }
360
361
362
363 template <typename Iterator>
364 inline IteratorOverIterators<Iterator>::operator const BaseIterator &() const
365 {
366 return element_of_iterator_collection;
367 }
368
369
370
371 template <typename Iterator>
372 inline IteratorRange<Iterator>::IteratorRange()
373 : it_begin()
374 , it_end()
375 {}
376
377
378
379 template <typename Iterator>
380 inline IteratorRange<Iterator>::IteratorRange(const iterator b,
381 const iterator e)
382 : it_begin(b)
383 , it_end(e)
384 {}
385
386
387 template <typename Iterator>
388 inline typename IteratorRange<Iterator>::IteratorOverIterators
389 IteratorRange<Iterator>::begin()
390 {
391 return it_begin;
392 }
393
394
395 template <typename Iterator>
396 inline typename IteratorRange<Iterator>::IteratorOverIterators
397 IteratorRange<Iterator>::begin() const
398 {
399 return it_begin;
400 }
401
402
403 template <typename Iterator>
404 inline typename IteratorRange<Iterator>::IteratorOverIterators
405 IteratorRange<Iterator>::end()
406 {
407 return it_end;
408 }
409
410
411 template <typename Iterator>
412 inline typename IteratorRange<Iterator>::IteratorOverIterators
413 IteratorRange<Iterator>::end() const
414 {
415 return it_end;
416 }
417
418
419 DEAL_II_NAMESPACE_CLOSE
420
421 #endif