#include <iostream>
#include <unordered_map>
#include <cmath>
#include <chrono>
#include <functional>

class TimedSection {
public:
	TimedSection(std::string nameOfMeasurment) : nameOfMeasurment(nameOfMeasurment) {
		start = std::chrono::high_resolution_clock::now();
	}
	
	~TimedSection() {
		auto elapsedTime = std::chrono::high_resolution_clock::now() - start;
		std::cout << "Measurment taken(" << nameOfMeasurment << ") Elapsed time: " <<
			std::chrono::duration_cast<std::chrono::nanoseconds>(elapsedTime).count() << "ns" << std::endl;
	}
	
private:
	std::string nameOfMeasurment;
	std::chrono::time_point<std::chrono::high_resolution_clock> start;
};

template<typename Arg, typename F>
auto memoize(F&& f) {
	return [f](Arg arg) {
		static std::unordered_map<Arg, decltype(f(arg))> memoizedArgs;
		if(memoizedArgs.find(arg) == memoizedArgs.end()) {
			memoizedArgs[arg] = f(arg);
		}
		
		return memoizedArgs[arg];
	};
}

int main() {
	std::function<int(int)> fib = [&fib](int n) {return n < 2 ? 1 : fib(n-1) + fib(n-2);};

	
	auto memoizedFib = memoize<int>(fib);
	
	{
		TimedSection("without memoization");
		for(auto i = 0; i < 100; i++) {
			fib(30);
		}
	}
	
	{
		TimedSection("with memoization");
		for(auto i = 0; i < 100; i++) {
			memoizedFib(30);
		}
	}
	
	return 0;
}