internal/ranges.hpp

View this file on GitHub
Last update: 2024-06-01 20:25:26+09:00
Include: #include "internal/ranges.hpp"

Depends on

Required by

Verified with

Code

#pragma once


#include <ranges>
#include <concepts>
#include <tuple>


#include "internal/dev_env.hpp"
#include "internal/type_traits.hpp"


namespace uni {

namespace internal {


template<class Range>
concept resizable_range
  = std::ranges::range<Range> &&
    requires (Range& r) { r.resize(0); };

template<class range>
concept simple_view
  = std::ranges::view<range> && std::ranges::range<const range> &&
    std::same_as<std::ranges::iterator_t<range>, std::ranges::iterator_t<const range>> &&
    std::same_as<std::ranges::sentinel_t<range>, std::ranges::sentinel_t<const range>>;


template<class... Ranges>
concept zip_is_common = (sizeof...(Ranges) == 1 && (std::ranges::common_range<Ranges> && ...))
    || (!(std::ranges::bidirectional_range<Ranges> && ...) && (std::ranges::common_range<Ranges> && ...))
    || ((std::ranges::random_access_range<Ranges> && ...) && (std::ranges::sized_range<Ranges> && ...));


template<bool Const, class... Views>
concept all_contiguous = (std::ranges::contiguous_range<maybe_const_t<Const, Views>> && ...);

template<bool Const, class... Views>
concept all_random_access = (std::ranges::random_access_range<maybe_const_t<Const, Views>> && ...);

template<bool Const, class... Views>
concept all_bidirectional = (std::ranges::bidirectional_range<maybe_const_t<Const, Views>> && ...);

template<bool Const, class... Views>
concept all_forward = (std::ranges::forward_range<maybe_const_t<Const, Views>> && ...);


template<bool Const, class... Views> struct zip_view_iterator_category {};

template<bool Const, class... Views>
    requires all_forward<Const, Views...>
struct zip_view_iterator_category<Const, Views...> {
    using iterator_category = std::input_iterator_tag;
};


template<bool Const, class... Views>
static auto _most_primitive_iterator_concept() noexcept(NO_EXCEPT) {
    if constexpr(all_random_access<Const, Views...>)
        return std::random_access_iterator_tag{};
    else if constexpr(all_bidirectional<Const, Views...>)
        return std::bidirectional_iterator_tag{};
    else if constexpr(all_forward<Const, Views...>)
        return std::forward_iterator_tag{};
    else
        return std::input_iterator_tag{};
}

template<bool Const, class... Views>
using most_primitive_iterator_concept = decltype(_most_primitive_iterator_concept<Const, Views...>());


template<class Range, bool Const>
using range_iterator_category = typename std::iterator_traits<
        std::ranges::iterator_t<maybe_const_t<Const, Range>>
    >::iterator_category;



template<class Range>
static constexpr auto _iterator_concept() noexcept(NO_EXCEPT) {
    if constexpr(std::ranges::random_access_range<Range>)
        return std::random_access_iterator_tag{};
    else if constexpr(std::ranges::bidirectional_range<Range>)
        return std::bidirectional_iterator_tag{};
    else if constexpr(std::ranges::forward_range<Range>)
        return std::forward_iterator_tag{};
    else
        return std::input_iterator_tag{};
}

template<class Range>
using iterator_concept = decltype(_iterator_concept<Range>());



template<std::ranges::range Range> struct cached_position {
    constexpr bool has_value() const { return false; }

    constexpr std::ranges::iterator_t<Range> get(const Range&) const {
        __builtin_unreachable();
    }

    constexpr void set(const Range &, const std::ranges::iterator_t<Range> &) const {}
};

template<std::ranges::forward_range Range>
struct cached_position<Range> : protected std::optional<std::ranges::iterator_t<Range>> {
    using std::optional<std::ranges::iterator_t<Range>>::optioanl;
    using std::optional<std::ranges::iterator_t<Range>>::has_value;

    constexpr std::ranges::iterator_t<Range> get(const Range&) const {
        assert(this->has_value());
        return **this;
    }

    constexpr void set(const Range&, const std::ranges::iterator_t<Range>& itr) {
        assert(!this->has_value());
        this->emplace(*itr);
    }
};


template<std::ranges::random_access_range Range>
    requires(sizeof(std::ranges::range_difference_t<Range>) <= sizeof(std::ranges::iterator_t<Range>))
struct cached_position<Range> {
  private:
    std::ranges::range_difference_t<Range> _offset = -1;

  public:
    cached_position() = default;

    constexpr cached_position(const cached_position &) = default;

    constexpr cached_position(cached_position &&other) noexcept {
        *this = std::move(other);
    }

    constexpr cached_position &operator=(const cached_position &) = default;

    constexpr cached_position &operator=(cached_position &&other) noexcept {
        // Propagate the cached offset, but invalidate the source.
        this->_offset = other._offset;
        other._offset = -1;
        return *this;
    }

    constexpr bool has_value() const { return this->_offset >= 0; }

    constexpr std::ranges::iterator_t<Range> get(Range& range) const {
        assert(this->has_value());
        return std::ranges::begin(range) + this->_offset;
    }

    constexpr void set(Range &range, const std::ranges::iterator_t<Range> &itr) {
        assert(!this->has_value());
        this->_offset = itr - std::ranges::begin(range);
    }
};


template<typename T, int Disc>
struct absent { };

template<bool PRESENT, class T, int Disc = 0>
using maybe_present_t = std::conditional_t<PRESENT, T, absent<T, Disc>>;


} // namespace internal


namespace views::adaptor {


template<class Adaptor, class... Args>
concept adaptor_invocable = requires { std::declval<Adaptor>()(std::declval<Args>()...); };

template<class Adaptor, class... Args>
concept adaptor_partial_app_viable =
    (Adaptor::arity > 1) && (sizeof...(Args) == Adaptor::arity - 1) &&
    (std::constructible_from<std::remove_cvref_t<Args>, Args> && ...);

template<class Adaptor, class... Args> struct partial;

template<class, class> struct pipe;


template<class Derived> struct range_adaptor_closure {};


template<class T, class U>
    requires(!std::same_as<T, range_adaptor_closure<U>>)
void is_range_adaptor_closure_fn(const T &, const range_adaptor_closure<U> &);


template<class T>
concept is_range_adaptor_closure = requires(T t) { adaptor::is_range_adaptor_closure_fn(t, t); };


template<class Self, class Range>
    requires is_range_adaptor_closure<Self> && adaptor_invocable<Self, Range>
constexpr auto operator|(Range&& range, Self&& self) {
    return std::forward<Self>(self)(std::forward<Range>(range));
}


template<class Lhs, class Rhs>
    requires is_range_adaptor_closure<Lhs> && is_range_adaptor_closure<Rhs>
constexpr auto operator|(Lhs&& lhs, Rhs&& rhs) {
    return pipe<std::remove_cvref_t<Lhs>, std::remove_cvref_t<Rhs>>{ std::forward<Lhs>(lhs), std::forward<Rhs>(rhs)};
}


template<class Derived> struct range_adaptor {
    template<class... Args>
        requires adaptor_partial_app_viable<Derived, Args...>
    inline constexpr auto operator()(Args&& ..._args) const noexcept(NO_EXCEPT) {
        return partial<Derived, std::remove_cvref_t<Args>...>{
            std::forward<Args>(_args)...
        };
    }
};

template<class Adaptor>
concept closure_has_simple_call_op = Adaptor::has_simple_call_op;

template<class Adaptor, class... Args>
concept adaptor_has_simple_extra_args =
    Adaptor::has_simple_extra_args ||
    Adaptor::template has_simple_extra_args<Args...>;

template<class Adaptor, class... Args>
struct partial : range_adaptor_closure<partial<Adaptor, Args...>> {
    std::tuple<Args...> args;

    constexpr partial(Args... _args) noexcept(NO_EXCEPT) : args(std::move(_args)...) {}

    template<class Range>
        requires adaptor_invocable<Adaptor, Range, const Args &...>
    inline constexpr auto operator()(Range&& range) const & noexcept(NO_EXCEPT) {
        const auto forwarder = [&range](const auto &..._args) constexpr noexcept(NO_EXCEPT) {
            return Adaptor{}(std::forward<Range>(range), _args...);
        };
        return std::apply(forwarder, this->args);
    }

    template<class Range>
        requires adaptor_invocable<Adaptor, Range, Args...>
    inline constexpr auto operator()(Range&& range) && noexcept(NO_EXCEPT) {
        const auto forwarder = [&range](auto &..._args) constexpr noexcept(NO_EXCEPT) {
            return Adaptor{}(std::forward<Range>(range), std::move(_args)...);
        };
        return std::apply(forwarder, this->args);
    }

    template<class Range>
    inline constexpr auto operator()(Range&& range) const && = delete;
};

template<class Adaptor, class Arg>
struct partial<Adaptor, Arg> : range_adaptor_closure<partial<Adaptor, Arg>> {
    Arg arg;

    constexpr partial(Arg _arg) noexcept(NO_EXCEPT) : arg(std::move(_arg)) {}

    template<class Range>
        requires adaptor_invocable<Adaptor, Range, const Arg &>
    inline constexpr auto operator()(Range&& range) const & noexcept(NO_EXCEPT) {
        return Adaptor{}(std::forward<Range>(range), this->arg);
    }

    template<class Range>
        requires adaptor_invocable<Adaptor, Range, Arg>
    inline constexpr auto operator()(Range&& range) && noexcept(NO_EXCEPT) {
        return Adaptor{}(std::forward<Range>(range), std::move(this->arg));
    }

    template<class Range>
    inline constexpr auto operator()(Range&& range) const && = delete;
};

template<class Adaptor, class... Args>
    requires adaptor_has_simple_extra_args<Adaptor, Args...> && (std::is_trivially_copyable_v<Args> && ...)
struct partial<Adaptor, Args...> : range_adaptor_closure<partial<Adaptor, Args...>> {
    std::tuple<Args...> args;

    constexpr partial(Args... _args) noexcept(NO_EXCEPT) : args(std::move(_args)...) {}

    template<class Range>
        requires adaptor_invocable<Adaptor, Range, const Args &...>
    inline constexpr auto operator()(Range&& range) const noexcept(NO_EXCEPT) {
        const auto forwarder = [&range](const auto &..._args) constexpr noexcept(NO_EXCEPT) {
            return Adaptor{}(std::forward<Range>(range), _args...);
        };
        return std::apply(forwarder, this->args);
    }

    static constexpr bool has_simple_call_op = true;
};

template<class Adaptor, class Arg>
    requires adaptor_has_simple_extra_args<Adaptor, Arg> &&
             std::is_trivially_copyable_v<Arg>
struct partial<Adaptor, Arg> : range_adaptor_closure<partial<Adaptor, Arg>> {
    Arg arg;

    constexpr partial(Arg _arg) noexcept(NO_EXCEPT) : arg(std::move(_arg)) {}

    template<class Range>
        requires adaptor_invocable<Adaptor, Range, const Arg &>
    inline constexpr auto operator()(Range&& range) const noexcept(NO_EXCEPT) {
        return Adaptor{}(std::forward<Range>(range), this->arg);
    }

    static constexpr bool has_simple_call_op = true;
};

template<class Lhs, class Rhs, class Range>
concept pipe_invocable = requires {
    std::declval<Rhs>()(std::declval<Lhs>()(std::declval<Range>()));
};

template<class Lhs, class Rhs> struct pipe : range_adaptor_closure<pipe<Lhs, Rhs>> {
    [[no_unique_address]] Lhs lhs;
    [[no_unique_address]] Rhs rhs;

    constexpr pipe(Lhs _lhs, Rhs _rhs) noexcept(NO_EXCEPT) : lhs(std::move(_lhs)), rhs(std::move(_rhs)) {}

    template<class Range>
        requires pipe_invocable<const Lhs &, const Rhs &, Range>
    inline constexpr auto operator()(Range&& range) const & noexcept(NO_EXCEPT) {
        return rhs(lhs(std::forward<Range>(range)));
    }

    template<class Range>
        requires pipe_invocable<Lhs, Rhs, Range>
    inline constexpr auto operator()(Range&& range) && noexcept(NO_EXCEPT) {
        return std::move(rhs)(std::move(lhs)(std::forward<Range>(range)));
    }

    template<class Range>
    inline constexpr auto operator()(Range&& range) const && = delete;
};


template<class Lhs, class Rhs>
    requires closure_has_simple_call_op<Lhs> && closure_has_simple_call_op<Rhs>
struct pipe<Lhs, Rhs> : range_adaptor_closure<pipe<Lhs, Rhs>> {
    [[no_unique_address]] Lhs lhs;
    [[no_unique_address]] Rhs rhs;

    constexpr pipe(Lhs _lhs, Rhs _rhs) noexcept(NO_EXCEPT) : lhs(std::move(_lhs)), rhs(std::move(_rhs)) {}

    template<class Range>
        requires pipe_invocable<const Lhs &, const Rhs &, Range>
    inline constexpr auto operator()(Range&& range) const noexcept(NO_EXCEPT) {
        return rhs(lhs(std::forward<Range>(range)));
    }

    static constexpr bool has_simple_call_op = true;
};


} // namespace views::adaptor


} // namespace uni

#line 2 "internal/ranges.hpp"


#include <ranges>
#include <concepts>
#include <tuple>


#line 2 "internal/dev_env.hpp"


#ifdef LOCAL_JUDGE
    inline constexpr bool DEV_ENV = true;
    inline constexpr bool NO_EXCEPT = false;
#else
    inline constexpr bool DEV_ENV = false;
    inline constexpr bool NO_EXCEPT = true;
#endif // LOCAL_JUDGE


#if __cplusplus >= 202100L
    #define CPP20 true
    #define CPP23 true
#elif __cplusplus >= 202002L
    #define CPP20 true
    #define CPP23 false
#else
    #define CPP20 false
    #define CPP23 false
#endif
#line 2 "internal/type_traits.hpp"


#include <iostream>
#include <vector>
#include <type_traits>
#include <algorithm>
#include <utility>


#line 12 "internal/type_traits.hpp"


namespace uni {

namespace internal {


template<class... Ts> struct tuple_or_pair { using type = std::tuple<Ts...>; };
template<class T, class U> struct tuple_or_pair<T,U> { using type = std::pair<T, U>; };
template <class... Ts> using tuple_or_pair_t = typename tuple_or_pair<Ts...>::type;

template<class T>
constexpr std::underlying_type_t<T> to_underlying(const T& v) noexcept(NO_EXCEPT) {
    return static_cast<std::underlying_type_t<T>>(v);
}


template<class T, class... Ts>
using are_same = std::conjunction<std::is_same<T, Ts>...>;

template<class T, class... Ts>
inline constexpr bool are_same_v = are_same<T, Ts...>::value;


template<class T, class... Ts>
using is_same_as_any_of = std::disjunction<std::is_same<T, Ts>...>;

template<class T, class... Ts>
inline constexpr bool is_same_as_any_of_v = is_same_as_any_of<T, Ts...>::value;

template<class T, class... Ts>
concept same_as_any_of = is_same_as_any_of_v<T, Ts...>;


template<class Base, class... Derived>
using is_base_of_all = std::conjunction<std::is_base_of<Base, Derived>...>;

template<class Base, class... Derived>
inline constexpr bool is_base_of_all_v = is_base_of_all<Base, Derived...>::value;


template<class Base, class... Derived>
using is_base_of_any = std::disjunction<std::is_base_of<Base, Derived>...>;

template<class Base, class... Derived>
inline constexpr bool is_base_of_any_v = is_base_of_any<Base, Derived...>::value;


template<class T> struct remove_cvref {
  using type = typename std::remove_cv_t<std::remove_reference_t<T>>;
};

template<class T> using remove_cvref_t = typename remove_cvref<T>::type;


template<class T> struct literal_operator { static constexpr const char* value = ""; };

template<> struct literal_operator<unsigned> { static constexpr const char* value = "U"; };
template<> struct literal_operator<long> { static constexpr const char* value = "L"; };
template<> struct literal_operator<unsigned long> { static constexpr const char* value = "UL"; };
template<> struct literal_operator<long long> { static constexpr const char* value = "LL"; };
template<> struct literal_operator<unsigned long long> { static constexpr const char* value = "ULL"; };


template<> struct literal_operator<float> { static constexpr const char* value = "F"; };
template<> struct literal_operator<double> { static constexpr const char* value = "D"; };
template<> struct literal_operator<long double> { static constexpr const char* value = "LD"; };

#ifdef __SIZEOF_INT128__

template<> struct literal_operator<__int128_t> { static constexpr const char* value = "LLL"; };
template<> struct literal_operator<__uint128_t> { static constexpr const char* value = "ULLL"; };

#endif

template<class T> inline constexpr auto literal_operator_v = literal_operator<T>::value;


template <std::size_t N, typename... Types>
struct nth_type {};

template <class Head, class... Tail>
struct nth_type<0, Head, Tail...> {
	using type = Head;
};

template <std::size_t N, class Head, class... Tail>
struct nth_type<N, Head, Tail...> : public nth_type<N - 1, Tail...> {};

template <std::size_t N, typename... Types>
using nth_type_t = typename nth_type<N, Types...>::type;


template<template <class...> class, class> struct is_template_of : std::false_type {};
template<template <class...> class Template, class... Args> struct is_template_of<Template, Template<Args...>> : std::true_type {};

template<template <class...> class Template, class Type>
inline constexpr bool is_template_of_v = is_template_of<Template, Type>::value;

template<class Type, template <class...> class Template>
concept substituted_from = is_template_of_v<Template, Type>;

template<template <class...> class Base, class Derived>
struct _is_basic_tempalte_of
{
    template<class... Ts>
    static constexpr std::true_type  test(const Base<Ts...> *);

    static constexpr std::false_type test(...);

    using type = decltype(test(std::declval<Derived*>()));
};


template<template <class...> class Base, class Derived>
using is_basic_tempalte_of = _is_basic_tempalte_of<Base, Derived>::type;

template<template <class...> class Base, class Derived>
inline constexpr bool is_basic_tempalte_of_v = is_basic_tempalte_of<Base, Derived>::value;

template<class Derived, template <class...> class Base>
concept derived_from_template = is_basic_tempalte_of_v<Base, Derived>;


template<class T> struct is_loggable {
    template<class U>
    static constexpr auto External(U &&v) -> decltype(_debug(v), std::true_type());
    static constexpr std::false_type External(...);

    template<class U>
    static constexpr auto Member(U &&v) -> decltype(v._debug(), std::true_type());
    static constexpr std::false_type Member(...);

    static constexpr bool value = (
      decltype(External(std::declval<T>()))::value ||
      decltype(Member(std::declval<T>()))::value
    );

};

template<class T>
inline constexpr auto is_loggable_v = is_loggable<T>::value;

template<class T>
concept loggable = is_loggable_v<T>;


template<class T> struct _has_iterator {
    template<class U>
    static constexpr auto ADL(U &&v) -> decltype(begin(v), end(v), std::true_type());
    static constexpr std::false_type ADL(...);

    template<class U>
    static constexpr auto STL(U &&v) -> decltype(std::begin(v), std::end(v), std::true_type());
    static constexpr std::false_type STL(...);

    template<class U>
    static constexpr auto Member(U &&v) -> decltype(v.begin(), v.end(), std::true_type());
    static constexpr std::false_type Member(...);
};

template<class T> struct has_iterator {
    struct ADL : decltype(_has_iterator<T>::ADL(std::declval<T>())) {};
    struct STL : decltype(_has_iterator<T>::STL(std::declval<T>())) {};
    struct Member : decltype(_has_iterator<T>::Member(std::declval<T>())) {};

    static constexpr auto adl_v = ADL::value;
    static constexpr auto stl_v = STL::value;
    static constexpr auto member_v = Member::value;
};


template<class T>
struct is_iterable {
    static constexpr bool value =  has_iterator<T>::adl_v || has_iterator<T>::stl_v || has_iterator<T>::member_v;
};

template<class T>
inline constexpr auto is_iterable_v = is_iterable<T>::value;

template<class T>
concept iterable = is_iterable_v<T>;

namespace iterator_resolver {


template<class T>
inline constexpr auto begin(T&& v) noexcept(NO_EXCEPT) {
    static_assert(is_iterable_v<T>);
    if constexpr(has_iterator<T>::member_v) {
        return v.begin();
    }
    else {  // ADL
        using std::begin;
        return begin(std::forward<T>(v));
    }
}

template<class T>
inline constexpr auto end(T&& v) noexcept(NO_EXCEPT) {
    static_assert(is_iterable_v<T>);
    if constexpr(has_iterator<T>::member_v) {
        return v.end();
    }
    else {  // ADL
        using std::end;
        return end(std::forward<T>(v));
    }
}


};


template<class C> using iterator_t = decltype(iterator_resolver::begin(std::declval<C&>()));

template<class C> using container_size_t = decltype(std::size(std::declval<C&>()));


template<bool Const, class T>
using maybe_const_t = std::conditional_t<Const, const T, T>;


template<class T> using with_ref = T&;
template<class T> concept can_reference = requires { typename with_ref<T>; };


} // namespace internal

}  // namespace uni
#line 11 "internal/ranges.hpp"


namespace uni {

namespace internal {


template<class Range>
concept resizable_range
  = std::ranges::range<Range> &&
    requires (Range& r) { r.resize(0); };

template<class range>
concept simple_view
  = std::ranges::view<range> && std::ranges::range<const range> &&
    std::same_as<std::ranges::iterator_t<range>, std::ranges::iterator_t<const range>> &&
    std::same_as<std::ranges::sentinel_t<range>, std::ranges::sentinel_t<const range>>;


template<class... Ranges>
concept zip_is_common = (sizeof...(Ranges) == 1 && (std::ranges::common_range<Ranges> && ...))
    || (!(std::ranges::bidirectional_range<Ranges> && ...) && (std::ranges::common_range<Ranges> && ...))
    || ((std::ranges::random_access_range<Ranges> && ...) && (std::ranges::sized_range<Ranges> && ...));


template<bool Const, class... Views>
concept all_contiguous = (std::ranges::contiguous_range<maybe_const_t<Const, Views>> && ...);

template<bool Const, class... Views>
concept all_random_access = (std::ranges::random_access_range<maybe_const_t<Const, Views>> && ...);

template<bool Const, class... Views>
concept all_bidirectional = (std::ranges::bidirectional_range<maybe_const_t<Const, Views>> && ...);

template<bool Const, class... Views>
concept all_forward = (std::ranges::forward_range<maybe_const_t<Const, Views>> && ...);


template<bool Const, class... Views> struct zip_view_iterator_category {};

template<bool Const, class... Views>
    requires all_forward<Const, Views...>
struct zip_view_iterator_category<Const, Views...> {
    using iterator_category = std::input_iterator_tag;
};


template<bool Const, class... Views>
static auto _most_primitive_iterator_concept() noexcept(NO_EXCEPT) {
    if constexpr(all_random_access<Const, Views...>)
        return std::random_access_iterator_tag{};
    else if constexpr(all_bidirectional<Const, Views...>)
        return std::bidirectional_iterator_tag{};
    else if constexpr(all_forward<Const, Views...>)
        return std::forward_iterator_tag{};
    else
        return std::input_iterator_tag{};
}

template<bool Const, class... Views>
using most_primitive_iterator_concept = decltype(_most_primitive_iterator_concept<Const, Views...>());


template<class Range, bool Const>
using range_iterator_category = typename std::iterator_traits<
        std::ranges::iterator_t<maybe_const_t<Const, Range>>
    >::iterator_category;



template<class Range>
static constexpr auto _iterator_concept() noexcept(NO_EXCEPT) {
    if constexpr(std::ranges::random_access_range<Range>)
        return std::random_access_iterator_tag{};
    else if constexpr(std::ranges::bidirectional_range<Range>)
        return std::bidirectional_iterator_tag{};
    else if constexpr(std::ranges::forward_range<Range>)
        return std::forward_iterator_tag{};
    else
        return std::input_iterator_tag{};
}

template<class Range>
using iterator_concept = decltype(_iterator_concept<Range>());



template<std::ranges::range Range> struct cached_position {
    constexpr bool has_value() const { return false; }

    constexpr std::ranges::iterator_t<Range> get(const Range&) const {
        __builtin_unreachable();
    }

    constexpr void set(const Range &, const std::ranges::iterator_t<Range> &) const {}
};

template<std::ranges::forward_range Range>
struct cached_position<Range> : protected std::optional<std::ranges::iterator_t<Range>> {
    using std::optional<std::ranges::iterator_t<Range>>::optioanl;
    using std::optional<std::ranges::iterator_t<Range>>::has_value;

    constexpr std::ranges::iterator_t<Range> get(const Range&) const {
        assert(this->has_value());
        return **this;
    }

    constexpr void set(const Range&, const std::ranges::iterator_t<Range>& itr) {
        assert(!this->has_value());
        this->emplace(*itr);
    }
};


template<std::ranges::random_access_range Range>
    requires(sizeof(std::ranges::range_difference_t<Range>) <= sizeof(std::ranges::iterator_t<Range>))
struct cached_position<Range> {
  private:
    std::ranges::range_difference_t<Range> _offset = -1;

  public:
    cached_position() = default;

    constexpr cached_position(const cached_position &) = default;

    constexpr cached_position(cached_position &&other) noexcept {
        *this = std::move(other);
    }

    constexpr cached_position &operator=(const cached_position &) = default;

    constexpr cached_position &operator=(cached_position &&other) noexcept {
        // Propagate the cached offset, but invalidate the source.
        this->_offset = other._offset;
        other._offset = -1;
        return *this;
    }

    constexpr bool has_value() const { return this->_offset >= 0; }

    constexpr std::ranges::iterator_t<Range> get(Range& range) const {
        assert(this->has_value());
        return std::ranges::begin(range) + this->_offset;
    }

    constexpr void set(Range &range, const std::ranges::iterator_t<Range> &itr) {
        assert(!this->has_value());
        this->_offset = itr - std::ranges::begin(range);
    }
};


template<typename T, int Disc>
struct absent { };

template<bool PRESENT, class T, int Disc = 0>
using maybe_present_t = std::conditional_t<PRESENT, T, absent<T, Disc>>;


} // namespace internal


namespace views::adaptor {


template<class Adaptor, class... Args>
concept adaptor_invocable = requires { std::declval<Adaptor>()(std::declval<Args>()...); };

template<class Adaptor, class... Args>
concept adaptor_partial_app_viable =
    (Adaptor::arity > 1) && (sizeof...(Args) == Adaptor::arity - 1) &&
    (std::constructible_from<std::remove_cvref_t<Args>, Args> && ...);

template<class Adaptor, class... Args> struct partial;

template<class, class> struct pipe;


template<class Derived> struct range_adaptor_closure {};


template<class T, class U>
    requires(!std::same_as<T, range_adaptor_closure<U>>)
void is_range_adaptor_closure_fn(const T &, const range_adaptor_closure<U> &);


template<class T>
concept is_range_adaptor_closure = requires(T t) { adaptor::is_range_adaptor_closure_fn(t, t); };


template<class Self, class Range>
    requires is_range_adaptor_closure<Self> && adaptor_invocable<Self, Range>
constexpr auto operator|(Range&& range, Self&& self) {
    return std::forward<Self>(self)(std::forward<Range>(range));
}


template<class Lhs, class Rhs>
    requires is_range_adaptor_closure<Lhs> && is_range_adaptor_closure<Rhs>
constexpr auto operator|(Lhs&& lhs, Rhs&& rhs) {
    return pipe<std::remove_cvref_t<Lhs>, std::remove_cvref_t<Rhs>>{ std::forward<Lhs>(lhs), std::forward<Rhs>(rhs)};
}


template<class Derived> struct range_adaptor {
    template<class... Args>
        requires adaptor_partial_app_viable<Derived, Args...>
    inline constexpr auto operator()(Args&& ..._args) const noexcept(NO_EXCEPT) {
        return partial<Derived, std::remove_cvref_t<Args>...>{
            std::forward<Args>(_args)...
        };
    }
};

template<class Adaptor>
concept closure_has_simple_call_op = Adaptor::has_simple_call_op;

template<class Adaptor, class... Args>
concept adaptor_has_simple_extra_args =
    Adaptor::has_simple_extra_args ||
    Adaptor::template has_simple_extra_args<Args...>;

template<class Adaptor, class... Args>
struct partial : range_adaptor_closure<partial<Adaptor, Args...>> {
    std::tuple<Args...> args;

    constexpr partial(Args... _args) noexcept(NO_EXCEPT) : args(std::move(_args)...) {}

    template<class Range>
        requires adaptor_invocable<Adaptor, Range, const Args &...>
    inline constexpr auto operator()(Range&& range) const & noexcept(NO_EXCEPT) {
        const auto forwarder = [&range](const auto &..._args) constexpr noexcept(NO_EXCEPT) {
            return Adaptor{}(std::forward<Range>(range), _args...);
        };
        return std::apply(forwarder, this->args);
    }

    template<class Range>
        requires adaptor_invocable<Adaptor, Range, Args...>
    inline constexpr auto operator()(Range&& range) && noexcept(NO_EXCEPT) {
        const auto forwarder = [&range](auto &..._args) constexpr noexcept(NO_EXCEPT) {
            return Adaptor{}(std::forward<Range>(range), std::move(_args)...);
        };
        return std::apply(forwarder, this->args);
    }

    template<class Range>
    inline constexpr auto operator()(Range&& range) const && = delete;
};

template<class Adaptor, class Arg>
struct partial<Adaptor, Arg> : range_adaptor_closure<partial<Adaptor, Arg>> {
    Arg arg;

    constexpr partial(Arg _arg) noexcept(NO_EXCEPT) : arg(std::move(_arg)) {}

    template<class Range>
        requires adaptor_invocable<Adaptor, Range, const Arg &>
    inline constexpr auto operator()(Range&& range) const & noexcept(NO_EXCEPT) {
        return Adaptor{}(std::forward<Range>(range), this->arg);
    }

    template<class Range>
        requires adaptor_invocable<Adaptor, Range, Arg>
    inline constexpr auto operator()(Range&& range) && noexcept(NO_EXCEPT) {
        return Adaptor{}(std::forward<Range>(range), std::move(this->arg));
    }

    template<class Range>
    inline constexpr auto operator()(Range&& range) const && = delete;
};

template<class Adaptor, class... Args>
    requires adaptor_has_simple_extra_args<Adaptor, Args...> && (std::is_trivially_copyable_v<Args> && ...)
struct partial<Adaptor, Args...> : range_adaptor_closure<partial<Adaptor, Args...>> {
    std::tuple<Args...> args;

    constexpr partial(Args... _args) noexcept(NO_EXCEPT) : args(std::move(_args)...) {}

    template<class Range>
        requires adaptor_invocable<Adaptor, Range, const Args &...>
    inline constexpr auto operator()(Range&& range) const noexcept(NO_EXCEPT) {
        const auto forwarder = [&range](const auto &..._args) constexpr noexcept(NO_EXCEPT) {
            return Adaptor{}(std::forward<Range>(range), _args...);
        };
        return std::apply(forwarder, this->args);
    }

    static constexpr bool has_simple_call_op = true;
};

template<class Adaptor, class Arg>
    requires adaptor_has_simple_extra_args<Adaptor, Arg> &&
             std::is_trivially_copyable_v<Arg>
struct partial<Adaptor, Arg> : range_adaptor_closure<partial<Adaptor, Arg>> {
    Arg arg;

    constexpr partial(Arg _arg) noexcept(NO_EXCEPT) : arg(std::move(_arg)) {}

    template<class Range>
        requires adaptor_invocable<Adaptor, Range, const Arg &>
    inline constexpr auto operator()(Range&& range) const noexcept(NO_EXCEPT) {
        return Adaptor{}(std::forward<Range>(range), this->arg);
    }

    static constexpr bool has_simple_call_op = true;
};

template<class Lhs, class Rhs, class Range>
concept pipe_invocable = requires {
    std::declval<Rhs>()(std::declval<Lhs>()(std::declval<Range>()));
};

template<class Lhs, class Rhs> struct pipe : range_adaptor_closure<pipe<Lhs, Rhs>> {
    [[no_unique_address]] Lhs lhs;
    [[no_unique_address]] Rhs rhs;

    constexpr pipe(Lhs _lhs, Rhs _rhs) noexcept(NO_EXCEPT) : lhs(std::move(_lhs)), rhs(std::move(_rhs)) {}

    template<class Range>
        requires pipe_invocable<const Lhs &, const Rhs &, Range>
    inline constexpr auto operator()(Range&& range) const & noexcept(NO_EXCEPT) {
        return rhs(lhs(std::forward<Range>(range)));
    }

    template<class Range>
        requires pipe_invocable<Lhs, Rhs, Range>
    inline constexpr auto operator()(Range&& range) && noexcept(NO_EXCEPT) {
        return std::move(rhs)(std::move(lhs)(std::forward<Range>(range)));
    }

    template<class Range>
    inline constexpr auto operator()(Range&& range) const && = delete;
};


template<class Lhs, class Rhs>
    requires closure_has_simple_call_op<Lhs> && closure_has_simple_call_op<Rhs>
struct pipe<Lhs, Rhs> : range_adaptor_closure<pipe<Lhs, Rhs>> {
    [[no_unique_address]] Lhs lhs;
    [[no_unique_address]] Rhs rhs;

    constexpr pipe(Lhs _lhs, Rhs _rhs) noexcept(NO_EXCEPT) : lhs(std::move(_lhs)), rhs(std::move(_rhs)) {}

    template<class Range>
        requires pipe_invocable<const Lhs &, const Rhs &, Range>
    inline constexpr auto operator()(Range&& range) const noexcept(NO_EXCEPT) {
        return rhs(lhs(std::forward<Range>(range)));
    }

    static constexpr bool has_simple_call_op = true;
};


} // namespace views::adaptor


} // namespace uni