EMAN2
Public Member Functions | Public Attributes
EMAN::PriorityQueue< ValueT, KeyT > Class Template Reference

Template class for a priority queue. More...

#include <priority_queue.h>

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]
template<class ValueT, class KeyT>
EMAN::PriorityQueue< ValueT, KeyT >::~PriorityQueue ( ) [inline]

Destructor.

Definition at line 49 of file priority_queue.h.

References EMAN::PriorityQueue< ValueT, KeyT >::keyQueue, EMAN::PriorityQueue< ValueT, KeyT >::queueLength, and EMAN::PriorityQueue< ValueT, KeyT >::valueQueue.

        {
                delete [] keyQueue ;
                for ( int i = 0 ; i < queueLength ; i ++ )
                {
                        delete valueQueue [ i ] ;
                }
                delete [] valueQueue ;
        };

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.

References EMAN::PriorityQueue< ValueT, KeyT >::isFull(), EMAN::PriorityQueue< ValueT, KeyT >::keyQueue, EMAN::PriorityQueue< ValueT, KeyT >::queueLength, v, and EMAN::PriorityQueue< ValueT, KeyT >::valueQueue.

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

        {
                if ( this->isFull() )
                {
                        printf("PRIORITY QUEUE FILLED UP !!! \n");
                        return ;
                }

                int ind = queueLength ;
                int tind ;
                queueLength ++ ;

                while ( ind > 0 )
                {
                        tind = ( ind + 1 ) / 2 - 1 ;
                        if ( k < keyQueue[tind] )
                        {
                                keyQueue[ ind ] = keyQueue [ tind ] ;
                                valueQueue [ ind ] = valueQueue [ tind ] ;
                                ind = tind ;
                        }
                        else
                        {
                                break;
                        }
                }

                valueQueue[ ind ] = v ;
                keyQueue [ ind ] = k ;
        };
template<class ValueT, class KeyT>
int EMAN::PriorityQueue< ValueT, KeyT >::getLength ( ) [inline]

Get current length.

Definition at line 62 of file priority_queue.h.

References EMAN::PriorityQueue< ValueT, KeyT >::queueLength.

        {
                return this->queueLength ;
        };
template<class ValueT, class KeyT>
bool EMAN::PriorityQueue< ValueT, KeyT >::isEmpty ( ) [inline]
template<class ValueT, class KeyT>
bool EMAN::PriorityQueue< ValueT, KeyT >::isFull ( ) [inline]

Test whether full.

Definition at line 78 of file priority_queue.h.

References EMAN::PriorityQueue< ValueT, KeyT >::maxLength, and EMAN::PriorityQueue< ValueT, KeyT >::queueLength.

Referenced by EMAN::PriorityQueue< ValueT, KeyT >::add().

        {
                return ( this->queueLength == this->maxLength  ) ;
        };
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 EMAN::PriorityQueue< ValueT, KeyT >::isEmpty(), EMAN::PriorityQueue< ValueT, KeyT >::keyQueue, EMAN::PriorityQueue< ValueT, KeyT >::queueLength, v, and EMAN::PriorityQueue< ValueT, KeyT >::valueQueue.

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

        {
                if ( this->isEmpty() )
                {
                        v = NULL ;
                        k = 0 ;
                        return ;
                }

                v = valueQueue[0] ;
                k = keyQueue[0] ;
                queueLength -- ;

                if ( queueLength == 0 )
                {
                        valueQueue[0] = NULL ;
                        return ;
                }

                ValueT * vv = valueQueue [ queueLength ] ;
                KeyT kk = keyQueue [ queueLength ], lowk ;
                int ind = 0, tind, ind2, ind3 ;
                while ( 1 )
                {
                        ind2 = 2 * ( ind + 1 ) - 1 ;
                        ind3 = ind2 + 1 ;
                        tind = ind ; 
                        lowk = kk ;

                        if ( ind2 >= queueLength )
                        {
                                break ;
                        }
                        else 
                        {
                                if ( keyQueue [ ind2 ] < lowk )
                                {
                                        tind = ind2 ;
                                        lowk = keyQueue [ ind2 ] ;
                                }

                                if ( ind3 < queueLength )
                                {
                                        if ( keyQueue [ ind3 ] < lowk )
                                        {
                                                tind = ind3 ;
                                        }
                                }

                                if ( ind != tind )
                                {
                                        valueQueue [ ind ] = valueQueue [ tind ] ;
                                        keyQueue [ ind ] = keyQueue [ tind ] ;
                                        ind = tind ;
                                }
                                else
                                {
                                        break ;
                                }
                        }
                }

                valueQueue [ ind ] = vv ;
                keyQueue [ ind ] = kk ;
                valueQueue [ queueLength ] = NULL ;
                keyQueue [ queueLength ] = NULL ;
        };

Member Data Documentation

template<class ValueT, class KeyT>
KeyT* EMAN::PriorityQueue< ValueT, KeyT >::keyQueue
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.

Referenced by EMAN::PriorityQueue< ValueT, KeyT >::isFull(), and EMAN::PriorityQueue< ValueT, KeyT >::PriorityQueue().

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

The documentation for this class was generated from the following file: