Debian Codegraph @

include/deal.II/base/linear_index_iterator.h

raw
1 // ------------------------------------------------------------------------
2 //
3 // SPDX-License-Identifier: LGPL-2.1-or-later
4 // Copyright (C) 2018 - 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_linear_index_iterator_h
16 #define dealii_linear_index_iterator_h
17
18 #include <deal.II/base/config.h>
19
20 #include <deal.II/base/exceptions.h>
21
22 #include <iterator>
23
24
25 DEAL_II_NAMESPACE_OPEN
26 /**
27 * Many classes in deal.II, such as FullMatrix, TransposeTable, and
28 * SparseMatrix, store their data in contiguous buffers (though the
29 * <em>interpretation</em> of what the elements of these buffers represent
30 * can, of course, be complex). For example, FullMatrix and TransposeTable
31 * store their data in row major and column major order respectively, whereas
32 * for SparseMatrix the mapping from buffer location to matrix entry
33 * $\mathbf{A}(i, j)$ is more complicated. In any case, however, the
34 * contiguous arrangements of elements enables random access iteration.
35 *
36 * LinearIndexIterator provides most of the functionality needed to write
37 * iterators for these classes. LinearIndexIterator is essentially a
38 * simplified version of <code>boost::iterator_facade</code> that assumes
39 * <code>AccessorType</code> provides certain members (documented below) that
40 * completely describe the state of the iterator. The intended use of this
41 * class is for containers to define their own accessor classes and then use
42 * the curiously recurring template pattern (CRTP) technique to define their
43 * iterators. For example, here is a container that uses LinearIndexIterator
44 * to define its own iterator classes:
45 *
46 * @code
47 * template <typename T>
48 * class Container
49 * {
50 * protected:
51 * // forward declaration for friendship
52 * template <bool Constness>
53 * class Iterator;
54 *
55 * template <bool Constness>
56 * class Accessor
57 * {
58 * public:
59 * // const iterators store a const pointer
60 * using container_pointer_type
61 * = std::conditional_t<Constness,
62 * const Container<T>*,
63 * Container<T>*>;
64 *
65 * // This alias is assumed to exist.
66 * using size_type = std::size_t;
67 *
68 * // constructor.
69 * Accessor(const container_pointer_type container,
70 * const std::ptrdiff_t index);
71 *
72 * // constructor.
73 * Accessor();
74 *
75 * // get a constant reference to the current value.
76 * const T& value() const;
77 *
78 * protected:
79 * container_pointer_type container;
80 * std::ptrdiff_t linear_index;
81 *
82 * // LinearIndexIterator needs access to linear_index and container.
83 * friend class LinearIndexIterator<Iterator<Constness>,
84 * Accessor<Constness>>;
85 * };
86 *
87 * template <bool Constness>
88 * class Iterator : public LinearIndexIterator<Iterator<Constness>,
89 * Accessor<Constness>>
90 * {
91 * // Constructor.
92 * Iterator(Container<T> * const container, const std::ptrdiff_t index);
93 *
94 * // implement additional constructors here, but all state should be
95 * // contained in the Accessor, which is a member of the base class.
96 * };
97 *
98 * public:
99 * using size_type = std::size_t;
100 * using const_iterator = Iterator<true>;
101 * using iterator = Iterator<false>;
102 *
103 * iterator begin ();
104 * iterator end ();
105 *
106 * const_iterator begin () const;
107 * const_iterator end () const;
108 * };
109 * @endcode
110 *
111 * @tparam DerivedIterator As shown in the example above, concrete iterator
112 * classes should use this class with the CRTP technique: this provides the
113 * boiler-plate comparison and arithmetic operators for iterators. This is
114 * necessary for, e.g., LinearIndexIterator::operator++() to return the
115 * correct type.
116 *
117 * @tparam AccessorType LinearIndexIterator assumes that the
118 * <code>AccessorType</code> template parameter has the following members
119 * which completely describe the current state of the iterator:
120 * <ol>
121 * <li>A pointer named <code>container</code> to the original container (e.g.,
122 * the relevant SparseMatrix). This should be a <code>const</code> pointer
123 * for <code>const</code> iterators.</li>
124 * <li>An array index named <code>linear_index</code> that stores the current
125 * position in the container's storage buffer. <code>linear_index</code> does
126 * not need to be an integer: it could be a class type (convertible to the
127 * correct index type of the container) that implements
128 * <code>operator+=</code>, <code>operator&lt;</code>, and
129 * <code>operator==</code>. For example, one could implement a strided
130 * iterator by implementing <code>operator+=</code> and
131 * <code>operator-</code> with multiplicative factors.</li>
132 * </ol>
133 * In addition, <code>AccessorType</code> should declare the relevant
134 * LinearIndexIterator instantiation to be a <code>friend</code> and define a
135 * <code>size_type</code> type.
136 *
137 * @note TransposeTable uses this template to implement its iterators.
138 */
139 template <typename DerivedIterator, typename AccessorType>
140 class LinearIndexIterator
141 {
142 public:
143 /**
144 * Iterator category.
145 */
146 #ifdef DEAL_II_HAVE_CXX20
147 using iterator_category = std::contiguous_iterator_tag;
148 #else
149 using iterator_category = std::random_access_iterator_tag;
150 #endif
151
152 /**
153 * An alias for the type you get when you dereference an iterator of the
154 * current kind.
155 */
156 using value_type = AccessorType;
157
158 /**
159 * Difference type.
160 */
161 using difference_type = std::ptrdiff_t;
162
163 /**
164 * Reference type.
165 */
166 using reference = const value_type &;
167
168 /**
169 * Pointer type.
170 */
171 using pointer = const value_type *;
172
173 /**
174 * Size type used by the underlying container.
175 */
176 using size_type = typename value_type::size_type;
177
178 /**
179 * Copy operator.
180 */
181 DerivedIterator &
182 operator=(const DerivedIterator &it);
183
184 /**
185 * Prefix increment.
186 */
187 DerivedIterator &
188 operator++();
189
190 /**
191 * Postfix increment.
192 */
193 DerivedIterator
194 operator++(int);
195
196 /**
197 * Prefix decrement.
198 */
199 DerivedIterator &
200 operator--();
201
202 /**
203 * Postfix decrement.
204 */
205 DerivedIterator
206 operator--(int);
207
208 /**
209 * Return an iterator that is @p n entries ahead of the current one.
210 */
211 DerivedIterator
212 operator+(const difference_type n) const;
213
214 /**
215 * Return an iterator that is @p n entries behind the current one.
216 */
217 DerivedIterator
218 operator-(const difference_type n) const;
219
220 /**
221 * Increment the iterator position by @p n.
222 */
223 DerivedIterator &
224 operator+=(const difference_type n);
225
226 /**
227 * Decrement the iterator position by @p n.
228 */
229 DerivedIterator &
230 operator-=(const difference_type n);
231
232 /**
233 * Return the distance between the current iterator and the argument. The
234 * distance is given by how many times one has to apply operator++() to the
235 * current iterator to get the argument (for a positive return value), or
236 * operator--() (for a negative return value).
237 */
238 difference_type
239 operator-(const DerivedIterator &p) const;
240
241 /**
242 * Dereferencing operator.
243 */
244 reference
245 operator*() const;
246
247 /**
248 * Dereferencing operator.
249 */
250 pointer
251 operator->() const;
252
253 /**
254 * Comparison operator. Returns <code>true</code> if both iterators point to
255 * the same entry in the same container.
256 */
257 template <typename OtherIterator>
258 std::enable_if_t<std::is_convertible_v<OtherIterator, DerivedIterator>, bool>
259 operator==(const OtherIterator &right) const
260 {
261 const auto &right_2 = static_cast<const DerivedIterator &>(right);
262 return this->accessor == right_2.accessor;
263 }
264
265 /**
266 * Opposite of operator==().
267 */
268 template <typename OtherIterator>
269 std::enable_if_t<std::is_convertible_v<OtherIterator, DerivedIterator>, bool>
270 operator!=(const OtherIterator &right) const
271 {
272 return !(*this == right);
273 }
274
275 /**
276 * Comparison operator: uses the same ordering as operator<(), but also
277 * checks for equality.
278 *
279 * This function is only valid if both iterators point into the same
280 * container.
281 */
282 bool
283 operator<=(const DerivedIterator &) const;
284
285 /**
286 * Comparison operator: uses the same ordering as operator>(), but also
287 * checks for equality.
288 *
289 * This function is only valid if both iterators point into the same
290 * container.
291 */
292 bool
293 operator>=(const DerivedIterator &) const;
294
295 /**
296 * Comparison operator. Result is true if either the first row number is
297 * smaller or if the row numbers are equal and the first index is smaller.
298 *
299 * This function is only valid if both iterators point into the same
300 * container.
301 */
302 bool
303 operator<(const DerivedIterator &) const;
304
305 /**
306 * Comparison operator. Works in the same way as operator<(), just the other
307 * way round.
308 */
309 bool
310 operator>(const DerivedIterator &) const;
311
312 protected:
313 /*
314 * The inheriting class should have a default constructor.
315 */
316 LinearIndexIterator() = default; // NOLINT
317
318 /**
319 * Constructor that copies an accessor.
320 */
321 LinearIndexIterator(const AccessorType accessor);
322
323 protected:
324 /**
325 * Store an object of the accessor class.
326 */
327 AccessorType accessor;
328 };
329
330
331
332 template <typename DerivedIterator, typename AccessorType>
333 inline DerivedIterator &
334 LinearIndexIterator<DerivedIterator, AccessorType>::operator=(
335 const DerivedIterator &it)
336 {
337 accessor.container = it.container;
338 accessor.linear_index = it.linear_index;
339 return static_cast<DerivedIterator &>(*this);
340 }
341
342
343
344 template <typename DerivedIterator, typename AccessorType>
345 inline DerivedIterator &
346 LinearIndexIterator<DerivedIterator, AccessorType>::operator++()
347 {
348 return operator+=(1);
349 }
350
351
352
353 template <typename DerivedIterator, typename AccessorType>
354 inline DerivedIterator
355 LinearIndexIterator<DerivedIterator, AccessorType>::operator++(int)
356 {
357 const DerivedIterator copy(this->accessor);
358 operator+=(1);
359 return copy;
360 }
361
362
363
364 template <typename DerivedIterator, typename AccessorType>
365 inline DerivedIterator &
366 LinearIndexIterator<DerivedIterator, AccessorType>::operator--()
367 {
368 return operator+=(-1);
369 }
370
371
372
373 template <typename DerivedIterator, typename AccessorType>
374 inline DerivedIterator
375 LinearIndexIterator<DerivedIterator, AccessorType>::operator--(int)
376 {
377 const DerivedIterator copy(this->accessor);
378 operator+=(-1);
379 return copy;
380 }
381
382
383
384 template <typename DerivedIterator, typename AccessorType>
385 inline DerivedIterator
386 LinearIndexIterator<DerivedIterator, AccessorType>::operator+(
387 const difference_type n) const
388 {
389 DerivedIterator copy(this->accessor);
390 copy += n;
391 return copy;
392 }
393
394
395
396 template <typename DerivedIterator, typename AccessorType>
397 inline DerivedIterator
398 LinearIndexIterator<DerivedIterator, AccessorType>::operator-(
399 const difference_type n) const
400 {
401 DerivedIterator copy(this->accessor);
402 copy += -n;
403 return copy;
404 }
405
406
407
408 template <typename DerivedIterator, typename AccessorType>
409 inline DerivedIterator &
410 LinearIndexIterator<DerivedIterator, AccessorType>::operator+=(
411 const difference_type n)
412 {
413 accessor.linear_index += n;
414 return static_cast<DerivedIterator &>(*this);
415 }
416
417
418
419 template <typename DerivedIterator, typename AccessorType>
420 inline DerivedIterator &
421 LinearIndexIterator<DerivedIterator, AccessorType>::operator-=(
422 const difference_type n)
423 {
424 return operator+=(-n);
425 }
426
427
428
429 template <typename DerivedIterator, typename AccessorType>
430 inline
431 typename LinearIndexIterator<DerivedIterator, AccessorType>::difference_type
432 LinearIndexIterator<DerivedIterator, AccessorType>::operator-(
433 const DerivedIterator &other) const
434 {
435 Assert(this->accessor.container == other.accessor.container,
436 ExcMessage(
437 "Only iterators pointing to the same container can be compared."));
438 return this->accessor.linear_index - other.accessor.linear_index;
439 }
440
441
442
443 template <typename DerivedIterator, typename AccessorType>
444 inline typename LinearIndexIterator<DerivedIterator, AccessorType>::reference
445 LinearIndexIterator<DerivedIterator, AccessorType>::operator*() const
446 {
447 return accessor;
448 }
449
450
451
452 template <typename DerivedIterator, typename AccessorType>
453 inline typename LinearIndexIterator<DerivedIterator, AccessorType>::pointer
454 LinearIndexIterator<DerivedIterator, AccessorType>::operator->() const
455 {
456 return &accessor;
457 }
458
459
460
461 template <typename DerivedIterator, typename AccessorType>
462 inline bool
463 LinearIndexIterator<DerivedIterator, AccessorType>::operator<=(
464 const DerivedIterator &other) const
465 {
466 return (*this == other) || (*this < other);
467 }
468
469
470
471 template <typename DerivedIterator, typename AccessorType>
472 inline bool
473 LinearIndexIterator<DerivedIterator, AccessorType>::operator>=(
474 const DerivedIterator &other) const
475 {
476 return !(*this < other);
477 }
478
479
480
481 template <typename DerivedIterator, typename AccessorType>
482 inline bool
483 LinearIndexIterator<DerivedIterator, AccessorType>::operator<(
484 const DerivedIterator &other) const
485 {
486 Assert(this->accessor.container == other.accessor.container,
487 ExcMessage(
488 "Only iterators pointing to the same container can be compared."));
489 return this->accessor.linear_index < other.accessor.linear_index;
490 }
491
492
493
494 template <typename DerivedIterator, typename AccessorType>
495 inline bool
496 LinearIndexIterator<DerivedIterator, AccessorType>::operator>(
497 const DerivedIterator &other) const
498 {
499 return other < static_cast<const DerivedIterator &>(*this);
500 }
501
502
503
504 template <typename DerivedIterator, typename AccessorType>
505 inline LinearIndexIterator<DerivedIterator, AccessorType>::LinearIndexIterator(
506 const AccessorType accessor)
507 : accessor(accessor)
508 {}
509
510
511 DEAL_II_NAMESPACE_CLOSE
512
513 #endif