#ifndef HASHTABLE__HPP_
#define HASHTABLE__HPP_

#include <vector>
#include <list>
#include <algorithm>

template <class T>
class Func2{
	const int n;
public:
	Func2(int i): n(i) { }
	int operator()(const T& x) const { return (x+x/3)%n; }
};

template <typename T, typename Fun >
class HashTable{
	std::vector<std::list<T> > ht;
	const Fun f;

public:
	HashTable(int size): ht(size), f(size) {}

	bool has(const T& val) const;
	int size(const T& val) const { return ht[f(val)].size(); }
	int size() const;
	void insert(const T& val) { ht[f(val)].push_back(val); }
	void erase(const T& val) { ht[f(val)].remove(val); }
};

template<typename T, typename Fun>
bool HashTable<T,Fun>::has(const T& val) const{
	int k=f(val);
	return (std::find(ht[k].begin(),ht[k].end(),val))!=ht[k].end();
}

template<typename T, typename Fun>
int HashTable<T,Fun>::size() const{
	int sum=0;
	for(unsigned int i=0;i<ht.size();++i){
		sum+=ht[i].size();
	}
	return sum;
}

#endif //_HASHTABLE_HPP_