#ifndef SAMPLE_PREFETCHER_H
#define SAMPLE_PREFETCHER_H

#include <assert.h>

#include <vector>
#include <list>

template<class KeyType,class ItemType>
struct Container
{
	int theHeight,theWidth,theKeyShift;
	unsigned long long theTagMask; // dictates number of bits used to tag elements (includes lower index bits for simulation purposes only)
	unsigned long long theIndexMask; // based only on Height of structure

	typedef std::pair<KeyType,ItemType> Item;
	typedef std::list<Item> ListType;
	std::vector<ListType> theItems;
	typedef typename ListType::iterator Iter;
	Container(
		int aHeight
	,	int aWidth
	,	int aKeyShift
	,	int aTagBits
	)
	:	theHeight(aHeight)
	,	theWidth(aWidth)
	,	theKeyShift(aKeyShift)
	,	theTagMask((1ULL<<aTagBits)-1)
	,	theIndexMask(theHeight-1)
	{
		assert(!(theHeight & theIndexMask));
		theItems.resize(theHeight);
		for(int i=0;i<theHeight;++i)
			theItems[i].resize(theWidth);
	}

	~Container() {
		/*for(int i=0;i<theHeight;++i)
			for(int j=0;j<theWidth;++i)
				theItems[i].push_back(new ItemType());*/
	}

	Item insert(KeyType aKey,ItemType anItem) {
		int aKeyIndex(index(aKey));
		Item anOldItem(*theItems[aKeyIndex].rbegin());
		theItems[aKeyIndex].pop_back();
		KeyType aTag = tag(aKey);
		theItems[aKeyIndex].push_front(std::make_pair(aTag,anItem));
		theItems[aKeyIndex].front().second.EVICT_DETECTOR = aKey;
		//fprintf(stderr,"insert %llx [%d:%d/%d]\n",aKey,index(aKey),theHeight,theWidth);
		return anOldItem;
	}

	Iter end() {
		return theItems[0].end();
	}

	static inline unsigned long long inthash(unsigned long long key)
	{
		key += (key << 12);
		key ^= (key >> 22);
		key += (key << 4);
		key ^= (key >> 9);
		key += (key << 10);
		key ^= (key >> 2);
		key += (key << 7);
		key ^= (key >> 12);
		return key;
	}

	int index(KeyType aKey) {
		return (inthash(aKey >> theKeyShift) & theIndexMask);
	}

	int tag(KeyType aKey) {
		return (inthash(aKey >> theKeyShift) & theTagMask);
	}

	Iter find(KeyType aKey) {
		ListType& aList(theItems[index(aKey)]);
		KeyType aTag = tag(aKey);
		for(Iter i=aList.begin();i!=aList.end();i++) {
			//fprintf(stderr,"search for %llx in %llx [%d:%d/%d]\n",aKey,i->first,index(aKey),theHeight,theWidth);
			if (i->first == aTag) {
				aList.push_front(*i);
				aList.erase(i);
				return aList.begin();
			}
		}
		return end();
	}

	bool erase(KeyType aKey) {
		ListType& aList(theItems[index(aKey)]);
		KeyType aTag = tag(aKey);
		for(Iter i=aList.begin();i!=aList.end();i++) {
			if (i->first == aTag) {
				aList.erase(i);
				aList.resize(theWidth);
				return true;
			}
		}
		return false;
	}

};

#endif