#ifndef __UOPCACHE_H__
#define __UOPCACHE_H__

#include <map>
#include <list>

template <class kT, class vT, class factoryT, class cacheT=map<kT,vT> >
class Cache {

public:
	Cache(factoryT &f, int i=256) : factory(f) {max=i;}
	vT &operator[](const kT &k)
	{
		typename cacheT::iterator iter=cache.find(k);
		if (iter!=cache.end())
			return iter->second;
		vT &v=cache[k];
		factory.produce(k,v);
		queue.push_front(k);
		if (queue.size()>=max)
		{
			kT victim=queue.back();
			factory.recycle(cache[victim]);
			cache.erase(victim);
			queue.pop_back();
		}
		return v;
	}
private:
	unsigned int max;
	cacheT cache;
	list<kT> queue;
	factoryT &factory;
};

template <class kT, class vT, class factoryT, bool tdmap, class cacheT=map<kT,vT> >
class MapCache {

public:
	MapCache(int i=256) : max(i) {}
	vT &operator[](const kT &k)
	{
		typename cacheT::iterator iter=cache.find(k);
		if (iter!=cache.end())
			return iter->second;
		vT &v=cache[k];
		factory.produce(k,tdmap,v);
		queue.push_front(k);
		if (queue.size()>=max)
		{
			kT victim=queue.back();
			factory.recycle(cache[victim]);
			cache.erase(victim);
			queue.pop_back();
		}
		return v;
	}
private:
	unsigned int max;
	cacheT cache;
	list<kT> queue;
	factoryT factory;
};

#endif