Logo Search packages:      
Sourcecode: passage version File versions  Download package

SimpleVector.h

// 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.
*/

#include "minorGems/common.h"



#ifndef SIMPLEVECTOR_INCLUDED
#define SIMPLEVECTOR_INCLUDED

#include <string.h>           // for memory moving functions


const int defaultStartSize = 50;

template <class Type>
class SimpleVector {
      public:
      
            SimpleVector();         // create an empty vector
            SimpleVector(int sizeEstimate); // create an empty vector with a size estimate
            
            ~SimpleVector();
            
            
            void push_back(Type x);       // add x to the end of the vector
            
            Type *getElement(int index);        // get a ptr to element at index in vector
            
            
            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 deleteElement( 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();


        
      private:
            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;
      }     

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 bool SimpleVector<Type>::deleteElement(int index) {
      if( index < numFilledElements) {    // if index valid for this vector
            
            if( index != numFilledElements - 1)  {    // this spot somewhere in middle
            
                  // 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, numBytesToMove);
                  }
                  
            numFilledElements--;    // one less element in vector
            return true;
            }
      else {                        // index not valid for this vector
            return false;
            }
      }


template <class Type>
inline bool SimpleVector<Type>::deleteElement( 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
            
            Type *newAlloc = new Type[newMaxSize];
            int sizeOfElement = sizeof(Type);
            int numBytesToMove = sizeOfElement*(numFilledElements);
            
            // move into new space
            memcpy((void *)newAlloc, (void *) elements, numBytesToMove);
            
            // delete old space
            delete [] elements;
            
            elements = newAlloc;
            maxSize = newMaxSize;   
            
            elements[numFilledElements] = x;
            numFilledElements++;    
            }
      }



template <class Type>
inline Type *SimpleVector<Type>::getElementArray() {
    Type *newAlloc = new Type[ numFilledElements ];
    int sizeOfElement = sizeof( Type );
    int numBytesToCopy = sizeOfElement * numFilledElements;
            
    // copy into new space
    memcpy( (void *)newAlloc, (void *)elements, numBytesToCopy );

    return newAlloc;
    }



template <>
inline char *SimpleVector<char>::getElementString() {
    char *newAlloc = new char[ numFilledElements + 1 ];
    int sizeOfElement = sizeof( char );
    int numBytesToCopy = sizeOfElement * numFilledElements;
            
    // copy into new space
    memcpy( (void *)newAlloc, (void *)elements, numBytesToCopy );

    newAlloc[ numFilledElements ] = '\0';
    
    return newAlloc;
    }



#endif

Generated by  Doxygen 1.6.0   Back to index