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

#ifndef _LIST_H_ 
#define _LIST_H_ 
 
//#include "public.h" 
#ifndef POSITION 
typedef struct{} *POSITION; 
#endif 
 
template 
class CList  
{ 
protected: 
	struct CNode 
	{ 
		CNode* pNext; 
		CNode* pPrev; 
		TYPE data; 
	}; 
public: 
// Construction 
	CList(); 
 
// Attributes (head and tail) 
	// count of elements 
	int GetCount() const; 
	BOOL IsEmpty() const; 
 
	// peek at head or tail 
	TYPE& GetHead(); 
	TYPE GetHead() const; 
	TYPE& GetTail(); 
	TYPE GetTail() const; 
 
// Operations 
	// get head or tail (and remove it) - don't call on empty list ! 
	TYPE RemoveHead(); 
	TYPE RemoveTail(); 
 
	// add before head or after tail 
	POSITION AddHead(ARG_TYPE newElement); 
	POSITION AddTail(ARG_TYPE newElement); 
 
	// add another list of elements before head or after tail 
	void AddHead(CList* pNewList); 
	void AddTail(CList* pNewList); 
 
	// remove all elements 
	void RemoveAll(); 
 
	// iteration 
	POSITION GetHeadPosition() const; 
	POSITION GetTailPosition() const; 
	TYPE& GetNext(POSITION& rPosition); // return *Position++ 
	TYPE GetNext(POSITION& rPosition) const; // return *Position++ 
	TYPE& GetPrev(POSITION& rPosition); // return *Position-- 
	TYPE GetPrev(POSITION& rPosition) const; // return *Position-- 
 
	// getting/modifying an element at a given position 
	TYPE& GetAt(POSITION position); 
	TYPE GetAt(POSITION position) const; 
	void SetAt(POSITION pos, ARG_TYPE newElement); 
	void RemoveAt(POSITION position); 
 
	// inserting before or after a given position 
	POSITION InsertBefore(POSITION position, ARG_TYPE newElement); 
	POSITION InsertAfter(POSITION position, ARG_TYPE newElement); 
 
	// helper functions (note: O(n) speed) 
	POSITION Find(ARG_TYPE searchValue, POSITION startAfter = NULL) const; 
		// defaults to starting at the HEAD, return NULL if not found 
	POSITION FindIndex(int nIndex) const; 
		// get the 'nIndex'th element (may return NULL) 
 
// Implementation 
protected: 
	CNode* m_pNodeHead; 
	CNode* m_pNodeTail; 
	int m_nCount; 
	void FreeNode(CNode*); 
 
public: 
	~CList(); 
}; 
 
///////////////////////////////////////////////////////////////////////////// 
// CList inline functions 
 
template 
inline int CList::GetCount() const 
	{ return m_nCount; } 
template 
inline BOOL CList::IsEmpty() const 
	{ return m_nCount == 0; } 
template 
inline TYPE& CList::GetHead() 
	{ ASSERT(m_pNodeHead != NULL); 
		return m_pNodeHead->data; } 
template 
inline TYPE CList::GetHead() const 
	{ ASSERT(m_pNodeHead != NULL); 
		return m_pNodeHead->data; } 
template 
inline TYPE& CList::GetTail() 
	{ ASSERT(m_pNodeTail != NULL); 
		return m_pNodeTail->data; } 
template 
inline TYPE CList::GetTail() const 
	{ ASSERT(m_pNodeTail != NULL); 
		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::GetNext(POSITION& rPosition) const // 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::GetPrev(POSITION& rPosition) const // 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 TYPE CList::GetAt(POSITION position) const 
	{ CNode* pNode = (CNode*) position; 
		return pNode->data; } 
template 
inline void CList::SetAt(POSITION pos, ARG_TYPE newElement) 
	{ CNode* pNode = (CNode*) pos; 
		pNode->data = newElement; } 
 
 
template 
CList::CList() 
{ 
	m_nCount = 0; 
	m_pNodeHead = m_pNodeTail = NULL; 
} 
 
template 
void CList::RemoveAll() 
{ 
	ATLASSERT(this); 
	// destroy elements 
	CNode* pNode; 
	while(m_pNodeHead != m_pNodeTail) 
	{ 
		pNode = m_pNodeTail; 
		m_pNodeTail = m_pNodeTail->pPrev; 
		delete pNode; 
	} 
	delete m_pNodeHead; 
 
	m_nCount = 0; 
	m_pNodeHead = m_pNodeTail = NULL; 
} 
 
template 
CList::~CList() 
{ 
	RemoveAll(); 
	ASSERT(m_nCount == 0); 
} 
 
template 
void CList::FreeNode(CList::CNode* pNode) 
{ 
	delete pNode; 
	m_nCount--; 
	ASSERT(m_nCount >= 0);  // make sure we don't underflow 
} 
 
template 
POSITION CList::AddHead(ARG_TYPE newElement) 
{ 
	ATLASSERT(this); 
 
	CNode* pNewNode = new CNode; 
	ASSERT(pNewNode != NULL); 
	if(pNewNode == NULL) 
		return NULL; 
	pNewNode->pNext = pNewNode->pPrev = NULL; 
	 
	m_nCount ++; 
	pNewNode->data = newElement; 
	if (m_pNodeHead != NULL) 
	{ 
		m_pNodeHead->pPrev = pNewNode; 
		pNewNode->pNext = m_pNodeHead; 
	} 
	else 
		m_pNodeTail = pNewNode; 
	m_pNodeHead = pNewNode; 
	return (POSITION) pNewNode; 
} 
 
template 
POSITION CList::AddTail(ARG_TYPE newElement) 
{ 
	ATLASSERT(this); 
	CNode* pNewNode = new CNode; 
	ASSERT(pNewNode != NULL); 
	if(pNewNode == NULL) 
		return NULL; 
	pNewNode->pNext = pNewNode->pPrev = NULL; 
	m_nCount++; 
 
	pNewNode->data = newElement; 
	 
	if (m_pNodeTail != NULL) 
	{ 
		m_pNodeTail->pNext = pNewNode; 
		pNewNode->pPrev = m_pNodeTail; 
	} 
	else 
		m_pNodeHead = pNewNode; 
	m_pNodeTail = pNewNode; 
	return (POSITION) pNewNode; 
} 
 
template 
void CList::AddHead(CList* pNewList) 
{ 
	ATLASSERT(this); 
 
	ASSERT(pNewList != NULL); 
	ATLASSERT(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) 
{ 
	ATLASSERT(this); 
	ASSERT(pNewList != NULL); 
	ATLASSERT(pNewList); 
 
	// add a list of same elements 
	POSITION pos = pNewList->GetHeadPosition(); 
	while (pos != NULL) 
		AddTail(pNewList->GetNext(pos)); 
} 
 
template 
TYPE CList::RemoveHead() 
{ 
	ATLASSERT(this); 
	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() 
{ 
	ATLASSERT(this); 
	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, ARG_TYPE newElement) 
{ 
	ATLASSERT(this); 
 
	if (position == NULL) 
		return AddHead(newElement); // insert before nothing -> head of the list 
 
	// Insert it before position 
	CNode* pOldNode = (CNode*) position; 
	CNode* pNewNode = new CNode; 
	ASSERT( pNewNode != NULL ); 
 
	m_nCount ++; 
	pNewNode->data = newElement; 
 
	if (pOldNode->pPrev != NULL) 
	{ 
		pOldNode->pPrev->pNext = pNewNode; 
		pNewNode->pPrev = pOldNode->pPrev; 
		pNewNode->pNext = pOldNode; 
	} 
	else 
	{ 
		ASSERT(pOldNode == m_pNodeHead); 
		pNewNode->pNext = pOldNode; 
		m_pNodeHead = pNewNode;		 
	} 
	pOldNode->pPrev = pNewNode; 
	return (POSITION) pNewNode; 
} 
 
template 
POSITION CList::InsertAfter(POSITION position, ARG_TYPE newElement) 
{ 
	ATLASSERT(this); 
 
	if (position == NULL) 
		return AddTail(newElement); // insert after nothing -> tail of the list 
 
	// Insert it before position 
	CNode* pOldNode = (CNode*) position; 
	CNode* pNewNode = new CNode; 
	ASSERT( pNewNode != NULL ); 
 
	m_nCount ++; 
	pNewNode->data = newElement; 
 
	if (pOldNode->pNext != NULL) 
	{ 
		pNewNode->pNext = pOldNode->pNext; 
		pOldNode->pNext->pPrev = pNewNode; 
		pNewNode->pPrev = pOldNode; 
	} 
	else 
	{ 
		ASSERT(pOldNode == m_pNodeTail); 
		pNewNode->pPrev = pOldNode; 
		m_pNodeTail = pNewNode; 
	} 
	pOldNode->pNext = pNewNode; 
	return (POSITION) pNewNode; 
} 
 
template 
void CList::RemoveAt(POSITION position) 
{ 
	ATLASSERT(this); 
 
	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 
{ 
	ATLASSERT(this); 
 
	if (nIndex >= m_nCount || nIndex < 0) 
		return NULL;  // went too far 
 
	CNode* pNode = m_pNodeHead; 
	while (nIndex--) 
	{ 
		pNode = pNode->pNext; 
	} 
	return (POSITION) pNode; 
} 
 
template 
BOOL WINAPI CompareElements(const TYPE* pElement1, const ARG_TYPE* pElement2) 
{ 
	ATLASSERT(pElement1 && pElement2); 
	return *pElement1 == *pElement2; 
} 
 
template 
POSITION CList::Find(ARG_TYPE searchValue, POSITION startAfter) const 
{ 
	ATLASSERT(this); 
 
	CNode* pNode = (CNode*) startAfter; 
	if (pNode == NULL) 
	{ 
		pNode = m_pNodeHead;  // start at head 
	} 
	else 
	{ 
		//ASSERT(AfxIsValidAddress(pNode, sizeof(CNode))); 
		pNode = pNode->pNext;  // start after the one specified 
	} 
 
	for (; pNode != NULL; pNode = pNode->pNext) 
		if (CompareElements(&pNode->data, &searchValue)) 
			return (POSITION)pNode; 
	return NULL; 
} 
#endif