DynamicPriorityQueue.hpp

00001 //::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
00002 //
00003 //        This file is part of E-Cell Simulation Environment package
00004 //
00005 //                Copyright (C) 1996-2002 Keio University
00006 //                Copyright (C) 2005 The Molecular Sciences Institute
00007 //
00008 //::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
00009 //
00010 //
00011 // E-Cell is free software; you can redistribute it and/or
00012 // modify it under the terms of the GNU General Public
00013 // License as published by the Free Software Foundation; either
00014 // version 2 of the License, or (at your option) any later version.
00015 // 
00016 // E-Cell is distributed in the hope that it will be useful,
00017 // but WITHOUT ANY WARRANTY; without even the implied warranty of
00018 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
00019 // See the GNU General Public License for more details.
00020 // 
00021 // You should have received a copy of the GNU General Public
00022 // License along with E-Cell -- see the file COPYING.
00023 // If not, write to the Free Software Foundation, Inc.,
00024 // 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
00025 // 
00026 //END_HEADER
00027 //
00028 // written by Eiichiro Adachi
00029 // modified by Koichi Takahashi
00030 //
00031 
00032 
00033 #ifndef __DYNAMICPRIORITYQUEUE_HPP
00034 #define __DYNAMICPRIORITYQUEUE_HPP
00035 #include <vector>
00036 #include <algorithm>
00037 
00038 //#include "Util.hpp"
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     This method returns the index of the given pointer to Item.
00173 
00174     The pointer must point to a valid item on theItemVector.
00175     Returned index is that of theItemVector.
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 // begin implementation
00197 
00198 template < typename Item >
00199 DynamicPriorityQueue< Item >::DynamicPriorityQueue()
00200   :
00201   theSize( 0 )
00202 {
00203   ; // do nothing
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   //  assert( aPosition < getSize() );
00224   const Index aPosition( theIndexVector[anIndex] );
00225 
00226   moveDownPos( aPosition );
00227 
00228   // If above moveDown() didn't move this item,
00229   // then we need to try moveUp() too.  If moveDown()
00230   // did work, nothing should be done.
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   // first pass: do nothing if move up doesn't occur.
00245   Item* aPredItem( theItemPtrVector[aPredecessor] );
00246   if( aPredecessor == aPosition || comp( anItem, aPredItem ) )
00247     {
00248       return;
00249     }
00250 
00251   // main loop
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 // this is an optimized version.
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   // first pass: simply return doing nothing if move down doesn't occur.
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;    // if the going down does not occur, return doing nothing.
00298     }
00299 
00300   // main loop
00301   while( 1 )
00302     {
00303       // bring up the successor
00304       theItemPtrVector[aPosition] = aSuccItem;
00305       theIndexVector[ getItemIndex( aSuccItem ) ] = aPosition;
00306       aPosition = aSuccessor;
00307 
00308       // the next successor
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       // if the going down is finished, break.
00327       if( comp( aSuccItem, anItem ) )
00328         {
00329           break;
00330         }
00331     }
00332 
00333   theItemPtrVector[aPosition] = anItem;
00334   theIndexVector[ getItemIndex( anItem ) ] = aPosition;
00335 }
00336 
00337 
00338 /* original version
00339 template < typename Item >
00340 void DynamicPriorityQueue< Item >::moveDown( Index anIndex )
00341 {
00342   Index aSuccessor( anIndex * 2 + 1 );
00343 
00344   if( aSuccessor < getSize() - 1 && comp( theItemPtrVector[aSuccessor], theItemPtrVector[aSuccessor + 1] ) )
00345     {
00346       ++aSuccessor;
00347     }
00348 
00349   Item* anItem( theItemPtrVector[anIndex] );
00350   
00351   while( aSuccessor < getSize() && comp( anItem, theItemPtrVector[aSuccessor] ) )
00352     {
00353       theItemPtrVector[anIndex] = theItemPtrVector[aSuccessor];
00354       theIndexVector[ theItemPtrVector[anIndex] - theFirstItemPtr ] = anIndex;
00355       anIndex = aSuccessor;
00356       aSuccessor = anIndex * 2 + 1;
00357 
00358       if( aSuccessor < getSize() - 1 && 
00359           comp( theItemPtrVector[aSuccessor], theItemPtrVector[ aSuccessor + 1 ] ) )
00360         {
00361           ++aSuccessor;
00362         }
00363     }
00364 
00365   theItemPtrVector[anIndex] = anItem;
00366   theIndexVector[ theItemPtrVector[anIndex] - theFirstItemPtr ] = anIndex;
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   Do not modify
00398   $Author: sachiboo $
00399   $Revision: 2619 $
00400   $Date: 2006-11-24 13:13:59 +0100 (Fri, 24 Nov 2006) $
00401   $Locker$
00402 */
00403 
00404 
00405 
00406 
00407 

Generated on Mon Dec 18 07:24:07 2006 for E-CELL C++ libraries (libecs and libemc) 3.1.105 by  doxygen 1.5.1