#include <priority_queue.h>
Collaboration diagram for EMAN::PriorityQueue< ValueT, KeyT >:
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. |
The smallest element is at the front
Definition at line 17 of file priority_queue.h.
|
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 };
|
|
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 };
|
|
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 };
|
|
Get current length.
Definition at line 62 of file priority_queue.h. 00063 {
00064 return this->queueLength ;
00065 };
|
|
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 };
|
|
Test whether full.
Definition at line 78 of file priority_queue.h. 00079 { 00080 return ( this->queueLength == this->maxLength ) ; 00081 };
|
|
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 };
|
|
Queue of keys.
Definition at line 30 of file priority_queue.h. |
|
Maximum number of elements int he queue.
Definition at line 24 of file priority_queue.h. |
|
Number of elements in queue.
Definition at line 21 of file priority_queue.h. |
|
Queue of elements.
Definition at line 27 of file priority_queue.h. |