bit_set.c

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

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

CoolBit_Set& CoolBit_Set::operator|= (const CoolBit_Set& b) {
  if (b.number_elements > this->size)
    this->grow(b.number_elements * BS_BITSPERBYTE);
  generate_set_operator(this, b, |, b_data[i]); // Calculate the union
  if (this->number_elements < b.number_elements)
    this->number_elements = b.number_elements;
  this->curpos = INVALID;                       // Invalidate current position
  return *this;                                 // Return refenerce
}


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

CoolBit_Set& CoolBit_Set::operator-= (const CoolBit_Set& b) {
  generate_set_operator(this, b, &~, 0);        // Calculate the difference
  this->curpos = INVALID;                       // Invalid current position
  return *this;                                 // Return refenerce
}


// 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 destructively 
//               modify the first with the result
// Input:        Reference to bit set
// Output:       Updated Bit Set object containing XOR of two sets

CoolBit_Set& CoolBit_Set::operator^= (const CoolBit_Set& b) {
  if (b.number_elements > this->size)
    this->grow(b.number_elements * BS_BITSPERBYTE);
  generate_set_operator(this, b, ^, b_data[i]); // Calculate the exclusive-OR
  if (this->number_elements < b.number_elements)
    this->number_elements = b.number_elements;
  this->curpos = INVALID;                       // Invalidate current position
  return *this;                                 // Return refenerce
}


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

CoolBit_Set& CoolBit_Set::operator&= (const CoolBit_Set& b) {
  generate_set_operator(this, b, &, 0);         // Calculate the exclusive-OR
  if (this->number_elements > b.number_elements) {
    this->number_elements = b.number_elements;  // shorten ourself
    for (; i < a_size; i++) a_data[i] = 0;      // and Zap excess bits
  }
  this->curpos = INVALID;                       // Invalid current position
  return *this;                                 // Return refenerce
}


// clear -- Remove all elements from the set
// Input:   None
// Output:  None

void CoolBit_Set::clear () {
  for (int i = 0; i < this->number_elements; i++) 
    this->data[i] = 0;                          // Initialize bits to zero
  this->curpos = INVALID;                       // Invalidate current position
}


// grow -- resize the bit set (private method)
// Input:    Minimum size requirement
// Output:   none

void CoolBit_Set::grow (int min_size) {
  if (this->growth_ratio != 0.0 &&
      (this->size * (1.0+growth_ratio)) >= min_size)
    min_size = (int)(this->size * (1.0 + growth_ratio)); // New size
  else
    min_size += alloc_size_s;                   // Update vector size
  resize(min_size);
}


// resize -- Resize the bit set for at least some specified number of elements
// Input:    Minimum size requirement
// Output:   TRUE/FALSE

void CoolBit_Set::resize (int n) {
  int nbytes = BS_BYTE_COUNT(n);
  unsigned char* temp = new unsigned char[nbytes]; // Allocate storage
  int i;
  for (i = 0; i < this->number_elements; i++) 
    temp[i] = this->data[i];                    // copy old data
  for (; i < nbytes; i++)
    temp[i] = 0;                                // clear new data
  delete [] this->data;                         // Free old storage
  this->data = temp;                            // Point to new storage
  this->size = nbytes;                          // Save number of bytes
  this->curpos = INVALID;                       // Reset current position
}


// operator= -- Overload the assignment operator for Bit Set objects
// Input:       Reference to Bit Set object
// Output:      Reference to Bit Set object

CoolBit_Set& CoolBit_Set::operator= (const CoolBit_Set& b) {
  if (this != &b) {
    int len = b.size;                           // Get size of object to copy
    if (this->size < len) {                     // If not enough storage
      delete [] this->data;                     // Deallocate old storage
      this->data = new unsigned char[len];      // Allocate same size storage
      this->size = len;                         // Maintain number of bytes
    }
    for (int i = 0; i < len; i++)
      this->data[i] = b.data[i];                // copy all bytes
    this->number_elements = b.number_elements;
    this->curpos = INVALID;                     // Reset current position
  }
  return *this;                                 // Return reference to object
}


// operator<< -- Overload the output operator for Bit Set objects
// Input:        Reference to stream, reference to Bit Set object
// Output:       Reference to stream

ostream& operator<< (ostream& os, const CoolBit_Set& b) {
  static char ascii_rep[10];                    // Static storage for 0's/1's
  os << "[ ";                                   // Output start of set bracket
  for (int i = 0; i < b.number_elements; i++) { // For each byte in the set
    strcpy (ascii_rep, "00000000 ");            // Assume majority of zeros
    for (int j = 7; j >= 0; j--)
      if (b.data[i] & (1 << j))
        ascii_rep[j] = '1';                     // Copy "1" character to string
    os << ascii_rep;                            // Output 0's and 1's for byte
  }
  os << "]\n";                                  // Output terminating bracket
  return os;                                    // Return reference to stream
}


// operator== -- Overload the equality operator for Bit Set objects
// Input:        Reference to Bit Set object
// Output:       TRUE/FALSE

Boolean operator== (const CoolBit_Set& b1, const CoolBit_Set& b2) {
  int len = min(b1.number_elements, b2.number_elements); // common length
  int i;
  for (i = 0; i < len; i++)                            
    if (b1.data[i] != b2.data[i])                 // Check for different bits
      return FALSE;                               // in common section
  for (i = len; i < b1.number_elements; i++)      // Check for nonzero bits in
    if (b1.data[i])                               // extra section of this
      return FALSE;                               
  for (i = len; i < b2.number_elements; i++)      // Check for nonzero bits in
    if (b2.data[i])                               // extra section of b
      return FALSE;                               
  return TRUE;                                    // Return success indication
}


// length -- Return number of elements in Set
// Input:    None
// Output:   Integer representing number of bits set 

int CoolBit_Set::length () const {
  int count = 0;                                // Temporary to hold count
  int len = this->number_elements;
  for (int i = 0; i < len; i++)                 // For each byte in the vector
    count += bits_set[this->data[i]];           // Add to count number bits set
  return count;                                 // Return element count 
}


// value_error -- Raise exception for CoolBit_Set::value() method
// Input:         None
// Output:        None

void CoolBit_Set::value_error () const {
  //RAISE (Error, SYM(CoolBit_Set), SYM(Invalid_Cpos),
  printf ("CoolBit_Set::value(): Invalid current position.\n");
  abort ();
}


// bracket_error -- Raise exception for CoolBit_Set::operator[]() method
// Input:           None
// Output:          None

void CoolBit_Set::bracket_error (int n) const {
  //RAISE (Error, SYM(CoolBit_Set), SYM(Out_Of_Range),
  printf ("CoolBit_Set::operator[](): Bit number %d out of range.\n", n);
  abort ();
}


// find_error -- Raise exception for CoolBit_Set::find() method
// Input:        None
// Output:       None

void CoolBit_Set::find_error (int n) const {
  //RAISE (Error, SYM(CoolBit_Set), SYM(Out_Of_Range),
  printf ("CoolBit_Set::find(): Bit number %d out of range.\n", n);
  abort ();
}


// put_error -- Raise exception for CoolBit_Set::put() method
// Input:       Start, end bit positions
// Output:      None

void CoolBit_Set::put_error (int start, int end) const {
  //RAISE (Error, SYM(CoolBit_Set), SYM(Invalid_Start_End),
  printf ("CoolBit_Set::put(): Start bit %d greater than end bit %d.\n",
          start, end);
  abort ();
}


// remove_error -- Raise exception for CoolBit_Set::remove() method
// Input:          None
// Output:         None

void CoolBit_Set::remove_error () const {
  //RAISE (Error, SYM(CoolBit_Set), SYM(Invalid_Cpos),
  printf ("CoolBit_Set::remove(): Invalid current position.\n");
  abort ();
}


// rem_start_end_error -- Raise exception for CoolBit_Set::remove(int,int) method
// Input:                 Start, end bit positions
// Output:                None

void CoolBit_Set::rem_start_end_error (int start, int end) const {
  //RAISE (Error, SYM(CoolBit_Set), SYM(Invalid_Start_End),
  printf ("CoolBit_Set::remove(): Start bit %d greater than end bit %d.\n",
          start, end);
  abort ();
}


// void set_growth_ratio (float) -- Set the growth percentage for the Vector
//                                  object.
// Input:                           Float ratio, type
// Output:                          None

void CoolBit_Set::set_growth_ratio (float ratio) {
#if ERROR_CHECKING
  if (ratio <= 0.0) {                           // If non-positive growth
    //RAISE (Error, SYM(CoolBit_Set), SYM(Negative_Ratio),
    printf ("CoolBit_Set::set_growth_ratio(): Negative growth ratio %f.\n",
            ratio);
    abort ();
  }
#endif
  this->growth_ratio = ratio;                   // Adjust ration
}


// void set_alloc_size (int) -- Set the default allocation size growth rate.
// Input:                       Growth size in number of elements, type
// Output:                      None

void CoolBit_Set::set_alloc_size (int n) {
#if ERROR_CHECKING
  if (n < 0) {                                  // If index out of range
    //RAISE (Error, SYM(CoolBit_Set), SYM(Negative_Size),
    printf ("CoolBit_Set::set_alloc_size(): Negative growth size %d.\n", n);
    abort ();
  }
#endif
  this->alloc_size_s = n;                       // Set growth size
}