Array< T > Class Template Reference

#include <Array.h>

Class Description

template<class T>
class MaxSDK::Array< T >

A generic array container, with proper support for non-POD types.

This template class is a generic, dynamic array container, similar to the STL class "vector". Whereas the classical 3ds Max SDK class Tab supports only POD types, this class supports non-POD types as well.

Note

POD stands for "plain old data", and basically denotes any data type which does not need to be constructed, destructed, and which can be copied with memcpy() rather than requiring a copy operator to be called.

Inheritance diagram for Array< T >:

Public Types
typedef const void *	elem2

Public Member Functions
typedef	int (__cdecl *CompareFnc)(const void *elem1
	Type of function to pass to sort(). More...
	Array ()
	Initializes an empty array. More...
	Array (size_t initUsedLength, const T &defaultVal=T(), size_t initGrowLength=kDefaultGrowthLength)
	Initializes an array with an initial size. More...
	Array (const Array< T > &src)
	Copy constructor. More...
	~Array ()
	Destructor. Destroys every element stored in the array, and frees the allocated storage. More...
Array< T > &	operator= (const Array< T > &src)
	Copy operator. More...
bool	operator== (const Array< T > &op) const
	Equality operator. More...
Array< T > &	setAt (size_t index, const T &value)
	Sets a copy of value at the given index. More...
Array< T > &	setAll (const T &value)
	Sets all the elements of the array to the given value. More...
size_t	append (const T &value)
	Appends a copy of value to the array. More...
Array< T > &	append (const T *values, size_t count)
	Appends one or more element(s) to the array. More...
Array< T > &	append (const Array< T > &array)
	Appends the contents of another array to this array. More...
Array< T > &	insertAt (size_t index, const T &value)
	Inserts a single value, at a given location, into this array. More...
Array< T > &	insertAt (size_t index, const T *values, size_t count)
	Inserts a one or more value(s), at a given location, into this array. More...
Array< T > &	removeAt (size_t index)
	Removes a single element from the array. More...
bool	remove (const T &value, size_t start=0)
	Searches for a value in the array and, if it is found, removes it from the array. More...
Array< T > &	removeFirst ()
	Removes the first element of the array. More...
Array< T > &	removeLast ()
	Removes the last element of the array. More...
Array< T > &	removeAll ()
	Removes all the elements from the array. More...
Array< T > &	removeSubArray (size_t startIndex, size_t endIndex)
	Removes a subset of the array. More...
bool	contains (const T &value, size_t start=0) const
	Determines if a value is stored in the array. More...
bool	find (const T &value, size_t &foundAt, size_t start=0) const
	Searches for a value in the array. More...
size_t	find (const T &value) const
	Searches for a value in the array. More...
size_t	findFrom (const T &value, size_t start) const
	Searches for a value in the array, starting at a given index. More...
size_t	length () const
	Returns the number of used elements (as opposed to simply allocated/reserved) in the array. More...
bool	isEmpty () const
	Returns true if the number of used elements in the array is 0; returns false otherwise. More...
size_t	lengthUsed () const
	Returns the number of elements used (as opposed to simply allocated/reserved) in the array. More...
Array< T > &	setLengthUsed (size_t length, const T &defaultVal=T())
	Sets the number of elements used (as opposed to simply allocated/reserved) in the array. More...
size_t	lengthReserved () const
	Returns the number of elements allocated/reserved (as opposed to actually used) in the array. More...
Array< T > &	setLengthReserved (size_t length)
	Sets the number of elements allocated/reserved (as opposed to actually used) in the array. More...
void	reserve (size_t capacity)
	Alias for setLengthReserved. More...
size_t	growLength () const
	Returns the growth length of the array. More...
Array< T > &	setGrowLength (size_t)
	Sets the growth length of the array. More...
Array< T > &	reverse ()
	Reverses the sequence of elements in the array. More...
Array< T > &	swap (size_t i1, size_t i2)
	Swaps two elements in this array. More...
void	sort (CompareFnc cmp)
	Sorts the elements of the array using a custom comparison function. More...
bool	isValidIndex (size_t) const
	Returns whether the given array index is valid for this array. More...
T &	operator[] (size_t i)
	Subscript operator. More...
const T &	operator[] (size_t i) const
const T &	at (size_t index) const
	Same as subscript operator. More...
T &	at (size_t index)
T &	first ()
	Accesses the first element in the array. More...
const T &	first () const
T &	last ()
	Accesses the last element in the array. More...
const T &	last () const
const T *	asArrayPtr () const
	Returns the array storage as a C-style array pointer. More...
T *	asArrayPtr ()

Protected Types
enum	{ kArrayGrowthThreshold = 0x10000, kDefaultGrowthLength = 8 }

Static Protected Member Functions
static size_t	quickSortPartition (T *data, size_t first, size_t last, CompareFnc cmp)
	The partition portion of the QuickSort algorithm. More...
static void	quickSortRecursive (T *data, size_t first, size_t last, CompareFnc cmp)
	Recursive QuickSort function used to sort the elements of the array. More...
static void	handleOutOfMemory ()
	Utility function, called when the array fails to allocate memory. More...
static T *	ArrayAllocate (size_t len)
	Allocates an array of elements without constructing them. More...
static void	ArrayConstruct (T *arrayBegin, size_t len, const T &defaultVal)
	Constructs an array of elements. More...
static void	ArrayDeAllocate (T *arrayBegin)
	De-allocates an array of elements without destructing them. More...
static void	ArrayDestruct (T *arrayBegin, size_t len)
	Destructs an array of elements. More...
static void	ArrayCopy (T *pCopy, const T *pSource, size_t nCount)
	Copies an array of elements to an already-constructed buffer. More...
static void	ArrayCopyOverlap (T *pCopy, const T *pSource, size_t nCount)
	Copies an array of elements when the target and destination memory buffers may overlap. More...
static void	ArrayCopyConstruct (T *pCopy, const T *pSource, size_t nCount)
	Copies and array of elements to a non-constructed. More...

Protected Attributes
T *	mpArray
	Pointer to the storage buffer. More...
size_t	mReservedLen
	The reserved length (in number of elements, not bytes). More...
size_t	mUsedLen
	The used length (in number of elements, not bytes). More...
size_t	mGrowLen
	The growth length. See setGrowLength(). More...

Additional Inherited Members
Static Public Member Functions inherited from MaxHeapOperators
static UtilExport void *	operator new (size_t size)
	Standard new operator used to allocate objects If there is insufficient memory, an exception will be thrown. More...
static UtilExport void *	operator new (size_t size, const std::nothrow_t &e)
	Standard new operator used to allocate objects if there is insufficient memory, NULL will be returned. More...
static UtilExport void *	operator new (size_t size, const char *filename, int line)
	New operator used to allocate objects that takes the filename and line number where the new was called If there is insufficient memory, an exception will be thrown. More...
static UtilExport void *	operator new (size_t size, int block_type, const char *filename, int line)
	New operator used to allocate objects that takes the type of memory, filename and line number where the new was called If there is insufficient memory, an exception will be thrown. More...
static UtilExport void *	operator new (size_t size, const std::nothrow_t &e, const char *filename, int line)
	New operator used to allocate objects that takes the filename and line number where the new was called If there is insufficient memory, NULL will be returned. More...
static UtilExport void *	operator new (size_t size, unsigned long flags)
	New operator used to allocate objects that takes extra flags to specify special operations If there is insufficient memory, an exception will be thrown. More...
static UtilExport void *	operator new (size_t size, const std::nothrow_t &e, unsigned long flags)
	New operator used to allocate objects that takes extra flags to specify special operations If there is insufficient memory, NULL will be returned. More...
static UtilExport void *	operator new[] (size_t size)
	New operator used to allocate arrays of objects If there is insufficient memory, an exception will be thrown. More...
static UtilExport void *	operator new[] (size_t size, const std::nothrow_t &e)
	New operator used to allocate arrays of objects If there is insufficient memory, NULL will be returned. More...
static UtilExport void *	operator new[] (size_t size, const char *filename, int line)
	New operator used to allocate arrays of objects If there is insufficient memory, an exception will be thrown. More...
static UtilExport void *	operator new[] (size_t size, int block_type, const char *filename, int line)
	New operator used to allocate arrays of objects. More...
static UtilExport void *	operator new[] (size_t size, const std::nothrow_t &e, const char *filename, int line)
	New operator used to allocate arrays of objects If there is insufficient memory, NULL will be returned. More...
static UtilExport void *	operator new[] (size_t size, unsigned long flags)
	New operator used to allocate arrays of objects If there is insufficient memory, an exception will be thrown. More...
static UtilExport void *	operator new[] (size_t size, const std::nothrow_t &e, unsigned long flags)
	New operator used to allocate arrays of objects If there is insufficient memory, NULL will be returned. More...
static UtilExport void	operator delete (void *ptr)
	Standard delete operator used to deallocate an object If the pointer is invalid, an exception will be thrown. More...
static UtilExport void	operator delete (void *ptr, const std::nothrow_t &e)
	Standard delete operator used to deallocate an object If the pointer is invalid, nothing will happen. More...
static UtilExport void	operator delete (void *ptr, const char *filename, int line)
	Delete operator used to deallocate an object that takes the filename and line number where the delete was called If the pointer is invalid, an exception will be thrown. More...
static UtilExport void	operator delete (void *ptr, int block_type, const char *filename, int line)
	Delete operator used to deallocate an object that takes the type of memory, filename and line number where the delete was called If the pointer is invalid, an exception will be thrown. More...
static UtilExport void	operator delete (void *ptr, const std::nothrow_t &e, const char *filename, int line)
	Delete operator used to deallocate an object that takes the filename and line number where the delete was called If the pointer is invalid, nothing will happen. More...
static UtilExport void	operator delete (void *ptr, unsigned long flags)
	Delete operator used to deallocate an object that takes extra flags to specify special operations If the pointer is invalid, an exception will be thrown. More...
static UtilExport void	operator delete (void *ptr, const std::nothrow_t &e, unsigned long flags)
	Delete operator used to deallocate an object that takes extra flags to specify special operations If the pointer is invalid, nothing will happen. More...
static UtilExport void	operator delete[] (void *ptr)
	Standard delete operator used to deallocate an array of objects If the pointer is invalid, an exception will be thrown. More...
static UtilExport void	operator delete[] (void *ptr, const std::nothrow_t &e)
	Standard delete operator used to deallocate an array of objects If the pointer is invalid, nothing will happen. More...
static UtilExport void	operator delete[] (void *ptr, const char *filename, int line)
	Delete operator used to deallocate an array of objects that takes the filename and line number where the delete was called If the pointer is invalid, an exception will be thrown. More...
static UtilExport void	operator delete[] (void *ptr, int block_type, const char *filename, int line)
	Delete operator used to deallocate an array of objects that takes the type of memory, filename and line number where the delete was called If the pointer is invalid, an exception will be thrown. More...
static UtilExport void	operator delete[] (void *ptr, const std::nothrow_t &e, const char *filename, int line)
	Delete operator used to deallocate an array of objects that takes the filename and line number where the delete was called If the pointer is invalid, nothing will happen. More...
static UtilExport void	operator delete[] (void *ptr, unsigned long flags)
	Delete operator used to deallocate an array of objects that takes extra flags to specify special operations If the pointer is invalid, an exception will be thrown. More...
static UtilExport void	operator delete[] (void *ptr, const std::nothrow_t &e, unsigned long flags)
	Delete operator used to deallocate an array of objects that takes extra flags to specify special operations If the pointer is invalid, an exception will be thrown. More...
static UtilExport void *	operator new (size_t size, void *placement_ptr)
	Placement new operator. More...
static UtilExport void	operator delete (void *ptr, void *placement_ptr)
	Placement delete operator. More...

Member Typedef Documentation

typedef const void* elem2

Member Enumeration Documentation

anonymous enum

protected

Enumerator
kArrayGrowthThreshold	The maximum extra space (in bytes) that may be reserved when the buffer is enlarged. The array will usually enlarge the buffer by half its size whenever it runs out of space, unless that enlargement would exceed this value.
kDefaultGrowthLength	The default growth length. See setGrowLength().

         {
        kArrayGrowthThreshold = 0x10000,
        kDefaultGrowthLength = 8
    };

Constructor & Destructor Documentation

Array

(

)

Initializes an empty array.

: mpArray(NULL),
  mReservedLen(0),
  mUsedLen(0),
  mGrowLen(kDefaultGrowthLength)
{
    if(mGrowLen < 1) {
        // Growth length needs to be at least 1.
        mGrowLen = 1;
    }
}

Array	(	size_t	initUsedLength,
		const T &	defaultVal = T(),
		size_t	initGrowLength = kDefaultGrowthLength
	)

Initializes an array with an initial size.

Parameters

[in]	initUsedLength	- Number of elements initially allocated in the array.
[in]	defaultVal	- The default value for the elements initially allocated.
[in]	initGrowLength	- The initial growth length of the array. For more information on the growth length, see setGrowLength().

: mpArray(NULL),
  mReservedLen(0),
  mUsedLen(0),
  mGrowLen(growLength)
{
    if(mGrowLen < 1) {
        // Growth length needs to be at least 1.
        mGrowLen = 1;
    }

    // Re-size the array if a non-zero length was specified.
    if(usedLength > 0) {
        mpArray = ArrayAllocate(usedLength);
        if (mpArray == NULL) {
            handleOutOfMemory();
        }
        else {

            // Initialize the new elements
            ArrayConstruct(mpArray, usedLength, defaultVal);

            mReservedLen = usedLength;
            mUsedLen = usedLength;
        }
    }
}

Array

(

const Array< T > &

src

)

Copy constructor.

Copies the contents of another array.

Parameters

[in]

src

- Array from which the elements are copied.

: mpArray(NULL),
  mReservedLen(src.mReservedLen),
  mUsedLen(src.mUsedLen),
  mGrowLen(src.mGrowLen)
{
    if (mReservedLen > 0) {
        mpArray = ArrayAllocate(mReservedLen);
        if (mpArray == NULL) {
            handleOutOfMemory();
            mReservedLen = 0;
            mUsedLen = 0;
        }
        else {
            ArrayCopyConstruct(mpArray, src.mpArray, mUsedLen);
        }
    }
}

~Array

(

)

Destructor. Destroys every element stored in the array, and frees the allocated storage.

{
    if (mpArray != NULL) {
        ArrayDestruct(mpArray, mUsedLen);
        ArrayDeAllocate(mpArray);
    }
}

Member Function Documentation

typedef int

(

__cdecl *

CompareFnc

)

const

Type of function to pass to sort().

Must return:

• < 0 if elem1 is smaller than elem2,
• > 0 if elem 1 is greater,
• or 0 if they're equal.

Array< T > & operator=

(

const Array< T > &

src

)

Copy operator.

Copies the contents of another array.

Parameters

[in]

src

- Array from which the elements are copied.

Returns

A reference to 'this'.

{
    if (this != &src) {
        // Re-allocate the buffer if necessary
        if (mReservedLen < src.mUsedLen) {
            // Destroy the existing list
            if (mpArray != NULL) {
                ArrayDestruct(mpArray, mUsedLen);
                ArrayDeAllocate(mpArray);
            }
            // Allocate a new buffer
            mReservedLen = src.mUsedLen;
            mpArray = ArrayAllocate(mReservedLen);
            if (mpArray == NULL) { // ...so this only happens if failure.
                handleOutOfMemory();
                mReservedLen = 0;
                mUsedLen = 0;
                return *this;
            }
            // Copy the list
            mUsedLen = src.mUsedLen;
            ArrayCopyConstruct(mpArray, src.mpArray, mUsedLen);
        }
        else if(mUsedLen < src.mUsedLen) {
            // The entire destination list is to be overwritten
            ArrayCopy(mpArray, src.mpArray, mUsedLen);
            // Remaining elements need to be added to the list
            ArrayCopyConstruct(mpArray + mUsedLen, src.mpArray + mUsedLen, src.mUsedLen - mUsedLen);
            mUsedLen = src.mUsedLen;
        }
        else if(mUsedLen > src.mUsedLen) {
            // Copy the entire source list.
            ArrayCopy(mpArray, src.mpArray, src.mUsedLen);
            // Truncate unused elements in the destination list.
            ArrayDestruct(mpArray + src.mUsedLen, mUsedLen - src.mUsedLen);
            mUsedLen = src.mUsedLen;
        }
        else {
            // Lists are of identical size; simply copy the entire contents
            ArrayCopy(mpArray, src.mpArray, mUsedLen);
        }
    }
    return *this;
}

bool operator==

(

const Array< T > &

op

)

const

Equality operator.

Parameters

[in]

op

- Array to be compared to 'this'.

Returns

true if and only if both arrays contain the same number of elements and each of these elements if equal to the corresponding element from the other Array.

{
    if (mUsedLen == cpr.mUsedLen)
    {
        for (size_t i = 0; i < mUsedLen; i++)
            if (mpArray[i] != cpr.mpArray[i])
                return false;
        return true;
    }
    return false;
}

T & operator[] ( size_t  i )

inline

Subscript operator.

Parameters

[in]

i

- Index of array element to access. This index must be within the array bounds. If the index is out of bounds it will throw a MaxSDK::Util::MaxOutOfRangeException exception.

Returns

A reference to the array element at the specified index.

Remarks

Does implement bounds checking.

{
    if (!isValidIndex(i))
    {
        DbgAssert(false);
        throw MaxSDK::Util::OutOfRangeException(_M("Argument index out of bounds, passed into a MaxSDK::Array::operator[]"));
    }
    return mpArray[i];
}

const T & operator[] ( size_t  i ) const

inline

{ 
    if (!isValidIndex(i))
    {
        DbgAssert(false);
        throw MaxSDK::Util::OutOfRangeException(_M("Argument index out of bounds, passed into a MaxSDK::Array::operator[]"));
    }
    return mpArray[i];
}

const T & at ( size_t  index ) const

inline

Same as subscript operator.

Parameters

[in]

index

- Index of array element to access. This index must be within the array bounds.

Returns

A reference to the array element at the specified index.

Remarks

Does not implement bounds checking.

{ 
    if (!isValidIndex(i))
    {
        DbgAssert(false);
        throw MaxSDK::Util::OutOfRangeException(_M("Argument index out of bounds, passed into a MaxSDK::Array::at()"));
    }
    return mpArray[i];
}

T & at ( size_t  index )

inline

{ 
    if (!isValidIndex(i))
    {
        DbgAssert(false);
        throw MaxSDK::Util::OutOfRangeException(_M("Argument index out of bounds, passed into a MaxSDK::Array::at()"));
    }
    return mpArray[i];
}

Array< T > & setAt ( size_t  index, const T &  value  )

inline

Sets a copy of value at the given index.

Parameters

[in]	index	- The position in the array where a copy of value is placed. This index must be within the array bounds.
[in]	value	- a reference to the original object.

Returns

A reference to 'this'.

Remarks

Does not implement bounds checking.

{ 
    if (!isValidIndex(i))
    {
        DbgAssert(false);
        throw MaxSDK::Util::OutOfRangeException(_M("Argument index out of bounds, passed into a MaxSDK::Array::setAt()"));
    }
    mpArray[i] = value;
    return *this;
}

Array< T > & setAll

(

const T &

value

)

Sets all the elements of the array to the given value.

Parameters

[in]

value

- The value to which the elements of the array are set.

Returns

A reference to 'this'.

{
    for (size_t i = 0; i < mUsedLen; i++) {
        mpArray[i] = value;
    }
    return *this;
}

T & first ( )

inline

Accesses the first element in the array.

Returns

A reference to the first element of the array.

Remarks

It is invalid to call this on an empty array.

{ 
    DbgAssert(!this->isEmpty());
    DbgAssert(mpArray != nullptr);
    if (this->isEmpty() || (nullptr == mpArray))
    {
        throw MaxSDK::Util::RunTimeException(_M("Attempting to call MaxSDK::Array::first() on an empty array"));
    }
    return mpArray[0]; 
}

const T & first ( ) const

inline

{ 
    DbgAssert(!this->isEmpty());
    DbgAssert(mpArray != nullptr);
    if (this->isEmpty() || (nullptr == mpArray))
    {
        throw MaxSDK::Util::RunTimeException(_M("Attempting to call MaxSDK::Array::first() on an empty array"));
    }
    return mpArray[0];
}

T & last ( )

inline

Accesses the last element in the array.

Returns

A reference to the last element of the array.

Remarks

It is invalid to call this on an empty array.

{
    DbgAssert(!this->isEmpty());
    DbgAssert(mpArray != nullptr);
    if (this->isEmpty() || (nullptr == mpArray))
    {
        throw MaxSDK::Util::RunTimeException(_M("Attempting to call MaxSDK::Array::last() on an empty array"));
    }
    return mpArray[mUsedLen-1];
}

const T & last ( ) const

inline

{ 
    DbgAssert(!this->isEmpty()); 
    DbgAssert(mpArray != nullptr);
    if (this->isEmpty() || (nullptr == mpArray))
    {
        throw MaxSDK::Util::RunTimeException(_M("Attempting to call MaxSDK::Array::last() on an empty array"));
    }
    return mpArray[mUsedLen-1];
}

size_t append ( const T &  value )

inline

Appends a copy of value to the array.

Parameters

[in]

value

- A reference to the original value.

Returns

The number of elements in the array prior to the append operation.

{ 
    insertAt(mUsedLen, value);
    return mUsedLen-1; 
}

Array< T > & append	(	const T *	values,
		size_t	count
	)

Appends one or more element(s) to the array.

Parameters

[in]	values	- A pointer to a C-style array of elements, from which the appended elements will be copied.
[in]	count	- The number of elements to be appended.

Returns

A reference to 'this'.

{
    return insertAt(mUsedLen, values, count);
}

Array< T > & append

(

const Array< T > &

array

)

Appends the contents of another array to this array.

Parameters

[in]

array

- The array from which elements are to be appended.

Returns

A reference to 'this'.

{
    size_t otherLen = otherArray.length();
    if (otherLen == 0) {
        return *this;
    }
    size_t newLen = mUsedLen + otherLen;
    if (newLen > mReservedLen) {
        setLengthReserved(newLen);
    }

    ArrayCopyConstruct(mpArray + mUsedLen, otherArray.mpArray, otherLen);

    mUsedLen = newLen;
    return *this;
}

Array< T > & insertAt	(	size_t	index,
		const T &	value
	)

Inserts a single value, at a given location, into this array.

Parameters

[in]	index	- The index at which the element is to be inserted. This index must be smaller or equal to the used length of the array.
[in]	value	- The value to be inserted.

Returns

A reference to 'this'.

{
    DbgAssert(index >= 0 && index <= mUsedLen);

    if (mUsedLen >= mReservedLen) {
        size_t growth = (mUsedLen * sizeof(T)) < kArrayGrowthThreshold ?
            (mUsedLen / 2) : kArrayGrowthThreshold / sizeof(T);
        setLengthReserved(mUsedLen + __max(growth, mGrowLen));
    }

    if (index != mUsedLen) {

        // Initialize the new member of the array
        ArrayCopyConstruct(mpArray + mUsedLen, mpArray + mUsedLen - 1, 1);

        // Copy the remainder of the list that needs to be shifted
        for(size_t i = mUsedLen - 1; i > index; --i) {
            mpArray[i] = mpArray[i-1];
        }

        // Now copy the new element into the array
        mpArray[index] = value;
    }
    else {
        // Add the new value to the end of the list
        ArrayCopyConstruct(mpArray + mUsedLen, &value, 1);
    }

    mUsedLen++;
    return *this;
}

Array< T > & insertAt	(	size_t	index,
		const T *	values,
		size_t	count
	)

Inserts a one or more value(s), at a given location, into this array.

Parameters

[in]	index	- The index at which the element is to be inserted. This index must be smaller or equal to the used length of the array.
[in]	values	- A pointer to a C-style array of elements, from which the inserted elements will be copied.
[in]	count	- The number of elements to be inserted.

Returns

A reference to 'this'.

{
    DbgAssert(index >= 0 && index <= mUsedLen);

    if(index <= mUsedLen) {

        size_t lastInsertIndex = index + count - 1;

        // Increase the allocated memory if necessary
        size_t newUsedLen = mUsedLen + count;
        if(newUsedLen > mReservedLen) {

            // Allocate a new buffer
            T* newArray = ArrayAllocate(newUsedLen);
            if(newArray == NULL) {
                // Can't insert the new element since the allocation failed.
                handleOutOfMemory();
                return *this;
            }

            // Copy existing elements located to the left of the insertion range
            ArrayCopyConstruct(newArray, mpArray, index);

            // Copy the inserted elements
            ArrayCopyConstruct(newArray + index, values, count);

            // Copy existing elements located to the right of the insertion range
            if(index < mUsedLen) {
                ArrayCopyConstruct(newArray + index + count, mpArray + index, mUsedLen - index);
            }

            // Destroy the old array
            ArrayDestruct(mpArray, mUsedLen);
            ArrayDeAllocate(mpArray);

            mpArray = newArray;
            mUsedLen = newUsedLen;
            mReservedLen = newUsedLen;
        }
        else {
            if(index < mUsedLen) {
                // Shift elements that get moved beyond the current limit of the array
                ArrayCopyConstruct(mpArray + mUsedLen, mpArray + mUsedLen - count, count);

                // Shift elements that stay inside the current limits of the array
                if((index + count) < mUsedLen) {
                    ArrayCopyOverlap(mpArray + index + count, mpArray + index, mUsedLen - index - count);
                }

                // Copy new elements that get inserted within the current size of the array
                if(lastInsertIndex < mUsedLen) {
                    ArrayCopy(mpArray + index, values, count);
                }
                else {
                    ArrayCopy(mpArray + index, values, mUsedLen - index);
                }
            }

            // Copy new elements that get inserted beyond the current size of the array
            if(lastInsertIndex >= mUsedLen) {
                size_t numElementsInserted = (mUsedLen - index);
                DbgAssert(numElementsInserted < count);
                ArrayCopyConstruct(mpArray + mUsedLen, values + numElementsInserted, count - numElementsInserted);
            }

            mUsedLen += count;
        }
    }

    return *this;
}

Array< T > & removeAt

(

size_t

index

)

Removes a single element from the array.

Parameters

[in]

index

- The index of the element to be removed. This index must be valid (within bounds).

Returns

A reference to 'this'.

{
    DbgAssert(isValidIndex(index));

    if(index < mUsedLen) {
        // Shift array elements to the left if needed.
        //
        if (index < mUsedLen - 1) {
            for(size_t i = index; i < mUsedLen - 1; ++i) {
                mpArray[i] = mpArray[i+1];
            }
        }

        // Destroy the last element of the array
        ArrayDestruct(mpArray + mUsedLen - 1, 1);

        mUsedLen--;
    }

    return *this;
}

bool remove	(	const T &	value,
		size_t	start = 0
	)

Searches for a value in the array and, if it is found, removes it from the array.

Parameters

[in]	value	- The value to search for.
[in]	start	- The index at which to start searching. Preceding elements are not searched.

Returns

true if a value was found & removed; false otherwise.

Remarks

If multiple copies of the same value are stored in the array, only the first instance will be removed.

{
    const size_t i = this->findFrom(value, start);
    if (i == -1)
        return false;
    this->removeAt(i);
    return true;
}

Array< T > & removeFirst ( )

inline

Removes the first element of the array.

Returns

A reference to 'this'.

Remarks

Must not be called on an empty array.

{ 
    DbgAssert(!isEmpty()); 
    return removeAt(0); 
}

Array< T > & removeLast ( )

inline

Removes the last element of the array.

Returns

A reference to 'this'.

Remarks

Must not be called on an empty array.

{ 
    DbgAssert(!isEmpty());
    return removeAt(mUsedLen - 1); 
}

Array< T > & removeAll ( )

inline

Removes all the elements from the array.

Returns

A reference to 'this'.

{ 
    if(mUsedLen > 0) {
        ArrayDestruct(mpArray, mUsedLen);
        mUsedLen = 0;
    }
    return *this; 
}

Array< T > & removeSubArray	(	size_t	startIndex,
		size_t	endIndex
	)

Removes a subset of the array.

Parameters

[in]	startIndex	- The index of the first element to be removed.
[in]	endIndex	- The index of the last element to be removed.

Returns

A reference to 'this'.

Remarks

• Both the start and end indices must be within bounds.
• The end index must be greater or equal to the start index.

{
    DbgAssert(isValidIndex(startIndex));
    DbgAssert(startIndex <= endIndex);

    if(startIndex < mUsedLen) {

        if(endIndex >= mUsedLen) {
            endIndex = mUsedLen - 1;
        }

        size_t numToRemove = endIndex - startIndex + 1;

        // Shift all elements that reside on the right of the sub-array to be removed
        for(size_t i = endIndex + 1; i < mUsedLen; ++i) {
            mpArray[i - numToRemove] = mpArray[i];
        }

        // Truncate the array
        ArrayDestruct(mpArray + mUsedLen - numToRemove, numToRemove);

        mUsedLen -= numToRemove;
    }

    return *this;
}

bool contains ( const T &  value, size_t  start = 0  ) const

inline

Determines if a value is stored in the array.

Parameters

[in]	value	- The value for which to search for.
[in]	start	- The index at which to start searching. Preceding elements are not searched.

Returns

true if the value was found in the array; false otherwise.

{ 
    return this->findFrom(value, start) != -1;
}

bool find	(	const T &	value,
		size_t &	foundAt,
		size_t	start = 0
	)		const

Searches for a value in the array.

Parameters

[in]	value	- The value to search for.
[out]	foundAt	- The index at which the value was found. Indeterminate if the value was not found.
[in]	start	- The index at which to start searching. Preceding elements are not searched.

Returns

true if the value was found in the array; false otherwise.

{
    const size_t nFoundAt = this->findFrom(value, start);
    if (nFoundAt == -1)
        return false;
    index = nFoundAt;
    return true;
}

size_t find

(

const T &

value

)

const

Searches for a value in the array.

Parameters

[in]

value

- The value to search for.

Returns

The index at which the value was found, or -1 if the value was not found. (Since this returns an unsigned value, -1 is converted to the the largest positive value).

{
    return this->findFrom(value, 0);   // search from the beginning
}

size_t findFrom	(	const T &	value,
		size_t	start
	)		const

Searches for a value in the array, starting at a given index.

Parameters

[in]	value	- The value to search for.
[in]	start	- The index at which to start searching.

Returns

The index at which the value was found, or -1 if the value was not found. (Since this returns an unsigned value, -1 is converted to the the largest positive value).

{
    for (size_t i = start; i < this->mUsedLen; i++) {
        if (mpArray[i] == value)
            return i;
    }
    return (size_t)-1;
}

size_t length ( ) const

inline

Returns the number of used elements (as opposed to simply allocated/reserved) in the array.

{ 
    return mUsedLen;
}

bool isEmpty ( ) const

inline

Returns true if the number of used elements in the array is 0; returns false otherwise.

{ 
    return mUsedLen == 0; 
}

size_t lengthUsed ( ) const

inline

Returns the number of elements used (as opposed to simply allocated/reserved) in the array.

{ 
    return mUsedLen; 
}

Array< T > & setLengthUsed	(	size_t	length,
		const T &	defaultVal = T()
	)

Sets the number of elements used (as opposed to simply allocated/reserved) in the array.

Parameters

[in]	length	- The new "used length" of the array.
[in]	defaultVal	- The default value for new elements, used only if the length of the array is increased.

Returns

A reference to 'this'.

{
    DbgAssert(n >= 0);
    if (n > mReservedLen) {

        size_t growth = (mReservedLen * sizeof(T)) < kArrayGrowthThreshold ?
            (mReservedLen / 2) : kArrayGrowthThreshold / sizeof(T);

        size_t minSize = mReservedLen + __max(growth, mGrowLen);
        if ( n > minSize)
            minSize = n;
        setLengthReserved(minSize);
    }

    if(n > mUsedLen) {
        // Initialize the new elements
        ArrayConstruct(mpArray + mUsedLen, n - mUsedLen, defaultVal);
    }
    else {
        // Destroy the elements to be removed
        ArrayDestruct(mpArray + n, mUsedLen - n);
    }

    mUsedLen = n;
    return *this;
}

size_t lengthReserved ( ) const

inline

Returns the number of elements allocated/reserved (as opposed to actually used) in the array.

{ 
    return mReservedLen; 
}

Array< T > & setLengthReserved

(

size_t

length

)

Sets the number of elements allocated/reserved (as opposed to actually used) in the array.

Parameters

[in]

length

- The new "reserved length" of the array.

Returns

A reference to 'this'.

{
    DbgAssert(n >= 0);

    if(n != mReservedLen) {

        if(n == 0) {
            if(mReservedLen > 0) {
                ArrayDestruct(mpArray, mUsedLen);
                ArrayDeAllocate(mpArray);
                mpArray = NULL;
                mUsedLen = 0;
                mReservedLen = 0;
            }
        }
        else if(mReservedLen == 0) {
            mpArray = ArrayAllocate(n);
            if(mpArray == NULL) {
                // Failure to allocate memory; can't increase the reserved length.
                handleOutOfMemory();
                return *this;
            }
            mReservedLen = n;
        }
        else {
            T* oldArray = mpArray;
            size_t oldUsedLen = mUsedLen;

            // Allocate the new array
            mpArray = ArrayAllocate(n);
            if(mpArray == NULL) {
                // Failure to allocate memory; can't change the reserved length.
                handleOutOfMemory();
                mpArray = oldArray;
                return *this;
            }

            // Copy the old array to the new one.
            if(n < mUsedLen) {
                // The old members don't all fit in the new array
                ArrayCopyConstruct(mpArray, oldArray, n);
                mUsedLen = n;
            }
            else {
                ArrayCopyConstruct(mpArray, oldArray, mUsedLen);
            }
            mReservedLen = n;

            // Destroy the old array
            ArrayDestruct(oldArray, oldUsedLen);
            ArrayDeAllocate(oldArray);
        }
    }

    return *this;
}

void reserve

(

size_t

capacity

)

Alias for setLengthReserved.

Sets the number of elements allocated/reserved (as opposed to actually used) in the array. Named to be similar to the STL containers.

Parameters

[in]

capacity

- The new "reserved length" or possible capacity of the array.

Returns

void

{
    setLengthReserved(capacity);
}

size_t growLength ( ) const

inline

Returns the growth length of the array.

For more information on the growth length, see setGrowLength().

{ 
    return mGrowLen;
}

Array< T > & setGrowLength ( size_t  glen )

inline

Sets the growth length of the array.

The growth length is the minimum number elements by which the reserved space is grown whenever the array runs out of reserved space.

{ 
    DbgAssert(glen > 0);
    if(glen > 0) {
        mGrowLen = glen;
    }
    else {
        DbgAssert(false);
        // Growth length needs to be at least 1.
        mGrowLen = 1; 
    }
    return *this; 
}

Array< T > & reverse

(

)

Reverses the sequence of elements in the array.

Reverses the sequence of elements in the array such that the last element becomes the first.

Returns

A reference to 'this'.

{
    size_t halfUsedLen = mUsedLen/2;
    for (size_t i = 0; i < halfUsedLen; i++) {
        T tmp = mpArray[i];
        mpArray[i] = mpArray[mUsedLen - 1 - i];
        mpArray[mUsedLen - 1 - i] = tmp;
    }
    return *this;
}

Array< T > & swap	(	size_t	i1,
		size_t	i2
	)

Swaps two elements in this array.

Parameters

[in]	i1	- The index of the first element to swap. This index must be within bounds.
[in]	i2	- The index of the second element to swap. This index must be within bounds.

{
    DbgAssert(isValidIndex(i1));
    DbgAssert(isValidIndex(i2));

    if (i1 == i2) return *this;

    T tmp = mpArray[i1];
    mpArray[i1] = mpArray[i2];
    mpArray[i2] = tmp;
    return *this;
}

void sort

(

CompareFnc

cmp

)

Sorts the elements of the array using a custom comparison function.

The sort if performed with the QuickSort algorithm.

Parameters

[in]

cmp

- The comparison function used to order the elements.

See also

CompareFnc

                                                     {

    if(mUsedLen > 1) {
        // Use the standard C function of the type doesn't have a copy operator
        // (meaning that memcpy() is safe)
        /*  From MSDN: The compiler's support for type traits allows library writers to 
            determine various characteristics of a type at compile time. 
            All type traits return false if the specified conditions are not met. 
            Returns true if the CLR or native type has a copy assignment operator. */
        if(!__has_assign(T)) {
            qsort(mpArray, mUsedLen, sizeof(T), cmp);
        }
        else {
            quickSortRecursive(mpArray, 0, mUsedLen - 1, cmp);
        }
    }
}

const T * asArrayPtr ( ) const

inline

Returns the array storage as a C-style array pointer.

Remarks

Any modification to the contents of the array, through this pointer, may be dangerous.

{ 
    return mpArray;
}

T * asArrayPtr ( )

inline

{ 
    return mpArray; 
}

bool isValidIndex ( size_t  i ) const

inline

Returns whether the given array index is valid for this array.

Returns

true if the given index is within the bounds of this array; false otherwise.

{ 
    // We should prohibit index's that are the maximum size_t value
    return (i != (size_t)-1) && i < mUsedLen;
}

size_t quickSortPartition ( T *  data, size_t  first, size_t  last, CompareFnc  cmp  )

staticprotected

The partition portion of the QuickSort algorithm.

{
    const T& pivot = data[last]; // use the last item as the pivot
    size_t left = first; // sort from the first item
    size_t right = last - 1; // sort to the item excluding the pivot

    do {
        while ((left < last) && (cmp(&(data[left]), &pivot) <= 0))
        {
            ++left;
        }
        while ((right > first) && (cmp(&(data[right]), &pivot) >= 0))
        {
            --right;
        }
        if (left < right) {
            T swapValue = data[left];
            data[left] = data[right];
            data[right] = swapValue;
        }
    } while (left < right);

    if (cmp(&data[left], &pivot) > 0)
    {
        T swapValue = data[left];
        data[left] = data[last];
        data[last] = swapValue;
    }

    return left;
}

void quickSortRecursive ( T *  data, size_t  first, size_t  last, CompareFnc  cmp  )

staticprotected

Recursive QuickSort function used to sort the elements of the array.

{
    if (first < last)
    {
        size_t pivot_position = quickSortPartition(data, first, last, cmp);

        // Protect against overflow. Normally the "if (first < last)" test would
        // guard against this, but size_t is unsigned, meaning "right - 1" can result
        // in a test of -1 > 0 when right is 0, which is an invalid unsigned inequality.
        if (pivot_position > 0)
        {
            quickSortRecursive(data, first, pivot_position - 1, cmp);
        }
        quickSortRecursive(data, pivot_position + 1, last, cmp);
    }
}

void handleOutOfMemory ( )

inlinestaticprotected

Utility function, called when the array fails to allocate memory.

                                                           {

    DbgAssert(false);
    UtilOutOfMemoryException();
}

T * ArrayAllocate ( size_t  len )

inlinestaticprotected

Allocates an array of elements without constructing them.

{
    DbgAssert(len < 0x40000000);  // 1G sanity check
    T* p = (T*) UtilAllocateMemory(len * sizeof(T));
    return p;
}

void ArrayConstruct ( T *  arrayBegin, size_t  len, const T &  defaultVal  )

inlinestaticprotected

Constructs an array of elements.

{
    if(!__has_trivial_constructor(T))
    {
        for(size_t i = 0; i < len; ++i)
        {
            new(&(arrayBegin[i])) T(defaultVal);
        }
    }
}

void ArrayDeAllocate ( T *  arrayBegin )

inlinestaticprotected

De-allocates an array of elements without destructing them.

{
    UtilDeallocateMemory(arrayBegin);
}

void ArrayDestruct ( T *  arrayBegin, size_t  len  )

inlinestaticprotected

Destructs an array of elements.

{
    if(!__has_trivial_destructor(T)) 
    {
        for(size_t i = 0; i < len; ++i)
        {
            arrayBegin[i].~T();
        }
    }
}

void ArrayCopy ( T *  pCopy, const T *  pSource, size_t  nCount  )

staticprotected

Copies an array of elements to an already-constructed buffer.

Will use the copy operator if needed.

{
    // Auto-detect whether it's safe to use memcpy() or whether we need
    // to call the copy operator. We're counting on the fact that this condition,
    // being resolvable at compile-time, will be removed by the optimizer.
    if(__has_assign(T)) {
        // Type has an assignment operator; use it.
        for(size_t i = 0; i < nCount; ++i)
        {
            pCopy[i] = (pSource[i]);
        }
    }
    else {
        // Type does not have an assignment operator; use memcpy() as it's usually faster.
        if (nCount > 0) 
        {
            memcpy(pCopy, pSource, nCount * sizeof(T));
        }
    }
}

void ArrayCopyOverlap ( T *  pCopy, const T *  pSource, size_t  nCount  )

staticprotected

Copies an array of elements when the target and destination memory buffers may overlap.

{
    // Auto-detect whether it's safe to use memcpy() or whether we need
    // to call the copy operator. We're counting on the fact that this condition,
    // being resolvable at compile-time, will be removed by the optimizer.
    if(__has_assign(T)) {
        // Type has an assignment operator; use it.
        if (pCopy == pSource)
        {
            // nothing to do here, bail early
            return;
        }

        if (pCopy < pSource)
        {
            // forward iteration
            for(size_t i = 0; i < nCount; i++ )
            {
                pCopy[i] = pSource[i];
            }
        }
        else
        {
            // backward iteration
            for(size_t i = nCount - 1; i != (size_t)-1; --i)
            {
                pCopy[i] = pSource[i];
            }
        }
    }
    else {
        // Type does not have an assignment operator; use memcpy() as it's usually faster.
        if (nCount > 0) 
        {
            memmove(pCopy, pSource, nCount * sizeof(T));
        }
    }
}

void ArrayCopyConstruct ( T *  pCopy, const T *  pSource, size_t  nCount  )

staticprotected

Copies and array of elements to a non-constructed.

Will use the copy constructor if needed.

{
    // Auto-detect whether it's safe to use memcpy() or whether we need
    // to call the copy operator. We're counting on the fact that this condition,
    // being resolvable at compile-time, will be removed by the optimizer.
    if(__has_copy(T)) {
        // Type has an assignment operator; use it.
        for(size_t i = 0; i < nCount; ++i)
        {
            new(&(pCopy[i])) T(pSource[i]); // using placement new.
        }
    }
    else {
        // Type does not have an assignment operator; use memcpy() as it's usually faster.
        if (nCount > 0) 
        {
            memcpy(pCopy, pSource, nCount * sizeof(T));
        }
    }
}

Member Data Documentation

T* mpArray

protected

Pointer to the storage buffer.

size_t mReservedLen

protected

The reserved length (in number of elements, not bytes).

size_t mUsedLen

protected

The used length (in number of elements, not bytes).

size_t mGrowLen

protected

The growth length. See setGrowLength().