6
* Simple vector template class. Supports pushing at end and random-access deletions.
12
* Jason Rohrer 12-11-99 Added deleteAll function
13
* Jason Rohrer 1-30-2000 Changed to return NULL if get called on non-existent element
14
* Jason Rohrer 12-20-2000 Added a function for deleting a particular
16
* Jason Rohrer 12-14-2001 Added a function for getting the index of
17
* a particular element.
18
* Jason Rohrer 1-24-2003 Added a functions for getting an array or
19
* string of all elements.
20
* Jason Rohrer 7-26-2005 Added template <> to explicitly specialized
22
* Jason Rohrer 1-9-2009 Added setElementString method.
25
#include "minorGems/common.h"
29
#ifndef SIMPLEVECTOR_INCLUDED
30
#define SIMPLEVECTOR_INCLUDED
32
#include <string.h> // for memory moving functions
35
const int defaultStartSize = 50;
41
SimpleVector(); // create an empty vector
42
SimpleVector(int sizeEstimate); // create an empty vector with a size estimate
47
void push_back(Type x); // add x to the end of the vector
49
Type *getElement(int index); // get a ptr to element at index in vector
52
int size(); // return the number of allocated elements in the vector
54
bool deleteElement(int index); // delete element at an index in vector
57
* Deletes a particular element. Deletes the first element
58
* in vector == to inElement.
60
* @param inElement the element to delete.
62
* @return true iff an element was deleted.
64
bool deleteElement( Type inElement );
69
* Gets the index of a particular element. Gets the index of the
70
* first element in vector == to inElement.
72
* @param inElement the element to get the index of.
74
* @return the index if inElement, or -1 if inElement is not found.
76
int getElementIndex( Type inElement );
80
void deleteAll(); // delete all elements from vector
85
* Gets the elements as an array.
87
* @return the a new array containing all elements in this vector.
88
* Must be destroyed by caller, though elements themselves are
91
Type *getElementArray();
96
* Gets the char elements as a \0-terminated string.
98
* @return a \0-terminated string containing all elements in this
100
* Must be destroyed by caller.
102
char *getElementString();
106
* Sets the char elements as a \0-terminated string.
108
* @param inString a \0-terminated string containing all elements to
110
* Must be destroyed by caller.
112
void setElementString( char *inString );
117
int numFilledElements;
119
int minSize; // number of allocated elements when vector is empty
123
template <class Type>
124
inline SimpleVector<Type>::SimpleVector() {
125
elements = new Type[defaultStartSize];
126
numFilledElements = 0;
127
maxSize = defaultStartSize;
128
minSize = defaultStartSize;
131
template <class Type>
132
inline SimpleVector<Type>::SimpleVector(int sizeEstimate) {
133
elements = new Type[sizeEstimate];
134
numFilledElements = 0;
135
maxSize = sizeEstimate;
136
minSize = sizeEstimate;
139
template <class Type>
140
inline SimpleVector<Type>::~SimpleVector() {
144
template <class Type>
145
inline int SimpleVector<Type>::size() {
146
return numFilledElements;
149
template <class Type>
150
inline Type *SimpleVector<Type>::getElement(int index) {
151
if( index < numFilledElements && index >=0 ) {
152
return &(elements[index]);
158
template <class Type>
159
inline bool SimpleVector<Type>::deleteElement(int index) {
160
if( index < numFilledElements) { // if index valid for this vector
162
if( index != numFilledElements - 1) { // this spot somewhere in middle
164
// move memory towards front by one spot
165
int sizeOfElement = sizeof(Type);
167
int numBytesToMove = sizeOfElement*(numFilledElements - (index+1));
169
Type *destPtr = &(elements[index]);
170
Type *srcPtr = &(elements[index+1]);
172
memmove((void *)destPtr, (void *)srcPtr, numBytesToMove);
175
numFilledElements--; // one less element in vector
178
else { // index not valid for this vector
184
template <class Type>
185
inline bool SimpleVector<Type>::deleteElement( Type inElement ) {
186
int index = getElementIndex( inElement );
188
return deleteElement( index );
197
template <class Type>
198
inline int SimpleVector<Type>::getElementIndex( Type inElement ) {
199
// walk through vector, looking for first match.
200
for( int i=0; i<numFilledElements; i++ ) {
201
if( elements[i] == inElement ) {
212
template <class Type>
213
inline void SimpleVector<Type>::deleteAll() {
214
numFilledElements = 0;
215
if( maxSize > minSize ) { // free memory if vector has grown
217
elements = new Type[minSize]; // reallocate an empty vector
223
template <class Type>
224
inline void SimpleVector<Type>::push_back(Type x) {
225
if( numFilledElements < maxSize) { // still room in vector
226
elements[numFilledElements] = x;
229
else { // need to allocate more space for vector
230
int newMaxSize = maxSize << 1; // double size
232
Type *newAlloc = new Type[newMaxSize];
233
int sizeOfElement = sizeof(Type);
234
int numBytesToMove = sizeOfElement*(numFilledElements);
236
// move into new space
237
memcpy((void *)newAlloc, (void *) elements, numBytesToMove);
243
maxSize = newMaxSize;
245
elements[numFilledElements] = x;
252
template <class Type>
253
inline Type *SimpleVector<Type>::getElementArray() {
254
Type *newAlloc = new Type[ numFilledElements ];
255
int sizeOfElement = sizeof( Type );
256
int numBytesToCopy = sizeOfElement * numFilledElements;
258
// copy into new space
259
memcpy( (void *)newAlloc, (void *)elements, numBytesToCopy );
267
inline char *SimpleVector<char>::getElementString() {
268
char *newAlloc = new char[ numFilledElements + 1 ];
269
int sizeOfElement = sizeof( char );
270
int numBytesToCopy = sizeOfElement * numFilledElements;
272
// copy into new space
273
memcpy( (void *)newAlloc, (void *)elements, numBytesToCopy );
275
newAlloc[ numFilledElements ] = '\0';
283
inline void SimpleVector<char>::setElementString( char *inString ) {
288
int numChars = strlen( inString );
289
for( int i=0; i<numChars; i++ ) {
290
push_back( inString[i] );
added
removed
minorGems/util/SimpleVector.h
