coll_list.cpp

相当不错的入门程序

#include "stdafx.h"
#include "coll_list.h"


/////////////////////////////////////////////////////////////////////////////
// 数据桶
TBucket* TBucket::Create(TBucket*& pHead,UINT nMax,UINT cbElement)
{
	ASSERT(nMax>0&&cbElement>0);
	TBucket* pBucket=(TBucket*)new BYTE[sizeof(TBucket)+nMax*cbElement];
	pBucket->m_pNext=pHead;
	pHead=pBucket;
	return pBucket;
}

void TBucket::FreeDataChain()
{
	TBucket* pBucket=this;
	while(pBucket!=NULL)
	{	LPBYTE lpBytes=(LPBYTE) pBucket;
		TBucket* pNext=pBucket->m_pNext;
		delete[] lpBytes;
		pBucket=pNext;
	}
}


//////////////////////////////////////////////////////////////////////////
// TListPtr:标准实现
//////////////////////////////////////////////////////////////////////////

TListPtr::TListPtr(LONG nBlockSize)
{
	ASSERT(nBlockSize>0);
	m_nCount=0;
	m_pNodeHead=m_pNodeTail=m_pNodeFree=NULL;
	m_pBlocks=NULL;
	m_nBlockSize=nBlockSize;
}

VOID TListPtr::RemoveAll()
{
	CNode* pNode;
	for(pNode=m_pNodeHead; pNode!=NULL; pNode=pNode->pNext)
		CollDestructElements(&pNode->data,1);
	m_nCount=0;
	m_pNodeHead=m_pNodeTail=m_pNodeFree=NULL;
	m_pBlocks->FreeDataChain();
	m_pBlocks=NULL;
}

TListPtr::~TListPtr()
{
	RemoveAll();
	ASSERT(m_nCount==0);
}

TListPtr::CNode* TListPtr::NewNode(TListPtr::CNode* pPrev,TListPtr::CNode* pNext)
{
	// 块空,添加新块并完成链接
	if(m_pNodeFree==NULL)
	{	TBucket* pNewBlock=TBucket::Create(m_pBlocks,m_nBlockSize,sizeof(CNode));
		CNode* pNode=(CNode*)pNewBlock->Data();
		pNode += m_nBlockSize-1;
		for(LONG i=m_nBlockSize-1; i>=0; i--,pNode--)
		{	pNode->pNext=m_pNodeFree;
			m_pNodeFree=pNode;
		}
	}
	// 从链接对象中分配一个可用单元
	ASSERT(m_pNodeFree!=NULL);
	TListPtr::CNode* pNode=m_pNodeFree;
	m_pNodeFree=m_pNodeFree->pNext;
	pNode->pPrev=pPrev;
	pNode->pNext=pNext;
	m_nCount++;
	ASSERT(m_nCount>0);
	CollConstructElements(&pNode->data,1);
	return pNode;
}

VOID TListPtr::FreeNode(TListPtr::CNode* pNode)
{	CollDestructElements(&pNode->data,1);
	pNode->pNext=m_pNodeFree;
	m_pNodeFree=pNode;
	m_nCount--;
	ASSERT(m_nCount>=0);
	if(m_nCount==0) RemoveAll();
}

POSITION TListPtr::AddHead(LPVOID newElement)
{	CNode* pNewNode=NewNode(NULL,m_pNodeHead);
	pNewNode->data=newElement;
	if(m_pNodeHead!=NULL)
			m_pNodeHead->pPrev=pNewNode;
	else	m_pNodeTail=pNewNode;
	m_pNodeHead=pNewNode;
	return (POSITION) pNewNode;
}

POSITION TListPtr::AddTail(LPVOID newElement)
{	CNode* pNewNode=NewNode(m_pNodeTail,NULL);
	pNewNode->data=newElement;
	if(m_pNodeTail!=NULL)
			m_pNodeTail->pNext=pNewNode;
	else	m_pNodeHead=pNewNode;
	m_pNodeTail=pNewNode;
	return (POSITION)pNewNode;
}

VOID TListPtr::AddHead(TListPtr* pNewList)
{	ASSERT(pNewList!=NULL);
	POSITION pos=pNewList->GetTailPosition();
	while(pos!=NULL)
		AddHead(pNewList->GetPrev(pos));
}

VOID TListPtr::AddTail(TListPtr* pNewList)
{
	ASSERT(pNewList!=NULL);
	POSITION pos=pNewList->GetHeadPosition();
	while(pos!=NULL)
		AddTail(pNewList->GetNext(pos));
}

LPVOID TListPtr::RemoveHead()
{
	ASSERT(m_pNodeHead!=NULL);
	ASSERT(ClibIsValidAddress(m_pNodeHead,sizeof(CNode)));
	CNode* pOldNode=m_pNodeHead;
	LPVOID returnValue=pOldNode->data;
	m_pNodeHead=pOldNode->pNext;
	if(m_pNodeHead!=NULL)
			m_pNodeHead->pPrev=NULL;
	else	m_pNodeTail=NULL;
	FreeNode(pOldNode);
	return returnValue;
}

LPVOID TListPtr::RemoveTail()
{
	ASSERT(m_pNodeTail!=NULL);
	ASSERT(ClibIsValidAddress(m_pNodeTail,sizeof(CNode)));
	CNode* pOldNode=m_pNodeTail;
	LPVOID returnValue=pOldNode->data;
	m_pNodeTail=pOldNode->pPrev;
	if(m_pNodeTail!=NULL)
			m_pNodeTail->pNext=NULL;
	else	m_pNodeHead=NULL;
	FreeNode(pOldNode);
	return returnValue;
}

POSITION TListPtr::InsertBefore(POSITION position,LPVOID newElement)
{
	if(position==NULL)
		return AddHead(newElement);
	CNode* pOldNode=(CNode*) position;
	CNode* pNewNode=NewNode(pOldNode->pPrev,pOldNode);
	pNewNode->data=newElement;

	if(pOldNode->pPrev!=NULL)
	{	ASSERT(ClibIsValidAddress(pOldNode->pPrev,sizeof(CNode)));
		pOldNode->pPrev->pNext=pNewNode;
	}
	else
	{	ASSERT(pOldNode==m_pNodeHead);
		m_pNodeHead=pNewNode;
	}
	pOldNode->pPrev=pNewNode;
	return (POSITION) pNewNode;
}

POSITION TListPtr::InsertAfter(POSITION position,LPVOID newElement)
{
	if(position==NULL)
		return AddTail(newElement);
	CNode* pOldNode=(CNode*) position;
	ASSERT(ClibIsValidAddress(pOldNode,sizeof(CNode)));
	CNode* pNewNode=NewNode(pOldNode,pOldNode->pNext);
	pNewNode->data=newElement;
	if(pOldNode->pNext!=NULL)
	{	ASSERT(ClibIsValidAddress(pOldNode->pNext,sizeof(CNode)));
		pOldNode->pNext->pPrev=pNewNode;
	}
	else
	{	ASSERT(pOldNode==m_pNodeTail);
		m_pNodeTail=pNewNode;
	}
	pOldNode->pNext=pNewNode;
	return (POSITION)pNewNode;
}

VOID TListPtr::RemoveAt(POSITION position)
{	CNode* pOldNode=(CNode*) position;
	ASSERT(ClibIsValidAddress(pOldNode,sizeof(CNode)));
	if(pOldNode==m_pNodeHead)
	{	m_pNodeHead=pOldNode->pNext;
	}
	else
	{	ASSERT(ClibIsValidAddress(pOldNode->pPrev,sizeof(CNode)));
		pOldNode->pPrev->pNext=pOldNode->pNext;
	}
	if(pOldNode==m_pNodeTail)
	{	m_pNodeTail=pOldNode->pPrev;
	}
	else
	{	ASSERT(ClibIsValidAddress(pOldNode->pNext,sizeof(CNode)));
		pOldNode->pNext->pPrev=pOldNode->pPrev;
	}
	FreeNode(pOldNode);
}

POSITION TListPtr::FindIndex(LONG nIndex) CONST
{	if(nIndex>=m_nCount || nIndex<0)
		return NULL;
	CNode* pNode=m_pNodeHead;
	while(nIndex--)
	{	ASSERT(ClibIsValidAddress(pNode,sizeof(CNode)));
		pNode=pNode->pNext;
	}
	return (POSITION)pNode;
}

POSITION TListPtr::Find(LPVOID searchValue,POSITION startAfter) CONST
{	CNode* pNode=(CNode*) startAfter;
	if(pNode==NULL)
	{	pNode=m_pNodeHead;
	}
	else
	{	ASSERT(ClibIsValidAddress(pNode,sizeof(CNode)));
		pNode=pNode->pNext;
	}
	for(; pNode!=NULL; pNode=pNode->pNext)
		if(CollCompareElements(&pNode->data,&searchValue))
			return (POSITION)pNode;
	return NULL;
}