#ifndef _HASHTABLE_H
#define _HASHTABLE_H

#include <string.h>
#include <stdlib.h>

typedef unsigned long hash_t;

#define HTMINSIZE 8

template<class K, class V>
struct HTEntry
{
  K key;
  V value;
  struct HTEntry<K,V> *next;
};

template<class K, class V>
class HashTableIterator;

template<class K, class V>
class HashTable
{
  friend class HashTableIterator<K,V>;

 public:

  HashTable()
    {
      _buckets=NULL;
      _allocated=0;
      _size=0;

      grow();
    }
  
  ~HashTable()
    {}
  
  void grow()
    {
      if ((_size+1)<(_allocated*2/3))
	return;

      int newallocated=_size*3/2;

      if (newallocated<HTMINSIZE)
	newallocated=HTMINSIZE;

      struct HTEntry<K,V> **newbuckets=(struct HTEntry<K,V>**) 
	calloc(sizeof(HTEntry<K,V>*), newallocated);
      
      if (_buckets!=NULL)
	{
	  for (int i=0;i<_allocated;i++)
	    {
	      while (_buckets[i]!=NULL)
		{
		  struct HTEntry<K,V> *e=_buckets[i];
		  
		  _buckets[i]=e->next;
		  
		  hash_t h=hthash(e->key);
		  int index=h%newallocated;
		  e->next=newbuckets[index];
		  newbuckets[index]=e;
		}
	    }
	  free(_buckets);
	}

      _buckets=newbuckets;
      _allocated=newallocated;
    }

  void put(K key, V value)
    {
      hash_t h=hthash(key);
      grow();

      int index=h%_allocated;

      // look for a matching entry in the bucket and update the value
      // if there is one.

      struct HTEntry<K,V> *e = _buckets[index];
      
      while (e!=NULL) 
	{
	  if (htequal(e->key, key))
	    {
	      e->value=value;
	      return;
	    }
	  e=e->next;
	}
      
      // nope, just create a new element and prepend it.
      struct HTEntry<K,V> *newe = (struct HTEntry<K,V>*) 
	malloc(sizeof(struct HTEntry<K,V>));
      newe->key=key;
      newe->value=value;
      newe->next=_buckets[index];
      _buckets[index]=newe;
      _size++;
    }

  V get(K key)
    {
      hash_t h=hthash(key);

      int index=h%_allocated;

      if (_buckets[index]==NULL)
	{
	  return NULL;
	}

      struct HTEntry<K,V> *e = _buckets[index];
      
      while (e!=NULL) 
	{
	  if (htequal(e->key, key))
	    {
	      return e->value;
	    }
	  e=e->next;
	}

      return NULL;
    }

  HashTableIterator<K,V> *iterator()
    {
      return new HashTableIterator<K,V>(this);
    }

  int getSize()
    {
      return _size;
    }

  /** returns success **/
  int remove(K key)
    {
      hash_t h=hthash(key);
      
      int index=h%_allocated;
      
      if (_buckets[index]==NULL)
	{
	  return 0;
	}

      struct HTEntry<K,V> *e = _buckets[index];
      struct HTEntry<K,V> **pe = &_buckets[index];

      while (e!=NULL) 
	{
	  if (htequal(e->key, key))
	    {
	      *pe=e->next;
	      free(e);
	      _size--;
	      return 1;
	    }
	  pe=&(e->next);
	  e=e->next;
	}

      return NULL;

    }

  struct HTEntry<K,V> **_buckets;
  int _allocated;
  int _size;
};

inline hash_t hthash(const char *s)
{
  hash_t h=0;
  int len=strlen(s);

  for (int i=0;i<len;i++)
    {
      h=(h<<7)+s[i]+(h>>23);
    }
  
  return h+len;
}

inline hash_t htequal(const char *a,const char *b)
{
  return !strcmp(a,b);
}

inline hash_t hthash(long a)
{
  return a;
}

inline hash_t htequal(long a, long b)
{
  return a==b;
}

template<class K, class V>
class HashTableIterator
{
 public:
  HashTableIterator(HashTable<K,V> *ht)
    {
      _ht=ht;
      _currentbucket=-1;
      _currentnode=NULL;
      _nextbucket=-1;
      _nextnode=NULL;
    }

  bool hasMore()
    {
      return nextInternal();
    }

  bool next()
    {
      bool b=nextInternal();
      if (!b)
	return false;

      _currentnode=_nextnode;
      _currentbucket=_nextbucket;

      return true;
    }

  K getKey()
    {
      return _currentnode->key;
    }

  V getValue()
    {
      return _currentnode->value;      
    }

  bool nextInternal()
    {
      _nextbucket=_currentbucket;
      _nextnode=_currentnode;

      if (_nextnode!=NULL)
	{
	  _nextnode=_nextnode->next;
	  if (_nextnode!=NULL)
	    return true;
	}

      while (_nextnode==NULL)
	{
	  _nextbucket++;
	  if (_nextbucket>=_ht->_allocated)
	    return false;
	  
	  _nextnode=_ht->_buckets[_nextbucket];
	}

      return (_nextnode!=NULL);
    }

 private:
  HashTable<K,V> *_ht;
  int _currentbucket,_nextbucket;
  struct HTEntry<K,V> *_currentnode,*_nextnode;
};


#endif