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


		MCArray.h


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


		Author:	Pierre (from Sree's PB classes).
		Date:	12/11/97

		This file contains the declaration for the TMCArray template class.
		The TMCArray is a "typed" array, this means that the elements stored within
		the array retain their type information and that you should not need to cast
		array accesses to get the correct type.
	
		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/23/99		Ian			Replaced MCMemory.h by MCMemoryAlloc.h & MCMemoryCopy.h.
		09/11/99	Pierre		Fixed Swap
		8/11/99		Ian			SetElemSpace() needed to copy the min of new and old elements.
		7/7/99		Ian			Swap(): Wasn't taking a reference so we were making a copy.
		6/10/99		Ian			Array API changes.
		05/20/99	dsm			fixed an assert
		5/17/99		Ian			Added kBeginIndex.
		4/22/99		Ian			Fixed a bug with Reset() used to set itself to the first
								element in the array which isn't right if there are no
								elements in the array, it now sets itself to fMyArray.Begin().
		4/7/99		psq			Fixed friend problem introduced by Ian's last changed (not sure it will
								work on Mac).
		4/6/99		Ian			Fixed some illegal friend declarations that MW and VC were
								letting us get away with.
		3/5/99		psq			checks newAddr before MCmemcpy in SetElemSpace
		03/02/99	dsm			formatted [] inline accessors on one line for debug purpose
		12/2/98		Eml			Made SetElemSpace SMP friendly : no longer does MLRealloc
		11/25/98	Ian			Cleaned out the last of the sorting stuff.
		11/12/98	MAZ			added MC_DECLARE_ARRAY
		11/06/98	pbk			removed pb compatibility macros.
		11/03/98	pbk			decreased the size of the array from 76 bytes to 20 bytes
								added functionality to create an array from existing data 
								or as subarray from another array
		10/26/98	del/dsm		replaced = by MCmemcpy in TMCArray::SetElem
		10/19/98	Thierry		fCustomData set to NULL in ZeroInternals
		10/14/98	Ian			Fixed sorting.
		9/9/98		Ian			Cleaned out some dead code, got rid of ResetArray(),
								use ArrayFree() instead. Implemented the fZeroMem flag.
								AddElem now uses SetElem() instead of assigning
								directly into the array.
		9/3/98		psq			massive overhaul
		8/6/98		Greg		Fixed double parentheses on line 485 (for Craig)
		06/08/98	Nba			Added Last, Prev and MorePrev to iterator
		6/2/98		Greg		Made InsertElem virtual, so I could override it in
								TMCClassArray()
		5/7/98		Ian			Had to make some functions virtual, so that the TMCClassArray
								would work right.
		5/6/98		Ian			Moved class safe code to MCClassArray.
		5/5/98		Ian			Iterator::operator =() can't change arrays.
								Changed a bunch of (T*)BaseAddress() to ArrayData(), and fixed
								a bug in RemoveElem() that was going removing from the wrong
								place. Also did a little work on the Sort code, but it
								still doesn't work.
		4/14/98		Joshua		Fixed backward asserts in FirstElem and LastElem
		4/6/98		Ian			Implemented CopyElems(), not the most efficient method but
								it'll do.
		4/06/98		Emil		changed fCurrent++ to ++ fCurrent in iterator::Next()
		3/24/98		link		Removed unused variable in QMiddle().
		3/23/98		Ian			Added FirstElem, and LastElem, added an Erase that takes
								a start and end iterator.
		3/20/98		Ian			Cleaned up TMCArray class, added const functions where
								appropriate. Unprotected iterator constructor, there is no
								real reason it needs to be protected.
		3/16/98		Ian			Changed MCmemcpys to MCmemmoves. MCmemcpy doesn't deal with
								the case where you are copying overlaping memory blocks,
								MCmemmove does.
		3/15/98		Ian			Added operator = for iterator.
		3/11/98		link		Fixed unused arguments warnings.
		3/5/98		Ian			Added comments and cleaned up the code a little.
		3/2/98		Ian			Added this header, and added the ifndef __MWERKS__ around
								the pragma warning.

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

#ifndef __MCArray__
#define __MCArray__

#include "MCArrayTypes.h"
#include "MCAssert.h"
#include "MCBasicDefines.h"
#include "MCBasicTypes.h"
#include "MCIterator.h"
#include "MCMath.h"
#include "MCMemoryAlloc.h"
#include "MCMemoryCopy.h"
#include "MCStatusCode.h"



//#include <string.h>


// =================================================================================================================
// TMCArray
// =================================================================================================================

#ifdef  _MSC_VER	// visual c++ 
	//disable "this used in base member initializer list" warning from VC
#pragma warning( disable : 4355)
#endif

/// \addtogroup MCCore
/// \{

/// <P>TMCArray is an array used to store simple types, structs or classes that don't need a constructor nor a destructor.
/// For example, you can use it with int32, TVector3, TMCString255, 
/// but <B>not</B> with TMCDynamicString (memory leaks on destruction). </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, 
/// 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: TMCPtrArray, TMCCountedPtrArray, TMCClassArray and TMCExtensibleArray, TMCStaticArray and TMCStaticClassArray. </P>
///
template<class T> class TMCArray : 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
	///
	TMCArray		(void);

	// ****************************************************************************
	//								TMCArray
	// 
	/// 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 ?
	/// 
	TMCArray		(uint32	 initialCount,
					 boolean initialZeroMem);

	// ****************************************************************************
	//								TMCArray
	// 
	/// 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 ?
	/// 
	TMCArray		(uint32	 initialCount,
					 uint32	 initialSpace,
					 uint32	 initialGrowSize,
					 boolean initialZeroMem);

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


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

	/// Frees the memory used by the array (if it owns it).
	/// 
	~TMCArray		(void);


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


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

protected:	
	// Allocate the array, disregards the existing data so be careful calling this explicitly (can create leak?).
	/// <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 (can create leak?)
	/// <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:

	///Frees existing Data, then references an existing array without taking ownership
	void	ArrayAlias				(T*		 baseAddress,		///External memory to use for this array.
									 uint32	 elemCount);		///The number of array elements in use in that memory.

	void	ArrayAlias				(T*		 baseAddress,		///External memory to use for this array.
									 uint32	 elemCount,		
									 uint32	 elemSpace);		///The number of array elements in use in that memory.

	void	ArrayAlias				(void*	 baseAddress,		///External memory to use for this array.
									 uint32	 elemCount,		
									 uint32	 elemSpace)			///The number of array elements in use in that memory.
	{ ArrayAlias((T*)baseAddress, elemCount, elemSpace); }

	void	ArrayAlias				(TMCArray<T>& sourceArray);

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



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

	/// Sets the number of elements to have memory allocated for.
	///	\note This memory is unconstructed, uninitialized (if GetZeroMem is false) 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		(MCSize nAsMCSize);

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

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

	/// Returns an iterator initialized to the beginning 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&		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 TMCArray<T>&	fromArray, uint32 startIndex, uint32 nbItems, uint32 insertIndex);

	/// Append one array on to the end of another.
	/// 
	boolean			Append			(const TMCArray<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			(TMCArray<T>& fromArray);

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

	/// Returns a pointer to the data at the passed in index.
	/// 
	inline T*		Pointer			(MCSize i)			{MCAssert(IsValid());				
															 MCAssert(i < GetElemCount());			
															 return fArrayData + i;}					

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

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

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

	/// Sets the value of a number of elements of the array, grows the array if necessary
	void Assign(int32 elemCount, const T& value);
	void AssignArithmeticalSuite(int32 elemCount, const T &u0, const T &a);		

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

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

	/// Inserts elements at the given index
	///
	/// \param index  where to insert
	/// \param count  number to insert
	/// \param data   the data to insert
	boolean			InsertElem		(uint32 index, uint32 count, const T& data);

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


	// ****************************************************************************
	//								FindElem
	// 
	/// Finds the index of the first instance of item in the array (if it exists).
	/// 
	/// \param item  the item to serch for
	/// \return ::kUnusedIndex if item is not in the array, otherwise a valid index
	///
	uint32 FindElem(const T& item) const;

	// ****************************************************************************
	//								DichoSearch
	// 
	/// Finds the index of an instance of item in the array.
	///
	/// \return ::kUnusedIndex if item is not in the array, otherwise a valid index
	///
	int32 DichoSearch(const int32 beginIndex,const int32 endIndex, const T &item) const;
	int32 DichoSearch(const T &item) const;

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

	void ReorderArray(const TMCArray<int32>& reoderedIndex);

protected:
#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
											}
};
/// \}


// Alloc array on the stack using alloca.
// WARNING: make sure you know well how alloca is working
// before using this as the memory will not be always available
#define AllocaArray(array, size)			array.ArrayAlias(alloca(size*array.GetElemSize()), 0, size);


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

// =================================================================================================================
// Construction
// =================================================================================================================
template<class T> TMCArray<T>::TMCArray(
	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> TMCArray<T>::TMCArray(
	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 - Copy constructor 
// =================================================================================================================

template<class T> TMCArray<T>::TMCArray(
	const TMCArray<T>&	inFromArray)
{
	if(!ArrayAlloc(0, 0, inFromArray.GetGrowSize(), true))
	{
		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> TMCArray<T>::TMCArray (
	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> TMCArray<T>::TMCArray(
	TMCArray<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> TMCArray<T>::~TMCArray (void)
{
	ArrayFree();
	fArrayFlags &= ~eValid;
}

// =================================================================================================================
// operator= - Copy all the elements from fromArray into this array, overwrites this arrays existing
//	elements.
// =================================================================================================================
template<class T> TMCArray<T>& TMCArray<T>::operator=(const TMCArray<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;
}

// =================================================================================================================
// ArrayAlloc - Ignores existing data, so be carefull if you are calling this explicitly.
// =================================================================================================================
template<class T> boolean TMCArray<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 TMCArray<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;
	}
}

///Frees existing Data, then references an existing array without taking ownership
template<class T> void TMCArray<T>::ArrayAlias(	T*		 baseAddress,
												uint32	 elemCount)
{
	ArrayFree();
	ArrayAllocFromBuffer(baseAddress, false, elemCount, elemCount);
}

template<class T> void TMCArray<T>::ArrayAlias(	T*		 baseAddress,
												uint32	 elemCount,
												uint32	 elemSpace)
{
	ArrayFree();
	ArrayAllocFromBuffer(baseAddress, false, elemCount, elemSpace);
}

template<class T> void TMCArray<T>::ArrayAlias(TMCArray<T>& sourceArray)
{
	ArrayAlias(sourceArray.ArrayData(),sourceArray.GetElemCount());
}



// =================================================================================================================
// 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 TMCArray<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 TMCArray<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, fElemCount * GetElemSize());
				}
			}
			if (!newAddr)
			{
				MCNotify("Array allocation failed!");
				return false;
			}

			if(GetZeroMem())
			{
				if(n > fElemCount)
				{
					MCmemfill8(
						0,
						newAddr + (fElemCount * GetElemSize()),
						(n - fElemCount) * 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 necessary.
// =================================================================================================================
template<class T> boolean TMCArray<T>::SetElemCount(MCSize nAsMCSize)
{
	MCAssert(IsValid());

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

	uint32 n(static_cast<uint32>(nAsMCSize));

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

	// to make sure that elements are still initialized to zero when the size of the array
	// decreases (Charles Dec 2006)
	if (GetZeroMem() && n < fElemCount)
	{
		MCmemfill8(0,BaseAddress() + (n * GetElemSize()),
						(fElemCount-n) * GetElemSize());
	}

	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 TMCArray<T>::AddElemCount(uint32 n)
{
	MCAssert(IsValid());
	MCAssert(n >= 0);
	
	n = n + GetElemCount();
	if (n > GetElemSpace())	
	{
		if (!GetGrowSize())
		{
			MCNotify("grow size 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;
}

template<class T> void TMCArray<T>::AssignArithmeticalSuite(int32 elemCount, const T &u0, const T &a)
{
	SetElemCount(elemCount);

	T currentValue = u0;

	for (int32 elemIndex=0; elemIndex<elemCount; elemIndex++)
	{
		fArrayData[elemIndex] = currentValue;
		currentValue = currentValue + a;
	}
}

/// Sets the value of a number of elements of the array
template<class T> void TMCArray<T>::Assign(int32 elemCount, const T& value)
{
	SetElemCount(elemCount);

	for (int32 i=0;i<elemCount;i++)
	{
		SetElem(i,value);
	}
}



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

	MCAssert(index < GetElemCount());

	if(GetElemSize() < kStructureCopyThreshold)
	{
		fArrayData[index] = data;
	}
	else
	{
		MCmemcpy(&fArrayData[index], &data, GetElemSize());
	}
}

// =================================================================================================================
// GetElem - Assign the index'th element of the array into data.
// =================================================================================================================
template<class T> void TMCArray<T>::GetElem(uint32 index, T&  data) const
{
	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 TMCArray<T>::AddElem(const T& data)											
{
	MCAssert(IsValid());
	
	if (GetElemCount() == GetElemSpace())
	{
		if (IsInArray(&data))
		{
			T tmpData = data;
			if (!SetElemSpace(GetElemSpace()+GetGrowSize()))
			{
				return false;
			}
			if (!SetElemCount(GetElemCount() + 1))
			{
				return false;
			}
			SetElem(GetElemCount() - 1, tmpData);

			return true;
		}

		else 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 TMCArray<T>::InsertElem(uint32 index, const T& data)
{
	MCAssert(IsValid());

	MCAssert(!IsInArray(&data));

	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> boolean TMCArray<T>::InsertElem(uint32 index, uint32 count, const T& data)
{
	MCAssert(IsValid());

	MCAssert(!IsInArray(&data));

	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 + count))
		{
			FillWithValue(data, index, count);
		}
		else
		{
			return false;
		}
	}
	else if(AddElemCount(count))
	{
		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 + count);
		
			MCAssertPointerCheck(BaseAddress());

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

		FillWithValue(data, index, count);
	
		return true;
	}

	return false;
}

template<class T> int32 TMCArray<T>::DichoSearch(const int32 begin,const int32 end, const T &item) const
{
	if (begin == end)
	{
		if ( (*this)[begin] == item)
			return begin;
		else
			return kUnusedIndex;
	}
	const int32 middle = begin + (end-begin)/2;

	if (item <= (*this)[middle])
		return DichoSearch(begin, middle, item);

	return DichoSearch(middle+1, end, item);
}

template<class T> int32 TMCArray<T>::DichoSearch(const T &item) const
{
	return DichoSearch(0,GetElemCount()-1,item);
}

//Find the index of the first instance of item if it exists in the array.
template<class T> uint32 TMCArray<T>::FindElem(const T& item) const
{
	uint32 result = kUnusedIndex;

	T* cur = fArrayData;

	if (fArrayData)
	{
		const uint32 elemCount = GetElemCount();

		for (uint32 i=0; i<elemCount; i++) 
		{
			if (cur[i] == item)
			{
				result = i;
				break;
			}
		}
	}
	return result;
}


// =================================================================================================================
// RemoveElem - Remove an element from the array.
// =================================================================================================================
template<class T> void TMCArray<T>::RemoveElem(MCSize index, MCSize 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;
		}


		MCSize memLoc		= GetElemSize() * index;
		MCSize srcMemLoc	= GetElemSize() * (index + count);
		MCSize copySize		= GetElemSize() * (GetElemCount() - index - count);

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

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

		SetElemCount(GetElemCount() - count);
	}
}

// =================================================================================================================
// Erase - Remove the elements of the array from startIterator to endIterator.
// =================================================================================================================
template<class T> void TMCArray<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.
// =================================================================================================================
template<class T> boolean TMCArray<T>::CopyElems(
	const TMCArray<T>&	fromArray,
	uint32				startIndex,
	uint32				nbItems,
	uint32				insertAtIndex) 
{
	uint32 countAboveInsertIndex=GetElemCount()-insertAtIndex;

	boolean	result = AddElemCount(nbItems);

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

			//Move the items after the ones we are copying. 
			if(countAboveInsertIndex>0)
			{
				T* src	= Pointer(insertAtIndex);
				T* dst	= Pointer(insertAtIndex + nbItems);

				MCmemmove(dst, src, countAboveInsertIndex * GetElemSize());
			}
			
			//Copy the data from fromArray into us.
			T* dst	= Pointer(insertAtIndex);
			MCmemcpy(dst, fromArray.Pointer(startIndex), nbItems * GetElemSize());
		}
	}
	return result;
}

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

// =================================================================================================================
// Append - Fill an array range with the value passed in.
// =================================================================================================================
template<class T> void TMCArray<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 TMCArray<T>::Swap(TMCArray<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>
void TMCArray<T>::ReorderArray(const TMCArray<int32>& reoderedIndex)
{
	const int32 count = reoderedIndex.GetElemCount();

	TMCArray<T> newArray;
	newArray.SetElemCount(count);

	for (int32 i=0; i<count; ++i)
	{
		newArray[i] = (*this)[reoderedIndex[i]];
	}

	Swap(newArray);
}


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

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

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


#define MC_DECLARE_ARRAY(_tableType, _tableName) typedef TMCArray<_tableType> _tableName

#endif // for entire file
