sarray.hpp

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

//*******************************************************************
//	SArray.hpp
//	模块名称：启程动态数组C++模板类 
//	version:2.0
//  说明：该链表是在1.0版本的基础上强化了数据插入与删除的修正版，
//	本代码提供对动态数组的支持，在内存中程序将数据分块存放，
//　避免了大块内存的申请，同时也和普通的双向链表不同的是本代码提供
//　了对内部数据的快速索引，大大提高了数据访问速度。
//		增强程序对随机操作的支持，在链表的空间利用率<用户指定的比例时自动整理数据
//	程序员也可以重载判断是否需要进行数据整理的虚函数IsNeedCompack来使用自己的规则
//	该链表的主要目标是大量数据的管理，提供一个快速的数据插入删除等接口．在使用它时
//	配置一套好的参数将大大提高程序的执行效率，事实证明，该链表的执行效率大大高于
//	MFC提供的CArray
//		本代码可以任意使用、修改、传播，但作者不对使用该链表造成的后果承担任何直接或间接责任。
//		黄建雄　[e-mail]
//　update
//		2.0 黄建雄		2004-06-02
//		1.0 黄建雄		2003-09-25
//////////////////////////////////////////////////////////////////////

#if !defined(AFX_SARRAY_H__B1D40C22_2698_4202_921E_36D447EA4199__INCLUDED_)
#define AFX_SARRAY_H__B1D40C22_2698_4202_921E_36D447EA4199__INCLUDED_

#if _MSC_VER > 1000
#pragma once
#endif // _MSC_VER > 1000

#ifndef ASSERT
#define ASSERT(a) void()
#endif

#ifndef BOOL
#define BOOL int
#endif


template<class T>
class CSArray  
{
	typedef struct _SARRAYNODE{
		struct _SARRAYNODE *	pPrevNode;	//前一节点
		T				   *	pData;		//存储实际数据数组的数据块的指针	
		WORD					dwUsed;		//被占用的空间数,初始时为0，最大值为该结点的长度
		struct _SARRAYNODE *	pNextNode;	//后一节点
	}SARRAYNODE;

public:
	CSArray(WORD nGrowBy=5){
		m_pCurNode=m_pHeadNode=m_pTailNode=NULL;
		m_nCurIndex=-1;
		m_nCount=0;
		m_nEmpty=0;
		m_nGrowBy=nGrowBy;
		m_byZipKey=10;	//默认压缩阀值为10%
	}

	virtual ~CSArray(){Free();}

	//******************************************
	//	name:Add
	//	function:添加数据
	//	input:　T newElement-新数据
	//  return: 成功=数据索引号,失败=-1
	//	remark: 
	//******************************************
	int Add(T newElement)
	{
		if(m_nGrowBy==0)//
			return -1;
		if(m_pHeadNode==NULL)
		{
			if(!(m_pHeadNode=NewNode())) return -1;
			*m_pHeadNode->pData=newElement;
			m_pHeadNode->dwUsed=1;
			m_nCurIndex=0;
			m_nCount=1;
			m_nEmpty=m_nGrowBy-1;
			m_pCurNode=m_pTailNode=m_pHeadNode;
		}
		else
		{
			if(m_pTailNode->dwUsed==m_nGrowBy)
			{
				SARRAYNODE *pNewNode=NewNode();
				if(!pNewNode) return -1;
				pNewNode->pPrevNode=m_pTailNode;
				m_pTailNode->pNextNode=pNewNode;
				m_pTailNode=pNewNode;
				m_nEmpty+=m_nGrowBy;
			}
			m_pTailNode->pData[m_pTailNode->dwUsed++]=newElement;
			m_nCount++;
			m_nEmpty--;
			m_nCurIndex=m_nCount-m_pTailNode->dwUsed;
			m_pCurNode=m_pTailNode;
		}
		return m_nCount-1;
	}

	//******************************************
	//	name:AddBatch
	//	function:批量添加数据
	//	input:　T *pElement-源数组指针
	//			int count-数组大小
	//  return: BOOL　TRUE－成功；FALSE－失败
	//	remark: 
	//******************************************
	BOOL AddBatch(T *pElement,int count)
	{
		for(int i=0;i<count;i++)
			if(Add(pElement[i])==-1)
				return FALSE;
			return TRUE;
	}


	//******************************************
	//	name:Copy
	//	function:数据复制
	//	input:　CSArray & src-源动态数组
	//  return: 
	//	remark: 使用前请先确保两个对象有相同的数据类型
	//******************************************
	void Copy(CSArray &src )
	{
		T *pt;
		RemoveAll();
		int size=src.GetSize();
		SetSize(size);
		for(int i=0;i<m_nCount;i++)
		{
			pt=src.GetPtAt(i);
			SetAt(*pt,i);
		}
	}

	//******************************************
	//	name:GetAt
	//	function:获取数组指定位置的数据
	//	input:　int index-指定位置
	//  return: T 数据
	//	remark: 
	//******************************************
	T GetAt(DWORD index){
		SARRAYNODE      *pDest=NULL;
		ASSERT(index>=0&&index<m_nCount);
		pDest=GetDestSegEntry(index);
		return ((T *)pDest->pData)[index-m_nCurIndex];
	}
	
	//******************************************
	//	name:GetPtAt
	//	function:获取数组指定位置的数据的指针
	//	input:　int index-指定位置
	//  return: T 数据
	//	remark: 提供对内部数据的直接访问，小心使用!!
	//******************************************
	T *GetPtAt(DWORD index){
		SARRAYNODE      *pDest=NULL;
		ASSERT(index>=0&&index<m_nCount);
		pDest=GetDestSegEntry(index);
		return ((T *)pDest->pData)+index-m_nCurIndex;
	}
	
	T operator[](DWORD index){ return GetAt(index);}
	
	//******************************************
	//	name:GetSize
	//	function:获取数组的数据容量
	//	input:　
	//  return: int 数据容量
	//	remark: 
	//******************************************
	int GetSize(){return m_nCount;}
	
	void SetCompackKey(BYTE byKey){ m_byZipKey=byKey;}
	//******************************************
	//	name:SetAt
	//	function:修改数组指定位置的数据
	//	input:　T newElement-新数据
	//			int index-指定索引号
	//  return: BOOL TURE-成功；FALSE－失败
	//	remark: 
	//******************************************
	BOOL SetAt(DWORD index,T &newElement)
	{
		SARRAYNODE      *pDest=NULL;
		if(index<0||index>m_nCount-1)
			return FALSE;
		pDest=GetDestSegEntry(index);
		*(pDest->pData+index-m_nCurIndex)=newElement;
		return TRUE;
	}

	//******************************************
	//	name:InsertAt
	//	function:在数组指定位置插入一个新数据
	//	input:　int index-指定索引号
	//			T newElement-待插入的数据
	//  return: BOOL TURE-成功；FALSE－失败
	//	remark: 
	//******************************************
	int InsertAt(DWORD index,T newElement)
	{
		if(index>m_nCount)
			return -1;
		if(index==m_nCount) 
			return Add(newElement);
		SARRAYNODE *pDest=GetDestSegEntry(index);
		if(pDest->dwUsed==m_nGrowBy)
		{
			SARRAYNODE *pAddNode=NewNode();
			if(!pAddNode) return -1;
			pAddNode->dwUsed=pDest->dwUsed-(WORD)(index-m_nCurIndex);
			memcpy(pAddNode->pData,
				pDest->pData+index-m_nCurIndex,
				sizeof(T)*pAddNode->dwUsed);
			*(pDest->pData+index-m_nCurIndex)=newElement;
			pDest->dwUsed=(WORD)(index-m_nCurIndex+1);
			SARRAYNODE *pNext=pDest->pNextNode;
			pDest->pNextNode=pAddNode;
			pAddNode->pPrevNode=pDest;
			if(pNext){
				pNext->pPrevNode=pAddNode;
				pAddNode->pNextNode=pNext;
			}else
			{
				m_pTailNode=pAddNode;
			}
			m_nEmpty+=m_nGrowBy-1;
		}else
		{
			memmove(pDest->pData+index-m_nCurIndex+1,
				pDest->pData+index-m_nCurIndex,
				(pDest->dwUsed-(index-m_nCurIndex))*sizeof(T));
			*(pDest->pData+index-m_nCurIndex)=newElement;
			pDest->dwUsed++;
			m_nEmpty--;
		}
		m_nCount++;
		if(IsNeedCompack()) Compack();
		return index;
	}

	//******************************************
	//	name:RemoveAt
	//	function:删除数组中指定索引号中包含的数据
	//	input:　int index-指定索引号
	//  return: BOOL TURE-成功；FALSE－失败
	//	remark: 
	//******************************************
	BOOL RemoveAt(DWORD index)
	{
		if(index<0||index>=m_nCount)
			return FALSE;
		SARRAYNODE *pDest=GetDestSegEntry(index);
		m_nCount--;
		if(pDest->dwUsed==1)
		{
			SARRAYNODE *pPrev=pDest->pPrevNode;
			SARRAYNODE *pNext=pDest->pNextNode;
			if(!pPrev) 
			{
				m_pHeadNode=pNext;
				if(m_pHeadNode) m_pHeadNode->pPrevNode=NULL;
			}else
			{
				pPrev->pNextNode=pNext;
			}
			if(!pNext)
			{
				m_pTailNode=pPrev;
				if(m_pTailNode) m_pTailNode->pNextNode=NULL;
			}else
			{
				pNext->pPrevNode=pPrev;
			}
			if(pDest==m_pCurNode)
			{
				m_pCurNode=m_pHeadNode;
				m_nCurIndex=m_pHeadNode?0:-1;
			}
			FreeNode(pDest);
			m_nEmpty-=(m_nGrowBy-1);
		}else
		{
			memmove(pDest->pData+index-m_nCurIndex,
				pDest->pData+index-m_nCurIndex+1,
				sizeof(T)*(pDest->dwUsed-(index-m_nCurIndex+1)));
			pDest->dwUsed--;
			m_nEmpty++;
			if(IsNeedCompack()) Compack();
		}
		return TRUE;