#ifndef _HASHMAP_H
#define _HASHMAP_H

template< class Key, class Data >
class HashMapNode {
public:
   Key first;
   Data second;
   size_t index;
   HashMapNode * next;
   HashMapNode * my_next;
   HashMapNode(const Key & k, const Data & v, const size_t i) {
      first = k;
      second = v;
      index = i;
      next = 0;
      my_next = 0;
   }
};

template< class Key, class Data >
class HashIterator {
   HashMapNode< Key, Data > * node;
public:

   HashIterator() {
      node = 0;
   }

   HashIterator(const HashIterator & cp) {
      node = pc.node;
   }

   HashIterator(HashMapNode< Key, Data > * ptr) {
      node = ptr;
   }

   HashIterator & operator++() {
      node = node->my_next;
      return *this;
   }

   HashIterator & operator++(int) {
      node = node->my_next;
      return *this;
   }

   bool operator==(const HashIterator & right) {
      bool ret = false;
      ret = node == right.node;
      return ret;
   }

   bool operator!=(const HashIterator & right) {
      bool ret = false;
      ret = node != right.node;
      return ret;
   }

   HashIterator & operator=(const HashIterator & cp) {
      node = cp.node;
      return *this;
   }
   
   HashMapNode< Key, Data > * operator->() {
      return node;
   }
};

inline
int hashpjw(const char* t)
{
   unsigned h=0, g;
   for(;*t;++t) {
      h = (h << 4)+ *t;
      if((g=h)&0xf0000000) {
         h ^= g>>24;
         h ^= g;
      }
   }
   return h;
}

template< class Key >
class DefaultHashFunction {
public:
   size_t operator()(const Key & first) const {
      size_t hc = ::hashpjw(first.c_str());
      return hc;
   }
};

template< class Key, class Value, class HashFun = DefaultHashFunction< Key > >
class hashmap {
public:
   typedef HashIterator< Key, Value > iterator;

private:
   HashMapNode< Key, Value > ** tbl;
   HashMapNode< Key, Value > * head;
   size_t tbl_size;
   size_t _size;
   HashFun hash;

public:
   hashmap(const size_t sz = 1001) {
      tbl_size = sz;
      head = 0;
      tbl = new HashMapNode< Key, Value >*[tbl_size]; 
      for(size_t i = 0; i < tbl_size; i++) {
         tbl[i] = 0; 
      }
      _size = 0;
   }
   ~hashmap() {
      for(size_t i = 0; i < tbl_size; i++) {
         while(tbl[i]) {
            HashMapNode< Key, Value > * temp = tbl[i];
            tbl[i] = temp->next;
            delete temp;
         }
      }
      delete [] tbl;
   }
   void put(const Key & k, const Value & v) {
      size_t index = hash(k) % tbl_size;
      HashMapNode< Key, Value > * nn = tbl[index];
      if(nn == 0) {
         HashMapNode< Key, Value > * n = new HashMapNode< Key, Value >(k,v,index);
         n->my_next = head;
         head = n;
         tbl[index] = n;
         _size++;
      }
      else {
         bool found = false;
         for(HashMapNode< Key, Value > * p = nn; p; p = p->next) {
            if(p->first == k) {
               p->second = v;
               found = true;
               break;
            }
         }
         if(!found) {
            HashMapNode< Key, Value > * n = new HashMapNode< Key, Value >(k,v,index);
            n->my_next = head;
            head = n;
            n->next = tbl[index];
            tbl[index] = n;
            _size++;
         }
      }
   }
   Value & get(const Key & k) {
      size_t index = hash(k) % tbl_size;
      HashMapNode< Key, Value > * n = tbl[index];
      if(n) {
         for(HashMapNode< Key, Value > * p = n; p; p = p->next) {
            if(p->first == k) {
               return p->second;
            }
         }
      }
      put(k,Value());
      return get(k);
   }

   Value & operator[](const Key & k) {
      return get(k);
   }

   iterator begin() const {
      return iterator(head);
   }
 
   iterator end() const {
      return iterator(0);
   }

   iterator find(const Key & k) {
      size_t index = hash(k) % tbl_size;
      HashMapNode< Key, Value > * nn = tbl[index];
      if(nn) {
         for(HashMapNode< Key, Value > * n = nn; n; n = n->next) {
            if(n->first == k) {
               return iterator(n);
            }
         }
      }
      return 0;
   }

   void erase(iterator ptr) {
      HashMapNode< Key, Value > * n = tbl[ptr->index];
      if(iterator(n) == ptr) {
         tbl[ptr->index] = n->next;
         _size--;
         delete n;
      }
      else {
         while(n) {
            if(n->next == ptr->next) {
               n->next = ptr->next;
               delete n;
               _size--;
            }
            n = n->next;
         }
      }
   }   

   const size_t size() const {
      return _size;
   }

   const size_t size() {
      return _size;
   }
};

#endif /* _HASHMAP_H */
