00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017 #ifndef __itkPriorityQueueContainer_h
00018 #define __itkPriorityQueueContainer_h
00019
00020 #include "itkObject.h"
00021 #include "itkObjectFactory.h"
00022 #include "itkVectorContainer.h"
00023
00024 #include <functional>
00025 #include <queue>
00026 #include <vector>
00027
00028 namespace itk
00029 {
00030
00031
00032
00033
00034
00035 template< typename TElement, typename TElementIdentifier = int >
00036 class ElementWrapperInterface
00037 {
00038 public:
00039 typedef TElement ElementType;
00040 typedef TElementIdentifier ElementIdentifierType;
00041
00042 ElementWrapperInterface() {}
00043 virtual ~ElementWrapperInterface() {}
00044
00045 virtual TElementIdentifier GetLocation( const ElementType& element) = 0;
00046 virtual void SetLocation( ElementType& element, const ElementIdentifierType& identifier) = 0;
00047 virtual bool is_less( const ElementType& element1, const ElementType& element2 ) = 0;
00048 virtual bool is_greater( const ElementType& element1, const ElementType& element2 ) = 0;
00049 };
00050
00051
00052
00053
00054
00055
00056
00057
00058 template< typename TElementWrapperPointer, typename TElementIdentifier = int >
00059 class ElementWrapperPointerInterface
00060 {
00061 public:
00062 typedef TElementWrapperPointer ElementWrapperPointerType;
00063 typedef TElementIdentifier ElementIdentifierType;
00064
00065 ElementWrapperPointerInterface() { }
00066 ~ElementWrapperPointerInterface() { }
00067
00068 TElementIdentifier GetLocation( const ElementWrapperPointerType& element)
00069 {
00070 return( (*element).GetLocation(*element) );
00071 }
00072
00073 void SetLocation( ElementWrapperPointerType element, const ElementIdentifierType& identifier)
00074 {
00075 (*element).SetLocation(*element, identifier);
00076 }
00077
00078 bool is_less( const ElementWrapperPointerType& element1, const ElementWrapperPointerType& element2 )
00079 {
00080 return( (*element1).is_less( (*element1), (*element2) ) );
00081 }
00082
00083 bool is_greater( const ElementWrapperPointerType& element1, const ElementWrapperPointerType& element2 )
00084 {
00085 return( (*element1).is_greater( (*element1), (*element2) ) );
00086 }
00087 };
00088
00089
00090
00091
00092
00093
00094
00095
00096
00097
00098 template<
00099 typename TElement,
00100 typename TElementPriority = double,
00101 typename TElementIdentifier = int
00102 >
00103 class MinPriorityQueueElementWrapper :
00104 public ElementWrapperInterface<
00105 MinPriorityQueueElementWrapper< TElement,
00106 TElementPriority,
00107 TElementIdentifier >,
00108 TElementIdentifier
00109 >
00110 {
00111 public:
00112 typedef TElement ElementType;
00113 typedef TElementPriority ElementPriorityType;
00114 typedef TElementIdentifier ElementIdentifierType;
00115
00116 ElementType m_Element;
00117 ElementPriorityType m_Priority;
00118 ElementIdentifierType m_Location;
00119
00120 MinPriorityQueueElementWrapper() : m_Priority( 0 ), m_Location( -1 )
00121 {}
00122
00123 MinPriorityQueueElementWrapper( ElementType element, ElementPriorityType priority ) :
00124 m_Element( element ), m_Priority( priority ), m_Location( -1 )
00125 {}
00126
00127 virtual ~MinPriorityQueueElementWrapper() {}
00128
00129 bool operator>( const MinPriorityQueueElementWrapper& other) const
00130 {
00131 return this->m_Priority > other.m_Priority;
00132 }
00133
00134 bool operator<( const MinPriorityQueueElementWrapper& other) const
00135 {
00136 return this->m_Priority < other.m_Priority;
00137 }
00138
00139 bool operator==( const MinPriorityQueueElementWrapper& other) const
00140 {
00141 return this->m_Priority == other.m_Priority;
00142 }
00143
00144 ElementIdentifierType GetLocation( const MinPriorityQueueElementWrapper& element)
00145 {
00146 return element.m_Location;
00147 }
00148
00149 void SetLocation( MinPriorityQueueElementWrapper& element, const TElementIdentifier& identifier)
00150 {
00151 element.m_Location = identifier;
00152 }
00153
00154
00155 virtual bool is_less( const MinPriorityQueueElementWrapper& element1, const MinPriorityQueueElementWrapper& element2 )
00156 {
00157 return( element1 < element2 );
00158 }
00159
00160 virtual bool is_greater( const MinPriorityQueueElementWrapper& element1, const MinPriorityQueueElementWrapper& element2 )
00161 {
00162 return( element1 > element2 );
00163 }
00164
00165 };
00166
00167
00168
00169
00170 template<
00171 typename TElement,
00172 typename TElementPriority = double,
00173 typename TElementIdentifier = int
00174 >
00175 class MaxPriorityQueueElementWrapper :
00176 public MinPriorityQueueElementWrapper< TElement,
00177 TElementPriority,
00178 TElementIdentifier >
00179 {
00180 public:
00181 typedef TElement ElementType;
00182 typedef TElementPriority ElementPriorityType;
00183 typedef TElementIdentifier ElementIdentifierType;
00184
00185 typedef MinPriorityQueueElementWrapper<ElementType,
00186 ElementPriorityType,
00187 ElementIdentifierType > Superclass;
00188 MaxPriorityQueueElementWrapper( ) :
00189 MinPriorityQueueElementWrapper< ElementType,
00190 ElementPriorityType,
00191 ElementIdentifierType >( ) {}
00192
00193 MaxPriorityQueueElementWrapper( ElementType element,
00194 ElementPriorityType priority ) :
00195 MinPriorityQueueElementWrapper< ElementType,
00196 ElementPriorityType,
00197 ElementIdentifierType >( element, priority ) {}
00198
00199 virtual ~MaxPriorityQueueElementWrapper() {}
00200
00201 bool is_less( const MaxPriorityQueueElementWrapper& element1,
00202 const MaxPriorityQueueElementWrapper& element2 )
00203 {
00204 return( element1 > element2 );
00205 }
00206 bool is_less( const Superclass& element1,
00207 const Superclass& element2 )
00208 {
00209 return Superclass::is_less(element1, element2);
00210 }
00211
00212 bool is_greater( const MaxPriorityQueueElementWrapper& element1,
00213 const MaxPriorityQueueElementWrapper& element2 )
00214 {
00215 return( element1 < element2 );
00216 }
00217 bool is_greater( const Superclass& element1,
00218 const Superclass& element2 )
00219 {
00220 return Superclass::is_greater(element1, element2);
00221 }
00222 };
00223
00224
00225
00226 template<
00227 typename TElementWrapper,
00228 typename TElementWrapperInterface,
00229 typename TElementPriority = double,
00230 typename TElementIdentifier = int
00231 >
00232 class PriorityQueueContainer :
00233 public VectorContainer< TElementIdentifier, TElementWrapper >
00234 {
00235
00236 public:
00237 typedef PriorityQueueContainer Self;
00238 typedef VectorContainer< TElementIdentifier, TElementWrapper > Superclass;
00239 typedef SmartPointer<Self> Pointer;
00240 typedef SmartPointer<const Self> ConstPointer;
00241
00242 typedef TElementIdentifier ElementIdentifier;
00243 typedef TElementWrapper Element;
00244 typedef TElementWrapperInterface ElementInterface;
00245
00246 private:
00247 typedef Superclass VectorType;
00248
00249
00250
00251
00252 public:
00253 PriorityQueueContainer():
00254 VectorType() {}
00255
00256
00257
00258
00259 PriorityQueueContainer(const Self& r): VectorType(r) {}
00260
00261 template <class TInputIterator>
00262 PriorityQueueContainer(TInputIterator first, TInputIterator last):
00263 VectorType(first, last) {}
00264
00265 public:
00266 itkNewMacro(Self);
00267 itkTypeMacro(PriorityQueueContainer, VectorContainer);
00268
00269
00270
00271
00272 void Clear( ) { this->Initialize( ); }
00273 bool Empty( ) const { return( this->empty() ); }
00274 void Push( Element element )
00275 {
00276 this->push_back( element );
00277 this->UpdateUpTree( static_cast< ElementIdentifier >( this->Size( ) ) - 1 );
00278 }
00279
00280 Element Peek( )
00281 {
00282 itkAssertOrThrowMacro( (!Empty( )), "Element is Empty" );
00283 return( GetElementAtLocation( 0 ) );
00284 }
00285
00286 void Pop( )
00287 {
00288 m_Interface.SetLocation( GetElementAtLocation( 0 ), -1 );
00289 if( this->Size( ) > 1 )
00290 {
00291 SetElementAtLocation( 0,
00292 GetElementAtLocation(
00293 static_cast< ElementIdentifier >( this->Size( ) - 1 ) ) );
00294 this->pop_back();
00295 UpdateDownTree( 0 );
00296 }
00297 else
00298 {
00299 if( this->Size() == 1 )
00300 this->pop_back();
00301 }
00302 }
00303
00304 void Update( Element element )
00305 {
00306 ElementIdentifier location = m_Interface.GetLocation( element );
00307 itkAssertOrThrowMacro( (location != -1), "element is unknown");
00308 itkAssertOrThrowMacro( (location < static_cast< ElementIdentifier >( this->Size( ) ) ),
00309 "Element location is out of range" );
00310 UpdateDownTree( location );
00311 UpdateUpTree( location );
00312 }
00313
00314 void DeleteElement( Element element )
00315 {
00316 ElementIdentifier location = m_Interface.GetLocation( element );
00317 m_Interface.SetLocation( element, -1);
00318
00319 itkAssertOrThrowMacro( (location != -1), "element is unknown");
00320 itkAssertOrThrowMacro( (location < static_cast< ElementIdentifier >( this->Size( ) ) ),
00321 "Element location is out of range" );
00322
00323 if( location == static_cast< ElementIdentifier >( this->Size( ) ) - 1 )
00324 {
00325 this->pop_back();
00326 }
00327 else
00328 {
00329 SetElementAtLocation( location, GetElementAtLocation( this->Size( ) - 1 ) );
00330 this->pop_back();
00331 UpdateDownTree( location );
00332 UpdateUpTree( location );
00333 }
00334 }
00335
00336 protected:
00337
00338
00339 ElementInterface m_Interface;
00340
00341 inline Element& GetElementAtLocation( const ElementIdentifier& identifier )
00342 {
00343 return this->operator[]( identifier );
00344 }
00345
00346 inline void SetElementAtLocation( const ElementIdentifier& identifier,
00347 Element element )
00348 {
00349 this->operator[]( identifier ) = element;
00350 m_Interface.SetLocation( element, identifier );
00351 }
00352
00353 inline ElementIdentifier GetParent( const ElementIdentifier& identifier ) const
00354 {
00355 return( (identifier - 1) >> 1 );
00356 }
00357
00358 inline ElementIdentifier GetLeft( const ElementIdentifier& identifier ) const
00359 {
00360 return( (identifier << 1) + 1 );
00361 }
00362
00363 inline ElementIdentifier GetRight( const ElementIdentifier& identifier ) const
00364 {
00365 return( (identifier << 1) + 2 );
00366 }
00367
00368 void UpdateUpTree( const ElementIdentifier& identifier )
00369 {
00370 if( identifier > 0 )
00371 {
00372 ElementIdentifier id( identifier );
00373 Element element = GetElementAtLocation( id );
00374 ElementIdentifier parentIdentifier = GetParent( id );
00375 Element parent_element = GetElementAtLocation( parentIdentifier );
00376
00377 while( ( id > 0 ) &&
00378 m_Interface.is_less( element, parent_element ) )
00379 {
00380 SetElementAtLocation( id, parent_element );
00381 id = parentIdentifier;
00382 if( id > 0 )
00383 {
00384 parentIdentifier = GetParent( id );
00385 parent_element = GetElementAtLocation( parentIdentifier );
00386 }
00387 }
00388 SetElementAtLocation( id, element );
00389 }
00390 }
00391
00392 void UpdateDownTree( const ElementIdentifier& identifier )
00393 {
00394 ElementIdentifier id( identifier );
00395 Element element = GetElementAtLocation( id );
00396
00397 ElementIdentifier queueSize =
00398 static_cast< ElementIdentifier >( this->Size( ) );
00399
00400 while( id < queueSize )
00401 {
00402 ElementIdentifier childIdentifier = GetLeft( id );
00403 if( childIdentifier >= queueSize )
00404 {
00405 break;
00406 }
00407 if( ( childIdentifier + 1 < queueSize ) &&
00408 ( m_Interface.is_less( GetElementAtLocation( childIdentifier + 1 ),
00409 GetElementAtLocation( childIdentifier ) ) ) )
00410 {
00411 ++childIdentifier;
00412 }
00413 Element temp = GetElementAtLocation( childIdentifier );
00414 if( m_Interface.is_less( element, temp ) )
00415 {
00416 break;
00417 }
00418
00419 SetElementAtLocation( id, temp );
00420 id = childIdentifier;
00421 }
00422
00423 SetElementAtLocation( id, element );
00424 }
00425 };
00426
00427 }
00428
00429 #endif
00430