/****************************************************************************************************

		MCClassArray.h
		Copyright: (c) 2001 Eovia Corp. All rights reserved.

		MOVED FROM MCCore\Include

		Author:	Arnaud
		Date:	10/1/2003

****************************************************************************************************/

#ifndef __MCClassArray__
#define __MCClassArray__

#if CP_PRAGMA_ONCE
#pragma once
#endif

#include "MCStatusCode.h"
#include "MCIterator.h"
#include "MCMemoryAlloc.h"
#include "MCMemoryCopy.h"
#include "MCMath.h"

#if !defined(qLeanMCCore)
	#include "MCException.h"
#endif

//needed for classes that don't derive from TMCObject
//#ifndef qMacho
#include <new.h>
///#endif

/// \addtogroup MCCore
/// \{

/// <P>TMCClassArray is an array used to store structs or classes that need a constructor or a destructor.
/// For example, you can use it with TMCDynamicString and the memory used by the strings will be freed when the array is destroyed.
///
/// <P>Indexes to access the Array classes are ZERO based (array[0] gives you the first element) </P>
///
/// <P>Arrays grows dynamically as you add elements, 
/// so it is very dangerous to keep pointers to elements of the array: if the array is reallocated, 
/// your pointers will become invalid. In this case, you should use indexes.
/// For better efficiency, preallocate the number of elements you'll need (or use an estimation of the space if possible). <BR>
/// In eSmartGrow mode (the default), the size of the extra space added when the array is reallocated (the grow size) 
/// depends on the number of elements already in the array. Otherwise, a constant grow size is used.
/// </P>
///
/// <P>Other array classes are: TMCArray, TMCPtrArray, TMCCountedPtrArray, and TMCExtensibleArray. </P>
///
template <class T> class TMCClassArray : public TMCObject
{
public:
	
	/// Creates an empty array
	/// 
	TMCClassArray(void);

	// ****************************************************************************
	//								TMCClassArray
	// 
	/// Constructs an array with a certain number of elements already accessible (and constructed).
	/// 
	/// \param initialCount    initial number of array elements.
	/// 
	explicit TMCClassArray(uint32 initialCount);

	// ****************************************************************************
	//								TMCClassArray
	// 
	/// Constructs an array with a certain number of elements already accessible (and constructed), 
	/// and/or some extra space to extend the array without reallocating it.
	/// \note This constructor turns off eSmartGrow, so the grow size is constant
	/// 
	/// \param initialCount     Initial number of array elements.
	/// \param initialSpace     Pre-allocate space for this many elements (must be bigger than initialCount).
	/// \param initialGrowSize  How many elements to grow the array when we grow past the end
	/// 
	TMCClassArray(
		uint32	initialCount,
		uint32	initialSpace,
		uint32	initialGrowSize);

	/// Copy constructor: Construct an array from an existing array.
	/// 
	TMCClassArray(const TMCClassArray<T>& inFromArray);

	
	// ****************************************************************************
	//								TMCClassArray
	// 
	/// Constructs an array from existing memory.
	/// \note: If you pass inAquireMemory = false then this array CANNOT grow past elemSpace,
	/// and will not free the memory passed in.
	/// 
	/// \param baseAddress     External memory to use for this array.
	/// \param inAquireMemory  Should we take possession this memory.
	/// \param elemCount       The number of array elements in use in that memory.
	/// \param elemSpace       The number of array elements that can be used in that memory.
	/// 
	TMCClassArray(
		T* const &	baseAddress,
		boolean		inAquireMemory,
		uint32		elemCount,
		uint32		elemSpace);


	// ****************************************************************************
	//								TMCClassArray
	// 
	/// Constructs an alias to an existing array.
	/// \note: This array CANNOT grow past elemSpace, and will not free the memory passed in.
	/// Also this array is an alias to the array passed in NOT a copy so be carefull.
	/// 
	/// \param array      Alias elements from this array.
	/// \param elemStart  Start alias here.
	/// \param elemCount  Alias this many elements.
	/// 
	TMCClassArray(
		TMCClassArray<T>&	array,
		uint32				elemStart,
		uint32				elemCount);

	/// Destructs the elements of the array and frees the memory (if the array owns it).
	///
	~TMCClassArray(void);

	/// operator=: Assignment operator copies all the data from one array to another.
	///
	TMCClassArray<T>&	operator=(const TMCClassArray<T>& fromArray);

	//Declare iterator types for this array
	typedef TMCIterator<T, TMCClassArray<T> > iterator;
	typedef TMCConstIterator<T, TMCClassArray<T> > const_iterator;

protected:
	// Allocation/Deallocation functions
	// Allocate the array, disregards the existing data so be careful calling this explicitly.
	/// <B> !!! DO NOT CALL THIS !!! </B>
	///
	boolean	ArrayAlloc(
		uint32	initialCount,		//Initial number of array elements.
		uint32	initialSpace,		//Pre-allocate space for this many elements.
		uint32	initialGrowSize);	//How many elements to grow the array when we grow past the end.

	// Allocate the array, using existing data
	/// <B> !!! DO NOT CALL THIS !!! </B>
	///
	boolean ArrayAllocFromBuffer(
		T*		baseAddress,	//External memory to use for this array.
		boolean	inAquireMemory, //Should we take possession this memory.
		uint32	elemCount,		//The number of array elements in use in that memory.
		uint32	elemSpace);		//The number of array elements that can be used in that memory.

public:
	
	// ****************************************************************************
	//								ArrayFree
	// 
	/// Frees all the memory held by this array (unless it uses external memory).
	///	And sets the element count to 0.
	/// 
	void		ArrayFree(void);

	/// IsValid(): Check to see if the class is valid.
	/// 
	inline boolean 	IsValid(void) const				{return ((fArrayFlags&eValid) != 0);}

	/// returns kNoErr if the given index is valid, kOutOfRangeError otherwise (use with ThrowIfError(array.IsIndexInvalid(i);)
	///
	inline MCErr	IsIndexInvalid(int32 i) const	{ MCAssert(IsValid()); return ((0<=i)&&(i<(int32)GetElemCount())) ? kNoErr : kOutOfRangeError; }

	////////////////////////////////////////////////////////////////
	// Simple member accessors

	/// Returns the address at which the elements of the array begin
	/// 
	inline	int8* 		BaseAddress(void)			{return (int8*)fArrayData;}

	/// Returns the address at which the elements of the array begin
	/// 
	inline	const int8* BaseAddress(void) const		{return (const int8*)fArrayData;}

	/// Returns the size of one element
	/// 
	inline	uint32		GetElemSize(void) const		{return sizeof(T);}

	/// Returns the size by which the array grows
	/// 
	inline	uint32		GetGrowSize	(void) const	{return GetSmartGrow()	? MC_Min(fArrayFlags&eGrowMask, 1 + (uint32)(GetElemCount()*kSmartGrowPercentage))
																			: fArrayFlags&eGrowMask;}

	/// Returns the number of elements that can be stored in the array (before the next reallocation)
	/// 
	inline	uint32		GetElemSpace(void) const	{return fElemSpace;}

	/// Returns the actual number of (valid) elements in the array. Those elements can be accessed with the operator []
	/// 
	inline	uint32		GetElemCount(void) const	{return fElemCount;}

	/// Returns true if the array doesn't own its memory
	/// 
	inline boolean		ExternalMemory	()			{return ((fArrayFlags&eExternalMem) != 0);}

	/// Returns true if the grow size is dynamic
	/// 
	inline	boolean		GetSmartGrow(void) const	{return ((fArrayFlags&eSmartGrow) != 0);}

	/// Returns a pointer to the first element
	/// 
	inline	T*			ArrayData(void)				{return fArrayData;}

	/// Returns a pointer to the first element
	/// 
	inline	const T*	ArrayData(void) const		{return fArrayData;}

	/// Returns true if the element is in the array
	///
	inline  boolean     IsInArray(const T* data) const {return ((data >= fArrayData) && (data < fArrayData+fElemCount));}


	// Setters.

	/// Sets the valid flag to true
	/// 
	inline void		SetValid		(boolean valid)	{if (valid)	fArrayFlags|=eValid; else fArrayFlags&=(~eValid);}
	
	/// Sets the growSize (and sets the eSmartGrow flag to false)
	/// 
	inline void		SetGrowSize		(uint32 g)		{Assert ((g&eGrowMask) == g); fArrayFlags = (g&eGrowMask) | (fArrayFlags&eNotGrowMask); fArrayFlags&=(~eSmartGrow); }

	/// Sets the eSmartGrow flag and computes the maximum grow size (in elements count) 
	/// 
	inline void		SetSmartGrow	()				{fArrayFlags= eSmartGrow | (fArrayFlags & eNotGrowMask) | ( eGrowMask & (kMaxMemoryForGrow / GetElemSize()) ) ;}

	/// Set the number of elements to have memory allocated for.
	///	Note: This memory is unconstructed, uninitialied and isn't considered
	///	part of the array until the element count reaches the memory.
	/// 
	boolean SetElemSpace(uint32 n);

	/// Set the number of elements in the array.
	///
	boolean SetElemCount(uint32 n);

	/// Add the passed in number of elemens to the array.
	///
	boolean AddElemCount(uint32 n);

	/// Returns a reference to the begining iterator for the array.
	///
	const_iterator	Begin(void) const	{return const_iterator(*this,GetElemCount()>0?0:kEndIndex);}

	/// Returns a reference to the begining iterator for the array.
	///
	iterator		Begin(void)			{return iterator(*this,GetElemCount()>0?0:kEndIndex);}

	/// Returns a reference to the ending iterator for the array.
	///
	const_iterator	End(void) const		{return const_iterator(*this,kEndIndex);}

	/// Returns a reference to the ending iterator for the array.
	///
	iterator		End(void)			{return iterator(*this,kEndIndex);}

	/// Returns a reference to the first element in the array.
	///
	T&					FirstElem(void)				{MCAssert(IsValid());
													 MCAssert(GetElemCount()>0);
													 return fArrayData[0];}

	/// Returns a reference to the first element in the array.
	///
	const T&			FirstElem(void) const		{MCAssert(IsValid());
													 MCAssert(GetElemCount()>0);
													 return fArrayData[0];}

	/// Returns a reference to the last element in the array.
	///
	T&					LastElem(void)				{MCAssert(IsValid());
													 MCAssert(GetElemCount()>0);
													 return fArrayData[GetElemCount() - 1];}

	/// Returns a reference to the last element in the array.
	///
	const T&			LastElem(void) const		{MCAssert(IsValid());
													 MCAssert(GetElemCount()>0);
													 return fArrayData[GetElemCount() - 1];}


	/// Erases a single element in the array that is referenced by the iterator.
	///
	void	Erase(const iterator& elementToErase)	{RemoveElem(elementToErase.GetIndex(), 1);}

	/// Erases a range of elements in the array from the startIterator to the endIterator.
	///
	void	Erase(const iterator& start, const iterator& end);

	/// Copy elements from one array to another.
	///
	boolean	CopyElems(
		const TMCClassArray<T>&	fromArray,
		uint32					firstIndex,
		uint32					nbItems,
		uint32					insertIndex);

	/// Append one array on to the end of another.
	///
	boolean	Append(const TMCClassArray<T>& fromArray);
	
	/// Fill an array range with the value passed in.
	///
	void FillWithValue(
		const T&	inValue,					//Value to fill with
		uint32		inStart = kBeginIndex,		//Start filling from here (default is fill from start).
		uint32		inLength = kUnusedIndex);	//Fill this many items (default is fill to end).
	
	/// Swaps the contents of two arrays.
	///
	void Swap(TMCClassArray<T>& fromArray);


	// =================================================================================================================
	// Access Methods
	// =================================================================================================================

	/// Returns a pointer to the data at the passed in index.
	///
	inline T*		Pointer			(uint32 i)				{MCAssert(IsValid());				
															 MCAssert(i < GetElemCount());			
															 return fArrayData + i;}					
	
	/// Returns a pointer to the data at the passed in index.
	///
	inline const T*	Pointer			(uint32 i) const		{MCAssert(IsValid());				
															 MCAssert(i < GetElemCount());			
															 return fArrayData + i;}					
																	 									
	/// Returns a reference to the data at the passed in index.
	///
	inline T& 		operator[]		(uint32 i) 				{ MCAssert(IsValid()); MCAssert(i < GetElemCount()); return fArrayData[i]; }

	/// Returns a reference to the data at the passed in index.
	///
	inline const T&	operator[]		(uint32 i) const		{ MCAssert(IsValid()); MCAssert(i < GetElemCount()); return fArrayData[i]; }


	// =================================================================================================================
	// Element Functions
	// =================================================================================================================	
	
	/// Set the contents of arrray index to the passed in data reference.
	///
	void SetElem(uint32 index, const T& data);

	/// Get the contents of arrray index into the passed in data reference.
	///
	void GetElem(uint32 index, T& data) const;

	/// Add an element to the end of the array and assign it the data reference that is passed in.
	///
	boolean	AddElem(const T& data);

	/// Add an element to the end of the array and returns a reference to it.
	///
	T& AddElem();

	
	// ****************************************************************************
	//								InsertElem
	// 
	/// Inserts one element at the given index
	/// 
	/// \param index  where to insert
	/// \param data   the data to insert
	/// 
	boolean	InsertElem(uint32 index, const T& data);

	/// Remove one or more elements from the array starting from the passed in index.
	///
	void RemoveElem(uint32 index, uint32 count);

	/// Get rid of any space that has been allocated to the array and isn't being used.
	///
	inline boolean 	CompactArray(void){return SetElemSpace (GetElemCount());}


	// ****************************************************************************
	//								FindElem
	// 
	/// Finds the index in this array of the given element
	///
	/// \note Requires that T implements an operator ==
	/// 
	/// \param elemToFind  the element to search for
	/// \return ::kUnusedIndex if elemToFind is not in the array, otherwise a valid index
	///
	uint32	FindElem	(const T& elemToFind)const;

	
	// ****************************************************************************
	//								RemoveElem
	// 
	/// Removes (only) one occurence of an element (after searching for it)
	///
	/// \note Requires that T implements an operator ==
	/// 
	/// \param elemToRemove  the element to remove.
	/// 
	void 	RemoveElem	(T& elemToRemove);

protected:
	// =================================================================================================================
	// Data
	// =================================================================================================================
	uint32		fElemCount;		///< The number of elements in use.
	uint32		fElemSpace;		///< The number of elements allocated (unconstructed).
	uint32		fArrayFlags;	///< Flags that control the behavior of the array

	// =================================================================================================================
	// Array Data
	// =================================================================================================================
	T*			fArrayData;		///< The memory block used by the array

	// =================================================================================================================
	// Update Array Pointer
	// =================================================================================================================	
	void		UpdateDataPointer(void)	 	{fArrayData=(T*)BaseAddress();}


	// =================================================================================================================
	// Maintenance
	// =================================================================================================================	
#ifdef qTrackArray
	static uint32 sReallocCount;
	uint32 fReallocCount;

	void InitReallocVariables();
	void ReallocCalled();
#endif

	void 		ZeroInternals(void)
	{
		fArrayData = 0;
		fElemCount = 0;
		fElemSpace = 0;
		fArrayFlags = 0;
#ifdef qTrackArray
		InitReallocVariables();
#endif
	}
	void		Construct(T* inDataStart, uint32 numConstruct, const T& inInitValue);
	void		Destruct(T* inDataStart, uint32 numDestruct);
};
/// \}

// =================================================================================================================
// Construction
// =================================================================================================================

template<class T> TMCClassArray<T>::TMCClassArray (void) 
{
	if(!ArrayAlloc(0, 0, eDefaultGrowSize))
	{
		MCNotify("Array allocation failed in constructor!");
	}
	SetSmartGrow();
	MCAssert(IsValid());
}

// =================================================================================================================
// Construction
// =================================================================================================================

template<class T> TMCClassArray<T>::TMCClassArray (uint32 initialCount)
{
	if(!ArrayAlloc(initialCount, initialCount, 0))
	{
		MCNotify("Array allocation failed in constructor!");
	}
	SetSmartGrow();
	MCAssert(IsValid());
}

// =================================================================================================================
// Construction
// =================================================================================================================

template<class T> TMCClassArray<T>::TMCClassArray (
	uint32	initialCount,		//Initial number of elements.
	uint32	initialSpace,		//Alocate space for this many elements.
	uint32	initialGrowSize)	//Increase memory by this many elements when we need to add space.
{
	if(!ArrayAlloc(initialCount, initialSpace, initialGrowSize))
	{
		MCNotify("Array allocation failed in constructor!");
	}

	MCAssert(IsValid());
}


// =================================================================================================================
// Construction
// =================================================================================================================

template<class T> TMCClassArray<T>::TMCClassArray (const TMCClassArray<T>& inFromArray)
{
	if(!ArrayAlloc(0, 0, inFromArray.GetGrowSize()))
	{
		MCNotify("Array allocation failed in constructor!");
	}
	else
	{
		*this = inFromArray;
	}

	MCAssert(IsValid());
}

// =================================================================================================================
// Construction - from external memory
//	Note: This array cannot be resized past the passed in elemSpace, and the array will NOT release
//	the memory buffer passed in.
// =================================================================================================================
template<class T> TMCClassArray<T>::TMCClassArray (
	T* const&	baseAddress,	//Pointer to alocated memory elemSpace elements long.
	boolean		inAquireMemory, //Should we take possession this memory.
	uint32		elemCount,		//The number of array elements in use in that memory.
	uint32		elemSpace)		//The number of array elements that can be used in that memory.
{
	if(!ArrayAllocFromBuffer(baseAddress, inAquireMemory, elemCount, elemSpace))
	{
		MCNotify("Array allocation failed in constructor!");
	}
	MCAssert(IsValid());
}

// =================================================================================================================
// Construction - from existing array, makes an alias to that array.
//	Note: This array cannot be resized past the passed in elemSpace, and the array will NOT release
//	the memory buffer passed in.
// =================================================================================================================
template<class T> TMCClassArray<T>::TMCClassArray (
	TMCClassArray<T>&	array,		//Alias elements from this array.
	uint32				elemStart,	//Start alias here.
	uint32				elemCount)	//Alias this many elements.
{
	if (elemCount == 0)
	{
		ArrayAllocFromBuffer(NULL, false, 0, 0);
	}
	else
	{
		MCAssert((elemStart < array.GetElemCount()) && (elemStart + elemCount <= array.GetElemCount()));
		
		if(!ArrayAllocFromBuffer(&array[elemStart], false, elemCount, elemCount))
		{
			MCNotify("Array allocation failed in constructor!");
		}
		else
		{
			fArrayFlags |= eArrayAlias;
		}
	}
	MCAssert(IsValid());
}

// =================================================================================================================
// Destruction
// =================================================================================================================
template<class T> TMCClassArray<T>::~TMCClassArray (void)
{
	ArrayFree();
	fArrayFlags &= ~eValid;
}

// =================================================================================================================
// operator=
// =================================================================================================================
template<class T> TMCClassArray<T>&	TMCClassArray<T>::operator=(const TMCClassArray<T>& fromArray)
{
	if(&fromArray != this)
	{
		if (fromArray.GetSmartGrow())	//Copy the SmartGrow flag
			SetSmartGrow();

		uint32 toCopy = fromArray.GetElemCount();

		//Set ourselves to have the same number of elements as the source array.
		if(SetElemCount(toCopy))
		{
#if 0
			//This could probably be optimized. See the stl vector::operator=() for ideas.
			//Try allocating the memory then placement newing them with the original's elements.
#else
			//Now walk all our items and assign them from the source array.
			const T* from = fromArray.ArrayData();
			T* to = (T*)BaseAddress();
			while(toCopy--)
			{
				*to++ = *from++;
			}
#endif
		}
		else
		{
			//Should we set this array as invalid?
			MCNotify("Unable to complete operator=() memory allocation failed.");
		}
	}
	return *this;
}


// =================================================================================================================
// ArrayAlloc - Ignores existing data, so be carefull if you are calling this explicitly.
// =================================================================================================================
template<class T> boolean TMCClassArray<T>::ArrayAlloc (
	uint32	initialCount,
	uint32	initialSpace,
	uint32	initialGrowSize)
{
	
	ZeroInternals ();
	
	if(MCVerify(initialCount <= initialSpace))
	{
		fArrayFlags |= eValid;

		MCAssert(!ExternalMemory());
		fArrayFlags &= ~eExternalMem;

		SetGrowSize(initialGrowSize);

		if (!SetElemSpace (initialSpace))
		{
			return false;
		}

		if (!SetElemCount (initialCount))
		{
			fArrayFlags &= ~eValid;
			return false;
		}
	}
	else
	{
		MCNotify("initialCount > initialSpace");
		return false;
	}

	return true;
}

// =================================================================================================================
// ArrayAllocFromBuffer - from external memory
//	Ignores existing data, so be carefull if you are calling this explicitly.
// =================================================================================================================
template<class T> boolean TMCClassArray<T>::ArrayAllocFromBuffer(
	T*		baseAddress,
	boolean	inAquireMemory,
	uint32	elemCount,
	uint32	elemSpace)
{
	ZeroInternals ();
	
	if(MCVerify(elemCount <= elemSpace))
	{
		fArrayData	= baseAddress;
		fArrayFlags |= eValid;

		if(!inAquireMemory)
		{
			fArrayFlags |= eExternalMem;
		}

		fElemCount	 = elemCount;
		fElemSpace	 = elemSpace;	

		return true;
	}
	else
	{
		MCNotify("elemCount > elemSpace");
		return false;
	}
}

// =================================================================================================================
// ArrayFree - Free all the memory help by this array, unless it uses external memory
//	then we just set the element count to 0.
// =================================================================================================================
template<class T> void TMCClassArray<T>::ArrayFree (void)
{
	if (IsValid())
	{
		//We need to force the destruction of each element.
		SetElemCount(0);

		if(!ExternalMemory())
		{
			SetElemSpace(0);
		}
	}
}

// =================================================================================================================
// Construct
// =================================================================================================================
template<class T> void TMCClassArray<T>::Construct(T* inDataStart, uint32 numConstruct, const T& inInitValue)
{
	while(numConstruct--)
	{
		new (inDataStart) T(inInitValue);
		inDataStart++;
	}
}

// =================================================================================================================
// Destruct
// =================================================================================================================
template<class T> void TMCClassArray<T>::Destruct(T* inDataStart, uint32 numDelete)
{
	while(numDelete--)
	{
		inDataStart->~T();
		inDataStart++;
	}
}

// =================================================================================================================
// SetElemSpace
// =================================================================================================================
template<class T> boolean TMCClassArray<T>::SetElemSpace(uint32 n)
{
	MCAssert(IsValid());
	MCAssert(GetElemSize()>0);	
	
	if (n == GetElemSpace())
	{
		return true;
	}

	if(!ExternalMemory())
	{
		if(n < GetElemCount())
		{
			//Removing elements.
			T*	deleteFrom = ArrayData() + n;
			Destruct(deleteFrom, GetElemCount() - n);

			fElemCount = n;
		}

		uint32	newSize	= GetElemSize() * n;
		int8*	newAddr;
		int8*	oldAddr = nil;

		//try to resize base address
		if(newSize)
		{
			if (!BaseAddress()) 
			{
				newAddr = (int8*)MCmalloc(newSize);
			}
			else
			{
				oldAddr = BaseAddress();
				newAddr = (int8*)MCmalloc(newSize);
				if (newAddr)
				{
#ifdef qTrackArray
					ReallocCalled();
#endif
					MCmemcpy(newAddr, oldAddr, MC_Min(GetElemCount(), n) * GetElemSize());
				}
			}
			if (!newAddr)
			{
				MCAssertMessage("Array allocation failed!");
				return false;
			}
		}
		else
		{
			if (BaseAddress())
			{
				MCfree(BaseAddress());
			}
			newAddr = NULL;
		}

		//set new pointer values and sizes
		fArrayData	= (T*)newAddr;
		fElemSpace		= n;

		UpdateDataPointer();
		if (oldAddr)
		{
			MCfree(oldAddr);
		}
		return true;
	}
	else
	{
		MCNotify("Can't resize array with external memory");
		return false;
	}
}

// =================================================================================================================
// SetElemCount - Change the number of elements in use by this array, will expand the array's
//	memory if neccessary. If n is less than count then count - n elements
//	from the end of the array will be destructed. If n > count the new memory will be void constructed.
// =================================================================================================================
template<class T> boolean TMCClassArray<T>::SetElemCount(uint32 n)
{
	MCAssert(IsValid());

	//This will cause an overflow with any iterators.
	MCAssert(n < kEndIndex);

	if(n < GetElemCount())
	{
		//Removing elements.
		T*	deleteFrom = ArrayData() + n;
		Destruct(deleteFrom, GetElemCount() - n);
	}

	if (n > GetElemSpace())	
	{
		if (!SetElemSpace (n))
		{
			return false;
		}
	}

	if(n > GetElemCount())
	{
		//Adding elements.
		T*	constructFrom = ArrayData() + GetElemCount();
		Construct(constructFrom, n - GetElemCount(), T());
	}
	fElemCount = n;
		
	return true;
}

// =================================================================================================================
// AddElemCount - Increment the number of elements in use by this array, will expand the array's
//	memory by a multiple of the grow size if neccessary. Any new elements will be void constructed.
// =================================================================================================================
template<class T> boolean TMCClassArray<T>::AddElemCount(uint32 n)
{
	MCAssert(IsValid());
	MCAssert(n >= 0);
	
	n = n + GetElemCount();
	if (n > GetElemSpace())	
	{
		if (!GetGrowSize())
		{
			MCAssertMessage("grow size is zero!!");
			return false;
		}

		int32 space;
		if(n % GetGrowSize())
		{
			space = (n/GetGrowSize() + 1)*GetGrowSize();
		}
		else
		{
			space = n;
		}
		
		
		if(!SetElemSpace (space))
		{
			return false;
		}
	}
		
	if(n > GetElemCount())
	{
		//Adding elements.
		T*	constructFrom = ArrayData() + GetElemCount();
		Construct(constructFrom, n - GetElemCount(), T());
	}
	fElemCount = n;
		
	return true;
}




// =================================================================================================================
// SetElem - Assign data to the index'th element of the array.
// =================================================================================================================
template<class T> void TMCClassArray<T>::SetElem(uint32 index, const T&  data)
{
	MCAssert(IsValid());
	MCAssert(BaseAddress());

	MCAssert(index < GetElemCount());

	fArrayData[index] = data;
}

// =================================================================================================================
// GetElem - Assign the index'th element of the array into data.
// =================================================================================================================
template<class T> void TMCClassArray<T>::GetElem(uint32 index, T&  data) const
{
	MCAssert(IsValid());
	MCAssert(BaseAddress());

	MCAssert(index < GetElemCount());
	
	data = fArrayData[index];
}

// =================================================================================================================
// AddElem - Add an element to the array an assign data to it.
// =================================================================================================================
template<class T> inline boolean TMCClassArray<T>::AddElem (const T&  data)											
{
	MCAssert(IsValid());
	
	if (GetElemCount() == GetElemSpace())
	{
		if (IsInArray(&data))
		{
			const T tmpData(data);
			if (!SetElemSpace(GetElemSpace()+GetGrowSize()))
			{
				return false;
			}
			Construct((T *)(BaseAddress() + (GetElemSize() * GetElemCount())), 1, tmpData);
			//Increment the element count.
			fElemCount++;

			return true;
		}

		if (!SetElemSpace (GetElemSpace()+GetGrowSize()))
		{
			return false;
		}
	}

	//Construct directly into the memory just past the last element currently in use.
	Construct((T *)(BaseAddress() + (GetElemSize() * GetElemCount())), 1, data);
	//Increment the element count.
	fElemCount++;

	return true;									
}

// =================================================================================================================
// AddElem - Add an element to the array
// =================================================================================================================
template<class T> inline T& TMCClassArray<T>::AddElem ()											
{
	MCAssert(IsValid());
	
	if (GetElemCount() == GetElemSpace())	
	{
		if (!SetElemSpace (GetElemSpace()+GetGrowSize()))
		{
#if defined(qLeanMCCore)
			throw;
#else
			ThrowIfNoMem(0);
#endif
		}
	}
	//Construct directly into the memory just past the last element currently in use.
	T* newElem = fArrayData + fElemCount;

	new (newElem) T;

	fElemCount++;

	return *newElem;									
}
// =================================================================================================================
// InsertElem - Insert an element into the array an assign data to it.
//	Note: You can pass an index that is greater that the element count, we will simply increase
//	the size of the array to hold at least index number of elements.
// =================================================================================================================
template<class T> boolean TMCClassArray<T>::InsertElem(uint32 index, const T& data)
{
	MCAssert(IsValid());

	MCAssert(!IsInArray(&data));
	/*
		We allow an Insert to the end (ie if GetElemCount == 4 (indexes 0-3)) and then
		we call InsertElem(4, data) this will work even though the index 4 doesnt yet exist

		BECAUSE - if we have 0 elements then there is no fBaseAddress - but we want to be 
		able to insert to an empty list!!
	*/
	
	if(index > GetElemCount())
	{
		//We allow them to grow the array automatically by
		//inserting past the end of the array.
		if(AddElemCount(index - GetElemCount() + 1))
		{
			SetElem(index, data);
		}
		else
		{
			return false;
		}
	}
#if 1
	else
	{
		//We would prefer not to call SetElemCount() since that void constructs the 
		//new element as well as incrementing the element count. Instead
		//if we need to resize the memory we will, we will then move the
		//existing items, if neccessary, and then construct the new element directly
		//into it's memory.

		//Check if we need to resize the array.
		if(GetElemCount() == GetElemSpace())
		{
			//Increase the memory allocated for this array, by the grow size.
			if(!SetElemSpace(GetElemCount() + GetGrowSize()))
			{
				return false;
			}
		}

		uint32 moveSize	= GetElemSize() * (GetElemCount() - index);	//Amount of memory to move.
		uint32 moveFrom	= GetElemSize() * index;					//Where to move from.
		
		//If moveSize is non-zero then we are inserting before the new end of the array.
		if(moveSize)
		{
			// Since the regions overlap we must move memory with MCmemmove instead of MCmemcpy.
			uint32 moveTo = GetElemSize() * (index + 1); //Where to move to.
		
			MCAssertPointerCheck(BaseAddress());

			MCmemmove(BaseAddress() + moveTo, BaseAddress() + moveFrom, moveSize);
		}

		//Construct the element whose memory we just allocated/vacated, with the data passed in.
		Construct((T *)(BaseAddress() + moveFrom), 1, data);
		//Now increment fElemCount by hand.
		fElemCount++;
		return true;
	}
#else
	else if(AddElemCount(1))
	{
		cnt = cnt - index;

		uint32 copySize		= GetElemSize() * cnt;
		uint32 srcOffset	= GetElemSize() * index;
		
		//If copySize is non-zero then we are inserting before the new end of the array.
		if(copySize)
		{
			// Since the regions overlap we must move memory with MCmemmove instead of MCmemcpy.
			uint32 dstOffset	= GetElemSize() * (index + 1);
		
			MCAssertPointerCheck(BaseAddress());

			MCmemmove(BaseAddress() + dstOffset, BaseAddress() + srcOffset, copySize);
		}
		//Construct the element whose memory we just allocated/vacated, with the data passed in.
		Construct((T *)(BaseAddress() + srcOffset), 1, data);
	
		return true;
	}
#endif
	return false;
}

// =================================================================================================================
// RemoveElem - Remove an element from the array.
// =================================================================================================================
template<class T> void TMCClassArray<T>::RemoveElem(uint32 index, uint32 count)
{
	if(count > 0)
	{
		MCAssert(IsValid());
		MCAssert(BaseAddress());
		MCAssert(index < GetElemCount());

		if (index + count > GetElemCount())
		{
			MCAssertMessage("Removing more items than are in the array!!");
			count = GetElemCount() - index;
		}


		uint32 memLoc		= GetElemSize() * index;
		uint32 srcMemLoc	= GetElemSize() * (index + count);
		uint32 copySize		= GetElemSize() * (GetElemCount() - index - count);
		
		T*		deleteFrom	= ArrayData() + index;
		uint32	deleteCount	= count;
		Destruct(deleteFrom, deleteCount);

		MCmemmove(BaseAddress() + memLoc, BaseAddress() + srcMemLoc, copySize);
		
		// We don't want to call SetElemCount(GetElemCount() - count) here
		// because that would destruct the elements at the end (and we don't
		// want to do that since we MCmemmoved them to their new location
		// ---Greg (6/2/98)
		fElemCount -= count;
	}
}


// =================================================================================================================
// Erase
// =================================================================================================================
// Erase the elements of the array from startIterator to endIterator.
template<class T> void TMCClassArray<T>::Erase(const iterator& startIterator, const iterator& endIterator)
{
	MCAssert(startIterator.fMyArray == endIterator.fMyArray);
	if(startIterator.fMyArray != endIterator.fMyArray)
	{
		MCAssert(startIterator.fCurrentIndex < endIterator.fCurrentIndex);
		RemoveElem(startIterator.fCurrentIndex, endIterator.fCurrentIndex - startIterator.fCurrentIndex);
	}
}

// =================================================================================================================
// CopyElems - Inserts nbItems (starting at startIndex) items of fromArray into this list at position insertIndex.
// =================================================================================================================
template<class T> boolean TMCClassArray<T>::CopyElems(
	const TMCClassArray<T>&	fromArray,
	uint32					firstIndex,
	uint32					nbItems,
	uint32					insertIndex) 
{
	boolean	result		= true;
	uint32	fromIndex	= firstIndex;
	uint32	lastFrom	= fromIndex + nbItems;
	uint32	toIndex		= insertIndex;
	uint32	lastTo		= toIndex + nbItems;

	uint32 newSize = GetElemCount()+nbItems;
	if (GetElemSpace() < newSize)
	{
		SetElemSpace(newSize);
	}
	//Copy over the elements from the other list, element by element.
	while(fromIndex < lastFrom && result)
	{
		result = InsertElem(toIndex, fromArray[fromIndex]);
		fromIndex++;
		toIndex++;
	};
	return result;
}

#define MC_DECLARE_CLASS_ARRAY(tableType, tableName) typedef TMCClassArray<tableType> tableName

// =================================================================================================================
// Append - Adds the elements from fromArray on to the end of this one.
// =================================================================================================================
template<class T> boolean TMCClassArray<T>::Append(const TMCClassArray<T>& fromArray)
{
	return CopyElems(fromArray, kBeginIndex, fromArray.GetElemCount(), GetElemCount());
}

// =================================================================================================================
// Append - Fill an array range with the value passed in.
// =================================================================================================================
template<class T> void TMCClassArray<T>::FillWithValue(
	const T&	inValue,	//Value to fill with
	uint32		inStart,	//Start filling from here (default is fill from start).
	uint32		inLength)	//Fill this many items (default is fill to end).
{
	if((GetElemCount() > 0) && (inLength > 0))
	{
		uint32 fillIndex = inStart;
		uint32 lastFill;

		if((inLength == kUnusedIndex) || (inStart + inLength > GetElemCount()))
		{
			lastFill = GetElemCount() - inStart;
		}
		else
		{
			lastFill = inStart + inLength;
		}

		while(fillIndex < lastFill)
		{
			fArrayData[fillIndex++] = inValue;
		}
	}
}

// =================================================================================================================
// Swap - Swaps the contents of two arrays..
// =================================================================================================================
template<class T> void TMCClassArray<T>::Swap(TMCClassArray<T>& fromArray)
{
	uint32 swapValue;
	
	swapValue = fElemCount;
	fElemCount = fromArray.fElemCount;
	fromArray.fElemCount = swapValue;

	swapValue = fElemSpace;
	fElemSpace = fromArray.fElemSpace;
	fromArray.fElemSpace = swapValue;

	swapValue = fArrayFlags;
	fArrayFlags = fromArray.fArrayFlags;
	fromArray.fArrayFlags = swapValue;

	T*	swapPtr = fArrayData;
	fArrayData = fromArray.fArrayData;
	fromArray.fArrayData = swapPtr;
	
	UpdateDataPointer();
	fromArray.UpdateDataPointer();
}

// =================================================================================================================
// FindElem - Find the index in this array of elemToFind, if elemToFind is not in the array return kUnusedIndex
//	Note: Requires that T implement an operator==.
// =================================================================================================================
template<class T> uint32 TMCClassArray<T>::FindElem(const T& elemToFind) const
{
	uint32 foundIndex = kUnusedIndex;
	typename TMCClassArray<T>::const_iterator iter(*this);
	for (const T* curElem = iter.First(); iter.More(); curElem = iter.Next())
	{
		if (*curElem == elemToFind)
		{
			foundIndex = iter.GetIndex();
			break;
		}
	}
	return foundIndex;
}

// =================================================================================================================
// RemoveElem - If elemToRemove exists in this array remove it.
//	Note: Only removes one occurence of elemToRemove.
// =================================================================================================================
template<class T> void TMCClassArray<T>::RemoveElem(T& elemToRemove)
{
	uint32 foundIndex = FindElem(elemToRemove);
	if (foundIndex != kUnusedIndex)
		RemoveElem(foundIndex, 1);
}

#ifdef qTrackArray
template<class T> uint32 TMCClassArray<T>::sReallocCount = 0;

template<class T> void TMCClassArray<T>::InitReallocVariables()
{
	fReallocCount = 0;
}

template<class T> void TMCClassArray<T>::ReallocCalled()
{
	sReallocCount++;
	fReallocCount++;
	MCAssert(sReallocCount < 80);
	MCAssert(fReallocCount < 10);
}
#endif
#endif
