sequence.hpp

Go to the documentation of this file.

// SPDX-License-Identifier: BSD-2-Clause
 
#ifndef pRC_CORE_BASIC_SEQUENCE_H
#define pRC_CORE_BASIC_SEQUENCE_H
 
#include <prc/core/basic/direction.hpp>
#include <prc/core/basic/functions/isqrt.hpp>
#include <prc/core/basic/functions/max.hpp>
#include <prc/core/basic/limits.hpp>
#include <prc/core/basic/type_traits.hpp>
#include <prc/core/container/type_traits.hpp>
#include <prc/core/functors/add.hpp>
#include <prc/core/functors/div.hpp>
#include <prc/core/functors/equal.hpp>
#include <prc/core/functors/greater.hpp>
#include <prc/core/functors/greater_equal.hpp>
#include <prc/core/functors/less.hpp>
#include <prc/core/functors/less_equal.hpp>
#include <prc/core/functors/minus.hpp>
#include <prc/core/functors/mod.hpp>
#include <prc/core/functors/mul.hpp>
#include <prc/core/functors/sub.hpp>
 
namespace pRC
{
    template<class T, T... Seq>
    Sequence(std::integer_sequence<T, Seq...> const) -> Sequence<T, Seq...>;
 
    template<Size... Ns>
    Sequence(Sizes<Ns...> const) -> Sequence<Size, Ns...>;
 
    template<class T, T... Seq>
    class Sequence
    {
    public:
        using Type = T;
        using Dimension = Constant<Size, sizeof...(Seq)>;
 
        static constexpr auto value(Index const index)
        {
            return StackArray<T, Dimension{}>(Seq...)[index];
        }
 
    public:
        ~Sequence() = default;
        constexpr Sequence(Sequence const &) = default;
        constexpr Sequence(Sequence &&) = default;
        constexpr Sequence &operator=(Sequence const &) & = default;
        constexpr Sequence &operator=(Sequence &&) & = default;
        constexpr Sequence() = default;
        constexpr Sequence(std::integer_sequence<T, Seq...> const) {}
    };
 
    template<Size... Ns>
    class Sequence<Size, Ns...>
    {
    private:
        static constexpr auto linearizable()
        {
            if constexpr(((Ns != 0) && ...))
            {
                auto S = NumericLimits<Size>::max();
                ((S /= Ns), ...);
                return S != 0;
            }
            else
            {
                return true;
            }
        }
 
    public:
        using Type = Size;
        using Dimension = Constant<Size, sizeof...(Ns)>;
        using IsLinearizable = Constant<Bool, linearizable()>;
 
        static constexpr auto value(Index const index)
        {
            return StackArray<Size, Dimension{}>(Ns...)[index];
        }
 
        static constexpr auto size(Index const index)
        {
            return value(index);
        }
 
        template<class E = IsLinearizable, If<E> = 0>
        static constexpr auto size()
        {
            return (Ns * ... * Size(1));
        }
 
    public:
        ~Sequence() = default;
        constexpr Sequence(Sequence const &) = default;
        constexpr Sequence(Sequence &&) = default;
        constexpr Sequence &operator=(Sequence const &) & = default;
        constexpr Sequence &operator=(Sequence &&) & = default;
        constexpr Sequence() = default;
        constexpr Sequence(std::integer_sequence<Size, Ns...> const) {}
 
        explicit constexpr operator Size() const
        {
            return size();
        }
    };
 
    template<class T, T... As, T... Bs, If<IsInvocable<Add, T, T>> = 0,
        If<IsSatisfied<(sizeof...(As) == sizeof...(Bs))>> = 0>
    static inline constexpr auto operator+(Sequence<T, As...> const,
        Sequence<T, Bs...> const)
    {
        return Sequence<T, (As + Bs)...>();
    }
 
    template<class T, T... As, T B, If<IsInvocable<Add, T, T>> = 0>
    static inline constexpr auto operator+(Sequence<T, As...> const,
        Constant<T, B> const)
    {
        return Sequence<T, (As + B)...>();
    }
 
    template<class T, T A, T... Bs, If<IsInvocable<Add, T, T>> = 0>
    static inline constexpr auto operator+(Constant<T, A> const,
        Sequence<T, Bs...> const)
    {
        return Sequence<T, (A + Bs)...>();
    }
 
    template<class T, T... As, T... Bs, If<IsInvocable<Sub, T, T>> = 0,
        If<IsSatisfied<(sizeof...(As) == sizeof...(Bs))>> = 0>
    static inline constexpr auto operator-(Sequence<T, As...> const,
        Sequence<T, Bs...> const)
    {
        return Sequence<T, (As - Bs)...>();
    }
 
    template<class T, T... As, T B, If<IsInvocable<Sub, T, T>> = 0>
    static inline constexpr auto operator-(Sequence<T, As...> const,
        Constant<T, B> const)
    {
        return Sequence<T, (As - B)...>();
    }
 
    template<class T, T... As, T... Bs, If<IsInvocable<Mul, T, T>> = 0,
        If<IsSatisfied<(sizeof...(As) == sizeof...(Bs))>> = 0>
    static inline constexpr auto operator*(Sequence<T, As...> const,
        Sequence<T, Bs...> const)
    {
        return Sequence<T, (As * Bs)...>();
    }
 
    template<class T, T... As, T B, If<IsInvocable<Mul, T, T>> = 0>
    static inline constexpr auto operator*(Sequence<T, As...> const,
        Constant<T, B> const)
    {
        return Sequence<T, (As * B)...>();
    }
 
    template<class T, T A, T... Bs, If<IsInvocable<Mul, T, T>> = 0>
    static inline constexpr auto operator*(Constant<T, A> const,
        Sequence<T, Bs...> const)
    {
        return Sequence<T, (A * Bs)...>();
    }
 
    template<class T, T... As, T... Bs, If<IsInvocable<Div, T, T>> = 0,
        If<IsSatisfied<(sizeof...(As) == sizeof...(Bs))>> = 0>
    static inline constexpr auto operator/(Sequence<T, As...> const,
        Sequence<T, Bs...> const)
    {
        return Sequence<T, (As / Bs)...>();
    }
 
    template<class T, T... As, T B, If<IsInvocable<Div, T, T>> = 0>
    static inline constexpr auto operator/(Sequence<T, As...> const,
        Constant<T, B> const)
    {
        return Sequence<T, (As / B)...>();
    }
 
    template<class T, T... As, T... Bs, If<IsInvocable<Mod, T, T>> = 0,
        If<IsSatisfied<(sizeof...(As) == sizeof...(Bs))>> = 0>
    static inline constexpr auto operator%(Sequence<T, As...> const,
        Sequence<T, Bs...> const)
    {
        return Sequence<T, (As % Bs)...>();
    }
 
    template<class T, T... As, T B, If<IsInvocable<Mod, T, T>> = 0>
    static inline constexpr auto operator%(Sequence<T, As...> const,
        Constant<T, B> const)
    {
        return Sequence<T, (As % B)...>();
    }
 
    template<class T, T... Is, If<IsInvocable<Minus, T>> = 0>
    static inline constexpr auto operator-(Sequence<T, Is...> const)
    {
        return Sequence<T, -Is...>();
    }
 
    template<class T, T... As, T... Bs>
    static inline constexpr auto operator,(Sequence<T, As...> const,
        Sequence<T, Bs...> const)
    {
        return Sequence<T, As..., Bs...>();
    }
 
    template<class T, T... As, T... Bs,
        If<IsSatisfied<(sizeof...(As) == sizeof...(Bs))>> = 0>
    static inline constexpr auto operator==(Sequence<T, As...> const,
        Sequence<T, Bs...> const)
    {
        return ((As == Bs) && ...);
    }
 
    template<class T, T... As, T B>
    static inline constexpr auto operator==(Sequence<T, As...> const,
        Constant<T, B> const)
    {
        return ((As == B) && ...);
    }
 
    template<class T, T A, T... Bs>
    static inline constexpr auto operator==(Constant<T, A> const,
        Sequence<T, Bs...> const)
    {
        return ((A == Bs) && ...);
    }
 
    template<class T, T... As, T... Bs,
        If<IsSatisfied<(sizeof...(As) == sizeof...(Bs))>> = 0>
    static inline constexpr auto operator!=(Sequence<T, As...> const,
        Sequence<T, Bs...> const)
    {
        return ((As != Bs) || ...);
    }
 
    template<class T, T... As, T B>
    static inline constexpr auto operator!=(Sequence<T, As...> const,
        Constant<T, B> const)
    {
        return ((As != B) || ...);
    }
 
    template<class T, T A, T... Bs>
    static inline constexpr auto operator!=(Constant<T, A> const,
        Sequence<T, Bs...> const)
    {
        return ((A != Bs) || ...);
    }
 
    template<class T, T... As, T... Bs, If<IsInvocable<LessEqual, T, T>> = 0,
        If<IsSatisfied<(sizeof...(As) == sizeof...(Bs))>> = 0>
    static inline constexpr auto operator<=(Sequence<T, As...> const,
        Sequence<T, Bs...> const)
    {
        return ((As <= Bs) && ...);
    }
 
    template<class T, T... As, T B, If<IsInvocable<LessEqual, T, T>> = 0>
    static inline constexpr auto operator<=(Sequence<T, As...> const,
        Constant<T, B> const)
    {
        return ((As <= B) && ...);
    }
 
    template<class T, T A, T... Bs, If<IsInvocable<LessEqual, T, T>> = 0>
    static inline constexpr auto operator<=(Constant<T, A> const,
        Sequence<T, Bs...> const)
    {
        return ((A <= Bs) && ...);
    }
 
    template<class T, T... As, T... Bs, If<IsInvocable<GreaterEqual, T, T>> = 0,
        If<IsSatisfied<(sizeof...(As) == sizeof...(Bs))>> = 0>
    static inline constexpr auto operator>=(Sequence<T, As...> const,
        Sequence<T, Bs...> const)
    {
        return ((As >= Bs) && ...);
    }
 
    template<class T, T... As, T B, If<IsInvocable<GreaterEqual, T, T>> = 0>
    static inline constexpr auto operator>=(Sequence<T, As...> const,
        Constant<T, B> const)
    {
        return ((As >= B) && ...);
    }
 
    template<class T, T A, T... Bs, If<IsInvocable<GreaterEqual, T, T>> = 0>
    static inline constexpr auto operator>=(Constant<T, A> const,
        Sequence<T, Bs...> const)
    {
        return ((A >= Bs) && ...);
    }
 
    template<class T, T... As, T... Bs, If<IsInvocable<Equal, T, T>> = 0,
        If<IsSatisfied<(sizeof...(As) == sizeof...(Bs))>> = 0>
    static inline constexpr auto operator<(Sequence<T, As...> const,
        Sequence<T, Bs...> const)
    {
        return ((As < Bs) && ...);
    }
 
    template<class T, T... As, T B, If<IsInvocable<Equal, T, T>> = 0>
    static inline constexpr auto operator<(Sequence<T, As...> const,
        Constant<T, B> const)
    {
        return ((As < B) && ...);
    }
 
    template<class T, T A, T... Bs, If<IsInvocable<Equal, T, T>> = 0>
    static inline constexpr auto operator<(Constant<T, A> const,
        Sequence<T, Bs...> const)
    {
        return ((A < Bs) && ...);
    }
 
    template<class T, T... As, T... Bs, If<IsInvocable<Equal, T, T>> = 0,
        If<IsSatisfied<(sizeof...(As) == sizeof...(Bs))>> = 0>
    static inline constexpr auto operator>(Sequence<T, As...> const,
        Sequence<T, Bs...> const)
    {
        return ((As > Bs) && ...);
    }
 
    template<class T, T... As, T B, If<IsInvocable<Equal, T, T>> = 0>
    static inline constexpr auto operator>(Sequence<T, As...> const,
        Constant<T, B> const)
    {
        return ((As > B) && ...);
    }
 
    template<class T, T A, T... Bs, If<IsInvocable<Equal, T, T>> = 0>
    static inline constexpr auto operator>(Constant<T, A> const,
        Sequence<T, Bs...> const)
    {
        return ((A > Bs) && ...);
    }
 
    template<class T, T... Seq, class F, class... Xs,
        If<IsInvocable<F, Xs..., Constant<T, Seq>...>> = 0>
    static inline constexpr decltype(auto) expand(Sequence<T, Seq...> const,
        F &&f, Xs &&...args)
    {
        return forward<F>(f)(forward<Xs>(args)..., Constant<T, Seq>()...);
    }
 
    template<class T, T N>
    static inline constexpr auto makeSeries()
    {
        return Sequence(std::make_integer_sequence<T, N>());
    }
 
    template<class T>
    static inline constexpr auto makeSeriesFor()
    {
        return Sequence<T>();
    }
 
    template<class T, class... Ts, If<IsSatisfied<(sizeof...(Ts) > 0)>> = 0>
    static inline constexpr auto makeSeriesFor()
    {
        return makeSeries<T, sizeof...(Ts)>();
    }
 
    template<class T, auto... Ts, If<IsSatisfied<(sizeof...(Ts) > 0)>> = 0>
    static inline constexpr auto makeSeriesFor()
    {
        return makeSeries<T, sizeof...(Ts)>();
    }
 
    template<class T, T First, T Last, Direction D = Direction::Forwards,
        T Step = T(1),
        If<IsSatisfied<(
            D == Direction::Forwards || D == Direction::Backwards)>> = 0,
        If<IsSatisfied<((Last - First) % Step == 0)>> = 0>
    static inline constexpr auto makeRange()
    {
        if constexpr(First > Last)
        {
            return Sequence<T>();
        }
        else
        {
            if constexpr(D == Direction::Forwards)
            {
                return makeSeries<T, (Last - First) / Step>() *
                    Constant<T, Step>() +
                    Constant<T, First>();
            }
            if constexpr(D == Direction::Backwards)
            {
                return reverse(
                    makeRange<T, First, Last, Direction::Forwards, Step>());
            }
        }
    }
 
    template<class T, Size N, T V>
    static inline constexpr auto makeConstantSequence()
    {
        if constexpr(N == 0)
        {
            return Sequence<T>();
        }
        else
        {
            return Sequence<T, V>(), makeConstantSequence<T, N - Size(1), V>();
        }
    }
 
    template<class F, class T, T I1, T I2, T... Is,
        If<IsInvocable<F, T, T>> = 0>
    static inline constexpr auto reduce(Sequence<T, I1, I2, Is...> const)
    {
        constexpr auto I = F()(I1, I2);
 
        if constexpr(sizeof...(Is) == 0)
        {
            return I;
        }
        else
        {
            return reduce<F>(Sequence<T, I, Is...>());
        }
    }
 
    template<class F, class T, T I>
    static inline constexpr auto reduce(Sequence<T, I> const)
    {
        return I;
    }
 
    template<Index... Ps, class T, T... Is,
        If<IsSatisfied<(sizeof...(Is) == sizeof...(Ps))>> = 0,
        If<IsSatisfied<((Ps < sizeof...(Is)) && ...)>> = 0,
        If<IsUnique<Constant<Index, Ps>...>> = 0>
    static inline constexpr auto permute(Sequence<T, Is...> const)
    {
        return Sequence<T, Sequence<T, Is...>::value(Ps)...>();
    }
 
    template<class T, T... Is>
    static inline constexpr auto reverse(Sequence<T, Is...> const)
    {
        return expand(makeSeriesFor<Index, Is...>(),
            [](auto const... is)
            {
                return Sequence<T,
                    Sequence<T, Is...>::value(
                        sizeof...(is) - Size(1) - is)...>();
            });
    }
 
    template<Direction D, Size Step, class T, T First, T... Is,
        If<IsSatisfied<(
            D == Direction::Leftwards || D == Direction::Rightwards)>> = 0>
    static inline constexpr auto rotate(Sequence<T, First, Is...> const)
    {
        if constexpr(D == Direction::Leftwards)
        {
            if constexpr(Step == 0)
            {
                return Sequence<T, First, Is...>();
            }
            else
            {
                return rotate<D, Step - Size(1)>(Sequence<T, Is..., First>());
            }
        }
        if constexpr(D == Direction::Rightwards)
        {
            return reverse(rotate<Direction::Leftwards, Step>(
                reverse(Sequence<Index, First, Is...>())));
        }
    }
 
    template<Direction D, Size Step, class T,
        If<IsSatisfied<(
            D == Direction::Leftwards || D == Direction::Rightwards)>> = 0>
    static inline constexpr auto rotate(Sequence<T> const)
    {
        return Sequence<T>();
    }
 
    template<Index O = 0, class T, T... Is, class... Seqs,
        If<IsSatisfied<((Sequence<T, Is...>::size() == Seqs::size()) && ...)>> =
            0>
    static inline constexpr auto zip(Sequence<T, Is...> const, Seqs const...)
    {
        using S = Sequence<T, Is...>;
 
        if constexpr(O < S::size() - 1)
        {
            return (Sequence<T, S::value(O), Seqs::value(O)...>(),
                zip<O + 1>(S(), Seqs()...));
        }
        else
        {
            return Sequence<T, S::value(O), Seqs::value(O)...>();
        }
    }
 
    template<class F, class T, T... Is>
    static inline constexpr auto filter(Sequence<T, Is...> const)
    {
        if constexpr(sizeof...(Is) == 0)
        {
            return Sequence<T>();
        }
        else if constexpr(sizeof...(Is) == 1)
        {
            if constexpr(F()(Is...))
            {
                return Sequence<T, Is...>();
            }
            else
            {
                return Sequence<T>();
            }
        }
        else
        {
            return (filter<F>(Sequence<T, Is>()), ...);
        }
    }
 
    template<class F, class T, T... As, T... Bs, class... Seqs,
        If<IsInvocable<F, T, T>> = 0,
        If<IsSatisfied<((Sequence<T, As...>::size() == Seqs::size()) && ... &&
            (Sequence<T, As...>::size() == Sequence<T, Bs...>::size()))>> = 0>
    static inline constexpr auto pick(Sequence<T, As...> const,
        Sequence<T, Bs...> const, Seqs const...)
    {
        if constexpr(sizeof...(Seqs) == 0)
        {
            return Sequence<T, F()(As, Bs)...>();
        }
        else
        {
            return pick<F>(Sequence<T, F()(As, Bs)...>(), Seqs()...);
        }
    }
 
    template<Index D, Index... Ds, class T, T... Is,
        If<IsSatisfied<(sizeof...(Ds) < sizeof...(Is))>> = 0,
        If<IsSatisfied<(max(D, Ds...) < sizeof...(Is))>> = 0,
        If<IsUnique<Constant<Index, D>, Constant<Index, Ds>...>> = 0>
    static inline constexpr auto chip(Sequence<T, Is...> const)
    {
        if constexpr(sizeof...(Ds) != 0)
        {
            return chip<((Ds < D) ? Ds : Ds - 1)...>(
                chip<D>(Sequence<T, Is...>()));
        }
        else
        {
            return expand((makeSeries<Index, D>(),
                              makeRange<Index, D + 1, sizeof...(Is)>()),
                [](auto const... seq)
                {
                    return Sequence<T, Sequence<T, Is...>::value(seq)...>();
                });
        }
    }
 
    template<class T, T... Is>
    static inline constexpr auto chip(Sequence<T, Is...> const)
    {
        return Sequence<T, Is...>();
    }
 
    template<Index S, Index... Ss, class T, T... Is,
        If<IsSatisfied<(sizeof...(Ss) < sizeof...(Is))>> = 0,
        If<IsSatisfied<(max(S, Ss...) < sizeof...(Is))>> = 0,
        If<IsUnique<Constant<Index, S>, Constant<Index, Ss>...>> = 0>
    static inline constexpr auto select(Sequence<T, Is...> const)
    {
        if constexpr(sizeof...(Ss) != 0)
        {
            return (Sequence<T, Sequence<T, Is...>::value(S)>(),
                select<Ss...>(Sequence<T, Is...>()));
        }
        else
        {
            return Sequence<T, Sequence<T, Is...>::value(S)>();
        }
    }
 
    template<class T, T... Is>
    static inline constexpr auto select(Sequence<T, Is...> const)
    {
        return Sequence<T>();
    }
 
    template<Index B, Index P, class T, T... Is,
        If<IsSatisfied<(sizeof...(Is) % B == 0)>> = 0,
        If<IsSatisfied<(P < B)>> = 0>
    static inline constexpr auto cut(Sequence<T, Is...> const)
    {
        return expand(makeSeries<Index, sizeof...(Is) / B>() +
                Constant<Index, P * sizeof...(Is) / B>(),
            [](auto const... is)
            {
                return Sequence<T, Sequence<T, Is...>::value(is)...>();
            });
    }
 
    template<Index I, Index L, class T, T... Is,
        If<IsSatisfied<(L <= sizeof...(Is))>> = 0, If<IsSatisfied<(I < L)>> = 0>
    static inline constexpr auto trim(Sequence<T, Is...> const)
    {
        return expand(makeRange<Index, I, L>(),
            [](auto const... is)
            {
                return select<is...>(Sequence<T, Is...>());
            });
    }
 
    template<class F = Less, class T, T I, T... Is,
        If<IsInvocableResult<Bool, F, T, T>> = 0>
    static inline constexpr auto sort(Sequence<T, I, Is...> const)
    {
        if constexpr(sizeof...(Is) == 0)
        {
            return Sequence<T, I>();
        }
        else if constexpr((F()(I, Is) && ...))
        {
            return (Sequence<T, I>(), sort<F>(Sequence<T, Is...>()));
        }
        else
        {
            return sort<F>(Sequence<T, Is..., I>());
        }
    }
 
    template<class T, T From, T... Froms, T To, T... Tos, T P, T... Ps,
        If<IsSatisfied<(sizeof...(Froms) == sizeof...(Tos) &&
            sizeof...(Froms) == sizeof...(Ps))>> = 0>
    static inline constexpr auto getPermutation(
        Sequence<T, From, Froms...> const, Sequence<T, To, Tos...> const,
        Sequence<T, P, Ps...> const)
    {
        {
            if constexpr(From != To)
            {
                return getPermutation(Sequence<T, Froms..., From>(),
                    Sequence<T, To, Tos...>(), Sequence<T, Ps..., P>());
            }
            else if constexpr(sizeof...(Froms) > 0)
            {
                return (Sequence<T, P>(),
                    getPermutation(Sequence<T, Froms...>(),
                        Sequence<T, Tos...>(), Sequence<T, Ps...>()));
            }
            else
            {
                return Sequence<T, P>();
            }
        }
    }
 
    template<class T, T... Froms, T... Tos,
        If<IsSatisfied<(sizeof...(Froms) == sizeof...(Tos))>> = 0>
    static inline constexpr auto getPermutation(Sequence<T, Froms...> const,
        Sequence<T, Tos...> const)
    {
        return getPermutation(Sequence<T, Froms...>(), Sequence<T, Tos...>(),
            makeSeriesFor<T, Froms...>());
    }
 
    template<class T, T... Froms>
    static inline constexpr auto getPermutation(Sequence<T, Froms...> const)
    {
        return getPermutation(Sequence<T, Froms...>(),
            sort(Sequence<T, Froms...>()));
    }
 
    template<class T, T N, T... Ps>
    static inline constexpr auto integerFactorization(Constant<T, N> const,
        Sequence<T, Ps...> const = Sequence<T>())
    {
        constexpr auto P = []()
        {
            if(N == 0)
            {
                return T(0);
            }
 
            if(N % 2 == 0)
            {
                return T(2);
            }
 
            for(T i = 3; i <= iSqrt(N); i += 2)
            {
                if(N % i == 0)
                {
                    return i;
                }
            }
 
            return N;
        }();
 
        if constexpr(P == N)
        {
            return Sequence<T, Ps..., N>();
        }
        else
        {
            return integerFactorization(Constant<T, N / P>(),
                Sequence<T, Ps..., P>());
        }
    }
}
#endif // pRC_CORE_BASIC_SEQUENCE_H