464 lines
12 KiB
C++
464 lines
12 KiB
C++
// Jason Rohrer
|
|
// SimpleVector.h
|
|
|
|
/**
|
|
*
|
|
* Simple vector template class. Supports pushing at end and random-access deletions.
|
|
* Dynamically sized.
|
|
*
|
|
*
|
|
* Created 10-24-99
|
|
* Mods:
|
|
* Jason Rohrer 12-11-99 Added deleteAll function
|
|
* Jason Rohrer 1-30-2000 Changed to return NULL if get called on non-existent element
|
|
* Jason Rohrer 12-20-2000 Added a function for deleting a particular
|
|
* element.
|
|
* Jason Rohrer 12-14-2001 Added a function for getting the index of
|
|
* a particular element.
|
|
* Jason Rohrer 1-24-2003 Added a functions for getting an array or
|
|
* string of all elements.
|
|
* Jason Rohrer 7-26-2005 Added template <> to explicitly specialized
|
|
* getElementString.
|
|
* Jason Rohrer 1-9-2009 Added setElementString method.
|
|
* Jason Rohrer 9-7-2009 Fixed int types.
|
|
* Added appendElementString.
|
|
* Jason Rohrer 11-11-2009 Changed second deleteElement to allow
|
|
* SimpleVectors containing ints.
|
|
* Jason Rohrer 12-23-2009 New push_back for arrays.
|
|
* Jason Rohrer 1-5-2010 Reduced default size to conserve memory.
|
|
* Jason Rohrer 1-12-2010 Added copy constructor and assignment
|
|
* operator.
|
|
* Jason Rohrer 1-16-2010 Fixed bugs in new constructor/operator.
|
|
* Jason Rohrer 1-18-2010 Fixed memmove/memcpy bugs.
|
|
* Jason Rohrer 1-28-2010 Data protected for subclass access.
|
|
* Jason Rohrer 4-28-2010 Fast version of getElement.
|
|
* Jason Rohrer 5-14-2010 String parameters as const to fix warnings.
|
|
*/
|
|
|
|
#include "minorGems/common.h"
|
|
|
|
|
|
|
|
#ifndef SIMPLEVECTOR_INCLUDED
|
|
#define SIMPLEVECTOR_INCLUDED
|
|
|
|
#include <string.h> // for memory moving functions
|
|
|
|
|
|
const int defaultStartSize = 2;
|
|
|
|
template <class Type>
|
|
class SimpleVector {
|
|
public:
|
|
|
|
SimpleVector(); // create an empty vector
|
|
SimpleVector(int sizeEstimate); // create an empty vector with a size estimate
|
|
|
|
~SimpleVector();
|
|
|
|
|
|
// copy constructor
|
|
SimpleVector( const SimpleVector &inCopy );
|
|
|
|
// assignment operator
|
|
SimpleVector & operator = (const SimpleVector &inOther );
|
|
|
|
|
|
|
|
|
|
void push_back(Type x); // add x to the end of the vector
|
|
|
|
// add array of elements to the end of the vector
|
|
void push_back(Type *inArray, int inLength);
|
|
|
|
|
|
Type *getElement(int index); // get a ptr to element at index in vector
|
|
|
|
Type *getElementFast(int index); // no bounds checking
|
|
|
|
|
|
int size(); // return the number of allocated elements in the vector
|
|
|
|
bool deleteElement(int index); // delete element at an index in vector
|
|
|
|
/**
|
|
* Deletes a particular element. Deletes the first element
|
|
* in vector == to inElement.
|
|
*
|
|
* @param inElement the element to delete.
|
|
*
|
|
* @return true iff an element was deleted.
|
|
*/
|
|
bool deleteElementEqualTo( Type inElement );
|
|
|
|
|
|
|
|
/**
|
|
* Gets the index of a particular element. Gets the index of the
|
|
* first element in vector == to inElement.
|
|
*
|
|
* @param inElement the element to get the index of.
|
|
*
|
|
* @return the index if inElement, or -1 if inElement is not found.
|
|
*/
|
|
int getElementIndex( Type inElement );
|
|
|
|
|
|
|
|
void deleteAll(); // delete all elements from vector
|
|
|
|
|
|
|
|
/**
|
|
* Gets the elements as an array.
|
|
*
|
|
* @return the a new array containing all elements in this vector.
|
|
* Must be destroyed by caller, though elements themselves are
|
|
* not copied.
|
|
*/
|
|
Type *getElementArray();
|
|
|
|
|
|
|
|
/**
|
|
* Gets the char elements as a \0-terminated string.
|
|
*
|
|
* @return a \0-terminated string containing all elements in this
|
|
* vector.
|
|
* Must be destroyed by caller.
|
|
*/
|
|
char *getElementString();
|
|
|
|
|
|
/**
|
|
* Sets the char elements as a \0-terminated string.
|
|
*
|
|
* @param inString a \0-terminated string containing all elements to
|
|
* set this vector with.
|
|
* Must be destroyed by caller.
|
|
*/
|
|
void setElementString( const char *inString );
|
|
|
|
|
|
|
|
/**
|
|
* Appends chars from a \0-terminated string.
|
|
*
|
|
* @param inString a \0-terminated string containing all elements to
|
|
* append to this vector.
|
|
* Must be destroyed by caller.
|
|
*/
|
|
void appendElementString( const char *inString );
|
|
|
|
|
|
|
|
protected:
|
|
Type *elements;
|
|
int numFilledElements;
|
|
int maxSize;
|
|
int minSize; // number of allocated elements when vector is empty
|
|
};
|
|
|
|
|
|
template <class Type>
|
|
inline SimpleVector<Type>::SimpleVector() {
|
|
elements = new Type[defaultStartSize];
|
|
numFilledElements = 0;
|
|
maxSize = defaultStartSize;
|
|
minSize = defaultStartSize;
|
|
}
|
|
|
|
template <class Type>
|
|
inline SimpleVector<Type>::SimpleVector(int sizeEstimate) {
|
|
elements = new Type[sizeEstimate];
|
|
numFilledElements = 0;
|
|
maxSize = sizeEstimate;
|
|
minSize = sizeEstimate;
|
|
}
|
|
|
|
template <class Type>
|
|
inline SimpleVector<Type>::~SimpleVector() {
|
|
delete [] elements;
|
|
}
|
|
|
|
|
|
|
|
// copy constructor
|
|
template <class Type>
|
|
inline SimpleVector<Type>::SimpleVector( const SimpleVector<Type> &inCopy )
|
|
: elements( new Type[ inCopy.maxSize ] ),
|
|
numFilledElements( inCopy.numFilledElements ),
|
|
maxSize( inCopy.maxSize ), minSize( inCopy.minSize ) {
|
|
|
|
// if these objects contain pointers to stack, etc, this is not
|
|
// going to work (not a deep copy)
|
|
// because it won't invoke the copy constructors of the objects!
|
|
//memcpy( elements, inCopy.elements, sizeof( Type ) * numFilledElements );
|
|
|
|
for( int i=0; i<inCopy.numFilledElements; i++ ) {
|
|
elements[i] = inCopy.elements[i];
|
|
}
|
|
|
|
}
|
|
|
|
|
|
|
|
// assignment operator
|
|
template <class Type>
|
|
inline SimpleVector<Type> & SimpleVector<Type>::operator = (
|
|
const SimpleVector<Type> &inOther ) {
|
|
|
|
// pattern found on wikipedia:
|
|
|
|
// avoid self-assignment
|
|
if( this != &inOther ) {
|
|
|
|
// 1: allocate new memory and copy the elements
|
|
Type *newElements = new Type[ inOther.maxSize ];
|
|
|
|
// again, memcpy doesn't work here, because it doesn't invoke
|
|
// copy constructor on contained object
|
|
/*memcpy( newElements, inOther.elements,
|
|
sizeof( Type ) * inOther.numFilledElements );
|
|
*/
|
|
for( int i=0; i<inOther.numFilledElements; i++ ) {
|
|
newElements[i] = inOther.elements[i];
|
|
}
|
|
|
|
|
|
// 2: deallocate old memory
|
|
delete [] elements;
|
|
|
|
// 3: assign the new memory to the object
|
|
elements = newElements;
|
|
numFilledElements = inOther.numFilledElements;
|
|
maxSize = inOther.maxSize;
|
|
minSize = inOther.minSize;
|
|
}
|
|
|
|
// by convention, always return *this
|
|
return *this;
|
|
}
|
|
|
|
|
|
|
|
|
|
|
|
|
|
template <class Type>
|
|
inline int SimpleVector<Type>::size() {
|
|
return numFilledElements;
|
|
}
|
|
|
|
template <class Type>
|
|
inline Type *SimpleVector<Type>::getElement(int index) {
|
|
if( index < numFilledElements && index >=0 ) {
|
|
return &(elements[index]);
|
|
}
|
|
else return NULL;
|
|
}
|
|
|
|
|
|
template <class Type>
|
|
inline Type *SimpleVector<Type>::getElementFast(int index) {
|
|
return &(elements[index]);
|
|
}
|
|
|
|
|
|
template <class Type>
|
|
inline bool SimpleVector<Type>::deleteElement(int index) {
|
|
if( index < numFilledElements) { // if index valid for this vector
|
|
|
|
if( index != numFilledElements - 1) {
|
|
// this spot somewhere in middle
|
|
|
|
|
|
|
|
// memmove NOT okay here, because it leaves shallow copies
|
|
// behind that cause errors when the whole element array is
|
|
// destroyed.
|
|
|
|
/*
|
|
// move memory towards front by one spot
|
|
int sizeOfElement = sizeof(Type);
|
|
|
|
int numBytesToMove = sizeOfElement*(numFilledElements - (index+1));
|
|
|
|
Type *destPtr = &(elements[index]);
|
|
Type *srcPtr = &(elements[index+1]);
|
|
|
|
memmove( (void *)destPtr, (void *)srcPtr,
|
|
(unsigned int)numBytesToMove);
|
|
*/
|
|
|
|
|
|
for( int i=index+1; i<numFilledElements; i++ ) {
|
|
elements[i - 1] = elements[i];
|
|
}
|
|
}
|
|
|
|
numFilledElements--; // one less element in vector
|
|
return true;
|
|
}
|
|
else { // index not valid for this vector
|
|
return false;
|
|
}
|
|
}
|
|
|
|
|
|
template <class Type>
|
|
inline bool SimpleVector<Type>::deleteElementEqualTo( Type inElement ) {
|
|
int index = getElementIndex( inElement );
|
|
if( index != -1 ) {
|
|
return deleteElement( index );
|
|
}
|
|
else {
|
|
return false;
|
|
}
|
|
}
|
|
|
|
|
|
|
|
template <class Type>
|
|
inline int SimpleVector<Type>::getElementIndex( Type inElement ) {
|
|
// walk through vector, looking for first match.
|
|
for( int i=0; i<numFilledElements; i++ ) {
|
|
if( elements[i] == inElement ) {
|
|
return i;
|
|
}
|
|
}
|
|
|
|
// no element found
|
|
return -1;
|
|
}
|
|
|
|
|
|
|
|
template <class Type>
|
|
inline void SimpleVector<Type>::deleteAll() {
|
|
numFilledElements = 0;
|
|
if( maxSize > minSize ) { // free memory if vector has grown
|
|
delete [] elements;
|
|
elements = new Type[minSize]; // reallocate an empty vector
|
|
maxSize = minSize;
|
|
}
|
|
}
|
|
|
|
|
|
template <class Type>
|
|
inline void SimpleVector<Type>::push_back(Type x) {
|
|
if( numFilledElements < maxSize) { // still room in vector
|
|
elements[numFilledElements] = x;
|
|
numFilledElements++;
|
|
}
|
|
else { // need to allocate more space for vector
|
|
int newMaxSize = maxSize << 1; // double size
|
|
|
|
// NOTE: memcpy does not work here, because it does not invoke
|
|
// copy constructors on elements.
|
|
// And then "delete []" below causes destructors to be invoked
|
|
// on old elements, which are shallow copies of new objects.
|
|
|
|
Type *newAlloc = new Type[newMaxSize];
|
|
/*
|
|
unsigned int sizeOfElement = sizeof(Type);
|
|
unsigned int numBytesToMove = sizeOfElement*(numFilledElements);
|
|
|
|
|
|
// move into new space
|
|
memcpy((void *)newAlloc, (void *) elements, numBytesToMove);
|
|
*/
|
|
|
|
// must use element-by-element assignment to invoke constructors
|
|
for( int i=0; i<numFilledElements; i++ ) {
|
|
newAlloc[i] = elements[i];
|
|
}
|
|
|
|
|
|
// delete old space
|
|
delete [] elements;
|
|
|
|
elements = newAlloc;
|
|
maxSize = newMaxSize;
|
|
|
|
elements[numFilledElements] = x;
|
|
numFilledElements++;
|
|
}
|
|
}
|
|
|
|
|
|
|
|
template <class Type>
|
|
inline void SimpleVector<Type>::push_back(Type *inArray, int inLength) {
|
|
|
|
for( int i=0; i<inLength; i++ ) {
|
|
push_back( inArray[i] );
|
|
}
|
|
}
|
|
|
|
|
|
|
|
template <class Type>
|
|
inline Type *SimpleVector<Type>::getElementArray() {
|
|
Type *newAlloc = new Type[ numFilledElements ];
|
|
|
|
// shallow copy not good enough!
|
|
/*
|
|
unsigned int sizeOfElement = sizeof( Type );
|
|
unsigned int numBytesToCopy = sizeOfElement * numFilledElements;
|
|
|
|
// copy into new space
|
|
//memcpy( (void *)newAlloc, (void *)elements, numBytesToCopy );
|
|
*/
|
|
|
|
// use assignment to ensure that constructors are invoked on element copies
|
|
for( int i=0; i<numFilledElements; i++ ) {
|
|
newAlloc[i] = elements[i];
|
|
}
|
|
|
|
return newAlloc;
|
|
}
|
|
|
|
|
|
|
|
template <>
|
|
inline char *SimpleVector<char>::getElementString() {
|
|
char *newAlloc = new char[ numFilledElements + 1 ];
|
|
unsigned int sizeOfElement = sizeof( char );
|
|
unsigned int numBytesToCopy = sizeOfElement * numFilledElements;
|
|
|
|
// memcpy fine here, since shallow copy good enough for chars
|
|
// copy into new space
|
|
memcpy( (void *)newAlloc, (void *)elements, numBytesToCopy );
|
|
|
|
newAlloc[ numFilledElements ] = '\0';
|
|
|
|
return newAlloc;
|
|
}
|
|
|
|
|
|
template <>
|
|
inline void SimpleVector<char>::appendElementString( const char *inString ) {
|
|
// slow but correct
|
|
|
|
unsigned int numChars = strlen( inString );
|
|
for( unsigned int i=0; i<numChars; i++ ) {
|
|
push_back( inString[i] );
|
|
}
|
|
}
|
|
|
|
|
|
|
|
template <>
|
|
inline void SimpleVector<char>::setElementString( const char *inString ) {
|
|
deleteAll();
|
|
|
|
appendElementString( inString );
|
|
}
|
|
|
|
|
|
|
|
|
|
|
|
|
|
#endif
|