
//**************************************************************************/
// Copyright (c) 2008 Autodesk, Inc.
// All rights reserved.
//
// Use of this software is subject to the terms of the Autodesk license
// agreement provided at the time of installation or download, or which
// otherwise accompanies this software in either electronic or hard copy form.
//
//**************************************************************************/
// DESCRIPTION:
// CREATED: October 2008
//**************************************************************************/

namespace mudbox {

void MBDLL_DECL QuickSort( void *pBase, unsigned int  iNum, unsigned int  iSize, int ( * fComparator ) ( const void *, const void * ) );

/// \brief An internal helper class, representing a block of memory.  Use the Store class instead.
class MBDLL_DECL Block
{
protected:
	Block( const char *sName, unsigned int iItemSize )
    {                                                                     
    	m_sName = sName;
    	m_pNext = s_pHead;
    	m_pPrev = 0;
    	if ( m_pNext ) m_pNext->m_pPrev = this;
    	s_pHead = this;
    	m_iItemSize = iItemSize;
    };

	~Block( void );
	Block *m_pNext, *m_pPrev;
	unsigned int m_iItemSize;
	static Block *s_pHead;

public:
	inline static const Block *Head( void ) { return s_pHead; };
	inline const Block *Next( void ) const { return m_pNext; };
	inline unsigned int ItemSize( void ) const { return m_iItemSize; };

	const char *Name( void ) const;
	long long Size( void ) const;
	long long Address( void ) const;
	static void LogAll( float fSizeFilter = 0.01f, bool bSortByAddress = false );
	void Check( void ) const;
	static void CheckAll( void );
	static bool RegisterMemoryBlock( long long iSize );
	static bool UnregisterMemoryBlock( long long iSize );
	static void SetAllocatorID( const char *pAllocatorID );
	static void CopyMemoryBlock( void *pDestination, const void *pSource, long long iSize );

	const char *m_sName;
};

/// \brief An internal helper class, representing an array.  Use the Store class instead.
template < typename type >
class MBDLL_TEMPLATE_DECL Array : public Block
{
	friend class Block;
public:
	Array( const char *sName ) : Block( sName, sizeof(type) )
	{ 
		m_bData = true; 
		m_iSize = 0; 
		m_pArray = 0; 
		m_pThis = this;
	};
	Array( const char *sName, unsigned int iSize ) : Block( sName, sizeof(type) ) 
	{ 
		m_bData = true; 
		m_iSize = iSize;
		m_pArray = 0;
		try
		{
			if ( RegisterMemoryBlock( sizeof(type)*iSize ) )
			{
				SetAllocatorID( sName );
				m_pArray = new type[iSize];
				SetAllocatorID( 0 );
			}
			else
				throw &Error::s_cBadAlloc;
		}
		catch ( ... )
		{
			LogAll();
			throw &Error::s_cBadAlloc;
		};
		m_pThis = this;
	};
	Array( const char *sName, const type *pArray, int iSize ) : Block( sName, sizeof(type) )
	{ 
		m_bData = true; 
		m_pArray = 0;
		try
		{
			if ( RegisterMemoryBlock( sizeof(type)*iSize ) )
			{
				SetAllocatorID( sName );
				m_pArray = new type[iSize];
				SetAllocatorID( 0 );
			}
			else
				Error::ThrowBadAlloc();
		}
		catch ( ... )
		{
			// probably std::bad_alloc
			LogAll();
			throw &Error::s_cBadAlloc;
		};
		if( !m_pArray )
			return;

		memcpy( m_pArray, pArray, sizeof(type)*iSize ); 
		m_iSize = iSize; 
		m_pThis = this;
	};
	Array( const char *sName, bool bNoObjects ) : Block( sName, sizeof(type) )
	{ 
		m_bData = bNoObjects; 
		m_iSize = 0; 
		m_pArray = 0; 
		m_pThis = this;
	};
	Array( const char *sName, const Array<type> &a ) : Block( sName, sizeof(type) )
	{ 
		m_bData = true; 
		m_pArray = a.m_pArray; 
		m_iSize = a.m_iSize; 
		a.m_iSize = 0; 
		a.m_pArray = 0; 
		m_pThis = this;
	};
	void Clear( bool bDestruct = false ) 
	{ 
		bDestruct = bDestruct;

		if ( m_pArray ) 
		{	
			UnregisterMemoryBlock( (long long)(sizeof(type)*m_iSize) );
//			if ( bDestruct )
				delete [] m_pArray; 
//			else
//				delete m_pArray;
			m_pArray = 0; 
		}; 
		m_iSize = 0; 
	};
	inline Array<type> Clone( void ) const { Array<type> a; Copy( a ); return a; };
	inline bool Copy( Array<type> &a ) const 
	{ 
		if ( !a.Alloc( m_iSize ) )
			return false; 
		memcpy( a.m_pArray, m_pArray, sizeof(type)*a.m_iSize ); 
		return true;
	};
	inline void Set( unsigned int iStart, unsigned int iSize, unsigned char cPattern ) { MB_ASSERT( m_pThis == this ); MB_ASSERT( iStart+iSize <= m_iSize ); memset( m_pArray+iStart, int(cPattern), sizeof(type)*iSize ); };
	inline bool Extend( unsigned int iElementIndex )
	{
		if ( iElementIndex == 0xffffffff )
			return true;
		unsigned int iNewSize = m_iSize;
		while ( iElementIndex >= iNewSize )
			iNewSize = iNewSize*2+1;
		if( iNewSize > m_iSize )
			return Alloc( iNewSize );
		return true;
	};
	inline bool Alloc( unsigned int iNewSize )
	{
		if ( iNewSize == m_iSize )
			return true;
		MB_ASSERT( m_pThis == this ); 
		type *pNew = 0;
		try
		{
			if ( RegisterMemoryBlock( sizeof(type)*iNewSize ) )
			{
				SetAllocatorID( m_sName );
				pNew = new type[iNewSize];
				SetAllocatorID( 0 );
			}
			else
				throw &Error::s_cBadAlloc;		
		}
		catch ( Error * )
		{
			LogAll();
			return false;
		}
		catch ( ... )
		{
			// probably std::bad_alloc
			LogAll();
			throw &Error::s_cBadAlloc;
		};
		if( pNew == 0 )
			return false;
		if( m_iSize )
		{
			UnregisterMemoryBlock( sizeof(type)*m_iSize );
			if ( m_bData )			
				CopyMemoryBlock( pNew, m_pArray, Min( iNewSize, m_iSize )*sizeof(type) );
			else
				for ( unsigned int i = 0; i < Min( iNewSize, m_iSize ); i++ )
					pNew[i] = m_pArray[i];
			delete [] m_pArray;
		};
		m_pArray = pNew;
		m_iSize = iNewSize;
		return true;
	};

	inline type &operator []( int iIndex )
	{ 
		MB_ASSERT( m_pThis == this ); 
		MB_ONBUG( (unsigned int)(iIndex) >= m_iSize )
			return m_pArray[0];
		return m_pArray[iIndex]; 
	};
	inline type &operator []( unsigned int iIndex ) 
	{ 
		MB_ASSERT( m_pThis == this ); 
		MB_ONBUG( iIndex >= m_iSize ) 
			return m_pArray[0];
		return m_pArray[iIndex];
	};
	inline const type &operator []( unsigned int iIndex )  const
	{ 
		MB_ASSERT( m_pThis == this ); 
		MB_ONBUG( iIndex >= m_iSize )
			return m_pArray[0];
		return m_pArray[iIndex]; 
	};
	inline type *operator +( unsigned int iIndex ) { MB_ASSERT( m_pThis == this ); return &operator[]( iIndex ); };
	inline type *operator +( int iIndex ) { MB_ASSERT( m_pThis == this ); return &operator[]( iIndex ); };
	inline void operator =( const Array<type> &a ) { MB_ASSERT( m_pThis == this && a.m_pThis == &a ); Clear(); m_iSize = a.m_iSize; m_pArray = a.m_pArray; a.m_iSize = 0; a.m_pArray = 0; };

protected:

	mutable type *m_pArray;
	mutable unsigned int m_iSize;
	mutable bool m_bData;
	mutable const Array<type> *m_pThis;

public:
	~Array( void ) { MB_ASSERT( m_pThis == this ); Clear(); };
	virtual long long MemoryUsage( void ) const { return m_iSize*sizeof(type); };
};

/// \brief Simple array class.
/// 
/// This class represents a simple array and should be used in all circumstances instead of plain C-style arrays.
/// The class is templated, so that you can use to instantiate arrays of any type.
///
/// Its advantages of Store arrays include:
///
/// \li when the object is deleted, the associated data is deleted automatically. This means that if the Store instance
/// was created on the heap, or it is a member variable of another class, then you don't have to bother
/// freeing the memory, reducing the chance of a memory leak.
///
/// \li Additional functionality, such as expandability, sorting, and removing specified elements.
///
/// \li Easy to serialize.
///
/// \li The mudbox kernel can examine the list of all Store arrays in the memory at any time, which is helpful for 
/// diagnosing high memory footprint problems, as well as memory leaks.
/// 
/// Typical usage:
///
/// Typically, you create an empty Store instance, and then set the number of items (if you know it) by calling SetItemCount().
/// Alternatively, you can add elements into the array one by one, using the Add() function. 
/// If the elements of the array are class instances, their constructors and destructors can optionally be called when the array
/// space is allocated and deallocated. (You must call the right methods.)  For this reason, any class from which you will create an array should
/// have a constructor that takes no arguments.
///
/// When the array is extended
/// (for example when new elements are added by calling the Add() function), the existing array elements will be copied
/// to the new location with the "=" operator of the element class.  For this reason, you should ensure that this operator
/// will work correctly, especially in cases where your class contains pointers.  (If you have no "-" operator defined in the
/// data class, it will just do a direct memory copy.) 
///
/// A Store instance sometimes has more memory allocated than needed by the number of elements in the array.
/// See the Optimize() function for more details.
///
/// \b Note: If you use the "=" operator to copy one entire Store array to another, the original array is left empty.
/// (This is a speed optimization.)  If you want to do a deep copy of the contents of the Store array, you should
/// instead use the Clone() function as follows:
/// \code
/// Store<int> a;
/// a = b.Clone();
/// \endcode

template < typename type >
class MBDLL_TEMPLATE_DECL Store : public Array<type>
{
public:
	/// Creates an empty array.
	Store(
		const char *sName = "unknown"		///< [in] A name for the array (optional).  Displayed in the log only.
		) : Array<type>( sName ) { m_iSize = 0; };
		
	/// \brief Creates an array with space for some elements already allocated.
	///
	/// The content of the array is undefined.  (That is, constructors are not called.  To create an array where
	/// constructors and destructors are called automatically, use this call:
	///
	/// \code
	///    Store<myType> myInstance(false);
	/// \endcode
	Store(
		unsigned int iSize,		///< [in] The number of elements to allocate initially.
		const char *sName		///< [in] A name for the array (optional).  Displayed in the log only.
		) : Array<type>( sName, iSize ) { m_iSize = iSize; };
		
	/// \brief Creates an array and populates it will information copied from another array.
	///
	/// Note that the information from the source array is copied over using memcpy.  It is the caller's
	/// responsibility to check that the array being copied from contains enough values to copy before
	/// calling this constructor.
	Store(
		const type *pArray,				///< [in] The array from which to copy elements
		int iSize,						///< [in] The number of elements to copy over
		const char *sName = "unknown"	///< [in] A name for the array (optional).  Displayed in the log only.	
		) : Array<type>( sName, pArray, iSize ) { m_iSize = iSize; };
		
	/// Creates an empty array, allowing you to specify if elements have constructors or destructors that need to be called.
	Store(
		bool bNoObjects,	///< [in] if \b true, constructors and destructors will \b not be called on the array objects.
		const char *sName	///< [in] A name for the array (optional).  Displayed in the log only.
		) : Array<type>( sName, bNoObjects ) { m_iSize = 0; };
		
	/// Creates an array from another one. The other array becomes empty after the operation.
	Store(
		const Store &s	///< [in] The array whose contents will be transferred to this one
		) : Array<type>( s.m_sName, s ) { m_iSize = s.m_iSize; s.m_iSize = 0; };
		
	/// Destroys the contents of the array and deallocate its memory.
	~Store( void ) { Clear( !Array<type>::m_bData ); };

	/// Copies the contents of another array into this one, duplicating all data.  Returns \b true if successful.
	bool Copy(
		Store &s	///< [in] The array to be duplicated
		) const { s.m_iSize = m_iSize; return Array<type>::Copy( s ); };
	
	/// Returns a copy of this array. The returned copy will have a duplicate of all data in the original.
	Store Clone( void ) const { Store s; s.SetItemCount( m_iSize ); Copy( s ); return s; };
	
	/// Copies the contents of another array into this one, duplicating all data.
	void Clone(
		Store &s	///< [in] The array to be duplicated
		) const { s.SetItemCount( m_iSize ); Copy( s ); };

	/// Clears the array and deallocates its memory.
	inline void Clear(
		bool bDestruct = false	///< [in]  If \b true, the destructor will be called for each element.
		) { Array<type>::Clear( bDestruct ); m_iSize = 0; };
		
	/// \brief Sets the logical size of the array.  Returns \b true if successful.
	///
	/// If the new size is smaller than the current size, items at the end of the array will be discarded.
	/// If the new size is larger, then a new memory block will be allocated.  In this case, the existing items will
	/// only be copied to the new block only if bKeepContent is set to true.  
	inline bool SetItemCount(
		unsigned int iSize,			///< [in] The new size of the array
		bool bKeepContent = false	///< [in] if \b true, the original array contents will be preserved when the array size is increased.
		) 
	{ 
		if ( iSize <= m_iSize )
		{
			m_iSize = iSize;
			return true;
		};
		if ( !bKeepContent ) 
			Clear(); 
		if ( Array<type>::Alloc( iSize ) ) 
		{ 
			m_iSize = iSize; 
			return true; 
		};
		return false;
	};
	
	/// \brief Preallocates memory for the an array, without changing the array's logical size. Returns \b true if successful.
	///
	/// This method can be used to increase efficiency when an array is expected to grow by a large number of small
	/// steps.  For example, if you expect to add 50 items to an array one at a time, you can call Allocate() first to allocate
	/// the required space.  This will prevent the need for frequent reallocation.
	inline bool Allocate(
		unsigned int iSize,			///< [in] The new size for the array
		bool bKeepContent = false	///< [in] if \b true, the array contents will be preserved.  Otherwise they will be discarded.
		) { if ( !bKeepContent ) Clear(); return Array<type>::Alloc( iSize ); };
		
	/// \brief Extends the logical size of the array.  Returns \b true if successful.
	///
	/// If the specified size is not larger than the current array, nothing will happen.  Otherwise the logical
	/// size of the array will be extended to one more than the specified index.  New memory will be allocated as
	/// necessary to hold the new items.  Returns \b true if successful.
	inline bool Extend(
		unsigned int iIndex		///< [in] The array index to extend to.  For example, if you specify 7, the new array will contain 8 elements (indexed 0 to 7).
		)
	{ 
		if ( Array<type>::Extend( iIndex ) )
		{
			m_iSize = Max( m_iSize, iIndex+1 );
			return true;
		};
		return false;
	};
	
	/// \brief Extends the logical size of the array.   Returns \b true if successful.
	///
	/// If the specified size is not larger than the current array, nothing will happen.  Otherwise the logical
	/// size of the array will be extended to one more than the specified index.  New memory will be allocated as
	/// necessary to hold the new items.  Returns \b true if successful.
	inline bool Extend(
		int iIndex	///< [in] The array index to extend to.  For example, if you specify 7, the new array will contain 8 elements (indexed 0 to 7).
		) { return Extend( (unsigned int)iIndex ); };
		
	/// Removes the final items from the array.
	inline void RemoveTail(
		int iItemCount = 1		///< [in] The number if items to remove from the end of the array
		) { SetItemCount( ItemCount()-iItemCount ); };
		
	/// Fills the array with a specified element.
	inline void Fill(
		type cPattern		///< [in] The value to which every item in the array will be set
		) { for ( unsigned int i = 0; i < m_iSize; i++ ) operator[](i) = cPattern; };

	/// \brief Adds a new item to the array, increasing the array size by 1. The index of the added element is returned.
	///
	/// If you plan to add a number of objects using this method, you can improve efficiency by preallocating all the
	/// space you will need using the Allocate() method.
	inline unsigned int Add(
		const type &e	///< [in] The element to be added to the end of the array
		) { if( Array<type>::Extend( m_iSize ) ) { Array<type>::operator[]( m_iSize ) = e; return m_iSize++; } else return 0xffffffff; };
	
	/// \brief Adds a new item to the array, increasing the array size by 1. The index of the added element is returned.
	///
	/// If you plan to add a number of objects using this method, you can improve efficiency by preallocating all the
	/// space you will need using the Allocate() method.
	inline unsigned int Add(
		type &e	///< [in] The element to be added to the end of the array
		) { if( Array<type>::Extend( m_iSize ) ) { Array<type>::operator[]( m_iSize ) = e; return m_iSize++; } else return 0xffffffff; };

	/// \brief Transfers the contents of another array to this one, leaving the original array empty.
	///
	/// If you want to copy the contents of the source array (instead of transferring it), use the Copy() or Clone() functions.
	inline Store &operator =( const Store &s ) { m_iSize = s.m_iSize; s.m_iSize = 0; Array<type>::operator =( s ); return *this; };
	
	/// \brief Transfers the contents of another array to this one, leaving the original array empty.
	///
	/// If you want to copy the contents of the source array (instead of transferring it), use the Copy() or Clone() functions.
	void GetFrom(
		Store &s	///< [in] The array whose contents are to be transferred to this one
		) { m_iSize = s.m_iSize; Array<type>::operator =( s ); };
	
	/// Returns an indexed item from the array.
	const type &operator []( unsigned int iIndex ) const { return Array<type>::m_pArray[iIndex]; };
	
	/// Returns an indexed item from the array.
	type &operator []( unsigned int iIndex ) { MB_ASSERT( iIndex < m_iSize ); return Array<type>::m_pArray[iIndex]; };
	
	/// Returns an indexed item from the array.
	const type &operator []( int iIndex ) const { return operator[]( (unsigned int)iIndex ); };
	
	/// Returns an indexed item from the array.
	type &operator []( int iIndex ) { return operator[]( (unsigned int)iIndex ); };
	
	/// \brief Returns a pointer to an item in the array.  THIS FUNCTION IS UNSAFE.
	///
	/// This method allows you to access the address of an array element.  However, since many basic array operations
	/// can change the memory location of items in the array, this pointer should only be referenced immediately, and
	/// never kept around.
	inline type *operator +( unsigned int iIndex ) { return &operator[]( iIndex ); };
	
	/// \brief Returns a pointer to an item in the array.  THIS FUNCTION IS UNSAFE.
	///
	/// This method allows you to access the address of an array element.  However, since many basic array operations
	/// can change the memory location of items in the array, this pointer should only be referenced immediately, and
	/// never kept around.
	inline type *operator +( int iIndex ) { return &operator[]( iIndex ); };
	
	/// Returns \b true if the array has no items.
	inline bool IsEmpty( void ) const { return ItemCount() == 0; };
	
	/// Allows you to use the array as a boolean in \b if statements.  Evaluates to \b true if the array is not empty.
	inline operator bool( void ) const { return !IsEmpty(); };
	
	/// Evaluates to \b true if the array contains no items.
	inline bool operator !( void ) const { return IsEmpty(); };

	/// Makes a Store array from a regular C or C++ array.
	///
	/// This method takes a pointer to a block of memory that contains a C-style array of elements
	/// of the appropriate type, and makes that into a Mudbox array object.  Once this is called,
	/// the Store item will control the memory block, and extend or deallocate it as needed, as part
	/// of its own methods and destructor.
	///
	/// It is the responsibility of the caller to ensure that the source array is at least as big
	/// as the specified size.
	void SetBuffer( type *pData, unsigned int iSize = 0 ) { m_iSize = Array<type>::m_iSize = iSize; Array<type>::m_pArray = pData; };

	/// Serializes the the array and its contents from/to a stream.
	void Serialize(
		class Stream &s		///< [in] The stream from/to which to read/write the array
				   );

	/// \brief Sorts the items in the array.
	///
	/// This method will sort all the items in the array from least to greatest.  If the array is of
	/// a non-numeric or non-string type, this method determines the relative ordering of items using the
	/// subtraction ("-") operator.  In order to use this method, you must ensure that the subtraction operator
	/// is defined for the data type stored in this array, with these properties:
	///
	///   if A is less than B, then A-B must return a negative integer
	///
	///	  if A is greater than B, then A-B must return a positive integer
	///
	///   if A is equivalent to B, then A-B must return 0
	inline void Sort( void ) { QuickSort( Array<type>::m_pArray, m_iSize, sizeof(type), Compare ); };
	
	/// \brief Returns a pointer to the item in the array with a particular value. The array must be sorted before using this call.
	///
	/// This method uses a binary search to return a pointer to an element in the array with the specified value.  If the
	/// value is not found, then NULL is returned.
	/// Before this method can be called, the array must be sorted (by calling the Sort() method).
	///
	/// \b Note: The pointer returned by this function should not be kept for later use, as the contents of an array can
	/// move around in memory as items are added and removed.  It should only be used immediately.
	inline type *Find(
		type a		///< [in] The value to search for in the array
		) { return (type *) bsearch( &a, Array<type>::m_pArray, m_iSize, sizeof(type), Compare ); };
	
	/// \brief Returns a pointer to the item in the array with a particular value. The array must be sorted before using this call.
	///
	/// This method uses a binary search to return a pointer to an element in the array with the specified value.  If the
	/// value is not found, then NULL is returned.
	/// Before this method can be called, the array must be sorted (by calling the Sort() method).
	///
	/// \b Note: The pointer returned by this function should not be kept for later use, as the contents of an array can
	/// move around in memory as items are added and removed.  It should only be used immediately.
	inline type *Find( type *a ) { return (type *) bsearch( a, Array<type>::m_pArray, m_iSize, sizeof(type), Compare ); };
	
	/// Remove every occurrence of a specified item from the array. Returns the number of removed items.
	unsigned int Remove(
		const type &e	///< [in] the item to remove from the array
		)
	{
		unsigned int j = 0, i = 0;
		while ( i < ItemCount() )
		{
			if ( operator[]( i ) != e )
				operator[]( j++ ) = operator[]( i );
			i++;
		};
		SetItemCount( j );
		return i-j;
	};
	
	/// Removes the item at the specified index from the array.
	void Remove(
		unsigned int iIndex		///< [in] index of the item to be removed
		)
	{
		while ( iIndex+1 < ItemCount( ) )
		{
			operator[]( iIndex ) = operator[]( iIndex+1 );
			iIndex++;
		};
		SetItemCount( Min(iIndex,ItemCount()-1) );
	};
	
	/// \brief Removes duplicated items from the array after sorting it.
	///
	/// See the Sort() method for information on what makes an array Sort-able.
	/// This method sorts the contents of the array, then goes through and removes
	/// any duplicate entries, leaving a list of unique items.  It returns the number of
	/// items that were removed.
	unsigned int RemoveDuplicates( void )
	{
		if ( ItemCount() == 0 )
			return 0;
		Sort();
		unsigned int j = 0;
		for ( unsigned int i = 0; i < ItemCount()-1; i++ )
		{
			if ( operator[]( i ) != operator[]( i+1 ) )
				operator[]( j++ ) = operator[]( i );
		};
		operator[]( j++ ) = operator[]( ItemCount()-1 );
		unsigned iRemoved = ItemCount()-j;
		m_iSize = j;
		return iRemoved;
	};

	/// Returns the number of items in the array.
	inline unsigned int ItemCount( void ) const { return m_iSize; };
	
	/// Returns the last item in the array, or 0 if the array is empty.
	inline type &Last( void ) { if ( ItemCount() ) return operator []( ItemCount()-1 ); else throw new Error( "Store::LastItem called for an empty store" ); };

	/// \brief Reduces the allocated memory size to match the size of the current elements in the array.
	///
	/// Arrays derived from Store automatically grow their memory as needed to accommodate the items that
	/// are added to them.  For efficiency, when an array expands it allocates more memory than it immediately needs.
	/// This reduces the number of expensive memory allocations.
	///
	/// The Optimize methods allocates a new block of memory, precisely the size needed to hold the current contents
	/// of the array, then copies the array data to this new block before deleting the existing block.  Use it to
	/// minimize the memory footprint of arrays that are unlikely to expand, but that you need to keep around.
	inline void Optimize( void ) { Array<type>::Alloc( m_iSize ); };

protected:
	static int Compare( const void *a, const void *b ) { return (int)(*((type *)a)-*((type *)b)); };

public:
	mutable unsigned int m_iSize;
};

}; // end of namespace mudbox

