www.pudn.com > GameEngine_src.rar > CPriorityQueue.h

#ifndef CPriorityQueue_h 
#define CPriorityQueue_h 
 
#include  
#include  
 
 
 
///////////////////////////////////////////////////////////////////// 
// 
///////////////////////////////////////////////////////////////////// 
template 
class CPriorityQueue 
{ 
public: 
	CPriorityQueue(); 
	CPriorityQueue( int size ); 
	~CPriorityQueue(); 
 
	bool Init( int size ); 
	void Free(); 
 
	void Clear(); 
 
	bool Push( const T &t ); 
	bool Pop( T &t ); 
 
	T *GetPointer() { return m_queue; } 
	int GetLength() { return m_size + 1; } 
private: 
	int GetFather( int i ) { return (i - 1) >> 1; } 
	int GetSon1( int i ) { return (i << 1) + 1; } 
	int GetSon2( int i ) { return (i << 1) + 2; } 
 
private: 
	T	*m_queue; 
	int  m_max_size; 
	int  m_size; 
}; 
 
const int PQ_DEFAULT_SIZE = 128; 
 
///////////////////////////////////////////////////////////////////// 
// 
///////////////////////////////////////////////////////////////////// 
template 
CPriorityQueue::CPriorityQueue() 
{ 
	m_queue = NULL; 
	m_size = -1; 
	m_max_size = 0; 
} 
 
 
///////////////////////////////////////////////////////////////////// 
// 
///////////////////////////////////////////////////////////////////// 
template 
CPriorityQueue::CPriorityQueue( int size ) 
{ 
	m_queue = NULL; 
	m_size = -1; 
	m_max_size = 0; 
 
	Init( size ); 
} 
 
 
///////////////////////////////////////////////////////////////////// 
// 
///////////////////////////////////////////////////////////////////// 
template 
CPriorityQueue::~CPriorityQueue() 
{ 
	Free(); 
} 
 
 
///////////////////////////////////////////////////////////////////// 
// 
///////////////////////////////////////////////////////////////////// 
template 
bool CPriorityQueue::Init( int size ) 
{ 
	if ( size < 4 ) 
		size = PQ_DEFAULT_SIZE; 
 
	m_queue = (T *)malloc( size * sizeof(T) ); 
	if ( m_queue == NULL ) 
		return false; 
 
	m_max_size = size; 
	return true; 
} 
 
 
///////////////////////////////////////////////////////////////////// 
// 
///////////////////////////////////////////////////////////////////// 
template 
void CPriorityQueue::Clear() 
{ 
	for ( int i = 0; i < m_size; ++i ) 
	{ 
		m_queue[i].~T(); 
	} 
	m_size = -1; 
} 
 
///////////////////////////////////////////////////////////////////// 
// 
///////////////////////////////////////////////////////////////////// 
template 
void CPriorityQueue::Free() 
{ 
	Clear(); 
	free( m_queue ); 
	m_queue = NULL; 
	m_size = -1; 
	m_max_size = 0; 
} 
 
 
///////////////////////////////////////////////////////////////////// 
// 
///////////////////////////////////////////////////////////////////// 
template 
bool CPriorityQueue::Push( const T &t ) 
{ 
	if ( m_size + 1 < m_max_size ) 
	{ 
		++m_size; 
		new (&m_queue[m_size]) T; 
		m_queue[m_size] = t; 
 
		int index = m_size; 
		int father = GetFather( index ); 
 
		while( father >= 0 ) 
		{ 
			if ( m_queue[index] < m_queue[father] ) 
			{ 
				T temp = m_queue[index]; 
				m_queue[index] = m_queue[father]; 
				m_queue[father]= temp; 
 
				index = father; 
				father= GetFather( index ); 
			} 
			else 
				break; 
		} 
		return true; 
	} 
 
	return false; 
} 
 
///////////////////////////////////////////////////////////////////// 
// 
///////////////////////////////////////////////////////////////////// 
template 
bool CPriorityQueue::Pop( T &t ) 
{ 
	if ( m_size >= 0 ) 
	{ 
		t = m_queue[0]; 
		 
		m_queue[0] = m_queue[m_size]; 
		m_queue[m_size].~T(); 
 
		int index = 0; 
		int son1 = GetSon1( 0 ); 
		int son2 = GetSon2( 0 ); 
 
		while( son1 < m_size && son2 < m_size ) 
		{ 
			int son = ( m_queue[son2] < m_queue[son1] ? son2 : son1 ); 
 
			if ( m_queue[son] < m_queue[index] ) 
			{ 
				T temp = m_queue[index]; 
				m_queue[index] = m_queue[son]; 
				m_queue[son] = temp; 
 
				index = son; 
				son1 = GetSon1( index ); 
				son2 = GetSon2( index ); 
			} 
			else 
				break; 
	 
		} 
 
		--m_size; 
		return true; 
	} 
 
	return false; 
} 
 
 
///////////////////////////////////////////////////////////////////// 
// 
///////////////////////////////////////////////////////////////////// 
template 
class CMaxHeap 
{ 
public: 
	CMaxHeap(); 
	CMaxHeap( int size ); 
	~CMaxHeap(); 
 
	bool Init( int size ); 
	void Free(); 
 
	void Clear(); 
 
	bool Push( const T &t ); 
	bool Pop( T &t ); 
 
	T *GetPointer() { return m_queue; } 
	int GetLength() { return m_size + 1; } 
private: 
	int GetFather( int i ) { return (i - 1) >> 1; } 
	int GetSon1( int i ) { return (i << 1) + 1; } 
	int GetSon2( int i ) { return (i << 1) + 2; } 
 
private: 
	T	*m_queue; 
	int  m_max_size; 
	int  m_size; 
}; 
 
 
 
///////////////////////////////////////////////////////////////////// 
// 
///////////////////////////////////////////////////////////////////// 
template 
CMaxHeap::CMaxHeap() 
{ 
	m_queue = NULL; 
	m_size = -1; 
	m_max_size = 0; 
} 
 
 
///////////////////////////////////////////////////////////////////// 
// 
///////////////////////////////////////////////////////////////////// 
template 
CMaxHeap::CMaxHeap( int size ) 
{ 
	m_queue = NULL; 
	m_size = -1; 
	m_max_size = 0; 
 
	Init( size ); 
} 
 
 
///////////////////////////////////////////////////////////////////// 
// 
///////////////////////////////////////////////////////////////////// 
template 
CMaxHeap::~CMaxHeap() 
{ 
	Free(); 
} 
 
 
///////////////////////////////////////////////////////////////////// 
// 
///////////////////////////////////////////////////////////////////// 
template 
bool CMaxHeap::Init( int size ) 
{ 
	if ( size < 4 ) 
		size = PQ_DEFAULT_SIZE; 
 
	m_queue = (T *)malloc( size * sizeof(T) ); 
	if ( m_queue == NULL ) 
		return false; 
 
	m_max_size = size; 
	return true; 
} 
 
 
///////////////////////////////////////////////////////////////////// 
// 
///////////////////////////////////////////////////////////////////// 
template 
void CMaxHeap::Clear() 
{ 
	for ( int i = 0; i < m_size; ++i ) 
	{ 
		m_queue[i].~T(); 
	} 
 
	m_size = -1; 
} 
 
///////////////////////////////////////////////////////////////////// 
// 
///////////////////////////////////////////////////////////////////// 
template 
void CMaxHeap::Free() 
{ 
	Clear(); 
	free( m_queue ); 
	m_queue = NULL; 
	m_size = -1; 
	m_max_size = 0; 
} 
 
 
///////////////////////////////////////////////////////////////////// 
// 
///////////////////////////////////////////////////////////////////// 
template 
bool CMaxHeap::Push( const T &t ) 
{ 
	if ( m_size + 1 < m_max_size ) 
	{ 
		++m_size; 
		new (&m_queue[m_size]) T; 
		m_queue[m_size] = t; 
 
		int index = m_size; 
		int father = GetFather( index ); 
 
		while( father >= 0 ) 
		{ 
			if ( Comp::less( m_queue[index] , m_queue[father] ) ) 
			{ 
				T temp = m_queue[index]; 
				m_queue[index] = m_queue[father]; 
				m_queue[father]= temp; 
 
				index = father; 
				father= GetFather( index ); 
			} 
			else 
				break; 
		} 
		return true; 
	} 
 
	return false; 
} 
 
///////////////////////////////////////////////////////////////////// 
// 
///////////////////////////////////////////////////////////////////// 
template 
bool CMaxHeap::Pop( T &t ) 
{ 
	if ( m_size >= 0 ) 
	{ 
		t = m_queue[0]; 
		 
		m_queue[0] = m_queue[m_size]; 
		m_queue[m_size].~T(); 
 
		int index = 0; 
		int son1 = GetSon1( 0 ); 
		int son2 = GetSon2( 0 ); 
 
		while( son1 < m_size && son2 < m_size ) 
		{ 
			int son = ( Comp::less( m_queue[son2] , m_queue[son1] ) ? son2 : son1 ); 
 
			if ( Comp::less( m_queue[son] , m_queue[index] ) ) 
			{ 
				T temp = m_queue[index]; 
				m_queue[index] = m_queue[son]; 
				m_queue[son] = temp; 
 
				index = son; 
				son1 = GetSon1( index ); 
				son2 = GetSon2( index ); 
			} 
			else 
				break; 
	 
		} 
 
		--m_size; 
		return true; 
	} 
 
	return false; 
} 
#endif