sarray.hpp

实习性 动态数组(第二版) 大量数据的管理是很多程序员的心病

	}

	//******************************************
	//	name:SetSize()
	//	function:设置数据的容量
	//	input:　int size -数据的容量
	//  return: BOOL TURE-成功；FALSE－失败
	//	remark:只允许扩大容量
	//******************************************
	BOOL SetSize(DWORD size){
		SARRAYNODE *pNewNode=NULL;
		if(m_nCount>=size)
			return FALSE;
		if(m_pTailNode)
		{
			if((WORD)(size-m_nCount)<=m_nGrowBy-m_pTailNode->dwUsed)
			{//neet not to enlarge the buffer
				m_pTailNode->dwUsed+=(WORD)(size-m_nCount);
				m_nEmpty-=size-m_nCount;
				m_nCount=size;
				return TRUE;
			}else if(m_pTailNode->dwUsed!=m_nGrowBy)
			{//fill the tail node to full
				m_nEmpty+=m_nGrowBy-m_pTailNode->dwUsed;
				m_nCount+=m_nGrowBy-m_pTailNode->dwUsed;
				m_pTailNode->dwUsed=m_nGrowBy;
			}
		}
		int newsegs=(size-m_nCount+m_nGrowBy-1)/m_nGrowBy;
		for(int i=0;i<newsegs;i++)
		{
			pNewNode=NewNode();
			if(!pNewNode) return FALSE;
			pNewNode->dwUsed=(i<newsegs-1)?m_nGrowBy:(WORD)(size-m_nCount);
			if(!m_pHeadNode)
			{
				m_pHeadNode=m_pTailNode=m_pCurNode=pNewNode;
				m_nCurIndex=0;
			}
			ASSERT(m_pTailNode);
			m_pTailNode->pNextNode=pNewNode;
			pNewNode->pPrevNode=m_pTailNode;
			m_pTailNode=pNewNode;
			m_nCount+=pNewNode->dwUsed;
		}
		return TRUE;
	}
	
	//******************************************
	//	name:SetGrowBy()
	//	function:设置数据增长幅度
	//	input:　
	//  return: 
	//	remark: 在初始化时使用
	//******************************************
	void SetGrowBy(WORD nGrowBy)
	{
		ASSERT(m_nCount==0);
		m_nGrowBy=nGrowBy;
	}

	//******************************************
	//	name:RemoveAll()
	//	function:清空对象中的数据
	//	input:　
	//  return: BOOL TURE-成功；FALSE－失败
	//	remark:
	//******************************************
	BOOL RemoveAll(){
		if(m_pHeadNode==NULL)
			return TRUE;
		Free();
		m_pCurNode=m_pHeadNode=m_pTailNode=NULL;
		m_nCurIndex=-1;
		m_nCount=0;
		m_nEmpty=0;
		return TRUE;
	}

	//*********************************************
	//  name:Compack
	//	function :压缩数据
	//	remark:将链表中各结点段的空余空间进行整理，释放多余的节点
	//*********************************************
	void Compack()
	{
		SARRAYNODE *pTmp1,*pTmp2=NULL;
		if(m_pHeadNode==m_pTailNode) return;
		pTmp1=FindNotFullNode(m_pHeadNode,m_pTailNode);
		while(pTmp1)
		{
			if(pTmp2==NULL)	pTmp2=pTmp1->pNextNode;
			ASSERT(pTmp2);
			while(pTmp1->dwUsed!=(DWORD)m_nGrowBy&&pTmp2)
			{
				if(pTmp2->dwUsed<=(m_nGrowBy-pTmp1->dwUsed))
				{//the node can free
					memcpy(pTmp1->pData+pTmp1->dwUsed,
						pTmp2->pData,
						sizeof(T)*pTmp2->dwUsed);
					pTmp1->dwUsed+=pTmp2->dwUsed;
					if(m_pTailNode==pTmp2)
					{
						m_pTailNode=pTmp2->pPrevNode;
						m_pTailNode->pNextNode=NULL;
						FreeNode(pTmp2);
						pTmp2=NULL;
					}else
					{
						pTmp2->pPrevNode->pNextNode=pTmp2->pNextNode;
						pTmp2->pNextNode->pPrevNode=pTmp2->pPrevNode;
						SARRAYNODE *p=pTmp2->pNextNode;
						FreeNode(pTmp2);
						pTmp2=p;
					}
				}else
				{//dest node remain data
					DWORD dwMoveItems=m_nGrowBy-pTmp1->dwUsed;
					memcpy(pTmp1->pData+pTmp1->dwUsed,
						pTmp2->pData,
						sizeof(T)*dwMoveItems);
					memmove(pTmp2->pData,
						pTmp2->pData+dwMoveItems,
						sizeof(T)*(pTmp2->dwUsed-dwMoveItems));
					pTmp2->dwUsed-=(WORD)dwMoveItems;
					pTmp1->dwUsed=m_nGrowBy;
				}
			}//while
			SARRAYNODE *pFind=FindNotFullNode(pTmp1,pTmp2);
			if(!pFind)
			{
				pTmp1=FindNotFullNode(pTmp1,m_pTailNode);
			}else
			{
				pTmp1=pFind;
			}
			pTmp2=NULL;
		}//while
		m_pCurNode=m_pHeadNode;//avoid the current node been deleted
		m_nCurIndex=0;
		if(m_pTailNode)
			m_nEmpty=m_nGrowBy-m_pTailNode->dwUsed;
		else
			m_nEmpty=0;
	}	
protected:


	//********************************************
	//	name:IsNeedCompack
	//	function:判断是否需要对数据进行压缩
	//*********************************************
	virtual BOOL IsNeedCompack()
	{
		if(m_nEmpty<m_nGrowBy) return FALSE;
		return ((m_nEmpty-m_nGrowBy)*100>m_nCount*m_byZipKey);
	}
	//******************************************
	//	name:Free()
	//	function:释放对象占用的空间，
	//	input:
	//  return:void
	//	remark:内部使用,外部要清空对象请使用RemoveAll()接口
	//******************************************
	virtual void Free()
	{
		SARRAYNODE *temp1,*temp2;
		temp1=m_pHeadNode;
		while(temp1!=NULL)
		{
			temp2=temp1->pNextNode;
			FreeNode(temp1);
			temp1=temp2;
		}
	}
private:

	//************************************************
	//	FreeNode
	//	释放该结点占用的内存
	//************************************************
	void FreeNode(SARRAYNODE *pNode)
	{
		delete []pNode->pData;
		delete pNode;
	}
	//*********************************************
	//	查找有空闲空间的结点
	//*********************************************
	SARRAYNODE *FindNotFullNode(SARRAYNODE *pBegin,SARRAYNODE *pEnd)
	{
		SARRAYNODE *pRet=pBegin;
		if(!pEnd) pEnd=m_pTailNode;
		while(pRet&&pRet->dwUsed==m_nGrowBy&&pRet!=pEnd) pRet=pRet->pNextNode;
		if(pRet==m_pTailNode||pRet==pEnd) pRet=NULL;
		return pRet;
	}

	//*******************************************
	//	name NewNode
	//	function:为一个新结点分配空间
	//********************************************
	SARRAYNODE *NewNode()
	{
		SARRAYNODE *pRet=new SARRAYNODE;
		if(!pRet) return NULL;
		pRet->pPrevNode=pRet->pNextNode=NULL;
		pRet->dwUsed=0;
		pRet->pData=new T[m_nGrowBy];
		if(pRet->pData==NULL)
		{
			delete pRet;
			return NULL;
		}
		return pRet;
	}
	//******************************************
	//	name:GetDestSegEntry()
	//  function:获取数据所在链表的节点指针
	//	input:	int index -数据索引
	//  return: SARRAYNODE * -数据所在链表的节点指针
	//	remark:内部使用，
	//******************************************
	SARRAYNODE * GetDestSegEntry(DWORD index)
	{
		SARRAYNODE * ret=NULL;
		int			i=0;
		DWORD			offset=0;
		if(index<m_nCurIndex)// dest pData is in before cur pData segment 
		{
			if(m_nCurIndex>2*index)
			{	//find the seg from head;
				ret=m_pHeadNode;
				while(offset+ret->dwUsed<=index)
				{
					offset+=ret->dwUsed;
					ret=ret->pNextNode;
				}
			}else	
			{	//find the seg from cur seg;
				ret=m_pCurNode;
				offset=m_nCurIndex;
				while(offset>index)
				{
					ret=ret->pPrevNode;
					offset-=ret->dwUsed;
				}
			}
			m_nCurIndex=offset;
		}else if(index>=(m_nCurIndex+m_pCurNode->dwUsed))
		{
			if(m_nCurIndex+m_nCount<2*index)
			{//find the seg from cur
				ret=m_pCurNode;
				offset=m_nCurIndex;
				while(offset+ret->dwUsed<=index)
				{
					offset+=ret->dwUsed;
					ret=ret->pNextNode;
				}
			}else
			{//find the seg from tail
				ret=m_pTailNode;
				offset=m_nCount-ret->dwUsed;;
				while(offset>index)
				{
					ret=ret->pPrevNode;
					offset-=ret->dwUsed;
				}
			}
			m_nCurIndex=offset;
		}else
		{//in cur pData seg
			ret=m_pCurNode;
		}
		m_pCurNode=ret;
		return ret;
	}

/////////////////////////////////////////////////////////////////////
//  private data
	DWORD m_nCurIndex;	//当前节点的第一个元素的索引号
	DWORD m_nCount;		//数组对象包括的数据数
	WORD m_nGrowBy;		//每次增长的尺寸
	DWORD m_nEmpty;		//空出的空间数量

	BYTE m_byZipKey;	//压缩阀值
	SARRAYNODE * m_pCurNode;	//链表中当前节点的指针，在数据检索时确定从向个方向搜索
	SARRAYNODE * m_pHeadNode;	//头节点
	SARRAYNODE * m_pTailNode;	//尾结点
};

#endif // !defined(AFX_SARRAY_H__B1D40C22_2698_4202_921E_36D447EA4199__INCLUDED_)