/* This file is part of cardwords
   (c) 1998 1999 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>

// CardWords_HashTable defines a hash table suitable for CardWords_Strings.

// This is a type required by the hash table:
template <class data_type>
struct CardWords_HashTableListElement {
public:
  const  data_type     datum;
  CardWords_HashTableListElement * next;
  
  CardWords_HashTableListElement (const data_type &d);
  CardWords_HashTableListElement (const
                                  CardWords_HashTableListElement<data_type> &
                                  );
  CardWords_HashTableListElement () : next(0){}
  ~CardWords_HashTableListElement () {}
};
template <class data_type>
inline
CardWords_HashTableListElement<data_type>::CardWords_HashTableListElement
(const data_type &d)
  : datum(d),
    next(0)
{
}
template <class data_type>
inline
CardWords_HashTableListElement<data_type>::CardWords_HashTableListElement
(const CardWords_HashTableListElement<data_type> &other)
  : datum(other.datum),
    next(0)
{
}

// 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 CardWords_HashTable {
public:
  typedef size_t (*hash_function_type) (const data_type &);
  typedef bool   (*sequence_ordering) (const data_type *, const data_type *);
  
  CardWords_HashTable(size_t size,
                      hash_function_type function,
                      sequence_ordering  less_than = 0);
  ~CardWords_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);
  
  CardWords_HashTable(); // uses default size and hash function and ordering;

  // Storing in a vector requires the copy constructor:
  CardWords_HashTable(const CardWords_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 CardWords_HashTableListElement<data_type> list_element;

  CardWords_MySlist<list_element> global_list;

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

  CardWords_MySlist<list_element>::iterator cached_global;
  //                                        for get_global_next
  
  size_t             hash_size;
  hash_function_type hash_function;
  sequence_ordering  less_than_function;
};

template <class data_type>
inline
CardWords_HashTable<data_type>::
CardWords_HashTable(size_t size,

                    CardWords_HashTable<data_type>::hash_function_type
                    function,

                    CardWords_HashTable<data_type>::sequence_ordering
                    less_than = 0)
{
  hash_size = size;
  hash_function = function;
  less_than_function = less_than;
  
  cached_element = 0;
  cached_key = UINT_MAX; // numeric_limits<size_t>::max();
  cached_global = global_list.begin();
  
  table = new (list_element *) [hash_size];
  for (size_t index = 0; index < hash_size; ++index) {
    table[index] = 0;
  }
}

// Storing in a vector requires the copy constructor. Note However, that we do
// *not* produce a copy, but the same as would be produced by the explicit
// constructor above, with the same arguments.
template <class data_type>
inline
CardWords_HashTable<data_type>::CardWords_HashTable
(const CardWords_HashTable<data_type> &other)
{
  hash_size = other.hash_size;
  hash_function = other.hash_function;
  less_than_function = other.less_than_function;
  
  cached_element = 0;
  cached_key = UINT_MAX; //numeric_limits<size_t>::max();
  cached_global = global_list.begin();
  
  table = new (list_element *) [hash_size];
  for (size_t index = 0; index < hash_size; ++index) {
    table[index] = 0;
  }
}

template <class data_type>
inline
CardWords_HashTable<data_type>::~CardWords_HashTable()
{
  delete [] table;
  // global_list is destroyed automatically
}

template <class data_type>
inline void
CardWords_HashTable<data_type>::set_default_hash_size(size_t size)
{
  default_hash_size = size;
}
template <class data_type>
inline void
CardWords_HashTable<data_type>::
set_default_hash_function(CardWords_HashTable<data_type>::
                          hash_function_type f)
{
  default_hash_function = f;
}
template <class data_type>
inline void
CardWords_HashTable<data_type>::
set_default_ordering(CardWords_HashTable<data_type>::sequence_ordering o)
{
  default_less_than = o;
}

template <class data_type>
inline
CardWords_HashTable<data_type>::CardWords_HashTable() // uses default size and
  //                                                     hash function
{
  hash_size = default_hash_size;
  hash_function = default_hash_function;
  less_than_function = default_less_than;
  
  cached_element = 0;
  cached_key = UINT_MAX; //numeric_limits<size_t>::max();
  cached_global = global_list.begin();
  
  table = new (list_element *) [hash_size];
  for (size_t index = 0; index < hash_size; ++index) {
    table[index] = 0;
  }
}

// insert datum if not already there:
template <class data_type>
inline  const data_type *
CardWords_HashTable<data_type>::insert (const data_type &d)
{
  // test if it is already there:
  size_t key = hash_function(d);
  list_element * element;
  list_element ** last_next;
  for (element = *(last_next = &(table [key])); // element = table[key];
       element != 0;
       element = *(last_next = &(element->next)) // element = element->next;
      ) {
    if ( d == element->datum ) {
       // d is already there
      return &(element->datum);
    }
  }
  // d is not yet contained, so insert it:
  global_list.push_front(d);
  *last_next = &(*global_list.begin());
  cached_global = global_list.begin();
  return &((*global_list.begin()).datum);
}

// return a pointer to the contained datum if there, or NULL otherwise
template <class data_type>
inline const data_type *
CardWords_HashTable<data_type>::contains (const data_type &d) const
{
  size_t key = hash_function(d);
  list_element * element;
  for (element = table [key];
       element != 0;
       element = element->next) {
    if ( d == element->datum ) {
      // d is in the list
      return &(element->datum);
    }
  }
  // d is not contained:
  return 0;
}

// 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.
template <class data_type>
inline     const data_type   *
CardWords_HashTable<data_type>::get_next (size_t key)
{
  if (key == cached_key && cached_element != 0) {
    cached_element = cached_element->next;
    if (cached_element == 0) return 0;
    return &(cached_element->datum);
  }
  cached_key = key;
  cached_element = table[key];
  if (cached_element == 0) return 0;
  return &(cached_element->datum);
}
  
template <class data_type>
inline void
CardWords_HashTable<data_type>::remove (const data_type & d)
{
  // test if d is in the list at all:
  size_t key = hash_function(d);
  list_element * element;
  list_element ** last_next;
  for (element = *(last_next = &(table [key])); // element = table[key];
       element != 0;
       element = *(last_next = &(element->next)) // element = element->next;
      ) {
    if ( d == element->datum ) {
      // d is in the list.
      // remove it from the hash_table:
      *last_next = element->next;
      // remove it from the global list:
      // We do not know the iterator of element.
      // This removal can take a long time.
      CardWords_MySlist<list_element>::iterator iter;
      CardWords_MySlist<list_element>::iterator last_iter =
        (                                              global_list.begin() );
      
      for (iter = global_list.begin();
#ifdef DEBUG
           iter != global_list.end() // this should not be reached!
             //                         We cheched that it is contained.
#endif
             ;
           last_iter = iter++) {
        if ((*iter).datum == d) { // we found the right iterator
          if (iter == global_list.begin()) {
            global_list.pop_front();
          }
          else {
            global_list.erase_after(last_iter);
          }
          cached_global = global_list.begin();
          return; // nothing more to do
        }
        // search further for the right iterator
      }
      // such a pity, we are still here. That means we found an element in the
      // hash table, but not in the global list. This is a bug.
      assert (0);
      exit (1);
    }
    else
      // Remember its ok to be here!
      continue;
  }
}

// return number of contained words:
template <class data_type>
inline size_t
CardWords_HashTable<data_type>::size (void) const
{
  return global_list.size();
}

/* No sorting required
// sort according to sequence_ordering:
template <class data_type>
inline void
CardWords_HashTable<data_type>::sort (void)
{
  global_list.sort(less_than_function);
  cached_global = global_list.begin();
}
*/

// return a pointer to the next datum in this hash table, mo matter what
// key it has:
template <class data_type>
inline const data_type *
CardWords_HashTable<data_type>::get_global_next (void)
{
  if (cached_global == global_list.end()) {
    cached_global = global_list.begin();
    return static_cast<const data_type *>(0);
  }
  return &((*cached_global++).datum);
}

// reset the get_global_next_functionality: next time, it should return the
// first datum:
template <class data_type>
inline void
CardWords_HashTable<data_type>::reset_global_next (void)
{
  cached_global = global_list.begin();
}
#endif