#include <tuple>
#include <functional>
#include <memory>
#include <iostream>

template<int n>
struct _apply {
  template<typename _Ret, typename... _Fargs, typename... _Targs, typename... _Oargs>
  static _Ret run(std::function<_Ret(_Fargs...)> fn,
		  std::tuple<_Targs...> t,
		  _Oargs... o) {
    return _apply<n-1>::run(fn, t, std::get<n-1>(t), o...);
  }
};

template<>
struct _apply<0> {
  template<typename _Ret, typename... _Fargs, typename... _Targs, typename... _Oargs>
  static _Ret run(std::function<_Ret(_Fargs...)> fn,
		  std::tuple<_Targs...> t,
		  _Oargs... o) {
    return fn(o...);
  }
};

template<typename _Ret, typename... _Fargs, typename... _Targs, typename... _Oargs>
_Ret apply(std::function<_Ret(_Fargs...)> fn,
	   std::tuple<_Targs...> t,
	   _Oargs... o) {
  return _apply<sizeof...(_Targs)>::run(fn, t, o...);
}



template<int X, typename A, typename B>
struct __if {
  typedef A result;
};
template<typename A, typename B>
struct __if<0, A, B> {
  typedef B result;
};









template<typename A, typename B> struct _reverse_tuple;

template<typename... _Dest>
struct _reverse_tuple<std::tuple<>, std::tuple<_Dest...>> {
  typedef std::tuple<_Dest...> result;
};
template<typename _Orig1, typename... _Orign, typename... _Dest>
struct _reverse_tuple<std::tuple<_Orig1, _Orign...>, std::tuple<_Dest...>> {
  typedef typename _reverse_tuple<std::tuple<_Orign...>, std::tuple<_Orig1, _Dest...>>::result result;
};

template<typename... _X>
struct reverse_tuple {
  typedef typename _reverse_tuple<std::tuple<_X...>, std::tuple<>>::result result;
};
template<typename... _X>
struct reverse_tuple<std::tuple<_X...>> {
  typedef typename _reverse_tuple<std::tuple<_X...>, std::tuple<>>::result result;
};

template<typename... _X>
struct prepend_tuple;
template<typename... _X, typename _Y>
struct prepend_tuple<std::tuple<_X...>, _Y> {
  typedef std::tuple<_Y, _X...> result;
};

template<typename... _X>
struct append_tuple;
template<typename... _X, typename _Y>
struct append_tuple<std::tuple<_X...>, _Y> {
private:
  typedef typename reverse_tuple<_X...>::result reversed;
  typedef typename prepend_tuple<reversed, _Y>::result prepended;
public:
  typedef typename reverse_tuple<prepended>::result result;
};

template<typename _X>
struct tuple_maker;
template<typename... _X>
struct tuple_maker<std::tuple<_X...>> {
  static std::tuple<_X...> create(_X... x) {
    return std::tuple<_X...>(x...);
  }
  typedef std::function<std::tuple<_X...>(_X...)> function_type;
};






template<typename _Sig>
class curryable_impl_base;
template<typename _Ret, typename _Arg>
class curryable_impl_base<_Ret(_Arg)> {
 protected:
  typedef _Arg _NextArg;
 public:
  virtual _Ret operator()(_Arg) = 0;
};
template<typename _Ret, typename _Arg, typename... _Args>
class curryable_impl_base<_Ret(_Arg, _Args...)> {
 protected:
  typedef _Arg _NextArg;
 public:
  typedef curryable_impl_base<_Ret(_Args...)> _Next_base;
  virtual std::shared_ptr<_Next_base> operator()(_Arg) = 0;
};


template<int _N, typename _Si, bool _Zero>
struct _pop_first_n_args;
template<typename _Ret, typename... _Args>
struct _pop_first_n_args<0, _Ret(_Args...), true> {
  typedef _Ret result(_Args...);
};
template<int _N, typename _Ret, typename _Arg, typename... _Args>
struct _pop_first_n_args<_N, _Ret(_Arg, _Args...), false> {
  typedef typename _pop_first_n_args<_N-1, _Ret(_Args...), (_N-1)==0>::result result;
};

template<int _N, typename _Sig>
struct pop_first_n_args {
  typedef typename _pop_first_n_args<_N, _Sig, _N==0>::result result;
};




template<typename _Sig, typename... _Curried>
class _base_for {
public:
  typedef typename pop_first_n_args<sizeof...(_Curried), _Sig>::result curried_type;
  typedef curryable_impl_base<curried_type> result;
};




template<int remaining, typename _Signature, typename _Curried>
class _curryable;

template<typename _Ret, typename _Arg, typename... _Args, typename... _Curried>
class _curryable<1, _Ret(_Arg, _Args...), std::tuple<_Curried...>>
  : public _base_for<_Ret(_Arg, _Args...), _Curried...>::result {
    typedef typename _base_for<_Ret(_Arg, _Args...), _Curried...>::result _BaseType;
    typedef std::function<_Ret(_Arg, _Args...)> function_type;
    function_type _fn;
    std::tuple<_Curried...> _items;
 public:
    _curryable(function_type f, std::tuple<_Curried...> i)
      : _fn(f), _items(i) { }
      _Ret operator()(typename _BaseType::_NextArg arg) {
	return apply(_fn, _items, arg);
      }
  };

template<int _N, typename _Ret, typename _Arg, typename... _Args, typename... _Curried>
class _curryable<_N, _Ret(_Arg, _Args...), std::tuple<_Curried...>>
  : public _base_for<_Ret(_Arg, _Args...), _Curried...>::result {
    typedef typename _base_for<_Ret(_Arg, _Args...), _Curried...>::result _BaseType;
    typedef typename append_tuple<std::tuple<_Curried...>, typename _BaseType::_NextArg>::result next_tuple_type;
    typedef std::function<_Ret(_Arg, _Args...)> function_type;
    typedef _curryable<_N-1, _Ret(_Arg, _Args...), next_tuple_type> _Next;
    function_type _fn;
    std::tuple<_Curried...> _items;
 public:
    _curryable(function_type f, std::tuple<_Curried...> c)
      : _fn(f), _items(c)
      { }
      
      std::shared_ptr<typename _BaseType::_Next_base>
	operator()(typename _BaseType::_NextArg arg) {
	typedef tuple_maker<next_tuple_type> maker;
	auto new_items(apply(typename maker::function_type(maker::create), _items, arg));
	return std::shared_ptr<_Next>(new _Next(_fn, new_items));
      }
  };




template<typename _Sig>
class curryable;

template<typename _Ret, typename... _Args>
class curryable<_Ret(_Args...)> {
  typedef std::shared_ptr<curryable_impl_base<_Ret(_Args...)>> impl_type;
  impl_type _impl;
 public:
  curryable(impl_type i) : _impl(i) { }
    curryable(std::function<_Ret(_Args...)> fn)
      : _impl(new _curryable<sizeof...(_Args), _Ret(_Args...), std::tuple<>>(fn, std::tuple<>()))
      { }

      typedef typename pop_first_n_args<1, _Ret(_Args...)>::result next_sig;
      typedef typename __if<sizeof...(_Args)-1,  curryable<next_sig>, _Ret>::result next;
      template<typename _Arg>
      next operator()(_Arg arg) {
      return next(_impl->operator()(arg));
    }

    template<typename _Arg1, typename... _Argn>
      typename __if<sizeof...(_Args)-1-sizeof...(_Argn),
      curryable<typename pop_first_n_args<1 + sizeof...(_Argn), _Ret(_Args...)>::result>,
      _Ret>::result
      operator()(_Arg1 arg1, _Argn... argn) {
      return operator()(arg1)(argn...);
    }
};








using std::tuple;

double apply_test(char const *a, int b, double c) {
  std::cout<<"apply_test(\""<<a<<"\", "<<b<<", "<<c<<");\n";
  return std::string(a).size() + b + c;
}

int main() {
  std::function<double(char const *, int, double)> fn1(apply_test);

  curryable<double(char const *, int, double)> cc(fn1);

  std::cout<<"Calls: "<<cc("1",2,0.1)
	   <<"; "<<cc("a")(2)(9.8)
	   <<"; "<<cc("e",2)(2)
	   <<"; "<<cc("X")(2,3.4)<<"\n";
  std::function<double(double)> partial(cc("foo",2));
  std::cout<<partial(4.5)<<"\n";

  curryable<double(char const *,int,double)> fn2(apply_test);
  std::cout<<fn2("4")(8,7.3)<<"\n";

  return 0;
}