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