Return to list.ctt CVS log

Up to [WindowsNT SDKs] / mstools / mfc / samples / templdef

Microsoft Windows NT Build 297 06-28-1992

/////////////////////////////////////////////////////////////////////////////
// class CList<TYPE, ARG_TYPE, IS_SERIAL, HAS_CREATE> - a list containing 'TYPE' elements
// passed in parameters as ARG_TYPE
//
// This is a part of the Microsoft Foundation Classes C++ library.
// Copyright (C) 1992 Microsoft Corporation
// All rights reserved.
//
// This source code is only intended as a supplement to the
// Microsoft Foundation Classes Reference and Microsoft
// QuickHelp documentation provided with the library.
// See these sources for detailed information regarding the
// Microsoft Foundation Classes product.
/////////////////////////////////////////////////////////////////////////////

//$DECLARE_TEMPLATE

/////////////////////////////////////////////////////////////////////////////

template <class TYPE, class ARG_TYPE, int IS_SERIAL, int HAS_CREATE>
class CList : public CObject
{
#if IS_SERIAL
	DECLARE_SERIAL(CList)
#else
	DECLARE_DYNAMIC(CList)
#endif //!IS_SERIAL

protected:
	struct CNode
	{
		CNode*  pNext;
		CNode*  pPrev;
		TYPE    data;
	};
public:

// Construction
	CList(int nBlockSize=10);

// Attributes (head and tail)
	// count of elements
	int     GetCount() const
				{ return m_nCount; }
	BOOL    IsEmpty() const
				{ return m_nCount == 0; }

	// peek at head or tail
	TYPE&   GetHead()
				{ ASSERT(m_pNodeHead != NULL);
					return m_pNodeHead->data; }
	TYPE    GetHead() const
				{ ASSERT(m_pNodeHead != NULL);
					return m_pNodeHead->data; }
	TYPE&   GetTail()
				{ ASSERT(m_pNodeTail != NULL);
					return m_pNodeTail->data; }
	TYPE    GetTail() const
				{ ASSERT(m_pNodeTail != NULL);
					return m_pNodeTail->data; }

// 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
				{ return (POSITION) m_pNodeHead; }
	POSITION GetTailPosition() const
				{ return (POSITION) m_pNodeTail; }
	TYPE&   GetNext(POSITION& rPosition) // return *Position++
				{ CNode* pNode = (CNode*) rPosition;
					ASSERT(pNode != NULL);
					rPosition = (POSITION) pNode->pNext;
					return pNode->data; }
	TYPE    GetNext(POSITION& rPosition) const // return *Position++
				{ CNode* pNode = (CNode*) rPosition;
					ASSERT(pNode != NULL);
					rPosition = (POSITION) pNode->pNext;
					return pNode->data; }
	TYPE&   GetPrev(POSITION& rPosition) // return *Position--
				{ CNode* pNode = (CNode*) rPosition;
					ASSERT(pNode != NULL);
					rPosition = (POSITION) pNode->pPrev;
					return pNode->data; }
	TYPE    GetPrev(POSITION& rPosition) const // return *Position--
				{ CNode* pNode = (CNode*) rPosition;
					ASSERT(pNode != NULL);
					rPosition = (POSITION) pNode->pPrev;
					return pNode->data; }

	// getting/modifying an element at a given position
	TYPE&   GetAt(POSITION position)
				{ CNode* pNode = (CNode*) position;
					ASSERT(pNode != NULL);
					return pNode->data; }
	TYPE    GetAt(POSITION position) const
				{ CNode* pNode = (CNode*) position;
					ASSERT(pNode != NULL);
					return pNode->data; }
	void    SetAt(POSITION pos, ARG_TYPE newElement)
				{ CNode* pNode = (CNode*) pos;
					ASSERT(pNode != NULL);
					pNode->data = 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;
	CNode*  m_pNodeFree;
	struct CPlex* m_pBlocks;
	int     m_nBlockSize;

	CNode*  NewNode(CNode*, CNode*);
	void    FreeNode(CNode*);

public:
	~CList();
#if IS_SERIAL
	void    Serialize(CArchive&);
#endif //IS_SERIAL
#ifdef _DEBUG
	void    Dump(CDumpContext&) const;
	void    AssertValid() const;
#endif
};

//$IMPLEMENT_TEMPLATE

/////////////////////////////////////////////////////////////////////////////
//
// Implementation of List of TYPEs
//
/////////////////////////////////////////////////////////////////////////////

#include "afxcoll.h"
#pragma hdrstop

#include "plex.h"

#ifdef AFX_COLL_SEG
#pragma code_seg(AFX_COLL_SEG)
#endif

#if IS_SERIAL
IMPLEMENT_SERIAL(CList, CObject, 0);
#else
IMPLEMENT_DYNAMIC(CList, CObject);
#endif //!IS_SERIAL

#ifdef _DEBUG
#undef THIS_FILE
static char BASED_CODE THIS_FILE[] = __FILE__;
#endif

#if HAS_CREATE
#include "elements.h"       // used for special creation
#endif

/////////////////////////////////////////////////////////////////////////////

template <class TYPE, class ARG_TYPE, int IS_SERIAL, int HAS_CREATE>
CList<TYPE, ARG_TYPE, IS_SERIAL, HAS_CREATE>::CList(int nBlockSize)
{
	ASSERT(nBlockSize > 0);

	m_nCount = 0;
	m_pNodeHead = m_pNodeTail = m_pNodeFree = NULL;
	m_pBlocks = NULL;
	m_nBlockSize = nBlockSize;
}

template <class TYPE, class ARG_TYPE, int IS_SERIAL, int HAS_CREATE>
void CList<TYPE, ARG_TYPE, IS_SERIAL, HAS_CREATE>::RemoveAll()
{
	ASSERT_VALID(this);

	// destroy elements
#if HAS_CREATE
	register CNode* pNode;
	for (pNode = m_pNodeHead; pNode != NULL; pNode = pNode->pNext)
		DestructElement(&pNode->data);
#endif

	m_nCount = 0;
	m_pNodeHead = m_pNodeTail = m_pNodeFree = NULL;
	m_pBlocks->FreeDataChain();
	m_pBlocks = NULL;
}

template <class TYPE, class ARG_TYPE, int IS_SERIAL, int HAS_CREATE>
CList<TYPE, ARG_TYPE, IS_SERIAL, HAS_CREATE>::~CList()
{
	RemoveAll();
	ASSERT(m_nCount == 0);
}

/////////////////////////////////////////////////////////////////////////////
// Node helpers
/*
 * Implementation note: CNode's are stored in CPlex blocks and
 *  chained together. Free blocks are maintained in a singly linked list
 *  using the 'pNext' member of CNode with 'm_pNodeFree' as the head.
 *  Used blocks are maintained in a doubly linked list using both 'pNext'
 *  and 'pPrev' as links and 'm_pNodeHead' and 'm_pNodeTail'
 *   as the head/tail.
 *
 * We never free a CPlex block unless the List is destroyed or RemoveAll()
 *  is used - so the total number of CPlex blocks may grow large depending
 *  on the maximum past size of the list.
 */

template <class TYPE, class ARG_TYPE, int IS_SERIAL, int HAS_CREATE>
CList<TYPE, ARG_TYPE, IS_SERIAL, HAS_CREATE>::CNode*
CList<TYPE, ARG_TYPE, IS_SERIAL, HAS_CREATE>::NewNode(CList::CNode* pPrev, CList::CNode* pNext)
{
	if (m_pNodeFree == NULL)
	{
		// add another block
		CPlex* pNewBlock = CPlex::Create(m_pBlocks, m_nBlockSize,
				 sizeof(CNode));

		// chain them into free list
		CNode* pNode = (CNode*) pNewBlock->data();
		// free in reverse order to make it easier to debug
		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

	register CList::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

#if HAS_CREATE
	ConstructElement(&pNode->data);
#else
	memset(&pNode->data, 0, sizeof(TYPE));          // zero fill
#endif
	return pNode;
}

template <class TYPE, class ARG_TYPE, int IS_SERIAL, int HAS_CREATE>
void CList<TYPE, ARG_TYPE, IS_SERIAL, HAS_CREATE>::FreeNode(CList::CNode* pNode)
{
#if HAS_CREATE
	DestructElement(&pNode->data);
#endif
	pNode->pNext = m_pNodeFree;
	m_pNodeFree = pNode;
	m_nCount--;
	ASSERT(m_nCount >= 0);      // make sure we don't underflow
}

/////////////////////////////////////////////////////////////////////////////

template <class TYPE, class ARG_TYPE, int IS_SERIAL, int HAS_CREATE>
POSITION CList<TYPE, ARG_TYPE, IS_SERIAL, HAS_CREATE>::AddHead(ARG_TYPE newElement)
{
	ASSERT_VALID(this);

	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;
}

template <class TYPE, class ARG_TYPE, int IS_SERIAL, int HAS_CREATE>
POSITION CList<TYPE, ARG_TYPE, IS_SERIAL, HAS_CREATE>::AddTail(ARG_TYPE newElement)
{
	ASSERT_VALID(this);

	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;
}

template <class TYPE, class ARG_TYPE, int IS_SERIAL, int HAS_CREATE>
void CList<TYPE, ARG_TYPE, IS_SERIAL, HAS_CREATE>::AddHead(CList* pNewList)
{
	ASSERT_VALID(this);

	ASSERT(pNewList != NULL);
	ASSERT(pNewList->IsKindOf(RUNTIME_CLASS(CList)));
	ASSERT_VALID(pNewList);

	// add a list of same elements to head (maintain order)
	POSITION pos = pNewList->GetTailPosition();
	while (pos != NULL)
		AddHead(pNewList->GetPrev(pos));
}

template <class TYPE, class ARG_TYPE, int IS_SERIAL, int HAS_CREATE>
void CList<TYPE, ARG_TYPE, IS_SERIAL, HAS_CREATE>::AddTail(CList* pNewList)
{
	ASSERT_VALID(this);
	ASSERT(pNewList != NULL);
	ASSERT(pNewList->IsKindOf(RUNTIME_CLASS(CList)));
	ASSERT_VALID(pNewList);

	// add a list of same elements
	POSITION pos = pNewList->GetHeadPosition();
	while (pos)
		AddTail(pNewList->GetNext(pos));
}

template <class TYPE, class ARG_TYPE, int IS_SERIAL, int HAS_CREATE>
TYPE CList<TYPE, ARG_TYPE, IS_SERIAL, HAS_CREATE>::RemoveHead()
{
	ASSERT_VALID(this);
	ASSERT(m_pNodeHead != NULL);    // don't call on empty list !!!

	CNode* pOldNode = m_pNodeHead;
	ASSERT(pOldNode != NULL);
	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 <class TYPE, class ARG_TYPE, int IS_SERIAL, int HAS_CREATE>
TYPE CList<TYPE, class ARG_TYPE, int IS_SERIAL, int HAS_CREATE>::RemoveTail()
{
	ASSERT_VALID(this);
	ASSERT(m_pNodeTail != NULL);    // don't call on empty list !!!

	CNode* pOldNode = m_pNodeTail;
	ASSERT(pOldNode != NULL);
	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 <class TYPE, class ARG_TYPE, int IS_SERIAL, int HAS_CREATE>
POSITION CList<TYPE>::InsertBefore(POSITION position, ARG_TYPE newElement)
{
	ASSERT_VALID(this);

	if (position == NULL)
		return AddHead(newElement); // insert before nothing -> head of the list

	// Insert it before position
	CNode* pOldNode = (CNode*) position;
	CNode* pNewNode = NewNode(pOldNode->pPrev, pOldNode);
	pNewNode->data = newElement;

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

template <class TYPE, class ARG_TYPE, int IS_SERIAL, int HAS_CREATE>
POSITION CList<TYPE, ARG_TYPE, IS_SERIAL, HAS_CREATE>::InsertAfter(POSITION position, ARG_TYPE newElement)
{
	ASSERT_VALID(this);

	if (position == NULL)
		return AddTail(newElement); // insert after nothing -> tail of the list

	// Insert it before position
	CNode* pOldNode = (CNode*) position;
	CNode* pNewNode = NewNode(pOldNode, pOldNode->pNext);
	pNewNode->data = newElement;

	if (pOldNode->pNext != NULL)
	{
		pOldNode->pNext->pPrev = pNewNode;
	}
	else
	{
		ASSERT(pOldNode == m_pNodeTail);
		m_pNodeTail = pNewNode;
	}
	pOldNode->pNext = pNewNode;
	return (POSITION) pNewNode;
}

template <class TYPE, class ARG_TYPE, int IS_SERIAL, int HAS_CREATE>
void CList<TYPE, ARG_TYPE, IS_SERIAL, HAS_CREATE>::RemoveAt(POSITION position)
{
	ASSERT_VALID(this);
	ASSERT(position != NULL);

	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);
}


/////////////////////////////////////////////////////////////////////////////
// slow operations

template <class TYPE, class ARG_TYPE, int IS_SERIAL, int HAS_CREATE>
POSITION CList<TYPE, ARG_TYPE, IS_SERIAL, HAS_CREATE>::FindIndex(int nIndex) const
{
	ASSERT_VALID(this);
	ASSERT(nIndex >= 0);

	if (nIndex >= m_nCount)
		return NULL;        // went too far

	register CNode* pNode = m_pNodeHead;
	while (nIndex--)
		pNode = pNode->pNext;
	return (POSITION) pNode;
}

template <class TYPE, class ARG_TYPE, int IS_SERIAL, int HAS_CREATE>
POSITION CList<TYPE, ARG_TYPE, IS_SERIAL, HAS_CREATE>::Find(ARG_TYPE searchValue, POSITION startAfter) const
{
	ASSERT_VALID(this);

	register 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;
}

/////////////////////////////////////////////////////////////////////////////
// Serialization

#if IS_SERIAL
template <class TYPE, class ARG_TYPE, int IS_SERIAL, int HAS_CREATE>
void CList<TYPE, ARG_TYPE, IS_SERIAL, HAS_CREATE>::Serialize(CArchive& ar)
{
	ASSERT_VALID(this);

	CObject::Serialize(ar);

	if (ar.IsStoring())
	{
		ar << (WORD) m_nCount;
		for (CNode* pNode = m_pNodeHead; pNode != NULL;
		  pNode = pNode->pNext)
			ar << pNode->data;
	}
	else
	{
		WORD nNewCount;
		ar >> nNewCount;
		while (nNewCount--)
		{
			TYPE newData;
			ar >> newData;
			AddTail(newData);
		}
	}
}
#endif //IS_SERIAL

/////////////////////////////////////////////////////////////////////////////
// Diagnostics

#ifdef _DEBUG
template <class TYPE, class ARG_TYPE, int IS_SERIAL, int HAS_CREATE>
void CList<TYPE, ARG_TYPE, IS_SERIAL, HAS_CREATE>::Dump(CDumpContext& dc) const
{
	ASSERT_VALID(this);

#define MAKESTRING(x) #x
	dc << "a " MAKESTRING(CList) " with " << m_nCount << " elements";
#undef MAKESTRING
	if (dc.GetDepth() > 0)
	{
		POSITION pos = GetHeadPosition();
		dc << "\n";

		while (pos != NULL)
			dc << "\n\t" << GetNext(pos);
	}
}

template <class TYPE, class ARG_TYPE, int IS_SERIAL, int HAS_CREATE>
void CList<TYPE, ARG_TYPE, IS_SERIAL, HAS_CREATE>::AssertValid() const
{
	CObject::AssertValid();

	if (m_nCount == 0)
	{
		// empty list
		ASSERT(m_pNodeHead == NULL);
		ASSERT(m_pNodeTail == NULL);
	}
	else
	{
		// non-empty list
		ASSERT(m_pNodeHead != NULL);
		ASSERT(m_pNodeTail != NULL);
	}
}
#endif //_DEBUG

/////////////////////////////////////////////////////////////////////////////

This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.