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: 2008-10-12 12:46:48 $
00007   Version:   $Revision: 1.8 $
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 <assert.h>
00027 #include <vector>
00028 
00029 namespace itk
00030 {
00031 
00032 // first define a common interface all the wrapper will have to abide to
00033 // this will let us define our own wrapper with different behavior.
00034 // As an exemple we define below a wrapper for a min sorted or max sorted
00035 // queue.
00036 template< typename TElement, typename TElementIdentifier = int >
00037 class ElementWrapperInterface
00038 {
00039 public:
00040   typedef TElement                ElementType;
00041   typedef TElementIdentifier      ElementIdentifierType;
00042 
00043   ElementWrapperInterface() {}
00044   virtual ~ElementWrapperInterface() {}
00045 
00046   virtual TElementIdentifier GetLocation( const ElementType& element) = 0;
00047   virtual void SetLocation( ElementType& element, const ElementIdentifierType& identifier) = 0;
00048   virtual bool is_less( const ElementType& element1, const ElementType& element2 ) = 0;
00049   virtual bool is_greater( const ElementType& element1, const ElementType& element2 ) = 0;
00050 };
00051 
00052 
00053 //
00054 // If you want to manage the items outside the queue for example, if you don't
00055 // want the queue to manage the items memory, then you can use this wrapper
00056 // around pointers to items.  It follows the ElementWrapperInterface and thus
00057 // can be used in the queue.
00058 //
00059 template< typename TElementWrapperPointer, typename TElementIdentifier = int >
00060 class ElementWrapperPointerInterface
00061 {
00062 public:
00063   typedef TElementWrapperPointer      ElementWrapperPointerType;
00064   typedef TElementIdentifier          ElementIdentifierType;
00065 
00066   ElementWrapperPointerInterface() { }
00067   ~ElementWrapperPointerInterface() { }
00068 
00069   TElementIdentifier GetLocation( const ElementWrapperPointerType& element)
00070     {
00071     return( (*element).GetLocation(*element) );
00072     }
00073 
00074   void SetLocation( ElementWrapperPointerType element, const ElementIdentifierType& identifier)
00075     {
00076     (*element).SetLocation(*element, identifier);
00077     }
00078 
00079   bool is_less( const ElementWrapperPointerType& element1, const ElementWrapperPointerType& element2 )
00080     {
00081     return( (*element1).is_less( (*element1), (*element2) ) );
00082     }
00083 
00084   bool is_greater( const ElementWrapperPointerType& element1, const ElementWrapperPointerType& element2 )
00085     {
00086     return( (*element1).is_greater( (*element1), (*element2) ) );
00087     }
00088 };
00089 
00090 
00091 // To follow ITK rule, we template the Element priority and the element
00092 // identifier type.
00093 // For example, as we want to use this for decimation, the element will be some
00094 // kind of cell or point pointer, the priority will be whatever you want it to
00095 // be as long as you define the comparison operators, and the identifier will
00096 // set according to the size of the vector you want to create.
00097 //
00098 // this implementation is used for min sorted priorityqueue
00099 template<
00100   typename TElement,
00101   typename TElementPriority = double,
00102   typename TElementIdentifier = int
00103  >
00104 class MinPriorityQueueElementWrapper :
00105     public ElementWrapperInterface<
00106     MinPriorityQueueElementWrapper< TElement,
00107                                     TElementPriority,
00108                                     TElementIdentifier >,
00109     TElementIdentifier
00110     >
00111 {
00112 public:
00113   typedef TElement                ElementType;
00114   typedef TElementPriority        ElementPriorityType;
00115   typedef TElementIdentifier      ElementIdentifierType;
00116 
00117   ElementType                     m_Element;
00118   ElementPriorityType             m_Priority;
00119   ElementIdentifierType           m_Location;
00120 
00121   MinPriorityQueueElementWrapper() : m_Priority( 0 ), m_Location( -1 )
00122     {}
00123 
00124   MinPriorityQueueElementWrapper( ElementType element, ElementPriorityType priority ) :
00125     m_Element( element ), m_Priority( priority ), m_Location( -1 )
00126     {}
00127 
00128   virtual ~MinPriorityQueueElementWrapper() {}
00129 
00130   bool operator>( const MinPriorityQueueElementWrapper& other) const
00131     {
00132     return this->m_Priority > other.m_Priority;
00133     }
00134 
00135   bool operator<( const MinPriorityQueueElementWrapper& other) const
00136     {
00137     return this->m_Priority < other.m_Priority;
00138     }
00139 
00140   bool operator==( const MinPriorityQueueElementWrapper& other) const
00141     {
00142     return this->m_Priority == other.m_Priority;
00143     }
00144 
00145   ElementIdentifierType GetLocation( const MinPriorityQueueElementWrapper& element)
00146     {
00147     return element.m_Location;
00148     }
00149 
00150   void SetLocation( MinPriorityQueueElementWrapper& element, const TElementIdentifier& identifier)
00151     {
00152     element.m_Location = identifier;
00153     }
00154 
00155   // still virtual to be able to overload it in the Max flavor
00156   virtual bool is_less( const MinPriorityQueueElementWrapper& element1, const MinPriorityQueueElementWrapper& element2 )
00157     {
00158     return( element1 < element2 );
00159     }
00160 
00161   virtual bool is_greater( const MinPriorityQueueElementWrapper& element1, const MinPriorityQueueElementWrapper& element2 )
00162     {
00163     return( element1 > element2 );
00164     }
00165 
00166 };
00167 
00168 // this implementation is used for max sorted priorityqueue
00169 // most of the job is already done, just need to overload the less
00170 // and greater ops.
00171 template<
00172   typename TElement,
00173   typename TElementPriority = double,
00174   typename TElementIdentifier = int
00175  >
00176 class MaxPriorityQueueElementWrapper :
00177   public MinPriorityQueueElementWrapper< TElement,
00178                                          TElementPriority,
00179                                          TElementIdentifier >
00180 {
00181 public:
00182   typedef TElement                          ElementType;
00183   typedef TElementPriority                  ElementPriorityType;
00184   typedef TElementIdentifier                ElementIdentifierType;
00185 
00186   typedef MinPriorityQueueElementWrapper<ElementType,
00187                                          ElementPriorityType,
00188                                          ElementIdentifierType > Superclass;
00189   MaxPriorityQueueElementWrapper( ) :
00190     MinPriorityQueueElementWrapper< ElementType,
00191                                     ElementPriorityType,
00192                                     ElementIdentifierType >( ) {}
00193 
00194   MaxPriorityQueueElementWrapper( ElementType element,
00195     ElementPriorityType priority ) :
00196     MinPriorityQueueElementWrapper< ElementType,
00197                                     ElementPriorityType,
00198                                     ElementIdentifierType >( element, priority ) {}
00199 
00200   virtual ~MaxPriorityQueueElementWrapper() {}
00201 
00202   bool is_less( const MaxPriorityQueueElementWrapper& element1,
00203                 const MaxPriorityQueueElementWrapper& element2 )
00204     {
00205     return( element1 > element2 );
00206     }
00207   bool is_less( const Superclass& element1,
00208                 const Superclass& element2 )
00209     {
00210     return Superclass::is_less(element1, element2);
00211     }
00212 
00213   bool is_greater( const MaxPriorityQueueElementWrapper& element1,
00214                 const MaxPriorityQueueElementWrapper& element2 )
00215     {
00216     return( element1 < element2 );
00217     }
00218   bool is_greater( const Superclass& element1,
00219                    const Superclass& element2 )
00220     {
00221     return Superclass::is_greater(element1, element2);
00222     }
00223 };
00224 
00225 
00226 // finally, implement the priority queue itself on top of an itk::VectorContainer
00227 template<
00228   typename TElementWrapper,
00229   typename TElementWrapperInterface,
00230   typename TElementPriority = double,
00231   typename TElementIdentifier = int
00232   >
00233 class PriorityQueueContainer :
00234   public VectorContainer< TElementIdentifier, TElementWrapper >
00235 {
00236 
00237 public:
00238   typedef PriorityQueueContainer                                    Self;
00239   typedef VectorContainer< TElementIdentifier, TElementWrapper >    Superclass;
00240   typedef SmartPointer<Self>                                        Pointer;
00241   typedef SmartPointer<const Self>                                  ConstPointer;
00242 
00243   typedef TElementIdentifier          ElementIdentifier;
00244   typedef TElementWrapper             Element;
00245   typedef TElementWrapperInterface    ElementInterface;
00246 
00247 private:
00248   typedef Superclass                                    VectorType;
00249  // typedef typename VectorType::size_type              size_type;
00250 //  typedef typename VectorType::VectorIterator         VectorIterator;
00251 //  typedef typename VectorType::VectorConstIterator    VectorConstIterator;
00252 
00253 public:
00254  PriorityQueueContainer():
00255    VectorType() {}
00256  //PriorityQueueContainer(size_type n):
00257  //   VectorType(n) {}
00258  //PriorityQueueContainer(size_type n, const Element& x):
00259  //  VectorType(n, x) {}
00260  PriorityQueueContainer(const Self& r): VectorType(r) {}
00261 
00262  template <class TInputIterator>
00263  PriorityQueueContainer(TInputIterator first, TInputIterator last):
00264    VectorType(first, last) {}
00265 
00266 public:
00267   itkNewMacro(Self);
00268   itkTypeMacro(PriorityQueueContainer, VectorContainer);
00269 
00270   //void Reserve( ElementIdentifier NbOfElementsToStore )
00271   //{ this->Superclass->Reserve( NbOfElementsToStore ); }
00272   //void Squeeze( ) { this->Superclass->Squeeze( ); }
00273   void Clear( ) { this->Initialize( );  } // do not release memory
00274   bool Empty( ) const { return( this->empty() ); }
00275   void Push( Element element )
00276     {
00277     this->push_back( element );
00278     this->UpdateUpTree( static_cast< ElementIdentifier >( this->Size( ) ) - 1 );
00279     }
00280 
00281   Element Peek( )
00282     {
00283     assert( !Empty( ) );
00284     return( GetElementAtLocation( 0 ) );
00285     }
00286 
00287   void Pop( )
00288     {
00289     m_Interface.SetLocation( GetElementAtLocation( 0 ), -1 );
00290     if( this->Size( ) > 1 )
00291       {
00292       SetElementAtLocation( 0,
00293         GetElementAtLocation(
00294           static_cast< ElementIdentifier >( this->Size( ) - 1 ) ) );
00295       this->pop_back();
00296       UpdateDownTree( 0 );
00297       }
00298     else
00299       {
00300       if( this->Size() == 1 )
00301         this->pop_back();
00302       }
00303     }
00304 
00305   void Update( Element element )
00306     {
00307     ElementIdentifier location = m_Interface.GetLocation( element );
00308     assert( location != -1 );
00309     assert( location < static_cast< ElementIdentifier >( this->Size( ) ) );
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     assert( location != -1 );
00320     assert( location < static_cast< ElementIdentifier >( this->Size( ) ) );
00321 
00322     if( location == static_cast< ElementIdentifier >( this->Size( ) ) - 1 )
00323       {
00324       this->pop_back();
00325       }
00326     else
00327       {
00328       SetElementAtLocation( location,
00329         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 Sat Feb 28 13:17:34 2009 for ITK by doxygen 1.5.6 written by Dimitri van Heesch, © 1997-2000