splinterofchaos / zip-map-tuple.cpp

Created December 12, 2012

 
#include <tuple>
#include <iostream>
 
template< size_t ...i > struct IndexList {};
 
template< size_t ... > struct EnumBuilder;
 
// Increment cur until cur == end.
template< size_t end, size_t cur, size_t ...i >
struct EnumBuilder< end, cur, i... > 
    // Recurse, adding cur to i...
    : EnumBuilder< end, cur+1, i..., cur >
{
};
 
// cur == end; the list has been built.
template< size_t end, size_t ...i >
struct EnumBuilder< end, end, i... > {
    using type = IndexList< i... >;
};
 
template< size_t b, size_t e >
struct Enumerate {
    using type = typename EnumBuilder< e, b >::type;
};
 
template< class > struct IListFrom;
 
template< class ...X > 
struct IListFrom< std::tuple<X...> > {
    static constexpr size_t N = sizeof ...(X);
    using type = typename Enumerate< 0, N >::type;
};
 
// std::tuple_element<i,T> does not perfect forward.
template< size_t i, class T >
using Elem = decltype( std::get<i>(std::declval<T>()) );
 
template< size_t i > struct Get {
    template< class T >
    constexpr auto operator () ( T&& t ) 
        -> Elem< i, T >
    {
        return std::get<i>( std::forward<T>(t) );
    }
};
 
template< size_t i, class T, 
          class _T = typename std::decay<T>::type,
          size_t N = std::tuple_size<_T>::value - 1, // Highest index
          size_t j = N - i >
constexpr auto rget( T&& t ) 
    -> Elem< j, T >
{
    return std::get<j>( std::forward<T>(t) );
}
 
template< size_t i > struct RGet {
    template< class T >
    constexpr auto operator () ( T&& t ) 
        -> decltype( rget<i>( std::forward<T>(t) ) )
    {
        return rget<i>( std::forward<T>(t) );
    }
};
 
template< size_t i, class T, 
          class _T = typename std::decay<T>::type,
          size_t N = std::tuple_size<_T>::value,
          size_t j = i % N >
constexpr auto mod_get( T&& t ) 
    -> Elem< j, T >
{
    return std::get<j>( std::forward<T>(t) );
}
 
template< template<size_t> class Fi = Get, size_t ...i, class F, class T >
constexpr auto applyIndexList( IndexList<i...>, const F& f, T&& t )
    -> typename std::result_of< F( 
        typename std::result_of< Fi<i>(T) >::type...
    ) >::type
{
    return f( Fi<i>()(std::forward<T>(t))... );
}
 
template< template<size_t> class Fi = Get, class F, class T,
          class _T = typename std::decay<T>::type,
          class IL = typename IListFrom<_T>::type >
constexpr auto applyTuple( const F& f, T&& t )
    -> decltype( applyIndexList<Fi>(IL(),f,std::forward<T>(t)) )
{
    return applyIndexList<Fi>( IL(), f, std::forward<T>(t) );
}
 
// Because std::make_tuple can't be passed 
// to higher order functions.
constexpr struct MakeTuple {
    template< class ...X >
    constexpr std::tuple<X...> operator () ( X ...x ) {
        return std::tuple<X...>( std::move(x)... );
    }
} tuple{};
 
// Returns the initial elements. (All but the last.)
// init( {1,2,3} ) = {1,2}
template< class T,
          size_t N = std::tuple_size<T>::value, 
          class IL = typename Enumerate< 0, N-1 >::type >
constexpr auto init( const T& t )
    -> decltype( applyIndexList(IL(),tuple,t) )
{
    return applyIndexList( IL(), tuple, t );
}
 
// Returns a new tuple with every value from t except the first.
// tail( {1,2,3} ) = {2,3}
template< class T,
          size_t N = std::tuple_size<T>::value, 
          class IL = typename Enumerate< 1, N >::type >
constexpr auto tail( const T& t )
    -> decltype( applyIndexList(IL(),tuple,t) )
{
    return applyIndexList( IL(), tuple, t );
}
 
// Reconstruct t in reverse.
template< class T >
constexpr auto reverse( const T& t ) 
    -> decltype( applyTuple<RGet>(tuple,t) )
{
    return applyTuple< RGet >( tuple, t );
}
 
template< size_t i, size_t ...j, class F, class T >
void forEachIndex( IndexList<i,j...>, const F& f, const T& t ) {
    f( std::get<i>(t) );
    forEachIndex( IndexList<j...>(), f, t );
}
 
template< class F, class T >
void forEachIndex( IndexList<>, const F& f, const T& t ) {
}
 
template< class F, class T >
void forEach( const F& f, const T& t ) {
    constexpr size_t N = std::tuple_size<T>::value;
    using IL = typename Enumerate<0,N>::type;
    forEachIndex( IL(), f, t );
}
 
constexpr struct PrintItem {
    template< class X >
    void operator () ( const X& x ) const {
        std::cout << x << ' ';
    }
} printItem{};
 
constexpr struct PushBack {
    template< class ...X, class Y >
    constexpr auto operator () ( std::tuple<X...> t, Y y )
        -> std::tuple< X..., Y >
    {
        return std::tuple_cat( std::move(t), tuple(std::move(y)) );
    }
} pushBack{};
 
constexpr struct PushFront {
    template< class ...X, class Y >
    constexpr auto operator () ( std::tuple<X...> t, Y y )
        -> std::tuple< Y, X... >
    {
        return std::tuple_cat( tuple(std::move(y)), std::move(t) );
    }
} pushFront{};
 
constexpr auto head = Get<0>();
constexpr auto last = RGet<0>();
 
// Chain Left.
constexpr struct ChainL {
    template< class F, class X >
    constexpr X operator () ( const F&, X x ) {
        return x;
    }
 
    template< class F, class X, class Y, class ...Z >
    constexpr auto operator () ( const F& b, const X& x, const Y& y, const Z& ...z) 
        -> decltype( (*this)(b, b(x,y), z... ) )
    {
        return (*this)(b, b(x,y), z... );
    }
} chainl{};
 
// Fold Left.
constexpr struct FoldL {
    // Given f and {x,y,z}, returns f( f(x,y), z ).
    template< class F, class T >
    constexpr auto operator () ( const F& f, const T& t ) 
        -> decltype( applyTuple(chainl,pushFront(t,f)) )
    {
        return applyTuple( chainl, pushFront(t,f) );
    }
} foldl{};
 
// Fold Right.
constexpr struct FoldR {
    // Given f and {x,y,z}, returns f( f(z,y), x ).
    template< class F, class T >
    constexpr auto operator () ( const F& f, const T& t ) 
        -> decltype( foldl(f,reverse(t)) )
    {
        return foldl( f, reverse(t) );
    }
} foldr{};
 
auto ten = foldl( std::plus<int>(), std::make_tuple(1,2,3,4) );
 
template< class ...X >
constexpr auto third_arg( X&& ...x )
    -> Elem< 2, std::tuple<X...> >
{
    return std::get<2>( std::forward_as_tuple(std::forward<X>(x)...) );
}
 
 
template< class F, class ...X >
struct TFunction {
    F f;
    std::tuple<X...> applied; // applied arguments.
 
    template< class ...Y >
    constexpr TFunction( F f, Y&& ...y )
        : f( std::move(f) ), applied( std::forward<Y>(y)... )
    {
    }
 
    template< class ...Y, class T = std::tuple<X...,Y...> >
    constexpr T add( Y&& ...y ) {
        return std::tuple_cat (
            applied,
            std::forward_as_tuple( std::forward<Y>(y)... )
        );
    }
 
    template< class ...Y >
    constexpr auto operator () ( Y&& ...y )
        -> typename std::result_of< F( X..., Y... ) >::type
    {
        return applyTuple( f, add(std::forward<Y>(y)...) );
    }
};
 
template< class F, class ...X, class R = TFunction<F,X...> >
R tfun( F f, X ...x ) {
    return R( std::move(f), std::move(x)... );
}
 
#include <cmath>
 
// Quadratic root.
constexpr struct QRoot {
    using result = std::tuple<float,float>;
 
    result operator () ( float a, float b, float c ) const {
        float root = std::sqrt( b*b - 4*a*c );
        float den  = 2 * a;
        return result( (-b+root)/den, (-b-root)/den );
    }
} qroot{};
 
std::ostream& operator << ( std::ostream& os, const QRoot::result r ) {
    return os << std::get<0>(r) << " or " << std::get<1>(r);
}
 
// Convert a tuple-taking function to a normal one.
// curry : ( (a,b...) -> c ) x a x b... -> c
template< class F, class ...X >
constexpr auto curry( const F& f, X&& ...x )
    -> decltype( f( std::forward_as_tuple(std::forward<X>(x)...) ) )
{
    return f( std::forward_as_tuple(std::forward<X>(x)...) );
}
 
// Pair Sum.
// psum : (int,int) -> int
unsigned int psum( std::tuple<int,int> p ) {
    return head(p) + last(p);
}
 
int five = curry( psum, 3, 2 );
 
template< template<size_t> class Fi = Get, size_t i,
          class F, class ...T >
constexpr auto zipRow( const F& f, T&& ...t )
    -> decltype( f(Fi<i>()(std::forward<T>(t))...) )
{
    return f( Fi<i>()( std::forward<T>(t) )... );
}
 
template< template<size_t> class Fi = Get, size_t ...i,
          class Ret, class F, class ...T >
constexpr auto zipIndexList( IndexList<i...>, 
                             const Ret& r, const F& f, T&& ...t )
    -> decltype( r(zipRow<Fi,i>(f,std::forward<T>(t)...)...) )
{
    return r( zipRow< Fi, i >( f, std::forward<T>(t)... )... );
}
 
template< template<size_t> class Fi = Get,
          class Ret, class F, class T, class ...U,
          class _T = typename std::decay<T>::type,
          class IL = typename IListFrom<_T>::type >
constexpr auto zipTupleTo( const Ret& r, const F& f, T&& t, U&& ...u )
    -> decltype( zipIndexList<Fi>(IL(),r,f,std::forward<T>(t),std::forward<U>(u)...) )
{
    return zipIndexList<Fi>( IL(), r, f, std::forward<T>(t), std::forward<U>(u)... );
}
 
template< template<size_t> class Fi = Get,
          class F, class ...T >
constexpr auto zipTuple( const F& f, T&& ...t )
    -> decltype( zipTupleTo<Fi>(tuple,f,std::forward<T>(t)...) )
{
    return zipTupleTo<Fi>( tuple, f, std::forward<T>(t)... );
}
 
template< class X, class ...Y >
bool noneTrue( const X& x, const Y& ...rest ) {
    return x ? false : noneTrue(rest...);
}
 
bool noneTrue() { return true; }
 
// We require these polymorphic function objects.
constexpr struct Inc {
    template< class X >
    constexpr X operator () ( X x ) { return ++x; }
} inc{};
 
constexpr struct Eq {
    template< class X >
    constexpr bool operator () ( const X& a, const X& b ) 
    { return a == b; }
} eq{};
 
struct Or {
    template< class X >
    constexpr bool operator () ( const X& a, const X& b ) 
    { return a || b; }
};
 
// Wrapper to dereference arguments before applying.
// indirect : (a -> b) -> (*a -> b)
template< class F > struct Indirect {
    F f = F();
 
    constexpr Indirect( F f ) : f(std::move(f)) { }
 
    template< class ...It >
    constexpr auto operator () ( It ...it )
        -> decltype( f(*it...) )
    {
        return f( *it... );
    }
};
 
template< class F, class I = Indirect<F> > 
constexpr I indirect( F f ) {
    return I( std::move(f) );
}
 
 
#include <vector>
#include <algorithm>
template< class F, class ...X,
          class Result = typename std::result_of<F(X...)>::type,
          class Ret = std::vector<Result> >
Ret transform( const F& f, const std::vector<X>& ...vs )
{
    Ret r;
 
    const auto ends = tuple( vs.end()... );
 
    // Iterate through each vector in parallel.
    for( auto its  = tuple( vs.begin()... ); 
         // This unrolls to: not (it0==end0 || it1==end1 || ...)
         not foldl( Or(), zipTuple(eq,its,ends) );
         // Increment each iterator.
         its = zipTuple( inc, its ) )
    {
        r.emplace_back (
            applyTuple( indirect(f), its )
        );
    }
 
    return r;
}
 
// product : {x,y} x {a,b} -> {{x,a},{x,b},{y,a},{y,b}}
constexpr struct Product {
    // {...xi...} x {...aj...} -> {xi,aj}
    template< size_t i, size_t j, class T, class U >
    static constexpr auto zip( const T& t, const U& u )
        -> decltype( tuple(std::get<i>(t),std::get<j>(u)) )
    {
        return tuple( std::get<i>(t), std::get<j>(u) );
    }
 
    // {...xi...} x {a0,a1,a2...} -> { {xi,a0}, {xi,a1}, ... }
    template< size_t i, size_t ...j, class T, class U >
    static constexpr auto withI( IndexList<j...>, const T& t, const U& u )
        -> decltype( tuple(zip<i,j>(t,u)...) )
    {
        return tuple( zip<i,j>(t,u)... );
    }
        
    // {x...} x {a...} -> { {x,a}... }
    template< size_t ...i, size_t ...j, class T, class U >
    static constexpr auto withIndexes( IndexList<i...>, IndexList<j...> js,
                                       const T& t, const U& u )
        -> decltype( std::tuple_cat(withI<i>(js,t,u)...) )
    {
        return std::tuple_cat( withI<i>(js,t,u)... );
    }
 
    template< class T, class U,
              class IL  = typename IListFrom<T>::type,
              class IL2 = typename IListFrom<U>::type >
    constexpr auto operator () ( const T& t, const U& u )
        -> decltype( withIndexes(IL(),IL2(),t,u) )
    {
        return withIndexes( IL(), IL2(), t, u );
    }
} product{};
 
template< class F > struct ApplyF {
    F f = F();
 
    constexpr ApplyF( F f ) : f(std::move(f)) { }
 
    template< class T >
    constexpr auto operator () ( T&& t ) 
        -> decltype( applyTuple(f,std::forward<T>(t)) )
    {
        return applyTuple( f, std::forward<T>(t) );
    }
};
 
template< class F > 
constexpr ApplyF<F> applyF( F f ) {
    return ApplyF<F>(std::move(f));
}
 
constexpr struct MapTuple {
    template< class F, class T, class U >
    constexpr auto operator () ( const F& f, const T& t, const U& u )
        -> decltype( zipTuple(applyF(f),product(t,u)) )
    {
        return zipTuple( applyF(f), product(t,u) );
    }
} mapTuple{};
 
constexpr struct Id {
    template< class X >
    constexpr X operator () ( X&& x ) {
        return std::forward<X>(x);
    }
 
    template< class F, class X, class ...Y >
    constexpr auto operator () ( const F& f, X&& x, Y&& ...y )
        -> typename std::result_of< F(X,Y...) >::type
    {
        return f( std::forward<X>(x), std::forward<Y>(y)... );
    }
} id{};
 
 
int main() {
    auto sums = mapTuple( std::plus<int>(), tuple(1,2,3), tuple(7,8,9) );
    std::cout << "map (+) (1,2,3) (7,8,9) = ";
    forEach( printItem, sums );
    std::cout << std::endl;
 
    auto zipped = zipTupleTo( tuple, std::plus<int>(), tuple(1,10), 
                                                       tuple(2,20) );
    std::cout << " 1 +  2 = " << std::get<0>(zipped) << std::endl;
    std::cout << "10 + 20 = " << std::get<1>(zipped) << std::endl;
 
    std::vector<int> v = {1,10,100},
                     w = {2,20,200},
                     x = {3,30,300};
 
    auto vw = transform (
        [](int x, int y, int z){ return x+y+z; }, 
        v, w, x 
    );
    std::cout << "  1 +   2 +   3 = " << vw[0] << std::endl;
    std::cout << " 10 +  20 +  30 = " << vw[1] << std::endl;
    std::cout << "100 + 200 + 300 = " << vw[2] << std::endl;
 
    auto ab = std::make_tuple( 1, 3 );
    auto qroot_ab = [&] ( float c ) {
        return applyTuple( qroot, pushBack(ab,c) );
    };
    std::cout << "qroot(1,3,-4) = " << qroot_ab(-4) << std::endl;
    std::cout << "qroot(1,3,-5) = " << qroot_ab(-5) << std::endl;
 
    auto bc = std::make_tuple( 3, -4 );
    auto qroot_bc = [&] ( float a ) {
        return applyTuple( qroot, pushFront(bc,a) );
    };
    std::cout << "qroot(1,3,-4) = " << qroot_bc(1) << std::endl;
    std::cout << "qroot(1,3,-5) = " << qroot_bc(2) << std::endl;
 
    std::cout << "ten = " << ten << std::endl; // foldl example.
    std::cout << "five = " << five << std::endl; // Curry example.
 
    std::cout << "third_arg(1,2,3,4) = " << third_arg(1,2,3,4) << std::endl;
 
    std::cout << "2 + 4 = " 
              << applyTuple( std::plus<int>(), std::make_tuple(2,4) ) 
              << std::endl;
 
    constexpr auto t = std::make_tuple( 1, 'a', "str" );
    std::cout << "t = ";
    forEach( printItem, t );
    std::cout << std::endl;
 
    std::cout << "head = " << head(t) << std::endl;
    std::cout << "last = " << last(t) << std::endl;
 
    std::cout << "reverse = ";
    forEach( printItem, reverse(t) );
    std::cout << std::endl;
}