DUNE-FEM (unstable)

rangeutilities.hh
Go to the documentation of this file.
1// -*- tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 2 -*-
2// vi: set et ts=4 sw=2 sts=2:
3// SPDX-FileCopyrightInfo: Copyright © DUNE Project contributors, see file LICENSE.md in module root
4// SPDX-License-Identifier: LicenseRef-GPL-2.0-only-with-DUNE-exception
5#ifndef DUNE_COMMON_RANGE_UTILITIES_HH
6#define DUNE_COMMON_RANGE_UTILITIES_HH
7
8#include <algorithm>
9#include <utility>
10#include <type_traits>
11#include <bitset>
12
15
23namespace Dune
24{
25
36 template <typename T,
37 typename std::enable_if<IsIterable<T>::value, int>::type = 0>
38 typename T::value_type
39 max_value(const T & v) {
40 using std::max_element;
41 return *max_element(v.begin(), v.end());
42 }
43
44 template <typename T,
45 typename std::enable_if<!IsIterable<T>::value, int>::type = 0>
46 const T & max_value(const T & v) { return v; }
47
53 template <typename T,
54 typename std::enable_if<IsIterable<T>::value, int>::type = 0>
55 typename T::value_type
56 min_value(const T & v) {
57 using std::min_element;
58 return *min_element(v.begin(), v.end());
59 }
60
61 template <typename T,
62 typename std::enable_if<!IsIterable<T>::value, int>::type = 0>
63 const T & min_value(const T & v) { return v; }
64
70 template <typename T,
71 typename std::enable_if<IsIterable<T>::value, int>::type = 0>
72 bool any_true(const T & v) {
73 bool b = false;
74 for (const auto & e : v)
75 b = b or bool(e);
76 return b;
77 }
78
79 template <typename T,
80 typename std::enable_if<!IsIterable<T>::value, int>::type = 0>
81 bool any_true(const T & v) { return v; }
82
83 template<std::size_t N>
84 bool any_true(const std::bitset<N> & b)
85 {
86 return b.any();
87 }
88
94 template <typename T,
95 typename std::enable_if<IsIterable<T>::value, int>::type = 0>
96 bool all_true(const T & v) {
97 bool b = true;
98 for (const auto & e : v)
99 b = b and bool(e);
100 return b;
101 }
102
103 template <typename T,
104 typename std::enable_if<!IsIterable<T>::value, int>::type = 0>
105 bool all_true(const T & v) { return v; }
106
107 template<std::size_t N>
108 bool all_true(const std::bitset<N> & b)
109 {
110 return b.all();
111 }
112
113
114
115 namespace Impl
116 {
117
118 template <class T>
119 class IntegralRangeIterator
120 {
121 public:
122 typedef std::random_access_iterator_tag iterator_category;
123 typedef T value_type;
124 typedef std::make_signed_t<T> difference_type;
125 typedef const T *pointer;
126 typedef T reference;
127
128 constexpr IntegralRangeIterator() noexcept : value_(0) {}
129 constexpr explicit IntegralRangeIterator(value_type value) noexcept : value_(value) {}
130
131 pointer operator->() const noexcept { return &value_; }
132 constexpr reference operator*() const noexcept { return value_; }
133
134 constexpr reference operator[]( difference_type n ) const noexcept { return (value_ + n); }
135
136 constexpr bool operator==(const IntegralRangeIterator & other) const noexcept { return (value_ == other.value_); }
137 constexpr bool operator!=(const IntegralRangeIterator & other) const noexcept { return (value_ != other.value_); }
138
139 constexpr bool operator<(const IntegralRangeIterator & other) const noexcept { return (value_ <= other.value_); }
140 constexpr bool operator<=(const IntegralRangeIterator & other) const noexcept { return (value_ <= other.value_); }
141 constexpr bool operator>(const IntegralRangeIterator & other) const noexcept { return (value_ >= other.value_); }
142 constexpr bool operator>=(const IntegralRangeIterator & other) const noexcept { return (value_ >= other.value_); }
143
144 IntegralRangeIterator& operator++() noexcept { ++value_; return *this; }
145 IntegralRangeIterator operator++(int) noexcept { IntegralRangeIterator copy( *this ); ++(*this); return copy; }
146
147 IntegralRangeIterator& operator--() noexcept { --value_; return *this; }
148 IntegralRangeIterator operator--(int) noexcept { IntegralRangeIterator copy( *this ); --(*this); return copy; }
149
150 IntegralRangeIterator& operator+=(difference_type n) noexcept { value_ += n; return *this; }
151 IntegralRangeIterator& operator-=(difference_type n) noexcept { value_ -= n; return *this; }
152
153 friend constexpr IntegralRangeIterator operator+(const IntegralRangeIterator &a, difference_type n) noexcept { return IntegralRangeIterator(a.value_ + n); }
154 friend constexpr IntegralRangeIterator operator+(difference_type n, const IntegralRangeIterator &a) noexcept { return IntegralRangeIterator(a.value_ + n); }
155 friend constexpr IntegralRangeIterator operator-(const IntegralRangeIterator &a, difference_type n) noexcept { return IntegralRangeIterator(a.value_ - n); }
156
157 constexpr difference_type operator-(const IntegralRangeIterator &other) const noexcept { return (static_cast<difference_type>(value_) - static_cast<difference_type>(other.value_)); }
158
159 private:
160 value_type value_;
161 };
162
163 } // namespace Impl
164
165
166
175 template <class T>
177 {
178 public:
180 typedef T value_type;
182 typedef Impl::IntegralRangeIterator<T> iterator;
184 typedef std::make_unsigned_t<T> size_type;
185
187 constexpr IntegralRange(value_type from, value_type to) noexcept : from_(from), to_(to) {}
189 constexpr explicit IntegralRange(value_type to) noexcept : from_(0), to_(to) {}
191 constexpr IntegralRange(std::pair<value_type, value_type> range) noexcept : from_(range.first), to_(range.second) {}
192
194 constexpr iterator begin() const noexcept { return iterator(from_); }
196 constexpr iterator end() const noexcept { return iterator(to_); }
197
199 constexpr value_type operator[](const value_type &i) const noexcept { return (from_ + i); }
200
202 constexpr bool empty() const noexcept { return (from_ == to_); }
204 constexpr size_type size() const noexcept { return (static_cast<size_type>(to_) - static_cast<size_type>(from_)); }
205
207 constexpr bool contains(value_type index) const noexcept { return from_ <= index && index < to_; }
208
209 private:
210 value_type from_, to_;
211 };
212
213
228 template <class T, T to, T from = 0>
230 {
231 template <T ofs, T... i>
232 static std::integer_sequence<T, (i+ofs)...> shift_integer_sequence(std::integer_sequence<T, i...>);
233
234 public:
236 typedef T value_type;
238 typedef Impl::IntegralRangeIterator<T> iterator;
240 typedef std::make_unsigned_t<T> size_type;
241
243 typedef decltype(shift_integer_sequence<from>(std::make_integer_sequence<T, to-from>())) integer_sequence;
244
246 constexpr StaticIntegralRange() noexcept = default;
247
249 constexpr operator IntegralRange<T>() const noexcept { return {from, to}; }
251 constexpr operator integer_sequence() const noexcept { return {}; }
252
254 static constexpr integer_sequence to_integer_sequence() noexcept { return {}; }
255
257 static constexpr iterator begin() noexcept { return iterator(from); }
259 static constexpr iterator end() noexcept { return iterator(to); }
260
262 template <class U, U i>
263 constexpr auto operator[](const std::integral_constant<U, i> &) const noexcept
264 -> std::integral_constant<value_type, from + static_cast<value_type>(i)>
265 {
266 return {};
267 }
268
270 constexpr value_type operator[](const size_type &i) const noexcept { return (from + static_cast<value_type>(i)); }
271
273 static constexpr std::integral_constant<bool, from == to> empty() noexcept { return {}; }
275 static constexpr std::integral_constant<size_type, static_cast<size_type>(to) - static_cast<size_type>(from) > size() noexcept { return {}; }
276
278 static constexpr bool contains(value_type index) noexcept { return from <= index && index < to; }
279
280 };
281
291 template<class T, class U,
292 std::enable_if_t<std::is_same<std::decay_t<T>, std::decay_t<U>>::value, int> = 0,
293 std::enable_if_t<std::is_integral<std::decay_t<T>>::value, int> = 0>
294 inline static IntegralRange<std::decay_t<T>> range(T &&from, U &&to) noexcept
295 {
296 return IntegralRange<std::decay_t<T>>(std::forward<T>(from), std::forward<U>(to));
297 }
298
299 template<class T, std::enable_if_t<std::is_integral<std::decay_t<T>>::value, int> = 0>
300 inline static IntegralRange<std::decay_t<T>> range(T &&to) noexcept
301 {
302 return IntegralRange<std::decay_t<T>>(std::forward<T>(to));
303 }
304
305 template<class T, std::enable_if_t<std::is_enum<std::decay_t<T>>::value, int> = 0>
306 inline static IntegralRange<std::underlying_type_t<std::decay_t<T>>> range(T &&to) noexcept
307 {
308 return IntegralRange<std::underlying_type_t<std::decay_t<T>>>(std::forward<T>(to));
309 }
310
311 template<class T, T from, T to>
312 inline static StaticIntegralRange<T, to, from> range(std::integral_constant<T, from>, std::integral_constant<T, to>) noexcept
313 {
314 return {};
315 }
316
317 template<class T, T to>
318 inline static StaticIntegralRange<T, to> range(std::integral_constant<T, to>) noexcept
319 {
320 return {};
321 }
322
323
324
329
334
335 namespace Impl
336 {
337
338
339
340 // An iterator transforming a wrapped iterator using
341 // an unary function. It inherits the iterator-category
342 // of the underlying iterator.
343 //
344 // \tparam I Type of the underlying iterator
345 // \tparam F Type of transformation function that can either be applied directly or after dereferencing
346 // \tparam TT Type of transformation (ValueTransformationTag or IteratorTransformationTag)
347 // \tparam C An iterator category tag, defaults to the one of I
348 template <class I, class F, class TT, class C = typename std::iterator_traits<I>::iterator_category>
349 class TransformedRangeIterator;
350
351 template<class I, class F, class TT, class C>
352 struct TransformationRangeIteratorTraits
353 {
354 template<class FF>
355 static decltype(auto) transform(FF&& f, const I& it) {
356 if constexpr (std::is_same_v<TT,IteratorTransformationTag>)
357 {
358 if constexpr (Dune::IsCallable<FF(const I&)>::value)
359 return f(it);
360 else
361 return (*f)(it);
362 }
363 else
364 {
365 if constexpr (Dune::IsCallable<FF(decltype(*it))>::value)
366 return f(*it);
367 else
368 return (*f)(*it);
369 }
370 }
371
372 using reference = decltype(transform(std::declval<F>(), std::declval<I>()));
373 using value_type = Dune::AutonomousValue<reference>;
374 using pointer = std::conditional_t<std::is_lvalue_reference_v<reference>, value_type*, ProxyArrowResult<reference>>;
375 using difference_type = typename std::iterator_traits<I>::difference_type;
376 using Facade = Dune::IteratorFacade<TransformedRangeIterator<I,F,TT,C>, C, value_type, reference, pointer, difference_type>;
377 };
378
379
380 template <class I, class F, class TT, class C>
381 class TransformedRangeIterator :
382 public TransformationRangeIteratorTraits<I,F, TT, C>::Facade
383 {
384 using Traits = TransformationRangeIteratorTraits<I,F, TT, C>;
385 using Facade = typename Traits::Facade;
386
387 static constexpr bool isBidirectional = std::is_convertible_v<C, std::bidirectional_iterator_tag>;
388 static constexpr bool isRandomAccess = std::is_convertible_v<C, std::random_access_iterator_tag>;
389
390 public:
391
392 using Function = F;
393 using reference = typename Facade::reference;
394 using difference_type = typename Facade::difference_type;
395
396 template<class II, class FF>
397 constexpr TransformedRangeIterator(II&& it, FF&& f) noexcept :
398 it_(std::forward<II>(it)),
399 f_(std::forward<FF>(f))
400 {}
401
402 template<class II,
403 disableCopyMove<TransformedRangeIterator,II> =0,
404 std::enable_if_t<std::is_convertible_v<II, I> and std::is_default_constructible_v<F>, int> =0>
405 constexpr TransformedRangeIterator(II&& it) noexcept :
406 it_(std::forward<II>(it)),
407 f_()
408 {}
409
410 template<class FF,
411 disableCopyMove<TransformedRangeIterator,FF> =0,
412 std::enable_if_t<std::is_convertible_v<FF, F> and std::is_default_constructible_v<I>, int> =0>
413 constexpr TransformedRangeIterator(FF&& f) noexcept :
414 it_(),
415 f_(std::forward<FF>(f))
416 {}
417
418 // Explicitly initialize members. Using a plain
419 //
420 // constexpr TransformedRangeIterator() noexcept {}
421 //
422 // would default-initialize the members while
423 //
424 // constexpr TransformedRangeIterator() noexcept : it_(), f_() {}
425 //
426 // leads to value-initialization. This is a case where
427 // both are really different. If it_ is a raw pointer (i.e. POD)
428 // then default-initialization leaves it uninitialized while
429 // value-initialization zero-initializes it.
430 constexpr TransformedRangeIterator() noexcept :
431 it_(),
432 f_()
433 {}
434
435 // Dereferencing returns a value created by the function
436 constexpr reference operator*() const noexcept {
437 return Traits::transform(f_, it_);
438 }
439
440 protected:
441
443
444 // Export base iterator, such that equalilty comparison,
445 // differences, and inequality comparisons are automatically
446 // forwarded to the base iterator by the facade.
447 const I& baseIterator() const noexcept {
448 return it_;
449 }
450
451 I& baseIterator() noexcept {
452 return it_;
453 }
454
455 I it_;
456 Function f_;
457 };
458
459 } // namespace Impl
460
461
462
499 template <class R, class F, class T=ValueTransformationTag>
501 {
502 using RawConstIterator = std::decay_t<decltype(std::declval<const R>().begin())>;
503 using RawIterator = std::decay_t<decltype(std::declval<R>().begin())>;
504
505 public:
506
513 using const_iterator = Impl::TransformedRangeIterator<RawConstIterator, const F*, T>;
514
521 using iterator = Impl::TransformedRangeIterator<RawIterator, F*, T>;
522
529 using RawRange = std::remove_reference_t<R>;
530
534 template<class RR, class FF>
535 constexpr TransformedRangeView(RR&& rawRange, FF&& f) noexcept :
536 rawRange_(std::forward<RR>(rawRange)),
537 f_(std::forward<FF>(f))
538 {
539 static_assert(std::is_same_v<T, ValueTransformationTag> or std::is_same_v<T, IteratorTransformationTag>,
540 "The TransformationType passed to TransformedRangeView has to be either ValueTransformationTag or IteratorTransformationTag.");
541 }
542
551 constexpr const_iterator begin() const noexcept {
552 return const_iterator(rawRange_.begin(), &f_);
553 }
554
555 constexpr iterator begin() noexcept {
556 return iterator(rawRange_.begin(), &f_);
557 }
558
567 constexpr const_iterator end() const noexcept {
568 return const_iterator(rawRange_.end(), &f_);
569 }
570
571 constexpr iterator end() noexcept {
572 return iterator(rawRange_.end(), &f_);
573 }
574
578 template<class It=const_iterator,
579 std::enable_if_t<std::is_same_v<typename It::iterator_category,std::random_access_iterator_tag>, int> = 0>
580 constexpr decltype(auto) operator[](std::size_t i) const noexcept
581 {
582 return this->begin()[i];
583 }
584
588 template<class It=iterator,
589 std::enable_if_t<std::is_same_v<typename It::iterator_category,std::random_access_iterator_tag>, int> = 0>
590 constexpr decltype(auto) operator[](std::size_t i) noexcept
591 {
592 return this->begin()[i];
593 }
594
605 template<class Range=R,
606 class = std::void_t<decltype(std::declval<const Range>().size())>>
607 auto size() const noexcept
608 {
609 return rawRange_.size();
610 }
611
615 constexpr bool empty() const noexcept
616 {
617 return rawRange_.begin() == rawRange_.end();
618 }
619
623 const RawRange& rawRange() const noexcept
624 {
625 return rawRange_;
626 }
627
631 RawRange& rawRange() noexcept
632 {
633 return rawRange_;
634 }
635
636 private:
637 R rawRange_;
638 F f_;
639 };
640
669 template <class R, class F>
670 auto transformedRangeView(R&& range, F&& f)
671 {
672 return TransformedRangeView<R, std::decay_t<F>, ValueTransformationTag>(std::forward<R>(range), std::forward<F>(f));
673 }
674
702 template <class R, class F>
703 auto iteratorTransformedRangeView(R&& range, F&& f)
704 {
705 return TransformedRangeView<R, std::decay_t<F>, IteratorTransformationTag>(std::forward<R>(range), std::forward<F>(f));
706 }
707
708
721 template<class Range>
722 auto sparseRange(Range&& range) {
723 return Dune::iteratorTransformedRangeView(std::forward<Range>(range), [](auto&& it) {
724 return std::tuple<decltype(*it), decltype(it.index())>(*it, it.index());
725 });
726 }
727
732}
733
734#endif // DUNE_COMMON_RANGE_UTILITIES_HH
dynamic integer range for use in range-based for loops
Definition: rangeutilities.hh:177
constexpr iterator begin() const noexcept
obtain a random-access iterator to the first element
Definition: rangeutilities.hh:194
constexpr iterator end() const noexcept
obtain a random-access iterator past the last element
Definition: rangeutilities.hh:196
std::make_unsigned_t< T > size_type
unsigned integer type corresponding to value_type
Definition: rangeutilities.hh:184
Impl::IntegralRangeIterator< T > iterator
type of iterator
Definition: rangeutilities.hh:182
constexpr value_type operator[](const value_type &i) const noexcept
access specified element
Definition: rangeutilities.hh:199
constexpr bool contains(value_type index) const noexcept
check whether given index is within range [from, to)
Definition: rangeutilities.hh:207
constexpr bool empty() const noexcept
check whether the range is empty
Definition: rangeutilities.hh:202
constexpr IntegralRange(std::pair< value_type, value_type > range) noexcept
construct integer range std::pair
Definition: rangeutilities.hh:191
constexpr IntegralRange(value_type from, value_type to) noexcept
construct integer range [from, to)
Definition: rangeutilities.hh:187
constexpr size_type size() const noexcept
obtain number of elements in the range
Definition: rangeutilities.hh:204
constexpr IntegralRange(value_type to) noexcept
construct integer range [0, to)
Definition: rangeutilities.hh:189
T value_type
type of integers contained in the range
Definition: rangeutilities.hh:180
CRTP-Mixing class for stl conformant iterators of given iterator category.
Definition: iteratorfacades.hh:1053
constexpr decltype(auto) operator*() const
Dereferencing operator.
Definition: iteratorfacades.hh:1119
static integer range for use in range-based for loops
Definition: rangeutilities.hh:230
static constexpr iterator end() noexcept
obtain a random-access iterator past the last element
Definition: rangeutilities.hh:259
decltype(shift_integer_sequence< from >(std::make_integer_sequence< T, to-from >())) integer_sequence
type of corresponding std::integer_sequence
Definition: rangeutilities.hh:243
static constexpr bool contains(value_type index) noexcept
check whether given index is within range [from, to)
Definition: rangeutilities.hh:278
constexpr StaticIntegralRange() noexcept=default
default constructor
std::make_unsigned_t< T > size_type
unsigned integer type corresponding to value_type
Definition: rangeutilities.hh:240
T value_type
type of integers contained in the range
Definition: rangeutilities.hh:236
constexpr auto operator[](const std::integral_constant< U, i > &) const noexcept -> std::integral_constant< value_type, from+static_cast< value_type >(i)>
access specified element (static version)
Definition: rangeutilities.hh:263
static constexpr std::integral_constant< bool, from==to > empty() noexcept
check whether the range is empty
Definition: rangeutilities.hh:273
static constexpr iterator begin() noexcept
obtain a random-access iterator to the first element
Definition: rangeutilities.hh:257
static constexpr integer_sequence to_integer_sequence() noexcept
return corresponding std::integer_sequence
Definition: rangeutilities.hh:254
constexpr value_type operator[](const size_type &i) const noexcept
access specified element (dynamic version)
Definition: rangeutilities.hh:270
Impl::IntegralRangeIterator< T > iterator
type of iterator
Definition: rangeutilities.hh:238
static constexpr std::integral_constant< size_type, static_cast< size_type >(to) - static_cast< size_type >(from) > size() noexcept
obtain number of elements in the range
Definition: rangeutilities.hh:275
A range transforming the values of another range on-the-fly.
Definition: rangeutilities.hh:501
Impl::TransformedRangeIterator< RawIterator, F *, T > iterator
Iterator type.
Definition: rangeutilities.hh:521
constexpr TransformedRangeView(RR &&rawRange, FF &&f) noexcept
Construct from range and function.
Definition: rangeutilities.hh:535
Impl::TransformedRangeIterator< RawConstIterator, const F *, T > const_iterator
Const iterator type.
Definition: rangeutilities.hh:513
std::remove_reference_t< R > RawRange
Export type of the wrapped untransformed range.
Definition: rangeutilities.hh:529
RawRange & rawRange() noexcept
Export the wrapped untransformed range.
Definition: rangeutilities.hh:631
const RawRange & rawRange() const noexcept
Export the wrapped untransformed range.
Definition: rangeutilities.hh:623
constexpr const_iterator begin() const noexcept
Obtain a iterator to the first element.
Definition: rangeutilities.hh:551
auto size() const noexcept
Obtain the size of the range.
Definition: rangeutilities.hh:607
constexpr const_iterator end() const noexcept
Obtain a iterator past the last element.
Definition: rangeutilities.hh:567
constexpr bool empty() const noexcept
Checks whether the range is empty.
Definition: rangeutilities.hh:615
typename AutonomousValueType< T >::type AutonomousValue
Type free of internal references that T can be converted to.
Definition: typetraits.hh:588
EnableIfInterOperable< T1, T2, bool >::type operator<(const RandomAccessIteratorFacade< T1, V1, R1, D > &lhs, const RandomAccessIteratorFacade< T2, V2, R2, D > &rhs)
Comparison operator.
Definition: iteratorfacades.hh:638
EnableIfInterOperable< T1, T2, bool >::type operator>(const RandomAccessIteratorFacade< T1, V1, R1, D > &lhs, const RandomAccessIteratorFacade< T2, V2, R2, D > &rhs)
Comparison operator.
Definition: iteratorfacades.hh:684
EnableIfInterOperable< T1, T2, bool >::type operator<=(const RandomAccessIteratorFacade< T1, V1, R1, D > &lhs, const RandomAccessIteratorFacade< T2, V2, R2, D > &rhs)
Comparison operator.
Definition: iteratorfacades.hh:661
EnableIfInterOperable< T1, T2, bool >::type operator==(const ForwardIteratorFacade< T1, V1, R1, D > &lhs, const ForwardIteratorFacade< T2, V2, R2, D > &rhs)
Checks for equality.
Definition: iteratorfacades.hh:238
EnableIfInterOperable< T1, T2, bool >::type operator>=(const RandomAccessIteratorFacade< T1, V1, R1, D > &lhs, const RandomAccessIteratorFacade< T2, V2, R2, D > &rhs)
Comparison operator.
Definition: iteratorfacades.hh:706
EnableIfInterOperable< T1, T2, bool >::type operator!=(const ForwardIteratorFacade< T1, V1, R1, D > &lhs, const ForwardIteratorFacade< T2, V2, R2, D > &rhs)
Checks for inequality.
Definition: iteratorfacades.hh:260
auto iteratorTransformedRangeView(R &&range, F &&f)
Create a TransformedRangeView using an iterator transformation.
Definition: rangeutilities.hh:703
auto transformedRangeView(R &&range, F &&f)
Create a TransformedRangeView.
Definition: rangeutilities.hh:670
auto sparseRange(Range &&range)
Allow structured-binding for-loops for sparse iterators.
Definition: rangeutilities.hh:722
This file implements iterator facade classes for writing stl conformant iterators.
Dune namespace.
Definition: alignedallocator.hh:13
Check if a type is callable with ()-operator and given arguments.
Definition: typetraits.hh:162
This class encapsulates access of IteratorFacade.
Definition: iteratorfacades.hh:786
Tag to enable iterator based transformations in TransformedRangeView.
Definition: rangeutilities.hh:333
Tag to enable value based transformations in TransformedRangeView.
Definition: rangeutilities.hh:328
Traits for type conversions and type information.
Creative Commons License   |  Legal Statements / Impressum  |  Hosted by TU Dresden  |  generated with Hugo v0.111.3 (Nov 24, 23:30, 2024)