www.pudn.com > RCApp-src.zip > List.h

/* 
	RedEye Project (http://members.ozemail.com.au/~ndmcevoy/) 
	Copyright (C) 2003  Nick McEvoy 
 
	This library is free software; you can redistribute it and/or 
	modify it under the terms of the GNU Library General Public 
	License as published by the Free Software Foundation; either 
	version 2 of the License, or (at your option) any later version. 
 
	This library is distributed in the hope that it will be useful, 
	but WITHOUT ANY WARRANTY; without even the implied warranty of 
	MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU 
	Library General Public License for more details. 
 
	You should have received a copy of the GNU Library General Public 
	License along with this library; if not, write to the Free 
	Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. 
 
	----------------------------------------------------------------- 
 
		Commented for use with Doxygen (http://www.doxygen.org) 
 
	----------------------------------------------------------------- 
*/ 
 
/*! \file List.h 
 *	\brief Template class for a doubly linked list. 
 * 
 *		This file contains a template class for a doubly linked list. 
 */ 
 
#ifndef _RE_LIST_H_
#define _RE_LIST_H_
 
// System includes 
#include  
 
//! Used for abstract iteration position. 
struct __LISTPOSITION { }; 
//! Abstract iteration position. 
typedef __LISTPOSITION* LISTPOSITION; 
 
// Forward declare reList. 
template  
class reList; 
 
//!	A list node used to store pointers to a  object. 
/*! 
 *		reListNode is a list node used to store pointers to a  object, 
 *		and to the next and previous reListNode structs in the list. 
 */ 
template  
struct reListNode 
{ 
private: 
	//! The node element. 
	Type* mpItem; 
 
	//! The next node. 
	reListNode* mpNext; 
 
	//! The previous node. 
	reListNode* mpPrevious; 
 
	friend class reList; 
}; 
 
//!	A template class for a doubly linked list. 
/*! 
 *		reList is a template of a doubly linked list. 
 *		The list stores * pointers. 
 */ 
template  
class reList   
{ 
public: 
	//! Constructor. 
	/*! 
	 *		The constructor initialises data. 
	 * 
	 *	\param bDeleteOn - if true added items will be deleted on removal. 
	 */ 
	reList(bool bDeleteOn = true) 
		{ 
			mpFirst = NULL; 
			mpLast = NULL; 
			miCount = 0; 
			mbDeleteItems = bDeleteOn; 
		}; 
 
	//! Destructor. 
	/*! 
	 *		The destructor cleans up. 
	 */ 
	virtual ~reList(void) 
		{RemoveAll();}; 
 
	//! Add an element to the head of the list. 
	/*! 
	 *	\param pData - a pointer to the element to be added. 
	 *	\return none. 
	 */ 
	void 
	AddHead(Type* pData); 
 
	//! Add an element to the tail of the list. 
	/*! 
	 *	\param pData - a pointer to the element to be added. 
	 *	\return none. 
	 */ 
	void 
	AddTail(Type* pData); 
 
	//! Removes an element from the list. 
	/*! 
	 *		Find an element by pointer reference and remove it from the list. 
	 * 
	 *	\param pData - a pointer to the element to be removed. 
	 *	\return none. 
	 */ 
	void 
	Remove(Type* pData); 
 
	//! Removes an element from the list. 
	/*! 
	 *		Removes an element from the list, specified by Pos, 
	 *		then sets Pos to the LISTPOSITION value of the next 
	 *		entry in the list. 
	 * 
	 *	\param Pos - a list position of the element to be removed. 
	 *	\return none. 
	 */ 
	void 
	RemoveAt(LISTPOSITION& Pos); 
 
	//! Removes an element from the head of the list. 
	/*! 
	 *	\param none. 
	 *	\return none. 
	 */ 
	void 
	RemoveHead(); 
 
	//! Removes an element from the tail of the list. 
	/*! 
	 *	\param none. 
	 *	\return none. 
	 */ 
	void 
	RemoveTail(); 
 
	//! Removes all the elements from the list. 
	/*! 
	 *	\param none. 
	 *	\return none. 
	 */ 
	void 
	RemoveAll(); 
 
	//! Returns the head element of the list (can be null). 
	/*! 
	 *	\param none. 
	 *	\return a pointer to the head element of the list (can be null). 
	 */ 
	Type* 
	GetHead() const; 
 
	//! Returns the tail element of the list (can be null). 
	/*! 
	 *	\param none. 
	 *	\return a pointer to the tail element of the list (can be null). 
	 */ 
	Type* 
	GetTail() const; 
 
	//! Returns the position of the head element of the list. 
	/*! 
	 *	\param none. 
	 *	\return a list position of the head element. 
	 */ 
	const LISTPOSITION 
	GetHeadPosition() const; 
 
	//! Returns the position of the tail element of the list. 
	/*! 
	 *	\param none. 
	 *	\return a list position of the tail element. 
	 */ 
	const LISTPOSITION 
	GetTailPosition() const; 
 
	//! Gets the list element identified by Pos, then Pos is set to next element. 
	/*! 
	 *		Gets the list element identified by Pos, then sets Pos 
	 *		to the LISTPOSITION value of the next entry in the list. 
	 *		You can use GetNext() in a forward iteration loop if you 
	 *		establish the initial position with a call to GetHeadPosition(). 
	 * 
	 *	\param Pos - a list position of element to get, Pos is then set to 
	 *	             the next entry in the list. 
	 *	\return a pointer to the list element. 
	 */ 
	Type* 
	GetNext(LISTPOSITION& Pos) const; 
 
	//! Gets the list element identified by Pos, then Pos is set to previous element. 
	/*! 
	 *		Gets the list element identified by Pos, then sets Pos 
	 *		to the LISTPOSITION value of the previous entry in the list. 
	 *		You can use GetPrev() in a reverse iteration loop if you 
	 *		establish the initial position with a call to GetTailPosition(). 
	 * 
	 *	\param Pos - a list position of element to get, Pos is then set to 
	 *	             the previous entry in the list. 
	 *	\return a pointer to the list element. 
	 */ 
	Type* 
	GetPrev(LISTPOSITION& Pos) const; 
 
	//! Gets the list element identified by Pos. 
	/*! 
	 *	\param Pos - a list position of element to get. 
	 *	\return a pointer to the list element. 
	 */ 
	Type* 
	GetAt(LISTPOSITION& Pos) const; 
 
	//! Returns the number of elements in the list. 
	/*! 
	 *	\param none. 
	 *	\return the number of elements in the list. 
	 */ 
	int 
	GetCount() const 
		{return miCount;}; 
 
	//! Return if the list is empty or not. 
	/*! 
	 *	\param none. 
	 *	\return TRUE if the list is empty, otherwise FALSE. 
	 */ 
	bool 
	IsEmpty() const; 
 
private: 
	//! Copy constructor. 
	/*! 
	 *		The copy constructor is disallowed (ie. private). 
	 */ 
	reList(const reList &); 
 
	//! Assignment operator. 
	/*! 
	 *		The assignment operator is disallowed (ie. private). 
	 */ 
	reList& operator=(const reList &); 
 
	//! The first node in the list. 
	reListNode* mpFirst; 
 
	//! The last node in the list. 
	reListNode* mpLast; 
 
	//! The number of elements in the list. 
	int miCount; 
 
	//! A flag to indicate if items added to the list should be deleted. 
	bool mbDeleteItems; 
}; 
 
 
 
 
template  
void reList::AddHead(Type* pData) 
{ 
	reListNode* pNewNode = new reListNode; 
 
	if (!mpFirst) // First and only item in the list. 
	{ 
		pNewNode->mpNext     = NULL; 
		pNewNode->mpPrevious = NULL; 
 
		mpFirst = pNewNode; 
		mpLast  = pNewNode; 
	} 
	else 
	{ 
		pNewNode->mpPrevious = NULL; 
		pNewNode->mpNext = mpFirst; 
 
		mpFirst->mpPrevious = pNewNode; 
		mpFirst = pNewNode; 
	} 
 
	miCount++; 
 
	pNewNode->mpItem = pData; 
} 
 
 
 
 
template  
void reList::AddTail(Type* pData) 
{ 
	reListNode* pNewNode = new reListNode; 
 
	if (!mpFirst) // First and only item in the list. 
	{ 
		pNewNode->mpNext     = NULL; 
		pNewNode->mpPrevious = NULL; 
 
		mpFirst = pNewNode; 
		mpLast  = pNewNode; 
	} 
	else 
	{ 
		pNewNode->mpPrevious = mpLast; 
		pNewNode->mpNext = NULL; 
 
		mpLast->mpNext = pNewNode; 
		mpLast = pNewNode; 
	} 
 
	miCount++; 
 
	pNewNode->mpItem = pData; 
} 
 
 
 
 
template  
void reList::Remove(Type* pData) 
{ 
	reListNode* pNode = mpFirst; 
	while (pNode) 
	{ 
		if (pData == pNode->mpItem) 
		{ 
			if (mbDeleteItems) 
				delete pNode->mpItem; 
			pNode->mpItem = NULL; 
 
			delete pNode; 
			pNode = NULL; 
 
			miCount--; 
			break; 
		} 
 
		pNode = pNode->mpNext; 
	} 
} 
 
 
 
 
template  
void reList::RemoveAt(LISTPOSITION& Pos) 
{ 
	reListNode* pDeleteNode = (reListNode*)Pos; 
 
	if (pDeleteNode) 
	{ 
		Pos = (LISTPOSITION)pDeleteNode->mpNext; 
 
		if (pDeleteNode == mpFirst) 
			RemoveHead(); 
		else if (pDeleteNode == mpLast) 
			RemoveTail(); 
		else 
		{ 
			if (pDeleteNode->mpPrevious) 
				pDeleteNode->mpPrevious->mpNext = pDeleteNode->mpNext; 
 
			if (pDeleteNode->mpNext) 
				pDeleteNode->mpNext->mpPrevious = pDeleteNode->mpPrevious; 
 
			if (pDeleteNode->mpItem) 
			{ 
				if (mbDeleteItems) 
					delete pDeleteNode->mpItem; 
				pDeleteNode->mpItem = NULL; 
			} 
 
			delete pDeleteNode; 
			pDeleteNode = NULL; 
 
			miCount--; 
		} 
	} 
} 
 
 
 
 
template  
void reList::RemoveHead() 
{ 
	reListNode* pDeleteNode = mpFirst; 
 
	if (pDeleteNode) 
	{ 
		mpFirst = mpFirst->mpNext; 
 
		if (mpFirst) 
			mpFirst->mpPrevious = NULL; 
 
		if (pDeleteNode->mpItem) 
		{ 
			if (mbDeleteItems) 
				delete pDeleteNode->mpItem; 
			pDeleteNode->mpItem = NULL; 
		} 
 
		delete pDeleteNode; 
		pDeleteNode = NULL; 
 
		miCount--; 
	} 
} 
 
 
 
 
template  
void reList::RemoveTail() 
{ 
	reListNode* pDeleteNode = mpLast; 
 
	if (pDeleteNode) 
	{ 
		mpLast = mpLast->mpPrevious; 
 
		if (mpLast) 
			mpLast->mpNext = NULL; 
 
		if (pDeleteNode->mpItem) 
		{ 
			if (mbDeleteItems) 
				delete pDeleteNode->mpItem; 
			pDeleteNode->mpItem = NULL; 
		} 
 
		delete pDeleteNode; 
		pDeleteNode = NULL; 
 
		miCount--; 
	} 
} 
 
 
 
 
template  
void reList::RemoveAll() 
{ 
	while (mpFirst) 
		RemoveHead(); 
} 
 
 
 
 
template  
Type* reList::GetHead() const 
{ 
	if (mpFirst) 
		return mpFirst->mpItem; 
	else 
		return NULL; 
} 
 
 
 
 
template  
Type* reList::GetTail() const 
{ 
	if (mpLast) 
		return mpLast->mpItem; 
	else 
		return NULL; 
} 
 
 
 
 
template  
const LISTPOSITION reList::GetHeadPosition() const 
{ 
	return (LISTPOSITION)mpFirst; 
} 
 
 
 
 
template  
const LISTPOSITION reList::GetTailPosition() const 
{ 
	return (LISTPOSITION)mpLast; 
} 
 
 
 
 
template  
Type* reList::GetNext(LISTPOSITION& Pos) const 
{ 
	reListNode* pNode = (reListNode*)Pos; 
 
	if (!pNode) 
		return NULL; 
 
	Pos = (LISTPOSITION)pNode->mpNext; 
 
	return pNode->mpItem; 
} 
 
 
 
 
template  
Type* reList::GetPrev(LISTPOSITION& Pos) const 
{ 
	reListNode* pNode = (reListNode*)Pos; 
 
	if (!pNode) 
		return NULL; 
 
	Pos = (LISTPOSITION)pNode->mpPrevious; 
 
	return pNode->mpItem; 
} 
 
 
 
 
template  
Type* reList::GetAt(LISTPOSITION& Pos) const 
{ 
	reListNode* pNode = (reListNode*)Pos; 
 
	if (!pNode) 
		return NULL; 
 
	return pNode->mpItem; 
} 
 
 
 
 
template  
bool reList::IsEmpty() const 
{ 
	if (mpFirst) 
		return false; 
	else 
		return true; 
}

#endif // _RE_LIST_H_