Main Page | Modules | Namespace List | Class Hierarchy | Alphabetical List | Class List | Directories | File List | Namespace Members | Class Members | File Members

priority_queue.h

Go to the documentation of this file.
00001 // Copyright (C) 2005-2008 Washington University in St Louis, Baylor College of Medicine.  All rights reserved
00002 // Author:        Tao Ju (taoju@cse.wustl.edu)
00003 // Description:   A Priority queue implementation
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

Generated on Tue Jun 11 13:46:16 2013 for EMAN2 by  doxygen 1.3.9.1