/* This file is part of cardwords
   (c) 1998 1999 2000 Tobias Peters
   see file COPYING for the copyright terms.
   
   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 CARDWORDS_HASHTABLE_HH
#define CARDWORDS_HASHTABLE_HH

#include <sys/types.h>
#include "cardwords_myslist.hh"
#include <climits> //<limits>
namespace CardWords {

// HashTable defines a hash table suitable for Strings.

// This is a type required by the hash table:
template <class data_type>
struct HashTableListElement {
public:
  const  data_type     datum;
  HashTableListElement * next;
  
  HashTableListElement (const data_type &d);
  HashTableListElement (const
                                  HashTableListElement<data_type> &
                                  );
  HashTableListElement ();
  // default destructor is ok  ~HashTableListElement ();
};

// type requirements:
// data_type needs the copy constructor and the equality relation ==.
// It must be different from size_t.

/* The contents of this hash table is not only accessible through the hash
   key, but all contained words are also contained in a sequence (I don't
   know yet if vector or slist). This sequence is there for fast searching
   through *all* contained words, no matter what their hash value is. The
   sequence should perhaps be sorted.
*/
template <class data_type>
class HashTable {
public:
  typedef size_t (*hash_function_type) (const data_type &);
  typedef bool   (*sequence_ordering) (const data_type *, const data_type *);
  
  HashTable(size_t size,
                      hash_function_type function,
                      sequence_ordering  less_than = 0);
  ~HashTable();

  static void set_default_hash_size(size_t);
  static void set_default_hash_function(hash_function_type);
  static void set_default_ordering(sequence_ordering);
  
  HashTable(); // uses default size and hash function and ordering;

  // Storing in a vector requires the copy constructor:
  HashTable(const HashTable<data_type> &);

  // insert datum if not already there;
  const data_type * insert (const data_type &);

  // return a pointer to the contained datum if there, or NULL otherwise
  const data_type * contains (const data_type &) const;

  // return a pointer to a datum with this hash key, if one exists, or NULL
  // otherwise. If the previous call to this method had the same hash key
  // argument and returned not NULL, then a pointer to the next datum with
  // the same hash key will be returned, or NULL if the previous datum was
  // the last one.
  const data_type * get_next (size_t);

  // return a pointer to the next datum in this hash table, mo matter what
  // key it has:
  const data_type * get_global_next (void);

  // reset the get_global_next_functionality: next time, it should return the
  // first datum:
  void reset_global_next (void);

  void remove (const data_type &);

  // return number of contained words:
  size_t size (void) const;

  /* No sorting required
  // sort according to sequence_ordering:
  void sort (void);
  */
private:
  static size_t default_hash_size; // size for default constructor
  static hash_function_type default_hash_function; // for default constructor
  static sequence_ordering  default_less_than; // for default constructor
  
  typedef HashTableListElement<data_type> list_element;

  MySlist<list_element> global_list;

  list_element **table;
  list_element *cached_element; // for get_next()
  size_t       cached_key;    // for get_next()

  MySlist<list_element>::iterator cached_global;
  //                                        for get_global_next
  
  size_t             hash_size;
  hash_function_type hash_function;
  sequence_ordering  less_than_function;
};
}
#include "cardwords_hashtable.icc"
#endif