pqueue.h

真正的传奇源代码

/*
	Priority Queue

	Date:
		2002/02/25

	Note:
		赛阑 捞侩茄 快急鉴困 钮

	Usage:
		荤侩 傈 龋免 窃荐: SetCompareFunction
		荤侩 饶 龋免 窃荐: ClearAll
		府悸: ClearAll -> ResetVector
*/
#ifndef __ORZ_DATASTRUCTURE_PRIORITY_QUEUE__
#define __ORZ_DATASTRUCTURE_PRIORITY_QUEUE__


#include "vector.h"


template< class T >
class CPriorityQueue
{
protected:
	CVector< T >	m_vector;
	int				m_nCount;

	int  (*m_pfnCmp)( void *pArg, T *pFirst, T *pSecond );
	void *m_pArgCmpFunc;

public:
	CPriorityQueue( int nCapacity, int nIncrease );
	virtual ~CPriorityQueue();

	void ClearAll( bool bClearData = true, bool bDeleteArray = false );
	bool ResetVector();

	void SetCompareFunction( int (*pfnCmp)( void *pArg, T *pFirst, T *pSecond ), void *pArg );

	virtual bool Enqueue( T *pData );
	virtual T *  Dequeue();
	virtual T *  DequeueIndex( int nIndex );
	virtual int  GetCount();

	inline	T *& operator[]( int nIndex );

protected:
	virtual void UpHeap( int nCount, int nNode );
	virtual void DownHeap( int nCount, int nNode );
	virtual void Sort();
};


template< class T >
CPriorityQueue< T >::CPriorityQueue( int nCapacity, int nIncrease )
: m_vector( nCapacity, nIncrease ), m_nCount( 1 )
{
	m_vector[0] = NULL;
}


template< class T >
CPriorityQueue< T >::~CPriorityQueue()
{
}


template< class T >
void CPriorityQueue< T >::ClearAll( bool bClearData, bool bDeleteArray )
{
	m_vector.ClearAll( bClearData, bDeleteArray );
}


template< class T >
bool CPriorityQueue< T >::ResetVector()
{
	return m_vector.Create();
}


template< class T >
void CPriorityQueue< T >::SetCompareFunction( int (*pfnCmp)( void *pArg, T *pFirst, T *pSecond ), void *pArg )
{
	m_pfnCmp		= pfnCmp;
	m_pArgCmpFunc	= pArg;
}


template< class T >
bool CPriorityQueue< T >::Enqueue( T *pData )
{
	if ( m_vector.GetCapacity() <= m_nCount )
	{
		if ( m_vector.Expand() == false )
			return false;
	}

	m_vector[m_nCount] = pData;

	UpHeap( m_nCount, m_nCount++ );

	return true;
}


template< class T >
T * CPriorityQueue< T >::Dequeue()
{
	if ( GetCount() <= 0 )
		return NULL;

	T * pData	= m_vector[1];
	m_vector[1]	= m_vector[--m_nCount];

	DownHeap( m_nCount, 1 ); // 1 is root index

	m_vector[m_nCount] = NULL;

	return pData;
}


template< class T >
T * CPriorityQueue< T >::DequeueIndex( int nIndex )
{
	if ( GetCount() <= nIndex )
		return NULL;

	T *pData = m_vector[nIndex + 1];	
	memmove( &m_vector[nIndex + 1], &m_vector[nIndex + 2], sizeof( T * ) * (m_nCount-- - (nIndex + 1)) );

	Sort();

	m_vector[m_nCount] = NULL;

	return pData;
}


template< class T >
int CPriorityQueue< T >::GetCount()
{
	// ignore dummy node
	return m_nCount - 1;
}


template< class T >
T *& CPriorityQueue< T >::operator[]( int nIndex )
{
	// skip dummy node
	return m_vector[nIndex + 1];
}


template< class T >
void CPriorityQueue< T >::UpHeap( int nCount, int nNode )
{
	T * pData = m_vector[nNode];

	while ( nNode > 1 && // ignore dummy node
		    m_pfnCmp( m_pArgCmpFunc, m_vector[nNode >> 1], pData ) < 0 )
	{
		m_vector[nNode] = m_vector[nNode >> 1];
		nNode >>= 1;
	}

	m_vector[nNode] = pData;
}


template< class T >
void CPriorityQueue< T >::DownHeap( int nCount, int nNode )
{
	T * pData = m_vector[nNode];
	int nChild;

	while ( nNode <= nCount >> 1 )
	{
		nChild = nNode << 1; // left child

		if ( nChild < nCount && m_pfnCmp( m_pArgCmpFunc, m_vector[nChild], m_vector[nChild + 1] ) < 0 )
			nChild++; // right child

		if ( m_pfnCmp( m_pArgCmpFunc, pData, m_vector[nChild] ) >= 0 )
			break;

		m_vector[nNode] = m_vector[nChild];
		nNode = nChild;
	}

	m_vector[nNode] = pData;
}


template< class T >
void CPriorityQueue< T >::Sort()
{
	int nCount = m_nCount - 1;

	for ( int nNode = nCount >> 1; nNode >= 1; nNode-- )
		DownHeap( nCount, nNode );
}


#endif