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

EMAN::PriorityQueue< ValueT, KeyT > Class Template Reference

Template class for a priority queue. More...

#include <priority_queue.h>

Collaboration diagram for EMAN::PriorityQueue< ValueT, KeyT >:

Collaboration graph
[legend]
List of all members.

Public Member Functions

 PriorityQueue (int max)
 Constructor.
 ~PriorityQueue ()
 Destructor.
int getLength ()
 Get current length.
bool isEmpty ()
 Test whether empty.
bool isFull ()
 Test whether full.
void add (ValueT *v, KeyT k)
 Add an element.
void remove (ValueT *&v, KeyT &k)
 Remove an element.

Public Attributes

int queueLength
 Number of elements in queue.
int maxLength
 Maximum number of elements int he queue.
ValueT ** valueQueue
 Queue of elements.
KeyT * keyQueue
 Queue of keys.

Detailed Description

template<class ValueT, class KeyT>
class EMAN::PriorityQueue< ValueT, KeyT >

Template class for a priority queue.

The smallest element is at the front

Definition at line 17 of file priority_queue.h.


Constructor & Destructor Documentation

template<class ValueT, class KeyT>
EMAN::PriorityQueue< ValueT, KeyT >::PriorityQueue int  max  )  [inline]
 

Constructor.

Definition at line 37 of file priority_queue.h.

00038         {
00039                 this->maxLength = max ;
00040                 this->queueLength = 0 ;
00041                 this->valueQueue = new ValueT* [ max ] ;
00042                 this->keyQueue = new KeyT [ max ] ;
00043 
00044         };

template<class ValueT, class KeyT>
EMAN::PriorityQueue< ValueT, KeyT >::~PriorityQueue  )  [inline]
 

Destructor.

Definition at line 49 of file priority_queue.h.

00050         {
00051                 delete [] keyQueue ;
00052                 for ( int i = 0 ; i < queueLength ; i ++ )
00053                 {
00054                         delete valueQueue [ i ] ;
00055                 }
00056                 delete [] valueQueue ;
00057         };


Member Function Documentation

template<class ValueT, class KeyT>
void EMAN::PriorityQueue< ValueT, KeyT >::add ValueT *  v,
KeyT  k
[inline]
 

Add an element.

Definition at line 86 of file priority_queue.h.

Referenced by wustl_mm::SkeletonMaker::Volume::curveSkeleton(), wustl_mm::SkeletonMaker::Volume::curveSkeleton2D(), wustl_mm::SkeletonMaker::Volume::skeleton(), and wustl_mm::SkeletonMaker::Volume::surfaceSkeletonPres().

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         };

template<class ValueT, class KeyT>
int EMAN::PriorityQueue< ValueT, KeyT >::getLength  )  [inline]
 

Get current length.

Definition at line 62 of file priority_queue.h.

00063         {
00064                 return this->queueLength ;
00065         };

template<class ValueT, class KeyT>
bool EMAN::PriorityQueue< ValueT, KeyT >::isEmpty  )  [inline]
 

Test whether empty.

Definition at line 70 of file priority_queue.h.

Referenced by wustl_mm::SkeletonMaker::Volume::curveSkeleton(), wustl_mm::SkeletonMaker::Volume::curveSkeleton2D(), wustl_mm::SkeletonMaker::Volume::skeleton(), and wustl_mm::SkeletonMaker::Volume::surfaceSkeletonPres().

00071         {
00072                 return ( this->queueLength == 0 ) ;
00073         };

template<class ValueT, class KeyT>
bool EMAN::PriorityQueue< ValueT, KeyT >::isFull  )  [inline]
 

Test whether full.

Definition at line 78 of file priority_queue.h.

00079         {
00080                 return ( this->queueLength == this->maxLength  ) ;
00081         };

template<class ValueT, class KeyT>
void EMAN::PriorityQueue< ValueT, KeyT >::remove ValueT *&  v,
KeyT &  k
[inline]
 

Remove an element.

Definition at line 120 of file priority_queue.h.

References v.

Referenced by wustl_mm::SkeletonMaker::Volume::curveSkeleton(), wustl_mm::SkeletonMaker::Volume::curveSkeleton2D(), wustl_mm::SkeletonMaker::Volume::skeleton(), and wustl_mm::SkeletonMaker::Volume::surfaceSkeletonPres().

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         };


Member Data Documentation

template<class ValueT, class KeyT>
KeyT* EMAN::PriorityQueue< ValueT, KeyT >::keyQueue
 

Queue of keys.

Definition at line 30 of file priority_queue.h.

template<class ValueT, class KeyT>
int EMAN::PriorityQueue< ValueT, KeyT >::maxLength
 

Maximum number of elements int he queue.

Definition at line 24 of file priority_queue.h.

template<class ValueT, class KeyT>
int EMAN::PriorityQueue< ValueT, KeyT >::queueLength
 

Number of elements in queue.

Definition at line 21 of file priority_queue.h.

template<class ValueT, class KeyT>
ValueT** EMAN::PriorityQueue< ValueT, KeyT >::valueQueue
 

Queue of elements.

Definition at line 27 of file priority_queue.h.


The documentation for this class was generated from the following file:
Generated on Tue Jun 11 13:42:04 2013 for EMAN2 by  doxygen 1.3.9.1