listtemplates.h

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

			pNode = pNode->GetNext();
		return i;
	}

	// Members to find items in the list by ID, name, or index
	A *FindID(DWORD dwID, A *pNode=NULL)
	{
		if(!pNode)
			pNode = GetHead();
		return pNode->FindID(dwID);
	}
	A *FindName(const char *pszName, A *pNode=NULL)
	{
		if(!pNode)
			pNode = GetHead();
		return pNode->FindName(pszName);
	}
	A *FindIndex(int nIndex, A *pNode=NULL)
	{
		if(!pNode)
			pNode = GetHead();
		return pNode->FindIndex(nIndex);
	}

	bool Read(istream &is)
	{
		int n;
		is.read((char *)&n, sizeof(int));
		if(!is)
			return false;
		for(int i=0; i<n; i++)
		{
			A *pNode = new A;
			if(!pNode->Read(is))
				return false;
			AddTail(pNode);
		}
		return true;
	}
	void Write(ostream &os)
	{
		int n = GetCount();
		os.write((char *)&n, sizeof(int));
		for(A *pNode=GetHead(); pNode->IsInList(); pNode=pNode->GetNext())
			pNode->Write(os);
	}
};

/******************************************************************************
* Class: CTreeNode
*******************************************************************************
* Deriving from this class turns your class into a node to use in a tree of the
* specified order. It is templatized simply so it can use pointers of your
* class's type, keeping you from havig to cast pointers you get back.
* Example:
* class CMyObject : public CTreeNode<CMyObject, 4> { ... };
******************************************************************************/
template <class A, int nOrder> class CTreeNode
{
protected:
	A *m_pParent;
	A *m_pChild[nOrder];

public:
	CTreeNode()
	{
		m_pParent = NULL;
		for(register int i=0; i<nOrder; i++)
			m_pChild[i] = NULL;
	}
	~CTreeNode()
	{
		for(register int i=0; i<nOrder; i++)
		{
			if(m_pParent && m_pParent->GetChild(i) == this)
				m_pParent->SetChild(i, NULL);
			if(m_pChild[i])
				delete m_pChild[i];
		}
	}

	A *GetParent()				{ return m_pParent; }
	void SetParent(A *p)		{ m_pParent = p; }
	A *GetChild(int n)			{ return m_pChild[n]; }
	void SetChild(int n, A *p)	{ m_pChild[n] = p; }
};


/******************************************************************************
* Class: CAVLTreeNode
*******************************************************************************
* Deriving from this class turns your class into a node to use in an AVL tree.
* It was designed to work with CAVLTree (defined below).
* Example:
* #define CObjectTree CAVLTree<CObject>
* class CObject : public CAVLTreeNode<CObject> { ... };
******************************************************************************/
template <class A> class CAVLTreeNode : public CTreeNode<A, 2>
{
protected:
	short m_nBalance;

protected:
	// Rotates pRoot left or right. Used to balance the tree. Returns true when the new root's parent needs to change its balance.
	// (To visualize what it's doing for either direction, replace nDirection with Left and nOtherDir with Right or vice-versa.)
	static bool RotateOnce(A *pRoot, int nDirection)
	{
		int nOtherDir = (nDirection == Left) ? Right : Left;			// Get the other direction
		A *pParent = pRoot->m_pParent;
		int nSide = (pParent->m_pChild[Left] == pRoot) ? Left : Right;

		A *pNewRoot = pRoot->m_pChild[nOtherDir];						// Move nOtherDir child into root's current position (to move root in nDirection)
		pParent->m_pChild[nSide] = pNewRoot;							// (Make parent point to new root)
		pNewRoot->m_pParent = pParent;									// (Don't forget to change its parent)

		pRoot->m_pChild[nOtherDir] = pNewRoot->m_pChild[nDirection];	// Move new root's nDirection child to old root's nOtherDir
		if(pRoot->m_pChild[nOtherDir])
			pRoot->m_pChild[nOtherDir]->m_pParent = pRoot;				// (Don't forget to change its parent)
		
		pNewRoot->m_pChild[nDirection] = pRoot;							// Move old root down to the nDirection
		pRoot->m_pParent = pNewRoot;									// (Don't forget to change its parent)

		// Update balances and return true if new root's parent's balance has changed
		bool bRetVal = (pNewRoot->m_nBalance == 0) ? false : true;
		pRoot->m_nBalance = -(nDirection ? ++(pNewRoot->m_nBalance) : --(pNewRoot->m_nBalance));
		return bRetVal;
	}
	
	// Rotates pRoot left or right twice (by rotating child in opposite direction first). Used to balance the tree. Returns true when the new root's parent needs to change its balance.
	// (To visualize what it's doing for either direction, replace nDirection with Left and nOtherDir with Right or vice-versa.)
	static bool RotateTwice(A *pRoot, int nDirection)
	{
		int nOtherDir = (nDirection == Left) ? Right : Left;			// Get the other direction
		A *pParent = pRoot->m_pParent;
		int nSide = (pParent->m_pChild[Left] == pRoot) ? Left : Right;

		A *pNode = pRoot->m_pChild[nOtherDir];							// nOtherDir child doesn't move (but it gets a new parent)
		A *pNewRoot = pNode->m_pChild[nDirection];						// Move its nDirection child into root's current position (to move root in nDirection)
		pParent->m_pChild[nSide] = pNewRoot;							// (Make parent point to new root)
		pNewRoot->m_pParent = pParent;									// (Don't forget to change its parent)

		pRoot->m_pChild[nOtherDir] = pNewRoot->m_pChild[nDirection];	// Move new root's nDirection child to old root's nOtherDir
		if(pRoot->m_pChild[nOtherDir])
			pRoot->m_pChild[nOtherDir]->m_pParent = pRoot;				// (Don't forget to change its parent)

		pNode->m_pChild[nDirection] = pNewRoot->m_pChild[nOtherDir];	// Move new root's nOtherDir child to the node that's not moving
		if(pNode->m_pChild[nDirection])
			pNode->m_pChild[nDirection]->m_pParent = pNode;				// (Don't forget to change its parent)

		pNewRoot->m_pChild[nDirection] = pRoot;							// Move old root down to the nDirection
		pRoot->m_pParent = pNewRoot;									// (Don't forget to change its parent)
		pNewRoot->m_pChild[nOtherDir] = pNode;							// Put the node that didn't move under new root
		pNode->m_pParent = pNewRoot;									// (Don't forget to change its parent)

		// Update balances and return true
		pNewRoot->m_pChild[0]->m_nBalance = -max(pNewRoot->m_nBalance, 0);
		pNewRoot->m_pChild[1]->m_nBalance = -min(pNewRoot->m_nBalance, 0);
		pNewRoot->m_nBalance = 0;
		return true;
	}

	// Rebalances a single node. Returns true when the balance of pRoot's parent has been changed.
	static bool ReBalance(A *pRoot) 
	{
		bool bHeightChange = false;
		if(pRoot->m_nBalance < -1)
			bHeightChange = (pRoot->m_pChild[0]->m_nBalance == 1) ? RotateTwice(pRoot, Right) : RotateOnce(pRoot, Right);
		else if(pRoot->m_nBalance > 1)
			bHeightChange = (pRoot->m_pChild[1]->m_nBalance == -1) ? RotateTwice(pRoot, Left) : RotateOnce(pRoot, Left);
		return bHeightChange;
	}

	// Moves a locked node down in the tree down to where it can be safely deleted.
	static void MoveDown(A *pNode)
	{
		// Get pNode's parent and the side that points to pNode
		A *pParent = pNode->m_pParent;
		int nSide = (pParent->m_pChild[Left] == pNode) ? Left : Right;

		// Find the next item in the sort order (right one, then left all the way down)
		A *pSwap = pNode->m_pChild[Right];
		while(pSwap->m_pChild[Left])
			pSwap = pSwap->m_pChild[Left];

		// Swap the parent and right child pointers of the two nodes (must be handled differently if pNode is pSwap's parent)
		A *pTemp = pSwap->m_pChild[Right];
		if(pSwap->m_pParent == pNode)
		{
			pNode->m_pParent = pSwap;
			pSwap->m_pChild[Right] = pNode;
		}
		else
		{
			pNode->m_pParent = pSwap->m_pParent;
			pNode->m_pParent->m_pChild[(pNode->m_pParent->m_pChild[Left] == pSwap) ? Left : Right] = pNode;
			pSwap->m_pChild[Right] = pNode->m_pChild[Right];
			pSwap->m_pChild[Right]->m_pParent = pSwap;
		}
		pNode->m_pChild[Right] = pTemp;
		if(pNode->m_pChild[Right])
			pNode->m_pChild[Right]->m_pParent = pNode;
		pSwap->m_pParent = pParent;
		pParent->m_pChild[nSide] = pSwap;

		// Swap the left child of the two nodes (easy because pNode's left child is never NULL and pSwap's left child is always NULL)
		pSwap->m_pChild[Left] = pNode->m_pChild[Left];
		pSwap->m_pChild[Left]->m_pParent = pSwap;
		pNode->m_pChild[Left] = NULL;

		// Swap the balance factors of the two nodes
		short nTemp = pNode->m_nBalance;
		pNode->m_nBalance = pSwap->m_nBalance;
		pSwap->m_nBalance = nTemp;
	}

public:
	enum { Left, Right };
	CAVLTreeNode() : CTreeNode<A, 2>()	{ m_nBalance = 0; }
	bool IsInTree()						{ return (m_pParent != NULL); }
	int GetBalance()					{ return m_nBalance; }

	// Inserts the current node into an AVL tree which has a root of pRoot
	// pRoot is actually a placeholder node for the root, the tree actually starts in its left subtree
	// Returns true for success, false for failure
	bool Insert(A *pRoot)
	{
		A *pParent = pRoot;
		A *pNode = pRoot->m_pChild[Left];
		int nCompare = -1;
		while(pNode)
		{
			nCompare = pNode->Compare((A *)this);
			if(!nCompare)
				return false;
			pParent = pNode;
			pNode = pNode->m_pChild[(nCompare > 0) ? Right : Left];
		}
		pNode = (A *)this;
		pNode->m_pParent = pParent;
		pParent->m_pChild[(nCompare > 0) ? Right : Left] = pNode;

		while(pParent->IsInTree())
		{
			pNode = pParent;
			pParent = pNode->m_pParent;
			pNode->m_nBalance += nCompare;
			nCompare = (pParent->m_pChild[Left] == pNode) ? -1 : 1;
			if(!pNode->m_nBalance || ReBalance(pNode))
				break;
		}
		return true;
	}

	// Removes the current node from an AVL tree
	// Returns true for success, false for failure
	bool Remove()
	{
		if(m_pChild[Left] && m_pChild[Right])
			MoveDown((A *)this);

		int nDirection = (m_pChild[Left] != NULL) ? Left : Right;
		A *pParent = m_pParent;
		A *pNode = m_pChild[nDirection];
		m_pParent = NULL;
		m_pChild[nDirection] = NULL;
		int nCompare = (pParent->m_pChild[Left] == (A *)this) ? -1 : 1;
		pParent->m_pChild[(nCompare > 0) ? Right : Left] = pNode;
		if(pNode)
			pNode->m_pParent = pParent;

		while(pParent->IsInTree())
		{
			pNode = pParent;
			pParent = pNode->m_pParent;
			pNode->m_nBalance -= nCompare;
			nCompare = (pParent->m_pChild[Left] == pNode) ? -1 : 1;
			if(pNode->m_nBalance && !ReBalance(pNode))
				break;
		}
		return true;
	}
};


/*******************************************************************************
* Class: CAVLTree
********************************************************************************
* This class implements an AVL tree.
*******************************************************************************/
template <class A, class KeyType> class CAVLTree
{
protected:
	CAVLTreeNode<A> m_nRoot;
	int m_nCount;

	void RecursiveCount(A *pNode)
	{
		if(!pNode)
			return;
		m_nCount++;
		RecursiveCount(pNode->GetChild(0));
		RecursiveCount(pNode->GetChild(1));
	}

public:
	CAVLTree()				{ m_nCount = 0; }
	bool IsEmpty()			{ return (GetRoot() == NULL); }
	A *GetRoot()			{ return m_nRoot.GetChild(0); }
	bool Insert(A *pNode)	{ return pNode->Insert((A *)&m_nRoot); }
	bool Remove(A *pNode)	{ return pNode->Remove(); }

	int GetCount()
	{
		m_nCount = 0;
		RecursiveCount(GetRoot());
		return m_nCount;
	}
	int GetMaxDepth()
	{
		A *pNode = GetRoot();
		for(int nDepth=0; pNode; nDepth++)
			pNode = pNode->GetChild(pNode->GetBalance() <= 0 ? 0 : 1);
		return nDepth;
	}

	A *FindKey(KeyType tKey)
	{
		int nCompare;
		A *pNode = GetRoot();
		while(pNode && (nCompare = pNode->Compare(tKey)) != 0)
			pNode = (nCompare > 0) ? pNode->GetChild(1) : pNode->GetChild(0);
		return pNode;
	}
	A *Remove(KeyType tKey)
	{
		A *pNode = FindKey(tKey);
		if(pNode)
			pNode->Remove();
		return pNode;
	}
};

#endif	// __ListTemplates_h__