vector.c

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

  register size_t i = start;
  register size_t n = this->number_elements - start; // max number of elmts to search
  if (dir == -1) n = start + 1;
  for (; n > 0; n--, i += dir)
    if ((*(this->compare_s))(this->data[i], value) == TRUE) {
      this->curpos = i;
      return TRUE;
    }
  return FALSE;
}

// void grow () -- Adjust the memory size of a CoolVector to accomodate some size
// Input:            Interger number of elements to hold
// Output:           None

template<class Type> 
void CoolVector<Type>::grow (size_t min_size) {
  size_t new_size = (size_t)(this->size * (1.0 + growth_ratio)); // New size?
  if (new_size < min_size) new_size = min_size + alloc_size;
  resize(new_size);
}

// void resize () -- Adjust the memory size of a CoolVector to accomodate some size
// Input:            Interger number of elements to hold
// Output:           None

template<class Type> 
void CoolVector<Type>::resize (size_t new_size) {
  if (new_size <= this->size) {                 // Don't bother shrinking
#if ERROR_CHECKING  
    if (new_size < 0)                           // If index out of range
      this->resize_error (#Type,new_size);      // Raise exception
#endif
    return;
  }
#if ERROR_CHECKING  
  if (alloc_size == INVALID_ALLOCSZ())                  // If static size vector
    this->static_error (#Type);                 // Raise exception
#endif
  Type* temp = new Type[new_size];              // Allocate storage
  for (size_t i = 0; i < this->number_elements; i++)// For each element in Vector
    temp[i] = this->data[i];                    // Copy into new storage
  if (this->size != 0)
    delete [] this->data;                       // Free up old memory
  this->data = temp;                            // Assign new memory block
  this->size = new_size;                        // Save new size value
}


// push -- Add element to end of the CoolVector
// Input:  Type reference
// Output: TRUE if successful, FALSE if could not grow vector

template<class Type> 
Boolean CoolVector<Type>::push (const Type& value) {
  if (this->number_elements == this->size) {    // If not enough memory
    if (this->alloc_size == INVALID_ALLOCSZ())          // If not allowed to grow
      return FALSE;                             // Return failure flag
    this->grow(this->size+1);                   // Else grow the CoolVector
  }
  this->curpos = this->number_elements;         // Set current position
  this->data[this->number_elements++] = value;  // Assign new value
  return TRUE;                                  // Return success status
}


// push_new -- Add an element if it is not already there
// Input:      Reference to Type
// Output:     TRUE/FALSE

template<class Type> 
Boolean CoolVector<Type>::push_new (const Type& value) {
  if (this->number_elements == this->size && this->alloc_size == INVALID_ALLOCSZ())
    return FALSE;                               // Return failure flag
  if (this->find(value, this->number_elements-1, -1)) 
    return FALSE;               // If already in CoolVector
  if (this->number_elements >= this->size)      // If not enough memory
    this->grow(this->size+1);                   // Else grow the Vector
  this->curpos = this->number_elements;         // Set current position
  this->data[this->number_elements++] = value;  // Assign new value
  return TRUE;                                  // Return success status
}


// pop --   Return last element in the CoolVector
// Input:   None
// Output:  Type reference to last element in CoolVector

template<class Type> 
Type& CoolVector<Type>::pop () {
  if (this->number_elements > 0) {              // If there are elements
    this->curpos = INVALID_POS();                       // Invalidate current position
    return (this->data[--this->number_elements]); // Return the last one
  }
   return (this->data[0]); // Return an arbitrary one
}


// reverse -- Destructively reverse the order of elements in a CoolVector
// Input:     None
// Output:    None

template<class Type> 
void CoolVector<Type>::reverse () {
  Type temp;
  for (size_t i = 0, j = this->number_elements-1;       // Counting from front and rear
       i < this->number_elements / 2; i++, j--) { // until we reach the middle
    temp = this->data[i];                       // Save front data item
    this->data[i] = this->data[j];              // Switch with rear data item
    this->data[j] = temp;                       // Copy new rear data item
  }
  this->curpos = INVALID_POS();                 // Invalidate current position
}


// remove -- Destructively remove item at current position.
//           Shift remaining elmts to preserve order in vector.
// Input:   None
// Output:  Type reference to item removed

template<class Type> 
Type CoolVector<Type>::remove () {
  IterState i = this->curpos;
  if (i == INVALID_POS()) this->remove_error("Type");
  Type value = this->data[i];
  Type* elmts = &this->data[i];                 // Shift elements by 1 place
  while (++i < this->number_elements) {         // Copy over current
    *elmts = *(elmts + 1);              // Use assignment of class Type
    elmts++;            // Use assignment of class Type
  }
  this->number_elements--;                      // Update element count
  if (this->curpos == this->number_elements)    // If past end of vector
    this->curpos = INVALID_POS();                       // Invalidate current position
  return value;                                 // Return Vector reference
}


// remove -- Destructively remove the first occurrence of an element
// Input:   Type reference
// Output:  TRUE if element found and removed, FALSE otherwise

template<class Type> 
Boolean CoolVector<Type>::remove (const Type& value, int dir) {
  size_t start = 0;
  if (dir == -1) start = this->number_elements - 1;
  if (this->find(value, start, dir)) {          // When found
    size_t i = this->curpos;
    Type* elmts = &this->data[i];               // Shifts remaining elements
    while (++i < this->number_elements) {       // by 1 place
      *elmts = *(elmts + 1);            // Use assignment of class Type
      elmts++;          // Use assignment of class Type
    }
    this->number_elements--;                    // Update element count
    return TRUE;
  } else 
    return FALSE;
}


// remove_duplicates -- Destructively remove duplicate elements from CoolVector
// Input:               None
// Output:              TRUE if any removed, FALSE otherwise

template<class Type> 
Boolean CoolVector<Type>::remove_duplicates () {
  this->curpos = INVALID_POS();                 // Invalidate current position
  if (this->size == 0) return FALSE;
  Boolean success = FALSE;                      // Return value
  Type* old = this->data;                       // Old data
  this->data = new Type[this->size];            // New data
  size_t n = this->number_elements;             // length of old data
  this->number_elements = 0;
  for (size_t i = 0; i < n; i++) {              // For each element
    if (!this->find(old[i], this->number_elements-1, -1)) { // if not copied yet
      this->data[this->number_elements++] = old[i]; // copy value
      success = TRUE;                           // Set flag
    }
  }
  delete [] old;                                // destroy old data
  return success;
}


// replace -- Destructively replace the first occurrence of an element
// Input:     Two Type references
// Output:    TRUE if element found and replaced, FALSE otherwise

template<class Type> 
Boolean CoolVector<Type>::replace (const Type& t1, const Type& t2, int dir) {
  size_t start = 0;
  if (dir == -1) start = this->number_elements -1;
  if (this->find(t1, start, dir)) {
    this->data[this->curpos] = t2;              
    if (dir == +1) this->curpos++;              // Point to item after replace
    else this->curpos--;                        // in direction of dir
    if (this->curpos > this->number_elements) this->curpos = INVALID_POS();
    return TRUE;
  } else return FALSE;
}


// replace_all -- Destructively replace all occurrences of an element
// Input:         Two Type references
// Output:        TRUE if any element replaced, FALSE otherwise

template<class Type> 
Boolean CoolVector<Type>::replace_all (const Type& t1, const Type& t2) {
  Boolean success = FALSE;                      // Return value
  this->curpos = 0;
  for (;;) {
    if (!this->find(t1, this->curpos, +1)) return success;
    this->data[this->curpos++] = t2;            // Point to item after replace
    if (this->curpos > this->number_elements) this->curpos = INVALID_POS();
  }
}


// prepend -- Destructively insert the elements of some CoolVector at the beginning
// Input:     CoolVector reference
// Output:    TRUE if successful, FALSE if could not grow CoolVector

template<class Type> 
Boolean CoolVector<Type>::prepend (const CoolVector<Type>& v) {
  Type* temp;                                   // Declare temporary
  size_t old_size = this->size;                 // Keep old size
  size_t new_size = this->number_elements + v.number_elements; // Minimum size
  if (this->size < new_size) {                  // Enough memory?
    if (this->alloc_size == INVALID_ALLOCSZ())          // If not allowed to grow
      return FALSE;                             // Return failure flag
    this->size = (size_t)(this->size * (1.0 + growth_ratio)); // New size
    if (this->size < new_size)                  // If not enough
      this->size = new_size + this->alloc_size; // use alloc_size
  }
  temp = new Type[this->size];                  // Allocate required storage
  size_t i;
  for (i = 0; i < v.number_elements; i++)        // For all elements
    temp[i] = v.data[i];                        // Copy to beginning of CoolVector
  this->curpos = i;                             // Set current position
  for (i = 0; i < this->number_elements; i++)   // For each element
    temp[i+v.number_elements] = this->data[i];  // Copy into new storage
  if (old_size != 0)
    delete [] this->data;                       // Free up old memory
  this->data = temp;                            // Assign new memory block
  this->number_elements += v.number_elements;   // Update element count
  return TRUE;                                  // Return success flag
}


// append -- Destructively append the elements of some CoolVector at the beginning
// Input:    CoolVector reference
// Output:   TRUE if successful, FALSE if could not grow CoolVector

template<class Type> 
Boolean CoolVector<Type>::append (const CoolVector<Type>& v) {
  size_t new_size = this->number_elements + v.number_elements; // Minimum size
  if (this->size < new_size) {                  // Enough memory?
    if (this->alloc_size == INVALID_ALLOCSZ())          // If not allowed to grow
      return FALSE;                             // Return failure flag
    this->grow(new_size);
  }
  this->curpos = this->number_elements - 1;     // Set current position
  for (size_t i = 0; i < v.number_elements; i++)        // For each element
    this->data[i+this->number_elements] = v.data[i]; // Copy to end of CoolVector
  this->number_elements += v.number_elements;   // Update element count
  return TRUE;                                  // Return CoolVector reference
}


// insert_before -- Destructively insert an element before current position
// Input:           Type reference
// Output:          TRUE if successful, FALSE if could not grow CoolVector

template<class Type> 
Boolean CoolVector<Type>::insert_before (const Type&  value) {
  if (this->curpos == INVALID_POS())                    // If no current position
    return FALSE;                               // Return failure flag
  return this->insert_before(value, this->curpos);
}


// insert_after -- Destructively insert an element after current position
// Input:          Type reference
// Output:         TRUE if successful, FALSE if could not grow CoolVector

template<class Type> 
Boolean CoolVector<Type>::insert_after (const Type&  value) {
  if (this->curpos == INVALID_POS())                    // If no current position
    return FALSE;                               // Return failure flag
  return this->insert_after(value, this->curpos);