00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033 #ifndef __DYNAMICPRIORITYQUEUE_HPP
00034 #define __DYNAMICPRIORITYQUEUE_HPP
00035 #include <vector>
00036 #include <algorithm>
00037
00038
00039
00040 template < class T >
00041 struct PtrGreater
00042 {
00043 bool operator()( T x, T y ) const { return *y < *x; }
00044 };
00045
00046
00047 template < typename Item >
00048 class DynamicPriorityQueue
00049 {
00050
00051
00052 public:
00053
00054 typedef std::vector< Item > ItemVector;
00055 typedef std::vector< Item* > ItemPtrVector;
00056
00057 typedef typename ItemVector::size_type size_type;
00058 typedef typename ItemVector::difference_type Index;
00059
00060 typedef std::vector< Index > IndexVector;
00061
00062
00063 DynamicPriorityQueue();
00064
00065 inline void move( const Index anIndex );
00066
00067 inline void moveTop();
00068
00069 const Index getTopIndex() const
00070 {
00071 return( getItemIndex( theItemPtrVector.front() ) );
00072 }
00073
00074 const Item& getTopItem() const
00075 {
00076 return *( theItemPtrVector.front() );
00077 }
00078
00079 Item& getTopItem()
00080 {
00081 return *( theItemPtrVector.front() );
00082 }
00083
00084 const Item& getItem( const Index anIndex ) const
00085 {
00086 return theItemVector[ anIndex ];
00087 }
00088
00089 Item& getItem( const Index anIndex )
00090 {
00091 return theItemVector[ anIndex ];
00092 }
00093
00094 void popItem();
00095 const Index pushItem( const Item& anItem )
00096 {
00097 const Index anOldSize( theSize );
00098
00099 ++theSize;
00100
00101 if( getSize() > theItemPtrVector.size() )
00102 {
00103 theItemVector.resize( getSize() );
00104 theItemPtrVector.resize( getSize() );
00105 theIndexVector.resize( getSize() );
00106
00107 theItemVector.push_back( anItem );
00108
00109 for( Index i( 0 ); i < getSize(); ++i )
00110 {
00111 theItemPtrVector[i] = &theItemVector[i];
00112 }
00113
00114 *theItemPtrVector[ anOldSize ] = anItem;
00115
00116 make_heap( theItemPtrVector.begin(), theItemPtrVector.end(), comp );
00117
00118 for( Index i( 0 ); i < getSize(); ++i )
00119 {
00120 theIndexVector[ getItemIndex( theItemPtrVector[i] ) ] = i;
00121 }
00122 }
00123 else
00124 {
00125 *theItemPtrVector[ anOldSize ] = anItem;
00126 if( comp( &anItem, theItemPtrVector[ anOldSize ] ) )
00127 {
00128 moveDown( anOldSize );
00129 }
00130 else
00131 {
00132 moveUp( anOldSize );
00133 }
00134 }
00135
00136 return anOldSize;
00137 }
00138
00139
00140 bool isEmpty() const
00141 {
00142 return ( getSize() == 0 );
00143 }
00144
00145 size_type getSize() const
00146 {
00147 return theSize;
00148 }
00149
00150
00151 void clear();
00152
00153 void moveUp( const Index anIndex )
00154 {
00155 const Index aPosition( theIndexVector[anIndex] );
00156 moveUpPos( aPosition );
00157 }
00158
00159
00160 void moveDown( const Index anIndex )
00161 {
00162 const Index aPosition( theIndexVector[anIndex] );
00163 moveDownPos( aPosition );
00164 }
00165
00166 private:
00167
00168 inline void moveUpPos( const Index aPosition );
00169 inline void moveDownPos( const Index aPosition );
00170
00171
00172
00173
00174
00175
00176
00177 const Index getItemIndex( const Item * const ItemPtr ) const
00178 {
00179 return ItemPtr - &theItemVector.front();
00180 }
00181
00182 private:
00183
00184 ItemVector theItemVector;
00185 ItemPtrVector theItemPtrVector;
00186 IndexVector theIndexVector;
00187
00188 Index theSize;
00189
00190 PtrGreater< const Item* const > comp;
00191
00192 };
00193
00194
00195
00196
00197
00198 template < typename Item >
00199 DynamicPriorityQueue< Item >::DynamicPriorityQueue()
00200 :
00201 theSize( 0 )
00202 {
00203 ;
00204 }
00205
00206
00207 template < typename Item >
00208 void DynamicPriorityQueue< Item >::clear()
00209 {
00210 theItemVector.clear();
00211 theItemPtrVector.clear();
00212 theIndexVector.clear();
00213
00214 theSize = 0;
00215
00216 }
00217
00218
00219 template < typename Item >
00220 void DynamicPriorityQueue< Item >::
00221 move( Index anIndex )
00222 {
00223
00224 const Index aPosition( theIndexVector[anIndex] );
00225
00226 moveDownPos( aPosition );
00227
00228
00229
00230
00231 if( theIndexVector[anIndex] == aPosition )
00232 {
00233 moveUpPos( aPosition );
00234 }
00235 }
00236
00237
00238 template < typename Item >
00239 void DynamicPriorityQueue<Item>::moveUpPos( Index aPosition )
00240 {
00241 Item* const anItem( theItemPtrVector[aPosition] );
00242 Index aPredecessor( ( aPosition - 1 ) / 2 );
00243
00244
00245 Item* aPredItem( theItemPtrVector[aPredecessor] );
00246 if( aPredecessor == aPosition || comp( anItem, aPredItem ) )
00247 {
00248 return;
00249 }
00250
00251
00252 while( 1 )
00253 {
00254 theItemPtrVector[aPosition] = aPredItem;
00255 theIndexVector[ getItemIndex( aPredItem ) ] = aPosition;
00256 aPosition = aPredecessor;
00257
00258 aPredecessor = ( aPredecessor - 1 ) / 2;
00259
00260 aPredItem = theItemPtrVector[aPredecessor];
00261
00262 if( aPredecessor == aPosition || comp( anItem, aPredItem ) )
00263 {
00264 break;
00265 }
00266 }
00267
00268 theItemPtrVector[aPosition] = anItem;
00269 theIndexVector[ getItemIndex( anItem ) ] = aPosition;
00270 }
00271
00272
00273 template < typename Item >
00274 void DynamicPriorityQueue< Item >::moveDownPos( Index aPosition )
00275 {
00276 Item* const anItem( theItemPtrVector[aPosition] );
00277 Index aSuccessor( aPosition * 2 + 1);
00278
00279
00280
00281 if( aSuccessor < getSize() - 1 )
00282 {
00283 if( comp( theItemPtrVector[ aSuccessor ],
00284 theItemPtrVector[ aSuccessor + 1 ] ) )
00285 {
00286 ++aSuccessor;
00287 }
00288 }
00289 else if( aSuccessor >= getSize() )
00290 {
00291 return;
00292 }
00293
00294 Item* aSuccItem( theItemPtrVector[ aSuccessor ] );
00295 if( comp( aSuccItem, anItem ) )
00296 {
00297 return;
00298 }
00299
00300
00301 while( 1 )
00302 {
00303
00304 theItemPtrVector[aPosition] = aSuccItem;
00305 theIndexVector[ getItemIndex( aSuccItem ) ] = aPosition;
00306 aPosition = aSuccessor;
00307
00308
00309 aSuccessor = aSuccessor * 2 + 1;
00310
00311 if( aSuccessor < getSize() - 1 )
00312 {
00313 if( comp( theItemPtrVector[ aSuccessor ],
00314 theItemPtrVector[ aSuccessor + 1 ] ) )
00315 {
00316 ++aSuccessor;
00317 }
00318 }
00319 else if( aSuccessor >= getSize() )
00320 {
00321 break;
00322 }
00323
00324 aSuccItem = theItemPtrVector[ aSuccessor ];
00325
00326
00327 if( comp( aSuccItem, anItem ) )
00328 {
00329 break;
00330 }
00331 }
00332
00333 theItemPtrVector[aPosition] = anItem;
00334 theIndexVector[ getItemIndex( anItem ) ] = aPosition;
00335 }
00336
00337
00338
00339
00340
00341
00342
00343
00344
00345
00346
00347
00348
00349
00350
00351
00352
00353
00354
00355
00356
00357
00358
00359
00360
00361
00362
00363
00364
00365
00366
00367
00368
00369
00370 template < typename Item >
00371 void DynamicPriorityQueue< Item >::popItem()
00372 {
00373 Item* anItem( theItemPtrVector[0] );
00374 --theSize;
00375 theItemPtrVector[0] = theItemPtrVector[getSize()];
00376 theItemPtrVector[getSize()] = anItem;
00377
00378 theIndexVector[ getItemIndex( theItemPtrVector[0] ) ] = 0;
00379
00380 moveDown( 0 );
00381 }
00382
00383 template < typename Item >
00384 void DynamicPriorityQueue< Item >::moveTop()
00385 {
00386 Index aPosition( theIndexVector[ getTopIndex() ] );
00387
00388 moveDownPos( aPosition );
00389 }
00390
00391
00392 #endif // __DYNAMICPRIORITYQUEUE_HPP
00393
00394
00395
00396
00397
00398
00399
00400
00401
00402
00403
00404
00405
00406
00407