//---------------------------------------------------
//	Provides a simple typeless
//	dynamic array template class
//  Runs copy constructors when copying arrays about
//  Auto deletes & destructs elements when the array goes out of scope
//
// Created: JAT 15/03/06 from CoreEngine CoreArray.h file
//
//---------------------------------------------------

#ifdef ASURA_USE_PRAGMA_ONCE
	#pragma once
#endif

#ifndef __TOOLS_DYNAMICARRAY_H__
#define __TOOLS_DYNAMICARRAY_H__

// JGP - Required
#include "Debugging/Asura_Assert.h"

//---------------------------------------------------
//	Tools_DynamicArray class

template <class T>
class Tools_DynamicArray
{
public:

	// constructors
	inline Tools_DynamicArray( void );
	inline Tools_DynamicArray( const u_int uSize );
	inline Tools_DynamicArray( const Tools_DynamicArray<T>& xArray );
	
	// assignment operator
	inline Tools_DynamicArray<T>& operator = ( const Tools_DynamicArray<T>& xArray );

	// destructor
	inline ~Tools_DynamicArray( void );

	// get size
	inline const u_int GetSize( void ) const;

	// insert elements
	inline void Insert( const u_int uIndex, const u_int uItemCount );
	
	// remove elements
	inline void Remove( const u_int uIndex, const u_int uItemCount );
	
	// add an element
	inline void operator += ( const T& xItem );

	// add an array
	inline void operator += ( const Tools_DynamicArray<T>& xArray );

	// can fit
	inline const bool CanFit( const u_int uSize ) const;

	// reset the array
	inline void Reset();
	inline void Reset( const u_int uAllocSize );

	// resize the array

	inline void SetSize( const u_int uSize );
	// DLH - 04 April 2006 11:48:14 - Warning this only reserves more memory. It does NOT inrease the Size value so Get size will not change.
	inline void Resize( const u_int uSize );

	// cast to a T*
	inline operator const T*() const { return( m_pxContents ); }
	inline operator T*() { return( m_pxContents ); }

	inline const T* GetArray( void ) const { return m_pxContents; } 
	inline T* GetArray( void ) { return m_pxContents; } 

	// compare with other arrays
	inline const bool operator==( const Tools_DynamicArray<T>& xArray ) const;
	inline const bool operator!=( const Tools_DynamicArray<T>& xArray ) const;

	inline const T& operator[]( const u_int uIndex ) const;
	inline T& operator[]( const u_int uIndex );
	inline const T& operator[]( const int iIndex ) const;
	inline T& operator[]( const int iIndex );

	// Sort function: requires a < operator for the template type
	// Sort's 
	void Sort( void );
protected:

	T*	m_pxContents;
	u_int	m_uAllocSize;
	u_int	m_uArraySize;
	u_int   m_uStartAllocSize;

};

//---------------------------------------------------
// inlined functions
//---------------------------------------------------

// constructors
template <class T> inline Tools_DynamicArray<T>::Tools_DynamicArray( void )
{
	m_uAllocSize = 0;
	m_uArraySize = 0;
	m_uStartAllocSize = 0;
	m_pxContents = NULL;
}

template <class T> inline Tools_DynamicArray<T>::Tools_DynamicArray( const u_int uSize )
{
	m_uAllocSize = 0;
	m_uArraySize = 0;
	m_uStartAllocSize = uSize;
	m_pxContents = NULL;
	Reset();
}

template <class T> inline Tools_DynamicArray<T>::Tools_DynamicArray( const Tools_DynamicArray<T>& xArray )
{
	m_uAllocSize = 0;
	m_uArraySize = 0;
	m_uStartAllocSize = 0;
	m_pxContents = NULL;
	*this = xArray;
}

// assignment operator
template <class T> inline Tools_DynamicArray<T>& Tools_DynamicArray<T>::operator=(const Tools_DynamicArray<T>& xArray )
{
	m_uStartAllocSize = xArray.m_uStartAllocSize;
	Reset();
	Resize( xArray.m_uArraySize );
	const u_int uArraySize = xArray.GetSize();
	for ( u_int uIndex = 0; uIndex < uArraySize; uIndex++ )
	{
		const T& xSrc = xArray[uIndex];
		T& xDst = (*this)[uIndex];
		xDst = xSrc;
	}
	return *this;
}


// reset the array
template <class T> inline void Tools_DynamicArray<T>::Reset( void )
{
	Reset( m_uStartAllocSize );
}

template <class T> inline void Tools_DynamicArray<T>::Reset( const u_int uAllocSize )
{
 	if ( m_uAllocSize != uAllocSize )
	{
		if ( m_pxContents != NULL )  
		{
			delete[] m_pxContents;
		}

		m_uAllocSize = uAllocSize;
		
		if ( m_uAllocSize > 0 )
		{
			m_pxContents = new T[ m_uAllocSize ];
		}
		else
		{
			m_pxContents = NULL;
		}
	}
	m_uArraySize=0;
}


// destructor
template <class T> inline Tools_DynamicArray<T>::~Tools_DynamicArray()
{
 	if ( m_pxContents != NULL ) delete[] m_pxContents;
}


// get size
template <class T> inline const u_int Tools_DynamicArray<T>::GetSize( void ) const
{
	return m_uArraySize;
}


// insert blank array elements
template <class T> inline void Tools_DynamicArray<T>::Insert( const u_int uIndex, const u_int uItemCount )
{
	Asura_Assert( ( 0 < uItemCount ), "Tools_DynamicArray::Insert" );
	Asura_Assert( ( uIndex <= m_uArraySize ), "Tools_DynamicArray::Insert" );
	
	const u_int uNewArraySize = uItemCount + m_uArraySize;
	if( static_cast<u_int>( m_uAllocSize ) < uNewArraySize )
	{
		Resize( ( ( uNewArraySize * 3 + 1 ) / 2 ) );
	}
	
	{
		// DLH - Shift the existing items up to make room for the new ones
		u_int uCountShiftedItems = m_uArraySize - uIndex;
		for ( u_int uOffsetShiftedItem = 0; uOffsetShiftedItem < uCountShiftedItems; uOffsetShiftedItem++ )
		{
			m_pxContents[ uNewArraySize - 1 - uOffsetShiftedItem ] = m_pxContents[ m_uArraySize - 1 - uOffsetShiftedItem ];
		}
	}
	
	// DLH - Initialise the new items
	for ( u_int uOffsetNewItems = 0; uOffsetNewItems < uItemCount; uOffsetNewItems++ )
	{
		m_pxContents[ uIndex + uOffsetNewItems ] = T();
	}
	
	m_uArraySize = uNewArraySize;
}

// remove array elements
template <class T> inline void Tools_DynamicArray<T>::Remove( const u_int uIndex, const u_int uItemCount )
{
	Asura_Assert( ( 0 < uItemCount ), "Tools_DynamicArray::Remove" );
	Asura_Assert( ( ( uIndex + uItemCount ) <= m_uArraySize ), "Tools_DynamicArray::Remove" );
	
	const u_int uNewArraySize = m_uArraySize - uItemCount;
	
	// DLH - Shift the existing items down to make room for the new ones
	u_int uCountShiftedItems = uNewArraySize - uIndex;
	u_int uIndexShiftedItems = uIndex + uItemCount;
	for ( u_int uOffsetShiftedItem = 0; uOffsetShiftedItem < uCountShiftedItems; uOffsetShiftedItem++ )
	{
		m_pxContents[ uIndex + uOffsetShiftedItem ] = m_pxContents[ uIndexShiftedItems + uOffsetShiftedItem ];
	}
	
	m_uArraySize = uNewArraySize;
}

// add an element
template <class T> inline void Tools_DynamicArray<T>::operator += ( const T& xItem )
{
	if ( m_uAllocSize == m_uArraySize )
	{
		Resize( ( m_uAllocSize == 0 ) ? 1 : ( ( m_uAllocSize * 3 + 1 ) / 2 ) );
	}

	m_pxContents[m_uArraySize] = xItem;
	m_uArraySize++;
}


// add an array
template <class T> inline void Tools_DynamicArray<T>::operator += ( const Tools_DynamicArray<T>& xArray )
{
	for ( u_int uIndex = 0; uIndex < xArray.GetSize(); uIndex++ )
	{
		*this += xArray[ uIndex ];
	}
}

template <class T> inline const bool Tools_DynamicArray<T>::CanFit( const u_int uSize ) const
{
	return ( m_uArraySize + uSize <= m_uAllocSize );
}

// resize the array
template <class T> inline void Tools_DynamicArray<T>::SetSize( const u_int uSize )
{
	if ( m_uAllocSize < uSize )
	{
		Resize( uSize );
	}
	
	Asura_Assert( uSize <= m_uAllocSize, "Tools_DynamicArray::SetSize" );
	m_uArraySize = uSize;
}

template <class T> inline void Tools_DynamicArray<T>::Resize( const u_int uSize )
{
	T* pxNewContents;
	
	pxNewContents = new T[uSize];
	Asura_Assert( pxNewContents,  "Tools_DynamicArray::Resize" );

	if ( m_pxContents != NULL )
	{
		for ( u_int uIndex = 0; uIndex < ( ( uSize > m_uAllocSize ) ? m_uAllocSize : uSize ); uIndex++ )
		{
			pxNewContents[uIndex] = m_pxContents[uIndex];
		}
		delete[] m_pxContents;
	}

	m_pxContents = pxNewContents;
	m_uAllocSize = uSize;
}

// compare with other arrays
// Needs != operator on the templated type
template <class T> inline const bool Tools_DynamicArray<T>::operator == ( const Tools_DynamicArray<T>& xArray ) const
{
	if ( GetSize() != xArray.GetSize() )
	{
		return false;
	}
	for ( u_int uIndex = 0; uIndex < GetSize(); uIndex++ )
	{
		if ( m_pxContents[uIndex] != xArray[uIndex] )
		{
			return false;
		}
	}

	return true;
}

template <class T> inline const bool Tools_DynamicArray<T>::operator != ( const Tools_DynamicArray<T>& xArray ) const
{
	return !( (*this) == xArray );
}

template <class T> inline const T& Tools_DynamicArray<T>::operator[]( const u_int uIndex ) const 
{ 
	Asura_Assert( uIndex < static_cast<u_int>( m_uAllocSize ), "Tools_DyanmicArray::[]" );
	return m_pxContents[uIndex]; 
}

template <class T> inline T& Tools_DynamicArray<T>::operator[]( const u_int uIndex )  
{ 
	if ( uIndex >= static_cast<u_int>( m_uArraySize ) )
	{
		m_uArraySize = uIndex + 1;
	}
	while ( m_uAllocSize < m_uArraySize )
	{
		Resize( (m_uAllocSize == 0 ) ? 1 : m_uAllocSize * 2 );
	}
	return m_pxContents[uIndex]; 
}

template <class T> inline const T& Tools_DynamicArray<T>::operator[]( const int iIndex ) const 
{
	// Let the compiler do the work
	return operator[]( static_cast<u_int>( iIndex ) );

}

template <class T> inline T& Tools_DynamicArray<T>::operator[]( const int iIndex )  
{
	// Let the compiler do the work
	return operator[]( static_cast<u_int>( iIndex ) );
}

// JGP Static Internal Sort Routine
template<class T> static void SortArrayInternal( T* const m_pxData, const int iLo, const int iHi ) 
{
	//  lo is the lower index, hi is the upper index
	//  of the region of array a that is to be sorted
	int i = iLo;
	int j = iHi;
	T xTmp;
	T xMid = m_pxData[ ( iLo + iHi ) / 2 ];

	//  partition
	do
	{    
		while ( m_pxData[i] < xMid ) i++;
		while ( m_pxData[j] > xMid ) j--;
		if ( i <= j )
		{
			xTmp = m_pxData[i];
			m_pxData[i] = m_pxData[j];
			m_pxData[j] = xTmp;
			i++;
			j--;
		}
	} while ( i <= j );

	//  recursion
	if ( iLo < j ) SortArrayInternal<T>( m_pxData, iLo, j );
	if ( i < iHi) SortArrayInternal<T>( m_pxData, i, iHi ); 
}

// JGP Static templated sort function
template<class T> static void SortArray( T* const m_pxData, const int iArraySize )
{
	SortArrayInternal( m_pxData, 0, iArraySize - 1 );
}

// Public sort function
template<class T>
void Tools_DynamicArray<T>::Sort( void ) 
{
	return SortArray<T>( m_pxContents, m_uArraySize );
}

//---------------------------------------------------

#endif //  #ifndef __TOOLS_DYNAMICARRAY_H__

