span.hh

// -*- 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_STD_SPAN_HH
#define DUNE_COMMON_STD_SPAN_HH
 
#include <cassert>
#include <cstddef>
#include <exception>
#include <iterator>
#include <limits>
#include <stdexcept>
#include <string>
#include <type_traits>
#if __has_include(<version>)
  #include <version>
#endif
 
#include <dune/common/exceptions.hh>
#include <dune/common/std/memory.hh>
 
namespace Dune::Std {
 
inline constexpr std::size_t dynamic_extent = std::numeric_limits<std::size_t>::max();
 
namespace Impl {
 
template <std::size_t Extent>
class SpanSize
{
public:
  using size_type = std::size_t;
 
public:
  constexpr SpanSize () = default;
 
  constexpr SpanSize ([[maybe_unused]] size_type size) noexcept
  {
    assert(Extent == Std::dynamic_extent || Extent == size);
  }
 
  template <class Iter>
  constexpr SpanSize ([[maybe_unused]] Iter first, [[maybe_unused]] Iter last) noexcept
  {
    assert((std::distance(first,last) == Extent));
  }
 
  constexpr size_type size () const noexcept { return Extent; }
};
 
template <>
class SpanSize<Std::dynamic_extent>
{
public:
  using size_type = std::size_t;
 
public:
  constexpr SpanSize (size_type size = 0) noexcept
    : size_(size)
  {}
 
  template <class Iter>
  constexpr SpanSize (Iter first, Iter last) noexcept
    : size_(std::distance(first,last))
  {}
 
  constexpr size_type size () const noexcept { return size_; }
 
private:
  size_type size_;
};
 
template <class T>
struct TypeIdentity { using type = T; };
 
template <class T>
using TypeIdentity_t = typename TypeIdentity<T>::type;
 
} // end namespace Impl
 
 
template <class Element, std::size_t Extent = Std::dynamic_extent>
class span
    : public Impl::SpanSize<Extent>
{
  using base_type = Impl::SpanSize<Extent>; // base_type implements the member variable size()
 
  static_assert(std::is_object_v<Element> && !std::is_abstract_v<Element>);
 
public:
  using element_type = Element;
  using value_type = std::remove_cv_t<element_type>;
  using size_type = std::size_t;
  using difference_type = std::ptrdiff_t;
  using pointer = element_type*;
  using reference = element_type&;
  using const_reference  = const element_type&;
  using iterator = pointer;
  using reverse_iterator = std::reverse_iterator<iterator>;
#if __cpp_lib_ranges_as_const >202311L
  using const_iterator = std::const_iterator<iterator>;
  using const_reverse_iterator = std::const_iterator<reverse_iterator>;
#else
  using const_iterator = const iterator;
  using const_reverse_iterator = std::reverse_iterator<const_iterator>;
#endif
 
 
  static constexpr size_type extent = Extent;
 
public:
 
  template <std::size_t e = extent,
    std::enable_if_t<(e == dynamic_extent || e == 0), int> = 0>
  constexpr span () noexcept
    : base_type{}
    , data_{}
  {}
 
  template <class Iter,
    class U = std::remove_reference_t<decltype(*std::declval<Iter>())>,
    std::enable_if_t<std::is_convertible_v<U(*)[], element_type(*)[]>, int> = 0>
  #if __cpp_conditional_explicit >= 201806L
  explicit(extent != Std::dynamic_extent)
  #endif
  constexpr span (Iter first, size_type size)
    : base_type(size)
    , data_(Std::to_address(first))
  {}
 
  template <class Iter,
    class U = std::remove_reference_t<decltype(*std::declval<Iter>())>,
    std::enable_if_t<std::is_convertible_v<U(*)[], element_type(*)[]>, int> = 0>
  #if __cpp_conditional_explicit >= 201806L
  explicit(extent != Std::dynamic_extent)
  #endif
  constexpr span (Iter first, Iter last)
    : base_type(first,last)
    , data_(Std::to_address(first))
  {}
 
  template <class Range,
    decltype(std::begin(std::declval<Range>()), std::end(std::declval<Range>()), bool{}) = true,
    std::enable_if_t<not std::is_array_v<Range>, int> = 0>
  #if __cpp_conditional_explicit >= 201806L
  explicit(extent != Std::dynamic_extent)
  #endif
  constexpr span (Range& range)
    : span(std::begin(range), std::end(range))
  {}
 
  template <std::size_t N, std::size_t e = extent,
    std::enable_if_t<(e == Std::dynamic_extent || e == N), int> = 0>
  constexpr span (Impl::TypeIdentity_t<element_type> (&data)[N]) noexcept
    : base_type(N)
    , data_(data)
  {}
 
  template <class T, size_t N, std::size_t e = extent,
    std::enable_if_t<(e == Std::dynamic_extent || e == N), int> = 0,
    std::enable_if_t<std::is_convertible_v<T(*)[], element_type(*)[]>, int> = 0>
  constexpr span (std::array<T, N>& arr) noexcept
    : base_type(N)
    , data_(arr.data())
  {}
 
  template <class T, size_t N, std::size_t e = extent,
    std::enable_if_t<(e == Std::dynamic_extent || e == N), int> = 0,
    std::enable_if_t<std::is_convertible_v<const T(*)[], element_type(*)[]>, int> = 0>
  constexpr span (const std::array<T, N>& arr) noexcept
    : base_type(N)
    , data_(arr.data())
  {}
 
  template <class E = element_type,
    std::enable_if_t<std::is_const_v<E>, int> = 0>
  #if __cpp_conditional_explicit >= 201806L
  explicit(extent != Std::dynamic_extent)
  #endif
  constexpr span (std::initializer_list<value_type> il)
    : base_type(il.size())
    , data_(il.begin())
  {}
 
  constexpr span (const span& other) noexcept = default;
 
  template <class OtherElementType, std::size_t OtherExtent,
    std::enable_if_t<(extent == Std::dynamic_extent || OtherExtent == Std::dynamic_extent || extent == OtherExtent), int> = 0,
    std::enable_if_t<std::is_convertible_v<OtherElementType(*)[], element_type(*)[]>, int> = 0>
  #if __cpp_conditional_explicit >= 201806L
  explicit(extent != Std::dynamic_extent && OtherExtent == Std::dynamic_extent)
  #endif
  constexpr span (const span<OtherElementType, OtherExtent>& s) noexcept
    : base_type(s.size())
    , data_(s.data())
  {}
 
  constexpr span& operator= (const span& other) noexcept = default;
 
 
 
 
  constexpr iterator begin () const noexcept { return data_; }
 
  constexpr iterator end () const noexcept { return data_ + size(); }
 
  constexpr const_iterator cbegin () const noexcept { return data_; }
 
  constexpr const_iterator cend () const noexcept { return data_ + size(); }
 
  constexpr reverse_iterator rbegin() const noexcept { return reverse_iterator{end()}; }
 
  constexpr reverse_iterator rend() const noexcept { return reverse_iterator{begin()}; }
 
  constexpr const_reverse_iterator  crbegin() const noexcept { return reverse_iterator{end()}; }
 
  constexpr const_reverse_iterator  crend() const noexcept { return reverse_iterator{begin()}; }
 
 
 
 
  constexpr reference front () const
  {
    assert(not empty() && "front of empty span does not exist");
    return data_[0];
  }
 
  constexpr reference back () const
  {
    assert(not empty() && "front of empty span does not exist");
    return data_[size()-1];
  }
 
  constexpr reference at (size_type i) const
  {
    if (i >= size())
      throw std::out_of_range("Index " + std::to_string(i) + " out of range.");
    return data_[i];
  }
 
  constexpr reference operator[] (size_type i) const { return data_[i]; }
 
  constexpr pointer data () const noexcept { return data_; }
 
 
 
 
  template <std::size_t Count>
  constexpr span<element_type, Count> first () const
  {
    static_assert(Count <= Extent);
    assert(Count <= size());
    return span<element_type, Count>{data(), Count};
  }
 
  template <std::size_t Count>
  constexpr span<element_type, Count> last () const
  {
    static_assert(Count <= Extent);
    assert(Count <= size());
    return span<element_type, Count>{data()+ (size() - Count), Count};
  }
 
private:
 
  static constexpr std::size_t subspan_extent (std::size_t O, std::size_t C) noexcept
  {
    return (C != Std::dynamic_extent) ? C :
      (Extent != Std::dynamic_extent) ? Extent - O : Std::dynamic_extent;
  }
 
public:
 
 
  template <std::size_t Offset, std::size_t Count = Std::dynamic_extent>
  constexpr span<element_type, subspan_extent(Offset,Count)> subspan () const
  {
    static_assert(Offset <= Extent && (Count == Std::dynamic_extent || Count <= Extent - Offset));
    assert(Offset <= size() && (Count == Std::dynamic_extent || Count <= size() - Offset));
    return span<element_type, subspan_extent(Offset,Count)>{
      data() + Offset, Count != Std::dynamic_extent ? Count : size() - Offset};
  }
 
  constexpr span<element_type, Std::dynamic_extent> first (size_type count) const
  {
    assert(count <= size());
    return span<element_type, Std::dynamic_extent>{data(), count};
  }
 
  constexpr span<element_type, Std::dynamic_extent> last (size_type count) const
  {
    assert(count <= size());
    return span<element_type, Std::dynamic_extent>{data()+ (size() - count), count};
  }
 
 
  constexpr span<element_type, Std::dynamic_extent> subspan (size_type offset, size_type count = Std::dynamic_extent) const
  {
    assert(offset <= size() && (count == Std::dynamic_extent || count <= size() - offset));
    return span<element_type, Std::dynamic_extent>{
      data() + offset, count == Std::dynamic_extent ? size() - offset : count};
  }
 
 
 
 
  using base_type::size;
 
  constexpr size_type size_bytes () const noexcept { return size() * sizeof(element_type); }
 
  [[nodiscard]] constexpr bool empty () const noexcept { return size() == 0; }
 
 
private:
  pointer data_;
};
 
// deduction guide
// @{
 
template <class T, std::size_t N>
span (T (&)[N])
  -> span<T, N>;
 
template <class ElementType, class I, std::size_t Extent,
  std::enable_if_t<std::is_convertible_v<I,std::size_t>, int> = 0>
span (ElementType*, std::integral_constant<I,Extent>)
  -> span<ElementType, Extent>;
 
template <class ElementType, class I,
  std::enable_if_t<std::is_integral_v<I>, int> = 0,
  std::enable_if_t<std::is_convertible_v<I,std::size_t>, int> = 0>
span (ElementType*, I)
  -> span<ElementType, Std::dynamic_extent>;
 
template <class Iter,
  class Element = std::remove_reference_t<decltype(*std::declval<Iter>())>>
span (Iter,Iter)
  -> span<Element, Std::dynamic_extent>;
 
template <class Range,
  class First = decltype(std::begin(std::declval<Range>())),
  class Last = decltype(std::end(std::declval<Range>())),
  class Element = std::remove_reference_t<decltype(*std::declval<First>())>>
span (Range&)
  -> span<Element, Std::dynamic_extent>;
 
template <class T, size_t N>
span (std::array<T, N>&) -> span<T, N>;
 
template <class T, size_t N>
span (const std::array<T, N>&) -> span<const T, N>;
 
// @}
 
} // end namespace Dune::Std
 
#endif // DUNE_COMMON_STD_SPAN_HH