pqueue.h
上传用户:szopptop
上传日期:2013-04-23
资源大小:1047k
文件大小:4k
源码类别:

模拟服务器

开发平台:

Visual C++

  1. /*
  2. Priority Queue
  3. Date:
  4. 2002/02/25
  5. Note:
  6. 赛阑 捞侩茄 快急鉴困 钮
  7. Usage:
  8. 荤侩 傈 龋免 窃荐: SetCompareFunction
  9. 荤侩 饶 龋免 窃荐: ClearAll
  10. 府悸: ClearAll -> ResetVector
  11. */
  12. #ifndef __ORZ_DATASTRUCTURE_PRIORITY_QUEUE__
  13. #define __ORZ_DATASTRUCTURE_PRIORITY_QUEUE__
  14. #include "vector.h"
  15. template< class T >
  16. class CPriorityQueue
  17. {
  18. protected:
  19. CVector< T > m_vector;
  20. int m_nCount;
  21. int  (*m_pfnCmp)( void *pArg, T *pFirst, T *pSecond );
  22. void *m_pArgCmpFunc;
  23. public:
  24. CPriorityQueue( int nCapacity, int nIncrease );
  25. virtual ~CPriorityQueue();
  26. void ClearAll( bool bClearData = true, bool bDeleteArray = false );
  27. bool ResetVector();
  28. void SetCompareFunction( int (*pfnCmp)( void *pArg, T *pFirst, T *pSecond ), void *pArg );
  29. virtual bool Enqueue( T *pData );
  30. virtual T *  Dequeue();
  31. virtual T *  DequeueIndex( int nIndex );
  32. virtual int  GetCount();
  33. inline T *& operator[]( int nIndex );
  34. protected:
  35. virtual void UpHeap( int nCount, int nNode );
  36. virtual void DownHeap( int nCount, int nNode );
  37. virtual void Sort();
  38. };
  39. template< class T >
  40. CPriorityQueue< T >::CPriorityQueue( int nCapacity, int nIncrease )
  41. : m_vector( nCapacity, nIncrease ), m_nCount( 1 )
  42. {
  43. m_vector[0] = NULL;
  44. }
  45. template< class T >
  46. CPriorityQueue< T >::~CPriorityQueue()
  47. {
  48. }
  49. template< class T >
  50. void CPriorityQueue< T >::ClearAll( bool bClearData, bool bDeleteArray )
  51. {
  52. m_vector.ClearAll( bClearData, bDeleteArray );
  53. }
  54. template< class T >
  55. bool CPriorityQueue< T >::ResetVector()
  56. {
  57. return m_vector.Create();
  58. }
  59. template< class T >
  60. void CPriorityQueue< T >::SetCompareFunction( int (*pfnCmp)( void *pArg, T *pFirst, T *pSecond ), void *pArg )
  61. {
  62. m_pfnCmp = pfnCmp;
  63. m_pArgCmpFunc = pArg;
  64. }
  65. template< class T >
  66. bool CPriorityQueue< T >::Enqueue( T *pData )
  67. {
  68. if ( m_vector.GetCapacity() <= m_nCount )
  69. {
  70. if ( m_vector.Expand() == false )
  71. return false;
  72. }
  73. m_vector[m_nCount] = pData;
  74. UpHeap( m_nCount, m_nCount++ );
  75. return true;
  76. }
  77. template< class T >
  78. T * CPriorityQueue< T >::Dequeue()
  79. {
  80. if ( GetCount() <= 0 )
  81. return NULL;
  82. T * pData = m_vector[1];
  83. m_vector[1] = m_vector[--m_nCount];
  84. DownHeap( m_nCount, 1 ); // 1 is root index
  85. m_vector[m_nCount] = NULL;
  86. return pData;
  87. }
  88. template< class T >
  89. T * CPriorityQueue< T >::DequeueIndex( int nIndex )
  90. {
  91. if ( GetCount() <= nIndex )
  92. return NULL;
  93. T *pData = m_vector[nIndex + 1];
  94. memmove( &m_vector[nIndex + 1], &m_vector[nIndex + 2], sizeof( T * ) * (m_nCount-- - (nIndex + 1)) );
  95. Sort();
  96. m_vector[m_nCount] = NULL;
  97. return pData;
  98. }
  99. template< class T >
  100. int CPriorityQueue< T >::GetCount()
  101. {
  102. // ignore dummy node
  103. return m_nCount - 1;
  104. }
  105. template< class T >
  106. T *& CPriorityQueue< T >::operator[]( int nIndex )
  107. {
  108. // skip dummy node
  109. return m_vector[nIndex + 1];
  110. }
  111. template< class T >
  112. void CPriorityQueue< T >::UpHeap( int nCount, int nNode )
  113. {
  114. T * pData = m_vector[nNode];
  115. while ( nNode > 1 && // ignore dummy node
  116.     m_pfnCmp( m_pArgCmpFunc, m_vector[nNode >> 1], pData ) < 0 )
  117. {
  118. m_vector[nNode] = m_vector[nNode >> 1];
  119. nNode >>= 1;
  120. }
  121. m_vector[nNode] = pData;
  122. }
  123. template< class T >
  124. void CPriorityQueue< T >::DownHeap( int nCount, int nNode )
  125. {
  126. T * pData = m_vector[nNode];
  127. int nChild;
  128. while ( nNode <= nCount >> 1 )
  129. {
  130. nChild = nNode << 1; // left child
  131. if ( nChild < nCount && m_pfnCmp( m_pArgCmpFunc, m_vector[nChild], m_vector[nChild + 1] ) < 0 )
  132. nChild++; // right child
  133. if ( m_pfnCmp( m_pArgCmpFunc, pData, m_vector[nChild] ) >= 0 )
  134. break;
  135. m_vector[nNode] = m_vector[nChild];
  136. nNode = nChild;
  137. }
  138. m_vector[nNode] = pData;
  139. }
  140. template< class T >
  141. void CPriorityQueue< T >::Sort()
  142. {
  143. int nCount = m_nCount - 1;
  144. for ( int nNode = nCount >> 1; nNode >= 1; nNode-- )
  145. DownHeap( nCount, nNode );
  146. }
  147. #endif