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/concepts.hpp>
#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/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/not_equal.hpp>
#include <prc/core/functors/sub.hpp>
#include <prc/core/log/log.hpp>
 
namespace pRC
{
    template<class T, T... Seq>
    class Sequence
    {
    private:
        static constexpr auto linearizable()
        {
            if constexpr(((Seq != 0) && ...))
            {
                auto S = NumericLimits<T>::max();
                ((S /= Seq), ...);
                return S != 0;
            }
            else
            {
                return true;
            }
        }
 
    public:
        using Type = T;
        static constexpr Size Dimension = sizeof...(Seq);
 
        static constexpr auto value(Index const index)
        {
            if constexpr(cDebugLevel >= DebugLevel::Low)
            {
                if(!(index < Dimension))
                {
                    Logging::error(Sequence(), "index out of range.");
                }
            }
 
            using Array = Type[Dimension];
            return Array{Seq...}[index];
        }
 
        static constexpr auto size(Index const index)
            requires IsSame<Size, T>
        {
            return value(index);
        }
 
        static constexpr auto size()
            requires IsSame<Size, T> && (linearizable())
        {
            return (Seq * ... * T(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;
 
        explicit constexpr operator T() const
            requires requires { size(); }
        {
            return size();
        }
    };
 
    template<class T>
    concept IsSequence = !IsReference<T> && requires {
        {
            []<class U, U... Seq>(Sequence<U, Seq...> const &&)
            {
            }(declval<T>())
        };
    };
 
    template<Size... Ns>
    using Sizes = Sequence<Size, Ns...>;
 
    template<class T>
    concept IsSizes = IsSequence<T> && IsSize<typename T::Type>;
 
    template<class T, T... As, T... Bs>
        requires IsInvocable<Add, T, T> && (sizeof...(As) == sizeof...(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 B>
        requires IsInvocable<Add, T, T>
    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>
        requires IsInvocable<Add, T, T>
    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>
        requires IsInvocable<Sub, T, T> && (sizeof...(As) == sizeof...(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 B>
        requires IsInvocable<Sub, T, T>
    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>
        requires IsInvocable<Sub, T, T>
    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>
        requires IsInvocable<Mul, T, T> && (sizeof...(As) == sizeof...(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 B>
        requires IsInvocable<Mul, T, T>
    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>
        requires IsInvocable<Mul, T, T>
    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>
        requires IsInvocable<Div, T, T> && (sizeof...(As) == sizeof...(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 B>
        requires IsInvocable<Div, T, T>
    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>
        requires IsInvocable<Div, T, T>
    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>
        requires IsInvocable<Mod, T, T> && (sizeof...(As) == sizeof...(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 B>
        requires IsInvocable<Mod, T, T>
    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>
        requires IsInvocable<Mod, T, T>
    static inline constexpr auto operator%(Constant<T, A> const,
        Sequence<T, Bs...> const)
    {
        return Sequence<T, (A % Bs)...>();
    }
 
    template<class T, T... Is>
        requires IsInvocable<Minus, T>
    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<IsSequence A, IsSequence B>
    static inline constexpr auto operator==(A const, B const)
    {
        return IsSame<A, B>;
    }
 
    template<class T, T... As, T B>
        requires IsInvocable<Equal, T, T>
    static inline constexpr auto operator==(Sequence<T, As...> const,
        Constant<T, B> const)
    {
        return ((As == B) && ...);
    }
 
    template<class T, T A, T... Bs>
        requires IsInvocable<Equal, T, T>
    static inline constexpr auto operator==(Constant<T, A> const,
        Sequence<T, Bs...> const)
    {
        return ((A == Bs) && ...);
    }
 
    template<IsSequence A, IsSequence B>
    static inline constexpr auto operator!=(A const, B const)
    {
        return !IsSame<A, B>;
    }
 
    template<class T, T... As, T B>
        requires IsInvocable<NotEqual, T, T>
    static inline constexpr auto operator!=(Sequence<T, As...> const,
        Constant<T, B> const)
    {
        return ((As != B) || ...);
    }
 
    template<class T, T A, T... Bs>
        requires IsInvocable<NotEqual, T, T>
    static inline constexpr auto operator!=(Constant<T, A> const,
        Sequence<T, Bs...> const)
    {
        return ((A != Bs) || ...);
    }
 
    template<class T, T... As, T... Bs>
        requires IsInvocable<LessEqual, T, T> &&
        (sizeof...(As) == sizeof...(Bs))
    static inline constexpr auto operator<=(Sequence<T, As...> const,
        Sequence<T, Bs...> const)
    {
        return ((As <= Bs) && ...);
    }
 
    template<class T, T... As, T B>
        requires IsInvocable<LessEqual, T, T>
    static inline constexpr auto operator<=(Sequence<T, As...> const,
        Constant<T, B> const)
    {
        return ((As <= B) && ...);
    }
 
    template<class T, T A, T... Bs>
        requires IsInvocable<LessEqual, T, T>
    static inline constexpr auto operator<=(Constant<T, A> const,
        Sequence<T, Bs...> const)
    {
        return ((A <= Bs) && ...);
    }
 
    template<class T, T... As, T... Bs>
        requires IsInvocable<GreaterEqual, T, T> &&
        (sizeof...(As) == sizeof...(Bs))
    static inline constexpr auto operator>=(Sequence<T, As...> const,
        Sequence<T, Bs...> const)
    {
        return ((As >= Bs) && ...);
    }
 
    template<class T, T... As, T B>
        requires IsInvocable<GreaterEqual, T, T>
    static inline constexpr auto operator>=(Sequence<T, As...> const,
        Constant<T, B> const)
    {
        return ((As >= B) && ...);
    }
 
    template<class T, T A, T... Bs>
        requires IsInvocable<GreaterEqual, T, T>
    static inline constexpr auto operator>=(Constant<T, A> const,
        Sequence<T, Bs...> const)
    {
        return ((A >= Bs) && ...);
    }
 
    template<class T, T... As, T... Bs>
        requires IsInvocable<Less, T, T> && (sizeof...(As) == sizeof...(Bs))
    static inline constexpr auto operator<(Sequence<T, As...> const,
        Sequence<T, Bs...> const)
    {
        return ((As < Bs) && ...);
    }
 
    template<class T, T... As, T B>
        requires IsInvocable<Less, T, T>
    static inline constexpr auto operator<(Sequence<T, As...> const,
        Constant<T, B> const)
    {
        return ((As < B) && ...);
    }
 
    template<class T, T A, T... Bs>
        requires IsInvocable<Less, T, T>
    static inline constexpr auto operator<(Constant<T, A> const,
        Sequence<T, Bs...> const)
    {
        return ((A < Bs) && ...);
    }
 
    template<class T, T... As, T... Bs>
        requires IsInvocable<Greater, T, T> && (sizeof...(As) == sizeof...(Bs))
    static inline constexpr auto operator>(Sequence<T, As...> const,
        Sequence<T, Bs...> const)
    {
        return ((As > Bs) && ...);
    }
 
    template<class T, T... As, T B>
        requires IsInvocable<Greater, T, T>
    static inline constexpr auto operator>(Sequence<T, As...> const,
        Constant<T, B> const)
    {
        return ((As > B) && ...);
    }
 
    template<class T, T A, T... Bs>
        requires IsInvocable<Greater, T, T>
    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>
        requires IsInvocable<F, Xs..., Constant<T, Seq>...>
    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 []<T... Ns>(std::integer_sequence<T, Ns...> const)
        {
            return Sequence<T, Ns...>();
        }(std::make_integer_sequence<T, N>());
    }
 
    template<class T>
    static inline constexpr auto makeSeriesFor()
    {
        return Sequence<T>();
    }
 
    template<class T, class... Ts>
        requires(sizeof...(Ts) > 0)
    static inline constexpr auto makeSeriesFor()
    {
        return makeSeries<T, sizeof...(Ts)>();
    }
 
    template<class T, auto... Ts>
        requires(sizeof...(Ts) > 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)>
        requires(D == Direction::Forwards)
    static inline constexpr auto makeRange()
    {
        if constexpr(First >= Last)
        {
            return Sequence<T>();
        }
        else
        {
            return makeSeries<T, ceilDiv(Last - First, Step)>() *
                Constant<T, Step>() +
                Constant<T, First>();
        }
    }
 
    template<class T, T First, T Last, Direction D = Direction::Forwards,
        T Step = T(1)>
        requires(D == Direction::Backwards)
    static inline constexpr auto makeRange()
    {
        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>
        requires IsInvocable<F, T, T>
    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 F()(I, reduce<F>(Sequence<T, Is...>()));
        }
    }
 
    template<class F, class T, T I>
    static inline constexpr auto reduce(Sequence<T, I> const)
    {
        return I;
    }
 
    template<class F, class T>
    static inline constexpr auto reduce(Sequence<T> const)
    {
        return F::template Identity<T>();
    }
 
    template<Index... Ps, class T, T... Is>
        requires((sizeof...(Is) == sizeof...(Ps))) &&
        (((Ps < sizeof...(Is)) && ...))
    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... Is>
        requires(D == Direction::Leftwards || D == Direction::Rightwards)
    static inline constexpr auto rotate(Sequence<T, Is...> const)
    {
        return expand(makeSeriesFor<Index, Is...>(),
            [](auto const... seq)
            {
                if constexpr(D == Direction::Leftwards)
                {
                    return permute<(seq + Step % sizeof...(Is)) %
                        sizeof...(Is)...>(Sequence<T, Is...>());
                }
                if constexpr(D == Direction::Rightwards)
                {
                    return permute<(seq +
                                       (sizeof...(Is) - Step % sizeof...(Is))) %
                        sizeof...(Is)...>(Sequence<T, Is...>());
                }
            });
    }
 
    template<Index O = 0, class T, T... Is, class... Seqs>
        requires((Sequence<T, Is...>::size() == Seqs::size()) && ...)
    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>
        requires IsInvocable<F, T, T> && (sizeof...(As) == sizeof...(Bs)) &&
        ((sizeof...(As) == Seqs::Dimension) && ...)
    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>
        requires(sizeof...(Ds) < sizeof...(Is) && max(D, Ds...) < sizeof...(Is))
    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>
        requires(sizeof...(Ss) < sizeof...(Is) && max(S, Ss...) < sizeof...(Is))
    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>
        requires(sizeof...(Is) % B == 0 && P < B)
    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>
        requires(L <= sizeof...(Is) && I < L)
    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>
        requires IsPredicate<F, T, T>
    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>
        requires(sizeof...(Froms) == sizeof...(Tos) &&
            sizeof...(Froms) == sizeof...(Ps))
    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>
        requires(sizeof...(Froms) == sizeof...(Tos))
    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