#pragma once

#include <array>
#include <cstddef>
#include <limits>
#include <type_traits>

inline constexpr std::size_t dynamic_extent = std::numeric_limits<std::size_t>::max();

template <typename ElementType, std::size_t Extent = dynamic_extent>
class span;

namespace detail
{

template <typename E, std::size_t S>
struct span_storage {
    constexpr span_storage() noexcept = default;

    constexpr span_storage(E* p_ptr, std::size_t /*unused*/) noexcept : ptr(p_ptr) {}

    E*                           ptr  = nullptr;
    static constexpr std::size_t size = S;
};

template <typename E>
struct span_storage<E, dynamic_extent> {
    constexpr span_storage() noexcept = default;

    constexpr span_storage(E* p_ptr, std::size_t p_size) noexcept : ptr(p_ptr), size(p_size) {}

    E*          ptr  = nullptr;
    std::size_t size = 0;
};

using std::void_t;

template <typename T>
using uncvref_t = typename std::remove_cv_t<std::remove_reference_t<T>>;

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

template <typename T, std::size_t S>
struct is_span<span<T, S>> : std::true_type {
};

template <typename T>
static constexpr auto is_span_v = is_span<T>::value;

template <typename>
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>
static constexpr auto is_std_array_v = is_std_array<T>::value;

template <typename, typename = void>
struct has_size_and_data : std::false_type {
};

template <typename T>
struct has_size_and_data<T, void_t<decltype(std::size(std::declval<T>())), decltype(std::data(std::declval<T>()))>>
    : std::true_type {
};

template <typename T>
static constexpr auto has_size_and_data_v = has_size_and_data<T>::value;

template <typename C, typename U = uncvref_t<C>>
struct is_container {
    static constexpr bool value = !is_span_v<U> && !is_std_array_v<U> && !std::is_array_v<U> && has_size_and_data_v<C>;
};

template <typename C>
static constexpr auto is_container_v = is_container<C>::value;

template <typename T>
using remove_pointer_t = std::remove_pointer_t<T>;

template <typename, typename, typename = void>
struct is_container_element_type_compatible : std::false_type {
};

template <typename T, typename E>
struct is_container_element_type_compatible<
    T,
    E,
    typename std::enable_if<
        !std::is_same_v<std::remove_cv_t<decltype(std::data(std::declval<T>()))>, void>
        && std::is_convertible_v<remove_pointer_t<decltype(std::data(std::declval<T>()))> (*)[], E (*)[]>>::type>
    : std::true_type {
};

template <typename T, typename E>
static constexpr auto is_container_element_type_compatible_v = is_container_element_type_compatible<T, E>::value;

template <typename, typename = size_t>
struct is_complete : std::false_type {
};

template <typename T>
struct is_complete<T, decltype(sizeof(T))> : std::true_type {
};

template <typename T>
static constexpr auto is_complete_v = is_complete<T>::value;

} // namespace detail

template <typename ElementType, std::size_t Extent>
class span
{
    static_assert(std::is_object_v<ElementType>,
                  "A span's ElementType must be an object type (not a "
                  "reference type or void)");
    static_assert(detail::is_complete_v<ElementType>,
                  "A span's ElementType must be a complete type (not a forward "
                  "declaration)");
    static_assert(!std::is_abstract_v<ElementType>, "A span's ElementType cannot be an abstract class type");

    using storage_type = detail::span_storage<ElementType, Extent>;

public:
    // constants and types
    using element_type     = ElementType;
    using value_type       = std::remove_cv_t<ElementType>;
    using size_type        = std::size_t;
    using difference_type  = std::ptrdiff_t;
    using pointer          = element_type*;
    using const_pointer    = const element_type*;
    using reference        = element_type&;
    using const_reference  = const element_type&;
    using iterator         = pointer;
    using reverse_iterator = std::reverse_iterator<iterator>;

    static constexpr size_type extent = Extent;

    // [span.cons], span constructors, copy, assignment, and destructor
    template <std::size_t E = Extent, typename std::enable_if_t<(E == dynamic_extent || E <= 0), int> = 0>
    constexpr span() noexcept
    {
    }

    constexpr span(pointer ptr, size_type count) : storage_(ptr, count) { assert(extent == dynamic_extent || count == extent); }

    constexpr span(pointer first_elem, pointer last_elem) : storage_(first_elem, last_elem - first_elem)
    {
        assert(extent == dynamic_extent || last_elem - first_elem == static_cast<std::ptrdiff_t>(extent));
    }

    template <std::size_t N,
              std::size_t E = Extent,
              typename      = std::enable_if_t<(E == dynamic_extent || N == E)
                                               && detail::is_container_element_type_compatible_v<element_type (&)[N], ElementType>>>
    constexpr span(element_type (&arr)[N]) noexcept : storage_(arr, N)
    {
    }

    template <typename T,
              std::size_t N,
              std::size_t E = Extent,
              typename      = std::enable_if_t<(E == dynamic_extent || N == E)
                                               && detail::is_container_element_type_compatible_v<std::array<T, N>&, ElementType>>>
    constexpr span(std::array<T, N>& arr) noexcept : storage_(arr.data(), N)
    {
    }

    template <
        typename T,
        std::size_t N,
        std::size_t E = Extent,
        typename      = std::enable_if_t<(E == dynamic_extent || N == E)
                                         && detail::is_container_element_type_compatible_v<const std::array<T, N>&, ElementType>>>
    constexpr span(const std::array<T, N>& arr) noexcept : storage_(arr.data(), N)
    {
    }

    template <typename Container,
              std::size_t E = Extent,
              typename      = std::enable_if_t<E == dynamic_extent && detail::is_container_v<Container>
                                               && detail::is_container_element_type_compatible_v<Container&, ElementType>>>
    constexpr span(Container& cont) : storage_(std::data(cont), std::size(cont))
    {
    }

    template <typename Container,
              std::size_t E = Extent,
              typename      = std::enable_if_t<E == dynamic_extent && detail::is_container_v<Container>
                                               && detail::is_container_element_type_compatible_v<const Container&, ElementType>>>
    constexpr span(const Container& cont) : storage_(std::data(cont), std::size(cont))
    {
    }

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

    template <typename OtherElementType,
              std::size_t OtherExtent,
              typename = std::enable_if_t<(Extent == dynamic_extent || OtherExtent == dynamic_extent || Extent == OtherExtent)
                                          && std::is_convertible_v<OtherElementType (*)[], ElementType (*)[]>>>
    constexpr span(const span<OtherElementType, OtherExtent>& other) noexcept : storage_(other.data(), other.size())
    {
    }

    ~span() noexcept = default;

    constexpr span& operator=(const span& other) noexcept = default;

    // [span.sub], span subviews
    template <std::size_t Count>
    constexpr span<element_type, Count> first() const
    {
        assert(Count <= size());
        return {data(), Count};
    }

    template <std::size_t Count>
    constexpr span<element_type, Count> last() const
    {
        assert(Count <= size());
        return {data() + (size() - Count), Count};
    }

    template <std::size_t Offset, std::size_t Count = dynamic_extent>
    using subspan_return_t =
        span<ElementType, Count != dynamic_extent ? Count : (Extent != dynamic_extent ? Extent - Offset : dynamic_extent)>;

    template <std::size_t Offset, std::size_t Count = dynamic_extent>
    constexpr subspan_return_t<Offset, Count> subspan() const
    {
        assert(Offset <= size() && (Count == dynamic_extent || Offset + Count <= size()));
        return {data() + Offset, Count != dynamic_extent ? Count : size() - Offset};
    }

    constexpr span<element_type, dynamic_extent> first(size_type count) const
    {
        assert(count <= size());
        return {data(), count};
    }

    constexpr span<element_type, dynamic_extent> last(size_type count) const
    {
        assert(count <= size());
        return {data() + (size() - count), count};
    }

    constexpr span<element_type, dynamic_extent> subspan(size_type offset, size_type count = dynamic_extent) const
    {
        assert(offset <= size() && (count == dynamic_extent || offset + count <= size()));
        return {data() + offset, count == dynamic_extent ? size() - offset : count};
    }

    // [span.obs], span observers
    constexpr size_type size() const noexcept { return storage_.size; }

    constexpr size_type size_bytes() const noexcept { return size() * sizeof(element_type); }

    [[nodiscard]] constexpr bool empty() const noexcept { return size() == 0; }

    // [span.elem], span element access
    constexpr reference operator[](size_type idx) const
    {
        assert(idx < size());
        return *(data() + idx);
    }

    constexpr reference front() const
    {
        assert(!empty());
        return *data();
    }

    constexpr reference back() const
    {
        assert(!empty());
        return *(data() + (size() - 1));
    }

    constexpr pointer data() const noexcept { return storage_.ptr; }

    // [span.iterators], span iterator support
    constexpr iterator begin() const noexcept { return data(); }

    constexpr iterator end() 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()); }

private:
    storage_type storage_{};
};

/* Deduction Guides */
template <class T, size_t N>
span(T (&)[N]) -> span<T, N>;

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>;

template <class Container>
span(Container&) -> span<std::remove_reference_t<decltype(*std::data(std::declval<Container&>()))>>;

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

template <typename ElementType, std::size_t Extent>
constexpr span<ElementType, Extent> make_span(span<ElementType, Extent> s) noexcept
{
    return s;
}

template <typename T, std::size_t N>
constexpr span<T, N> make_span(T (&arr)[N]) noexcept
{
    return {arr};
}

template <typename T, std::size_t N>
constexpr span<T, N> make_span(std::array<T, N>& arr) noexcept
{
    return {arr};
}

template <typename T, std::size_t N>
constexpr span<const T, N> make_span(const std::array<T, N>& arr) noexcept
{
    return {arr};
}

template <typename Container>
constexpr span<std::remove_reference_t<decltype(*std::data(std::declval<Container&>()))>> make_span(Container& cont)
{
    return {cont};
}

template <typename Container>
constexpr span<const typename Container::value_type> make_span(const Container& cont)
{
    return {cont};
}

template <typename ElementType, std::size_t Extent>
span<const std::byte, ((Extent == dynamic_extent) ? dynamic_extent : sizeof(ElementType) * Extent)> as_bytes(
    span<ElementType, Extent> s) noexcept
{
    return {reinterpret_cast<const std::byte*>(s.data()), s.size_bytes()};
}

template <class ElementType, size_t Extent, typename = std::enable_if_t<!std::is_const_v<ElementType>>>
span<std::byte, ((Extent == dynamic_extent) ? dynamic_extent : sizeof(ElementType) * Extent)> as_writable_bytes(
    span<ElementType, Extent> s) noexcept
{
    return {reinterpret_cast<std::byte*>(s.data()), s.size_bytes()};
}

template <std::size_t N, typename E, std::size_t S>
constexpr auto get(span<E, S> s) -> decltype(s[N])
{
    return s[N];
}

namespace std
{
template <typename ElementType, size_t Extent>
class tuple_size<::span<ElementType, Extent>> : public integral_constant<size_t, Extent>
{
};

template <typename ElementType>
class tuple_size<::span<ElementType, ::dynamic_extent>>; // not defined

template <size_t I, typename ElementType, size_t Extent>
class tuple_element<I, ::span<ElementType, Extent>>
{
public:
    static_assert(Extent != ::dynamic_extent && I < Extent, "");
    using type = ElementType;
};

} // end namespace std