/* 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
*/

// cardwords_fasthashkey.hh

// fasthash_key will be another wordkey

/* About CardWords_FastHashKey:
   As CardWords_WordKey and CardWords_Hashkey, CardWords_FastHashKey will be a
   key to a word(CardWords_String). Words containing the same letters in
   different orders will have the same key.

   CardWords_FastHashKey will be calculated the following way:
   Each Char gets a Key Value. All key values in a word will be added and a
   modulo division produces the hash key.

   CardWords_FastHashKey must be initialized with the hash table size, usualy
   a prime, and with the factor by which the key values differ.
   This factor will have the following meaning: If the factor is n, then a
   word consisting of n 'a'-s will have the same hash value as a word
   consisting of exactly 1 'b'.
*/
#ifndef CARDWORDS_FASTHASHKEY_HH
#define CARDWORDS_FASTHASHKEY_HH

#include "cardwords_string.hh"

class CardWords_FastHashKey {
public:
  CardWords_FastHashKey ();
  CardWords_FastHashKey (const CardWords_String &);
  CardWords_FastHashKey (const CardWords_FastHashKey &);
  ~CardWords_FastHashKey ();
  CardWords_FastHashKey & operator = (const CardWords_String &);
  CardWords_FastHashKey & operator = (const CardWords_FastHashKey &);

  CardWords_FastHashKey & operator += (CardWords_Char);
  CardWords_FastHashKey & operator += (const CardWords_String &);
  CardWords_FastHashKey & operator += (const CardWords_FastHashKey &);
  
  CardWords_FastHashKey & operator -= (CardWords_Char);
  CardWords_FastHashKey & operator -= (const CardWords_String &);
  CardWords_FastHashKey & operator -= (const CardWords_FastHashKey &);

  
  
  size_t hash(void);

  // calculate a hash value without an object instance:
  static size_t key_of (const CardWords_String &);

  // equal_key function for stl's hash_multiset:
  static bool equal_key (const CardWords_String &, const CardWords_String &);

  // setting the hashing function parameters:
  static void init (size_t hash_table_size, size_t char_keys_factor);

  // the < operator is for storing the hash values in a set:
  bool operator < (const CardWords_FastHashKey &) const;
  
private:

  static size_t noOfChars;
  static size_t hashSize;

  static size_t * hashTerms;

  size_t             hashVal;
public:
  // getting the hash_table_size:
  static size_t get_size(void) {return hashSize;}
};

inline
CardWords_FastHashKey::CardWords_FastHashKey ()
  : hashVal(0)
{}

inline CardWords_FastHashKey &
CardWords_FastHashKey::operator += (CardWords_Char k)
{
  hashVal += hashTerms [k.internal_no()];
  if (hashVal >= hashSize) {
    hashVal -= hashSize;
  }
  return *this;
}

inline CardWords_FastHashKey &
CardWords_FastHashKey::operator += (const CardWords_String & s)
{
  const size_t len = s.length();
  for (size_t i = 0; i < len; ++i) {
    (*this) += s[i];
  }
  return *this;
}

inline CardWords_FastHashKey &
CardWords_FastHashKey::operator += (const CardWords_FastHashKey &other)
{
  hashVal += other.hashVal;
  if (hashVal >= hashSize) {
    hashVal -= hashSize;
  }
  return *this;
}

inline
CardWords_FastHashKey::CardWords_FastHashKey (const CardWords_String &other)
  : hashVal(0)
{
  (*this) += other;
}

inline
CardWords_FastHashKey::~CardWords_FastHashKey ()
{}

inline
CardWords_FastHashKey &
CardWords_FastHashKey::operator = (const CardWords_String &other)
{
  hashVal = 0;
  return (*this)+= other;
}

inline
CardWords_FastHashKey &
CardWords_FastHashKey::operator -= (CardWords_Char k)
{
  hashVal -= hashTerms [k.internal_no()];
  if (hashVal > hashSize) { // underflow
    hashVal += hashSize;
  }
  return *this;
}

inline
CardWords_FastHashKey &
CardWords_FastHashKey::operator -= (const CardWords_String &s)
{
  const size_t len = s.length();
  for (size_t i = 0; i < len; ++i) {
    (*this) -= s[i];
  }
  return *this;
}

inline CardWords_FastHashKey &
CardWords_FastHashKey::operator -= (const CardWords_FastHashKey &other)
{
  hashVal -= other.hashVal;
  if (hashVal > hashSize) { // underflow
    hashVal += hashSize;
  }
  return *this;
}

inline size_t CardWords_FastHashKey::hash(void)
{
  return hashVal;
}

inline
void
CardWords_FastHashKey::init (size_t hash_table_size,
                             size_t diff_factor)
{
  assert (hashSize == 0);
  assert (hash_table_size > 1);
  hashSize = hash_table_size;
  noOfChars = CardWords_Char::noOfChars();
  hashTerms = new size_t[noOfChars];

  assert (noOfChars > 1); //only blanko makes no sense
  hashTerms[1] = 1;
  for (size_t i = 2; i < noOfChars; ++i) {
    hashTerms[i] = (hashTerms[i-1] * diff_factor) % hash_table_size;
  }
}

// calculate a hash value without an object instance:
inline size_t CardWords_FastHashKey::key_of (const CardWords_String &s)
{
  const size_t len = s.length();
  size_t value = 0;
  for (size_t i = 0; i < len; ++i) {
    value += hashTerms[s[i].internal_no()];
  }
  return value % hashSize;
}

inline
CardWords_FastHashKey::
CardWords_FastHashKey (const CardWords_FastHashKey &other)
{
  hashVal = other.hashVal;
}

inline CardWords_FastHashKey &
CardWords_FastHashKey::operator = (const CardWords_FastHashKey &other)
{
  hashVal = other.hashVal;
  return *this;
}

inline
bool
CardWords_FastHashKey::operator < (const CardWords_FastHashKey &other) const
{
  return hashVal < other.hashVal;
}

// equal_key function for stl's hash_multiset:
// comparing two Strings for equality regarding the char occurrences
inline bool CardWords_FastHashKey::equal_key (const CardWords_String &s1,
                                            const CardWords_String &s2)
{
  size_t len = s1.length();
  if (len != s2.length()) {
    return false;
  }
  //  size_t * occurrences = new size_t [noOfChars];
  size_t index;
/*#define NEW_SIZE_T_SETS_TO_0
  #ifndef NEW_SIZE_T_SETS_TO_0
  for (index = 0; index < noOfChars; ++index) {
  occurrences[index] = 0;
  }
  #endif*/
  for (index = 0; index < len; ++index) {
    if(s1[index]!=s2[index]) {
      return false;
    }
  }
  return true;
  /*  
  for (index = 0; index < len; ++index) {
    if (occurrences[s1[index].internal_no()]-- == 0) {
      delete [] occurrences;
      return false;
    }
  }
  delete[]occurrences;
  return true;
  */
}
#endif