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


		MCCountedPtrArray.h


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


		Author:	Charles
		Date:	06/25/99

		Revision History

		when		who			what & why
		==========	==========	======================================================
		12/08/99	Arnaud		added smart grow.
		10/18/99	Nba			added qTrackArray for tracking reallocations of arrays
		9/2/99		Ian			Added a parallel context array, see MCCountedPtr.h & .cpp
								for information about CountedPtrContexts.
		8/11/99		Ian			SetElemSpace() needed to copy the min of new and old elements.
		7/29/99		Ian			Compiler specific code for friend declarations.
		7/26/99		Pierre		In SetElem protected the case where old == new
					
*****************************************************************************************/

#ifndef __MCCOUNTEDPTRARRAY__
#define __MCCOUNTEDPTRARRAY__

#if CP_PRAGMA_ONCE
#pragma once
#endif

#include "MCMath.h"
#include "MCPtrArray.h"

/// \addtogroup MCCore
/// \{

/// <P>TMCCountedPtrArray is an array used to store pointers to counted objects.
/// It ensures that the refcount of all the objects is properly and automatically updated.</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, TMCPtrArray, TMCClassArray and TMCExtensibleArray. </P>
///
template <class T> class TMCCountedPtrArray : 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
	/// 
	TMCCountedPtrArray			(void);

	// ****************************************************************************
	//								TMCCountedPtrArray
	// 
	/// Constructs an array with a certain number of elements already accessible (and initialized to NULL).
	/// 
	/// \param initialCount    initial number of array elements.
	/// 
	explicit TMCCountedPtrArray			(uint32	initialCount);		//Initial number of array elements.

	// ****************************************************************************
	//								TMCCountedPtrArray
	// 
	/// 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
	/// 
	TMCCountedPtrArray			(uint32	initialCount,
								 uint32	initialSpace,
								 uint32	initialGrowSize);


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

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


	// ****************************************************************************
	//								TMCCountedPtrArray
	// 
	/// 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.
	/// 
	TMCCountedPtrArray			(T** const&	baseAddress,
								 boolean	inAquireMemory,
								 uint32		elemCount,
								 uint32		elemSpace);

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

	/// Releases all the elements of the array and frees the memory (if the array owns it).
	///
	~TMCCountedPtrArray			(void);


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

	/// Declare iterator types for this array
	///
	typedef TMCPtrIterator<T, TMCCountedPtrArray<T> > iterator;

	/// Declare iterator types for this array
	///
	typedef TMCConstPtrIterator<T, TMCCountedPtrArray<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
	// 
	/// Releases all the elements of the array and frees the memory (if the array owns it)
	///	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 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;}

	/// 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);}
	iterator			End					(void)			{return iterator(*this,kEndIndex);}

	/// Returns the first element in the array (addrefs it).
	///
			void		FirstElem			(T** data);


	/// Returns the first element in the array (without calling addref on it).
	///
			T*			FirstElemNoAddRef	(void);

	/// Returns the first element in the array (without calling addref on it).
	///
			const T*	FirstElemNoAddRef	(void) const;

	// Returns the last element in the array (addrefs it).
			void		LastElem			(T** data);

	/// Returns the last element in the array (without calling addref on it).
	///
			T*			LastElemNoAddRef	(void);

	/// Returns the last element in the array (without calling addref on it).
	///
			const T*	LastElemNoAddRef	(void) const;

	/// 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 TMCCountedPtrArray<T>&	fromArray, uint32 startIndex,
											 uint32	nbItems, uint32 insertIndex);

	/// Append one array on to the end of another.
	///
			boolean		Append				(const TMCCountedPtrArray<T>& fromArray);

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

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


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

	
	// ****************************************************************************
	//								operator []
	// 
	///	Returns the data at the passed in index. 
	///
	/// \note the returned value is not a reference to the array element, so you cannot
	/// assign into an array with these operators (not an lvalue, and if it was we couldn't automatically update the refcount).
	/// 
	/// \param i  the index of the element to return
	/// 
	inline T* 		operator[]		(uint32 i) 				
	{ MCAssert(IsValid()); MCAssert(i < GetElemCount()); return fArrayData[i]; }

	// ****************************************************************************
	//								operator []
	// 
	///	Returns the data at the passed in index. 
	///
	/// \note the returned value is not a reference to the array element, so you cannot
	/// assign into an array with these operators (not an lvalue, and if it was we couldn't automatically update the refcount).
	/// 
	/// \param i  the index of the element to return
	///
	inline T*		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.
	///
	boolean			SetElem			(uint32 index, T* data);

	/// Get the contents of arrray index into the passed in data reference.
	///
	boolean			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			(T* data);

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

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

	/// Removes one element from the array starting from the passed in index.
	///
	void			RemoveElem		(T* elemToRemove);

	/// Gets 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
	///
	/// \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;

	/// In debug, verifies that the refcount of every object in the array is 1 
	/// (ie they'll be deleted when the array is destroyed)
	///
	void			CheckLastRefs	();

	/// 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;}
	
	void				Swap(TMCCountedPtrArray<T>& fromArray);

protected:
#if __MWERKS__
	friend class iterator;
	friend class const_iterator;
#elif __GNUC__
	friend class TMCCountedPtrArray<T>::iterator;
	friend class TMCCountedPtrArray<T>::const_iterator;
#else
	friend iterator;
	friend const_iterator;
#endif

#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
				}
#if Debug_ && qRecordCountedPtrRefs
private:
	CountedPtrContext*	fContexts;
	uint32				fContextCount;
#endif
};
/// \}

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


template<class T> TMCCountedPtrArray<T>::TMCCountedPtrArray (void) 
{
#if Debug_ && qRecordCountedPtrRefs
	fContexts		= NULL;
	fContextCount	= 0;
#endif
	if(!ArrayAlloc(0, 0, eDefaultGrowSize))
	{
		MCNotify("Array allocation failed in constructor!");
	}
	else
	{
		fArrayFlags|=eZeroMem;
	}
	SetSmartGrow();
	MCAssert(IsValid());
}
  

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

template<class T> TMCCountedPtrArray<T>::TMCCountedPtrArray(uint32	initialCount)	//Initial number of elements
{
#if Debug_ && qRecordCountedPtrRefs
	fContexts		= NULL;
	fContextCount	= 0;
#endif
	if(!ArrayAlloc(initialCount, initialCount, 0))
	{
		MCNotify("Array allocation failed in constructor!");
	}
	else
	{
		fArrayFlags|=eZeroMem;
	}
	SetSmartGrow();
	MCAssert(IsValid());
}

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

template<class T> TMCCountedPtrArray<T>::TMCCountedPtrArray (
	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 Debug_ && qRecordCountedPtrRefs
	fContexts		= NULL;
	fContextCount	= 0;
#endif
	if(!ArrayAlloc(initialCount, initialSpace, initialGrowSize))
	{
		MCNotify("Array allocation failed in constructor!");
	}
	else
	{
		fArrayFlags|=eZeroMem;
	}
	MCAssert(IsValid());
}


// =================================================================================================================
// Construction - Copy constructors
// =================================================================================================================

template<class T> TMCCountedPtrArray<T>::TMCCountedPtrArray(const TMCCountedPtrArray<T>& inFromArray)
{
#if Debug_ && qRecordCountedPtrRefs
	fContexts		= NULL;
	fContextCount	= 0;
#endif
	if(!ArrayAlloc(0, 0, inFromArray.GetGrowSize()))
	{
		MCNotify("Array allocation failed in constructor!");
	}
	else
	{
		fArrayFlags|=eZeroMem;
		*this = inFromArray;
	}
}

template<class T> TMCCountedPtrArray<T>::TMCCountedPtrArray(const TMCPtrArray<T>& inFromPtrArray)
{
#if Debug_ && qRecordCountedPtrRefs
	fContexts		= NULL;
	fContextCount	= 0;
#endif
	if(!ArrayAlloc(0, 0, inFromPtrArray.GetGrowSize()))
	{
		MCNotify("Array allocation failed in constructor!");
	}
	else
	{
		fArrayFlags|=eZeroMem;
		*this = inFromPtrArray;
	}
}

// =================================================================================================================
// Construction - from external memory
//	Note: If you pass inAquireMemory = false then this array CANNOT grow past elemSpace,
//	and will not free the memory passed in.
// =================================================================================================================
template<class T> TMCCountedPtrArray<T>::TMCCountedPtrArray(
	T** const &	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.
{
#if Debug_ && qRecordCountedPtrRefs
	fContexts		= NULL;
	fContextCount	= 0;
#endif
	if(!ArrayAllocFromBuffer(baseAddress, inAquireMemory, elemCount, elemSpace))
	{
		MCAssert (0);
		return;
	}
	fArrayFlags|=eZeroMem;
}

// =================================================================================================================
// 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> TMCCountedPtrArray<T>::TMCCountedPtrArray(
	TMCCountedPtrArray<T>&	array,		//Alias elements from this array.
	uint32					elemStart,	//Start alias here.
	uint32					elemCount)	//Alias this many elements.
{
#if Debug_ && qRecordCountedPtrRefs
	fContexts		= NULL;
	fContextCount	= 0;
#endif
#if Debug_
	MCAssert((elemStart < array.GetElemCount()) && (elemStart + elemCount < array.GetElemCount()));
#endif
	if(!ArrayAllocFromBuffer(&array[elemStart], false, elemCount, elemCount))
	{
		MCNotify("Array allocation failed in constructor!");
	}
	else
	{
		fArrayFlags |= eArrayAlias;
		fArrayFlags |= eZeroMem;
	}
	MCAssert(IsValid());
}

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

#if Debug_ && qRecordCountedPtrRefs
	if(fContexts)
	{
		MCfree(fContexts);
		fContexts = NULL;
	}
#endif
}

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

		uint32 toCopy = inFromArray.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*>(inFromArray[fromIndex]));
			}
		}
		else
		{
			//Should we set this array as invalid?
			MCNotify("Unable to complete operator=() memory allocation failed.");
		}
	}
	return *this;
}

// =================================================================================================================
// operator= - Copy all the elements from fromArray into this array, overwrites this arrays existing
//	elements.
// =================================================================================================================
template<class T> TMCCountedPtrArray<T>& TMCCountedPtrArray<T>::operator=(const TMCPtrArray<T>& inFromPtrArray)
{
	//Short circut test, if we are being assigned to ourself.
	if (inFromPtrArray.GetSmartGrow())	//Copy the SmartGrow flag
		SetSmartGrow();
	
	uint32 toCopy = inFromPtrArray.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*>(inFromPtrArray[fromIndex]));
		}
	}
	else
	{
		//Should we set this array as invalid?
		MCNotify("Unable to complete operator=() memory allocation failed.");
	}
	return *this;	
}

// =================================================================================================================
// ArrayAlloc
// =================================================================================================================
template<class T> boolean TMCCountedPtrArray<T>::ArrayAlloc(uint32 initialCount, uint32	initialSpace, uint32 initialGrowSize)
{
	ZeroInternals ();
	
	fArrayFlags |= eValid;

	if (initialCount > initialSpace)
	{
		fArrayFlags &= ~eValid;
		return false;
	}
	
	MCAssert(!ExternalMemory());
	fArrayFlags &= ~eExternalMem;

	SetGrowSize(initialGrowSize);

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

	if (!SetElemCount (initialCount))
	{
		fArrayFlags &= ~eValid;
		return false;
	}

	return true;
}

// =================================================================================================================
// ArrayAlloc - from external memory
// =================================================================================================================
template<class T> boolean TMCCountedPtrArray<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 TMCCountedPtrArray<T>::ArrayFree (void)
{
	if (IsValid())
	{
		for(uint32 releaseElemIndex = 0;  releaseElemIndex < GetElemCount(); releaseElemIndex++)
		{
			SetElem(releaseElemIndex, NULL);
		}
		SetElemCount(0);

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

// =================================================================================================================
// SetElemSpace
// =================================================================================================================
template<class T> boolean TMCCountedPtrArray<T>::SetElemSpace(uint32 n)
{
	MCAssert(IsValid());
	MCAssert(GetElemSize()>0);	
	
	//Easy out, we are already at the correct size.
	if (n == GetElemSpace())
	{
		return true;
	}

	//Can only resize if it is our own memory.
	if(!ExternalMemory())
	{

#if 0
//This was neccessary before I fixed the MCmemcpy() bugs below, but
//I think it is potentially dangerous, so I'm commenting it out for now.
		if(n < GetElemCount())
		{
			fElemCount = n;
		}
#endif

		//Caclulate the new memory size (in bytes).
		uint32	newSize	= GetElemSize() * n;
		int8*	newAddr;
		int8*	oldAddr = nil;

		//Try to resize base address
		if(newSize)
		{
			if (!BaseAddress()) 
			{
				newAddr = (int8*)MCmalloc(newSize);
#if Debug_ && qRecordCountedPtrRefs
				fContexts		= (CountedPtrContext*)MCmalloc(n * sizeof(CountedPtrContext));
				fContextCount	= n;
#endif
			}
			else
			{
				oldAddr = BaseAddress();
				newAddr = (int8*)MCmalloc(newSize);
				if (newAddr)
				{
#ifdef qTrackArray
					ReallocCalled();
#endif
					MCmemcpy(newAddr, oldAddr, MC_Min(n, GetElemSpace()) * GetElemSize());
				}
#if Debug_ && qRecordCountedPtrRefs
				CountedPtrContext* oldContexts = fContexts;
				fContexts = (CountedPtrContext*)MCmalloc(n * sizeof(CountedPtrContext));
				if (fContexts)
				{
					fContextCount = n;
					MCmemcpy(fContexts, oldContexts, MC_Min(n, GetElemSpace()) * GetElemSize());
					MCfree(oldContexts);
				}
#endif
			}

			if (!newAddr)
			{
				MCAssertMessage("Array allocation failed!");
				return false;
			}

			if(n > fElemSpace)
			{
				MCmemfill(
					0,
					newAddr + (fElemSpace * GetElemSize()),		//Fill from.
					(n - fElemSpace) * GetElemSize());			//Amount of data to fill.
#if Debug_ && qRecordCountedPtrRefs
				MCmemfill(
					0,
					fContexts + fElemSpace,							//Fill from.
					(n - fElemSpace) * sizeof(CountedPtrContext));	//Amount of data to fill.
#endif
			}
		}
		else
		{
			if (BaseAddress())
			{
				MCfree(BaseAddress());
			}

#if Debug_ && qRecordCountedPtrRefs
			if(fContexts)
			{
				fContextCount = 0;
				MCfree(fContexts);
				fContexts = NULL;
			}
#endif
			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 TMCCountedPtrArray<T>::SetElemCount(uint32 n)
{
	MCAssert(IsValid());

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

	if(n < GetElemCount())
	{
		//Removing elements, must use SetElem() to properly clear the data.
		uint32 removeIndex = GetElemCount();
		while(removeIndex > n)
		{
			SetElem(removeIndex - 1, NULL);

			removeIndex--;
		}
	}

	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 if neccessary.
// =================================================================================================================
template<class T> boolean TMCCountedPtrArray<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 - Assign data to the index'th element of the array.
// =================================================================================================================
template<class T> boolean TMCCountedPtrArray<T>::SetElem(uint32 index, T* data)
{
	MCAssert(IsValid());
	MCAssert(BaseAddress());

	MCAssert(index < GetElemCount());
	T* old = fArrayData[index];
	if (old != data)
	{
		if(old != NULL)
		{
#if Debug_ && qRecordCountedPtrRefs
			MCAssert(fContextCount > index);
			RemoveCPStackReference<T>(old, fContexts[index]);
#endif
			old->Release();
		}

		if (data)
		{
			data->AddRef();
#if Debug_ && qRecordCountedPtrRefs
			if(fContexts[index] == 0)
			{
				fContexts[index] = GetNewCountedPtrContext();
			}
			MCAssert(fContextCount > index);
			AddCPStackReference<T>(data, fContexts[index]);
#endif
		}
#if Debug_ && qRecordCountedPtrRefs
		else if(fContexts[index] != 0)
		{
			MCAssert(fContextCount > index);
			ReleaseCountedPtrContext(fContexts[index]);
		}
#endif
		//We happen to know that the size of this element is 4 bytes and it is much
		//faster to just do the assignment.
		fArrayData[index] = data;
	}
	return true;
}

// =================================================================================================================
// GetElem
// =================================================================================================================
template<class T> boolean TMCCountedPtrArray<T>::GetElem(uint32 index, T** data) const
{
	MCAssert(IsValid());
	MCAssert(BaseAddress());

	MCAssert(index < GetElemCount());
	
	ReleaseIfNotNull<T>(data);
	*data = fArrayData[index];

	if (*data)
	{
		(*data)->AddRef();

#if Debug_ && qRecordCountedPtrRefs
		if(macroIsCountedPtr(data))
		{
			AddCPStackReference<T>(*data, macroRetreiveCPContext(data));
		}
		else
		{
			AddPStackReference<T>(*data, data);
		}
#endif
	}

	return true;
}


// =================================================================================================================
// AddElem
// =================================================================================================================
template<class T> inline boolean TMCCountedPtrArray<T>::AddElem (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 TMCCountedPtrArray<T>::InsertElem(uint32 index, 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)
		{
			uint32 srcOffset	= GetElemSize() * index;
			uint32 dstOffset	= GetElemSize() * (index + 1);
		
			MCAssertPointerCheck(BaseAddress());

			// Since the regions overlap we must move memory with MCmemmove instead of MCmemcpy.
			MCmemmove(BaseAddress() + dstOffset, BaseAddress() + srcOffset, copySize);

#if Debug_ && qRecordCountedPtrRefs
			if (fContexts)
			{
				//Move the contexts to keep them aligned with the array elements
				MCmemmove(
					fContexts + (index + 1),			//Move to 1 past the inserted index.
					fContexts + index, 					//Move from the inserted index.
					cnt * sizeof(CountedPtrContext));	//Moving "count" items.
			}
#endif

			//We just moved the items up one, and left index's element with a stale
			//value, clear it.
			fArrayData[index] = NULL;

		}

		SetElem(index, data);
	
		return true;
	}

	return false;
}

// =================================================================================================================
// RemoveElem - Remove an element from the array.
// =================================================================================================================
template<class T> boolean TMCCountedPtrArray<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;
		}

		for (uint32 ii = index; ii < index+count; ii++)
		{
			if(fArrayData[ii] != NULL)
			{
#if Debug_ && qRecordCountedPtrRefs
				MCAssert(fContextCount > ii);
				RemoveCPStackReference<T>(fArrayData[index], fContexts[ii]);
				ReleaseCountedPtrContext(fContexts[ii]);
#endif
				fArrayData[ii]->Release();
			}
		}

		uint32 memLoc		= GetElemSize() * index;
		uint32 srcMemLoc	= GetElemSize() * (index + count);
		uint32 copySize		= GetElemSize() * (GetElemCount() - index - count);
		
		MCmemmove(
			BaseAddress() + memLoc,		//Move from index
			BaseAddress() + srcMemLoc,	//Move to index + count
			copySize);					//Move this many items.
		
		MCmemfill(	0,									//Fill the last "count" number
					BaseAddress() + memLoc + copySize,	//of elements in the array data
					GetElemSize() * count);				//with NULL.

#if Debug_ && qRecordCountedPtrRefs
		MCmemmove(
			fContexts + index,												//Move to index.
			fContexts + (index + count),									//Move from index + count.
			(GetElemCount() - index - count) * sizeof(CountedPtrContext));	//Move this many items.
		
		MCmemfill(
			0,									//Fill the last "count" number
			fContexts + GetElemCount() - count,	//of items in the fContexts
			count * sizeof(CountedPtrContext)); //array with 0.
#endif

		SetElemCount(GetElemCount() - count);
	}
	return true;
}

// =================================================================================================================
// Erase - Remove the elements of the array from startIterator to endIterator.
// =================================================================================================================
template<class T> void TMCCountedPtrArray<T>::Erase(const iterator& startIterator, const iterator& endIterator)
{
	MCAssertIfFalse(startIterator.fMyArray == endIterator.fMyArray);
	if(startIterator.fMyArray != endIterator.fMyArray)
	{
		MCAssertIfFalse(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.
// =================================================================================================================
// Inserts nbItems (starting at firstIndex) items of fromArray into this list at position insertIndex
template<class T> boolean TMCCountedPtrArray<T>::CopyElems(
	const TMCCountedPtrArray<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.
	while(fromIndex < lastFrom && result)
	{
		result = InsertElem(toIndex, const_cast<T*>(fromArray[fromIndex]));
		fromIndex++;
		toIndex++;
	};
	return result;
}

#define MC_DECLARE_COUNTED_PTR_ARRAY(tableType, tableName) typedef TMCCountedPtrArray<tableType> tableName

template<class T> inline void TMCCountedPtrArray<T>::FirstElem(T** data)
{
	GetElem(0, data);
}

template<class T> inline T* TMCCountedPtrArray<T>::FirstElemNoAddRef(void)
{
	return *fArrayData;
}

template<class T> inline const T* TMCCountedPtrArray<T>::FirstElemNoAddRef(void) const
{
	return *fArrayData;
}

template<class T> inline void TMCCountedPtrArray<T>::LastElem(T** data)
{
	GetElem(fElemCount - 1, data);
}

template<class T> inline T* TMCCountedPtrArray<T>::LastElemNoAddRef(void)
{
	return *(fArrayData + fElemCount - 1);
}

template<class T> inline const T* TMCCountedPtrArray<T>::LastElemNoAddRef(void) const
{
	return *(fArrayData + fElemCount - 1);
}

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

template<class T> inline uint32 TMCCountedPtrArray<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;
}

template<class T> void TMCCountedPtrArray<T>::CheckLastRefs()
{
#if Debug_
	for(uint32 releaseElemIndex = 0;  releaseElemIndex < GetElemCount(); releaseElemIndex++)
	{
		T* obj = ArrayData()[releaseElemIndex];
		obj->AddRef();
		uint refCount = obj->Release();
		if(refCount != 1)
		{
			MCNotify("this pointer is supposed to be the last reference");
#if qRecordCountedPtrRefs
			// the next line will assert : (conntext alread exist)
			// at this point, you will see what other contexts are leaking
//			if (refCount > 1) AddStackReference<T>(obj, this);
			ExploreStackReferencesIU(obj);
#endif
		}
	}
#endif
}


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



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

#if Debug_ && qRecordCountedPtrRefs
	{
		CountedPtrContext* tmp = fContexts;
		fContexts = fromArray.fContexts;
		fromArray.fContexts = tmp;
	}

	{
		uint32 tmp = fContextCount;
		fContextCount = fromArray.fContextCount;
		fromArray.fContextCount = tmp;
	}
#endif
}


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

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

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

#endif