#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{

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

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


    private:
    std::vector<std::list<T> > ht;
    const Fun f;

};

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_