set.c

来自「开放源码的编译器open watcom 1.6.0版的源代码」· C语言 代码 · 共 502 行 · 第 1/2 页

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

#include <cool/Set.h>

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

template <class Type> 
CoolSet<Type>::CoolSet() {
  long prime = hash_primes[this->current_bucket]; // Get prime number 
  this->table = new Bucket[prime];       // Allocate buckets
  this->h_function = &CoolSet_default_hash; // Setup hash 
  this->compare = &CoolSet_are_keys_equal;  // Setup compare
}


// CoolSet -- Simple constructor with one argument that creates a CoolSet 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> 
CoolSet<Type>::CoolSet(unsigned long n)
 : CoolBase_Hash_Table(n)
{
  long prime = hash_primes[this->current_bucket]; // Get prime number 
  this->table = new Bucket[prime];        // Allocate buckets
  this->h_function = &CoolSet_default_hash; // Setup hash 
  this->compare = &CoolSet_are_keys_equal;  // Setup compare
}


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

template <class Type> 
CoolSet<Type>::CoolSet(const CoolSet<Type>& s)
 : CoolBase_Hash_Table(s)
{
  long prime = hash_primes[this->current_bucket]; // Get prime number 
  this->table = new 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
}


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

template <class Type> 
CoolSet<Type>::~CoolSet() {
  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 CoolSet<Type>::operator== (const CoolSet<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 CoolSet
// Input:  Key searching for
// Output: TRUE/FALSE, current_position not updated

template <class Type> 
Boolean CoolSet<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 CoolSet<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& CoolSet<Type>::value () {
#if ERROR_CHECKING
  if (this->curpos == INVALID) {                // If invalid current positio
    //RAISE Error, SYM(CoolSet), SYM(Invalid_Cpos)
    printf ("CoolSet<%s>::value(): Invalid current position.\n", #Type);
    abort ();
  }
#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
  }
}


// ***** bug? remove does not leave current position pointed at next element?
// remove -- Remove element at current position from the set
// Input:    this*
// Output:   TRUE/FALSE

template <class Type> 
Boolean CoolSet<Type>::remove () {
  if (this->curpos == INVALID) {                // If valid current position
#if ERROR_CHECKING
    //RAISE Error, SYM(CoolSet), SYM(Invalid_Cpos)
    printf ("CoolSet<%s>::remove(): Invalid current position.\n", #Type);
    abort ();
#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 CoolSet is a subset of another
// Input:    Reference to a CoolSet object
// Output:   TRUE/FALSE

template <class Type> 
Boolean CoolSet<Type>::search (CoolSet<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 CoolSet<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 CoolSet<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