www.pudn.com > GameEngine_src.rar > CDynamicArray.h

#ifndef CDynamicArray_h 
#define CDynamicArray_h 
 
 
#include  
#include  
#include  
#include  
 
//---------------------------------------------------------------------------- 
//动态数组模板类,二维动态数组模板类 
//卢杭威宇创建 
//最后修改:2007/10/7 
//----------------------------------------------------------------------------- 
 
//const int ADD = 16;				//每次重分配数组时增加的长度 
 
////////////////////////////////////////////////////////////// 
//动态数组类模板 
////////////////////////////////////////////////////////////// 
template < class T > 
class CDynamicArray   
{ 
public: 
	CDynamicArray(); 
	~CDynamicArray(); 
	CDynamicArray( int isize ); 
	CDynamicArray( CDynamicArray &array ); 
 
	T &operator[]( int index ); 
 
	CDynamicArray &operator = ( CDynamicArray &array ); 
 
	int  GetSize() { return m_iSize; }; 
	T *  GetPointer() { return m_array; } 
	bool IsEmpty() { return m_iSize <= 0; } 
 
	bool Init( int iSize );							//初始化存储空间 
	void Free();									//释放数组空间 
	void Clear();									//清空数组,全部析构 
	//bool CreateNullElement( int iNum );				//创建一定数量的空元素 
 
	T *  CreateOneElement(); 
	void DeleteLastElement(); 
 
	bool Add( const T &t );							//加入一个元素 
	void Delete( int index );						//删除一个元素 
 
	void Remove( const T &t )						 
	{ int i = Find( t ); if ( i != -1 ) Delete(i); } 
 
	bool Insert( int index, const T &t );			//在指定位置插入一个元素 
 
	bool IsContain( const T &t )					//判断数组中是否包含某元素 
	{ return Find( t ) != -1; } 
 
	int	 Find( const T &t, int iStart, int iNum );	//在一个范围内查找元素 
	int  Find( const T &t ); 
 
	int  GetLength() { return m_iSize; } 
	bool SetSize( int iSize ); 
 
private: 
	bool IsFull( int isize ); 
	bool SetMaxSize( int iNewMaxSize ); 
 
private: 
	T * m_array;				//数组指针 
	int m_iSize;				//当前元素数量 
	int m_iMaxSize;				//当前分配的空间大小 
}; 
 
template  
CDynamicArray::CDynamicArray() 
{ 
	m_iSize = 0; 
	m_iMaxSize = 0; 
	m_array = NULL; 
} 
 
template  
CDynamicArray::~CDynamicArray() 
{ 
	Free(); 
} 
 
//////////////////////////////////////////////////////////////// 
//构造函数,分配一定大小空间 
/////////////////////////////////////////////////////////////// 
template  
CDynamicArray::CDynamicArray( int isize ) 
{ 
	m_iSize = 0; 
	m_iMaxSize = 0; 
	m_array = NULL; 
	Init( isize ); 
} 
 
//////////////////////////////////////////////////////////////// 
// 
/////////////////////////////////////////////////////////////// 
template  
CDynamicArray::CDynamicArray( CDynamicArray &array ) 
{ 
	SetMaxSize( array.m_iMaxSize ); 
	for ( int i = 0; i < array.m_iSize; ++i ) 
		Add( array.m_array[i] ); 
} 
 
//////////////////////////////////////////////////////////////// 
// 
/////////////////////////////////////////////////////////////// 
template  
CDynamicArray &CDynamicArray::operator = ( CDynamicArray &array ) 
{ 
	if ( this != &array ) 
	{ 
		Clear(); 
	 
		for ( int i = 0; i < array.m_iSize; ++i ) 
			Add( array.m_array[i] ); 
	} 
	return *this; 
} 
 
/////////////////////////////////////////////////////////// 
//判断数组是否满 
////////////////////////////////////////////////////////// 
template  
bool CDynamicArray::IsFull( int isize ) 
{ 
	return isize >= m_iMaxSize; 
} 
 
//////////////////////////////////////////////////////////// 
//改变数组的容量 
//////////////////////////////////////////////////////////// 
template  
bool CDynamicArray::SetMaxSize( int iNewMaxSize ) 
{ 
	if ( m_iMaxSize == 0 )								//数组尚未分配内存 
	{ 
		return Init( iNewMaxSize ); 
	} 
	else if ( iNewMaxSize > m_iMaxSize )				//增大数组空间 
	{ 
		//if ( iNewMaxSize - m_iMaxSize < 4 ) iNewMaxSize = m_iMaxSize + 8; 
		T * newArray = (T *) realloc( m_array, iNewMaxSize * sizeof(T) ); 
		if ( newArray == NULL ) 
		{ 
			assert(false); 
			return false; 
		} 
 
		//for ( int i = m_iMaxSize; i < iNewMaxSize; ++i ) 
			//::new (&newArray[i]) T;						//调用默认构造函数 
 
		m_array = newArray; 
		m_iMaxSize = iNewMaxSize; 
	} 
	else if ( iNewMaxSize > 0 && iNewMaxSize < m_iMaxSize )	//减小数组空间，部分元素析构 
	{ 
		for ( int i = iNewMaxSize; i < m_iSize; ++i ) 
			m_array[i].~T();							//析构 
 
		if ( iNewMaxSize < m_iSize ) 
			m_iSize = iNewMaxSize; 
	} 
	else if ( iNewMaxSize == 0 ) 
	{ 
		Free(); 
	} 
	//else iNewMaxSize小于零，或等于m_iSize，或等于m_iMaxSize 
 
	return true; 
} 
 
//////////////////////////////////////////////////////////// 
//初始化 
//////////////////////////////////////////////////////////// 
template  
bool CDynamicArray::Init( int iSize ) 
{ 
	if ( m_array != NULL ) 
		return false; 
 
	if ( iSize < 1 )	 
		iSize = 1; 
	 
	m_iMaxSize = iSize; 
	m_array = (T *)malloc( m_iMaxSize * sizeof(T) ); 
 
	if ( m_array == NULL ) 
	{ 
		assert(false); 
		return false; 
	} 
 
	//for ( int i = 0; i < m_iMaxSize; ++i ) 
		//::new ( &m_array[i] ) T; 
 
	return true; 
} 
 
//////////////////////////////////////////////////////////// 
//释放数组 
//////////////////////////////////////////////////////////// 
template  
void CDynamicArray::Free() 
{ 
	if ( m_array != NULL ) 
	{ 
		for ( int i = 0; i < m_iSize; ++i ) 
			m_array[i].~T(); 
	 
		free( m_array ); 
		m_array = NULL; 
		m_iMaxSize = 0; 
		m_iSize = 0; 
	} 
} 
 
//////////////////////////////////////////////////////////// 
//清空数组，所有元素析构 
//////////////////////////////////////////////////////////// 
template  
void CDynamicArray::Clear() 
{ 
	for ( int i = 0; i < m_iSize; ++i ) 
		m_array[i].~T(); 
	 
	m_iSize = 0; 
} 
 
//////////////////////////////////////////////////////////// 
//生成空元素,在原有元素的基础上 
//////////////////////////////////////////////////////////// 
template  
bool CDynamicArray::SetSize( int size ) 
{ 
//#ifdef _DEBUG 
	//assert( size > 0 ); 
//#endif 
 
	if ( size > m_iSize ) 
	{ 
		if ( SetMaxSize( size ) == false ) 
			return false; 
 
		for ( int i = m_iSize; i < size; ++i ) 
			::new (&m_array[i]) T; 
	} 
	else 
	{ 
		for ( int i = size; i < m_iSize; ++i ) 
			m_array[i].~T(); 
	} 
 
	m_iSize = size; 
	return true; 
} 
 
//////////////////////////////////////////////////////////// 
//在数组中增加一个元素 
//////////////////////////////////////////////////////////// 
template  
T *CDynamicArray::CreateOneElement() 
{ 
	if ( IsFull( m_iSize + 1 ) ) 
	{ 
		if ( SetMaxSize( m_iSize + 1 ) == false ) 
		{ 
			//assert(false); 
			return NULL; 
		} 
	} 
 
	::new (&m_array[m_iSize]) T; 
	++m_iSize; 
	return &m_array[m_iSize - 1];	 
} 
 
////////////////////////////////////////////////////////////// 
//删除数组中最后一个元素 
////////////////////////////////////////////////////////////// 
template  
void CDynamicArray::DeleteLastElement() 
{ 
	if ( m_iSize > 0 ) 
	{ 
		m_array[m_iSize - 1].~T(); 
		--m_iSize; 
	} 
} 
 
 
//////////////////////////////////////////////////////////// 
//重载数组[]操作符 
//////////////////////////////////////////////////////////// 
template  
T &CDynamicArray::operator[] ( int index ) 
{ 
#ifdef _DEBUG 
	assert( index >= 0 && index < m_iMaxSize ); 
#endif 
 
	return m_array[index]; 
} 
 
////////////////////////////////////////////////////////////// 
//将新元素加入数组 
////////////////////////////////////////////////////////////// 
template  
bool CDynamicArray::Add( const T &t ) 
{ 
	if ( IsFull( m_iSize + 1 ) ) 
	{ 
		if ( SetMaxSize( m_iSize + 1 ) == false ) 
			return false; 
	} 
 
	::new ( &m_array[m_iSize] ) T( t ); 
 
	m_iSize++; 
 
	return true; 
} 
 
//////////////////////////////////////////////////////////// 
//删除一个元素 
//////////////////////////////////////////////////////////// 
template  
void CDynamicArray::Delete( int index ) 
{ 
#ifdef _DEBUG 
	assert( index >= 0 && index <= m_iSize ); 
#endif 
 
	m_array[index].~T(); 
	memmove( &m_array[index], &m_array[index+1], ( m_iSize - index - 1 ) * sizeof(T) ); 
	--m_iSize; 
} 
 
//////////////////////////////////////////////////////////// 
//在某个位置插入一个元素 
//////////////////////////////////////////////////////////// 
template  
bool CDynamicArray::Insert( int index, const T &t ) 
{ 
#ifdef _DEBUG 
	assert( index >= 0 && index <= m_iSize ); 
#endif 
 
	if ( index == m_iSize ) 
		Add( t ); 
	else 
	{ 
		if ( IsFull( m_iSize + 1 ) ) 
		{ 
			if ( SetMaxSize( m_iSize + ADD ) == false ) 
				return false; 
		} 
		 
		memmove( &m_array[index+1], &m_array[index], (m_iSize - index) * sizeof(T) ); 
		::new (&m_array[index]) T( t ); 
		++m_iSize; 
	} 
 
	return true; 
} 
 
//////////////////////////////////////////////////////////// 
//查找某个元素的索引 
//////////////////////////////////////////////////////////// 
template  
int CDynamicArray::Find( const T &t, int iStart, int iNum ) 
{ 
#ifdef _DEBUG 
	assert( iStart >= 0 && iStart < m_iSize ); 
	assert( iNum > 0 && iNum <= m_iSize ); 
#endif 
 
	for ( int i = iStart; i < iStart + iNum; ++i ) 
	{ 
		if ( m_array[i] == t ) 
			return i; 
	} 
 
	return -1; 
} 
 
//////////////////////////////////////////////////////////// 
//查找某个元素的索引 
//////////////////////////////////////////////////////////// 
template  
int CDynamicArray::Find( const T &t ) 
{ 
	for ( int i = 0; i < m_iSize; ++i ) 
	{ 
		if ( m_array[i] == t ) 
			return i; 
	} 
 
	return -1; 
} 
 
 
//--------------------------------------------------二维数组类模板--------------------------------------------- 
//////////////////////////////////////////////////////////////// 
//二维数组类模板，基于CDynamicArray 
//row表示二维数组共有几行 
//col表示二维数组一行中有几个元素 
//////////////////////////////////////////////////////////////// 
template  
class CDoubleArray 
{ 
public: 
	CDoubleArray(); 
	CDoubleArray( int row, int col ); 
	CDoubleArray( CDoubleArray &array ); 
	~CDoubleArray(); 
	CDoubleArray &operator = ( CDoubleArray &array ); 
 
	bool Init( int row, int col ) { return SetSize( row, col ); } 
	void Free(); 
	 
	bool SetSize( int row, int col ); 
	bool ResetSize( int row, int col ); 
 
	int GetRow() { return m_iRow; } 
	int GetColumn() { return m_iColumn; } 
 
	CDynamicArray &operator [] ( int row ); 
	TYPE &operator () ( int row, int col ); 
private: 
	CDynamicArray< CDynamicArray > m_DoubleArray; 
	int m_iRow; 
	int m_iColumn; 
}; 
 
////////////////////////////////////////////////////////////////// 
// 
////////////////////////////////////////////////////////////////// 
template  
CDoubleArray::CDoubleArray() 
{ 
	m_iRow = 0; 
	m_iColumn = 0; 
} 
 
////////////////////////////////////////////////////////////////// 
// 
////////////////////////////////////////////////////////////////// 
template  
CDoubleArray::CDoubleArray( int row, int col ) 
{ 
	m_iRow = 0; 
	m_iColumn = 0; 
	Init( row, col ); 
} 
 
////////////////////////////////////////////////////////////////// 
// 
////////////////////////////////////////////////////////////////// 
template  
CDoubleArray::CDoubleArray( CDoubleArray &array ) 
{ 
	m_DoubleArray	= array.m_DoubleArray; 
	m_iRow			= array.m_iRow; 
	m_iColumn		= array.m_iColumn; 
} 
 
////////////////////////////////////////////////////////////////// 
// 
////////////////////////////////////////////////////////////////// 
template  
CDoubleArray::~CDoubleArray() 
{ 
	Free(); 
	m_iRow = 0; 
	m_iColumn = 0; 
} 
 
////////////////////////////////////////////////////////////////// 
// 
////////////////////////////////////////////////////////////////// 
template  
CDoubleArray &CDoubleArray::operator = ( CDoubleArray &array ) 
{ 
	if ( this != &array ) 
	{ 
		m_DoubleArray	= array.m_DoubleArray; 
		m_iRow			= array.m_iRow; 
		m_iColumn		= array.m_iColumn; 
	} 
 
	return *this; 
} 
 
////////////////////////////////////////////////////////////////// 
// 
////////////////////////////////////////////////////////////////// 
template  
void CDoubleArray::Free() 
{ 
	m_DoubleArray.Free(); 
	m_iRow = 0; 
	m_iColumn = 0; 
} 
 
////////////////////////////////////////////////////////////////// 
//设置数组的大小 
////////////////////////////////////////////////////////////////// 
template  
bool CDoubleArray::SetSize( int row, int col ) 
{ 
#ifdef _DEBUG 
	assert( row > 0 && col > 0 ); 
#endif 
 
	bool re = true; 
	re &= m_DoubleArray.SetSize( row ); 
 
	if ( re ) 
		m_iRow = row; 
 
	for ( int i = 0; i < m_iRow; ++i ) 
		re &= m_DoubleArray[i].SetSize( col ); 
 
	if ( re ) 
		m_iColumn = col; 
 
 
	return re; 
} 
 
////////////////////////////////////////////////////////////////// 
// 
////////////////////////////////////////////////////////////////// 
template  
bool CDoubleArray::ResetSize( int row, int col ) 
{ 
	Free(); 
	return SetSize( row, col ); 
} 
 
////////////////////////////////////////////////////////////////// 
// 
////////////////////////////////////////////////////////////////// 
template  
TYPE &CDoubleArray::operator () ( int row, int col ) 
{ 
#ifdef _DEBUG 
	assert( row >= 0 && row < m_iRow ); 
	assert( col >= 0 && col < m_iColumn ); 
#endif 
 
	return m_DoubleArray[row][col];	 
} 
 
////////////////////////////////////////////////////////////////// 
// 
////////////////////////////////////////////////////////////////// 
template  
CDynamicArray &CDoubleArray::operator [] ( int row ) 
{ 
#ifdef _DEBUG 
	assert( row >= 0 && row < m_iRow ); 
#endif 
 
	return m_DoubleArray[row]; 
} 
 
#endif