
/*
  File: include/basic/Array.h
  Description: Data array template class
  Part of the Mantis project
  (c) 2002 Lycos Inc.

  This file is distributed for the sole purpose of allowing you to write
  software to interface with Sonique 2 and other Mantis programs. It is
  not to be modified or used for any other purpose without written
  authorization.

  If you redistribute this file, it must be in the original package
  complete with all other files provided, including the usage agreement.

  Do not remove this notice.
*/

#ifndef _ARRAY_H__
#define _ARRAY_H__

#ifdef DEBUG_INCLUDE_ORDER
#pragma message("Including " __FILE__ "\n" )
#endif

#if _MSC_VER > 1000
#pragma once
#endif


#include "typesport.h"
#include <stdlib.h>
#include <memory.h>
#include <stdarg.h>



#pragma warning (disable:4786)		//turn off annoying "identifier was truncated in browser information"
#pragma warning (disable:4042)		//turn off annoying "bad storage class" bogus warning

typedef enum { ArrayItem_NoConstruct, ArrayItem_Construct, ArrayItem_ZeroMemory } ArrayItemInitialization;

template<class TYPE, uint32 BLOCKSIZE = 10, ArrayItemInitialization bInitialization = ArrayItem_Construct> 
class Array  
{
protected:
	TYPE	*m_pItems;
	uint32	m_nCount;
	uint32	m_nAllocated;

	virtual void* Realloc(void* pMem, size_t size)
	{
		return realloc(pMem, size);
	}
	void	Init()
	{
		m_nCount = m_nAllocated = 0;
		m_pItems = NULL;
	}
public:
	Array() { Init(); };
	Array(int32 Number, ...)
	{
		Init();
		va_list args;
		va_start( args, Number );
		while( Number-- )
		{
			AddTail( va_arg( args, const TYPE ) );
		}
		va_end( args );
	}

	virtual ~Array()
	{
		if( m_nAllocated )
		{
			while( m_nCount-- )
				m_pItems[m_nCount].TYPE::~TYPE();
#if 0//def _WIN32
			VirtualFree( m_pItems, 0, MEM_RELEASE );
#else
			Realloc( m_pItems, 0 );
#endif
			m_pItems		= 0;
			m_nCount		= 0;
			m_nAllocated	= 0;
		}
	};
//	template <class OTHERTYPE>
	Array( const Array& Other)
	{
		uint32 i;

		Init();
		SetCount(Other.GetCount(), false);
		switch(bInitialization)
		{
		case ArrayItem_Construct:
			for (i = 0; i < m_nCount; i++)
				::new((void*)&m_pItems[i]) TYPE ( (const TYPE&)Other[i] );
			break;
		default:
			memcpy(m_pItems, Other.m_pItems, GetCount()*sizeof(*m_pItems));
			break;
		}
	}
//	template <class OTHERTYPE>
	Array& operator =(const Array& Other)
	{
		uint32 i;

		switch(bInitialization)
		{
		case ArrayItem_Construct:
			SetCount(0);
			break;
		}
		SetCount(Other.GetCount(), false);

		switch(bInitialization)
		{
		case ArrayItem_Construct:
			for (i = 0; i < m_nCount; i++)
				::new((void*)&m_pItems[i]) TYPE ( (const TYPE&)Other[i] );
			break;
		default:
			memcpy(m_pItems, Other.m_pItems, GetCount()*sizeof(*m_pItems));
			break;
		}

		return *this;
	}

	__forceinline TYPE* GetAt( )					const{ return m_pItems; };
	__forceinline TYPE& GetAt( uint32 index )		const{ ASSERT( index < m_nCount ); return m_pItems[index]; };
	__forceinline TYPE& operator[]( uint32 index )	const{ return GetAt(index); };

	uint32 SetCount( int32 nSize, bool bPerformClassManagment = true ) // returns previous count
	{
		if( nSize < 0 )
			nSize = 0;

		uint32 nOldSize = m_nCount;

		if( nSize != (int32)m_nCount )
		{
			// remove any that might get lost
			if ( bPerformClassManagment && nSize < (int32)m_nCount )
			{
				switch(bInitialization)
				{
				case ArrayItem_Construct:
					for( uint32 i = nSize; i< m_nCount; i++ )
						m_pItems[i].TYPE::~TYPE();
					break;
				}
			}

#if 0 //def _WIN32
			TYPE *temp = (TYPE*) VirtualAlloc ( m_pItems, (nSize)*sizeof(TYPE), MEM_COMMIT, PAGE_EXECUTE_READWRITE );
#else
			TYPE *temp = (TYPE*) Realloc( m_pItems, (nSize)*sizeof(TYPE) );
#endif
			ASSERT( NULL != temp || !nSize );
			m_pItems = temp;

			if ( bPerformClassManagment && nSize > (int32)m_nCount )
			{
				int32 i;
				switch(bInitialization)
				{
				case ArrayItem_Construct:
					for( i = (int32)m_nCount; i< nSize; i++ )
						::new( (void*) &m_pItems[i] ) TYPE();
					break;
				case ArrayItem_ZeroMemory:
					memset( m_pItems+m_nCount, 0, (nSize-m_nCount)*sizeof(TYPE) );
					break;
				}
			}
			

			m_nAllocated = nSize;
			m_nCount	 = nSize; 
		}

		return nOldSize;
	}
	bool Grow()
	{

#if 0 // def _WIN32
		TYPE *temp = (TYPE*) VirtualAlloc ( m_pItems, (m_nAllocated + BLOCKSIZE)*sizeof(TYPE), MEM_COMMIT, PAGE_EXECUTE_READWRITE );
#else
		TYPE *temp = (TYPE*) Realloc( m_pItems, (m_nAllocated + BLOCKSIZE)*sizeof(TYPE) );
#endif

		ASSERT( NULL != temp);
		m_pItems = temp;
		
		m_nAllocated += BLOCKSIZE;
		return true;
	};
	
	void RemoveTail()
	{
		ASSERT( 0 != m_nCount );
		
		m_nCount--;
		switch(bInitialization)
		{
		case ArrayItem_Construct:
			m_pItems[m_nCount].TYPE::~TYPE();
			break;
		}
		
	};
		
	TYPE& Head() const
	{
		ASSERT( 0 != m_nCount );
		return m_pItems[0];
	};
	TYPE& Tail() const
	{
		ASSERT( 0 != m_nCount );
		return m_pItems[m_nCount-1];
	};

	
	__inline uint32 GetCount() const
	{
		return m_nCount;
	};

	template <class SearchClass>
	int32 Find( const SearchClass& item, uint32 nStartFrom = 0 ) const
	{
		for( ; nStartFrom < (uint32)m_nCount; nStartFrom++ )
		{
			if( m_pItems[nStartFrom] == item )
				return nStartFrom;
		}
		
		return -1;
	};

	TYPE& InsertBefore( uint32 index )
	{
		ASSERT( index <= m_nCount );
		if( m_nCount == m_nAllocated )
			if( !Grow() )
			{
				ASSERT(0);
				return *(TYPE*)NULL;
			}

		if( index < m_nCount )
			memmove( &m_pItems[index+1], &m_pItems[index], sizeof(TYPE) * (m_nCount - index) );

		switch(bInitialization)
		{
		case ArrayItem_Construct:
			::new( (void*) &m_pItems[index] ) TYPE();
			break;
		}
		m_nCount++;
		return m_pItems[index];
	};
	TYPE& InsertBefore( uint32 index, const TYPE& item )
	{
		ASSERT( index <= m_nCount );
		if( m_nCount == m_nAllocated )
			if( !Grow() )
			{
				ASSERT(0);
				return *(TYPE*)NULL;
			}

		if( index < m_nCount )
			memmove( &m_pItems[index+1], &m_pItems[index], sizeof(TYPE) * (m_nCount - index) );

		switch(bInitialization)
		{
		case ArrayItem_Construct:
			::new( (void*) &m_pItems[index] ) TYPE( (const TYPE&)item);
			break;
		default:
			m_pItems[index] = item;
			break;
		}
		m_nCount++;
		return m_pItems[index];
	};
	TYPE* InsertBefore( uint32 index, Array<TYPE>& Other )
	{
		return InsertBefore(index, &Other[0], Other.GetCount());
	}
	TYPE* InsertBefore( uint32 index, const TYPE* items, uint32 count )
	{
		//ASSERT(0); // this code looks bad.. never modifies the count!
		ASSERT( index <= m_nCount );
		uint32 m_nOldCount = m_nCount;
		SetCount(m_nCount+count,false);

		if( index < m_nOldCount )
			memmove( &m_pItems[index+count], &m_pItems[index], sizeof(TYPE) * (m_nOldCount - index) );

		switch(bInitialization)
		{
		case ArrayItem_Construct:
			{
				uint32 i;
				if( items )
				{
					for( i = 0; i < count; i++ )
						::new( (void*) &m_pItems[index+i] ) TYPE( (const TYPE&)items[i]);
				} else {
					for( i = 0; i < count; i++ )
						::new( (void*) &m_pItems[index+i] ) TYPE( );
				}
			}
			break;
		default:
			if( items )
				memcpy(&m_pItems[index], items, count*sizeof(TYPE));
			else
				memset(&m_pItems[index], 0, count*sizeof(TYPE));
			break;
		}
		return &m_pItems[index];
	};
	
	TYPE& InsertAfter(uint32 index )
	{
		return InsertBefore( index+1 );
	};
	TYPE& InsertAfter(uint32 index, const TYPE& item )
	{
		return InsertBefore( index+1 , item );
	};
	TYPE* InsertAfter( uint32 index, Array<TYPE>& Other )
	{
		return InsertAfter(index, &Other[0], Other.GetCount());
	}
	TYPE* InsertAfter(uint32 index, const TYPE* items, uint32 count )
	{
		return InsertBefore( index+1, items, count );
	};

	__forceinline void RemoveBlock( uint32 start, uint32 end )
	{
		switch(bInitialization)
		{
		case ArrayItem_Construct:
			for( uint32 i=start;i<=end;i++ )
				m_pItems[i].TYPE::~TYPE();
			break;
		}

		memmove( &m_pItems[start], &m_pItems[end+1], sizeof(TYPE) * (m_nCount - (end + 1) ) );
		m_nCount -= (end-start+1);
	};

	__forceinline void RemoveAt( uint32 index, uint32 count = 1 )
	{
		ASSERT(index+count<=m_nCount);
		RemoveBlock( index, index+count-1 );
	};

    //safe to call even if it's not in the array.
	__forceinline void Remove( const TYPE& pItem )
	{
		int32 index = Find(pItem);
		if(index >= 0 && index < (int32)m_nCount)
			RemoveAt(index);
    }

	__forceinline void Remove( const TYPE* pItem )
	{
		int32 index = GetIndex(pItem);
		if(index >= 0 && index < (int32)m_nCount)
			RemoveAt(index);
		else
			ASSERT(0);
	};

	void RemoveAll()
	{
		if( m_nCount )
			RemoveBlock( 0, m_nCount-1 );
	};


	__forceinline TYPE& AddTail( const TYPE& item )
	{ 
		if( m_nCount == m_nAllocated )
			if( !Grow() )
			{
				ASSERT(0);
				return *(TYPE*)NULL;
			}

		// construct
		switch(bInitialization)
		{
		case ArrayItem_Construct:
			::new( (void*) &m_pItems[m_nCount] ) TYPE( (const TYPE&)item);
			break;
		default:
			m_pItems[m_nCount] = item;
			break;
		}
		m_nCount++;
		return m_pItems[m_nCount-1];
	};
	__forceinline void AddTail( const TYPE* items, uint32 nCount )
	{ 
		uint32 i, nIndex;

		nIndex = m_nCount;
		SetCount( m_nCount+nCount, false );

		switch(bInitialization)
		{
		case ArrayItem_Construct:
			for (i = 0; i < nCount; i++)
				::new((void*)&m_pItems[i+nIndex]) TYPE ( (const TYPE&)items[i] );
			break;
		default:
			memcpy(m_pItems+nIndex, items, nCount*sizeof(*m_pItems));
			break;
		}
		
	};
	__forceinline void AddTail( const Array<TYPE>& Other )
	{
		if( Other.GetCount() )
			AddTail(&Other[0], Other.GetCount());
	}

	TYPE& AddTail()
	{
		if( m_nCount == m_nAllocated )
			if( !Grow() )
			{
				ASSERT(0);
				return *(TYPE*)NULL;
			}

		// construct
		switch(bInitialization)
		{
		case ArrayItem_Construct:
			::new( (void*) &m_pItems[m_nCount] ) TYPE();
			break;
		}
		m_nCount++;

		return m_pItems[m_nCount-1];
	};


	TYPE& AddTail( const TYPE *pitem )
	{ 
		return AddTail( *pitem );
	};

	TYPE& AddHead( const TYPE& item )
	{
		return InsertBefore( 0, item );
	};

	TYPE& AddHead( )
	{
		return InsertBefore( 0 );
	};

	bool MoveBlock( uint32 start, uint32 nCount, uint32 dest )
	{
		ASSERT( start < m_nCount /*&& start >= 0*/ );
		ASSERT( dest  < m_nCount /*&& dest  >= 0*/ );
		ASSERT( start+nCount <= m_nCount );
		ASSERT( dest		 <= m_nCount );

		char* pTemp;
	
		if (dest > start+nCount || dest+nCount < start)
		{
			//Take a copy of the source, move the inbetween data across, and put it at the destination
			pTemp = new char[ sizeof(TYPE) * nCount ];

			memmove( pTemp, &m_pItems[start], nCount * sizeof( TYPE ));
/// DO STUFF
		  
			if (dest > start)
				memmove( &m_pItems[start], &m_pItems[start+nCount], sizeof(TYPE) *( dest - start ) );
			else
				memmove( &m_pItems[ dest + nCount ], &m_pItems[ dest ], sizeof(TYPE) * ( start-dest ) );

			memmove( &m_pItems[ dest ], pTemp, sizeof(TYPE) * nCount );
		} 
		else 
		{
			//Blocks overlap..
			//Grab the little difference block, move the main one then put the difference back on the other side
			uint32 DifferenceSize = abs((int32)(dest-start));

			pTemp = new char[ sizeof(TYPE) * DifferenceSize ];

			memmove( pTemp, &m_pItems[((dest > start)?(start+nCount):(dest))], DifferenceSize * sizeof(TYPE) );
			memmove( &m_pItems[ dest ], &m_pItems[ start ], sizeof(TYPE) * nCount );
			memmove( &m_pItems[ ((dest > start)?(start):(dest+nCount)) ], pTemp, DifferenceSize * sizeof(TYPE) );
		}
		
		delete pTemp;

		return true;
	};

	__forceinline int GetIndex( const TYPE* item ) const
	{
		int Index = item - m_pItems;
		ASSERT( Index >= 0 && Index < (int)m_nCount && ((char*)item) == ((char*)m_pItems)+Index*sizeof(TYPE) );
		return Index;
	}

	__forceinline bool InRange( uint32 Index ) const
	{
		return Index < GetCount();
	}

	static int __cdecl CompareItemsForward(const void* a, const void* b)
	{
        return *((TYPE*)a) - *((TYPE*)b);
	}
	static int __cdecl CompareItemsReverse(const void* a, const void* b)
	{
        return *((TYPE*)b) - *((TYPE*)a);
	}
};

template<class TYPE, uint32 BLOCKSIZE, ArrayItemInitialization bInitialization>
void SortArray(Array<TYPE,BLOCKSIZE,bInitialization>& Dest, bool bReverseSort)
{
	if (Dest.GetCount() > 0)
    {
        if( !bReverseSort )
    		qsort(&Dest[0], Dest.GetCount(), sizeof(TYPE), &Array<TYPE,BLOCKSIZE,bInitialization>::CompareItemsForward);
        else
    		qsort(&Dest[0], Dest.GetCount(), sizeof(TYPE), &Array<TYPE,BLOCKSIZE,bInitialization>::CompareItemsReverse);
    }
}

#ifdef DEBUG_INCLUDE_ORDER
#pragma message("Done including " __FILE__ "\n" )
#endif

#endif 
