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

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

		MOVED FROM MCCore\Include

		Author:	Arnaud
		Date:	10/1/2003

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

#ifndef __MCPtrArray__
#define __MCPtrArray__

#if CP_PRAGMA_ONCE
#pragma once
#endif


#include "MCBasicDefines.h"
#include "MCMath.h"
#include "MCMemoryAlloc.h"
#include "MCMemoryCopy.h"
#include "MCPtrIterator.h"

#if !defined(qLeanMCCore)
	#include "MCArrayUtils.h"
	#include "MCCountedPtr.h"
	template<class T> class TMCCountedPtrArray;
#endif

/// \addtogroup MCCore
/// \{

/// <P>TMCPtrArray is an array used to store pointers to objects. The array does NOT own those objects,
/// so when it is destroyed, they still live. To delete those objects, call DeleteAndRemoveAll()</P>
///
/// <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.
/// 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, TMCCountedPtrArray, TMCClassArray and TMCExtensibleArray. </P>
///
template<class T> class TMCPtrArray : public TMCObject
{
public:
	typedef T	TTemplateType;	///The template type on which the array is based
	typedef T*	TValueType;		///A type that represents the data type stored in the array.

	/// Creates an empty array
	/// 
	TMCPtrArray(void);

	// ****************************************************************************
	//								TMCPtrArray
	// 
	/// Constructs an array with a certain number of elements already accessible
	/// 
	/// \param initialCount    initial number of array elements.
	/// \param initialZeroMem  Zero the memory allocated for array storage ?
	/// 
	TMCPtrArray(
		uint32	initialCount,
		boolean	initialZeroMem);

	// ****************************************************************************
	//								TMCPtrArray
	// 
	/// Constructs an array with a certain number of elements already accessible, 
	/// 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
	/// \param initialZeroMem   Zero the memory allocated for array storage ?
	/// 
	TMCPtrArray(
		uint32	initialCount,
		uint32	initialSpace,
		uint32	initialGrowSize,
		boolean	initialZeroMem);

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

#if !defined(qLeanMCCore)
	/// Copy constructor: Construct an array from an existing array.
	///
	TMCPtrArray(const TMCCountedPtrArray<T>& inFromCountedPtrArray);

	/// operator=: Assignment operator copies all the pointers from one array to another.
	///
	TMCPtrArray<T>&	operator=(const TMCCountedPtrArray<T>& fromCountedPtrArray);
#endif
	
	// ****************************************************************************
	//								TMCPtrArray
	// 
	/// 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.
	/// 
	TMCPtrArray(
		T** const &	baseAddress,
		boolean		inAquireMemory,
		uint32		elemCount,
		uint32		elemSpace);

	
	// ****************************************************************************
	//								TMCArray
	// 
	/// 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.
	/// 
	TMCPtrArray(
		TMCPtrArray<T>&	array,
		uint32			elemStart,
		uint32			elemCount);

	~TMCPtrArray(void);


	// ****************************************************************************
	//								DeleteAndRemoveElements
	// 
	/// Deletes some of the objects referenced by the array and then removes them from the array.
	/// 
	/// \param startIndex   index of the first elem to delete and remove
	/// \param deleteCount  number of elements to delete and remove
	/// 
	void	DeleteAndRemoveElements(uint32 startIndex, uint32 deleteCount);

	
	// ****************************************************************************
	//								DeleteAndRemoveAll
	// 
	/// Deletes all the objects referenced by the array and then removes them from the array.
	/// 
	inline void	DeleteAndRemoveAll()						{ DeleteAndRemoveElements(0, GetElemCount()); }


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


#if !defined(qLeanMCCore)
	/// Fills outArray
	template < class TArray2 > inline void QueryArray(	const MCIID& iid, TArray2& outArray) const 
	{
		::QueryArray(iid, *this, outArray);
	}
#endif

	/// Declare iterator types for this array
	///
	typedef TMCPtrIterator<T, TMCPtrArray<T> > iterator;
	typedef TMCConstPtrIterator<T, TMCPtrArray<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.
		boolean	initialZeroMem);//Zero the memory allocated for array storage?

	// 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);}

	// 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 (sizeof(T*))
	/// 
	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 newly allocated memory should be initialized with zero
	/// 
	inline	boolean		GetZeroMem	(void)	const	{return ((fArrayFlags&eZeroMem) != 0);}

	/// 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	T** const	ArrayData(void) const		{return fArrayData;}

	// Simple member accessors (Setters)

	/// Sets whether the newly allocated memory should be initialized with zero
	/// 
	inline void		SetZeroMem		(boolean z)				{if (z)	fArrayFlags|=eZeroMem; else fArrayFlags&=(~eZeroMem);}

	/// 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 an iterator initialized to the begining of the array.
	///
	const_iterator	Begin(void)	const		{return const_iterator(*this,GetElemCount()>0?0:kEndIndex);}

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

	/// Returns an iterator initialized to the end of the array.
	///
	const_iterator End(void) const			{return const_iterator(*this,kEndIndex);}

	/// Returns an iterator initialized to the end of 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* const		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* const		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 TMCPtrArray<T>&	fromArray,
		uint32					startIndex,
		uint32					numItems,
		uint32					insertAtIndex);

	/// Append one array on to the end of another.
	///
	boolean	Append(const TMCPtrArray<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(TMCPtrArray<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 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 T* const &	operator[]		(uint32 i) const
	{ MCAssert(IsValid()); MCAssert(i < GetElemCount()); return fArrayData[i]; }

	// =================================================================================================================
	// Element Functions
	// =================================================================================================================	

	/// Set the contents of array index to the passed in data reference.
	///
	void SetElem(uint32 index, const T* data);

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

	/// Get the contents of array index into the passed in data reference.
	///
	void GetElem(uint32 index, const 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);

	/// Insert one element into the array and assign the resulting item(s) the data data
	///	reference that is passed in.
	/// 
	boolean InsertElem(uint32 index, const T* data);

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

	/// Remove one instance of elemToRemove if it exists in the array.
	///
	void RemoveElem(T* elemToRemove);

	// ****************************************************************************
	//								FindElem
	// 
	/// Finds the index in this array of the given element
	///
	/// \param item  the element to search for
	/// \return ::kUnusedIndex if elemToFind is not in the array, otherwise a valid index
	///
	uint32 FindElem(const T* item) const;

	// ****************************************************************************
	//								FindNullPointersSuffixStart
	// 
	/// Find the first index of the suffix contianing the indexed pointer for which
	/// all pointers are NULL
	///
	/// \param index The index to start the search from
	/// \return the index of the first index in this block for which all pointers onwards 
	/// are NULL, or ::kUnusedIndex if there are not NULL pointers after this pointer. 
	///
	uint32 FindNullPointersSuffixStart(uint32 index) const;

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

protected:
//	friend class iterator;
//	friend class const_iterator;
#ifdef qTrackArray
	static uint32 sReallocCount;
	uint32 fReallocCount;

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

	// =================================================================================================================
	// 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();}
	void 		ZeroInternals(void)
				{
				fArrayData	= 0;
				fElemCount	= 0;
				fElemSpace	= 0;
				fArrayFlags	= 0;
#ifdef qTrackArray
				InitReallocVariables();
#endif
				}
};
/// \}

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

// =================================================================================================================
// Construction
// =================================================================================================================
template<class T> TMCPtrArray<T>::TMCPtrArray(
	uint32	initialCount,	//Initial number of elements
	boolean	initialZeroMem)	//Should we fill memory allocated for the array with 0?
{
	if(!ArrayAlloc(initialCount, initialCount, 0, initialZeroMem))
	{
		MCNotify("Array allocation failed in constructor!");
	}
	SetSmartGrow();
	MCAssert(IsValid());
}

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

template<class T> TMCPtrArray<T>::TMCPtrArray (
	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.
	boolean	initialZeroMem)		//Should we fill memory allocated for the array with 0?
{
	if(!ArrayAlloc(initialCount, initialSpace, initialGrowSize, initialZeroMem))
	{
		MCNotify("Array allocation failed in constructor!");
	}
	MCAssert(IsValid());
}


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

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

#if !defined(qLeanMCCore)

template<class T> TMCPtrArray<T>::TMCPtrArray(
	const TMCCountedPtrArray<T>&	inFromCountedPtrArray)
{
	if(!ArrayAlloc(0, 0, inFromCountedPtrArray.GetGrowSize(), true))
	{
		MCNotify("Array allocation failed in constructor!");
	}
	else
	{
		*this = inFromCountedPtrArray;
	}
	MCAssert(IsValid());
}

#endif

// =================================================================================================================
// 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> TMCPtrArray<T>::TMCPtrArray(
	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> TMCPtrArray<T>::TMCPtrArray(
	TMCPtrArray<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> TMCPtrArray<T>::~TMCPtrArray (void)
{
	ArrayFree();
	fArrayFlags &= ~eValid;
}


template<class T> void TMCPtrArray<T>::DeleteAndRemoveElements(uint32 startIndex, uint32 deleteCount)
{
	MCAssert(deleteCount <= GetElemCount());
	for (uint32 ii= startIndex; ii < deleteCount; ii++)
	{
		delete fArrayData[ii];
	}
	RemoveElem(startIndex, deleteCount);
}


// =================================================================================================================
// operator= - Copy all the elements from fromArray into this array, overwrites this arrays existing
//	elements.
// =================================================================================================================
template<class T> TMCPtrArray<T>&	TMCPtrArray<T>::operator=(const TMCPtrArray<T>& fromArray)
{
	//Short circut test, if we are being assigned to ourself.
	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))
		{
			//MCmemcpy is a little cheaper and we should be able to use it as source
			//and dest addresses shouldn't overlap.
			MCmemcpy(BaseAddress(), fromArray.BaseAddress(), toCopy * GetElemSize());
		}
		else
		{
			//Should we set this array as invalid?
			MCNotify("Unable to complete operator=() memory allocation failed.");
		}
	}
	return *this;
}

#if !defined(qLeanMCCore)
// =================================================================================================================
// operator= - Copy all the elements from fromArray into this array, overwrites this arrays existing
//	elements.
// =================================================================================================================
template<class T> TMCPtrArray<T>& TMCPtrArray<T>::operator=(const TMCCountedPtrArray<T>& inFromCountedPtrArray)
{
	//Short circut test, if we are being assigned to ourself.
	if (inFromCountedPtrArray.GetSmartGrow())	//Copy the SmartGrow flag
		SetSmartGrow();

	uint32 toCopy = inFromCountedPtrArray.GetElemCount();

	//Set ourselves to have the same number of elements as the source array.
	if(SetElemCount(toCopy))
	{
		//We must do this element by element because assigning the element changes
		//it's refcount, and so we cannot just move the data with MCmemcpy().
		for(uint32 fromIndex = 0; fromIndex < toCopy; fromIndex++)
		{
			//We are making a copy of the element from the other array, so we need to cast the
			//constness away from the element.
			SetElem(fromIndex, const_cast<T*>(inFromCountedPtrArray[fromIndex]));
		}
	}
	else
	{
		//Should we set this array as invalid?
		MCNotify("Unable to complete operator=() memory allocation failed.");
	}
	return *this;
}
#endif

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

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

		SetGrowSize(initialGrowSize);
		SetZeroMem(initialZeroMem);

		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 TMCPtrArray<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 TMCPtrArray<T>::ArrayFree (void)
{
	if (IsValid())
	{
		if(ExternalMemory())
		{
			SetElemCount(0);
		}
		else
		{
			SetElemSpace(0);
		}
	}
}

// =================================================================================================================
// SetElemSpace - Change the amount of memory available for this array.
// =================================================================================================================
template<class T> boolean TMCPtrArray<T>::SetElemSpace(uint32 n)
{
	MCAssert(IsValid());
	MCAssert(GetElemSize()>0);	
	
	if (n == GetElemSpace())
	{
		return true;
	}

	if(!ExternalMemory())
	{
		if(n < GetElemCount())
		{
			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(GetElemSpace(), n) * GetElemSize());
				}
			}
			if (!newAddr)
			{
				MCNotify("Array allocation failed!");
				return false;
			}

			if(GetZeroMem())
			{
				if(n > fElemSpace)
				{
					MCmemfill8(
						0,
						newAddr + (fElemSpace * GetElemSize()),
						(n - fElemSpace) * GetElemSize());
				}
			}
		}
		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.
// =================================================================================================================
template<class T> boolean TMCPtrArray<T>::SetElemCount(uint32 n)
{
	MCAssert(IsValid());

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

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

	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.
// =================================================================================================================
template<class T> boolean TMCPtrArray<T>::AddElemCount(uint32 n)
{
	MCAssert(IsValid());
	MCAssert(n >= 0);
	
	n = n + GetElemCount();
	if (n > GetElemSpace())	
	{
		if (!GetGrowSize())
		{
			MCAssertMessage("fGrowSize is zero!!");
			return false;
		}

		int32 space;
		if(n % GetGrowSize())
		{
			space = (n/GetGrowSize() + 1)*GetGrowSize();
		}
		else
		{
			space = n;
		}

		if(!SetElemSpace (space))
		{
			return false;
		}
	}
		
	fElemCount = n;
		
	return true;
}


// =================================================================================================================
// SetElem
// =================================================================================================================
template<class T> void TMCPtrArray<T>::SetElem(uint32 index, const T*  data)
{
	MCAssert(IsValid());
	MCAssert(BaseAddress());

	MCAssert(index < GetElemCount());

	fArrayData[index] = const_cast<T*>(data);
}

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

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

// =================================================================================================================
// GetElem - Assign the index'th element of the array into data.
// =================================================================================================================
template<class T> void TMCPtrArray<T>::GetElem(uint32 index, T*&  data)
{
	MCAssert(IsValid());
	MCAssert(BaseAddress());
	MCAssert(index < GetElemCount());
	
	data = (*this)[index];
}

// =================================================================================================================
// AddElem - Add an element to the array an assign data to it.
// =================================================================================================================
template<class T> inline boolean TMCPtrArray<T>::AddElem (const T*  data)											
{
	MCAssert(IsValid());
	
	if (GetElemCount() == GetElemSpace())	
	{
		if (!SetElemSpace (GetElemSpace()+GetGrowSize()))
		{
			return false;
		}
	}

	if (!SetElemCount (GetElemCount() + 1))
	{
		return false;
	}				
	
	SetElem(GetElemCount() - 1, data);	

	return true;									
}

// =================================================================================================================
// 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 TMCPtrArray<T>::InsertElem(uint32 index, const T* data)
{
	MCAssert(IsValid());

	uint32 cnt	= GetElemCount();

	/*
		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 > cnt)
	{
		//We allow them to grow the array automatically by
		//inserting past the end of the array.
		if(AddElemCount(index - cnt + 1))
		{
			SetElem(index, data);
		}
		else
		{
			return false;
		}
	}
	else if(AddElemCount(1))
	{
		cnt = cnt - index;

		uint32 copySize = GetElemSize() * cnt;
		
		//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 srcOffset	= GetElemSize() * index;
			uint32 dstOffset	= GetElemSize() * (index + 1);
		
			MCAssertPointerCheck(BaseAddress());

			MCmemmove(BaseAddress() + dstOffset, BaseAddress() + srcOffset, copySize);
			if(GetZeroMem())
			{
				MCmemfill8(0, fArrayData + index, GetElemSize());
			}
		}

		SetElem(index, data);
	
		return true;
	}

	return false;
}
template<class T> uint32 TMCPtrArray<T>::FindNullPointersSuffixStart(uint32 index) const
{
	MCAssert(IsValid());
	MCAssert(BaseAddress());
	if(MCVerifyNot(index >= GetElemCount()))
		return kUnusedIndex;
	T** cur = &(ArrayData()[index]);
	for (uint32 i = index, n = GetElemCount(); i < n; ++i)
	{
		if (*cur)
			return kUnusedIndex;
	}
	cur = &(ArrayData()[index]);
	for (uint32 lastTestedIdx = index, numAdditionalPointers = 0; lastTestedIdx > 0; --lastTestedIdx, ++numAdditionalPointers)
	{
		if (*(--cur))
			return lastTestedIdx;
	}
	return 0;


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

		if (index + count > GetElemCount())
		{
			MCNotify("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);

		MCmemmove(BaseAddress() + memLoc, BaseAddress() + srcMemLoc, copySize);

		if(GetZeroMem())
		{
			MCmemfill8(	0,
						BaseAddress() + memLoc + copySize,
						GetElemSize() * count);
		}

		SetElemCount(GetElemCount() - count);
	}
}

// =================================================================================================================
// Erase
// =================================================================================================================
// Erase the elements of the array from startIterator to endIterator.
template<class T> void TMCPtrArray<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 numItems (starting at startIndex) items of fromArray into this list at position insertIndex
template<class T> boolean TMCPtrArray<T>::CopyElems(const TMCPtrArray<T>& fromArray, uint32 startIndex, uint32 numItems, uint32 insertAtIndex) 
{
	boolean	result = AddElemCount(numItems);

	if(result)
	{
		if(startIndex < fromArray.GetElemCount())
		{
			if(startIndex + numItems >= fromArray.GetElemCount())
			{
				numItems = fromArray.GetElemCount() - startIndex;
			}

			T** src	= Pointer(insertAtIndex);

			//Move our items after the ones we are copying
			int32 howManyToMove = GetElemCount() - insertAtIndex - numItems;
			if (howManyToMove != 0)
			{
				T** dst	= Pointer(insertAtIndex + numItems);

				//Move the items in our array to their new location.
				MCmemmove(dst, src, howManyToMove * GetElemSize());
			}
			
			//Copy the data from fromArray into us.
			MCmemcpy(src, fromArray.Pointer(startIndex), numItems * GetElemSize());
		}
	}
	return result;
}

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

// =================================================================================================================
// FillWithValue - Fill an array range with the value passed in.
// =================================================================================================================
template<class T> void TMCPtrArray<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++] = const_cast<T*>(inValue);
		}
	}
}

// =================================================================================================================
// Swap - Swaps the contents of two arrays..
// =================================================================================================================
template<class T> void TMCPtrArray<T>::Swap(TMCPtrArray<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();
}

template<class T> inline void TMCPtrArray<T>::RemoveElem(T* elemToRemove) 
{
	uint32 i;
	T** cur = ArrayData();
	for (i=0; i<GetElemCount(); i++, cur++) 
	{
		if (*cur == elemToRemove) 
		{
			RemoveElem(i, 1);
			return;
		}
	}
}

template<class T> inline uint32 TMCPtrArray<T>::FindElem(const T* item) const 
{
	uint32 i;
	uint32 result = kUnusedIndex;

	T** cur = ArrayData();

	for (i=0; i<GetElemCount(); i++, cur++) 
	{
		if (*cur == item)
		{
			result = i;
			break;
		}
	}
	return result;
}

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

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

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

#define MC_DECLARE_PTR_ARRAY(tableType, tableName) typedef TMCPtrArray<tableType> tableName


#endif
