// SPDX-License-Identifier: BSD-3-Clause
#ifndef SUBSTRATE_SPAN
#define SUBSTRATE_SPAN

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

#if __cplusplus > 201703L
#include <span>
namespace substrate
{
	template<typename T, size_t E = std::dynamic_extent>
		using span = std::span<T, E>;
}
#else
#include <stdexcept>
#include <substrate/utility>
#include <substrate/iterator>
#include <substrate/internal/defs>

namespace substrate
{
	template<typename...> using void_t = void;

	template<bool B> using bool_constant = std::integral_constant<bool, B>;

	enum class byte : unsigned char { };

	constexpr SUBSTRATE_CXX17_INLINE auto dynamic_extent{std::numeric_limits<size_t>::max()};
	template<typename T, size_t extent> struct span;

	namespace internal
	{
		using std::false_type;
		using std::true_type;

		template<typename T> using removeCVRef_t = substrate::remove_cv_t<substrate::remove_reference_t<T>>;
		template<typename T> struct isSpan_t : false_type { };
		template<typename T, size_t N> struct isSpan_t<span<T, N>> : true_type { };
		template<typename T> constexpr bool isSpan() { return isSpan_t<T>::value; }
		template<typename T> struct isArray_t : false_type { };
		template<typename T, size_t N> struct isArray_t<std::array<T, N>> : true_type { };
		template<typename T> constexpr bool isArray() { return isArray_t<T>::value; }
		template<typename T, typename = void> struct isContainer_t : false_type { };

		template<typename T> struct isContainer_t<T, substrate::void_t<
			substrate::enable_if_t<
				!isSpan<removeCVRef_t<T>>() &&
				!isArray<removeCVRef_t<T>>() &&
				!std::is_array<substrate::remove_reference_t<T>>::value
			>,
			decltype(substrate::data(std::declval<T>())),
			decltype(substrate::size(std::declval<T>()))
		>> : true_type { };

		template<typename T> constexpr bool isContainer() { return isContainer_t<T>::value; }
		template<typename ...> struct and_t;
		template<> struct and_t<> : public true_type { };
		template<typename type1_t> struct and_t<type1_t> : public type1_t { };
		template<typename type1_t, typename type2_t> struct and_t<type1_t, type2_t> :
			public std::conditional<type1_t::value, type2_t, type1_t>::type { };
		template<typename toType_t, typename fromType_t> using isArrayConvertible =
			std::is_convertible<fromType_t (*)[], toType_t (*)[]>;

		template<size_t _extent> struct extentStorage_t
		{
			constexpr extentStorage_t(size_t) noexcept { }
			constexpr static size_t extent() noexcept { return _extent; }
		};

		template<> struct extentStorage_t<dynamic_extent>
		{
		private:
			size_t _extent;

		public:
			constexpr extentStorage_t(const size_t extent) noexcept : _extent{extent} { }
			constexpr size_t extent() const noexcept { return _extent; }
		};
	} // namespace internal

	template<typename T, size_t extent_v = dynamic_extent> struct span
	{
		static constexpr bool matches_extent = extent_v == dynamic_extent;

		template<size_t count>
			using count_is_dynamic_extent = substrate::bool_constant<count == dynamic_extent>;

		template<size_t offset, size_t count> static constexpr
			substrate::enable_if_t<!count_is_dynamic_extent<count>(), size_t>
			_subspanExtent() noexcept { return count; }

		template<size_t offset, size_t count> static constexpr
			substrate::enable_if_t<!matches_extent && count_is_dynamic_extent<count>(), size_t>
			_subspanExtent() noexcept { return extent_v - offset; }

		template<size_t offset, size_t count> static constexpr
			substrate::enable_if_t<matches_extent && count_is_dynamic_extent<count>(), size_t>
			_subspanExtent() noexcept { return dynamic_extent; }

		template<typename type_t, size_t N> using isCompatArray_t = internal::and_t<substrate::bool_constant<
			matches_extent || extent_v == N>, internal::isArrayConvertible<T, type_t>>;
		template<typename type_t, size_t N> constexpr static bool isCompatArray ()
			{ return isCompatArray_t<type_t, N>::value; }

	public:
		using value_type = substrate::remove_cv_t<T>;
		using element_type = T;
		using size_type = size_t;
		using reference = T &;
		using const_reference = const T &;
		using pointer = T *;
		using const_pointer = const T *;
		using iterator = normalIterator_t<pointer, span>;
		using const_iterator = normalIterator_t<const_pointer, span>;
		using reverse_iterator = std::reverse_iterator<iterator>;
		using const_reverse_iterator = std::reverse_iterator<const_iterator>;
		using difference_type = ptrdiff_t;

		constexpr static size_t extent = extent_v;

	private:
		SUBSTRATE_NO_UNIQUE_ADDRESS(internal::extentStorage_t<extent> _extent{0});
		pointer _ptr{nullptr};

	public:
		constexpr span() noexcept = default;
		constexpr span(const span &) noexcept = default;
		constexpr span(span &&) noexcept = default;
		constexpr span(pointer ptr, size_t count) noexcept : _extent{count}, _ptr{ptr} { }
		constexpr span(pointer first, pointer last) noexcept : span(first, last - first) { }

		template<typename type_t, size_t N, substrate::enable_if_t<isCompatArray<type_t, N>(), void *> = nullptr>
			constexpr span(type_t (&array)[N]) noexcept : span(static_cast<pointer>(array), N) { }
		template<typename type_t, size_t N, substrate::enable_if_t<isCompatArray<type_t, N>(), void *> = nullptr>
			constexpr span(std::array<type_t, N> &array) noexcept :
			span{static_cast<pointer>(array.data()), N} { }
		template<typename type_t, size_t N, substrate::enable_if_t<isCompatArray<const type_t, N>(), void *> = nullptr>
			constexpr span(const std::array<type_t, N> &array) noexcept :
			span{static_cast<pointer>(array.data()), N} { }

		// Allow converting a less-const span into a more const one
		template<typename type_t, size_t N, substrate::enable_if_t<std::is_same_v<T, const type_t>, void *> = nullptr>
			constexpr span(const span<type_t, N> &other) noexcept : span{other.data(), other.size()} { }

		template<class container_t, substrate::enable_if_t<extent_v == dynamic_extent &&
			internal::isContainer<container_t>(), void *> = nullptr>
		constexpr span(container_t &container) noexcept(noexcept(substrate::data(container)) &&
			noexcept(substrate::size(container))) : span(substrate::data(container), substrate::size(container)) { }

		template<class container_t, substrate::enable_if_t<extent_v == dynamic_extent &&
			internal::isContainer<container_t>(), void *> = nullptr>
		constexpr span(const container_t &container) noexcept(noexcept(substrate::data(container)) &&
			noexcept(substrate::size(container))) : span(substrate::data(container), substrate::size(container)) { }

		~span() noexcept = default;
		SUBSTRATE_CXX17_CONSTEXPR span &operator =(const span &) noexcept = default;
		SUBSTRATE_CXX17_CONSTEXPR span &operator =(span &&) noexcept = default;
		constexpr size_t size() const noexcept { return _extent.extent(); }
		constexpr size_t size_bytes() const noexcept { return size() * sizeof(T); }
		SUBSTRATE_NO_DISCARD(constexpr bool empty() const noexcept) { return size() == 0; }

		constexpr reference front() const noexcept
		{
			static_assert(extent != 0, "span extent must not be zero");
			static_assert(!empty(), "span must not be empty");
			return *_ptr;
		}

		constexpr reference back() const noexcept
		{
			static_assert(extent != 0, "span extent must not be zero");
			static_assert(!empty(), "span must not be empty");
			return _ptr[size() - 1];
		}

		constexpr reference operator [](const size_t idx) const noexcept
		{
			static_assert(extent != 0, "span extent must not be zero");
#if __cplusplus > 201703L
			if constexpr (std::is_constant_evaluated())
				static_assert(idx < size(), "index must be less than the size of the span");
#endif
			return _ptr[idx];
		}

		constexpr pointer data() const noexcept { return _ptr; }
		constexpr iterator begin() const noexcept { return iterator{_ptr}; }
		constexpr const_iterator cbegin() const noexcept { return const_iterator{_ptr}; }
		constexpr iterator end() const noexcept { return iterator{_ptr + size()}; }
		constexpr const_iterator cend() const noexcept { return const_iterator{_ptr + size()}; }
		constexpr reverse_iterator rbegin() const noexcept { return reverse_iterator{end()}; }
		constexpr const_reverse_iterator crbegin() const noexcept { return const_reverse_iterator{cend()}; }
		constexpr reverse_iterator rend() const noexcept { return reverse_iterator{begin()}; }
		constexpr const_reverse_iterator crend() const noexcept { return const_reverse_iterator{cbegin()}; }

		template<size_t count> constexpr substrate::enable_if_t<extent_v == dynamic_extent, span<T, count>>
			first() const noexcept
		{
			static_assert(count <= size(), "count must be less than or equal to the size of the span");
			return {data(), count};
		}

		template<size_t count> constexpr substrate::enable_if_t<extent_v != dynamic_extent, span<T, count>>
			first() const noexcept
		{
			static_assert(count <= extent, "count must be less than or equal to the extent of the span");
			return {data(), count};
		}

		constexpr span<T, dynamic_extent> first(size_t count) const noexcept
		{
			static_assert(count <= size(), "count must be less than or equal to the size of the span");
			return {data(), count};
		}

		template<size_t count> constexpr substrate::enable_if_t<extent_v == dynamic_extent, span<T, count>>
			last() const noexcept
		{
			static_assert(count <= size(), "count must be less than or equal to the size of the span");
			return {data() + (size() - count), count};
		}


		template<size_t count> constexpr substrate::enable_if_t<extent_v != dynamic_extent, span<T, count>>
			last() const noexcept
		{
			static_assert(count <= extent, "count must less than or equal to the extent of the span");
			return {data() + (size() - count), count};
		}


		constexpr span<T, dynamic_extent> last(size_t count) const noexcept
		{
			static_assert(count <= size(), "count must be less than or equal to the size of the span");
			return {data() + (size() - count), count};
		}

		template<size_t offset, size_t count = dynamic_extent> constexpr auto subspan() const noexcept ->
			substrate::enable_if_t<matches_extent && !count_is_dynamic_extent<count>(),
				span<T, _subspanExtent<offset, count>()>>
		{
			static_assert(offset <= size(), "offset must be less than or equal to the size of the span");
			static_assert(count <= size(), "count must be less than or equal to the size of the span");
			static_assert(count <= size() - offset, "count must be less than or equal to the size of the span minus the offset");
			return {data() + offset, count};
		}


		template<size_t offset, size_t count = dynamic_extent> constexpr auto subspan() const noexcept ->
			substrate::enable_if_t<!matches_extent && count_is_dynamic_extent<count>(),
				span<T, _subspanExtent<offset, count>()>>
		{
			static_assert(offset <= extent, "offset must be less than or equal to the extent of the span");

			return {data() + offset, size() - offset};
		}

		template<size_t offset, size_t count = dynamic_extent> constexpr auto subspan() const noexcept ->
			substrate::enable_if_t<matches_extent && count_is_dynamic_extent<count>(),
				span<T, _subspanExtent<offset, count>()>>
		{
			static_assert(offset <= size(), "offset must be less than or equal to the size of the span");
			static_assert(count <= size(), "count must be less than or equal to the size of the span");
			static_assert(count <= size() - offset, "count must be less than or equal to the size of the span minus the offset");
			return {data() + offset, size() - offset};
		}


		template<size_t offset, size_t count = dynamic_extent> constexpr auto subspan() const noexcept ->
			substrate::enable_if_t<!matches_extent && !count_is_dynamic_extent<count>(),
				span<T, _subspanExtent<offset, count>()>>
		{
			static_assert(offset <= extent, "offset must be less than or equal to the extent of the span");
			static_assert(count <= extent, "count must be less than or equal to the extent of the span");
			static_assert(count <= extent - offset, "count must be less than or equal to the extent of the span minus the offset");
			return {data() + offset, count};
		}

		SUBSTRATE_CXX14_CONSTEXPR span<T, dynamic_extent>
			subspan(size_t offset, size_t count = dynamic_extent) const
		{
#if __cplusplus > 201703L
			if constexpr (std::is_constant_evaluated())
				static_assert(offset <= size(), "Offset must be less than or equal to the size of the span");
			else
#endif
			if (offset > size())
				throw std::out_of_range{"Offset must be less than or equal to the size of the span"};
			if (count == dynamic_extent)
				count = size() - offset;
			else
			{
#if __cplusplus > 201703L
				if constexpr (std::is_constant_evaluated())
				{
					static_assert(count <= size(), "count must be less than or equal to the size of the span");
					static_assert(offset + count <= size(), "the sum of the offset and count must be less than or equal to the size of the span");
				}
				else
				{
#endif
					if (count > size())
						throw std::out_of_range{"count must be less than or equal to the size of the span"};
					if (offset + count > size())
						throw std::out_of_range{"the sum of the offset and count must be less than or equal to the size of the span"};
#if __cplusplus > 201703L
				}
#endif
			}
			return {data() + offset, count};
		}
	};

#if __cplusplus >= 201703L
	// These are the type deduction guides for span
	template<typename T, size_t N> span(T (&)[N]) -> span<T, N>;
	template<typename T, size_t N> span(std::array<T, N> &) -> span<T, N>;
	template<typename T, size_t N> span(const std::array<T, N> &) -> span<const T, N>;
	template<typename T> span(T *, size_t) -> span<T>;
	template<typename T> span(T *, T *) -> span<T>;
	template<typename container_t> span(container_t &) -> span<typename container_t::value_type>;
	template<typename container_t> span(const container_t &) -> span<const typename container_t::value_type>;
#endif

#if !defined(_MSC_VER) || _MSC_VER >= 1920
	template<typename T, size_t extent> inline span<const substrate::byte,
		extent == dynamic_extent ? dynamic_extent : extent * sizeof(T)>
		as_bytes(span<T, extent> span) noexcept
#else
	// MSVC < 2019 parser chokes on ?: inside a template parameter definition
	template <typename T, size_t extent, size_t U = extent == dynamic_extent ? dynamic_extent : extent * sizeof(T)>
	inline span<const substrate::byte, U> as_bytes(span<T, extent> span) noexcept
#endif
	{
		return {
			// NOLINTNEXTLINE(cppcoreguidelines-pro-type-reinterpret-cast)
			reinterpret_cast<const substrate::byte *>(span.data()),
			span.size_bytes()
		};
	}
#if !defined(_MSC_VER) || _MSC_VER >= 1920
	template<typename T, size_t extent> inline span<substrate::byte,
		extent == dynamic_extent ? dynamic_extent : extent * sizeof(T)>
		as_writeable_bytes(span<T, extent> span) noexcept
#else
	// MSVC < 2019 parser chokes on ?: inside a template parameter definition
	template <typename T, size_t extent, size_t U = extent == dynamic_extent ? dynamic_extent : extent * sizeof(T)>
	inline span<const substrate::byte, U> as_writeable_bytes(span<T, extent> span) noexcept
#endif
	{
		return {
			// NOLINTNEXTLINE(cppcoreguidelines-pro-type-reinterpret-cast)
			reinterpret_cast<substrate::byte *>(span.data()),
			span.size_bytes()
		};
	}
} // namespace substrate

namespace std // NOLINT(cert-dcl58-cpp)
{
	using substrate::dynamic_extent;
	using substrate::span;

	template<size_t index, typename T, size_t extent_> constexpr T &get(span<T, extent_> span) noexcept
	{
		static_assert(extent_ != dynamic_extent && index < extent_,
			"get<I> can only be used with a span of non-dynamic (fixed) extent");
		return span[index];
	}

	template<typename T, size_t extent_>
	struct tuple_size<span<T, extent_>> : public integral_constant<size_t, extent_>
	{
		static_assert(extent_ != dynamic_extent,
			"tuple_size can only be used with a span of non-dynamic (fixed) extent");
	};

	template<size_t index, typename T, size_t extent_> struct tuple_element<index, span<T, extent_>>
	{
		static_assert(extent_ != dynamic_extent,
			"tuple_element can only be used with a span of non-dynamic (fixed) extent");
		static_assert(index < extent_, "index is less than extent");
		using type = T;
	};
} // namespace std

#endif
#endif /* SUBSTRATE_SPAN */
/* vim: set ft=cpp ts=4 sw=4 noexpandtab: */
