Template class for a priority queue. More...

#include <priority_queue.h>

Public Member Functions
	PriorityQueue (int max)
	Constructor. More...

	~PriorityQueue ()
	Destructor. More...

int	getLength ()
	Get current length. More...

bool	isEmpty ()
	Test whether empty. More...

bool	isFull ()
	Test whether full. More...

void	add (ValueT *v, KeyT k)
	Add an element. More...

void	remove (ValueT *&v, KeyT &k)
	Remove an element. More...

Public Attributes
int	queueLength
	Number of elements in queue. More...

int	maxLength
	Maximum number of elements int he queue. More...

ValueT **	valueQueue
	Queue of elements. More...

KeyT *	keyQueue
	Queue of keys. More...

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

◆ PriorityQueue()

template<class ValueT , class KeyT >

EMAN::PriorityQueue< ValueT, KeyT >::PriorityQueue ( int max )

inline

Constructor.

Definition at line 37 of file priority_queue.h.

        {
                this->maxLength = max ;
                this->queueLength = 0 ;
                this->valueQueue = new ValueT* [ max ] ;
                this->keyQueue = new KeyT [ max ] ;
 
        };

◆ ~PriorityQueue()

template<class ValueT , class KeyT >

EMAN::PriorityQueue< ValueT, KeyT >::~PriorityQueue ( )

inline

Destructor.

Definition at line 49 of file priority_queue.h.

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

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

Member Function Documentation

◆ add()

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.

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

References EMAN::PriorityQueue< ValueT, KeyT >::isFull(), EMAN::PriorityQueue< ValueT, KeyT >::keyQueue, EMAN::PriorityQueue< ValueT, KeyT >::queueLength, 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().

◆ getLength()

template<class ValueT , class KeyT >

int EMAN::PriorityQueue< ValueT, KeyT >::getLength ( )

inline

Get current length.

Definition at line 62 of file priority_queue.h.

        {
                return this->queueLength ;
        };

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

◆ isEmpty()

template<class ValueT , class KeyT >

bool EMAN::PriorityQueue< ValueT, KeyT >::isEmpty ( )

inline

Test whether empty.

Definition at line 70 of file priority_queue.h.

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

Referenced by wustl_mm::SkeletonMaker::Volume::curveSkeleton(), wustl_mm::SkeletonMaker::Volume::curveSkeleton2D(), EMAN::PriorityQueue< ValueT, KeyT >::remove(), wustl_mm::SkeletonMaker::Volume::skeleton(), and wustl_mm::SkeletonMaker::Volume::surfaceSkeletonPres().

◆ isFull()

template<class ValueT , class KeyT >

bool EMAN::PriorityQueue< ValueT, KeyT >::isFull ( )

inline

Test whether full.

Definition at line 78 of file priority_queue.h.

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

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

◆ remove()

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.

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

References EMAN::PriorityQueue< ValueT, KeyT >::isEmpty(), EMAN::PriorityQueue< ValueT, KeyT >::keyQueue, EMAN::PriorityQueue< ValueT, KeyT >::queueLength, 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().

Member Data Documentation

◆ keyQueue

template<class ValueT , class KeyT >

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

Queue of keys.

Definition at line 30 of file priority_queue.h.

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

◆ maxLength

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.

◆ queueLength

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.

Referenced by EMAN::PriorityQueue< ValueT, KeyT >::add(), EMAN::PriorityQueue< ValueT, KeyT >::getLength(), EMAN::PriorityQueue< ValueT, KeyT >::remove(), and EMAN::PriorityQueue< ValueT, KeyT >::~PriorityQueue().

◆ valueQueue

template<class ValueT , class KeyT >

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

Queue of elements.

Definition at line 27 of file priority_queue.h.

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

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

priority_queue.h

Public Member Functions

Public Attributes

Detailed Description

Constructor & Destructor Documentation

◆ PriorityQueue()

◆ ~PriorityQueue()

Member Function Documentation

◆ add()

◆ getLength()

◆ isEmpty()

◆ isFull()

◆ remove()

Member Data Documentation

◆ keyQueue

◆ maxLength

◆ queueLength

◆ valueQueue