//
// 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 06/05/89 -- Initial design and implementation
// Updated: MBN 08/20/89 -- Changed usage of template to reflect new syntax
// Updated: MBN 09/15/89 -- Added conditional exception handling
// Updated: MBN 10/03/89 -- Fixed put() method to update value
// Updated: MBN 10/07/89 -- Fixed double entry count with use of iterators
// Updated: MBN 10/12/89 -- Changed "current_position" to "curpos" and changed
//                          state from bit set to bit set/get macros
// Updated: LGO 10/19/89 -- Fixed operator==() for tables with different bucket
//                          count but same elements -- tables grew separately
// Updated: MBN 12/22/89 -- Sprinkled "const" qualifiers all over the place!
// Updated: MBN 02/22/90 -- Changed size arguments from long to unsigned long
// Updated: MBN 02/23/90 -- Made operators -=, ^=, |=, &= return reference 
// Updated: MJF 03/12/90 -- Added group names to RAISE
// Updated: MJF 06/30/90 -- Added base class name to constructor initializer
//
// The Set<Type> class implements a set  of elements  of a user-specified type.
// This is accompilshed by using the parameterized type capability of C++.  The
// Set<Type> class implements a simple one-element hash table where the key and
// the value are the same thing.  The type of the Set class is the key/value in
// the Hash Table.  The  Set<Type> class is  derived from the Hash_Table  class
// and 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 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 private data  section of  a Set<Type> 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 static table of  selected prime numbers. This
// static table contained within  the class 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 default   hash  utilizes  the number   of  buckets  in order   to
// accomplish this. A user-supplied function should do something similar.
//
// Other items in the private data section include a pointer to a hash function
// and a  pointer to  a compare  function.   The compare   function  is 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(Type) is 4, that is shifted left  three bits with the result
// modulo the number of buckets determining the  hash. This  is ideal when Type
// is a pointer..   If sizeof(Type) is greater than  4,  then the 32 bit  value
// used  is  the  result of  exclusive-oring  successive 32-bit values  for the
// length of T1, 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  Set that can  contain 24 items before  resizing is
// necessary.  The second constructor accepts an integer argument and creates a
// Set that  can accomodate at  least the specified number  of items.  Finally,
// the third constructor takes a single argument  consisting of a  reference to
// another Set and duplicates its size and contents.
//
// Methods are provided to put, query,  and remove  an item from a set, perform
// the  intersection, union,  difference, and exclusive-or  of two  sets, check
// equality and inequality of  two set  objects, and determine if  one set is a
// subset of another. In  addition, the notion of  a current position  within a
// set is maintained and reset, next, previous,  find,  and get value functions
// for setting and using the current position are provided.  Also  for use with
// the current position are the next  union, next intersetion, next difference,
// and next  exclusive-or  operations. These    allow a   user to access    the
// first/next individual item that results  from some logical  operation. These
// functions are particularly efficient, since no temporary Set<Type> structure
// is created. Finally, functions to set the  compare and hash functions for an
// instance of a set, get the count of the number of items in a set, output the
// set to a stream, clear all elements from a set,  and determine if  a  set is
// empty are also available.
//

#ifndef SETH					// If no Set class,
#define SETH					// define it

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

#ifndef GENERIC_H
#include <cool/Generic.h>
#endif

typedef long Set_state;				// Current position state

template <class Type> Set {
  struct Type ## _bucket {			// Structure for bucket
    Type data[BUCKET_SIZE];
  };
  typedef Boolean (*Type ## _Set_Item_Compare) (const Type&, const Type&);
  typedef long (*Type ## _Set_Hash) (const Type&);
}

template <class Type>
class Set<Type> : public Hash_Table {		// Define Set
private:
  Type next_data;				// Slot to hold next_union data
  Type ## _bucket* table;			// Pointer to key buckets
  Type ## _Set_Hash h_function;			// Pointer to hash function
  Type ## _Set_Item_Compare compare;		// Pointer operator== function
  friend Boolean Type ## _Set_are_keys_equal (const Type&, const Type&);
  friend long Type ## _Set_default_hash (const Type&);
  
  Boolean do_find (const Type&) CONST;		// Set current position

public:
  Set<Type> ();					// Set of default size
  Set<Type> (unsigned long);			// Set for at least size
  Set<Type> (const Set<Type>&);			// Set with reference
  ~Set<Type>();					// Destructor

  Boolean find (const Type&);			// Set current position
  Type& value ();				// Get value at current
  Boolean remove ();				// Remove item current position
  
  Boolean put (const Type&);			// Put element into set
  Boolean remove (const Type&);			// Remove element from set
  Boolean search (Set<Type>&);			// Subset operator
  Boolean resize (long);			// Resize for at least count

  Set<Type> operator | (Set<Type>&);		// Union of two sets       
  Set<Type> operator - (Set<Type>&);		// Difference of two sets  
  Set<Type> operator ^ (Set<Type>&);		// Exclusive-or of two sets
  Set<Type> operator & (Set<Type>&);		// Intersection of two sets

  Set<Type>& operator |= (Set<Type>&);		// Union of two sets
  Set<Type>& operator -= (Set<Type>&);		// Difference of two sets
  Set<Type>& operator ^= (Set<Type>&);		// Exclusive-or of two sets
  Set<Type>& operator &= (Set<Type>&);		// Intersection of two sets

  inline void set_union (Set<Type>&);		// Union of two sets       
  inline void set_difference (Set<Type>&);	// Difference of two sets  
  inline void set_xor (Set<Type>&);		// Exclusive-or of two sets
  inline void set_intersection (Set<Type>&);	// Intersection of two sets

  Boolean next_union (Set<Type>&);		// Return next union item
  Boolean next_difference (Set<Type>&);		// Return next difference item
  Boolean next_xor (Set<Type>&);		// Return next exclusive-or
  Boolean next_intersection (Set<Type>&);	// Return next intersection
  
  Set<Type>& operator= (const Set<Type>&);	// Assignment
  inline friend ostream& operator<< (ostream&, const Set<Type>*); // output
  friend ostream& operator<< (ostream&, const Set<Type>&); // Overload output

  Boolean operator== (const Set<Type>&) CONST;	      // Set equality test
  inline Boolean operator!= (const Set<Type>&) CONST; // Set inequality test

  inline void set_hash (Type ## _Set_Hash);	// Set the hash function
  inline void set_compare (Type ## _Set_Item_Compare); // Set compare function
};

MACRO Default_Set_Hash (KeyT) {
#if ISSAME(KeyT, charP, String, Gen_String)
#ifndef CHARH
#include <cool/char.h>
#endif
Boolean KeyT##_Set_are_keys_equal (const KeyT& v1, const KeyT& v2) {
  return !strcmp (v1, v2);
}
long KeyT##_Set_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 KeyT##_Set_are_keys_equal (const KeyT& k1, const KeyT& k2) {
  return ((k1 == k2) ? TRUE : FALSE);
}


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

long KeyT##_Set_default_hash (const KeyT& key) {
  if (sizeof (key) <= 4)
    return (long(key) >> 3);
  else {
    int hash_value = 0;
    char* temp = (char*) &key;
    for (int i = 0; i < sizeof (key); i++) {
      hash_value = hash_value ^ temp[i];
      if (hash_value < 0)
	hash_value = -hash_value;
    }
    return (hash_value >> 3);
  }
}

#endif
}

template <class Type> Set {
  Default_Set_Hash (Type);
}

// set_union -- Determine the union of two sets
// Input:       Reference to a Bit Set object
// Output:      None

template <class Type> 
inline void Set<Type>::set_union (Set<Type>& b) {
  this->operator|= (b);
}


// set_difference -- Determine the difference of two sets
// Input:            Reference to a Bit Set object
// Output:           None

template <class Type> 
inline void Set<Type>::set_difference (Set<Type>& b) {
  this->operator-= (b);
}


// set_xor -- Determine the exclusive-OR of two sets
// Input:     Reference to a Bit Set object
// Output:    None

template <class Type> 
inline void Set<Type>::set_xor (Set<Type>& b) {
  this->operator^= (b);
}


// set_intersection -- Determine the intersection of two sets
// Input:              Reference to a Bit Set object
// Output:             None

template <class Type> 
inline void Set<Type>::set_intersection (Set<Type>& b) {
  this->operator&= (b);
}

  
// operator!= -- Return logical result of not equal comparison test
// Input:        Reference to another Bit Set object
// Output:       Boolean TRUE/FALSE

template <class Type> 
inline Boolean Set<Type>::operator!= (const Set<Type>& b) CONST {
  return (!(this->operator== (b)));
}


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

template <class Type> 
inline void Set<Type>::set_hash (Type ## _Set_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 Type> 
inline void Set<Type>::set_compare (Type ## _Set_Item_Compare c) {
  this->compare = c;
}


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

template <class Type> 
Set<Type>::Set<Type> () {
  long prime = hash_primes[this->current_bucket]; // Get prime number 
  this->table = new Type ## _bucket[prime];	 // Allocate buckets
  this->h_function = &Type ## _Set_default_hash; // Setup hash 
  this->compare = &Type ## _Set_are_keys_equal;	 // Setup compare
}


// Set -- Simple constructor with one argument that creates a Set 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 Type> 
Set<Type>::Set<Type> (unsigned long n)
#ifdef __cplusplus
 : Hash_Table(n)
#else
 : (n)
#endif
{
  long prime = hash_primes[this->current_bucket]; // Get prime number 
  this->table = new Type ## _bucket[prime];	  // Allocate buckets
  this->h_function = &Type ## _Set_default_hash;  // Setup hash 
  this->compare = &Type ## _Set_are_keys_equal;	  // Setup compare
}


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

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


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

template <class Type> 
Set<Type>::~Set<Type> () {
  delete this->table;				// Free key/value storage
}


// Operator== -- Determine if two hash tables are equal. This is accompilished
//               by seeing that for each key/value in SeType, the same
//               key/value also exists in Set2
// Input:        this*, reference to second set
// Output:       TRUE/FALSE

template <class Type> 
Boolean Set<Type>::operator== (const Set<Type>& s) CONST {
  if (this->length() != s.length())	       // If not same number of entries
    return FALSE;			       // Then tables are not equal
  if (this->get_bucket_count() == s.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 != s.get_count_in_bucket(i))	//Count eq?
	return FALSE;				// No, tables !equal
      Type* this_bucket = this->table[i].data;
      Type* s_bucket = s.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 s
	  if ((*this->compare)(this_bucket[j], s_bucket[k]))
	    goto good;
	return FALSE;				// Not the same, so tables !eq
      good: ;
      }
    }
  } else {
    for (long i = 0; i < s.get_bucket_count (); i++)      // For each bucket
      for (int j = 0; j < s.get_count_in_bucket(i); j++)  // For each item
	if (!this->do_find(s.table[i].data[j]))		  // If key in table
	  return FALSE;			       // Key not in table so different
  }
  return TRUE;					  // No difference, so equal
}


// do_find -- Find key/value in Set
// Input:  Key searching for
// Output: TRUE/FALSE, current_position not updated

template <class Type> 
Boolean Set<Type>::do_find (const Type& key) CONST {
  long prime = hash_primes[this->current_bucket]; // Prime number of buckets
  unsigned long hash = ((*this->h_function)(key)) % prime; // Get hash value
  for (long i = 0; i < this->items_in_buckets[hash]; i++) { // For each entry
    if (((*this->compare)(key,this->table[hash].data[i])) == TRUE)
      return TRUE;				// Return success
  }
  return FALSE;
}

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

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


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

template <class Type> 
Type& Set<Type>::value () {
#if ERROR_CHECKING
  if (this->curpos == INVALID)			// If invalid current position
    RAISE (Error, SYM(Set), SYM(Invalid_Cpos),
	   "Set<%s>::value(): Invalid current position", #Type);
#endif
  if (TRAVERSED(this->curpos))			// If data in 2nd set
     return this->next_data;			// Return saved value
  else {
    unsigned long hash = BUCKET_NUMBER(this->curpos); // Get bucket number
    long index = BUCKET_INDEX(this->curpos);	      // Get Bucket index
    return (this->table[hash].data[index]);	      // Return value
  }
}


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

template <class Type> 
Boolean Set<Type>::remove () {
  if (this->curpos == INVALID) {		// If valid current position
#if ERROR_CHECKING
    RAISE (Error, SYM(Set), SYM(Invalid_Cpos),
	   "Set<%s>::remove(): Invalid current position", #Type);
#endif
    return FALSE;				// Return failure
  }
  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] = this->table[hash].data[count-1];
  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);
    this->curpos |= SET_TRAVERSED(FALSE);	// Reset traverse flag
  }
  else
    this->curpos = INVALID;			// Else invalidate marker
  return TRUE;					// Return success
}


// search -- Determine if one Set is a subset of another
// Input:    Reference to a Set object
// Output:   TRUE/FALSE

template <class Type> 
Boolean Set<Type>::search (Set<Type>& s) {
  if (this->length() < s.length())		// If more elements in 2nd set
    return FALSE;				// Then it is not a subset
  for (s.reset(); s.next(); )			// For each entry in 2nd set
    if (this->find (s.value()) == FALSE)	// If not in 1st set
      return FALSE;				// Then it's not a subset
  return TRUE;					// Else it's a subset
}


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

template <class Type> 
Boolean Set<Type>::put (const Type& key) {
retry:  
  long prime = hash_primes[this->current_bucket]; // Prime number of buckets
  unsigned long hash = ((*this->h_function)(key)) % prime; // Get hash value
  if (this->items_in_buckets[hash] == BUCKET_SIZE) {	   // If bucket is full
    this->resize (hash_primes[this->current_bucket++]*BUCKET_SIZE);
    goto retry;					// Try again 
  }
  this->table[hash].data[this->items_in_buckets[hash]] = key;
  this->entry_count++;				// Increment table entry count
  this->curpos = SET_BUCKET_NUMBER(hash);	// Save bucket number
  this->curpos |= SET_BUCKET_INDEX(this->items_in_buckets[hash]);
  this->curpos |= SET_TRAVERSED(FALSE);		// Reset traverse flag
  this->items_in_buckets[hash]++;		// Increment bucket item count
  return TRUE;					// Indicate success
}


// remove -- Remove an element from the set
// Input:    this*, reference to a key
// Output:   TRUE/FALSE

template <class Type> 
Boolean Set<Type>::remove (const Type& 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)(key,this->table[hash].data[i]) == TRUE) {
      this->table[hash].data[i] = this->table[hash].data[count-1];
      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);
	this->curpos |= SET_TRAVERSED(FALSE);	// Reset traverse flag
      }
      else
	this->curpos = INVALID;			// Else invalidate marker
      return TRUE;
    }
  }
  return FALSE;					// Return failure flag
}


// resize -- Resize a Set object to hold at least some number items
// Input:    this*, minimum number of items to hold
// Output:   TRUE/FALSE

template <class Type> 
Boolean Set<Type>::resize (long n) {
#if ERROR_CHECKING
  if (n < 0)					// If invalid size specified
    RAISE (Error, SYM(Set), SYM(Negative_Size),
	   "Set<%s>::resize(): Negative resize %d", #Type, n);
#endif
  Type ## _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
    long new_size = long((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
  t2 = new Type ## _bucket[new_prime];		     // Allocate new buckets
  for (i = 0; i < old_prime; i++) {		     // For each bucket count
    for (int j = 0; j < this->items_in_buckets[i]; j++) { // For each item
      Type key = this->table[i].data[j];	// Get key from table
      unsigned long hash = ((*this->h_function)(key)) % new_prime; // Get hash 
      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; 	             // Copy key into new table
      t1[hash]++;				     // Increment 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
  return TRUE;					// Return success
}


// operator| -- Return the union of two sets, that is all elements in each set
// Input:       Reference to a set
// Output:      New Set object containing union of two sets

template <class Type> 
Set<Type> Set<Type>::operator| (Set<Type>& s) {
  Set<Type> result(this->length() + s.length()); // Temporary variable
  for (this->reset(); this->next (); )		// For each entry in 1st set
    result.put (this->value());			// Put entry to result set
  result.operator|=(s);
  return result;				// Return resulting union
}


// operator- -- Return the difference of two sets, that is all elements in
//              the first set that are not in the second
// Input:       Reference to a set
// Output:      New Set object containing difference of two sets

template <class Type> 
Set<Type> Set<Type>::operator- (Set<Type>& s) {
  Set<Type>* result;				// Temporary variable
  result = new Set<Type>(this->length());	// Allocate enough storage
  result->entry_count = 0;			// Initialize entry count
  for (this->reset(); this->next (); )		// For each entry in 1st set
    if (s.find (this->value()) == FALSE) 	// If entry not in 2nd set
      result->put (this->value());		// Put entry to result set
  result->curpos = INVALID;			// Invalidate current position
  return *result;				// Return resulting union
}


// operator^ -- Return the exclusive-OR of two sets, that is all elements in
//              the first set that are not in the second and all elements in the
//              second set that are not in the first
// Input:       Reference to set
// Output:      New Set object containing XOR of two sets

template <class Type> 
Set<Type> Set<Type>::operator^ (Set<Type>& s) {
  Set<Type>* result;				// Temporary variable
  if (this->length() > s.length()) 		// Determine longest storage
    result = new Set<Type> (this->length());	// Allocate storage
  else						// Else the other one is bigger
    result = new Set<Type> (s.length());	// Allocate storage equal to s
  result->entry_count = 0;			// Initialize entry count
  for (this->reset(); this->next (); )		// For each entry in 1st set
    if (s.find (this->value()) == FALSE) 	// If entry not in 2nd set
      result->put (this->value());		// Put entry to result set
  for (s.reset(); s.next (); )			// For each entry in 2nd set
    if (this->find (s.value()) == FALSE) 	// If entry not in 1st set
      result->put (s.value());			// Put entry to result set
  result->curpos = INVALID;			// Invalidate current position
  return *result;				// Return resulting union
}


// operator& -- Return the intersection of two sets, that is all elements that
//              are in both sets
// Input:       Reference to Set object
// Output:      New Set object containing intersection of two sets

template <class Type> 
Set<Type> Set<Type>::operator& (Set<Type>& s) {
  Set<Type>* result;				// Temporary variable
  if (this->length() < s.length()) 		// Determine smallest storage
    result = new Set<Type> (this->length());	// Allocate storage
  else						// Else the other one is bigger
    result = new Set<Type> (s.length());	// Allocate storage equal to b
  result->entry_count = 0;			// Initialize entry count
  for (this->reset(); this->next (); )		// For each entry in 1st set
    if (s.find (this->value()) == TRUE) 	// If entry in 2nd set
      result->put (this->value());		// Put entry to result set
  result->curpos = INVALID;			// Invalidate current position
  return *result;				// Return resulting union
}
 

// operator|= -- Determine the union of two sets, that is all elements in each
//               set and modify the source with the result
// Input:        Reference to a set
// Output:       Updated Set object containing union of two sets

template <class Type> 
Set<Type>& Set<Type>::operator|= (Set<Type>& s) {
  for (s.reset (); s.next (); )			// For each entry in 2nd set
    if (this->find (s.value()) == FALSE) 	// If not in 1st set
      this->put (s.value ());			// Put to result set
  this->curpos = INVALID;			// Invalidate current position
  return *this;					// Return reference
}


// operator-= -- Determine the difference of two sets, that is all elements in
//               the first set that are not in the second and modify the source
//               with the result
// Input:        Reference to a set
// Output:       Updated Set object containing difference of two sets

template <class Type> 
Set<Type>& Set<Type>::operator-= (Set<Type>& s) {
  Set<Type>* result;				// Temporary variable
  result = new Set<Type> (this->length());	// Allocate storage 
  result->entry_count = 0;			// Initialize entry count
  for (this->reset(); this->next (); )		// For each entry in 1st set
    if (s.find (this->value()) == FALSE) 	// If entry not in 2nd set
      result->put (this->value());		// Add to result set
  result->h_function = this->h_function;	// Use same hash function
  result->compare = this->compare;		// Use same compare function
  *this = *result;				// Copy new set
  this->curpos = INVALID;			// Invalidate current position
  delete result;                                // Delete temporary storage
  return *this;					// Return reference
}


// operator^= -- Determine the exclusive-OR of two sets, that is all elements 
//               in the first set that are not in the second and all elements 
//               in the second set that are not in the first and modify the
//               source with the result
// Input:        Reference to set
// Output:       Updated Set object containing XOR of two sets

template <class Type> 
Set<Type>& Set<Type>::operator^= (Set<Type>& s) {
  Set<Type>* result;				// Temporary variable
  if (this->length() > s.length()) 		// Determine longest storage
    result = new Set<Type> (this->length());	// Allocate storage 
  else						// Else the other one is bigger
    result = new Set<Type> (s.length());	// Allocate storage equal to s
  for (this->reset(); this->next (); )		// For each entry in 1st set
    if (s.find (this->value()) == FALSE) 	// If entry not in 2nd set
      result->put (this->value());		// Put entry to result set
  for (s.reset(); s.next (); )			// For each entry in 2nd set
    if (this->find (s.value()) == FALSE) 	// If entry not in 1st set
      result->put (s.value());			// Put entry to result set
  result->curpos = INVALID;			// Invalidate current position
  result->h_function = this->h_function;	// Use same hash function
  result->compare = this->compare;		// Use same compare function
  *this = *result;				// Copy new set
  delete result;                                // Delete temporary storage
  return *this;					// Return reference
}


// operator&= -- Determine the intersection of two sets, that is all elements
//               that are in both sets and modify the source with the result
// Input:        Reference to Set object
// Output:       Updated Set object containing intersection of two sets

template <class Type> 
Set<Type>& Set<Type>::operator&= (Set<Type>& s) {
  Set<Type>* result;				// Temporary variable
  result = new Set<Type> (this->length());	// Allocate storage 
  for (this->reset(); this->next (); )		// For each entry in 1st set
    if (s.find (this->value()) == TRUE) 	// If entry in 2nd set
      result->put (this->value());		// Add to result set
  result->h_function = this->h_function;	// Use same hash function
  result->compare = this->compare;		// Use same compare function
  *this = *result;				// Copy new set
  this->curpos = INVALID;			// Invalidate current position
  delete result;                                // Delete temporary storage
  return *this;					// Return reference
}
 

// next_intersection -- Position at the next intersection of two Sets.
// Input:               Reference to Set object
// Output:              TRUE/FALSE, current position updated

template <class Type> 
Boolean Set<Type>::next_intersection (Set<Type>& s) {
  if (this->curpos != INVALID && TRAVERSED(this->curpos)) // Traversed already?
    return FALSE;				// Indicate no more elements
  while (this->next () == TRUE)	{		// While there are elements
    if (BUCKET_NUMBER(this->curpos) >= s.get_bucket_count())
      return FALSE;				// Return failure status
    if (s.find(this->value()) == TRUE)		// If element in 2nd set
      return TRUE;				// Return success status
  }
  this->curpos = INVALID;			// Invalidate current position
  return FALSE;					// Return failure status
}


// next_union -- Position at the next union of two Sets.
// Input:        Reference to Set object
// Output:       TRUE/FALSE, current position updated

template <class Type> 
Boolean Set<Type>::next_union (Set<Type>& s) {
  if ((this->curpos != INVALID && !TRAVERSED(this->curpos)) ||
      this->curpos == INVALID) {
    if (this->next () == TRUE)			// If more elements in 1st set
      return TRUE;				// Return success status
    else					// Else set traversed flag
      this->curpos = SET_TRAVERSED(TRUE);
  }
  while (s.next () == TRUE) {			// While more elements in 2nd 
    if (this->find(s.value()) == FALSE) {	// If element not in 1st set
      this->curpos |= SET_TRAVERSED(TRUE);	// Reset flag zeroed by find
      this->next_data = s.value();		// Refer to next piece of data
      return TRUE;				// Return success status
    }
  }
  this->curpos = INVALID;			// Invalidate current position
  return FALSE;					// Return failure status
}


// next_difference -- Position at the zero-relative integer of the next bit in 
//                    the difference of two Sets.
// Input:             Reference to Set object
// Output:            TRUE/FALSE, current position updated

template <class Type> 
Boolean Set<Type>::next_difference (Set<Type>& s) {
  if (this->curpos != INVALID && TRAVERSED(this->curpos)) // Traversed already?
    return FALSE;				// Indicate no more elements
  while (this->next () == TRUE)	{		// While there are elements
    if (BUCKET_NUMBER(this->curpos) >= s.get_bucket_count())
      return FALSE;				// Return failure status
    if (s.find(this->value()) == FALSE)		// If element not in 2nd set
      return TRUE;				// Return success status
  }
  this->curpos = INVALID;			// Invalidate current position
  return FALSE;					// Return failure status
}


// next_xor -- Position at the zero-relative integer of the next bit in 
//             the XOR of two Sets.
// Input:      Reference to Set object
// Output:     TRUE/FALSE, current position updated

template <class Type> 
Boolean Set<Type>::next_xor (Set<Type>& s) {
  if ((this->curpos != INVALID && !TRAVERSED(this->curpos)) ||
      this->curpos == INVALID) {
	if (this->next_difference (s) == TRUE)	// If more elements in 1st set
	  return TRUE;				// Return success status
	else {					// Else set traversed flag
	  this->curpos = SET_TRAVERSED(TRUE);
	  s.reset();				// Reset current position
	}
      }
  if ((s.curpos != INVALID && !TRAVERSED(s.curpos)) || s.curpos == INVALID) {
    this->reset();				// Reset 1st set pointer
    if (s.next_difference (*this)) {		// If any other elements in 2nd
      this->curpos |= SET_TRAVERSED(TRUE);	// Reset flag set by find
      this->next_data = s.value();		// Save data for value()
      return TRUE;				// Return success status
    }
  }
  this->curpos = INVALID;			// Invalidate current position
  return FALSE;					// Return failure status
}


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

template <class Type> Set {
inline ostream& operator<< (ostream& os, const Set<Type>* s) {
  return operator<< (os, *s);
}
}


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

template <class Type> Set {
ostream& operator<< (ostream& os, const Set<Type>& s) {
  os << "[ ";					// Output opening bracket
  for (int i = 0; i < s.get_bucket_count(); i++) // For each bucket
    for (int j = 0; j < s.get_count_in_bucket(i); j++) // For each key/pair
      os << s.table[i].data[j] << " ";		 // Output the key
  os << "]\n";					 // Output bracket
  return os;						 // Return stream
}
}


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

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

#endif						// End of SETH
