#ifndef _HASHMAP_H

/*

(C) Copyright 2019.  All rights reserved.
This file is the intellectual property of Matthew W. Coan.

STL STYLE HASHTABLE...

Auhtor: Matthew W. Coan
Date: Sat Mar  2 18:04:59 EST 2019

*/

template< class Key, class Value >
class HashMapNode {
public:
   Key key;
   Value value;
   size_t index;
   HashMapNode * next;
   HashMapNode(const Key & k, const Value & v, const size_t i) {
      key = k;
      value = v;
      index = i;
      next = 0;
   }
};

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 & key) const {
      size_t hc = ::hashpjw(key.c_str());
      return 0xFFFFFFFF - hc;
   }
};

template< class Key, class Value, class HashFun = DefaultHashFunction< Key > >
class hashmap {
public:
   typedef HashMapNode< Key, Value > * iterator;
private:
   HashMapNode< Key, Value > ** tbl;
   size_t tbl_size;
   size_t _size;
   HashFun hash;
public:
   hashmap(const size_t sz = 1001) {
      tbl_size = sz;
      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);
         tbl[index] = n;
         _size++;
      }
      else {
         bool found = false;
         for(HashMapNode< Key, Value > * p = nn; p; p = p->next) {
            if(p->key == k) {
               p->value = v;
               found = true;
               break;
            }
         }
         if(!found) {
            HashMapNode< Key, Value > * n = new HashMapNode< Key, Value >(k,v,index);
            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->key == k) {
               return p->value;
            }
         }
      }
      put(k,Value());
      return get(k);
   }

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

   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->key == k) {
               return n;
            }
         }
      }
      return 0;
   }

   iterator end() {
      return 0;
   }

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

#endif /* _HASHMAP_H */
