Main Page   Groups   Namespace List   Class Hierarchy   Alphabetical List   Compound List   File List   Namespace Members   Compound Members   File Members   Concepts

itkPriorityQueueContainer.h

Go to the documentation of this file.
00001 /*=========================================================================
00002 
00003   Program:   Insight Segmentation & Registration Toolkit
00004   Module:    $RCSfile: itkPriorityQueueContainer.h,v $
00005   Language:  C++
00006   Date:      $Date: 2009-05-13 22:05:47 $
00007   Version:   $Revision: 1.9 $
00008 
00009   Copyright (c) Insight Software Consortium. All rights reserved.
00010   See ITKCopyright.txt or http://www.itk.org/HTML/Copyright.htm for details.
00011 
00012      This software is distributed WITHOUT ANY WARRANTY; without even
00013      the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
00014      PURPOSE.  See the above copyright notices for more information.
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 // first define a common interface all the wrapper will have to abide to
00032 // this will let us define our own wrapper with different behavior.
00033 // As an exemple we define below a wrapper for a min sorted or max sorted
00034 // queue.
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 // If you want to manage the items outside the queue for example, if you don't
00054 // want the queue to manage the items memory, then you can use this wrapper
00055 // around pointers to items.  It follows the ElementWrapperInterface and thus
00056 // can be used in the queue.
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 // To follow ITK rule, we template the Element priority and the element
00091 // identifier type.
00092 // For example, as we want to use this for decimation, the element will be some
00093 // kind of cell or point pointer, the priority will be whatever you want it to
00094 // be as long as you define the comparison operators, and the identifier will
00095 // set according to the size of the vector you want to create.
00096 //
00097 // this implementation is used for min sorted priorityqueue
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   // still virtual to be able to overload it in the Max flavor
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 // this implementation is used for max sorted priorityqueue
00168 // most of the job is already done, just need to overload the less
00169 // and greater ops.
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 // finally, implement the priority queue itself on top of an itk::VectorContainer
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  // typedef typename VectorType::size_type              size_type;
00249 //  typedef typename VectorType::VectorIterator         VectorIterator;
00250 //  typedef typename VectorType::VectorConstIterator    VectorConstIterator;
00251 
00252 public:
00253  PriorityQueueContainer():
00254    VectorType() {}
00255  //PriorityQueueContainer(size_type n):
00256  //   VectorType(n) {}
00257  //PriorityQueueContainer(size_type n, const Element& x):
00258  //  VectorType(n, x) {}
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   //void Reserve( ElementIdentifier NbOfElementsToStore )
00270   //{ this->Superclass->Reserve( NbOfElementsToStore ); }
00271   //void Squeeze( ) { this->Superclass->Squeeze( ); }
00272   void Clear( ) { this->Initialize( );  } // do not release memory
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   // One instance of the interface to deal with the functions calls
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 

Generated at Thu May 28 11:10:43 2009 for ITK by doxygen 1.5.5 written by Dimitri van Heesch, © 1997-2000