//
// Copyright (C) 1991 Texas Instruments Incorporated.
//
// Permission is granted to any individual or institution to use, copy, modify,
// and distribute this software, provided that this complete copyright and
// permission notice is maintained, intact, in all copies and supporting
// documentation.
//
// Texas Instruments Incorporated provides this software "as is" without
// express or implied warranty.
//
// Created: MBN 05/16/89 -- Initial design and implementation
// Updated: MBN 06/01/89 -- Implemented the notion of current position.
// Updated: MBN 06/06/89 -- Separated and derived Hash_Table from Base_Hash
//                          to reduce replication of common code.
// Updated: LGO 06/20/89 -- Use correct default hash and compare for char* keys
// Updated: LGO 07/03/89 -- Fix resize bug in the put method
// Updated: MBN 08/19/89 -- Changed template usage
// Updated: MBN 09/20/89 -- Added conditional exception handling
// Updated: MBN 09/26/89 -- Added method to return key at current position
// Updated: LGO 10/02/89 -- Substituted Tkey and Tval for T1 and T2
// Updated: MBN 10/07/89 -- Changed get() method to match Association + Symbol
// Updated: MBN 10/11/89 -- Fixed operator==() for tables with different bucket
//                          count but same elements -- tables grew separately
// Updated: MBN 10/12/89 -- Changed "current_position" to "curpos", added
//                          current_position() method for Iterator<Type>, and
//                          converted state from bit set to bit set/get macros
// Updated: LGO 10/16/89 -- Re-write operator<< to be const
// Updated: MBN 10/19/89 -- Made compare_keys and compare_values_s slots static
//                          and added optional argument to set_compare methods
// Updated: MBN 12/15/89 -- Fixed no-dereferenced pointer-to-function in find()
// Updated: LGO 02/07/90 -- Change resize to not use a tempoorary for key and
//                          value.  Avoids extra constructor and destructor
//                          calls.
// Updated: MBN 02/23/90 -- Changed size arguments from long to unsigned long
// Updated: MJF 06/30/90 -- Added base class name to constructor initializer
//
// The  Hash_Table<Tkey,Tval> class is  publicly  derived from  the  Hash_Table
// class and implements hash tables  of user-specified types  for both the  key
// and the  value.   This is accompilshed  by    using  the parameterized  type
// capability  of C++.   The Hash Table class is  dynamic in nature.  It's size
// (ie.  the number of buckets in the table) is always some prime number.  Each
// bucket holds 8 items.  No wholes are  left in a bucket;  if a key/value pair
// is removed   from the middle of  a  bucket, following  entries are moved up.
// When a  hash  on  a key ends up   in a bucket that  is  full, the  table  is
// enlarged.  The Hash_Table<Tkey,Tval> class  is parameterized over two types.
// The first type Tkey specifies the type of the key,  and the second type Tval
// specifies the type of the value.
//
// The private  data section of  a Hash  Table  has a  slot that points  to the
// physical memory allocated for some prime number of buckets each of which has
// memory allocated for 8 items.  The number of buckets  currently in the table
// is accessed by an index into a global table of selected prime numbers.  This
// global table eliminates the somewhat  expensive runtime computation of prime
// numbers.  The table consists of  prime numbers where  the difference between
// any two successive entries gets progressively larger as you move through the
// table.  The specified range of primes  results in an arbitrary limitation of
// 2^22 entries in a single hash table.
//
// When a hash on a key ends up in a bucket that is full, the table is enlarged
// to the next prime number of buckets or to the prime number  that is at least
// large enough  to  accommodate a user-specified  growth ratio. The entries in
// the  buckets are  then rehashed  into   the new  table.   Selection  of   an
// appropriate   hash function is crucial  to  uniform distribution through the
// table. The result of the hash function is  then divided by the  prime number
// of buckets to accomplish this. A user-supplied  function should do something
// similar.
//
// Other items in the private data section (inherited from Base Hash) include a
// pointer to a byte vector (that is, unsigned char) that  maintains a count of
// the number of entries in each bucket, a growth ratio that can be used to set
// a growth rate percentage when necessary,  an entry count,  an index into the
// prime number table that indicates the number of  buckets in the table, and a
// current position  that maintains the bucket number and index into the bucket
// of the last hash operation.
//
// Three other slots contain a pointer to a key  compare function, a pointer to
// a value compare  function, and a pointer to  a  hash function, respectively.
// The compare functions are  used  in equality  operations on key/value items.
// The default compare function is the  built-in == operator.  The default hash
// function  is either a  simple 32 bit  value if sizeof(Tkey)   is 4,  that is
// shifted left three   bits  with the result  modulo  the  number   of buckets
// determining the  hash. This is  ideal when Tkey is a  pointer to  a key.  If
// sizeof(Tkey) is greater than 4, then the 32 bit value used  is the result of
// exclusive-oring successive 32-bit values  for the  length of Tkey,  and then
// applying the same bit shift and modulo operation as before.
//
// Three different constructors are provided.   The first constructor  takes no
// arguments and  creates a  hash table with  three buckets that  can contain a
// total of 24 items.   The second constructor  accepts an integer argument and
// creates a hash table of some prime number of buckets that  can accomodate at
// least the specified number of items.  Finally, the third constructor takes a
// single argument consisting of a reference to a Hash Table and duplicates its
// size and contents.
//
// The  Hash Table  class implements the notion  of a current position. This is
// useful for  iterating through    the  table of  hashed values.   The current
// position is maintained in a a long that is accessed via several preprocessor
// macros to select bits. The first bit field is of length 24 and maintains the
// bucket  (prime) number last  used.  The second bit field is  of length 8 and
// maintains the index of the last item in a  bucket. Methods to reset, move to
// the next and previous, find, and get  the value at  the current position are
// provided.
//
// Methods are provided to put a value based on some  key into the table, get a
// value based on some key from the  table,  remove  a value  based on some key
// from the table, and to clear all values from the table entirely. The output,
// assignment, and equality operators are overloaded for hash  tables. Finally,
// two functions to  set the hash  and compare functions  for an instance of  a
// hash table, accessor methods to get the bucket and total entry count,  and a
// method to set the growth ratio are also available.

#ifndef HASH_TABLEH				// If no Hash Table class,
#define HASH_TABLEH				// define it

#ifndef BASE_HASH_TABLEH			// If no Base Hash class,
#include <cool/Base_Hash.h>				// define it
#endif	

template <class Tkey, class Tval> Hash_Table {
  struct Hash_Table<Tkey,Tval>_pair {		// Structure for hash/value
    Tkey key;
    Tval value;
  };

  struct Hash_Table<Tkey,Tval>_bucket {		// Structure for bucket
    struct Hash_Table<Tkey,Tval>_pair data[BUCKET_SIZE];
  };

  typedef Boolean
    (*Hash_Table<Tkey,Tval>_Key_Compare) (const Tkey&, const Tkey&);
  typedef Boolean
    (*Hash_Table<Tkey,Tval>_Value_Compare) (const Tval&, const Tval&);
  typedef unsigned long (*Hash_Table<Tkey,Tval>_Hash) (const Tkey&);
}

template <class Tkey, class Tval>
class Hash_Table<Tkey,Tval> : public Hash_Table {
protected:
  Hash_Table<Tkey,Tval>_bucket* table;		// Pointer to key/value buckets
  Hash_Table<Tkey,Tval>_Hash h_function;		// Pointer to hash function
  static Hash_Table<Tkey,Tval>_Key_Compare compare_keys_s; // Key compare
  static Hash_Table<Tkey,Tval>_Value_Compare compare_values_s; // Value compare
  friend Boolean Hash_Table<Tkey,Tval>_keys_equal (const Tkey&, const Tkey&);
  friend Boolean Hash_Table<Tkey,Tval>_values_equal (const Tval&, const Tval&);
  friend unsigned long Hash_Table<Tkey,Tval>_default_hash (const Tkey& key);

public:
  Hash_Table<Tkey,Tval> ();			// Hash table of default size
  Hash_Table<Tkey,Tval> (unsigned long);	// Hash table for at least size
  Hash_Table<Tkey,Tval> (const Hash_Table<Tkey,Tval>&); // Hash table reference
  ~Hash_Table<Tkey,Tval>();			// Destructor

  Boolean put (const Tkey&, CONST Tval&);       // Hash key/value
  Boolean get (const Tkey&, Tval&);		// Get associated value for key
  Boolean get_key (const Tval&, Tkey&);		// Get associated key for value
  Boolean remove (const Tkey&);			// Remove key/value from table
  void resize (long);				// Resize for at least count
  
  Boolean find (const Tkey&);			// Set current position
  const Tkey& key ();				// Get key at current position
  Boolean remove ();				// Remove key/value at curpos
  const Tval& value ();				// value at current position

  inline friend ostream& operator<< (ostream&, const Hash_Table<Tkey,Tval>*);
  friend ostream& operator<< (ostream&, const Hash_Table<Tkey,Tval>&);
  Hash_Table<Tkey,Tval>& operator= (const Hash_Table<Tkey,Tval>&);

  Boolean operator== (const Hash_Table<Tkey,Tval>&); // is equal
  inline Boolean operator!= (const Hash_Table<Tkey,Tval>&); // is not eq

  void set_hash (Hash_Table<Tkey,Tval>_Hash); // Set hash function
  void set_key_compare (Hash_Table<Tkey,Tval>_Key_Compare = NULL); 
  void set_value_compare (Hash_Table<Tkey,Tval>_Value_Compare = NULL);
};

MACRO Default_Hash_Compare(KeyT, ValueT) {
#if ISSAME(KeyT, charP, String, Gen_String)
#ifndef CHARH
#include <cool/char.h>
#endif
Boolean Hash_Table<KeyT,ValueT>_keys_equal (const KeyT& v1, const KeyT& v2) {
  return !strcmp (v1, v2);
}
unsigned long Hash_Table<KeyT,ValueT>_default_hash (const KeyT& key) {
  return sxhash(key);
}
#else

// are_keys_equal -- Compares two keys using the user supplied comparison
//                   function or the built-in operator== otherwise
// Input:            References to two keys
// Output:           TRUE/FALSE

Boolean Hash_Table<KeyT,ValueT>_keys_equal (const KeyT& k1, const KeyT& k2) {
  return (k1 == k2);
}

// default_hash -- Implements the hash mechanism 
// Input:          Reference to a key
// Output:         Hash value (0-relative index into based table)

unsigned long Hash_Table<KeyT,ValueT>_default_hash (const KeyT& key) {
  if (sizeof (KeyT) <= 4)
    return (((unsigned long) key) >> 2);
  else {
    int nlongs = sizeof(KeyT)/sizeof(long);
    register CONST unsigned long* objp = (CONST unsigned long*) &key;
    register unsigned long hash = *objp++;
    while (--nlongs > 0) hash ^= *objp++;
    return hash &= 0x7fffffffL;			// Make sure bit 32 is zero
  }
}
#endif

}

template <class Tkey, class Tval> Hash_Table {
  Default_Hash_Compare(Tkey, Tval);
}

// are_values_equal -- Compares values using the default operator == function
// Input:              References to two values
// Output:             TRUE/FALSE

template <class Tkey, class Tval> Hash_Table {
  Boolean Hash_Table<Tkey,Tval>_values_equal (const Tval& v1, const Tval& v2) {
    return ((v1 == v2) ? TRUE : FALSE);
  }
}


// Hash_Table -- Simple constructor with no arguments that creates a hash
//               table object with the minimal prime number of buckets and
//               uses the default hash function.
// Input:        None
// Output:       None

template <class Tkey, class Tval> 
Hash_Table<Tkey,Tval>::Hash_Table<Tkey,Tval> () {
  long prime = hash_primes[this->current_bucket]; // Get prime number 
  this->table = (Hash_Table<Tkey,Tval>_bucket*)new Hash_Table<Tkey,Tval>_bucket[prime]; 
  this->h_function = &Hash_Table<Tkey,Tval>_default_hash;
  if (this->compare_keys_s == NULL)		// If no value assigned yet
    this->compare_keys_s = &Hash_Table<Tkey,Tval>_keys_equal;
  if (this->compare_values_s == NULL)		// If no value assigned yet
    this->compare_values_s = &Hash_Table<Tkey,Tval>_values_equal;
}


// Hash_Table -- Simple constructor with one argument that creates a hash
//               table object with the minimal prime number of buckets that
//               holds some user-supplied number of items and uses the default
//               hash function.
// Input:        Minimal number of items table must hold
// Output:       None

template <class Tkey, class Tval> 
Hash_Table<Tkey,Tval>::Hash_Table<Tkey,Tval> (unsigned long n)
#ifdef __cplusplus
 : Hash_Table(n)
#else
 : (n)
#endif
{
  long prime = hash_primes[this->current_bucket]; // Get prime number 
  this->table = (Hash_Table<Tkey,Tval>_bucket*)new Hash_Table<Tkey,Tval>_bucket[prime]; 
  this->h_function = &Hash_Table<Tkey,Tval>_default_hash;
  if (this->compare_keys_s == NULL)		// If no value assigned yet
    this->compare_keys_s = &Hash_Table<Tkey,Tval>_keys_equal;
  if (this->compare_values_s == NULL)		// If no value assigned yet
    this->compare_values_s = &Hash_Table<Tkey,Tval>_values_equal;
}


// Hash_Table -- Constructor that takes a reference to an existing hash table
//               and duplicates both its size and contents
// Input:        Reference to hash table object
// Output:       None

template <class Tkey, class Tval> 
Hash_Table<Tkey,Tval>::Hash_Table<Tkey,Tval> (const Hash_Table<Tkey,Tval>& h)
#ifdef __cplusplus
 : Hash_Table(h)
#else
 : (h)
#endif
{
  long prime = hash_primes[this->current_bucket]; // Get prime number 
  this->table = (Hash_Table<Tkey,Tval>_bucket*)new Hash_Table<Tkey,Tval>_bucket[prime]; 
  for (long i = 0; i < prime; i++) {		// For each bucket count
    for (int j = 0; j < h.items_in_buckets[i]; j++) { // For items in bucket
      this->table[i].data[j].key = h.table[i].data[j].key; // Copy key 
      this->table[i].data[j].value = h.table[i].data[j].value; // Copy value
    }
  }
  this->h_function = h.h_function;		// Use the same hash function
  this->compare_keys_s = h.compare_keys_s;	// Use same compare function
  this->compare_values_s = h.compare_values_s;	// Use same compare function
}


// ~Hash_Table -- Destructor for the Hash_Table class
// Input:         this*
// Output:        None

template <class Tkey, class Tval> 
Hash_Table<Tkey,Tval>::~Hash_Table<Tkey,Tval> () {
  delete this->table;				// Free key/value storage
}


// find -- Find key/value in hash table
// Input:  Key searching for
// Output: TRUE/FALSE; current_position updated

template <class Tkey, class Tval> 
Boolean Hash_Table<Tkey,Tval>::find (const Tkey& key) {
  long prime = hash_primes[this->current_bucket]; // Prime number of buckets
  unsigned long hash = ((*this->h_function)(key)) % prime; // Get hash value 
  for (int i = 0; i < this->items_in_buckets[hash]; i++) { // For each entry
    if ((*this->compare_keys_s)(key,this->table[hash].data[i].key) == TRUE){
      this->curpos = SET_BUCKET_NUMBER(hash);	// Set bucket number
      this->curpos |= SET_BUCKET_INDEX(i);	// Set bucket index
      return TRUE;				// Return success
    }
  }
  return FALSE;
}


// key --  Return key at current position
// Input:  None
// Output: Reference to key at current position

template <class Tkey, class Tval> 
const Tkey& Hash_Table<Tkey,Tval>::key () {
  if (this->curpos != INVALID) {		// If valid current position
    unsigned long hash = BUCKET_NUMBER(this->curpos); // Get bucket number
    long index = BUCKET_INDEX(this->curpos);	      // Get index in bucket
    return (this->table[hash].data[index].key);	      // Return value
  }
  else						// Else 
    this->key_error (#Tkey,#Tval);		// Raise exception
}


// value -- Return value at current position
// Input:   None
// Output:  Reference to value at current position

template <class Tkey, class Tval> 
const Tval& Hash_Table<Tkey,Tval>::value () {
  if (this->curpos != INVALID) {		// If valid current position
    unsigned long hash = BUCKET_NUMBER(this->curpos); // Get bucket number
    long index = BUCKET_INDEX(this->curpos);	      // Get index in bucket
    return (this->table[hash].data[index].value);     // Return value
  }
  else						// Else 
    this->value_error (#Tkey,#Tval);		// Raise exception
}


// put -- Hash key/value pair into table if not already there
// Input: this*, key, value
// Output:TRUE when key is new, else FALSE

template <class T1, class T2> 
Boolean Hash_Table<T1,T2>::put (const T1& key, CONST T2& value) {
 retry:
  long prime = hash_primes[this->current_bucket]; // Prime number of buckets
  unsigned long hash = ((*this->h_function)(key)) % prime; // Get hash value
  int index = this->items_in_buckets[hash];
  this->curpos = SET_BUCKET_NUMBER(hash);	// Save bucket number
  for (int i = 0; i < index; i++)		// For each item
    if ((*this->compare_keys_s)(key,this->table[hash].data[i].key) == TRUE) {
      this->table[hash].data[i].value = value;	// Already there, update value
      this->curpos |= SET_BUCKET_INDEX(i);	// Update bucket index position
      return FALSE;				// And return found
    }
  if (index >= BUCKET_SIZE) {			// If bucket is full
    this->resize (hash_primes[this->current_bucket+1]*BUCKET_SIZE); // Grow
    goto retry;
  }
  this->table[hash].data[index].key = key;
  this->table[hash].data[index].value = value;
  this->entry_count++;				// Increment table entry count
  this->curpos |= SET_BUCKET_INDEX(index);	// Update bucket index position
  this->items_in_buckets[hash]++;		// Increment bucket item count
  return TRUE;					// Indicate new
}


// get -- Get a value based on a key from the table
// Input: this*, reference to a key
// Output:Value for key/value pair from table
//        Returns TRUE when entry is found, else false

template <class Tkey, class Tval> 
Boolean Hash_Table<Tkey,Tval>::get (const Tkey& key, Tval& value) {
  Boolean result = FALSE;			 // Assume we don't find entry
  long prime = hash_primes[this->current_bucket]; // Prime number of buckets
  unsigned long hash = ((*this->h_function)(key)) % prime; // Get hash value
  for (int i = 0; i < this->items_in_buckets[hash]; i++) { // For each entry
    if ((*this->compare_keys_s)(key,this->table[hash].data[i].key) == TRUE) {
      this->curpos = SET_BUCKET_NUMBER(hash);	// Save bucket number
      this->curpos|= SET_BUCKET_INDEX(i);	// Save index into bucket
      value = this->table[hash].data[i].value;	// Copy value in table
      result = TRUE;				// Inidicate success
      break;					// Break out of loop
    }
  }
  return result;				// Return success/failure
}


// get_key --Get a key based on a value from the table
// Input:    this*, reference to a value, reference to place to store key
// Output:   TRUE if found with value in reference argument, else FALSE

template <class Tkey, class Tval> 
Boolean Hash_Table<Tkey,Tval>::get_key (const Tval& value, Tkey& key) {
  long prime = hash_primes[this->current_bucket]; // Prime number of buckets
  for (long i = 0; i < prime; i++)		  // For each bucket, search
    for (int j = 0; j < this->items_in_buckets[i]; j++) // For item in bucket
      if ((*this->compare_values_s)(value,this->table[i].data[j].value)==TRUE){
	this->curpos = SET_BUCKET_NUMBER(i);	// Set bucket number
	this->curpos|= SET_BUCKET_INDEX(j);	// Set index into bucket
	key = this->table[i].data[j].key;	// Return key for value
	return TRUE;				// Indicate success
      }
  return FALSE;					// Indicate failure
}


// remove -- Remove element at current position from the set
// Input:    this*
// Output:   TRUE/FALSE

template <class Tkey, class Tval> 
Boolean Hash_Table<Tkey,Tval>::remove () {
  if (this->curpos != INVALID) {		// If valid current position
    unsigned long hash = BUCKET_NUMBER(this->curpos); // Get bucket number
    long index = BUCKET_INDEX(this->curpos);	// Get index in bucket
    int count = this->items_in_buckets[hash];	// Number of items in bucket
    this->table[hash].data[index].key = this->table[hash].data[count-1].key;
    this->table[hash].data[index].value = this->table[hash].data[count-1].value;
    this->entry_count--;			// Decrement table entry count
    this->items_in_buckets[hash]--;		// Decrement bucket item count
    if (this->items_in_buckets[hash]) {		// If any more items in bucket
      this->curpos = SET_BUCKET_NUMBER(hash);	// Save bucket number
      this->curpos |= SET_BUCKET_INDEX(this->items_in_buckets[hash]-1);
    }
    else
      this->curpos = INVALID;			// Else invalidate marker
    return TRUE;				// Return success
  }
  this->remove_error (#Tkey, #Tval);		// Raise exception
  return FALSE;					// Return failure
}


// remove -- Remove a value based on a key from the table
// Input:    this*, reference to a key
// Output:   TRUE/FALSE

template <class Tkey, class Tval> 
Boolean Hash_Table<Tkey,Tval>::remove (const Tkey& key) {
  long prime = hash_primes[this->current_bucket]; // Prime number of buckets
  unsigned long hash = ((*this->h_function)(key)) % prime; // Get hash value
  int count = this->items_in_buckets[hash];	// Number of items in bucket
  for (int i = 0; i < count; i++) {		// For each entry in bucket
    if ((*this->compare_keys_s)(key,this->table[hash].data[i].key) == TRUE) {
      this->table[hash].data[i].key = this->table[hash].data[count-1].key;
      this->table[hash].data[i].value = this->table[hash].data[count-1].value;
      this->entry_count--;			// Decrement table entry count
      this->items_in_buckets[hash]--;		// Decrement bucket item count
      if (this->items_in_buckets[hash]) {	// If any more items in bucket
	this->curpos = SET_BUCKET_NUMBER(hash);	// Save bucket number
	this->curpos |= SET_BUCKET_INDEX(this->items_in_buckets[hash]-1);
      }
      else
	this->curpos = INVALID;			// Else invalidate marker
      return TRUE;
    }
  }
  return FALSE;					// Return failure flag
}


// resize -- Resize a hash table object to hold at least some number items
// Input:    this*, minimum number of items to hold
// Output:   None

template <class Tkey, class Tval> 
void Hash_Table<Tkey,Tval>::resize (long n) {
#if ERROR_CHECKING
  if (n < 0)					// If invalid size
    this->resize_error (#Tkey, #Tval, n);	// Raise exception
#endif
  Hash_Table<Tkey,Tval>_bucket* t2;		// Temporary variable
  long old_prime = hash_primes[this->current_bucket]; // Get prime number 
  while (hash_primes[this->current_bucket]*BUCKET_SIZE < n) // Find prime big
    this->current_bucket++;		        // ... enough for number items
  if (this->growth_ratio != 0.0) {		// If a growth ratio is set
    int new_size = int((old_prime * BUCKET_SIZE) * (1.0 + this->growth_ratio));
    if (new_size > n)
      while (hash_primes[this->current_bucket]*BUCKET_SIZE < new_size)
	this->current_bucket++;		        // Enough size for growth ratio
  }
 retry:
  long new_prime = hash_primes[this->current_bucket];// Get prime number 
  unsigned char* t1 = new unsigned char[new_prime];  // Counts items in buckets
  for (long i = 0; i < new_prime; i++)		// For each bucket count
    t1[i] = 0;					// Initialize to zero
  // NOTE: We should use the overloaded operator new to construct only
  //       the new buckets, and use memcpy instead of operator= for copying
  t2 = (Hash_Table<Tkey,Tval>_bucket*)new Hash_Table<Tkey,Tval>_bucket[new_prime]; 
  for (i = 0; i < old_prime; i++) {		// For each bucket count
    Hash_Table<Tkey,Tval>_pair* data = this->table[i].data;
    for (int j = 0; j < this->items_in_buckets[i]; j++) { // For each item
      unsigned long hash = ((*this->h_function)(data[j].key)) % new_prime;
      if (t1[hash] == BUCKET_SIZE) {		// Overflow bucket -- resize
	delete t1;				// Delete allocated storage
	delete t2;				// Delete allocated storage
	this->current_bucket++;			// Increment bucket count
	goto retry;				// Go retry again
      }
      t2[hash].data[t1[hash]].key = data[j].key; // Copy key into new table
      t2[hash].data[t1[hash]].value = data[j].value;//Copy value into new table
      t1[hash]++;				// Increment bucket item count
    }
  }
  delete this->items_in_buckets;		// Free up old storage
  delete this->table;				// Free up old storage
  this->items_in_buckets = t1;			// Point to new item count
  this->table = t2;				// Point to new buckets
  this->curpos = INVALID;			// Invalidate current position
}

// operator<< -- Overload the output operator to provide a crude print
//               capability for hash table objects
// Input:        ostream reference, hash table pointer
// Output:       None

template <class Tkey, class Tval> Hash_Table {
inline ostream& operator<< (ostream& os, const Hash_Table<Tkey,Tval>* h) {
  return operator<< (os, *h);
}
}


// operator<< -- Overload the output operator to provide a crude print
//               capability for hash table objects
// Input:        ostream reference, hash table reference
// Output:       None

template <class Tkey, class Tval> Hash_Table {
ostream& operator<< (ostream& os, const Hash_Table<Tkey,Tval>& h) {
  for (long i = 0; i < h.get_bucket_count(); i++) { // For each bucket
    for (int j = 0; j < h.get_count_in_bucket(i); j++) { // For each key/pair
      os << "(" << h.table[i].data[j].key;	     // Output the key
      os << "," << h.table[i].data[j].value;	     // Output the value
      os << ")\n";				     // And a newline
    }
  }
  return os;					// Return refererence to stream
}
}


// Operator= -- Assignment of one hash table to another duplicating size and
//              contents and returning old storage
// Input:       Reference to hash table object
// Output:      Reference to new hash table object

template <class Tkey, class Tval> 
Hash_Table<Tkey,Tval>& Hash_Table<Tkey,Tval>::operator= (const Hash_Table<Tkey,Tval>& h) {
  Hash_Table::operator=(h);
  long prime = hash_primes[this->current_bucket]; // Get prime number
  delete this->table;				 // Return old table storage
  this->table = (Hash_Table<Tkey,Tval>_bucket*)new Hash_Table<Tkey,Tval>_bucket[prime]; 
  for (long i = 0; i < prime; i++) {		// For each bucket count
    for (int j = 0; j < h.items_in_buckets[i]; j++) {// For each item in bucket
      this->table[i].data[j].key = h.table[i].data[j].key; // Copy key 
      this->table[i].data[j].value = h.table[i].data[j].value; // Copy value
    }
  }
  this->compare_keys_s = h.compare_keys_s;	// Use same compare function
  this->compare_values_s = h.compare_values_s;	// Use same compare function
  return *this;					// Return reference
}


// operator!= -- Determine if two hash tables are unequal
// Input:        this*, reference to second hash table
// Output:       TRUE/FALSE

template <class Tkey, class Tval> 
inline Boolean Hash_Table<Tkey,Tval>::operator!= (const Hash_Table<Tkey,Tval>& t) {
  return (!operator== (t));
}
  

// operator== -- Determine if two hash tables are equal. This is accomplished
//               by seeing that for each key/value pair in table1, there is the
//               the same pair somewhere in table2.
// Input:        Reference to hash table
// Output:       TRUE/FALSE

template <class Tkey, class Tval> 
Boolean Hash_Table<Tkey,Tval>::operator==(const Hash_Table<Tkey,Tval>& h) {
  if (this->length() != h.length())	       // If not same number of entries
    return FALSE;			       // Then tables are not equal
  if (this->get_bucket_count() == h.get_bucket_count()) { // If same bucket cnt
    for (long i = 0; i < this->get_bucket_count(); i++) {  // for each bucket
      int count = this->get_count_in_bucket(i);
      if (count != h.get_count_in_bucket(i))	//Count eq?
	return FALSE;				// No, tables !equal
      Hash_Table<Tkey,Tval>_pair* this_bucket = this->table[i].data;
      Hash_Table<Tkey,Tval>_pair* h_bucket = h.table[i].data;
      for (int j = 0; j < count; j++) {		// For each item in this
	for (int k = 0; k < count; k++) {	// For each item in h
	  if ((*this->compare_keys_s)(this_bucket[j].key, h_bucket[k].key)) {
	    if ((*this->compare_values_s)(this_bucket[j].value, // key same,
					  h_bucket[j].value))   // is value?
	      goto good;
	    return FALSE;			// Not the same, so tables !eql
	  }
	}
      good: ;
      }
    }
    return TRUE;			       // No difference, so equal
  } else {
    Tval temp;				       // Temporary storage;
    for (long i = 0; i < h.get_bucket_count (); i++) {   // For each bucket
      for (int j = 0; j < h.get_count_in_bucket(i); j++) // For each item
	if (this->get (h.table[i].data[j].key, temp) == TRUE)// If key in table
	  if ((*this->compare_values_s)(h.table[i].data[j].value, temp))
	    continue;			       // Key/value same, continue
	  else
	    return FALSE;		       // Value different, return FALSE
	else
	  return FALSE;			       // Key not in table so different
    }
  }
  return TRUE;				       // No difference, so equal
}


// Set_hash -- Set the hash function for this instance
// Input:      Pointer to hash function
// Output:     None

template <class Tkey, class Tval> 
void Hash_Table<Tkey,Tval>::set_hash (Hash_Table<Tkey,Tval>_Hash h) {
  this->h_function = h;
}


// set_key_compare -- Set the compare function for this instance
// Input:             Pointer to compare function
// Output:            None

template <class Tkey, class Tval> 
void Hash_Table<Tkey,Tval>::set_key_compare (Hash_Table<Tkey,Tval>_Key_Compare c) {
  if (c == NULL)				// If no method supplied
    this->compare_keys_s = &Hash_Table<Tkey,Tval>_keys_equal; // Use default
  else
    this->compare_keys_s = c;
}


// set_value_compare -- Set the compare function for this instance
// Input:               Pointer to compare function
// Output:              None

template <class Tkey, class Tval> 
void Hash_Table<Tkey,Tval>::set_value_compare(Hash_Table<Tkey,Tval>_Value_Compare c) {
  if (c == NULL)
    this->compare_values_s = &Hash_Table<Tkey,Tval>_values_equal;
  else
    this->compare_values_s = c;
}

// If all the generic support hasn't been loaded yet, do it now.
#ifndef GENERIC_H
#include <cool/Generic.h>
#endif

#endif						// End #ifdef of HASH_TABLEH
