www.pudn.com > WinGOS.rar > List.h

// CList.h: interface for the CArray class. 
// 
////////////////////////////////////////////////////////////////////// 
 
#ifndef _GOS_LIST_H_ 
#define _GOS_LIST_H_ 
 
///////////////////////////////////////////////////////////////////////////// 
// CList inline functions 
 
template 
__inline int CList::GetSize() const 
	{ return m_nCount; } 
template 
__inline BOOL CList::IsEmpty() const 
	{ return !m_nCount; } 
template 
__inline TYPE& CList::GetHead() 
	{ return m_pNodeHead->data; } 
template 
__inline TYPE& CList::GetTail() 
	{ return m_pNodeTail->data; } 
template 
__inline POSITION CList::GetHeadPosition() const 
	{ return (POSITION) m_pNodeHead; } 
template 
__inline POSITION CList::GetTailPosition() const 
	{ return (POSITION) m_pNodeTail; } 
template 
__inline TYPE& CList::GetNext(POSITION& rPosition) // return *Position++ 
	{ CNode* pNode = (CNode*) rPosition; 
		rPosition = (POSITION) pNode->pNext; 
		return pNode->data; } 
template 
__inline TYPE& CList::GetPrev(POSITION& rPosition) // return *Position-- 
	{ CNode* pNode = (CNode*) rPosition; 
		rPosition = (POSITION) pNode->pPrev; 
		return pNode->data; } 
template 
__inline TYPE& CList::GetAt(POSITION position) 
	{ CNode* pNode = (CNode*) position; 
		return pNode->data; } 
template 
__inline void CList::SetAt(POSITION pos, const TYPE& newElement) 
	{ CNode* pNode = (CNode*) pos; 
		pNode->data = newElement; } 
 
template 
CList::CList(int nBlockSize) 
{ 
	m_nCount = 0; 
	m_pNodeHead = m_pNodeTail = m_pNodeFree = NULL; 
	m_pBlocks = NULL; 
	m_nBlockSize = nBlockSize; 
	DEBUG_ONLY(nBlockSize=CHeap::ElementCount(sizeof(CNode),nBlockSize,sizeof(CPlex*))); 
	ASSERT(m_nBlockSize==nBlockSize); 
} 
 
template 
void CList::RemoveAll() 
{ 
	// destroy elements 
	m_nCount = 0; 
	m_pNodeHead = m_pNodeTail = m_pNodeFree = NULL; 
	m_pBlocks->FreeDataChain(); 
	m_pBlocks = NULL; 
} 
 
template 
CList::~CList() 
{ 
	RemoveAll(); 
	ASSERT(m_nCount == 0); 
} 
 
template 
PVOID CList::NewNode(CNode* pPrev, CNode* pNext) 
{ 
	if (m_pNodeFree == NULL) 
	{ 
		CNode* pNode = (CNode*)CPlex::CreateHead(m_pBlocks, 
			m_nBlockSize*sizeof(CNode)); 
		pNode += m_nBlockSize - 1; 
		for (int i = m_nBlockSize-1; i >= 0; i--, pNode--) 
		{ 
			pNode->pNext = m_pNodeFree; 
			m_pNodeFree = pNode; 
		} 
	} 
	ASSERT(m_pNodeFree != NULL);  // we must have something 
 
	CNode* pNode = m_pNodeFree; 
	m_pNodeFree = m_pNodeFree->pNext; 
	pNode->pPrev = pPrev; 
	pNode->pNext = pNext; 
	m_nCount++; 
	ASSERT(m_nCount > 0);  // make sure we don't overflow 
	return pNode; 
} 
 
template 
void CList::FreeNode(CNode* pNode) 
{ 
	pNode->pNext = m_pNodeFree; 
	m_pNodeFree = pNode; 
	m_nCount--; 
	ASSERT(m_nCount >= 0);  // make sure we don't underflow 
 
	// if no more elements, cleanup completely 
	if (m_nCount == 0)RemoveAll(); 
} 
 
template 
POSITION CList::AddHead(const TYPE& newElement) 
{ 
	CNode* pNewNode = (CNode*)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; 
} 
 
template 
POSITION CList::AddTail(const TYPE& newElement) 
{ 
	CNode* pNewNode = (CNode*)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; 
} 
 
template 
void CList::AddHead(CList* pNewList) 
{ 
	ASSERT(pNewList); 
	// add a list of same elements to head (maintain order) 
	POSITION pos = pNewList->GetTailPosition(); 
	while (pos != NULL) 
		AddHead(pNewList->GetPrev(pos)); 
} 
 
template 
void CList::AddTail(CList* pNewList) 
{ 
	ASSERT(pNewList); 
	// add a list of same elements 
	POSITION pos = pNewList->GetHeadPosition(); 
	while (pos != NULL) 
		AddTail(pNewList->GetNext(pos)); 
} 
 
template 
TYPE CList::RemoveHead() 
{ 
	ASSERT(m_pNodeHead != NULL);  // don't call on empty list !!! 
 
	CNode* pOldNode = m_pNodeHead; 
	TYPE returnValue = pOldNode->data; 
 
	m_pNodeHead = pOldNode->pNext; 
	if (m_pNodeHead != NULL) 
		m_pNodeHead->pPrev = NULL; 
	else 
		m_pNodeTail = NULL; 
	FreeNode(pOldNode); 
	return returnValue; 
} 
 
template 
TYPE CList::RemoveTail() 
{ 
	ASSERT(m_pNodeTail != NULL);  // don't call on empty list !!! 
 
	CNode* pOldNode = m_pNodeTail; 
	TYPE returnValue = pOldNode->data; 
 
	m_pNodeTail = pOldNode->pPrev; 
	if (m_pNodeTail != NULL) 
		m_pNodeTail->pNext = NULL; 
	else 
		m_pNodeHead = NULL; 
	FreeNode(pOldNode); 
	return returnValue; 
} 
 
template 
POSITION CList::InsertBefore(POSITION position, const TYPE& newElement) 
{ 
	if (position == NULL) 
		return AddHead(newElement); // insert before nothing -> head of the list 
 
	// Insert it before position 
	CNode* pOldNode = (CNode*)position; 
	CNode* pNewNode = (CNode*)NewNode(pOldNode->pPrev, pOldNode); 
	pNewNode->data = newElement; 
 
	if (pOldNode->pPrev != NULL) 
		pOldNode->pPrev->pNext = pNewNode; 
	else 
		m_pNodeHead = pNewNode; 
	pOldNode->pPrev = pNewNode; 
	return (POSITION) pNewNode; 
} 
 
template 
POSITION CList::InsertAfter(POSITION position, const TYPE& newElement) 
{ 
	if (position == NULL) 
		return AddTail(newElement); // insert after nothing -> tail of the list 
 
	// Insert it before position 
	CNode* pOldNode = (CNode*)position; 
	CNode* pNewNode = (CNode*)NewNode(pOldNode, pOldNode->pNext); 
	pNewNode->data = newElement; 
 
	if (pOldNode->pNext != NULL) 
		pOldNode->pNext->pPrev = pNewNode; 
	else 
		m_pNodeTail = pNewNode; 
	pOldNode->pNext = pNewNode; 
	return (POSITION) pNewNode; 
} 
 
template 
void CList::RemoveAt(POSITION position) 
{ 
	CNode* pOldNode = (CNode*) position; 
	// remove pOldNode from list 
	if (pOldNode == m_pNodeHead) 
		m_pNodeHead = pOldNode->pNext; 
	else 
		pOldNode->pPrev->pNext = pOldNode->pNext; 
	if (pOldNode == m_pNodeTail) 
		m_pNodeTail = pOldNode->pPrev; 
	else 
		pOldNode->pNext->pPrev = pOldNode->pPrev; 
	FreeNode(pOldNode); 
} 
 
template 
POSITION CList::FindIndex(int nIndex) const 
{ 
	if (nIndex >= m_nCount || nIndex < 0) 
		return NULL;  // went too far 
	CNode* pNode = m_pNodeHead; 
	while (nIndex--) 
		pNode = pNode->pNext; 
	return (POSITION) pNode; 
} 
 
template 
int CList::GetIndex(POSITION position) const 
{ 
	CNode* pNode; 
	int nIndex=0; 
	for(pNode = m_pNodeHead ; pNode ; pNode = pNode->pNext) 
	{ 
		if((POSITION)pNode==position) 
			return nIndex; 
		nIndex++; 
	} 
	return -1; 
} 
 
template 
POSITION CList::Find(const TYPE& searchValue, POSITION startAfter) const 
{ 
	CNode* pNode = (CNode*) startAfter; 
	if (pNode == NULL) 
		pNode = m_pNodeHead;  // start at head 
	else 
		pNode = pNode->pNext;  // start after the one specified 
	for (; pNode != NULL; pNode = pNode->pNext) 
		if(pNode->data==searchValue) 
			return (POSITION)pNode; 
	return NULL; 
} 
 
#endif _GOS_LIST_H_