//original post: http://s...content-available-to-author-only...o.com/2011/03/17/automatic-memoization-in-cplusplus0x/
//a BOOST way of doing it: http://w...content-available-to-author-only...t.org/doc/libs/1_49_0/libs/flyweight/example/fibonacci.cpp
#include <iostream>
#include <functional>
#include <map>

#include <time.h>

//maahcros
#define TIME(__x) init=clock(); __x; final=clock()-init; std::cout << "time:"<<(double)final / ((double)CLOCKS_PER_SEC)<<std::endl;
#define TIME_INIT  clock_t init, final;
//void sleep(unsigned int mseconds) { clock_t goal = mseconds + clock(); while (goal > clock()); }

//the original memoize
template <typename ReturnType, typename... Args>
std::function<ReturnType (Args...)> memoize(std::function<ReturnType (Args...)> func)
{
	std::map<std::tuple<Args...>, ReturnType> cache;
	return ([=](Args... args) mutable  {
		std::tuple<Args...> t(args...);
		if (cache.find(t) == cache.end()) {
			cache[t] = func(args...);
		}
		return cache[t];
	});
}

/// wrapped factorial
struct factorial_class {

	/// the original factorial renamed into _factorial
	int _factorial(int n) {
		if (n==0) return 1;
		else {
		 std::cout<<" calculating factorial("<<n<<"-1)*"<<n<<std::endl;
		 sleep(0.5);
		 return factorial(n-1)*n;
		}
	}

	/// the trick function :)
	int factorial(int n) {
		if (memo) return (*memo)(n);
		return _factorial(n);
	}

	/// we're not a function, but a function object
	int operator()(int n) {
		return _factorial(n);
	}

	/// the trick holder
	std::function<int(int)>* memo;

	factorial_class() { memo=0; }
};

int main()
{
 TIME_INIT
	auto fact=factorial_class(); //virgin wrapper
	auto factorial = memoize( (std::function<int(int)>(fact) ) ); //memoize with the virgin wrapper copy
	fact.memo=&factorial; //spoilt wrapper
	factorial = memoize( (std::function<int(int)>(fact) ) ); //a new memoize with the spoilt wrapper copy

	TIME ( std::cout<<"factorial(3)="<<factorial(3)<<std::endl; ) // 3 calculations
	TIME ( std::cout<<"factorial(4)="<<factorial(4)<<std::endl; ) // 1 calculation
	TIME ( std::cout<<"factorial(6)="<<factorial(6)<<std::endl; ) // 2 calculations
	TIME ( std::cout<<"factorial(5)="<<factorial(5)<<std::endl; ) // 0 calculations

 	TIME ( std::cout<<"factorial(12)="<<factorial(12)<<std::endl; )
	TIME ( std::cout<<"factorial(8)="<<factorial(8)<<std::endl;  )
	return 0;
}

//upd: gotta find a way to make it work with std::function<int(int)>* memo; instead of a pointer