00001
00002
00003
00004
00005 #ifndef PRIORITYQUEUE_H
00006 #define PRIORITYQUEUE_H
00007
00008 #include <cstdlib>
00009 #include <cstdio>
00010
00011 namespace EMAN {
00012
00016 template < class ValueT, class KeyT >
00017 class PriorityQueue
00018 {
00019 public:
00021 int queueLength ;
00022
00024 int maxLength ;
00025
00027 ValueT ** valueQueue ;
00028
00030 KeyT * keyQueue ;
00031
00032 public:
00033
00037 PriorityQueue ( int max )
00038 {
00039 this->maxLength = max ;
00040 this->queueLength = 0 ;
00041 this->valueQueue = new ValueT* [ max ] ;
00042 this->keyQueue = new KeyT [ max ] ;
00043
00044 };
00045
00049 ~PriorityQueue ()
00050 {
00051 delete [] keyQueue ;
00052 for ( int i = 0 ; i < queueLength ; i ++ )
00053 {
00054 delete valueQueue [ i ] ;
00055 }
00056 delete [] valueQueue ;
00057 };
00058
00062 int getLength ( )
00063 {
00064 return this->queueLength ;
00065 };
00066
00070 bool isEmpty ( )
00071 {
00072 return ( this->queueLength == 0 ) ;
00073 };
00074
00078 bool isFull ( )
00079 {
00080 return ( this->queueLength == this->maxLength ) ;
00081 };
00082
00086 void add ( ValueT * v, KeyT k )
00087 {
00088 if ( this->isFull() )
00089 {
00090 printf("PRIORITY QUEUE FILLED UP !!! \n");
00091 return ;
00092 }
00093
00094 int ind = queueLength ;
00095 int tind ;
00096 queueLength ++ ;
00097
00098 while ( ind > 0 )
00099 {
00100 tind = ( ind + 1 ) / 2 - 1 ;
00101 if ( k < keyQueue[tind] )
00102 {
00103 keyQueue[ ind ] = keyQueue [ tind ] ;
00104 valueQueue [ ind ] = valueQueue [ tind ] ;
00105 ind = tind ;
00106 }
00107 else
00108 {
00109 break;
00110 }
00111 }
00112
00113 valueQueue[ ind ] = v ;
00114 keyQueue [ ind ] = k ;
00115 };
00116
00120 void remove ( ValueT *& v, KeyT & k )
00121 {
00122 if ( this->isEmpty() )
00123 {
00124 v = NULL ;
00125 k = 0 ;
00126 return ;
00127 }
00128
00129 v = valueQueue[0] ;
00130 k = keyQueue[0] ;
00131 queueLength -- ;
00132
00133 if ( queueLength == 0 )
00134 {
00135 valueQueue[0] = NULL ;
00136 return ;
00137 }
00138
00139 ValueT * vv = valueQueue [ queueLength ] ;
00140 KeyT kk = keyQueue [ queueLength ], lowk ;
00141 int ind = 0, tind, ind2, ind3 ;
00142 while ( 1 )
00143 {
00144 ind2 = 2 * ( ind + 1 ) - 1 ;
00145 ind3 = ind2 + 1 ;
00146 tind = ind ;
00147 lowk = kk ;
00148
00149 if ( ind2 >= queueLength )
00150 {
00151 break ;
00152 }
00153 else
00154 {
00155 if ( keyQueue [ ind2 ] < lowk )
00156 {
00157 tind = ind2 ;
00158 lowk = keyQueue [ ind2 ] ;
00159 }
00160
00161 if ( ind3 < queueLength )
00162 {
00163 if ( keyQueue [ ind3 ] < lowk )
00164 {
00165 tind = ind3 ;
00166 }
00167 }
00168
00169 if ( ind != tind )
00170 {
00171 valueQueue [ ind ] = valueQueue [ tind ] ;
00172 keyQueue [ ind ] = keyQueue [ tind ] ;
00173 ind = tind ;
00174 }
00175 else
00176 {
00177 break ;
00178 }
00179 }
00180 }
00181
00182 valueQueue [ ind ] = vv ;
00183 keyQueue [ ind ] = kk ;
00184 valueQueue [ queueLength ] = NULL ;
00185 keyQueue [ queueLength ] = NULL ;
00186 };
00187
00188 };
00189
00190
00191 }
00192
00193 #endif