listtemplates.h

大型多人在线游戏开发,该书光盘上附带的源码

/*
[e-mail]
Copyright (c) 2000, Sean O'Neil
All rights reserved.

Redistribution and use in source and binary forms, with or without
modification, are permitted provided that the following conditions are met:

* Redistributions of source code must retain the above copyright notice,
  this list of conditions and the following disclaimer.
* Redistributions in binary form must reproduce the above copyright notice,
  this list of conditions and the following disclaimer in the documentation
  and/or other materials provided with the distribution.
* Neither the name of this project nor the names of its contributors
  may be used to endorse or promote products derived from this software
  without specific prior written permission.

THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
POSSIBILITY OF SUCH DAMAGE.
*/

#ifndef __ListTemplates_h__
#define __ListTemplates_h__

#include <fstream.h>


template <class NODE, class INDEX> class CArray
{
protected:
	INDEX m_nElements;			// The number of elements in the array
	INDEX m_nLockedElements;	// The number of locked elements in the array
	unsigned char *m_pFlags;	// An array of element status flags
	NODE *m_pBuffer;			// The array of elements

public:
	enum { Locked = 0x80, Dirty = 0x40 };

	// Constructor/destructor methods
	CArray(INDEX nElements=0)
	{
		m_nElements = 0;
		if(nElements)
			Init(nElements);
	}
	~CArray()		{ Cleanup(); }

	// Init and Cleanup methods
	void Init(INDEX nElements)
	{
		Cleanup();
		m_nElements = nElements;
		m_nLockedElements = 0;
		m_pFlags = new unsigned char[m_nElements];
		memset(m_pFlags, 0, m_nElements);
		m_pBuffer = new NODE[m_nElements];
	}
	void Cleanup()
	{
		if(m_nElements)
		{
			delete []m_pBuffer;
			delete m_pFlags;
			m_nElements = 0;
		}
	}

	// Info methods
	INDEX GetElementCount()				{ return m_nElements; }
	INDEX GetElementSize()				{ return sizeof(NODE); }
	INDEX GetArraySize()				{ return GetElementCount() * GetElementSize(); }
	INDEX GetLockedElementCount()		{ return m_nLockedElements; }
	INDEX GetFreeElementCount()			{ return GetElementCount() - GetLockedElementCount(); }

	// Status flag methods
	unsigned char GetFlags(INDEX n)					{ return m_pFlags[n]; }
	void SetFlags(INDEX n, unsigned char nFlags)	{ m_pFlags[n] |= nFlags; }
	void ClearFlags(INDEX n, unsigned char nFlags)	{ m_pFlags[n] &= ~nFlags; }

	// Array manipulation methods
	NODE *GetBuffer()					{ return m_pBuffer; }
	NODE *operator[](INDEX n)			{ return &m_pBuffer[n]; }
};


template <class NODE, class INDEX> class CStackedArray : public CArray<NODE, INDEX>
{
protected:
	INDEX *m_pStack;			// A stack of free element indices

public:
	// Constructor/destructor methods
	CStackedArray(INDEX nElements=0)
	{
		m_nElements = 0;
		if(nElements)
			Init(nElements);
	}
	~CStackedArray()		{ Cleanup(); }

	// Init and Cleanup methods
	void Init(INDEX nElements)
	{
		Cleanup();
		CArray<NODE, INDEX>::Init(nElements);
		m_pStack = new INDEX[m_nElements];
		for(INDEX i=0; i<m_nElements; i++)
			m_pStack[i] = i;
	}
	void Cleanup()
	{
		if(m_nElements)
			delete m_pStack;
		CArray<NODE, INDEX>::Cleanup();
	}

	// Array manipulation methods
	INDEX LockElement()
	{
		INDEX nElement = (INDEX)-1;
		if(m_nLockedElements < m_nElements)
		{
			nElement = m_pStack[m_nLockedElements++];
			m_pFlags[nElement] = Locked;
		}
		return nElement;
	}
	void UnlockElement(INDEX n)
	{
		m_pFlags[n] = 0;
		m_pStack[--m_nLockedElements] = n;
	}

	INDEX GetStackIndex(INDEX n)		{ return m_pStack[n]; }
};

template <class NODE, class INDEX> class CPackedArray : public CArray<NODE, INDEX>
{
protected:
	INDEX m_nLowestUnused;		// The index of the lowest unused element in the array

public:
	// Constructor/destructor methods
	CPackedArray(INDEX nElements=0)
	{
		m_nElements = 0;
		if(nElements)
			Init(nElements);
	}
	~CPackedArray()		{ Cleanup(); }

	// Init and Cleanup methods
	void Init(INDEX nElements)
	{
		Cleanup();
		CArray<NODE, INDEX>::Init(nElements);
		m_nLowestUnused = 0;
	}
	void Cleanup()
	{
	}

	// Array manipulation methods
	INDEX LockElement()
	{
		INDEX nElement = (INDEX)-1;
		if(m_nLowestUnused < m_nElements)
		{
			nElement = m_nLowestUnused++;
			m_pFlags[nElement] |= Locked;
			m_nLockedElements++;
			while(m_nLowestUnused < m_nElements && (m_pFlags[m_nLowestUnused] & Locked))
				m_nLowestUnused++;
		}
		return nElement;
	}
	void UnlockElement(INDEX n)
	{
		m_pFlags[n] &= ~Locked;
		m_nLockedElements--;
		m_nLowestUnused = n < m_nLowestUnused ? n : m_nLowestUnused;
	}
};



/******************************************************************************
* Class: CListNode
*******************************************************************************
* Deriving from this class turns your class into a node that can be used in a 
* doubly-linked list. It was designed to work with CLinkedList (defined below)
* in such a way that objects can insert and remove themselves from the list.
* It is only templatized so it can use pointers of your class's type to keep
* you from having to cast all returned pointers.
Example:
#define CMyObjectList CLinkedList<CMyObject>
class CMyObject : public CListNode<CMyObject> { ... };
******************************************************************************/
template <class A> class CListNode
{
public:
	A *m_pNext;			// Points to next item in the list
	A *m_pPrevious;		// Points to previous item in the list

public:
	// Constructors/destructors
	CListNode()					{ m_pNext = m_pPrevious = NULL; }
	~CListNode()				{ Remove(); }
	static void InitList(CListNode<A> &nHead, CListNode<A> &nTail)
	{
		nHead.m_pNext = (A *)&nTail;
		nTail.m_pPrevious = (A *)&nHead;
	}

	// Members to get the next and previous pointers (must use Insert/Remove members to set them)
	A *GetNext()				{ return m_pNext; }
	A *GetPrevious()			{ return m_pPrevious; }

	// Functions for searching the list, override these functions to use
	DWORD GetID()				{ return 0; }
	const char *GetName()		{ return ""; }
	void Write(ostream &os)		{ os.write((char *)this, sizeof(A)); }
	bool Read(istream &is)
	{
		is.read((char *)this, sizeof(A));
		m_pNext = m_pPrevious = NULL;
		return (!is ? false : true);
	}

	// Members to insert into, remove from, and check status in a list
	bool IsInList()				{ return (m_pNext != NULL && m_pPrevious != NULL); }
	void InsertBefore(A *pNode)
	{
		if(pNode && !IsInList())
		{
			m_pNext = pNode;
			m_pPrevious = pNode->m_pPrevious;
			pNode->m_pPrevious->m_pNext = (A *)this;
			pNode->m_pPrevious = (A *)this;
		}
	}
	void InsertAfter(A *pNode)
	{
		if(pNode && !IsInList())
		{
			m_pPrevious = pNode;
			m_pNext = pNode->m_pNext;
			pNode->m_pNext->m_pPrevious = (A *)this;
			pNode->m_pNext = (A *)this;
		}
	}
	void Remove()
	{
		if(m_pPrevious)
			m_pPrevious->m_pNext = m_pNext;
		if(m_pNext)
			m_pNext->m_pPrevious = m_pPrevious;
		m_pNext = m_pPrevious = NULL;
	}

	// Members to find items in the list by ID, name, or index
	A *FindID(DWORD dwID)
	{
		for(A *pNode = (A *)this; pNode->IsInList(); pNode=pNode->GetNext())
		{
			if(dwID == pNode->GetID())
				return pNode;
		}
		return NULL;
	}
	A *FindName(const char *pszName)
	{
		for(A *pNode = (A *)this; pNode->IsInList(); pNode=pNode->GetNext())
		{
			if(stricmp(pszName, pNode->GetName()) == 0)
				return pNode;
		}
		return NULL;
	}
	A *FindIndex(int nIndex)
	{
		A *pNode = (A *)this;
		for(int i=0; pNode->IsInList() && i<nIndex; i++)
			pNode = pNode->GetNext();
		return pNode->IsInList() ? pNode : NULL;
	}
};

/*******************************************************************************
* Class: CLinkedList
********************************************************************************
* This class implements a doubly-linked list that allows the objects within it
* to insert and remove themselves without access to the actual list (to insert,
* a pointer to an item already in the list is needed). To accomplish this,
* static head and tail nodes must be kept instead of pointers, and no count
* variable can used (because the objects have no way to update them). The head
* and tail nodes point to each other when the list is empty. See CListNode above
* for more information.
Important Note:
The static head and tail nodes mark the end of the list, not NULL. Use
CListNode::IsInList() to see when you've reached the end, like this:
for(CObject *p = list.GetHead(); p->IsInList(); p = p->GetNext()) { ... }
*******************************************************************************/
template <class A> class CLinkedList
{
protected:
	CListNode<A> m_nHead;	// Points to head item
	CListNode<A> m_nTail;	// Points to tail item

public:
	// Constructors/destructors
	CLinkedList()		{ CListNode<A>::InitList(m_nHead, m_nTail); }
	~CLinkedList()		{ RemoveAll(); }

	// Members to get the head and tail items of the list
	A *GetHead()		{ return m_nHead.GetNext(); }
	A *GetTail()		{ return m_nTail.GetPrevious(); }

	// Members to add items to the list
	void AddHead(A *p)					{ p->InsertAfter((A *)&m_nHead); }
	void AddTail(A *p)					{ p->InsertBefore((A *)&m_nTail); }
	void InsertBefore(A *p, A *pNode)	{ p->InsertBefore(pNode); }
	void InsertAfter(A *p, A *pNode)	{ p->InsertAfter(pNode); }

	// Members to remove items from the list
	A *Remove(A *p)		{ p->Remove(); return p; }
	A *RemoveHead()		{ return Remove(GetHead()); }
	A *RemoveTail()		{ return Remove(GetTail()); }
	void RemoveAll()	{ while(GetHead()->IsInList()) delete GetHead(); }

	// Members to get the size of the list
	bool IsEmpty()		{ return !GetHead()->IsInList(); }
	int GetCount()
	{
		register A *pNode = GetHead();
		for(int i=0; pNode->IsInList(); i++)