vector.c

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

}


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

template<class Type> 
Boolean CoolVector<Type>::insert_before (const Type&  value, size_t index) {
  size_t n = this->number_elements+1;
  if (n >= this->size) {                        // If not enough memory
    if (this->alloc_size == INVALID_ALLOCSZ())          // If not allowed to grow
      return FALSE;                             // Return failure flag
    this->grow(n);
  }
  this->curpos = index;                         // Current position at insertion
  Type* elmts = &this->data[n-1];               // Use operator= of Type
  while (--n > index) {                         // shift elements by 1 place
    *elmts = *(elmts - 1);                      // Copy over current
    elmts--;
  }    
  this->data[this->curpos] = value;             // Assign new value
  this->number_elements++;
  return TRUE;                                  // Return CoolVector reference
}


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

template<class Type> 
Boolean CoolVector<Type>::insert_after (const Type&  value, size_t index) {
  size_t n = this->number_elements+1;
  if (n >= this->size) {                        // If not enough memory
    if (this->alloc_size == INVALID_ALLOCSZ())          // If not allowed to grow
      return FALSE;                             // Return failure flag
    this->grow(n);
  }
  this->curpos = ++index;                       // Current position at insertion
  Type* elmts = &this->data[n-1];               // Use operator= of Type
  while (--n > index) {                         // shift elements by 1 place
    *elmts = *(elmts - 1);                      // Copy over current
    elmts--;
  }    
  this->data[this->curpos] = value;             // Assign new value
  this->number_elements++;
  return TRUE;                                  // Return CoolVector reference
}



// merge -- Destructively merge two CoolVectors of the same size using a user
//          supplied predicate function. The predicate function returns
//          TRUE if and only if the first element preceeds the second.
// Input:   CoolVector reference and pointer to Predicate function
// Output:  None

template<class Type> 
void CoolVector<Type>::merge(const CoolVector<Type>& v, int (*pred)(const Type&, const Type&)) {
  size_t old_size = this->size;                 // Keep old size
  size_t total = this->number_elements+v.number_elements; // Min space required
  if (this->size < total) {
    this->size = (size_t)(this->size*(1.0+growth_ratio)); // New size by ratio
    if (this->size < total)                           // check growth
      this->size = total + this->alloc_size;          // New size by growth
  }
  Type* temp = new Type[this->size];            // Allocated storage
  for (size_t i=0,j=0,k=0; i < total; i++) {    // For all elements
    if (j >= this->number_elements) {           // If past end of CoolVector
      for (; k < v.number_elements; k++, i++)   // Copy rest of other vector
        temp[i] = v.data[k];                    // Copy element value
      break;                                    // Break out of loop when done
    }
    else if (k >= v.number_elements) {          // If past end of other vector
      for (; j < this->number_elements;j++,i++) // Copy rest of other vector
        temp[i] = this->data[j];                // Copy element value
      break;                                    // Break out of loop when done
    }
    else {
      if ((*pred)(this->data[j], v.data[k]) < 0) // If it goes here
        temp[i] = this->data[j++];              // Copy first element
      else
        temp[i] = v.data[k++];                  // Copy second element
    }
  }
  if (old_size != 0)
    delete [] this->data;                       // Free up old memory
  this->data = temp;                            // Assign new memory block
  this->number_elements = total;                // Update element count
  this->curpos = INVALID_POS();                 // Invalidate current position
}


// sort -- Destructively sort the elements of a vector using the supplied
//         predicate function. The predicate function returns TRUE if and only
//         if the first element preceeds the second. This routine uses the 
//         Heap Sort algorithm as given in "Numerical Recipes in C" p247.
// Input:   Pointer to predicate function
// Output:  None

#ifdef __cplusplus
 
#include <stdlib.h>             // include the standard c library

extern "C" {
typedef int (*_cmp_rtn)( const void *, const void * );
};

template<class Type> 
void CoolVector<Type>::sort (register int (*p)(const Type&, const Type&)) {
  if (this->number_elements > 1)                // If more than one element
    qsort((void*) this->data,
          (size_t)(unsigned int) this->number_elements, (size_t)sizeof(Type),
          (_cmp_rtn) p);
}

#else                                           // Not all machines have qsort

template<class Type> 
void CoolVector<Type>::sort (int (*p)(const Type&, const Type&)) {
  if (this->number_elements > 1) {              // If more than one element
    size_t n = this->number_elements;
    size_t l, j, ir, i;
    Type temp;
    Type* v_prime = this->data - 1;             // Adjust for 1-based index
    l = (n >> 1) + 1;
    ir = n;
    while (TRUE) {
      if (l > 1)
        temp = v_prime[--l];
      else {
        temp = v_prime[ir];
        v_prime[ir] = v_prime[1];
        if (--ir == 1) {
          v_prime[1] = temp;
          break;
        }
      }
      i = l;
      j = i << 1;
      while (j <= ir) {
        if (j < ir && (*p)(v_prime[j], v_prime[j+1]) < 0)
          ++j;
        if ((*p)(temp, v_prime[j]) < 0) {
          v_prime[i] = v_prime[j];
          j += (i = j);
        }
        else
          j = ir + 1;
      }
      v_prime[i] = temp;
    }
    this->curpos = INVALID_POS();                       // Invalidate current position
  }
}
#endif
  
// ostream& operator<< () -- Overload the output operator for CoolVector reference
// Input:                    Ostream reference and CoolVector reference
// Output:                   Ostream reference

template<class Type>
ostream& operator<< (ostream& os, const CoolVector<Type>& v) {
  if (v.length() == 0)                          // If no elements in vector
    os << " Empty ";                            // Indicate empty status
  else {
    os << "[ ";
    for (size_t i = 0; i < v.length(); i++)     // For each element
      os << v.data[i] << " ";                   // Output value to stream
    os << "]";
  }
  return os;                                    // Return ostream reference
}



// shuffle_remove -- Destructively remove item at current position
//           Shuffle last element up to fill hole.
// Input:   None
// Output:  Type reference to item removed

template<class Type> 
Type CoolVector<Type>::shuffle_remove () {
  size_t i = this->curpos;
  if (i == INVALID_POS()) this->remove_error("Type");
  Type value = this->data[i];
  this->data[this->curpos] =                    // fill hole at curpos
    this->data[this->number_elements - 1];      // with last element in vector
  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
}



// shuffle_remove -- Destructively remove the first occurrence of an element
//           Shuffle last element up to fill hole
// Input:   Type reference
// Output:  TRUE if element found and removed, FALSE otherwise

template<class Type> 
Boolean CoolVector<Type>::shuffle_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
    this->data[this->curpos] =                  // fill hole at curpos
      this->data[this->number_elements - 1];    // with last element in vector
    this->number_elements--;                    // Update element count
    return TRUE;
  } else 
    return FALSE;
}


// shuffle_insert_before -- Destructively insert an element before current position
//            Shuffle last element up to fill hole
// Input:           Type reference
// Output:          TRUE if successful, FALSE if could not grow CoolVector

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


// shuffle_insert_after -- Destructively insert an element after current position
//            Shuffle last element up to fill hole
// Input:          Type reference
// Output:         TRUE if successful, FALSE if could not grow CoolVector

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

// shuffle_insert_before -- Destructively insert an element before specified index
//            Shuffle element at current position to end of vector
// Input:           Type reference and an index position
// Output:          TRUE if successful, FALSE if could not grow CoolVector

template<class Type> 
Boolean CoolVector<Type>::shuffle_insert_before (const Type&  value, size_t index) {
  size_t n = this->number_elements+1;
  if (n >= this->size) {                        // If not enough memory
    if (this->alloc_size == INVALID_ALLOCSZ())          // If not allowed to grow
      return FALSE;                             // Return failure flag
    this->grow(n);
  }
  this->curpos = index;                         // Current position at insertion
  this->data[this->number_elements] =           // Move data at curpos
    this->data[this->curpos];                   // to end of vector
  this->data[this->curpos] = value;             // Assign new value
  this->number_elements++;
  return TRUE;                                  // Return CoolVector reference
}



// shuffle_insert_after -- Destructively insert an element after specified index
//            Shuffle element at current position to end of vector
// Input:          Type reference and an index position
// Output:         TRUE if successful, FALSE if could not grow CoolVector

template<class Type> 
Boolean CoolVector<Type>::shuffle_insert_after (const Type&  value, size_t index) {
  size_t n = this->number_elements+1;
  if (n >= this->size) {                        // If not enough memory
    if (this->alloc_size == INVALID_ALLOCSZ())          // If not allowed to grow
      return FALSE;                             // Return failure flag
    this->grow(n);
  }
  this->curpos = ++index;                       // Current position at insertion
  this->data[this->number_elements] =           // Move data at curpos
    this->data[this->curpos];                   // to end of vector
  this->data[this->curpos] = value;             // Assign new value
  this->number_elements++;
  return TRUE;                                  // Return CoolVector reference
}

#endif // VECTORC