Created
November 8, 2026 09:03
-
-
Save PyMaster22/a619dcd009aaa67cc329776c6ff35523 to your computer and use it in GitHub Desktop.
Type-level metaprogramming in C++. A few features are broken or bad, so I am archiving it and starting on a v2.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| /* Requires preprocessing with something that understands variadic macros first. */ | |
| #define CPP11 201103L | |
| #define CPP_EMPTY() | |
| #define CPP_DEFER(macro) macro CPP_EMPTY() | |
| #define CPP_GlueHelper_Actual(x,y) x##y | |
| #define CPP_Glue(x,y) CPP_GlueHelper_Actual(x,y) | |
| #define CPP_Identity(x) x | |
| #define CPP_fst(x,...) x | |
| #define CPP_snd(x,...) CPP_fst(__VA_ARGS__,CPP_Nil) | |
| #define CPP_IsProbe(...) CPP_snd(__VA_ARGS__,0) | |
| #define CPP_Probe() idk, 1 | |
| #define CPP_NotHelpers_0 CPP_Probe() | |
| #define CPP_Not(Bool) CPP_IsProbe(CPP_Glue(CPP_NotHelpers_,Bool)) | |
| #define CPP_Bool(Anything) CPP_Not(CPP_Not(Anything)) | |
| #define CPP_IfHelper_0(t,...) __VA_ARGS__ | |
| #define CPP_IfHelper_1(t,...) t | |
| #define CPP_If(condition) CPP_Glue(CPP_IfHelper_,condition) | |
| #define CPP_Car(cons) CPP_fst cons | |
| #define CPP_Cdr(cons) CPP_snd cons | |
| #define CPP_IsPairProbe(...) CPP_Probe() | |
| #define CPP_IsPair(x) CPP_IsProbe(CPP_IsPairProbe x) | |
| #define CPP_MapIndirection() CPP_Map | |
| #define CPP_MapStep(func,cons) (func(CPP_Car(cons)),CPP_DEFER(CPP_MapIndirection)()(func,CPP_Cdr(cons))) | |
| #define CPP_MapEnd(func,cons) CPP_Nil | |
| #define CPP_Map(func,cons) CPP_If(CPP_IsPair(cons))(CPP_MapStep,CPP_MapEnd)(func,cons) | |
| #define CPP_EachIndirection() CPP_Each | |
| #define CPP_EachStep(func,cons) func(CPP_Car(cons)) CPP_DEFER(CPP_EachIndirection)()(func,CPP_Cdr(cons)) | |
| #define CPP_EachEnd(func,cons) | |
| #define CPP_Each(func,cons) CPP_If(CPP_IsPair(cons))(CPP_EachStep,CPP_EachEnd)(func,cons) | |
| #define CPP_Eval0(x) x | |
| #define CPP_Eval1(x) CPP_Eval0(CPP_Eval0(CPP_Eval0(CPP_Eval0(CPP_Eval0(x))))) | |
| #define CPP_Eval2(x) CPP_Eval1(CPP_Eval1(CPP_Eval1(CPP_Eval1(CPP_Eval1(x))))) | |
| #define CPP_Eval3(x) CPP_Eval2(CPP_Eval2(CPP_Eval2(CPP_Eval2(CPP_Eval2(x))))) | |
| #define CPP_Eval4(x) CPP_Eval3(CPP_Eval3(CPP_Eval3(CPP_Eval3(CPP_Eval3(x))))) | |
| #define CPP_Hash # | |
| /* The only* specialized functions */ | |
| struct True; | |
| struct False; | |
| template<class LHS, class RHS> struct Equal; | |
| template<class Condition, class TrueCase, class FalseCase> struct Ternary; | |
| template<class LHS, class RHS> struct Equal{typedef False value;}; | |
| template<class LHS> struct Equal<LHS,LHS>{typedef True value;}; | |
| template<class T, class F> struct Ternary<False,T,F>{typedef F value;}; | |
| template<class T, class F> struct Ternary<True ,T,F>{typedef T value;}; | |
| #if (__cplusplus >= CPP11) || (!defined(__cplusplus)) | |
| #if !defined(__cplusplus) | |
| CPP_Hash if (CPP_GlueHelper_Actual(__,cplusplus) >= CPP11) | |
| #endif | |
| template<class...> struct ArgContainer; | |
| struct NoArgs; | |
| template<class Type, class Object> struct IsType; | |
| template<class...> struct HasArgs; | |
| template<class... Args> struct TakeFirstArg; | |
| template<class... Args> struct DropFirstArg; | |
| template<template<class...>class Function, class ArgContainer> struct FunctionApplier; | |
| template<class Type, class Object> struct IsType{typedef False value;}; | |
| template<template<class...> class Type, class... GenericArgs, class... ObjectArgs> struct IsType<Type<GenericArgs...>,Type<ObjectArgs...> >{typedef True value;}; | |
| template<> struct HasArgs<>{typedef False value;}; | |
| template<> struct HasArgs<ArgContainer<> >{typedef False value;}; | |
| template<class... Args> struct HasArgs{typedef True value;}; | |
| template<> struct TakeFirstArg<>{typedef NoArgs value;}; | |
| template<class Arg1, class... Args> struct TakeFirstArg<Arg1,Args...>{typedef Arg1 value;}; | |
| template<> struct DropFirstArg<>{typedef ArgContainer<> value;}; | |
| template<class Arg1, class... Args> struct DropFirstArg<Arg1,Args...>{typedef ArgContainer<Args...> value;}; | |
| template<template<class...>class Function, class... Args> struct FunctionApplier<Function,ArgContainer<Args...>>{typedef typename Function<Args...>::value value;}; | |
| #if !defined(__cplusplus) | |
| CPP_Hash endif | |
| #endif | |
| #endif | |
| template<class E> struct Error; | |
| template<class X> struct I; | |
| template<class X> struct I{typedef X value;}; | |
| template<class X> struct LNot; | |
| template<class X> struct BooleanCast; | |
| template<class X, class Y> struct LAnd; | |
| template<class X, class Y> struct LOr; | |
| template<class X, class Y> struct LXor; | |
| template<class X, class Y> struct LImplies; | |
| template<class X> struct LNot{typedef typename Equal<X,False>::value value;}; /* Only one falsy value */ | |
| template<class X> struct BooleanCast{typedef typename LNot<typename LNot<X>::value>::value value;}; | |
| template<class X, class Y> struct LAnd{typedef typename Ternary<typename BooleanCast<X>::value, BooleanCast<Y>, I<False> >::value::value value;}; | |
| template<class X, class Y> struct LOr{typedef typename Ternary<typename BooleanCast<X>::value, I<True>, BooleanCast<Y> >::value::value value;}; | |
| //template<class X, class Y> struct LXor{typedef typename LNot<typename Equal<typename BooleanCast<X>::value, typename BooleanCast<Y>::value>::value>::value value;}; | |
| template<class X, class Y> struct LXor{typedef typename Ternary<typename BooleanCast<X>::value,LNot<Y>,BooleanCast<Y> >::value::value value;}; | |
| template<class X, class Y> struct LImplies{typedef typename Ternary<typename BooleanCast<X>::value, BooleanCast<Y>, I<True> >::value::value value;}; | |
| struct Nil; | |
| template<class Car, class Cdr> struct Cons; | |
| template<template<class> class Funtion, class ConsArr> struct Map; | |
| template<template<class> class Predicate, class ConsArr> struct Filter; | |
| template<template<class, class> class Function, class ConsArr, class InitialLHS> struct FoldLeft; | |
| template<class ConsArr, class Value> struct Prepend; | |
| template<class ConsArr, class Value> struct Append; | |
| template<class LeftArr, class RightArr> struct Concat; | |
| template<class ConsArr, class Value> struct MemberOf; | |
| /* I won't consider this a rule breaking, as technically, with an oracle of IsType, this is possible without specialization. | |
| * See below; C++11 allows, C++98 is a lot more restrictive in what we can do. */ | |
| template<class ConsMaybe> struct IsCons; | |
| #if (__cplusplus >= CPP11) || (!defined(__cplusplus)) | |
| #if !defined(__cplusplus) | |
| CPP_Hash if (CPP_GlueHelper_Actual(__,cplusplus) >= CPP11) | |
| #endif | |
| template<class ConsMaybe> struct IsCons{typedef typename Ternary<typename Equal<ConsMaybe,Nil>::value,I<True>,IsType<Cons<Nil,Nil>,ConsMaybe> >::value::value value;}; | |
| template<class... Args> struct Consify; | |
| template<class... Args> struct Consify{typedef typename Ternary<typename HasArgs<Args...>::value,Cons<typename Ternary<typename Equal<typename TakeFirstArg<Args...>::value,NoArgs>::value,I<Nil>,TakeFirstArg<Args...> >::value::value,typename Ternary<typename HasArgs<typename DropFirstArg<Args...>::value>::value,FunctionApplier<Consify,typename DropFirstArg<Args...>::value>,I<Nil> >::value::value>,Nil>::value value;}; | |
| #endif | |
| #if !defined(__cplusplus) | |
| CPP_Hash else | |
| #endif | |
| #if (__cplusplus < CPP11) || (!defined(__cplusplus)) | |
| template<class ConsMaybe> struct IsCons{typedef typename Equal<ConsMaybe,Nil>::value value;}; | |
| template<class Car, class Cdr> struct IsCons<Cons<Car,Cdr> >{typedef True value;}; | |
| #if !defined(__cplusplus) | |
| CPP_Hash endif | |
| #endif | |
| #endif | |
| struct Nil{ | |
| typedef Nil car; | |
| typedef Nil cdr; | |
| }; | |
| template<class Car, class Cdr> struct Cons{ | |
| typedef Car car; | |
| typedef Cdr cdr; | |
| }; | |
| template<template<class> class Function, class ConsArr> struct Map{ | |
| typedef Cons< | |
| typename Function<typename ConsArr::car>::value, | |
| typename Ternary<typename Equal<typename ConsArr::cdr,Nil>::value, | |
| I<Nil>, | |
| Map<Function, typename ConsArr::cdr> | |
| >::value::value | |
| > value; | |
| }; | |
| template<template<class> class Predicate, class ConsArr> struct Filter{ | |
| private: /* hygiene */ | |
| typedef typename Ternary<typename Equal<typename ConsArr::cdr,Nil>::value, | |
| I<Nil>, | |
| Filter<Predicate, typename ConsArr::cdr> | |
| >::value::value Rest; | |
| public: | |
| typedef typename Ternary<typename Predicate<typename ConsArr::car>::value, | |
| Cons<typename ConsArr::car, Rest>, | |
| Rest | |
| >::value value; | |
| }; | |
| template<template<class, class> class Function, class ConsArr, class LHS> struct FoldLeft{ | |
| private: | |
| typedef typename Ternary<typename Equal<typename ConsArr::car,Nil>::value,I<LHS>,Function<LHS,typename ConsArr::car> >::value::value Applied; | |
| public: | |
| typedef typename Ternary<typename Equal<typename ConsArr::cdr,Nil>::value, | |
| I<Applied>, | |
| FoldLeft<Function, typename ConsArr::cdr, Applied> | |
| >::value::value value; | |
| }; | |
| template<class ConsArr, class Value> struct Prepend{ | |
| typedef Cons<Value,ConsArr> value; | |
| }; | |
| template<class ConsArr, class Value> struct Append{ | |
| private: | |
| typedef typename Equal<typename ConsArr::cdr,Nil>::value Predicate; | |
| public: | |
| typedef Cons< | |
| typename Ternary<Predicate, Value, typename ConsArr::car>::value, | |
| typename Ternary<Predicate, I<Nil>, Append<typename ConsArr::cdr, Value> >::value::value | |
| > value; | |
| }; | |
| template<class LeftArr, class RightArr> struct Concat{ | |
| typedef typename Ternary<typename Equal<LeftArr,Nil>::value, | |
| RightArr, | |
| Cons< | |
| typename LeftArr::car, | |
| typename Ternary<typename Equal<typename LeftArr::cdr,Nil>::value, | |
| I<RightArr>, | |
| Concat<typename LeftArr::cdr, RightArr> | |
| >::value::value | |
| > >::value value; | |
| }; | |
| template<class ConsArr, class Value> struct MemberOf{ | |
| typedef typename Ternary<typename Equal<typename ConsArr::car,Value>::value, | |
| I<I<True> >, | |
| Ternary<typename Equal<typename ConsArr::cdr,Nil>::value, | |
| I<False>, | |
| MemberOf<typename ConsArr::cdr, Value> | |
| > >::value::value::value value; | |
| }; | |
| /* association con or smth sounded funy */ | |
| /* Cons<Cons<key,Cons<value,Nil> >,Cons<Cons<key2,Cons<value2,Nil> >, ... > > */ | |
| template<class AssocCons, class Key> struct AssocLookup; | |
| template<class AssocCons, class Key, class Value> struct AssocAdd; | |
| template<class AssocCons, class Key> struct AssocRemove; | |
| template<class AssocCons> struct AssocKeys; | |
| template<class AssocOld, class AssocNew> struct AssocJoin; | |
| template<class AssocCons, class Key> struct AssocLookup{ | |
| typedef typename Ternary<typename Equal<typename AssocCons::car::car,Key>::value, | |
| I<I<typename AssocCons::car::cdr::car> >, | |
| Ternary<typename Equal<typename AssocCons::cdr,Nil>::value, | |
| I<Nil>, | |
| AssocLookup<typename AssocCons::cdr,Key> | |
| > >::value::value::value value; | |
| }; | |
| template<class AssocCons, class Key> struct AssocRemove{ | |
| typedef typename Ternary<typename Equal<typename AssocCons::car::car,Key>::value, | |
| I<I<typename AssocCons::cdr> >, | |
| Ternary<typename Equal<typename AssocCons::cdr,Nil>::value, | |
| I<AssocCons>, | |
| /* I gave up on cleanness here )`: */ | |
| I<Cons<typename AssocCons::car,typename Ternary<typename Equal<typename AssocCons::cdr,Nil>::value,I<Nil>,AssocRemove<typename AssocCons::cdr,Key> >::value::value> > | |
| > >::value::value::value value; | |
| }; | |
| template<class AssocCons, class Key, class Value> struct AssocAdd{ | |
| /* Just to ensure we don't clutter memory with 20000000 instances of the key "Q" or whatever | |
| * May become significantly slow if this is done a lot on large alists */ | |
| typedef Cons<Cons<Key,Cons<Value,Nil> >, typename AssocRemove<AssocCons,Key>::value> value; | |
| }; | |
| template<class AssocCons> struct AssocKeys{ | |
| private: | |
| template<class AList> struct Implementation{ | |
| typedef Cons<typename AList::car::car,typename Ternary<typename Equal<typename AList::cdr,Nil>::value, | |
| I<Nil>, | |
| AssocKeys<typename AList::cdr> | |
| >::value::value> value; | |
| }; | |
| public: | |
| typedef typename Ternary<typename Equal<AssocCons,Nil>::value, | |
| I<Nil>, | |
| Implementation<AssocCons> | |
| >::value::value value; | |
| }; | |
| template<class AssocOld, class AssocNew> struct AssocJoin{ | |
| /* for each key in AssocNew, add value AssocNew[key] to AssocOld with key key. | |
| * for key in AssocKeys<AssocNew>::value, AssocOld <= AssocAdd<AssocOld,key,AssocLookup<AssocNew,Key>> */ | |
| private: | |
| template<class AList, class Key> struct SubFunc{ | |
| typedef typename AssocAdd<AList,Key,typename AssocLookup<AssocNew,Key>::value>::value value; | |
| }; | |
| public: | |
| typedef typename FoldLeft<SubFunc,typename AssocKeys<AssocNew>::value,AssocOld>::value value; | |
| }; | |
| namespace Comb{ /* Namespaced cause utility is iffy at my best guess. */ | |
| /* Macro metaprogram completed; also why this cannot be compiled with pedantic C++98 now :) | |
| * Just make sure you at least have C99 or an extensive compiler like GCC */ | |
| /* also technically could all be written via typedef to a certain basis | |
| * but something about that feels wrong. */ | |
| #define CPP_CombinatorDeclarer(x) struct x; \ | |
| namespace _impl_{ template<class CombArr> struct CPP_Glue(x,Comb); } | |
| /*CPP_CombinatorDeclarer(S) | |
| CPP_CombinatorDeclarer(K) | |
| CPP_CombinatorDeclarer(I) | |
| CPP_CombinatorDeclarer(B) | |
| CPP_CombinatorDeclarer(C) | |
| CPP_CombinatorDeclarer(W)*/ | |
| CPP_Eval2(CPP_Each(CPP_CombinatorDeclarer,(S,(K,(I,(B,(C,(W,CPP_Nil)))))))) | |
| template<class X> struct TrueIdentity; | |
| template<class CombArr> struct Stepper; | |
| template<class CombArr> struct Normalize; /* Reduce to weak head normal form. */ | |
| template<class X> struct TrueIdentity{typedef X value;}; | |
| template<class CombArr> struct Stepper{ | |
| private: | |
| typedef typename CombArr::car Head; | |
| typedef typename CombArr::cdr Rest; | |
| /* That moment when you make a whole abstraction just so | |
| * that you didn't need a simple binary/linear tree */ | |
| typedef typename AssocLookup< | |
| Cons<Cons<S,Cons<_impl_::SComb<Rest>,Nil> >, | |
| Cons<Cons<K,Cons<_impl_::KComb<Rest>,Nil> >, | |
| Cons<Cons<I,Cons<_impl_::IComb<Rest>,Nil> >, | |
| Cons<Cons<B,Cons<_impl_::BComb<Rest>,Nil> >, | |
| Cons<Cons<C,Cons<_impl_::CComb<Rest>,Nil> >, | |
| Cons<Cons<W,Cons<_impl_::WComb<Rest>,Nil> >, | |
| Nil> > > > > > | |
| ,Head>::value LookupValue; | |
| public: | |
| typedef CombArr out; | |
| typedef Stepper<typename Ternary<typename IsCons<Head>::value, | |
| /* Hacky cause I is redefined in this land */ | |
| TrueIdentity<Concat<Head,Rest> >, | |
| Ternary<typename Equal<LookupValue,Nil>::value, | |
| TrueIdentity<CombArr>, | |
| LookupValue | |
| > >::value::value::value> value; | |
| }; | |
| template<class CombArr> struct Normalize{ | |
| private: | |
| typedef typename Stepper<CombArr>::value::out Stepped; | |
| public: | |
| typedef typename Ternary<typename Equal<CombArr,Stepped>::value, | |
| TrueIdentity<CombArr>, | |
| Normalize<Stepped> | |
| >::value::value value; | |
| }; | |
| namespace _impl_{ /* I am of the opinion these should be hidden */ | |
| template<class CombArr> struct SComb{ | |
| /* Cons<X,Cons<Y,Cons<Z,Rest> > > => Cons<X,Cons<Z,Cons<Cons<Y,Cons<Z,Nil> >,Rest> > > */ | |
| private: | |
| typedef typename CombArr::car X; | |
| typedef typename CombArr::cdr::car Y; | |
| typedef typename CombArr::cdr::cdr::car Z; | |
| typedef typename CombArr::cdr::cdr::cdr Rest; | |
| typedef typename MemberOf<Cons<X,Cons<Y,Cons<Z,Nil> > >,Nil>::value UnderDetermined; | |
| public: | |
| typedef typename Ternary<UnderDetermined, Cons<S,CombArr>, | |
| Cons<X,Cons<Z,Cons<Cons<Y,Cons<Z,Nil> >,Rest> > > | |
| >::value value; | |
| }; | |
| template<class CombArr> struct KComb{ | |
| /* Cons<X,Cons<Y,Rest> > => Cons<X,Rest> */ | |
| private: | |
| typedef typename CombArr::car X; | |
| typedef typename CombArr::cdr::car Y; | |
| typedef typename CombArr::cdr::cdr Rest; | |
| typedef typename MemberOf<Cons<X,Cons<Y,Nil> >,Nil>::value UnderDetermined; | |
| public: | |
| typedef typename Ternary<UnderDetermined, Cons<K,CombArr>, | |
| Cons<X,Rest> | |
| >::value value; | |
| }; | |
| template<class CombArr> struct IComb{ | |
| /* Cons<X,Rest> => Cons<X,Rest> */ | |
| /* could be Identity, but consistency, pls */ | |
| private: | |
| typedef typename CombArr::car X; | |
| typedef typename CombArr::cdr Rest; | |
| typedef typename MemberOf<Cons<X,Nil>,Nil>::value UnderDetermined; | |
| public: | |
| typedef typename Ternary<UnderDetermined, Cons<I,CombArr>, | |
| Cons<X,Rest> | |
| >::value value; | |
| }; | |
| template<class CombArr> struct BComb{ | |
| /* Cons<X,Cons<Y,Cons<Z,Rest> > > => Cons<X,Cons<Cons<Y,Cons<Z,Nil> >,Rest> > */ | |
| private: | |
| typedef typename CombArr::car X; | |
| typedef typename CombArr::cdr::car Y; | |
| typedef typename CombArr::cdr::cdr::car Z; | |
| typedef typename CombArr::cdr::cdr::cdr Rest; | |
| typedef typename MemberOf<Cons<X,Cons<Y,Cons<Z,Nil> > >,Nil>::value UnderDetermined; | |
| public: | |
| typedef typename Ternary<UnderDetermined, Cons<B,CombArr>, | |
| Cons<X,Cons<Cons<Y,Cons<Z,Nil> >,Rest> > | |
| >::value value; | |
| }; | |
| template<class CombArr> struct CComb{ | |
| /* Cons<X,Cons<Y,Cons<Z,Rest> > > => Cons<X,Cons<Z,Cons<Y,Rest> > > */ | |
| private: | |
| typedef typename CombArr::car X; | |
| typedef typename CombArr::cdr::car Y; | |
| typedef typename CombArr::cdr::cdr::car Z; | |
| typedef typename CombArr::cdr::cdr::cdr Rest; | |
| typedef typename MemberOf<Cons<X,Cons<Y,Cons<Z,Nil> > >,Nil>::value UnderDetermined; | |
| public: | |
| typedef typename Ternary<UnderDetermined, Cons<C,CombArr>, | |
| Cons<X,Cons<Z,Cons<Y,Rest> > > | |
| >::value value; | |
| }; | |
| template<class CombArr> struct WComb{ | |
| /* Cons<X,Cons<Y,Rest> > => Cons<X,Cons<Y,Cons<Y,Rest> > > */ | |
| private: | |
| typedef typename CombArr::car X; | |
| typedef typename CombArr::cdr::car Y; | |
| typedef typename CombArr::cdr::cdr Rest; | |
| typedef typename MemberOf<Cons<X,Cons<Y,Nil> >,Nil>::value UnderDetermined; | |
| public: | |
| typedef typename Ternary<UnderDetermined, Cons<W,CombArr>, | |
| Cons<X,Cons<Y,Cons<Y,Rest> > > | |
| >::value value; | |
| }; | |
| } | |
| } | |
| namespace Integer{ | |
| /* Conslike object; also little endian */ | |
| template<class Bit, class Rest> struct Int; | |
| /* Conslike object generator */ | |
| template<template<class> class Function, class Counter> struct Generator; | |
| struct IntPos; struct IntNeg; /* Determines sign through infinite expansion */ | |
| template<class Int1> struct Normalize; /* Normalizes infinite expansion; not strictly needed within Integer:: */ | |
| template<class Int1> struct IsNegative; | |
| template<class Int1> struct IsZero; | |
| template<class Int1> struct IsTerminal; /* Is 0 or -1, technically */ | |
| template<class Int1> struct BNot; | |
| template<template<class,class> class Operator, class LeftInt, class RightInt> struct BinaryBitwise; /* The functional appraoch is growing! */ | |
| #if (__cplusplus >= CPP11) || (!defined(__cplusplus)) | |
| #if !defined(__cplusplus) | |
| CPP_Hash if (CPP_GlueHelper_Actual(__,cplusplus) >= CPP11) | |
| #endif | |
| template<template<class...> class Op, class... Args> struct NAryBitwise{ | |
| private: | |
| typedef typename FoldLeft<LAnd,typename Map<IsTerminal,typename Consify<Args...>::value>::value,True>::value Terminal; | |
| typedef typename Op<typename Args::head...>::value HeadsValue; | |
| public: | |
| typedef Int<HeadsValue,typename Ternary<Terminal, | |
| Ternary<HeadsValue,IntNeg,IntPos>, | |
| NAryBitwise<Op,typename Args::tail...> | |
| >::value::value> value; | |
| }; | |
| #if !defined(__cplusplus) | |
| CPP_Hash endif | |
| #endif | |
| #endif | |
| template<class Int1> struct BitLength; | |
| template<class Int1, class Shift> struct LeftShift; | |
| template<class Int1, class Shift> struct RightShift; | |
| template<class Int1> struct Negate; | |
| template<class Int1> struct Abs; | |
| template<class Int1> struct Sign; | |
| template<class Int1> struct Increment; | |
| template<class Int1> struct Decrement; | |
| template<class Int1, class Int2> struct Add; | |
| template<class LeftInt, class RightInt> struct Subtract; | |
| template<class Int1, class Int2> struct Multiply; | |
| template<class Int1, class Int2> struct IntEqual; | |
| template<class LeftInt, class RightInt> struct GreaterThan; | |
| template<class LeftInt, class RightInt> struct LessThan; | |
| template<class Dividend, class Divisor> struct Divide; | |
| template<class Int1, class Modulus> struct Modulo; | |
| template<class Lower, class Upper> struct Range; /* Inclusive, as it always should have been. */ | |
| template<class Int1, class Length> struct Truncate; | |
| namespace Math{ | |
| template<class Int1, class Int2> struct Min; | |
| template<class Int1, class Int2> struct Max; | |
| template<class Int1, class Int2> struct GCD; | |
| template<class Int1, class Int2> struct LCM; | |
| template<class Int1> struct IntSqrt; | |
| template<class Base, class Exp> struct Power; | |
| template<class Int1> struct Factorial; | |
| template<class Base, class Exp, class Modulus> struct PowerMod; | |
| template<class Int1, class Modulus> struct ExtendedGCD; | |
| template<class Int1, class Modulus> struct ModularInverse; | |
| } | |
| namespace _impl_{ | |
| struct DivideByZero; /* errors */ | |
| struct ValueError; | |
| template<class Numer, class Denom, class q, class r, class i> struct DivMod; | |
| template<class Int1, class Left, class Right> struct BinSqrt; | |
| template<class Int1, class Modulus, class PrevX, class X, class PrevY, class Y> struct XGCD; | |
| } | |
| template<class Bit, class Rest> struct Int{ | |
| typedef Bit head; | |
| typedef Rest tail; | |
| }; | |
| struct IntPos{ /* incidentally 0 */ | |
| typedef False head; | |
| typedef IntPos tail; | |
| }; | |
| struct IntNeg{ /* incidentally -1 */ | |
| typedef True head; | |
| typedef IntNeg tail; | |
| }; | |
| template<template<class> class Function, class Counter> struct Generator{ | |
| private: | |
| typedef typename Ternary<typename Equal<typename Function<typename Increment<Counter>::value>::value,Nil>::value, | |
| Nil, | |
| Generator<Function,typename Increment<Counter>::value> | |
| >::value Next; | |
| public: | |
| typedef typename Function<Counter>::value car; | |
| typedef Next cdr; | |
| }; | |
| template<class Int1> struct Normalize{ | |
| typedef typename Ternary<typename IsTerminal<Int1>::value, | |
| typename Ternary<typename Int1::head,IntNeg,IntPos>::value, | |
| Int<typename Int1::head,typename Ternary<typename IsTerminal<Int1>::value, | |
| I<Nil>, | |
| Normalize<typename Int1::tail> | |
| >::value::value> | |
| >::value value; | |
| }; | |
| template<class Int1> struct IsNegative{ | |
| private: | |
| typedef typename Int1::tail Tail; | |
| public: | |
| typedef typename Ternary<typename Equal<Tail,typename Tail::tail>::value, | |
| Equal<Tail,IntNeg>, | |
| IsNegative<Tail> | |
| >::value::value value; | |
| }; | |
| template<class Int1> struct IsZero{ | |
| typedef typename Ternary<typename Int1::head, | |
| I<I<False> >, | |
| Ternary<typename Equal<Int1,IntPos>::value, | |
| I<True>, | |
| IsZero<typename Int1::tail> | |
| > >::value::value::value value; | |
| }; | |
| template<class Int1> struct IsTerminal{ | |
| typedef typename Ternary<typename IsZero<Int1>::value, | |
| I<True>, | |
| IsZero<typename Increment<Int1>::value> | |
| >::value::value value; | |
| }; | |
| template<class Int1> struct BNot{ | |
| private: | |
| typedef typename Int1::head Head; | |
| typedef typename Int1::tail Tail; | |
| public: | |
| typedef Int<typename LNot<Head>::value, typename Ternary<typename MemberOf<Cons<IntPos,Cons<IntNeg,Nil> >,Tail>::value, | |
| Ternary<typename Tail::head, | |
| IntPos, | |
| IntNeg | |
| >, BNot<Tail> | |
| >::value::value> value; | |
| }; | |
| template<template<class,class> class Op, class LHS, class RHS> struct BinaryBitwise{ | |
| private: | |
| typedef typename LHS::head LHead; | |
| typedef typename RHS::head RHead; | |
| typedef typename LHS::tail LTail; | |
| typedef typename RHS::tail RTail; | |
| typedef typename LAnd<typename IsTerminal<LHS>::value,typename IsTerminal<RHS>::value>::value Terminal; | |
| public: | |
| typedef Int<typename Op<LHead,RHead>::value,typename Ternary<Terminal, | |
| Ternary<typename Op<LHead,RHead>::value,IntNeg,IntPos>, | |
| BinaryBitwise<Op,LTail,RTail> | |
| >::value::value> value; | |
| }; | |
| template<class Int1> struct Negate{ | |
| typedef typename Increment<typename BNot<Int1>::value>::value value; | |
| }; | |
| template<class Int1> struct Abs{ | |
| typedef typename Ternary<typename IsNegative<Int1>::value,Negate<Int1>,I<Int1> >::value::value value; | |
| }; | |
| template<class Int1> struct Sign{ | |
| typedef typename Ternary<typename IsNegative<Int1>::value,I<IntNeg>,Ternary<typename IsZero<Int1>::value,IntPos,Int<True,IntPos> > >::value::value value; | |
| }; | |
| template<class Int1> struct BitLength{ | |
| typedef typename Increment<typename Ternary<typename IsTerminal<Int1>::value, | |
| BNot<Int1>,//Ternary<typename IsZero<Int1>::value,IntNeg,IntPos>, | |
| BitLength<typename Int1::tail> | |
| >::value::value>::value value; | |
| }; | |
| template<class Int1, class Shift> struct LeftShift{ | |
| private: | |
| typedef typename Ternary<typename IsNegative<Shift>::value,Error<_impl_::ValueError>,I<True> >::value::value Check; | |
| public: | |
| typedef typename Ternary<typename LAnd<typename IsZero<Shift>::value,Check>::value, | |
| I<Int1>, | |
| LeftShift<Int<False,Int1>,typename Decrement<Shift>::value> | |
| >::value::value value; | |
| }; | |
| template<class Int1, class Shift> struct RightShift{ | |
| private: | |
| typedef typename Ternary<typename IsNegative<Shift>::value,Error<_impl_::ValueError>,I<True> >::value::value Check; | |
| public: | |
| typedef typename Ternary<typename LAnd<typename IsZero<Shift>::value,Check>::value, | |
| I<Int1>, | |
| RightShift<typename Int1::tail,typename Decrement<Shift>::value> | |
| >::value::value value; | |
| }; | |
| template<class Int1> struct Increment{ | |
| private: | |
| typedef typename Int1::head Head; | |
| typedef typename Int1::tail Tail; | |
| public: | |
| typedef Int<typename LNot<Head>::value, typename Ternary<Head, | |
| Ternary<typename MemberOf<Cons<IntPos,Cons<IntNeg,Nil> >,Tail>::value, | |
| Ternary<typename Tail::head, | |
| IntPos, | |
| Int<True,IntPos> | |
| >, | |
| Increment<Tail> | |
| >, | |
| I<I<Tail> > | |
| >::value::value::value> value; | |
| }; | |
| template<class Int1> struct Decrement{ | |
| private: | |
| typedef typename Int1::head Head; | |
| typedef typename Int1::tail Tail; | |
| public: | |
| typedef Int<typename LNot<Head>::value, typename Ternary<Head, | |
| I<I<Tail> >, | |
| Ternary<typename MemberOf<Cons<IntPos,Cons<IntNeg,Nil> >,Tail>::value, | |
| Ternary<typename Tail::head, | |
| Int<False,IntNeg>, | |
| IntNeg | |
| >, | |
| Decrement<Tail> | |
| > >::value::value::value> value; | |
| }; | |
| template<class Int1, class Int2> struct Add{ /* I have never seen a more convoluted addition, but I do usually get specialization */ | |
| private: | |
| typedef typename Int1::head Head1; | |
| typedef typename Int1::tail Tail1; | |
| typedef typename Int2::head Head2; | |
| typedef typename Int2::tail Tail2; | |
| typedef typename Ternary<Head1,True,Head2>::value IncrementOnce; | |
| typedef typename Ternary<Head1,Head2,False>::value IncrementTwice; | |
| typedef Int<False, typename Ternary<typename IsTerminal<Int1>::value, | |
| Ternary<typename IsZero<Int1>::value,I<Tail2>,Decrement<Tail2> >, | |
| I<Add<Tail1,Tail2> > | |
| >::value::value::value> Next; | |
| public: | |
| typedef typename Ternary<IncrementOnce, | |
| Increment<typename Ternary<IncrementTwice, | |
| Increment<Next>, | |
| I<Next> | |
| >::value::value >, | |
| I<Next> | |
| >::value::value value; | |
| }; | |
| template<class Int1, class Int2> struct Subtract{ | |
| typedef typename Add<Int1, typename Negate<Int2>::value>::value value; | |
| }; | |
| template<class Int1, class Int2> struct Multiply{ | |
| private: | |
| typedef typename Int1::head Head1; | |
| typedef typename Int1::tail Tail1; | |
| typedef typename Int2::head Head2; | |
| typedef typename Int2::tail Tail2; | |
| typedef Int<False, typename Ternary<typename IsTerminal<Int1>::value, | |
| Ternary<typename IsZero<Int1>::value,I<IntPos>,Negate<Int2> >, | |
| I<Multiply<Tail1,Int2> > | |
| >::value::value::value> Next; | |
| public: | |
| typedef typename Ternary<Head1, | |
| Add<Int2,Next>, | |
| I<Next> | |
| >::value::value value; | |
| }; | |
| template<class Int1, class Int2> struct IntEqual{ | |
| /* Int1 == Int2; 0 == Int1 - Int2 */ | |
| typedef typename IsZero<typename Subtract<Int1,Int2>::value>::value value; | |
| }; | |
| template<class Int1, class Int2> struct GreaterThan{ | |
| /* Int1 > Int2; 0 > Int2 - Int1; IsNegative<Int2 - Int1> */ | |
| typedef typename IsNegative<typename Subtract<Int2,Int1>::value>::value value; | |
| }; | |
| template<class Int1, class Int2> struct LessThan{ | |
| /* Int1 < Int2; Int2 > Int1 */ | |
| typedef typename GreaterThan<Int2,Int1>::value value; | |
| }; | |
| template<class Int1, class Int2> struct Divide{ | |
| private: | |
| typedef typename Ternary<typename IsZero<Int2>::value,Error<_impl_::DivideByZero>,I<True> >::value::value Check; | |
| typedef typename Abs<Int1>::value Abs1; | |
| typedef typename Abs<Int2 >::value Abs2; | |
| typedef typename LXor<typename IsNegative<Int1>::value,typename IsNegative<Int2>::value>::value Sign; | |
| typedef typename _impl_::DivMod<Abs1,Abs2,IntPos,IntPos,typename BitLength<Abs1>::value>::value DivMod_; | |
| public: | |
| typedef typename Ternary<Sign, | |
| Ternary<typename IsZero<typename DivMod_::cdr::car>::value,Negate<typename DivMod_::car>,BNot<typename DivMod_::car> >, | |
| I<I<typename DivMod_::car> > | |
| >::value::value::value value; | |
| }; | |
| template<class Int1, class Int2> struct Modulo{ | |
| typedef typename Subtract<Int1,typename Multiply<Int2,typename Divide<Int1,Int2>::value>::value>::value value; | |
| }; | |
| template<class Low, class High> struct Range{ | |
| private: | |
| typedef typename Ternary<typename LessThan<High,Low>::value,Error<_impl_::ValueError>,I<True> >::value::value Check; | |
| public: | |
| typedef Cons<Low,typename Ternary<typename LAnd<typename IntEqual<Low,High>::value,Check>::value, | |
| I<Nil>, | |
| Range<typename Increment<Low>::value,High> | |
| >::value::value> value; | |
| }; | |
| template<class Int1, class Length> struct Truncate{ | |
| private: | |
| /* Why have _impl_ when ____? */ | |
| template<class Int2, class Len> struct Truncate2; | |
| template<class Int2, class Len> struct Truncate2{ | |
| typedef typename Ternary<typename GreaterThan<Len,IntPos>::value, | |
| Int<typename Int2::head, | |
| typename Ternary<typename GreaterThan<Len,IntPos>::value, | |
| Truncate2<typename Int2::tail,typename Decrement<Len>::value>, | |
| I<IntPos> | |
| >::value::value>, | |
| IntPos | |
| >::value value; | |
| }; | |
| public: | |
| /* Now I can Normalize without being ~O(n^2) */ | |
| typedef typename Normalize<typename Truncate2<Int1,Length>::value>::value value; | |
| }; | |
| namespace _impl_{ | |
| /* | |
| * def DivMod(dividend, divisor,q=0,r=0,i=None): | |
| * #if(divisor==0):1/0 | |
| * #if(i==None):i=dividend.bit_length()-1 | |
| * if(i==-1):return(q,r) | |
| * R=(r<<1)|((dividend>>i)&1) | |
| * return(DivMod(dividend,divisor,q|(1<<i if R>=divisor else 0),R-(divisor if R>=divisor else 0),i-1)) | |
| */ | |
| template<class Dividend, class Divisor, class q, class r, class i> struct DivMod{ | |
| private: | |
| typedef typename Abs<i>::value Guardedi; | |
| typedef typename BinaryBitwise<LOr, | |
| Int<False,r>, // slightly smaller <<1 | |
| // slightly smaller &1 | |
| Int<typename RightShift<Dividend,Guardedi>::value::head,IntPos> | |
| >::value R; | |
| typedef typename LNot<typename LessThan<R,Divisor>::value>::value RGreaterEq; | |
| typedef Cons<q,Cons<r,Nil> > Output; | |
| public: | |
| typedef typename Ternary<typename IntEqual<i,IntNeg>::value, | |
| I<Output>, | |
| DivMod<Dividend,Divisor, | |
| typename BinaryBitwise<LOr,q,typename Ternary<RGreaterEq, | |
| LeftShift<Int<True,IntPos>,Guardedi>, | |
| I<IntPos> | |
| >::value::value>::value, | |
| typename Ternary<RGreaterEq, | |
| Subtract<R,Divisor>, | |
| I<R> | |
| >::value::value, | |
| typename Decrement<i>::value | |
| > >::value::value value; | |
| }; | |
| /* | |
| * def isqrt(n,L=0,R=-1): | |
| * #if(n<0):raise ValueError() | |
| * #if(R==-1):R=n+1 | |
| * if(L==R-1):return(L) | |
| * M=(L+R)//2 | |
| * return(isqrt(n,M if M*M<=n else L,R if M*M<=n else M)) | |
| */ | |
| template<class Int1, class L, class R> struct BinSqrt{ | |
| private: | |
| typedef typename Add<L,R>::value::tail M; | |
| typedef typename GreaterThan<typename Multiply<M,M>::value,Int1>::value Check; | |
| public: | |
| typedef typename Ternary<typename IntEqual<L,typename Decrement<R>::value>::value, | |
| I<L>, | |
| BinSqrt<Int1, | |
| typename Ternary<Check,L,M>::value, | |
| typename Ternary<Check,M,R>::value | |
| > >::value::value value; | |
| }; | |
| /* | |
| * def xgcd(a,b,prevx=1,x=0,prevy=0,y=1): | |
| * if(b==0):return(a,prevx,prevy) | |
| * Q=lambda prev,cur:prev-a//b*cur | |
| * return(xgcd(b,a%b,x,Q(prevx,x),y,Q(prevy,y))) | |
| */ | |
| template<class Int1, class Modulus, class PrevX, class X, class PrevY, class Y> struct XGCD{ | |
| private: | |
| template<class Prev, class Cur> struct Q; | |
| typedef typename IsZero<Modulus>::value ModZero; | |
| typedef Cons<Int1,Cons<PrevX,Cons<PrevY,Nil> > > Output; | |
| template<class Prev, class Cur> struct Q{ | |
| typedef typename Subtract<Prev,typename Multiply<typename Ternary<ModZero,I<IntPos>,Divide<Int1,Modulus> >::value::value,Cur>::value>::value value; | |
| }; | |
| public: | |
| typedef typename Ternary<ModZero, | |
| I<Output>, | |
| XGCD< | |
| Modulus,typename Ternary<ModZero,I<IntPos>,Modulo<Int1,Modulus> >::value::value, | |
| X,typename Q<PrevX,X>::value, | |
| Y,typename Q<PrevY,Y>::value | |
| > >::value::value value; | |
| }; | |
| } | |
| namespace Math{ | |
| template<class Int1, class Int2> struct Min{ | |
| typedef typename Ternary<typename LessThan<Int1,Int2>::value,Int1,Int2>::value value; | |
| }; | |
| template<class Int1, class Int2> struct Max{ | |
| typedef typename Ternary<typename GreaterThan<Int1,Int2>::value,Int1,Int2>::value value; | |
| }; | |
| template<class Int1, class Int2> struct GCD{ | |
| private: | |
| /* Anything But 0 */ | |
| typedef typename Ternary<typename IsZero<Int2>::value,IntNeg,Int2>::value Guarded2; | |
| public: | |
| typedef typename Ternary<typename IsZero<Int2>::value, | |
| Abs<Int1>, | |
| GCD<Int2,typename Modulo<Int1,Guarded2>::value> | |
| >::value::value value; | |
| }; | |
| template<class Int1, class Int2> struct LCM{ | |
| typedef typename Divide<typename Abs<typename Multiply<Int1,Int2>::value>::value,typename GCD<Int1,Int2>::value>::value value; | |
| }; | |
| template<class Int1> struct IntSqrt{ | |
| private: | |
| typedef typename Ternary<typename IsNegative<Int1>::value,Error<_impl_::ValueError>,I<True> >::value::value Check; /* Imaginary numbers are all in your head */ | |
| public: | |
| typedef typename _impl_::BinSqrt<Int1,IntPos,typename Increment<Int1>::value>::value value; | |
| }; | |
| /* def Power(x,y):return(((x if y&1 else 1)*Power(x*x,y//2)) if y>1 else (x if y>0 else 1)) */ | |
| template<class x, class y> struct Power{ | |
| private: | |
| typedef typename Ternary<typename GreaterThan<y,Int<True,IntPos> >::value,Power<typename Multiply<x,x>::value,typename y::tail>,I<x> >::value::value BaseCase; | |
| public: | |
| typedef typename Ternary<typename GreaterThan<y,Int<True,IntPos> >::value, | |
| Multiply<typename Ternary<typename y::head,x,Int<True,IntPos> >::value,BaseCase>, | |
| Ternary<typename GreaterThan<y,IntPos>::value,x,Int<True,IntPos> > | |
| >::value::value value; | |
| }; | |
| template<class Int1> struct Factorial{ | |
| typedef typename FoldLeft<Multiply,typename Ternary<typename IsZero<Int1>::value, | |
| I<Cons<Int<True,IntPos>,Nil> >, | |
| Range<Int<True,IntPos>,Int1> | |
| >::value::value,Int<True,IntPos> >::value value; | |
| }; | |
| /* def PowerMod(x,y,m):x%=m;return(((x if y&1 else 1)*PowerMod(x*x,y//2,m)) if y>1 else (x if y>0 else 1)) */ | |
| template<class Base, class y, class m> struct PowerMod{ | |
| private: | |
| typedef typename Modulo<Base,m>::value x; | |
| typedef typename Ternary<typename GreaterThan<y,Int<True,IntPos> >::value,PowerMod<typename Multiply<x,x>::value,typename y::tail,m>,I<x> >::value::value BaseCase; | |
| public: | |
| typedef typename Modulo<typename Ternary<typename GreaterThan<y,Int<True,IntPos> >::value, | |
| Multiply<typename Ternary<typename y::head,x,Int<True,IntPos> >::value,BaseCase>, | |
| Ternary<typename GreaterThan<y,IntPos>::value,x,Int<True,IntPos> > | |
| >::value::value,m>::value value; | |
| }; | |
| template<class Int1, class Modulus> struct ExtendedGCD{ | |
| typedef typename _impl_::XGCD<Int1,Modulus,Int<True,IntPos>,IntPos,IntPos,Int<True,IntPos> >::value value; | |
| }; | |
| template<class Int1, class Modulus> struct ModularInverse{ | |
| private: | |
| typedef typename ExtendedGCD<Int1,typename Abs<Modulus>::value>::value EGCD; | |
| typedef typename Ternary<typename IntEqual<Int<True,IntPos>,typename EGCD::car>::value, | |
| I<True>, | |
| Error<_impl_::ValueError> /* No modular multiplicative inverse exists */ | |
| >::value::value Check; | |
| public: | |
| typedef typename Ternary<Check, | |
| Modulo<typename EGCD::cdr::car,Modulus>, | |
| IntPos /* also err here if somehow */ | |
| >::value::value value; | |
| }; | |
| } | |
| } | |
| namespace Rational{ | |
| template<class Numer, class Denom> struct Rational; | |
| template<class Int1> struct ToRational; | |
| template<class Rat1> struct Normalize; | |
| template<class Rat1> struct Sign; | |
| template<class Rat1> struct Negate; | |
| template<class Rat1, class Rat2> struct RatEqual; | |
| template<class Rat1, class Rat2> struct GreaterThan; | |
| template<class Rat1, class Rat2> struct LessThan; | |
| template<class Rat1, class Rat2> struct Add; | |
| template<class Rat1, class Rat2> struct Subtract; | |
| template<class Rat1, class Rat2> struct Multiply; | |
| template<class Rat1> struct Reciprocal; | |
| template<class LeftRat, class RightRat> struct Divide; | |
| template<class Rat1> struct Floor; | |
| template<class Rat1> struct Ceil; | |
| //template<class Rat1> struct Round; /* Round up on tie */ | |
| template<class Rat1, class Int1> struct Power; | |
| template<class Rat1, class Rat2> struct Mediant; | |
| template<class Rat1, class Modulus> struct ToModular; | |
| namespace Continued{ | |
| template<class Rat1> struct Continue; | |
| template<class Cont> struct Discontinue; | |
| } | |
| template<class Numer, class Denom> struct Rational{ | |
| private: | |
| typedef typename Ternary<typename Integer::IsZero<Denom>::value,Error<Integer::_impl_::DivideByZero>,I<True> >::value::value Check; | |
| public: | |
| typedef Numer numer; | |
| typedef Denom denom; | |
| }; | |
| template<class Int1> struct ToRational{ | |
| typedef Rational<Int1,Integer::Int<True,Integer::IntPos> > value; | |
| }; | |
| template<class Rat> struct Sign{ | |
| typedef typename Ternary<typename Integer::IsZero<typename Rat::numer>::value,Integer::IntPos,typename Ternary<typename LXor<typename Integer::IsNegative<typename Rat::numer>::value,typename Integer::IsNegative<typename Rat::denom>::value>::value,typename Integer::IntNeg,typename Integer::Int<True,typename Integer::IntPos> >::value>::value value; | |
| }; | |
| template<class Rat> struct Negate{ | |
| typedef Rational<typename Integer::Negate<typename Rat::numer>::value,typename Rat::denom> value; | |
| }; | |
| template<class Rat1, class Rat2> struct RatEqual{ | |
| typedef typename Equal<typename Normalize<Rat1>::value,typename Normalize<Rat2>::value>::value value; | |
| }; | |
| template<class Rat1, class Rat2> struct GreaterThan{ | |
| /* A/B > X/Y; A*Y/B > X; A*Y > B*X */ | |
| typedef typename Integer::GreaterThan< | |
| typename Integer::Multiply<typename Rat1::numer,typename Rat2::denom>::value, | |
| typename Integer::Multiply<typename Rat2::numer,typename Rat1::denom>::value | |
| >::value value; | |
| }; | |
| template<class Rat1, class Rat2> struct LessThan{ | |
| typedef typename GreaterThan<Rat2,Rat1>::value value; | |
| }; | |
| template<class Rat> struct Normalize{ | |
| private: | |
| typedef typename Rat::numer Numer; | |
| typedef typename Rat::denom Denom; | |
| typedef typename Integer::Math::GCD<Numer,Denom>::value GCD; | |
| typedef typename Integer::Divide<Numer,GCD>::value NNumer; | |
| typedef typename Integer::Divide<Denom,GCD>::value NDenom; | |
| typedef typename Sign<Rat>::value Sign_; | |
| public: | |
| typedef Rational< | |
| typename Integer::Normalize<typename Integer::Multiply<Sign_,typename Integer::Abs<NNumer>::value>::value>::value, | |
| typename Integer::Normalize<typename Integer::Abs<NDenom>::value>::value | |
| > value; | |
| }; | |
| template<class Rat> struct Reciprocal{ | |
| typedef Rational<typename Rat::denom, typename Rat::numer> value; | |
| }; | |
| template<class Rat1, class Rat2> struct Multiply{ | |
| typedef typename Normalize<Rational< | |
| typename Integer::Multiply<typename Rat1::numer,typename Rat2::numer>::value, | |
| typename Integer::Multiply<typename Rat1::denom,typename Rat2::denom>::value | |
| > >::value value; | |
| }; | |
| template<class Rat1, class Rat2> struct Divide{ | |
| typedef typename Multiply<Rat1,typename Reciprocal<Rat2>::value>::value value; | |
| }; | |
| template<class Rat1, class Rat2> struct Add{ | |
| private: | |
| typedef typename Rat1::numer A; | |
| typedef typename Rat1::denom B; | |
| typedef typename Rat2::numer C; | |
| typedef typename Rat2::denom D; | |
| public: | |
| typedef typename Normalize<Rational< | |
| typename Integer::Add< | |
| typename Integer::Multiply<A,D>::value, | |
| typename Integer::Multiply<C,B>::value | |
| >::value, | |
| typename Integer::Multiply<B,D>::value | |
| > >::value value; | |
| }; | |
| template<class Rat1, class Rat2> struct Subtract{ | |
| typedef typename Add<Rat1,typename Negate<Rat2>::value>::value value; | |
| }; | |
| template<class Rat1> struct Floor{typedef typename Integer::Divide<typename Rat1::numer,typename Rat1::denom>::value value;}; | |
| template<class Rat1> struct Ceil{ | |
| private: | |
| typedef typename Normalize<Rat1>::value Rat2; | |
| public: | |
| typedef typename Ternary<typename Integer::IntEqual<Integer::Int<True,Integer::IntPos>,typename Rat2::denom>::value, | |
| typename Rat2::numer, | |
| typename Integer::Increment<typename Floor<Rat2>::value>::value | |
| >::value value; | |
| }; | |
| template<class Rat1, class Int1> struct Power{ | |
| private: | |
| typedef typename Integer::Abs<Int1>::value Abs1; | |
| /* In the case it wasn't already in normal form, | |
| * this protects against unnecessary integer ops. */ | |
| typedef typename Normalize<Rat1>::value Rat2; | |
| typedef Rational< | |
| typename Integer::Math::Power<typename Rat2::numer,Abs1>::value, | |
| typename Integer::Math::Power<typename Rat2::denom,Abs1>::value | |
| > Rat3; | |
| public: | |
| typedef typename Ternary<typename Integer::IsNegative<Int1>::value, | |
| Reciprocal<Rat3>, | |
| I<Rat3> | |
| >::value::value value; | |
| }; | |
| template<class Rat1, class Rat2> struct Mediant{ | |
| private: | |
| /* Absolutely necessary here */ | |
| typedef typename Normalize<Rat1>::value Rat3; | |
| typedef typename Normalize<Rat2>::value Rat4; | |
| public: | |
| typedef typename Normalize<Rational< | |
| typename Integer::Add<typename Rat3::numer,typename Rat4::numer>::value, | |
| typename Integer::Add<typename Rat3::denom,typename Rat4::denom>::value | |
| > >::value value; | |
| }; | |
| template<class Rat1, class Modulus> struct ToModular{ | |
| typedef typename Integer::Modulo< | |
| typename Integer::Multiply<typename Rat1::numer, | |
| typename Integer::Math::ModularInverse<typename Rat1::denom | |
| ,Modulus>::value>::value,Modulus>::value value; | |
| }; | |
| namespace Continued{ | |
| /* | |
| * # Big fan of this, but variadic | |
| * #def Continue(numer,denom,*cont): | |
| * # if(denom==0):return(cont) | |
| * # return(Continue(denom,numer%denom,*cont,numer//denom)) | |
| * | |
| * def Continue(numer,denom): | |
| * if(denom==0):return([]) | |
| * return([numer//denom,*Continue(denom,numer%denom)]) | |
| */ | |
| template<class Rat1> struct Continue{ | |
| private: | |
| /* Implementation'd to allow checking if dividing by zero */ | |
| template<class Numer, class Denom> struct Implementation{ | |
| typedef typename Integer::IsZero<Denom>::value ZeroDenom; | |
| /* So many guards I made a template! */ | |
| template<class ValuedObject> struct Guard{typedef typename Ternary<ZeroDenom,I<Nil>,ValuedObject>::value::value value;}; | |
| typedef typename Ternary<ZeroDenom,Nil,Cons< /* guard-ish */ | |
| typename Guard<Floor<Rational<Numer,Denom> > >::value, | |
| typename Guard<Implementation< | |
| Denom, | |
| typename Guard<Integer::Modulo<Numer,Denom> >::value | |
| > >::value | |
| > >::value value; | |
| }; | |
| typedef typename Normalize<Rat1>::value Rat2; | |
| public: | |
| typedef typename Implementation<typename Rat2::numer,typename Rat2::denom>::value value; | |
| }; | |
| /* | |
| * def Discontinue(cont): | |
| * if(len(cont)==1):return(cont[0],1) | |
| * Q=Discontinue(cont[1:]) | |
| * return(Q[1]+Q[0]*cont[0],Q[0]) | |
| */ | |
| template<class ContFrac> struct Discontinue{ | |
| private: | |
| typedef typename Equal<typename ContFrac::cdr,Nil>::value EOFrac; | |
| typedef typename Ternary<EOFrac,I<Nil>,Discontinue<typename ContFrac::cdr> >::value::value Q; | |
| typedef typename Ternary<EOFrac,ToRational<Integer::IntPos>,Reciprocal<Q> >::value::value ReciprocalQ; | |
| public: | |
| typedef typename Add<typename ToRational<typename ContFrac::car>::value,ReciprocalQ>::value value; | |
| }; | |
| } | |
| } | |
| /* Can hold anything, adresses are designed to be positive integers. */ | |
| namespace Memory{ | |
| /* A zero indicates that Value is sought. | |
| * Also all addresses are normalized to their absolute value. */ | |
| template<class Value, class ZeroBit, class OneBit> struct Memory; | |
| struct NULLMemory; | |
| template<class MemoryObject, class Address> struct MemoryLookup; | |
| template<class MemoryObject, class Address, class NewValue> struct MemoryWrite; | |
| template<class Value, class ZeroBit, class OneBit> struct Memory{ | |
| typedef Value value; | |
| typedef ZeroBit zero; | |
| typedef OneBit one; | |
| }; | |
| struct NULLMemory{ | |
| typedef Integer::IntPos value; | |
| typedef NULLMemory zero; | |
| typedef NULLMemory one; | |
| }; | |
| template<class MemoryObject, class Address> struct MemoryLookup{ | |
| private: | |
| template<class MemObj, class Addr> struct Implementation; | |
| template<class MemObj, class Addr> struct Implementation{ | |
| typedef typename Ternary<typename Equal<Addr,Integer::IntPos>::value, | |
| I<MemObj>, | |
| Ternary<typename Equal<MemObj,NULLMemory>::value, | |
| I<Integer::IntPos>, | |
| Implementation<typename Ternary<typename Addr::head, | |
| typename MemObj::one, | |
| typename MemObj::zero | |
| >::value,typename Addr::tail | |
| > > >::value::value::value value; | |
| }; | |
| public: | |
| typedef typename Implementation<MemoryObject, | |
| typename Integer::Normalize< | |
| typename Integer::Abs<Address | |
| >::value>::value>::value value; | |
| }; | |
| template<class MemoryObject, class Address, class Value> struct MemoryWrite{ | |
| private: | |
| template<class MemObj, class Addr, class Val> struct Implementation; | |
| template<class MemObj, class Addr, class Val> struct Implementation{ | |
| typedef typename Ternary<typename Equal<Addr,Integer::IntPos>::value, | |
| I<Memory<Val,typename MemObj::zero,typename MemObj::one> >, | |
| Implementation<typename Ternary<typename Addr::head, | |
| typename MemObj::one, | |
| typename MemObj::zero | |
| >::value,typename Addr::tail,Val> | |
| >::value::value NextMem; | |
| typedef typename Ternary<typename Equal<Addr,Integer::IntPos>::value, | |
| Memory<Val,typename MemObj::zero,typename MemObj::one>, | |
| Memory<typename MemObj::value, | |
| typename Ternary<typename Addr::head,typename MemObj::zero,NextMem>::value, | |
| typename Ternary<typename Addr::head,NextMem,typename MemObj::one>::value | |
| > >::value value; | |
| }; | |
| public: | |
| typedef typename Implementation<MemoryObject, | |
| typename Integer::Normalize< | |
| typename Integer::Abs<Address | |
| >::value>::value,Value>::value value; | |
| }; | |
| } | |
| namespace LISP{ | |
| struct Lambda; template<class Parameter, class Body, class Environment> struct Closure; | |
| //struct Car; struct Cdr; /* unneeded? */ | |
| template<class Name> struct Atom; | |
| template<class ConsProgram, class AssocEnvironment> struct Evaluator; | |
| /* this is such a f*king hack */ | |
| template<class Program, class Environment> struct Evaluator{ | |
| private: | |
| template<class ConsArr, class Env> struct Implementation{ | |
| typedef typename ConsArr::car Car; | |
| typedef typename ConsArr::cdr Cdr; | |
| template<class Implementable> struct Implement{ | |
| typedef typename Implementable::template Implementation<typename Cdr::car,typename Cdr::cdr::car,Env>::value value; | |
| }; | |
| template<class Function, class Argument> struct Applier{ | |
| typedef Cons<typename Evaluator<Function,Env>::value,Cons<Argument,Nil> > value; | |
| }; | |
| typedef typename Ternary<typename Equal<Car,Nil>::value, | |
| I<Nil>, | |
| Evaluator<typename Ternary<typename IsCons<Car>::value, | |
| Applier<Car,typename Cdr::car>, | |
| Implement<Car> | |
| >::value::value,Env> | |
| >::value::value value; | |
| }; | |
| public: | |
| typedef typename Ternary<typename IsCons<Program>::value, | |
| Implementation<Program,Environment>, | |
| I<Program> | |
| >::value::value value; | |
| }; | |
| template<class Name> struct Atom{ | |
| template<class,class, class Environment> struct Implementation{ | |
| private: | |
| typedef typename AssocLookup<Environment,Atom<Name> >::value NameValue; | |
| public: | |
| typedef typename Ternary<typename Equal<NameValue,Nil>::value, | |
| Atom<Name>, | |
| NameValue | |
| >::value value; | |
| };}; | |
| struct Lambda{ | |
| template<class Parameter, class Body, class Environment> struct Implementation{ | |
| typedef Closure<Parameter,Body,Environment> value; | |
| };}; | |
| template<class Parameter, class Body, class DefEnv> struct Closure{ | |
| template<class Argument, class, class CallEnv> struct Implementation{ | |
| typedef typename Evaluator<Body, | |
| typename AssocAdd<typename AssocJoin<CallEnv,DefEnv>::value,Parameter,Argument>::value | |
| >::value value; | |
| };}; | |
| } | |
| namespace Lazy{ | |
| template<template<class> class Function, class ConsArr> struct Map; | |
| template<template<class> class Predicate, class ConsArr> struct Filter; | |
| /* Not lazy, but for posterity. */ | |
| template<template<class,class> class Function, class ConsArr, class InitialLHS> struct FoldLeft; | |
| template<template<class> class Function, class ConsArr> struct Map{ | |
| private: | |
| template<template<class> class Func, class Array> struct Implementation{ | |
| typedef typename Func<typename Array::car>::value car; | |
| typedef typename Ternary<typename Equal<Nil,typename Array::cdr>::value,Nil,Implementation<Func,typename Array::cdr> >::value cdr; | |
| }; | |
| public: | |
| typedef Implementation<Function,ConsArr> value; | |
| }; | |
| template<template<class> class Predicate, class ConsArr> struct Filter{ | |
| private: | |
| /* yo dawg i heard you like helpers so i made some helpers for your helper */ | |
| template<template<class> class phi, class Array> struct Next{ | |
| typedef typename Array::car Car; | |
| typedef typename Array::cdr Cdr; | |
| typedef typename Ternary<typename phi<Car>::value, | |
| I<I<Car> >, | |
| Ternary<typename Equal<Cdr,Nil>::value, | |
| I<Nil>, | |
| Next<phi,Cdr> | |
| > >::value::value::value value; | |
| }; | |
| template<class Object, class Array> struct RestAfter{ | |
| typedef typename Array::cdr Cdr; | |
| typedef typename Ternary<typename Equal<typename Array::car,Object>::value, | |
| I<I<Cdr> >, | |
| Ternary<typename Equal<Cdr,Nil>::value, | |
| I<Nil>, | |
| RestAfter<Object,Cdr> | |
| > >::value::value::value value; | |
| }; | |
| template<template<class> class phi, class Array> struct Implementation{ | |
| typedef typename Next<phi,Array>::value car; | |
| typedef typename Ternary<typename Equal<typename Array::cdr,Nil>::value, | |
| Nil, | |
| Implementation<phi,typename RestAfter<car,Array>::value> | |
| >::value cdr; | |
| }; | |
| public: | |
| typedef Implementation<Predicate,ConsArr> value; | |
| }; | |
| template<template<class,class> class Function, class ConsArr, class LHS> struct FoldLeft{ | |
| private: | |
| typedef typename Ternary<typename Equal<typename ConsArr::car,Nil>::value,I<LHS>,Function<LHS,typename ConsArr::car> >::value::value Applied; | |
| public: | |
| typedef typename Ternary<typename Equal<typename ConsArr::cdr,Nil>::value, | |
| I<Applied>, | |
| FoldLeft<Function, typename ConsArr::cdr, Applied> | |
| >::value::value value; | |
| }; | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment