Project에 적용하기 위해서 작성한 Heap을 기반으로한 Priority Queue Class 입니다.
MultiThread-Safe 하긴한데 performance가 따라 줄지는 모르겟습니다.
성능 개선을 위한 부분 있다면 언제든지 코멘트 부탁 드립니다 ㅜㅜ;;;;
딱 보면 아시겠지만, 생각하는 프로그래머에 Code를 그대로 옮겨 놓은 듯 합니다.
^0^ 그럼 고운하루 되세요.
template< class T >
class CPriQueue
{
private:
int m_nCurIndex, m_nMaxsize;
CRITICAL_SECTION m_cs;
T *m_pTemplateArray;
void swap( int i, int j )
{
T t = m_pTemplateArray[i];
m_pTemplateArray[i] = m_pTemplateArray[j];
m_pTemplateArray[j] = t;
}
public:
CPriQueue()
{
m_pTemplateArray = NULL;
InitializeCriticalSection( &m_cs );
}
~CPriQueue()
{
FlushQueue();
delete []m_pTemplateArray;
DeleteCriticalSection( &m_cs );
m_pTemplateArray = NULL;
}
void SetQueueSize( unsigned int QueueSize )
{
if( QueueSize <= 0 )
QueueSize = 1;
m_pTemplateArray = new T[ QueueSize +1 ];
if( m_pTemplateArray )
{
m_nMaxsize = QueueSize;
m_nCurIndex = 0;
}
}
void Push( T t )
{
if( m_nCurIndex >= m_nMaxsize )
{
FlushQueue();
printf("******FULL Queue ******* ");
return;
}
int nParentIndex;
EnterCriticalSection( &m_cs );
m_pTemplateArray[ ++m_nCurIndex ] = t;
if( m_nCurIndex > 1 && m_pTemplateArray[ nParentIndex = m_nCurIndex >> 1 ] > m_pTemplateArray[m_nCurIndex] )
{
for ( int nCurrentIndex = m_nCurIndex;
nCurrentIndex > 1 && m_pTemplateArray[ nParentIndex = nCurrentIndex >> 1 ] > m_pTemplateArray[nCurrentIndex];
nCurrentIndex = nParentIndex )
{
swap( nParentIndex, nCurrentIndex );
}
}
LeaveCriticalSection( &m_cs );
}
T Pop()
{
if ( m_nCurIndex == 0 )
{
return 0;
}
int nChild = 0;
EnterCriticalSection( &m_cs );
T t = m_pTemplateArray[ 1 ];
m_pTemplateArray[ 1 ] = m_pTemplateArray[ m_nCurIndex-- ];
for( int i = 1; ( nChild = i << 1 ) <= m_nCurIndex ; i = nChild )
{
if( nChild + 1 <= m_nCurIndex && m_pTemplateArray[ nChild + 1 ] < m_pTemplateArray[ nChild ] )
{
nChild++;
}
if( m_pTemplateArray[ i ] <= m_pTemplateArray[ nChild ] )
{
break;
}
swap( nChild, i );
}
LeaveCriticalSection( &m_cs);
return t;
}
void FlushQueue()
{
UINT nfreameCount = 0;
T tFrame = NULL;
while( tFrame = Pop() )
{
delete tFrame;
tFrame = NULL;
nfreameCount++;
}
m_nCurIndex = 0;
printf("******Flush Queue ******* :: %d \n", nfreameCount );
}
};
