// Copyright (c) 2017-2018 Maikel Nadolski
//
// Permission is hereby granted, free of charge, to any person obtaining a copy
// of this software and associated documentation files (the "Software"), to deal
// in the Software without restriction, including without limitation the rights
// to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
// copies of the Software, and to permit persons to whom the Software is
// furnished to do so, subject to the following conditions:
//
// The above copyright notice and this permission notice shall be included in
// all copies or substantial portions of the Software.
//
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
// OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
// SOFTWARE.

#ifndef FUB_CORE_SPAN_HPP
#define FUB_CORE_SPAN_HPP

#include <cassert>
#include <array>
#include <tuple>
#include <type_traits>
#include <experimental/type_traits>

namespace std::experimental {

inline constexpr std::ptrdiff_t dynamic_extent = -1;

/// \defgroup spans Spans
/// Types and function which are about non-owning ranges of contiguous memory.

namespace detail {
/// @{
/// Tests if the specified type `T` is a `std::array<U, N>` for some U and N.
template <typename T> struct is_std_array : std::false_type {};
template <typename T, std::size_t N>
struct is_std_array<std::array<T, N>> : std::true_type {};
/// @}

template <typename T> using data_t = decltype(std::declval<T>().data());
template <typename T> using element_type_ = std::remove_pointer_t<data_t<T>>;
template <typename T> using array_type_t = element_type_<T> (*)[];
} // namespace detail

template <typename T, std::ptrdiff_t N> class span;

///////////////////////////////////////////////////////////////////////////////
//                                                        [span.traits.is_span]

/// Returns true if the specified T is a `span<S, N>` for some type S and
/// integer N.
template <typename T> struct is_span : std::false_type {};

/// Returns true if the specified T is a `span<S, N>` for some type S and
/// integer N.
template <typename T, std::ptrdiff_t N>
struct is_span<span<T, N>> : std::true_type {};

/// Returns true if the specified T is a `span<S, N>` for some type S and
/// integer N.
template <typename T> static constexpr bool is_span_v = is_span<T>::value;

///////////////////////////////////////////////////////////////////////////////
//                                                                 [span.class]

/// \ingroup spans
/// A span is a view over a contiguous sequence of objects, the storage of which
/// is owned by some other object.
///
/// All member functions of span have constant time complexity.
///
/// `T` is required to be a complete object type that is not an abstract
/// class type.
///
/// If `N` is negative and not equal to dynamic_­extent, the program is
/// ill-formed.
template <typename T, std::ptrdiff_t N = dynamic_extent> class span {
public:
  static_assert(N > 0, "span's extent needs to be non-negative.");

  using element_type = T;
  using pointer = T*;
  using reference = T&;
  using value_type = std::remove_cv_t<T>;
  using index_type = std::ptrdiff_t;
  using difference_type = std::ptrdiff_t;
  using iterator = pointer;
  using const_iterator = std::add_const_t<T>*;
  using reverse_iterator = std::reverse_iterator<iterator>;
  using const_reverse_iterator = std::reverse_iterator<const_iterator>;

  static constexpr index_type extent = N;
  static constexpr std::size_t sextent = static_cast<std::size_t>(N);

  /// \name  Constructors, copy, and assignment [span.cons]

  /// Constructs a span from a `pointer` and `size` pair.
  ///
  /// This performs an assertion check in debug builds which will terminate the
  /// application if the specified size does not match the extent.
  ///
  /// \param[in] p  a valid address pointing to the first element of the span.
  /// \param[in] size  the size such that `[p, p + size)` is a valid range.
  ///
  /// \pre `size == extent`
  ///
  /// \post `data() == p`
  /// \post `size() == size`
  ///
  /// \throws Nothing.
  constexpr span(pointer p, [[maybe_unused]] index_type size) : pointer_{p} {
    assert(size == extent);
  }

  /// Constructs a span from two pointers.
  ///
  /// This performs an assertion check in debug builds which will terminate the
  /// application if the specified size does not match the extent.
  ///
  /// \param[in] first  a valid address pointing to the first element of the
  /// span. \param[in] last  a pointer such that `[first, last)` is a valid
  /// range.
  ///
  /// \pre `last - first == extent`
  ///
  /// \post `data() == first`
  /// \post `size() == last - first`
  ///
  /// \throws Nothing.
  constexpr span(pointer first, pointer last) : span(first, last - first) {}

  /// Implicit conversion from a built-in C-style array.
  ///
  /// \param[in] arr  A native array which will be viewed on.
  ///
  /// \post `data() = &arr[0]`
  /// \post `size() == extent`
  ///
  /// \throws Nothing.
  constexpr span(element_type (&arr)[sextent]) noexcept // NOLINT
      : pointer_{&arr[0]} {}

  /// Implicit conversion from const `std::array`s.
  ///
  /// \param[in] arr  A `std::array` which will be viewed on.
  ///
  /// \pre `std::is_const<element_type>`
  ///
  /// \post `data() = arr.data()`
  /// \post `size() == extent`
  ///
  /// \throws Nothing.
  template <typename ValueType, std::size_t Extent,
            typename = std::enable_if_t<Extent == extent>,
            typename = std::enable_if_t<std::is_convertible<
                const ValueType (*)[], element_type (*)[]>::value>>
  constexpr span(const std::array<ValueType, Extent>& arr) noexcept // NOLINT
      : pointer_{arr.data()} {}

  /// Implicit conversion from mutable `std::array`s.
  ///
  /// \param[in] arr  A `std::array` which will be viewed on.
  ///
  /// \pre `M == extent`
  ///
  /// \post `data() = arr.data()`
  /// \post `size() == extent`
  ///
  /// \throws Nothing.
  template <typename ValueType, std::size_t Extent,
            typename = std::enable_if_t<Extent == extent>,
            typename = std::enable_if_t<std::is_convertible<
                ValueType (*)[], element_type (*)[]>::value>>
  constexpr span(std::array<ValueType, Extent>& arr) noexcept // NOLINT
      : pointer_{arr.data()} {}

  /// Implicit conversion operator from a mutable container.
  ///
  /// \param[in] container  A container which owns the contiguous memory. The
  ///            container must outlive this span, otherwise the span is
  ///            dangling.
  ///
  /// \tparam Container  A container class which has the class member functions
  ///                    `Container::data()` and `Container::size()`.
  ///
  /// \pre `container.size() == extent`
  /// \pre `!is_span_v<Container>`
  ///
  /// \post  `data() == container.data()`
  /// \post `size() == container.size() == extent`
  ///
  /// \throws Nothing.
#ifdef DOXYGEN
  template <typename Container>
#else
  template <typename Container,
            typename = std::enable_if_t<!std::is_array<Container>::value>,
            typename = std::enable_if_t<
                !detail::is_std_array<std::remove_const_t<Container>>::value>,
            typename = std::enable_if_t<!is_span<Container>::value>,
            typename = std::enable_if_t<std::is_convertible<
                detected_t<detail::array_type_t, Container&>,
                element_type (*)[]>::value>>
#endif
  constexpr span(Container& container) // NOLINT
      : pointer_{container.data()} {
    assert(container.size() == extent);
  }

  /// Implicit conversion operator from a constant container.
  ///
  /// \param[in] container  A container which owns the contiguous memory. The
  ///            container must outlive this span, otherwise the span is
  ///            dangling.
  ///
  /// \tparam Container  A container class which has the class member functions
  ///                    `Container::data()` and `Container::size()`.
  ///
  /// \pre `extent <= container.size()`
  /// \pre `!is_span_v<Container>`
  ///
  /// \post `data() == container.data()`
  /// \post `size() == container.size() == extent`
  ///
  /// \throws Nothing.
#ifdef DOXYGEN
  template <typename Container>
#else
  template <
      typename Container,
      typename = std::enable_if_t<!std::is_array<Container>::value>,
      typename = std::enable_if_t<!detail::is_std_array<Container>::value>,
      typename = std::enable_if_t<!is_span<Container>::value>,
      typename = std::enable_if_t<std::is_convertible<
          detected_t<detail::array_type_t, const Container&>,
          element_type (*)[]>::value>>
#endif
  constexpr span(const Container& container) // NOLINT
      : pointer_{container.data()} {
    assert(container.size() == extent);
  }

  /// Implicit conversion from other span types.
  ///
  /// \tparam S  the element type of the other span.
  /// \tparam M  the static extents of the other span.
  ///
  /// \pre s.size() == extent
  /// \pre std::is_convertible<S(*)[], T(*)[]>::value
  ///
  /// \post `data() == s.data()`
  /// \post `size() == s.size() == extent`.
#ifdef DOXYGEN
  template <typename S, std::ptrdiff_t M>
#else
  template <
      typename S, std::ptrdiff_t M,
      typename = std::enable_if_t<std::is_convertible<
          typename span<S, M>::element_type (*)[], element_type (*)[]>::value>,
      typename = std::enable_if_t<extent == M>>
#endif
  constexpr span(const span<S, M>& s) noexcept // NOLINT
      : pointer_{s.data()} {
  }

  template <
      typename S,
      typename = std::enable_if_t<std::is_convertible<
          typename span<S>::element_type (*)[], element_type (*)[]>::value>>
  constexpr span(const span<S>& s) // NOLINT
      : pointer_{s.data()} {
    assert(s.size() == extent);
  }

  /// Defaulted copy constructor to trivially copy the class member variables.
  ///
  /// \throws Nothing.
  constexpr span(const span& s) noexcept = default;

  /// \name Subviews [span.sub]

  /// Returns a span of the first `Count`-many elements of this span.
  ///
  /// \tparam Count  Size of the returned subspan.
  ///
  /// \pre `0 <= Count && Count <= extent`.
  ///
  /// \throws Nothing.
  template <ptrdiff_t Count,
            typename = std::enable_if_t<(0 <= Count && Count <= extent)>>
  constexpr span<element_type, Count> first() const {
    return {pointer_, Count};
  }

  /// Returns a span of the first `count`-many elements of this span.
  ///
  /// \param[in] count  Size of the returned subspan.
  ///
  /// \pre `0 <= count && count <= extent`.
  ///
  /// \throws Nothing.
  constexpr span<element_type> first(index_type count) const {
    assert(0 <= count && count <= size());
    return {pointer_, count};
  }

  /// Returns a span of the last `Count`-many elements of this span.
  ///
  /// \tparam Count  Size of the returned subspan.
  ///
  /// \pre `0 <= Count && Count <= extent`.
  ///
  /// \throws Nothing.
  template <ptrdiff_t Count,
            typename = std::enable_if_t<(0 <= Count && Count <= extent)>>
  constexpr span<element_type, Count> last() const {
    return {pointer_ + (extent - Count), Count};
  }

  /// Returns a span of the last `count`-many elements of this span.
  ///
  /// \param[in] count  Size of the returned subspan.
  ///
  /// \pre `0 <= count && count <= extent`.
  ///
  /// \throws Nothing.
  constexpr span<element_type> last(index_type count) const {
    assert(0 <= count && count <= extent);
    return {pointer_ + (extent - count), count};
  }

  /// Returns a subspan viewing `Count` many elements from offset `Offset`.
  ///
  /// \tparam Offset  the offset of the returned subspan.
  /// \tparam Count  Size of the returned subspan.
  ///
  /// \pre `0 <= Count && Count <= extent`.
  ///
  /// \throws Nothing.
  template <
      ptrdiff_t Offset, ptrdiff_t Count = dynamic_extent,
      typename = std::enable_if_t<(0 <= Offset && Offset <= extent)>,
      typename = std::enable_if_t<(Count == dynamic_extent ||
                                   (0 <= Count && Count + Offset <= extent))>>
  constexpr auto subspan() const {
#ifndef __cpp_if_constexpr
    struct if_constexpr_t_ {
      auto operator()(std::true_type, pointer p) {
        return span<T, extent - Offset>{p + Offset, extent - Offset};
      }
      auto operator()(std::false_type, pointer p) {
        return span<T, Count>{p + Offset, Count};
      }
    } if_constexpr_{};
    return if_constexpr_(Count == dynamic_extent, pointer_, extent);
#else
    if constexpr (Count == dynamic_extent) {
      return span<T, extent - Offset>{pointer_ + Offset, extent - Offset};
    } else {
      return span<T, Count>{pointer_ + Offset, Count};
    }
#endif
  }

  /// Returns a subspan viewing `count` many elements from offset `offset`.
  ///
  /// \param offset  the offset of the returned subspan.
  /// \param count  Size of the returned subspan.
  ///
  /// \pre `0 <= offset && offset <= extent`.
  /// \pre `count == dynamic_extent || 0 <= count && count + offset <= size()`.
  ///
  /// \throws Nothing.
  constexpr span<element_type>
  subspan(index_type offset, index_type count = dynamic_extent) const {
    assert(0 <= offset && offset <= size());
    assert(count == dynamic_extent ||
               (0 <= count && count + offset <= size()));
    return {pointer_ + offset,
            count == dynamic_extent ? size() - offset : count};
  }

  /// \name Observers [span.obs]

  /// Returns the number of elements in the span.
  ///
  /// \throws Nothing.
  constexpr index_type size() const noexcept { return extent; }

  /// Returns the number of bytes which are spanned by this span.
  ///
  /// \throws Nothing.
  constexpr index_type size_bytes() const noexcept {
    return sizeof(T) * extent;
  }

  /// Returns true if  `size() == 0`.
  ///
  /// \throws Nothing.
  constexpr bool empty() const noexcept { return false; }

  /// \name Element access [span.elem]

  /// Returns the underlying pointer.
  ///
  /// \throws Nothing.
  constexpr pointer data() const noexcept { return pointer_; }

  /// Accesses the n-th element of the spanned array.
  ///
  /// \throws Nothing.
  constexpr reference operator[](index_type n) const { return pointer_[n]; }

  /// Accesses the n-th element of the spanned array.
  ///
  /// \throws Nothing.
  constexpr reference operator()(index_type n) const { return pointer_[n]; }

  /// \name Iterator support [span.iterators]

  /// Returns an iterator pointing to the first element of the span.
  ///
  /// \throws Nothing.
  constexpr iterator begin() const noexcept { return pointer_; }

  /// Returns a const iterator pointing to the first element of the span.
  ///
  /// \throws Nothing.
  constexpr const_iterator cbegin() const noexcept { return pointer_; }

  /// Returns an iterator pointing one after the last element of the span.
  ///
  /// \throws Nothing.
  constexpr iterator end() const noexcept { return pointer_ + extent; }

  /// Returns a const iterator pointing one after the last element of the span.
  ///
  /// \throws Nothing.
  constexpr const_iterator cend() const noexcept { return pointer_ + extent; }

  /// Returns a reverse iterator pointing to the last element of the span.
  ///
  /// \throws Nothing.
  constexpr reverse_iterator rbegin() const noexcept {
    return reverse_iterator(end());
  }

  /// Returns a const reverse iterator pointing to the last element of the span.
  ///
  /// \throws Nothing.
  constexpr const_reverse_iterator crbegin() const noexcept {
    return const_reverse_iterator(cend());
  }

  /// Returns a reverse iterator pointing to the first element of the span.
  ///
  /// \throws Nothing.
  constexpr reverse_iterator rend() const noexcept {
    return reverse_iterator(begin());
  }

  /// Returns a const reverse iterator pointing to the first element of the
  /// span.
  ///
  /// \throws Nothing.
  constexpr const_reverse_iterator crend() const noexcept {
    return const_reverse_iterator(cbegin());
  }

private:
  pointer pointer_;
};

/// \ingroup spans
/// A span is a view over a contiguous sequence of objects, the storage of which
/// is owned by some other object.
///
/// All member functions of span have constant time complexity.
///
/// `T` is required to be a complete object type that is not an abstract
/// class type.
///
/// If `N` is negative and not equal to dynamic_­extent, the program is
/// ill-formed.
template <typename T> class span<T, 0> {
public:
  using element_type = T;
  using pointer = T*;
  using reference = T&;
  using value_type = std::remove_cv_t<T>;
  using index_type = std::ptrdiff_t;
  using difference_type = std::ptrdiff_t;
  using iterator = pointer;
  using const_iterator = std::add_const_t<T>*;
  using reverse_iterator = std::reverse_iterator<iterator>;
  using const_reverse_iterator = std::reverse_iterator<const_iterator>;

  static constexpr index_type extent = 0;

  /// \name  Constructors, copy, and assignment [span.cons]

  /// Constructs an empty span.
  ///
  /// \post `data() == nullptr`
  /// \post `size() == 0`
  ///
  /// \throws Nothing.
  constexpr span() noexcept = default;

  /// Constructs a span from a `pointer` + `size` pair.
  ///
  /// This performs an assertion check in debug builds which will terminate the
  /// application if the specified size does not match the extent.
  ///
  /// \pre `p` is a valid pointer.
  /// \pre `size == 0`
  ///
  /// \post `data() == p`
  /// \post `size() == 0`
  ///
  /// \throws Nothing.
  constexpr span(pointer p, [[maybe_unused]] index_type size) : pointer_{p} {
    assert(size == 0);
  }

  /// Constructs a span from two `pointer`s.
  ///
  /// This performs an assertion check in debug builds which will terminate the
  /// application if the specified size does not match the extent.
  ///
  /// \pre `first` and `last` are valid pointers.
  /// \pre `first == last`
  ///
  /// \post `data() == first`
  /// \post `size() == last - first`
  ///
  /// \throws Nothing.
  constexpr span(pointer first, pointer last) : span(first, last - first) {}

  /// Implicit conversion operator from a mutable container.
  ///
  /// \pre `container.size() == extent`
  /// \pre `!is_span_v<Container>`
  /// \pre `container.size() == 0`
  ///
  /// \post  `data() == container.data()`
  /// \post `size() == container.size()`
  ///
  /// \throws Nothing.
#ifdef DOXYGEN
  template <typename Container>
#else
  template <typename Container,
            typename = std::enable_if_t<!std::is_array<Container>::value>,
            typename = std::enable_if_t<!is_span<Container>::value>,
            typename = std::enable_if_t<
                std::is_convertible<detected_t<detail::array_type_t, Container>,
                                    element_type (*)[]>::value>>
#endif
  constexpr span(Container& container) // NOLINT
      : pointer_{container.data()} {
    assert(container.size() == extent);
  }

/// Implicit conversion operator from a constant container.
///
/// \pre `extent <= container.size()`
/// \pre `!is_span_v<Container>`
/// \pre `container.size() == 0`
///
/// \post `data() == container.data()`
/// \post `size() == container.size()`
///
/// \throws Nothing.
#ifdef DOXYGEN
  template <typename Container>
#else
  template <typename Container,
            typename = std::enable_if_t<!std::is_array<Container>::value>,
            typename = std::enable_if_t<!is_span<Container>::value>,
            typename = std::enable_if_t<
                std::is_convertible<detected_t<detail::array_type_t, Container>,
                                    element_type (*)[]>::value>>
#endif
  constexpr span(const Container& container) // NOLINT
      : pointer_{container.data()} {
    assert(container.size() == extent);
  }

  /// Implicit conversion from other span types.
  ///
  /// \pre std::is_convertible<S(*)[], T(*)[]>::value
  ///
  /// \post data() == s.data()
  ///
  /// \throws Nothing.
#ifdef DOXYGEN
  template <typename S>
#else
  template <
      typename S,
      typename = std::enable_if_t<std::is_convertible<
          typename span<S, 0>::element_type (*)[], element_type (*)[]>::value>>
#endif
  constexpr span(const span<S, 0>& s) noexcept // NOLINT
      : pointer_{s.data()} {
  }

  /// Defaulted copy constructor to trivially copy the class member variables.
  ///
  /// \throws Nothing.
  constexpr span(const span& s) noexcept = default;

  /// \name Observers [span.obs]

  /// Returns the number of elements in the span.
  ///
  /// \throws Nothing.
  constexpr index_type size() const noexcept { return 0; }

  /// Returns the number of bytes which are spanned by this span.
  ///
  /// \throws Nothing.
  constexpr std::ptrdiff_t size_bytes() const noexcept { return 0; }

  /// Returns true if  `size() == 0`.
  ///
  /// \throws Nothing.
  constexpr bool empty() const noexcept { return true; }

  /// \name Element access [span.elem]

  /// Returns the underlying pointer.
  ///
  /// \throws Nothing.
  constexpr pointer data() const noexcept { return pointer_; }

  /// \name Iterator support [span.iterators]

  /// Returns an iterator pointing to the first element of the span.
  ///
  /// \throws Nothing.
  constexpr iterator begin() const noexcept { return data(); }

  /// Returns a const iterator pointing to the first element of the span.
  ///
  /// \throws Nothing.
  constexpr const_iterator cbegin() const noexcept { return data(); }

  /// Returns an iterator pointing one after the last element of the span.
  ///
  /// \throws Nothing.
  constexpr iterator end() const noexcept { return begin() + size(); }

  /// Returns a const iterator pointing one after the last element of the span.
  ///
  /// \throws Nothing.
  constexpr const_iterator cend() const noexcept { return begin() + size(); }

  /// Returns a reverse iterator pointing to the last element of the span.
  ///
  /// \throws Nothing.
  constexpr reverse_iterator rbegin() const noexcept {
    return reverse_iterator(end());
  }

  /// Returns a const reverse iterator pointing to the last element of the span.
  ///
  /// \throws Nothing.
  constexpr const_reverse_iterator crbegin() const noexcept {
    return const_reverse_iterator(cend());
  }

  /// Returns a reverse iterator pointing to the first element of the span.
  ///
  /// \throws Nothing.
  constexpr reverse_iterator rend() const noexcept {
    return reverse_iterator(begin());
  }

  /// Returns a const reverse iterator pointing to the first element of the
  /// span.
  ///
  /// \throws Nothing.
  constexpr const_reverse_iterator crend() const noexcept {
    return const_reverse_iterator(cbegin());
  }

private:
  pointer pointer_{nullptr};
};

/// \ingroup spans
/// span is a compact view over a contiguous range of data.
///
/// This class models something like
///
/// \code struct span { pointer ptr; std::ptrdiff_t length; }; \endcode
///
/// Where the `length` can be omitted for statically sized views.
template <typename T> class span<T, dynamic_extent> {
public:
  using element_type = T;
  using pointer = T*;
  using reference = T&;
  using value_type = std::remove_cv_t<T>;
  using index_type = std::ptrdiff_t;
  using difference_type = std::ptrdiff_t;
  using iterator = pointer;
  using const_iterator = std::add_const_t<T>*;
  using reverse_iterator = std::reverse_iterator<iterator>;
  using const_reverse_iterator = std::reverse_iterator<const_iterator>;

  static constexpr index_type extent = dynamic_extent;

  /////////////////////////////////////////////////////////////////////////////
  // Constructors

  /// Constructs an empty span of size 0.
  ///
  /// This initializes the underlying pointer to nullptr and the size to 0.
  ///
  /// \throws Nothing.
  ///
  /// \post data() == nullptr
  /// \post size() == 0
  constexpr span() = default;

  /// Constructs a span from a `pointer` + `size` pair.
  ///
  /// This performs an assertion check in debug builds which will terminate the
  /// application if the specified size does not match the extent.
  ///
  /// \throws Nothing.
  ///
  /// \post data() == p
  /// \post size() == size
  constexpr span(pointer p, index_type size) noexcept
      : pointer_{p}, size_{size} {}

  /// Constructs a span from two `pointer`s.
  ///
  /// This performs an assertion check in debug builds which will terminate the
  /// application if the specified size does not match the extent.
  ///
  /// \throws Nothing.
  ///
  /// \post data() == first
  /// \post size() == last - first
  constexpr span(pointer first, pointer last) noexcept
      : pointer_{first}, size_{last - first} {}

  /// Implicit conversion from a built-in C-style array.
  ///
  /// \throws Nothing.
  ///
  /// \post data() = pointer(&arr[0])
  /// \post size() == M
  template <std::size_t M>
  constexpr span(element_type (&arr)[M]) noexcept // NOLINT
      : pointer_{&arr[0]}, size_{static_cast<index_type>(M)} {}

  /// Implicit conversion from mutable Container-like types.
  ///
  /// \pre S(*)[] is convertible to element_type(*)[]
  ///
  /// \throws Nothing.
  ///
  /// \post data() = container.data()
  /// \post size() = container.size()
  template <
      typename Container,
      typename = std::enable_if_t<!std::is_array<Container>::value>,
      typename =
          std::enable_if_t<!is_span<std::remove_const_t<Container>>::value>,
      typename = std::enable_if_t<
          std::is_convertible<detected_t<detail::array_type_t, Container&>,
                              element_type (*)[]>::value>>
  constexpr span(Container& container) noexcept // NOLINT
      : pointer_{container.data()}, size_{static_cast<index_type>(
                                        container.size())} {}

  /// Implicit conversion from other span types.
  ///
  /// \pre size() <= M
  /// \pre std::is_convertible<S(*)[], T(*)[]>::value
  ///
  /// \post data() == s.data()
  template <
      typename S, index_type OtherExtents,
      typename = std::enable_if_t<std::is_convertible<S (*)[], T (*)[]>::value>>
  constexpr span(const span<S, OtherExtents>& s) noexcept // NOLINT
      : pointer_{s.data()}, size_{s.size()} {}

  constexpr span(const span& s) noexcept = default;

  /// \name Subviews [span.sub]

  /// Returns a span of the first `Count`-many elements of this span.
  ///
  /// \tparam Count  Size of the returned subspan.
  ///
  /// \pre `0 <= Count && Count <= extent`.
  ///
  /// \throws Nothing.
  template <ptrdiff_t Count, typename = std::enable_if_t<0 <= Count>>
  constexpr span<element_type, Count> first() const {
    assert(Count <= size());
    return {pointer_, Count};
  }

  /// Returns a span of the first `count`-many elements of this span.
  ///
  /// \param[in] count  Size of the returned subspan.
  ///
  /// \pre `0 <= count && count <= extent`.
  ///
  /// \throws Nothing.
  constexpr span<element_type> first(index_type count) const {
    assert(0 <= count && count <= size());
    return {pointer_, count};
  }

  /// Returns a span of the last `Count`-many elements of this span.
  ///
  /// \tparam Count  Size of the returned subspan.
  ///
  /// \pre `0 <= Count && Count <= extent`.
  ///
  /// \throws Nothing.
  template <ptrdiff_t Count, typename = std::enable_if_t<0 <= Count>>
  constexpr span<element_type, Count> last() const {
    assert(Count <= size());
    return {pointer_ + (size() - Count), Count};
  }

  /// Returns a span of the last `count`-many elements of this span.
  ///
  /// \param[in] count  Size of the returned subspan.
  ///
  /// \pre `0 <= count && count <= extent`.
  ///
  /// \throws Nothing.
  constexpr span<element_type> last(index_type count) const {
    assert(0 <= count && count <= size());
    return {pointer_ + (extent - count), count};
  }

  /// Returns a subspan viewing `Count` many elements from offset `Offset`.
  ///
  /// \tparam Offset  the offset of the returned subspan.
  /// \tparam Count  Size of the returned subspan.
  ///
  /// \pre `0 <= Count && Count <= extent`.
  ///
  /// \throws Nothing.
  template <ptrdiff_t Offset, ptrdiff_t Count = dynamic_extent,
            typename = std::enable_if_t<0 <= Offset>>
  constexpr span<element_type, Count> subspan() const {
    assert(Offset <= size());
    assert(Count == dynamic_extent ||
               (0 <= Count && Count + Offset <= size()));
    return {pointer_ + Offset,
            Count == dynamic_extent ? size() - Offset : Count};
  }

  /// Returns a subspan viewing `count` many elements from offset `offset`.
  ///
  /// \param offset  the offset of the returned subspan.
  /// \param count  Size of the returned subspan.
  ///
  /// \pre `0 <= offset && offset <= extent`.
  /// \pre `count == dynamic_extent || 0 <= count && count + offset <= size()`.
  ///
  /// \throws Nothing.
  constexpr span<element_type>
  subspan(index_type offset, index_type count = dynamic_extent) const {
    assert(0 <= offset && offset <= size());
    assert(count == dynamic_extent ||
               (0 <= count && count + offset <= size()));
    return {pointer_ + offset,
            count == dynamic_extent ? size() - offset : count};
  }

  /// \name Observers [span.obs]

  /// Returns the number of elements in the span.
  ///
  /// \throws Nothing.
  constexpr index_type size() const noexcept { return size_; }

  /// Returns the number of bytes which are spanned by this span.
  ///
  /// \throws Nothing.
  constexpr index_type size_bytes() const noexcept { return sizeof(T) * size_; }

  /// Returns true if  `size() == 0`.
  ///
  /// \throws Nothing.
  constexpr bool empty() const noexcept { return size_ == 0; }

  /// \name Element access [span.elem]

  /// Returns the underlying pointer.
  ///
  /// \throws Nothing.
  constexpr pointer data() const noexcept { return pointer_; }

  /// Accesses the n-th element of the spanned array.
  ///
  /// \throws Nothing.
  constexpr reference operator[](index_type n) const { return pointer_[n]; }

  /// Accesses the n-th element of the spanned array.
  ///
  /// \throws Nothing.
  constexpr reference operator()(index_type n) const { return pointer_[n]; }

  /// \name Iterator support [span.iterators]

  /// Returns an iterator pointing to the first element of the span.
  ///
  /// \throws Nothing.
  constexpr iterator begin() const noexcept { return pointer_; }

  /// Returns a const iterator pointing to the first element of the span.
  ///
  /// \throws Nothing.
  constexpr const_iterator cbegin() const noexcept { return pointer_; }

  /// Returns an iterator pointing one after the last element of the span.
  ///
  /// \throws Nothing.
  constexpr iterator end() const noexcept { return pointer_ + size_; }

  /// Returns a const iterator pointing one after the last element of the span.
  ///
  /// \throws Nothing.
  constexpr const_iterator cend() const noexcept { return pointer_ + size_; }

  /// Returns a reverse iterator pointing to the last element of the span.
  ///
  /// \throws Nothing.
  constexpr reverse_iterator rbegin() const noexcept {
    return reverse_iterator(end());
  }

  /// Returns a const reverse iterator pointing to the last element of the span.
  ///
  /// \throws Nothing.
  constexpr const_reverse_iterator crbegin() const noexcept {
    return const_reverse_iterator(cend());
  }

  /// Returns a reverse iterator pointing to the first element of the span.
  ///
  /// \throws Nothing.
  constexpr reverse_iterator rend() const noexcept {
    return reverse_iterator(begin());
  }

  /// Returns a const reverse iterator pointing to the first element of the
  /// span.
  ///
  /// \throws Nothing.
  constexpr const_reverse_iterator crend() const noexcept {
    return const_reverse_iterator(cbegin());
  }

private:
  pointer pointer_{nullptr};
  index_type size_{0};
};

//#ifdef __cpp_deduction_guides

template <class T, typename I> span(T*, I)->span<T>;

template <class T, size_t N>
span(T (&)[N])->span<T, static_cast<std::ptrdiff_t>(N)>;

template <class T, size_t N>
span(std::array<T, N>&)->span<T, static_cast<std::ptrdiff_t>(N)>;

template <class T, size_t N>
span(const std::array<T, N>&)->span<const T, static_cast<std::ptrdiff_t>(N)>;

template <class Container>
span(Container&)->span<typename Container::value_type>;

template <class Container>
span(const Container&)->span<const typename Container::value_type>;

//#endif

template <class T, size_t N>
auto make_span(T (&array)[N]) -> span<T, static_cast<std::ptrdiff_t>(N)> {
  return span<T, static_cast<std::ptrdiff_t>(N)>(array);
}

template <class T, size_t N>
auto make_span(std::array<T, N>& array)
    -> span<T, static_cast<std::ptrdiff_t>(N)> {
  return span<T, static_cast<std::ptrdiff_t>(N)>(array);
}

template <class T, size_t N>
auto make_span(const std::array<T, N>& array)
    -> span<const T, static_cast<std::ptrdiff_t>(N)> {
  return span<const T, static_cast<std::ptrdiff_t>(N)>(array);
}

template <class Container>
auto make_span(Container& array) -> span<typename Container::value_type> {
  return span<typename Container::value_type>(array);
}

template <class Container>
auto make_span(const Container& array)
    -> span<const typename Container::value_type> {
  return span<const typename Container::value_type>(array);
}

}

#endif // !SPAN_HPP


// Copyright (c) 2018 Maikel Nadolski
//
// Permission is hereby granted, free of charge, to any person obtaining a copy
// of this software and associated documentation files (the "Software"), to deal
// in the Software without restriction, including without limitation the rights
// to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
// copies of the Software, and to permit persons to whom the Software is
// furnished to do so, subject to the following conditions:
//
// The above copyright notice and this permission notice shall be included in
// all copies or substantial portions of the Software.
//
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
// OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
// SOFTWARE.

/// @file This file introduces `extents<E0, ..., En>`, a compact
/// multi-dimensional size type. Each integral extent `Ei` stands an upper bound
/// in dimension `i` and can either be a compile-time constant signed integral
/// value or `dynamic_extent`. Each compile-time sized extent does not take any
/// extra byte.

#ifndef FUB_CORE_MDSPAN_HPP
#define FUB_CORE_MDSPAN_HPP

namespace std::experimental {
/// This is the storage type for the extents class and only takes storage for
/// dynamic extents.
///
/// This class is also responsible for accessing all extents.
template <std::size_t Rank, std::size_t DynamicRank,
          std::ptrdiff_t... StaticExtents>
class ExtentsStorage_;

/// This is the class template specialisation if all extents are statically
/// known.
///
/// In this case no extra storage is going to be used.
template <std::size_t Rank, std::ptrdiff_t... StaticExtents>
class ExtentsStorage_<Rank, 0, StaticExtents...> {
public:
  static_assert(Rank == sizeof...(StaticExtents),
                "Rank does not match sizeof...(StaticExtents)!");

  // [mdspan.extents.obs], Observers of the domain multi-index space

  /// Returns sizeof...(StaticExtents)
  static constexpr std::size_t rank() noexcept { return Rank; }

  /// Returns 0.
  static constexpr std::size_t rank_dynamic() noexcept { return 0; }

  /// Returns the n-th Static Extent.
  static constexpr std::ptrdiff_t static_extent(std::size_t n) noexcept {
    const std::ptrdiff_t static_extents[Rank]{StaticExtents...};
    return static_extents[n];
  }

  /// Returns the N-th Extent.
  ///
  /// In this case where all extents are known at compile time, this returns
  /// `static_extent(n)`.
  constexpr std::ptrdiff_t extent(size_t n) const noexcept {
    return static_extent(n);
  }
};

template <std::size_t Rank, std::ptrdiff_t... StaticExtents>
class ExtentsStorage_<Rank, Rank, StaticExtents...> {
public:
  static_assert(Rank == sizeof...(StaticExtents),
                "Rank does not match sizeof...(StaticExtents)!");

  // [mdspan.extents.constructors]

  ExtentsStorage_() = default;

  template <typename... IndexType,
            typename = std::enable_if_t<conjunction<
                std::is_convertible<IndexType, std::ptrdiff_t>...>::value>,
            typename = std::enable_if_t<sizeof...(IndexType) == Rank>>
  constexpr explicit ExtentsStorage_(IndexType... extent) noexcept
      : m_dynamic_extents{static_cast<std::ptrdiff_t>(extent)...} {}

  constexpr explicit ExtentsStorage_(
      const std::array<std::ptrdiff_t, Rank>& extents) noexcept
      : m_dynamic_extents{extents} {}

  // [mdspan.extents.obs], Observers of the domain multi-index space

  /// Returns sizeof...(StaticExtents)
  static constexpr std::size_t rank() noexcept { return Rank; }

  /// Returns sizeof...(StaticExtents)
  static constexpr std::size_t rank_dynamic() noexcept { return Rank; }

  /// Returns dynamic_extent.
  static constexpr std::ptrdiff_t static_extent(std::size_t /* n */) noexcept {
    return dynamic_extent;
  }

  /// Returns the N-th Extent.
  constexpr std::ptrdiff_t extent(size_t n) const noexcept {
    return m_dynamic_extents[n];
  }

private:
  std::array<std::ptrdiff_t, Rank> m_dynamic_extents{};
};

template <std::size_t Rank, std::size_t RankDynamic,
          std::ptrdiff_t... StaticExtents>
class ExtentsStorage_ {
public:
  // [mdspan.extents.constructors]

  ExtentsStorage_() = default;

  template <typename... IndexType,
            typename = std::enable_if_t<conjunction<
                std::is_convertible<IndexType, std::ptrdiff_t>...>::value>,
            typename = std::enable_if_t<sizeof...(IndexType) == RankDynamic>>
  constexpr explicit ExtentsStorage_(IndexType... extent) noexcept
      : m_dynamic_extents{static_cast<std::ptrdiff_t>(extent)...} {}

  constexpr explicit ExtentsStorage_(
      const std::array<std::ptrdiff_t, RankDynamic>& extents) noexcept
      : m_dynamic_extents{extents} {}

  // [mdspan.extents.obs], Observers of the domain multi-index space

  /// Returns sizeof...(StaticExtents)
  static constexpr std::size_t rank() noexcept { return Rank; }

  /// Returns sizeof...(StaticExtents)
  static constexpr std::size_t rank_dynamic() noexcept { return RankDynamic; }

  /// Returns dynamic_extent.
  static constexpr std::ptrdiff_t static_extent(std::size_t n) noexcept {
    constexpr std::ptrdiff_t static_extents[Rank]{StaticExtents...};
    return static_extents[n];
  }

  /// Returns the N-th Extent.
  constexpr std::ptrdiff_t extent(size_t n) const noexcept {
    constexpr std::ptrdiff_t static_extents[Rank]{StaticExtents...};
    if (static_extents[n] != dynamic_extent) {
      return static_extents[n];
    }
    return m_dynamic_extents[find_dynamic_extent_index(n)];
  }

private:
  std::array<std::ptrdiff_t, RankDynamic> m_dynamic_extents{};

  static constexpr std::size_t
  find_dynamic_extent_index(std::size_t n) noexcept {
    constexpr std::ptrdiff_t static_extents[Rank]{StaticExtents...};
    std::size_t dynamic_extent_index = 0;
    for (std::size_t dim = 0; dim < n; ++dim) {
      if (static_extents[dim] == dynamic_extent) {
        ++dynamic_extent_index;
      }
    }
    return dynamic_extent_index;
  }
};

template <typename... IndexType>
constexpr std::size_t count_dynamic_extents(IndexType... extent) noexcept {
  constexpr std::size_t Rank = sizeof...(IndexType);
  std::ptrdiff_t extents[Rank]{static_cast<std::ptrdiff_t>(extent)...};
  std::size_t counter = 0;
  for (std::size_t dim = 0; dim < Rank; ++dim) {
    if (extents[dim] == dynamic_extent) {
      ++counter;
    }
  }
  return counter;
}

/// An extents object defines a multidimensional index space which is the
/// Cartesian product of integers extents `[0..N0) * [0..N1) * ...`
template <std::ptrdiff_t... StaticExtents>
class extents : private ExtentsStorage_<sizeof...(StaticExtents),
                                        count_dynamic_extents(StaticExtents...),
                                        StaticExtents...> {
private:
  using base_type = ExtentsStorage_<sizeof...(StaticExtents),
                                    count_dynamic_extents(StaticExtents...),
                                    StaticExtents...>;

public:
  // Type Definitions

  using index_type = std::ptrdiff_t;

  // [mdspan.extents.constructors]

  using base_type::base_type;

  // [mdspan.extents.static_observers]

  /// Returns sizeof...(StaticExtents)
  static constexpr std::size_t rank() noexcept { return base_type::rank(); }

  /// Returns sizeof...(StaticExtents)
  static constexpr std::size_t rank_dynamic() noexcept {
    return base_type::rank_dynamic();
  }

  /// Returns the `n`-th `StaticExtent`.
  static constexpr std::ptrdiff_t static_extent(std::size_t n) noexcept {
    return base_type::static_extent(n);
  }

  // [mdspan.extents.observers]

  /// Returns the `n`-th run-time extent.
  constexpr std::ptrdiff_t extent(size_t n) const noexcept {
    return base_type::extent(n);
  }
};

// [mdspan.extents.traits.is_extent]

/// \ingroup type-traits
/// This is true `std::true_type` iff `E` is `extents<Es...>`
/// for some `std::ptrdiff_t... Es`.
/// @{
template <typename E> struct is_extents : std::false_type {};
template <std::ptrdiff_t... StaticExtents>
struct is_extents<extents<StaticExtents...>> : std::true_type {};
template <typename E> static constexpr bool is_extents_v = is_extents<E>::value;
/// @}

/// Returns: `true` if `lhs.rank() == rhs.rank()` and `lhs.extents(r) ==
/// rhs.extents(r)` for all `r` in the range `[0, lhs.rank())`, or false
/// otherwise.
template <std::ptrdiff_t... StaticExtentsL, std::ptrdiff_t... StaticExtentsR>
constexpr bool operator==(const extents<StaticExtentsL...>& lhs,
                          const extents<StaticExtentsR...>& rhs) noexcept {
  if (lhs.rank() != rhs.rank()) {
    return false;
  }
  for (std::size_t r = 0; r < lhs.rank(); ++r) {
    if (lhs.extent(r) != rhs.extent(r)) {
      return false;
    }
  }
  return true;
}

template <std::ptrdiff_t... StaticExtentsL, std::ptrdiff_t... StaticExtentsR>
constexpr bool operator!=(const extents<StaticExtentsL...>& left,
                          const extents<StaticExtentsR...>& right) noexcept {
  return !(left == right);
}

template <std::ptrdiff_t... StaticExtents>
constexpr std::ptrdiff_t Size_(const extents<StaticExtents...> e) noexcept {
  const std::size_t rank = e.rank();
  std::ptrdiff_t size = 1;
  for (std::size_t r = 0; r < rank; ++r) {
    size *= e.extent(r);
  }
  return size;
}

/// This layout creates mappings which do row first indexing (as in Fortran).
///
/// It holds for all valid `i` and `j` the equation
/// \code mapping(i + 1, j) - mapping(1, j) == 1 \endcode
struct layout_left {

  /// This mapping does row first indexing (as in Fortran).
  ///
  /// It holds for all valid `i` and `j` the equation
  /// \code mapping(i + 1, j) - mapping(1, j) == 1 \endcode
  template <typename Extents> class mapping : private Extents {
  public:
    static_assert(is_extents_v<Extents>,
                  "Extents must satisfy the extents concept.");

    /// \name Constructors / Destructors
    /// @{
    constexpr mapping() = default;
    constexpr mapping(const mapping&) = default;
    constexpr mapping(mapping&&) = default;
    mapping& operator=(const mapping& other) noexcept = default;
    mapping& operator=(mapping&& other) noexcept = default;

    /// Implicit Conversion from Extents.
    ///
    /// \throws Nothing.
    ///
    /// \post extents() == extents.
    constexpr mapping(const Extents& extents) : Extents{extents} {} // NOLINT
    /// @}

    /// \name Observers
    /// @{
    constexpr const Extents& extents() const noexcept { return *this; }

    constexpr std::ptrdiff_t required_span_size() const noexcept {
      return Size_(extents());
    }

    /// \return Returns the codomain index for specified multi dimensional index
    /// coordinates.
    ///
    /// \effect Equivalent to offset in
    /// \code
    ///    index_type offset = 0;
    ///    for(size_t k = 0; k < Extents::rank(); ++k) {
    ///      offset += i[k] * stride(k);
    ///    }
    /// \endcode
    /// \throws Nothing.
    template <
        typename... IndexType,
        typename = std::enable_if_t<conjunction<
            std::is_convertible<IndexType, std::ptrdiff_t>...>::value>,
        typename = std::enable_if_t<(sizeof...(IndexType) == Extents::rank())>>
    constexpr std::ptrdiff_t operator()(IndexType... indices) const noexcept {
      return DoMapping_(make_index_sequence<Extents::rank()>(), indices...);
    }

    /// \return Returns the stride value in a specified dimension r.
    ///
    /// \throws Nothing.
    constexpr std::ptrdiff_t stride(std::size_t r) const noexcept {
      std::ptrdiff_t stride = 1;
      for (std::size_t dim = 0; dim < r; ++dim) {
        stride *= extents().extent(dim);
      }
      return stride;
    }

    static constexpr bool is_always_unique() noexcept { return true; }
    static constexpr bool is_always_contiguous() noexcept { return true; }
    static constexpr bool is_always_strided() noexcept { return true; }

    constexpr bool is_unique() const noexcept { return true; }
    constexpr bool is_contiguous() const noexcept { return true; }
    constexpr bool is_strided() const noexcept { return true; }

    template <class OtherExtents>
    constexpr bool operator==(const mapping<OtherExtents>& other) const
        noexcept {
      return extents() == other.extents();
    }

    template <class OtherExtents>
    constexpr bool operator!=(const mapping<OtherExtents>& other) const
        noexcept {
      return !(*this == other);
    }
    /// @}

  private:
    template <std::size_t... Is, typename... IndexType>
    constexpr std::ptrdiff_t DoMapping_(index_sequence<Is...>,
                                        IndexType... indices) const noexcept {
      const std::ptrdiff_t is[Extents::rank()]{
          static_cast<std::ptrdiff_t>(indices)...};
      const std::ptrdiff_t strides[Extents::rank()]{stride(Is)...};
      std::ptrdiff_t index = 0;
      for (std::size_t r = 0; r < Extents::rank(); ++r) {
        index += strides[r] * is[r];
      }
      return index;
    }
  };
};

struct layout_right {
  template <typename Extents> class mapping : private Extents {
  public:
    constexpr mapping() = default;
    constexpr mapping(const mapping&) = default;
    constexpr mapping(mapping&&) = default;
    mapping& operator=(const mapping&) noexcept = default;
    mapping& operator=(mapping&&) noexcept = default;

    constexpr mapping(const Extents& extents) : Extents{extents} {}

    constexpr const Extents& extents() const noexcept { return *this; }

    constexpr std::ptrdiff_t required_span_size() const noexcept {
      return Size_(extents());
    }

    template <
        typename... IndexType,
        typename = std::enable_if_t<conjunction<
            std::is_convertible<IndexType, std::ptrdiff_t>...>::value>,
        typename = std::enable_if_t<(sizeof...(IndexType) == Extents::rank())>>
    constexpr std::ptrdiff_t operator()(IndexType... indices) const noexcept {
      return DoMapping_(make_index_sequence<Extents::rank()>(), indices...);
    }

    constexpr std::ptrdiff_t stride(std::size_t r) const noexcept {
      std::ptrdiff_t stride = 1;
      for (std::size_t dim = r + 1; dim < Extents::rank(); ++dim) {
        stride *= extents().extent(dim);
      }
      return stride;
    }

    static constexpr bool is_always_unique() noexcept { return true; }
    static constexpr bool is_always_contiguous() noexcept { return true; }
    static constexpr bool is_always_strided() noexcept { return true; }

    constexpr bool is_unique() const noexcept { return true; }
    constexpr bool is_contiguous() const noexcept { return true; }
    constexpr bool is_strided() const noexcept { return true; }

    template <class OtherExtents>
    constexpr bool operator==(const mapping<OtherExtents>& other) const
        noexcept {
      return extents() == other.extents();
    }

    template <class OtherExtents>
    constexpr bool operator!=(const mapping<OtherExtents>& other) const
        noexcept {
      return !(*this == other);
    }

  private:
    template <std::size_t... Is, typename... IndexType>
    constexpr std::ptrdiff_t DoMapping_(index_sequence<Is...>,
                                        IndexType... indices) const noexcept {
      const std::ptrdiff_t is[Extents::rank()]{
          static_cast<std::ptrdiff_t>(indices)...};
      const std::ptrdiff_t strides[Extents::rank()]{stride(Is)...};
      std::ptrdiff_t index = 0;
      for (std::size_t r = 0; r < Extents::rank(); ++r) {
        index += strides[r] * is[r];
      }
      return index;
    }
  };
};

struct layout_stride {
  template <class Extents> class mapping : private Extents {
  public:
    // [mdspan.layout.stride.cons], layout_stride::mapping constructors
    constexpr mapping() = default;

    constexpr mapping(
        const Extents& e,
        const std::array<std::ptrdiff_t, Extents::rank()>& s) noexcept
        : Extents(e), strides_(s) {}

    std::array<std::ptrdiff_t, Extents::rank()>
    MakeStrides(const layout_left::mapping<Extents>& other) {
      std::array<std::ptrdiff_t, Extents::rank()> strides;
      for (std::size_t s = 0; s < Extents::rank(); ++s) {
        strides[s] = other.stride(s);
      }
      return strides;
    }

    constexpr mapping(const layout_left::mapping<Extents>& other)
        : mapping(other.extents(), MakeStrides(other)) {}

    // [mdspan.layout.stride.ops], layout_stride::mapping operations
    constexpr const Extents& extents() const noexcept { return *this; }

    constexpr const std::array<std::ptrdiff_t, Extents::rank()>& strides() const
        noexcept {
      return strides_;
    }

    constexpr std::ptrdiff_t required_span_size() const noexcept {
      std::ptrdiff_t max = extents().extent(0) * strides_[0];
      for (std::size_t r = 1; r < Extents::rank(); ++r) {
        max = std::max(extents().extent(r) * strides_[r], max);
      }
      return max;
    }

    template <
        typename... IndexType,
        typename = std::enable_if_t<conjunction<
            std::is_convertible<IndexType, std::ptrdiff_t>...>::value>,
        typename = std::enable_if_t<(sizeof...(IndexType) == Extents::rank())>>
    std::ptrdiff_t operator()(IndexType... is) const {
      const std::array<std::ptrdiff_t, Extents::rank()> idx{
          static_cast<std::ptrdiff_t>(is)...};
      std::ptrdiff_t offset = 0;
      for (std::size_t r = 0; r < Extents::rank(); ++r) {
        offset += idx[r] * strides_[r];
      }
      return offset;
    }

    static constexpr bool is_always_unique() noexcept { return true; }
    static constexpr bool is_always_contiguous() noexcept { return false; }
    static constexpr bool is_always_strided() noexcept { return true; }

    constexpr bool is_unique() const noexcept { return true; }
    constexpr bool is_contiguous() const noexcept { return false; }
    constexpr bool is_strided() const noexcept { return true; }

    std::ptrdiff_t stride(size_t rank) const noexcept { return strides_[rank]; }

    template <class OtherExtents>
    constexpr bool operator==(const mapping<OtherExtents>& other) const
        noexcept {
      return extents() == other.extents();
    }
    template <class OtherExtents>
    constexpr bool operator!=(const mapping<OtherExtents>& other) const
        noexcept {
      return !(*this == other);
    }

  private:
    std::array<std::ptrdiff_t, Extents::rank()> strides_;
  };
};

template <class ElementType> struct accessor_basic {
  using offset_policy = accessor_basic;
  using element_type = ElementType;
  using reference = ElementType&;
  using pointer = ElementType*;

  constexpr pointer offset(pointer p, ptrdiff_t i) const noexcept {
    return p + i;
  }

  constexpr reference access(pointer p, ptrdiff_t i) const noexcept {
    return *offset(p, i);
  }

  constexpr pointer decay(pointer p) const noexcept { return p; }
};

template <class ElementType, class Extents, class LayoutPolicy = layout_right,
          class AccessorPolicy = accessor_basic<ElementType>>
class mdspan : AccessorPolicy, LayoutPolicy::template mapping<Extents> {
public:
  // Domain and codomain types
  using extents_type = Extents;
  using layout_type = LayoutPolicy;
  using accessor_type = AccessorPolicy;
  using mapping_type = typename layout_type::template mapping<extents_type>;
  using element_type = typename accessor_type::element_type;
  using value_type = std::remove_cv_t<element_type>;
  using index_type = std::ptrdiff_t;
  using difference_type = std::ptrdiff_t;
  using pointer = typename accessor_type::pointer;
  using reference = typename accessor_type::reference;

  // [mdspan.basic.cons], mdspan constructors, assignment, and destructor
  constexpr mdspan() noexcept = default;
  constexpr mdspan(const mdspan&) noexcept = default;
  constexpr mdspan(mdspan&&) noexcept = default;

  template <class... IndexType,
            typename = std::enable_if_t<conjunction<
                std::is_convertible<IndexType, std::ptrdiff_t>...>::value>,
            typename = std::enable_if_t<sizeof...(IndexType) ==
                                        Extents::rank_dynamic()>>
  explicit constexpr mdspan(pointer p, IndexType... dynamic_extents)
      : mdspan(p, Extents(dynamic_extents...)) {}

  template <class IndexType, std::size_t N>
  explicit constexpr mdspan(
      pointer p, const std::array<IndexType, N>& dynamic_extents)
      : mdspan(p, extents_type{dynamic_extents}) {}

  constexpr mdspan(pointer p, const mapping_type& m)
      : accessor_type(), mapping_type(m), ptr_(p) {}

  constexpr mdspan(pointer p, const mapping_type& m,
                         const accessor_type& a)
      : accessor_type(a), mapping_type(m), ptr_(p) {}

  template <class OtherElementType, class OtherExtents, class OtherLayoutPolicy,
            class OtherAccessorPolicy>
  constexpr mdspan(
      const mdspan<OtherElementType, OtherExtents, OtherLayoutPolicy,
                         OtherAccessorPolicy>& other)
      : accessor_type(), mapping_type(other.mapping()), ptr_(other.data()) {}

  ~mdspan() = default;

  constexpr mdspan& operator=(const mdspan&) noexcept = default;
  constexpr mdspan& operator=(mdspan&&) noexcept = default;

  template <class OtherElementType, class OtherExtents, class OtherLayoutPolicy,
            class OtherAccessorPolicy>
  constexpr mdspan& operator=(
      const mdspan<OtherElementType, OtherExtents, OtherLayoutPolicy,
                         OtherAccessorPolicy>& other) noexcept {
    static_cast<mapping_type&>(*this) = other.mapping();
    ptr_ = other.data();
    return *this;
  }

  // [mdspan.basic.mapping], mdspan mapping domain multi-index to access
  // codomain element
  constexpr reference operator[](index_type i) const noexcept {
    return this->operator()(i);
  }

  template <class... IndexType>
  constexpr reference operator()(IndexType... indices) const noexcept {
    const accessor_type acc = accessor();
    const mapping_type map = mapping();
    return acc.access(ptr_, map(indices...));
  }

  template <class IndexType, size_t N>
  constexpr reference operator()(const std::array<IndexType, N>& indices) const
      noexcept {
    const accessor_type acc = accessor();
    const mapping_type map = mapping();
    return acc.access(ptr_, std::apply(map, indices));
  }

  // [mdspan.basic.domobs], mdspan observers of the domain
  // multidimensional index space

  static constexpr int rank() noexcept { return Extents::rank(); }

  static constexpr int rank_dynamic() noexcept {
    return Extents::rank_dynamic();
  }

  static constexpr index_type static_extent(std::size_t rank) noexcept {
    return Extents::static_extent(rank);
  }

  constexpr Extents extents() const noexcept { return mapping().extents(); }

  constexpr index_type extent(std::size_t rank) const noexcept {
    return extents().extent(rank);
  }

  constexpr index_type size() const noexcept { return Size_(extents()); }

  constexpr index_type unique_size() const noexcept { return size(); }

  // [mdspan.basic.codomain], mdspan observers of the codomain
  constexpr span<element_type> get_span() const noexcept {
    return {accessor().decay(ptr_), mapping().required_span_size()};
  }

  constexpr pointer data() const noexcept { return ptr_; }

  // [mdspan.basic.obs], mdspan observers of the mapping
  static constexpr bool is_always_unique() noexcept {
    return mapping_type::is_always_unique();
  }
  static constexpr bool is_always_contiguous() noexcept {
    return mapping_type::is_always_contiguous();
  }
  static constexpr bool is_always_strided() noexcept {
    return mapping_type::is_always_strided();
  }

  constexpr mapping_type mapping() const noexcept { return *this; }
  constexpr accessor_type accessor() const noexcept { return *this; }
  constexpr bool is_unique() const noexcept { return mapping().is_unique(); }
  constexpr bool is_contiguous() const noexcept {
    return mapping().is_contiguous();
  }
  constexpr bool is_strided() const noexcept { return mapping().is_strided(); }

  constexpr index_type stride(std::size_t r) const {
    return mapping().stride(r);
  }

private:
  pointer ptr_{};
};

template <typename T, ptrdiff_t... Extents>
using static_mdspan = mdspan<T, extents<Extents...>>;

template <typename T> struct dynamic_extents_;

template <typename I, I... Is>
struct dynamic_extents_<integer_sequence<I, Is...>> {
  using type = extents<((void)Is, dynamic_extent)...>;
};

template <std::size_t Rank>
using dynamic_extents =
    typename dynamic_extents_<make_index_sequence<Rank>>::type;

// template <typename T, std::size_t Rank, typename Layout = layout_right>
// using DynamicMdSpan = mdspan<T, dynamic_extents<Rank>, Layout>;

template <typename T, std::size_t Rank, typename Layout = layout_left>
using dynamic_mdspan = mdspan<T, dynamic_extents<Rank>, Layout>;

template <typename T, typename E, typename A = accessor_basic<T>>
using strided_mdspan = mdspan<T, E, layout_stride, A>;

struct all_type {
  explicit all_type() = default;
};
static constexpr all_type all = all_type{};

/// \cond INTERNAL
template <typename T>
struct IsSliceRange_
    : disjunction<
          std::is_convertible<T, std::pair<std::ptrdiff_t, std::ptrdiff_t>>,
          std::is_convertible<T, all_type>> {};

template <typename I, typename... Is> constexpr I Accumulate_(I x0, Is... xi) {
  const I x[] = {x0, xi...};
  constexpr int size = 1 + static_cast<int>(sizeof...(Is));
  I total = I{};
  for (int i = 0; i < size; ++i) {
    total += x[i];
  }
  return total;
}

template <typename... SliceSpecifiers>
static constexpr std::size_t SliceRank_ =
    Accumulate_(static_cast<int>(IsSliceRange_<SliceSpecifiers>::value)...);
/// \endcond

// [mdspan.subspan], subspan creation
template <class ElementType, class Extents, class LayoutPolicy,
          class AccessorPolicy, class... SliceSpecifiers>
struct mdspan_subspan { // exposition only
  static constexpr std::size_t slice_rank = SliceRank_<SliceSpecifiers...>;
  using extents_t = dynamic_extents<slice_rank>;
  using layout_t = layout_stride;
  using type = mdspan<ElementType, extents_t, layout_t,
                            typename AccessorPolicy::offset_policy>;
};

template <class ElementType, class Extents, class LayoutPolicy,
          class AccessorPolicy, class... SliceSpecifiers>
using mdspan_subspan_t = // exposition only
    typename mdspan_subspan<ElementType, Extents, LayoutPolicy, AccessorPolicy,
                            SliceSpecifiers...>::type;

constexpr std::ptrdiff_t
SliceExtent_(const std::pair<std::ptrdiff_t, std::ptrdiff_t>& p) {
  assert(p.first <= p.second);
  assert(0 <= p.first);
  return p.second - p.first;
}

/// \cond INTERNAL
constexpr std::ptrdiff_t SliceExtent_(all_type) { return dynamic_extent; }

template <typename T, typename = std::enable_if_t<!IsSliceRange_<T>::value>>
constexpr std::ptrdiff_t SliceExtent_(T) {
  return 0;
}

template <std::size_t Rank, typename Slice>
constexpr std::array<std::ptrdiff_t, Rank + 1>
SlicePushBack__(std::true_type, std::array<std::ptrdiff_t, Rank> array,
                Slice slice) {
  std::array<std::ptrdiff_t, Rank + 1> grown{};
  for (std::size_t i = 0; i < Rank; ++i) {
    grown[i] = array[i];
  }
  grown[Rank] = SliceExtent_(slice);
  return grown;
}

template <std::size_t Rank, typename Slice>
constexpr std::array<std::ptrdiff_t, Rank>
SlicePushBack__(std::false_type, std::array<std::ptrdiff_t, Rank> array,
                Slice /* slice */) {
  return array;
}

template <std::size_t Rank, typename Slice>
constexpr auto SlicePushBack_(std::array<std::ptrdiff_t, Rank> array,
                              Slice slice) {
  return SlicePushBack__(IsSliceRange_<Slice>(), array, slice);
}

template <std::size_t Rank>
constexpr auto MakeSliceExtents__(std::array<std::ptrdiff_t, Rank> result) {
  return result;
}

template <std::size_t Rank, typename Slice, typename... Rest>
constexpr auto MakeSliceExtents__(std::array<std::ptrdiff_t, Rank> prev,
                                  Slice slice, Rest... slices) {
  return MakeSliceExtents__(SlicePushBack_(prev, slice), slices...);
}

template <typename... Slices>
constexpr auto MakeSliceExtents_(Slices... slices) {
  return MakeSliceExtents__(std::array<std::ptrdiff_t, 0>{}, slices...);
}

template <class ElementType, class Extents, class LayoutPolicy,
          class AccessorPolicy, std::size_t... Is>
constexpr std::array<std::ptrdiff_t, sizeof...(Is)> MakeStrideArray_(
    const mdspan<ElementType, Extents, LayoutPolicy, AccessorPolicy>& src,
    index_sequence<Is...>) {
  return {src.stride(Is)...};
}

template <typename T> struct Type_ {};

template <std::size_t N, std::size_t... Is>
constexpr std::array<std::size_t, N> AsStdArray__(const std::size_t (&array)[N],
                                                  index_sequence<Is...>) {
  return {array[Is]...};
}

template <std::size_t N>
constexpr std::array<std::size_t, N>
AsStdArray_(const std::size_t (&array)[N]) {
  return AsStdArray__(array, make_index_sequence<N>());
}

template <typename... Slices>
constexpr std::array<std::size_t, SliceRank_<Slices...>>
MakeRangeIndices__(Type_<Slices>... /* slices */) {
  constexpr std::size_t is_range[] = {IsSliceRange_<Slices>::value...};
  std::size_t ranges[SliceRank_<Slices...>]{};
  std::size_t ri = 0;
  for (std::size_t i = 0; i < sizeof...(Slices); ++i) {
    if (is_range[i]) {
      ranges[ri++] = i;
    }
  }
  return AsStdArray_(ranges);
}

template <typename... Slices, std::size_t... Is>
constexpr auto MakeRangeIndices_(index_sequence<Is...>,
                                 Type_<Slices>... /* slices */) {
  constexpr std::array<std::size_t, SliceRank_<Slices...>> indices{
      MakeRangeIndices__(Type_<Slices>{}...)};
  return index_sequence<indices[Is]...>{};
}

template <typename... Slices>
constexpr auto MakeRangeIndices_(Type_<Slices>... slices) {
  return MakeRangeIndices_(make_index_sequence<SliceRank_<Slices...>>{},
                           slices...);
}

template <typename... Slices> constexpr auto MakeRangeIndices(Slices...) {
  return MakeRangeIndices_(Type_<Slices>{}...);
}

template <class ElementType, class Extents, class LayoutPolicy,
          class AccessorPolicy, typename... Slices>
constexpr auto MakeSliceArray_(
    const mdspan<ElementType, Extents, LayoutPolicy, AccessorPolicy>& src,
    Slices...) {
  constexpr auto range_indices = MakeRangeIndices_(Type_<Slices>{}...);
  return MakeStrideArray_(src, range_indices);
}

constexpr std::ptrdiff_t MakeOrigin__(std::ptrdiff_t n) { return n; }

constexpr std::ptrdiff_t
MakeOrigin__(std::pair<std::ptrdiff_t, std::ptrdiff_t> p) {
  return p.first;
}

constexpr std::ptrdiff_t MakeOrigin__(all_type /* all */) { return 0; }

template <typename... Slices>
constexpr std::array<std::ptrdiff_t, sizeof...(Slices)>
MakeOrigin_(Slices... slices) {
  return {MakeOrigin__(slices)...};
}

template <std::size_t... Is, typename F, std::size_t N>
constexpr auto Apply_(index_sequence<Is...>, F fn,
                      std::array<std::ptrdiff_t, N> indices) {
  return fn(indices[Is]...);
}

template <typename F, std::size_t N>
constexpr auto Apply_(F fn, std::array<std::ptrdiff_t, N> indices) {
  return Apply_(make_index_sequence<N>{}, fn, indices);
}

constexpr std::ptrdiff_t MapToLength_(all_type) { return -1; }

constexpr std::ptrdiff_t
MapToLength_(const std::pair<std::ptrdiff_t, std::ptrdiff_t>& rng) {
  return rng.second - rng.first;
}

template <typename T, typename = std::enable_if_t<!IsSliceRange_<T>()>>
constexpr std::ptrdiff_t MapToLength_(T) {
  return 0;
}

template <typename Extents, typename... SliceSpecifiers>
constexpr std::array<std::ptrdiff_t, SliceRank_<SliceSpecifiers...>>
MakeSliceExtents2_(const Extents& e, SliceSpecifiers... slices) {
  const std::array<std::ptrdiff_t, Extents::rank()> length{
      MapToLength_(slices)...};
  std::array<std::ptrdiff_t, Extents::rank()> dyn_length{};
  for (std::size_t i = 0; i < Extents::rank(); ++i) {
    if (length[i] < 0) {
      dyn_length[i] = e.extent(i);
    } else {
      dyn_length[i] = length[i];
    }
  }
  std::array<std::ptrdiff_t, SliceRank_<SliceSpecifiers...>> extents{};
  std::size_t slice = 0;
  for (std::size_t i = 0; i < Extents::rank(); ++i) {
    if (dyn_length[i] > 0) {
      extents[slice] = dyn_length[i];
      slice = slice + 1;
    }
  return extents;
  }
}
/// \endcond

template <class ElementType, class Extents, class LayoutPolicy,
          class AccessorPolicy, class... SliceSpecifiers>
mdspan_subspan_t<ElementType, Extents, LayoutPolicy, AccessorPolicy,
                 SliceSpecifiers...>
subspan(
    const mdspan<ElementType, Extents, LayoutPolicy, AccessorPolicy>& src,
    SliceSpecifiers... slices) noexcept {
  const std::array<std::ptrdiff_t, Extents::rank()> origin =
      MakeOrigin_(slices...);
  const auto map = src.mapping();
  const auto acc = src.accessor();
  constexpr std::size_t slice_rank = SliceRank_<SliceSpecifiers...>;
  using SliceExtents = dynamic_extents<slice_rank>;
  const SliceExtents extents{MakeSliceExtents2_(src.extents(), slices...)};
  const std::array<std::ptrdiff_t, slice_rank> slice_array =
      MakeSliceArray_(src, slices...);
  const layout_stride::mapping<SliceExtents> slice_mapping(extents,
                                                           slice_array);
  return {acc.offset(src.data(), Apply_(map, origin)), slice_mapping};
}

template <typename> struct is_mdspan : std::false_type {};

template <typename T, typename E, typename L, typename A>
struct is_mdspan<mdspan<T, E, L, A>> : std::true_type {};

template <typename T> static constexpr bool is_mdspan_v = is_mdspan<T>::value;

}
#endif