//*****************************************************************************/
// Copyright (c) 1998-2006 Autodesk, Inc.
// All rights reserved.
// 
// These coded instructions, statements, and computer programs contain
// unpublished proprietary information written by Autodesk, Inc., and are
// protected by Federal copyright law. They may not be disclosed to third
// parties or copied or duplicated in any form, in whole or in part, without
// the prior written consent of Autodesk, Inc.
//*****************************************************************************/
/*==============================================================================

  file:     Array.imp.h
  author:   Daniel Levesque
  created:  27 March 2006
  description:
    Array container.

==============================================================================*/

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

template <class T>
Array<T>::Array(size_t usedLength, const T& defaultVal, size_t growLength)
: 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;
		}
	}
}

// This is the usual copy constructor with the caveat that,
// if the system can not allocate enough memory to satisfy the
// request then it is assumed that the entire system is in a
// dangerously low memory situation, and there is no alternative
// but to have the system gracefully abort (i.e., prompting the
// users to save files, and/or free up more memory, or what-have-you).
//
template <class T>
Array<T>::Array(const Array<T>& src)
: 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);
		}
	}
}

template <class T>
Array<T>::~Array()
{
	if (mpArray != NULL) {
		ArrayDestruct(mpArray, mUsedLen);
		ArrayDeAllocate(mpArray);
	}
}

// The assignment operator.  The assignment operator copies
// the data from the source array to this array.  If the
// source array contains more elements that this array has
// space to store, then this array is grown to meet the demand.
// Otherwise, the reserved length of this array does not change.
// After this operation is completed the used lengths of the
// two arrays will be equal.  The grow length of this array is
// not affected by this operation.
//
template <class T> Array<T>&
Array<T>::operator = (const Array<T>& src)
{
	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;
}


// The equal to operator.  The equal to operator compares
// the data in two arrays.  If the used length of the
// two arrays are the same and the corresponding entries of
// the two arrays are equal, true is returned. Otherwise,
// false is returned.
//
template <class T> bool
Array<T>::operator == (const Array<T>& cpr) const
{
	if (mUsedLen == cpr.mUsedLen) {
		for (size_t i = 0; i < mUsedLen; i++)
			if (mpArray[i] != cpr.mpArray[i])
				return false;
		return true;
	}
	return false;
}

// Sets all the elements within the used length of the array,
// (that is, elements 0..length()-1), to `value'.
//
template <class T> Array<T>&
Array<T>::setAll(const T& value)
{
	for (size_t i = 0; i < mUsedLen; i++) {
		mpArray[i] = value;
	}
	return *this;
}

// Appends the `otherArray' to the end of this array.  The used length of
// this array will increase by the length of the `otherArray'.  If the
// reserved length is not long enough it will increase by the amount
// necessary to fit the newly added elements (with the usual caveat about
// insufficient memory).
//
template <class T> Array<T>&
Array<T>::append(const Array<T>& otherArray)
{
	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;
}

// Inserts `value' at `index'.  The value formerly at `index'
// gets moved to `index+1',  `index+1 gets moved to `index+2' and so on.
// Note that insertAt(length(), value) is equivalent to append(value).
// The used length of the array will increase by one.  If the reserved
// length is not long enough it will increase by the grow length (with the
// usual caveat about insufficient memory).
//
template <class T> Array<T>&
Array<T>::insertAt(size_t index, const T& value)
{
	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;
}

template <class T> Array<T>&
Array<T>::insertAt(size_t index, const T* values, size_t count)
{
	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;
}

// Removes the element at `index'.  The used length will
// decrease by one.  `index' MUST BE within bounds.
//
template <class T> Array<T>&
Array<T>::removeAt(size_t index)
{
	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;
}

// Removes all elements starting with 'startIndex' and ending with 'endIndex'
// The used length will decrease by number of removed elements.
//
template <class T> Array<T>&
Array<T>::removeSubArray(size_t startIndex, size_t endIndex)
{
	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;
}

// Returns true if and only if the array contains `value' from
// index `start' onwards.  Returns, in `index', the first location
// that contains `value'.  The search begins at position `start'.
// `start' is supplied with a default value of `0', i.e., the
// beginning of the array.
//
template <class T> bool
Array<T>::find(const T& value, size_t& index, size_t start) const
{
	const size_t nFoundAt = this->findFrom(value, start);
	if (nFoundAt == -1)
		return false;
	index = nFoundAt;
	return true;
}

template <class T> size_t
Array<T>::find(const T& value) const
{
	return this->findFrom(value, 0);   // search from the beginning
}

template <class T> size_t
Array<T>::findFrom(const T& value, size_t start) const
{
	for (size_t i = start; i < this->mUsedLen; i++) {
		if (mpArray[i] == value)
			return i;
	}
	return -1;
}

// Allows you to set the used length of the array.
// If you try to set the used length to be greater than
// the reserved length, then the array is grown to a
// reasonable size (thus increasing both the used length
// AND the reserved length).
// Also, the reserved length will grow in growth length
// steps.
template <class T> Array<T>&
Array<T>::setLengthUsed(size_t n, const T& defaultVal)
{
	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;
}

// Allows you to set the reserved length of the array.
// If you set the reserved length to be less than
// the used length, then the used length is reset
// to match the new reserved length.  A reserved length
// of zero is valid.
//
template <class T> Array<T>&
Array<T>::setLengthReserved(size_t n)
{
	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;
}

// Reverses the order of the array.  That is if you have two
// arrays, `a' and `b', then if you assign `a = b' then call
// `a.reverse()' then a[0] == b[n], a[1] == b[n-1],... a[n] == b[0].
//
template <class T> Array<T>&
Array<T>::reverse()
{
	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;
}

// Swaps the elements in `i1' and `i2'.
//
template <class T> Array<T>&
Array<T>::swap(size_t i1, size_t i2)
{
	DbgAssert(isValidIndex(i1));
	DbgAssert(isValidIndex(i2));

	if (i1 == i2) return *this;

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

// Returns true if and only if `value' was removed from the array from
// position `start' onwards.  Only the first occurrence of `value'
// is removed.  Calling this function is equivalent to doing a "find(),
// then "removeAt()".
//
template <class T> bool
Array<T>::remove(const T& value, size_t start)
{
	const size_t i = this->findFrom(value, start);
	if (i == -1)
		return false;
	this->removeAt(i);
	return true;
}

template <class T> 
void Array<T>::sort(CompareFnc cmp) {

	if(mUsedLen > 1) {
		// Use the standard C function of the type doesn't have a copy operator
		// (meaning that memcpy() is safe)
		if(!__has_assign(T)) {
			qsort(mpArray, mUsedLen, sizeof(T), cmp);
		}
		else {
			quickSortRecursive(mpArray, 0, mUsedLen - 1, cmp);
		}
	}
}

template <class T>
void Array<T>::quickSortRecursive(T* data, size_t first, size_t last, CompareFnc cmp) {

	if(first < last) {
		const T& pivot = data[first];
		size_t left = first + 1;
		size_t right = last;

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

		// Move the pivot
		{
			T swapValue = data[first];
			data[first] = data[right];
			data[right] = swapValue;
		}

		quickSortRecursive(data, first, right - 1, cmp);
		quickSortRecursive(data, right + 1, last, cmp);
	}
}
