// Copyright (C) 1999,2000 Bruce Guenter <bruceg@em.ca>

//

// This program is free software; you can redistribute it and/or modify

// it under the terms of the GNU General Public License as published by

// the Free Software Foundation; either version 2 of the License, or

// (at your option) any later version.

//

// This program is distributed in the hope that it will be useful,

// but WITHOUT ANY WARRANTY; without even the implied warranty of

// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the

// GNU General Public License for more details.

//

// You should have received a copy of the GNU General Public License

// along with this program; if not, write to the Free Software

// Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA

#ifndef HASH_TABLE__H__

#define HASH_TABLE__H__

#include "mystring/mystring.h"

struct hash_base

{

  const mystring key;

  const unsigned hash;

  hash_base(const mystring& k, unsigned h)

    : key(k), hash(h)

    {

    }

};

template<class T>

struct hash_node : public hash_base

{

  T data;

  hash_node(const mystring& k, unsigned h, T d)

    : hash_base(k, h), data(d)

    {

    }

};

template<class T>

struct hash_ptr_node : public hash_base

{

  T* data;

  hash_ptr_node(const mystring& k, unsigned h, T* d)

    : hash_base(k, h), data(d)

    {

    }

  ~hash_ptr_node()

    {

      if(data)

	delete data;

    }

};

static const unsigned hash_prime_list[] = {

  53,         97,         193,       389,       769,

  1543,       3079,       6151,      12289,     24593,

  49157,      98317,      196613,    393241,    786433,

  1572869,    3145739,    6291469,   12582917,  25165843,

  50331653,   100663319,  201326611, 402653189, 805306457,

  1610612741, 3221225473U, 4294967291U

};

template<class TYPE, class NODE, class HASH>

class hash_table_iterator;

template<class TYPE, class NODE, class HASH>

class hash_table

{

  friend class hash_table_iterator<TYPE,NODE,HASH>;

  TYPE dummy;

  HASH hash;

  NODE** table;

  unsigned prime_index;

  unsigned prime;

  unsigned oversize;

  unsigned _count;

  unsigned rehash(unsigned h) const

    {

      return (h + 1) % prime;

    }

  void alloc()

    {

      prime = hash_prime_list[prime_index];

      oversize = prime*3/4;

      table = new NODE*[prime];

      for(unsigned i = 0; i < prime; i++)

	table[i] = 0;

      _count = 0;

    }

  void realloc(unsigned new_index)

    {

      //unsigned old_prime_index = prime_index;

      unsigned old_prime = prime;

      NODE** old_table = table;

      prime_index = new_index;

      alloc();

      for(unsigned i = 0; i < old_prime; i++)

	if(old_table[i])

	  base_insert(old_table[i], true);

    }

  unsigned lookup(const mystring& key, unsigned hash) const

    {

      for(unsigned h = hash % prime; table[h]; h = rehash(h))

	if(table[h]->hash == hash && table[h]->key == key)

	  return h;

      return prime;

    }

  unsigned lookup(const mystring& key) const

    {

      return lookup(key, hash(key));

    }

  bool base_insert(NODE* e, bool unique)

    {

      unsigned h;

      for(h = e->hash % prime; table[h]; h = rehash(h)) {

	if(table[h]->hash == e->hash &&

	   table[h]->key == e->key) {

	  if(unique)

	    return false;

	  else {

	    delete table[h];

	    --_count;

	    break;

	  }

	}

      }

      table[h] = e;

      ++_count;

      return true;

    }

public:

  typedef hash_table_iterator<TYPE,NODE,HASH> iterator;

  hash_table()

    : dummy(0), prime_index(0)

    {

      alloc();

    }

  ~hash_table()

    {

      if(table) {

	empty();

	delete[] table;

      }

    }

  void empty()

    {

      for(unsigned i = 0; i < prime; i++)

	if(table[i]) {

	  delete table[i];

	  table[i] = 0;

	}

      _count = 0;

    }

  bool exists(const mystring& key) const

    {

      return lookup(key) >= prime;

    }

  const TYPE& operator[](const mystring& key) const

    {

      unsigned h = lookup(key);

      return (h >= prime) ? dummy : table[h]->data;

    }

  TYPE& operator[](const mystring& key)

    {

      unsigned h = lookup(key);

      return (h >= prime) ? dummy : table[h]->data;

    }

  unsigned count() const 

    {

      return _count;

    }

  bool insert(const mystring& key, TYPE data)

    {

      NODE* e = new NODE(key, hash(key), data);

      if(_count >= oversize)

	realloc(prime_index+1);

      return base_insert(e, true);

    }

  bool set(const mystring& key, TYPE data)

    {

      NODE* e = new NODE(key, hash(key), data);

      if(_count >= oversize)

	realloc(prime_index+1);

      return base_insert(e, false);

    }

  bool remove(const mystring& key, bool mustexist = false)

    {

      unsigned h = lookup(key);

      if(h < prime) {

	delete table[h];

	table[h] = 0;

	--_count;

	return true;

      }

      else

	return !mustexist;

    }

};

// hash table iterator

// usage: for(var.iterator i = var; !i; i++) use(*i);

template<class TYPE, class NODE, class HASH>

class hash_table_iterator

{

  hash_table<TYPE,NODE,HASH>& table;

  unsigned index;

  void next()

    {

      while(index < table.prime && !table.table[index])

	++index;

    }

public:

  hash_table_iterator(hash_table<TYPE,NODE,HASH>& t) : table(t), index(0)

    {

      next();

    }

  bool operator!() const

    {

      return index < table.prime;

    }

  bool at_end() const

    {

      return index >= table.prime;

    }

  void operator++() 

    {

      ++index;

      next();

    }

  TYPE& operator*()

    {

      return table.table[index]->data;

    }

  const TYPE& operator*() const

    {

      return table.table[index]->data;

    }

};

class hash_sample

{

public:

  unsigned operator()(const mystring& str) const

    {

      unsigned h = 0;

      for(unsigned i = 0; i < str.length(); i++)

	h = (h << 1) ^ (unsigned)str[i];

      return h;

    }

};

#endif