Loading...
Searching...
No Matches
rangeutilities.hh
Go to the documentation of this file.
// -*- tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 2 -*-
// vi: set et ts=4 sw=2 sts=2:
// SPDX-FileCopyrightInfo: Copyright © DUNE Project contributors, see file LICENSE.md in module root
// SPDX-License-Identifier: LicenseRef-GPL-2.0-only-with-DUNE-exception
#ifndef DUNE_COMMON_RANGE_UTILITIES_HH
#define DUNE_COMMON_RANGE_UTILITIES_HH
#include <algorithm>
#include <utility>
#include <type_traits>
#include <bitset>
#include <dune/common/typetraits.hh>
#include <dune/common/iteratorfacades.hh>
namespace Dune
{
template <typename T,
typename std::enable_if<IsIterable<T>::value, int>::type = 0>
typename T::value_type
max_value(const T & v) {
using std::max_element;
return *max_element(v.begin(), v.end());
}
template <typename T,
typename std::enable_if<!IsIterable<T>::value, int>::type = 0>
const T & max_value(const T & v) { return v; }
template <typename T,
typename std::enable_if<IsIterable<T>::value, int>::type = 0>
typename T::value_type
min_value(const T & v) {
using std::min_element;
return *min_element(v.begin(), v.end());
}
template <typename T,
typename std::enable_if<!IsIterable<T>::value, int>::type = 0>
const T & min_value(const T & v) { return v; }
template <typename T,
typename std::enable_if<IsIterable<T>::value, int>::type = 0>
bool any_true(const T & v) {
bool b = false;
for (const auto & e : v)
b = b or bool(e);
return b;
}
template <typename T,
typename std::enable_if<!IsIterable<T>::value, int>::type = 0>
bool any_true(const T & v) { return v; }
template<std::size_t N>
bool any_true(const std::bitset<N> & b)
{
return b.any();
}
template <typename T,
typename std::enable_if<IsIterable<T>::value, int>::type = 0>
bool all_true(const T & v) {
bool b = true;
for (const auto & e : v)
b = b and bool(e);
return b;
}
template <typename T,
typename std::enable_if<!IsIterable<T>::value, int>::type = 0>
bool all_true(const T & v) { return v; }
template<std::size_t N>
bool all_true(const std::bitset<N> & b)
{
return b.all();
}
namespace Impl
{
template <class T>
class IntegralRangeIterator
{
public:
typedef std::random_access_iterator_tag iterator_category;
typedef T value_type;
typedef std::make_signed_t<T> difference_type;
typedef const T *pointer;
typedef T reference;
constexpr IntegralRangeIterator() noexcept : value_(0) {}
constexpr explicit IntegralRangeIterator(value_type value) noexcept : value_(value) {}
pointer operator->() const noexcept { return &value_; }
constexpr reference operator*() const noexcept { return value_; }
constexpr reference operator[]( difference_type n ) const noexcept { return (value_ + n); }
constexpr auto operator<=>(const IntegralRangeIterator & other) const noexcept = default;
IntegralRangeIterator& operator++() noexcept { ++value_; return *this; }
IntegralRangeIterator operator++(int) noexcept { IntegralRangeIterator copy( *this ); ++(*this); return copy; }
IntegralRangeIterator& operator--() noexcept { --value_; return *this; }
IntegralRangeIterator operator--(int) noexcept { IntegralRangeIterator copy( *this ); --(*this); return copy; }
IntegralRangeIterator& operator+=(difference_type n) noexcept { value_ += n; return *this; }
IntegralRangeIterator& operator-=(difference_type n) noexcept { value_ -= n; return *this; }
friend constexpr IntegralRangeIterator operator+(const IntegralRangeIterator &a, difference_type n) noexcept { return IntegralRangeIterator(a.value_ + n); }
friend constexpr IntegralRangeIterator operator+(difference_type n, const IntegralRangeIterator &a) noexcept { return IntegralRangeIterator(a.value_ + n); }
friend constexpr IntegralRangeIterator operator-(const IntegralRangeIterator &a, difference_type n) noexcept { return IntegralRangeIterator(a.value_ - n); }
constexpr difference_type operator-(const IntegralRangeIterator &other) const noexcept { return (static_cast<difference_type>(value_) - static_cast<difference_type>(other.value_)); }
private:
value_type value_;
};
} // namespace Impl
template <class T>
class IntegralRange
{
public:
typedef T value_type;
typedef Impl::IntegralRangeIterator<T> iterator;
typedef std::make_unsigned_t<T> size_type;
constexpr IntegralRange(value_type from, value_type to) noexcept : from_(from), to_(to) {}
constexpr explicit IntegralRange(value_type to) noexcept : from_(0), to_(to) {}
constexpr IntegralRange(std::pair<value_type, value_type> range) noexcept : from_(range.first), to_(range.second) {}
constexpr iterator begin() const noexcept { return iterator(from_); }
constexpr iterator end() const noexcept { return iterator(to_); }
constexpr value_type operator[](const value_type &i) const noexcept { return (from_ + i); }
constexpr bool empty() const noexcept { return (from_ == to_); }
constexpr size_type size() const noexcept { return (static_cast<size_type>(to_) - static_cast<size_type>(from_)); }
constexpr bool contains(value_type index) const noexcept { return from_ <= index && index < to_; }
private:
value_type from_, to_;
};
template <class T, T to, T from = 0>
class StaticIntegralRange
{
template <T ofs, T... i>
static std::integer_sequence<T, (i+ofs)...> shift_integer_sequence(std::integer_sequence<T, i...>);
public:
typedef T value_type;
typedef Impl::IntegralRangeIterator<T> iterator;
typedef std::make_unsigned_t<T> size_type;
typedef decltype(shift_integer_sequence<from>(std::make_integer_sequence<T, to-from>())) integer_sequence;
constexpr StaticIntegralRange() noexcept = default;
constexpr operator IntegralRange<T>() const noexcept { return {from, to}; }
constexpr operator integer_sequence() const noexcept { return {}; }
static constexpr integer_sequence to_integer_sequence() noexcept { return {}; }
static constexpr iterator begin() noexcept { return iterator(from); }
static constexpr iterator end() noexcept { return iterator(to); }
template <class U, U i>
constexpr auto operator[](const std::integral_constant<U, i> &) const noexcept
-> std::integral_constant<value_type, from + static_cast<value_type>(i)>
{
return {};
}
constexpr value_type operator[](const size_type &i) const noexcept { return (from + static_cast<value_type>(i)); }
static constexpr std::integral_constant<bool, from == to> empty() noexcept { return {}; }
static constexpr std::integral_constant<size_type, static_cast<size_type>(to) - static_cast<size_type>(from) > size() noexcept { return {}; }
static constexpr bool contains(value_type index) noexcept { return from <= index && index < to; }
};
template<class T, class U,
std::enable_if_t<std::is_same<std::decay_t<T>, std::decay_t<U>>::value, int> = 0,
std::enable_if_t<std::is_integral<std::decay_t<T>>::value, int> = 0>
constexpr static IntegralRange<std::decay_t<T>> range(T &&from, U &&to) noexcept
{
return IntegralRange<std::decay_t<T>>(std::forward<T>(from), std::forward<U>(to));
}
template<class T, std::enable_if_t<std::is_integral<std::decay_t<T>>::value, int> = 0>
constexpr static IntegralRange<std::decay_t<T>> range(T &&to) noexcept
{
return IntegralRange<std::decay_t<T>>(std::forward<T>(to));
}
template<class T, std::enable_if_t<std::is_enum<std::decay_t<T>>::value, int> = 0>
constexpr static IntegralRange<std::underlying_type_t<std::decay_t<T>>> range(T &&to) noexcept
{
return IntegralRange<std::underlying_type_t<std::decay_t<T>>>(std::forward<T>(to));
}
template<class T, T from, T to>
constexpr static StaticIntegralRange<T, to, from> range(std::integral_constant<T, from>, std::integral_constant<T, to>) noexcept
{
return {};
}
template<class T, T to>
constexpr static StaticIntegralRange<T, to> range(std::integral_constant<T, to>) noexcept
{
return {};
}
struct ValueTransformationTag {};
struct IteratorTransformationTag {};
namespace Impl
{
// An iterator transforming a wrapped iterator using
// an unary function. It inherits the iterator-category
// of the underlying iterator.
//
// \tparam I Type of the underlying iterator
// \tparam F Type of transformation function that can either be applied directly or after dereferencing
// \tparam TT Type of transformation (ValueTransformationTag or IteratorTransformationTag)
// \tparam C An iterator category tag, defaults to the one of I
template <class I, class F, class TT, class C = typename std::iterator_traits<I>::iterator_category>
class TransformedRangeIterator;
template<class I, class F, class TT, class C>
struct TransformationRangeIteratorTraits
{
template<class FF>
static decltype(auto) transform(FF&& f, const I& it) {
if constexpr (std::is_same_v<TT,IteratorTransformationTag>)
{
if constexpr (Dune::IsCallable<FF(const I&)>::value)
return f(it);
else
return (*f)(it);
}
else
{
if constexpr (Dune::IsCallable<FF(decltype(*it))>::value)
return f(*it);
else
return (*f)(*it);
}
}
using reference = decltype(transform(std::declval<F>(), std::declval<I>()));
using value_type = Dune::AutonomousValue<reference>;
using pointer = std::conditional_t<std::is_lvalue_reference_v<reference>, value_type*, ProxyArrowResult<reference>>;
using difference_type = typename std::iterator_traits<I>::difference_type;
using Facade = Dune::IteratorFacade<TransformedRangeIterator<I,F,TT,C>, C, value_type, reference, pointer, difference_type>;
};
template <class I, class F, class TT, class C>
class TransformedRangeIterator :
public TransformationRangeIteratorTraits<I,F, TT, C>::Facade
{
using Traits = TransformationRangeIteratorTraits<I,F, TT, C>;
using Facade = typename Traits::Facade;
static constexpr bool isBidirectional = std::is_convertible_v<C, std::bidirectional_iterator_tag>;
static constexpr bool isRandomAccess = std::is_convertible_v<C, std::random_access_iterator_tag>;
public:
using Function = F;
using reference = typename Facade::reference;
using difference_type = typename Facade::difference_type;
template<class II, class FF>
constexpr TransformedRangeIterator(II&& it, FF&& f) noexcept :
it_(std::forward<II>(it)),
f_(std::forward<FF>(f))
{}
template<class II,
disableCopyMove<TransformedRangeIterator,II> =0,
std::enable_if_t<std::is_convertible_v<II, I> and std::is_default_constructible_v<F>, int> =0>
constexpr TransformedRangeIterator(II&& it) noexcept :
it_(std::forward<II>(it)),
f_()
{}
template<class FF,
disableCopyMove<TransformedRangeIterator,FF> =0,
std::enable_if_t<std::is_convertible_v<FF, F> and std::is_default_constructible_v<I>, int> =0>
constexpr TransformedRangeIterator(FF&& f) noexcept :
it_(),
f_(std::forward<FF>(f))
{}
// Explicitly initialize members. Using a plain
//
// constexpr TransformedRangeIterator() noexcept {}
//
// would default-initialize the members while
//
// constexpr TransformedRangeIterator() noexcept : it_(), f_() {}
//
// leads to value-initialization. This is a case where
// both are really different. If it_ is a raw pointer (i.e. POD)
// then default-initialization leaves it uninitialized while
// value-initialization zero-initializes it.
constexpr TransformedRangeIterator() noexcept :
it_(),
f_()
{}
// Dereferencing returns a value created by the function
constexpr reference operator*() const noexcept {
return Traits::transform(f_, it_);
}
protected:
friend Dune::IteratorFacadeAccess;
// Export base iterator, such that equalilty comparison,
// differences, and inequality comparisons are automatically
// forwarded to the base iterator by the facade.
const I& baseIterator() const noexcept {
return it_;
}
I& baseIterator() noexcept {
return it_;
}
I it_;
Function f_;
};
} // namespace Impl
template <class R, class F, class T=ValueTransformationTag>
class TransformedRangeView
{
using RawConstIterator = std::decay_t<decltype(std::declval<const R>().begin())>;
using RawIterator = std::decay_t<decltype(std::declval<R>().begin())>;
public:
using const_iterator = Impl::TransformedRangeIterator<RawConstIterator, const F*, T>;
using iterator = Impl::TransformedRangeIterator<RawIterator, F*, T>;
using RawRange = std::remove_reference_t<R>;
template<class RR, class FF>
constexpr TransformedRangeView(RR&& rawRange, FF&& f) noexcept :
rawRange_(std::forward<RR>(rawRange)),
f_(std::forward<FF>(f))
{
static_assert(std::is_same_v<T, ValueTransformationTag> or std::is_same_v<T, IteratorTransformationTag>,
"The TransformationType passed to TransformedRangeView has to be either ValueTransformationTag or IteratorTransformationTag.");
}
constexpr const_iterator begin() const noexcept {
return const_iterator(rawRange_.begin(), &f_);
}
constexpr iterator begin() noexcept {
return iterator(rawRange_.begin(), &f_);
}
constexpr const_iterator end() const noexcept {
return const_iterator(rawRange_.end(), &f_);
}
constexpr iterator end() noexcept {
return iterator(rawRange_.end(), &f_);
}
template<class It=const_iterator,
std::enable_if_t<std::is_same_v<typename It::iterator_category,std::random_access_iterator_tag>, int> = 0>
constexpr decltype(auto) operator[](std::size_t i) const noexcept
{
return this->begin()[i];
}
template<class It=iterator,
std::enable_if_t<std::is_same_v<typename It::iterator_category,std::random_access_iterator_tag>, int> = 0>
constexpr decltype(auto) operator[](std::size_t i) noexcept
{
return this->begin()[i];
}
template<class Range=R,
class = std::void_t<decltype(std::declval<const Range>().size())>>
auto size() const noexcept
{
return rawRange_.size();
}
constexpr bool empty() const noexcept
{
return rawRange_.begin() == rawRange_.end();
}
const RawRange& rawRange() const noexcept
{
return rawRange_;
}
RawRange& rawRange() noexcept
{
return rawRange_;
}
private:
R rawRange_;
F f_;
};
template <class R, class F>
auto transformedRangeView(R&& range, F&& f)
{
return TransformedRangeView<R, std::decay_t<F>, ValueTransformationTag>(std::forward<R>(range), std::forward<F>(f));
}
template <class R, class F>
auto iteratorTransformedRangeView(R&& range, F&& f)
{
return TransformedRangeView<R, std::decay_t<F>, IteratorTransformationTag>(std::forward<R>(range), std::forward<F>(f));
}
template<class Range>
auto sparseRange(Range&& range) {
return Dune::iteratorTransformedRangeView(std::forward<Range>(range), [](auto&& it) {
return std::tuple<decltype(*it), decltype(it.index())>(*it, it.index());
});
}
}
#endif // DUNE_COMMON_RANGE_UTILITIES_HH
typetraits.hh
Traits for type conversions and type information.
iteratorfacades.hh
This file implements iterator facade classes for writing stl conformant iterators.
Dune::ArrayList::size
size_type size() const
Get the number of elements in the list.
Definition arraylist.hh:470
Dune::iteratorTransformedRangeView
auto iteratorTransformedRangeView(R &&range, F &&f)
Create a TransformedRangeView using an iterator transformation.
Definition rangeutilities.hh:697
Dune::transformedRangeView
auto transformedRangeView(R &&range, F &&f)
Create a TransformedRangeView.
Definition rangeutilities.hh:664
Dune::range
static constexpr IntegralRange< std::decay_t< T > > range(T &&from, U &&to) noexcept
free standing function for setting up a range based for loop over an integer range for (auto i: range...
Definition rangeutilities.hh:288
Dune::sparseRange
auto sparseRange(Range &&range)
Allow structured-binding for-loops for sparse iterators.
Definition rangeutilities.hh:716
Dune::disableCopyMove
std::enable_if_t< not Impl::disableCopyMoveHelper< This, T... >::value, int > disableCopyMove
Helper to disable constructor as copy and move constructor.
Definition typeutilities.hh:45
Dune::AutonomousValue
typename AutonomousValueType< T >::type AutonomousValue
Type free of internal references that T can be converted to.
Definition typetraits.hh:566
Dune::operator++
constexpr decltype(auto) operator++()
Preincrement operator.
Definition iteratorfacades.hh:1138
Dune::operator*
constexpr decltype(auto) operator*() const
Dereferencing operator.
Definition iteratorfacades.hh:1119
Dune::operator->
constexpr pointer operator->() const
Arrow access to members of referenced value.
Definition iteratorfacades.hh:1129
Dune::operator--
constexpr decltype(auto) operator--()
Predecrement operator.
Definition iteratorfacades.hh:1169
Dune::type
MPI_Datatype MPITraits< ParallelLocalIndex< T > >::type
Definition plocalindex.hh:317
Dune
Dune namespace
Definition alignedallocator.hh:13
Dune::any_true
bool any_true(const AlignedNumber< bool, align > &val)
Definition debugalign.hh:506
Dune::all_true
bool all_true(const AlignedNumber< bool, align > &val)
Definition debugalign.hh:512
Dune::max_value
T max_value(const AlignedNumber< T, align > &val)
Definition debugalign.hh:494
Dune::min_value
T min_value(const AlignedNumber< T, align > &val)
Definition debugalign.hh:500
Dune::const_iterator
Dune::IntegralRange
dynamic integer range for use in range-based for loops
Definition rangeutilities.hh:171
Dune::IntegralRange::begin
constexpr iterator begin() const noexcept
obtain a random-access iterator to the first element
Definition rangeutilities.hh:188
Dune::IntegralRange::end
constexpr iterator end() const noexcept
obtain a random-access iterator past the last element
Definition rangeutilities.hh:190
Dune::IntegralRange::size_type
std::make_unsigned_t< T > size_type
unsigned integer type corresponding to value_type
Definition rangeutilities.hh:178
Dune::IntegralRange::iterator
Impl::IntegralRangeIterator< T > iterator
type of iterator
Definition rangeutilities.hh:176
Dune::IntegralRange::operator[]
constexpr value_type operator[](const value_type &i) const noexcept
access specified element
Definition rangeutilities.hh:193
Dune::IntegralRange::contains
constexpr bool contains(value_type index) const noexcept
check whether given index is within range [from, to)
Definition rangeutilities.hh:201
Dune::IntegralRange::empty
constexpr bool empty() const noexcept
check whether the range is empty
Definition rangeutilities.hh:196
Dune::IntegralRange::IntegralRange
constexpr IntegralRange(std::pair< value_type, value_type > range) noexcept
construct integer range std::pair
Definition rangeutilities.hh:185
Dune::IntegralRange::IntegralRange
constexpr IntegralRange(value_type from, value_type to) noexcept
construct integer range [from, to)
Definition rangeutilities.hh:181
Dune::IntegralRange::size
constexpr size_type size() const noexcept
obtain number of elements in the range
Definition rangeutilities.hh:198
Dune::IntegralRange::IntegralRange
constexpr IntegralRange(value_type to) noexcept
construct integer range [0, to)
Definition rangeutilities.hh:183
Dune::IntegralRange::value_type
T value_type
type of integers contained in the range
Definition rangeutilities.hh:174
Dune::StaticIntegralRange
static integer range for use in range-based for loops
Definition rangeutilities.hh:224
Dune::StaticIntegralRange::end
static constexpr iterator end() noexcept
obtain a random-access iterator past the last element
Definition rangeutilities.hh:253
Dune::StaticIntegralRange::integer_sequence
decltype(shift_integer_sequence< from >(std::make_integer_sequence< T, to-from >())) integer_sequence
type of corresponding std::integer_sequence
Definition rangeutilities.hh:237
Dune::StaticIntegralRange::contains
static constexpr bool contains(value_type index) noexcept
check whether given index is within range [from, to)
Definition rangeutilities.hh:272
Dune::StaticIntegralRange::StaticIntegralRange
constexpr StaticIntegralRange() noexcept=default
default constructor
Dune::StaticIntegralRange::size_type
std::make_unsigned_t< T > size_type
unsigned integer type corresponding to value_type
Definition rangeutilities.hh:234
Dune::StaticIntegralRange::value_type
T value_type
type of integers contained in the range
Definition rangeutilities.hh:230
Dune::StaticIntegralRange::operator[]
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:257
Dune::StaticIntegralRange::empty
static constexpr std::integral_constant< bool, from==to > empty() noexcept
check whether the range is empty
Definition rangeutilities.hh:267
Dune::StaticIntegralRange::begin
static constexpr iterator begin() noexcept
obtain a random-access iterator to the first element
Definition rangeutilities.hh:251
Dune::StaticIntegralRange::to_integer_sequence
static constexpr integer_sequence to_integer_sequence() noexcept
return corresponding std::integer_sequence
Definition rangeutilities.hh:248
Dune::StaticIntegralRange::operator[]
constexpr value_type operator[](const size_type &i) const noexcept
access specified element (dynamic version)
Definition rangeutilities.hh:264
Dune::StaticIntegralRange::iterator
Impl::IntegralRangeIterator< T > iterator
type of iterator
Definition rangeutilities.hh:232
Dune::StaticIntegralRange::size
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:269
Dune::ValueTransformationTag
Tag to enable value based transformations in TransformedRangeView.
Definition rangeutilities.hh:322
Dune::IteratorTransformationTag
Tag to enable iterator based transformations in TransformedRangeView.
Definition rangeutilities.hh:327
Dune::TransformedRangeView
A range transforming the values of another range on-the-fly.
Definition rangeutilities.hh:495
Dune::TransformedRangeView::iterator
Impl::TransformedRangeIterator< RawIterator, F *, T > iterator
Iterator type.
Definition rangeutilities.hh:515
Dune::TransformedRangeView::TransformedRangeView
constexpr TransformedRangeView(RR &&rawRange, FF &&f) noexcept
Construct from range and function.
Definition rangeutilities.hh:529
Dune::TransformedRangeView::end
constexpr iterator end() noexcept
Definition rangeutilities.hh:565
Dune::TransformedRangeView::const_iterator
Impl::TransformedRangeIterator< RawConstIterator, const F *, T > const_iterator
Const iterator type.
Definition rangeutilities.hh:507
Dune::TransformedRangeView::RawRange
std::remove_reference_t< R > RawRange
Export type of the wrapped untransformed range.
Definition rangeutilities.hh:523
Dune::TransformedRangeView::begin
constexpr iterator begin() noexcept
Definition rangeutilities.hh:549
Dune::TransformedRangeView::rawRange
RawRange & rawRange() noexcept
Export the wrapped untransformed range.
Definition rangeutilities.hh:625
Dune::TransformedRangeView::rawRange
const RawRange & rawRange() const noexcept
Export the wrapped untransformed range.
Definition rangeutilities.hh:617
Dune::TransformedRangeView::begin
constexpr const_iterator begin() const noexcept
Obtain a iterator to the first element.
Definition rangeutilities.hh:545
Dune::TransformedRangeView::size
auto size() const noexcept
Obtain the size of the range.
Definition rangeutilities.hh:601
Dune::TransformedRangeView::end
constexpr const_iterator end() const noexcept
Obtain a iterator past the last element.
Definition rangeutilities.hh:561
Dune::TransformedRangeView::empty
constexpr bool empty() const noexcept
Checks whether the range is empty.
Definition rangeutilities.hh:609
Dune::IsCallable
Check if a type is callable with ()-operator and given arguments.
Definition typetraits.hh:162