ITK  4.1.0
Insight Segmentation and Registration Toolkit
itkPriorityQueueContainer.h
Go to the documentation of this file.
00001 /*=========================================================================
00002  *
00003  *  Copyright Insight Software Consortium
00004  *
00005  *  Licensed under the Apache License, Version 2.0 (the "License");
00006  *  you may not use this file except in compliance with the License.
00007  *  You may obtain a copy of the License at
00008  *
00009  *         http://www.apache.org/licenses/LICENSE-2.0.txt
00010  *
00011  *  Unless required by applicable law or agreed to in writing, software
00012  *  distributed under the License is distributed on an "AS IS" BASIS,
00013  *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
00014  *  See the License for the specific language governing permissions and
00015  *  limitations under the License.
00016  *
00017  *=========================================================================*/
00018 #ifndef __itkPriorityQueueContainer_h
00019 #define __itkPriorityQueueContainer_h
00020 
00021 #include "itkVectorContainer.h"
00022 #include "itkIntTypes.h"
00023 #include "itkNumericTraits.h"
00024 
00025 #include <functional>
00026 #include <queue>
00027 #include <vector>
00028 
00029 namespace itk
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,
00036           typename TElementIdentifier = IdentifierType >
00037 class ElementWrapperInterface
00038 {
00039 public:
00040   typedef TElement           ElementType;
00041   typedef TElementIdentifier ElementIdentifierType;
00042 
00043   static const ElementIdentifierType m_ElementNotFound;
00044 
00045   ElementWrapperInterface();
00046   virtual ~ElementWrapperInterface();
00047 
00048   virtual ElementIdentifierType GetLocation(const ElementType & element) const = 0;
00049 
00050   virtual void SetLocation(ElementType & element, const ElementIdentifierType & identifier) = 0;
00051 
00052   virtual bool is_less(const ElementType & element1,
00053                        const ElementType & element2) const = 0;
00054 
00055   virtual bool is_greater(const ElementType & element1,
00056                           const ElementType & element2) const = 0;
00057 };
00058 // ------------------------------------------------------------------------
00059 
00060 
00061 // ------------------------------------------------------------------------
00062 // If you want to manage the items outside the queue for example, if you don't
00063 // want the queue to manage the items memory, then you can use this wrapper
00064 // around pointers to items.  It follows the ElementWrapperInterface and thus
00065 // can be used in the queue.
00066 //
00067 template< typename TElementWrapperPointer,
00068           typename TElementIdentifier = IdentifierType >
00069 class ElementWrapperPointerInterface
00070 {
00071 public:
00072   typedef TElementWrapperPointer ElementWrapperPointerType;
00073   typedef TElementIdentifier     ElementIdentifierType;
00074 
00075   static const ElementIdentifierType m_ElementNotFound;
00076 
00077   ElementWrapperPointerInterface();
00078   virtual ~ElementWrapperPointerInterface();
00079 
00080   TElementIdentifier GetLocation(const ElementWrapperPointerType & element) const;
00081 
00082   void SetLocation(ElementWrapperPointerType & element,
00083                    const ElementIdentifierType & identifier);
00084 
00085   virtual bool is_less(const ElementWrapperPointerType & element1,
00086                const ElementWrapperPointerType & element2) const;
00087 
00088   virtual bool is_greater(const ElementWrapperPointerType & element1,
00089                   const ElementWrapperPointerType & element2) const;
00090 };
00091 // ------------------------------------------------------------------------
00092 
00093 // ------------------------------------------------------------------------
00094 // To follow ITK rule, we template the ElementWrapperType priority and the element
00095 // identifier type.
00096 // For example, as we want to use this for decimation, the element will be some
00097 // kind of cell or point pointer, the priority will be whatever you want it to
00098 // be as long as you define the comparison operators, and the identifier will
00099 // set according to the size of the vector you want to create.
00100 //
00101 // this implementation is used for min sorted priorityqueue
00102 template<
00103   typename TElement,
00104   typename TElementPriority = double,
00105   typename TElementIdentifier = IdentifierType
00106   >
00107 class MinPriorityQueueElementWrapper:
00108   public ElementWrapperInterface<
00109     MinPriorityQueueElementWrapper< TElement,
00110                                     TElementPriority,
00111                                     TElementIdentifier >,
00112     TElementIdentifier
00113     >
00114 {
00115 public:
00116   typedef MinPriorityQueueElementWrapper< TElement,
00117     TElementPriority,
00118     TElementIdentifier >     Superclass;
00119   typedef TElement           ElementType;
00120   typedef TElementPriority   ElementPriorityType;
00121   typedef TElementIdentifier ElementIdentifierType;
00122 
00123   ElementType           m_Element;
00124   ElementPriorityType   m_Priority;
00125   ElementIdentifierType m_Location;
00126 
00127   MinPriorityQueueElementWrapper();
00128 
00129   MinPriorityQueueElementWrapper(ElementType element,
00130                                  ElementPriorityType priority);
00131 
00132   virtual ~MinPriorityQueueElementWrapper();
00133 
00134   bool operator>(const MinPriorityQueueElementWrapper & other) const;
00135 
00136   bool operator<(const MinPriorityQueueElementWrapper & other) const;
00137 
00138   bool operator==(const MinPriorityQueueElementWrapper & other) const;
00139 
00140   ElementIdentifierType GetLocation(const MinPriorityQueueElementWrapper & element) const;
00141 
00142   void SetLocation(MinPriorityQueueElementWrapper & element,
00143                    const ElementIdentifierType & identifier);
00144 
00145   // still virtual to be able to overload it in the Max flavor
00146   virtual bool is_less(const MinPriorityQueueElementWrapper & element1,
00147                        const MinPriorityQueueElementWrapper & element2) const;
00148 
00149   virtual bool is_greater(const MinPriorityQueueElementWrapper & element1,
00150                           const MinPriorityQueueElementWrapper & element2) const;
00151 
00152 };
00153 // ------------------------------------------------------------------------
00154 
00155 
00156 // ------------------------------------------------------------------------
00157 // this implementation is used for max sorted priorityqueue
00158 // most of the job is already done, just need to overload the less
00159 // and greater ops.
00160 template<
00161   typename TElement,
00162   typename TElementPriority = double,
00163   typename TElementIdentifier = IdentifierType
00164   >
00165 class MaxPriorityQueueElementWrapper:
00166   public MinPriorityQueueElementWrapper< TElement,
00167                                          TElementPriority,
00168                                          TElementIdentifier >
00169 {
00170 public:
00171   typedef TElement           ElementType;
00172   typedef TElementPriority   ElementPriorityType;
00173   typedef TElementIdentifier ElementIdentifierType;
00174 
00175   typedef MinPriorityQueueElementWrapper< ElementType,
00176                                           ElementPriorityType,
00177                                           ElementIdentifierType > Superclass;
00178   MaxPriorityQueueElementWrapper();
00179 
00180   MaxPriorityQueueElementWrapper(ElementType element,
00181                                  ElementPriorityType priority);
00182 
00183   virtual ~MaxPriorityQueueElementWrapper() {}
00184 
00185   virtual bool is_less(const MaxPriorityQueueElementWrapper & element1,
00186                const MaxPriorityQueueElementWrapper & element2) const;
00187 
00188   virtual bool is_less(const Superclass & element1,
00189                const Superclass & element2) const;
00190 
00191   virtual bool is_greater(const MaxPriorityQueueElementWrapper & element1,
00192                   const MaxPriorityQueueElementWrapper & element2) const;
00193 
00194   virtual bool is_greater(const Superclass & element1,
00195                   const Superclass & element2) const;
00196 
00197 };
00198 // ------------------------------------------------------------------------
00199 
00200 
00201 // ------------------------------------------------------------------------
00202 // finally, implement the priority queue itself on top of an
00203 // itk::VectorContainer
00204 template<
00205   typename TElementWrapper,
00206   typename TElementWrapperInterface,
00207   typename TElementPriority = double,
00208   typename TElementIdentifier = IdentifierType
00209   >
00210 class PriorityQueueContainer:
00211   public VectorContainer< TElementIdentifier, TElementWrapper >
00212 {
00213 public:
00214   typedef PriorityQueueContainer                                 Self;
00215   typedef VectorContainer< TElementIdentifier, TElementWrapper > Superclass;
00216   typedef SmartPointer< Self >                                   Pointer;
00217   typedef SmartPointer< const Self >                             ConstPointer;
00218 
00219   typedef TElementIdentifier       ElementIdentifierType;
00220   typedef TElementWrapper          ElementWrapperType;
00221   typedef TElementWrapperInterface ElementInterfaceType;
00222 
00223   static const ElementIdentifierType m_ElementNotFound;
00224 
00225 public:
00226   PriorityQueueContainer();
00227   ~PriorityQueueContainer();
00228 
00229   template< class TInputIterator >
00230   PriorityQueueContainer(TInputIterator first, TInputIterator last):
00231     Superclass()
00232   {
00233     TInputIterator it = first;
00234     while( it != last )
00235       {
00236       this->Push( *it );
00237       ++it;
00238       }
00239   }
00240 
00241 public:
00242   itkNewMacro(Self);
00243   itkTypeMacro(PriorityQueueContainer, VectorContainer);
00244 
00245   //void Reserve( ElementIdentifier NbOfElementsToStore )
00246   //{ this->Superclass->Reserve( NbOfElementsToStore ); }
00247   //void Squeeze( ) { this->Superclass->Squeeze( ); }
00248   void Clear();
00249   bool Empty() const;
00250   void Push(ElementWrapperType element);
00251 
00252   const ElementWrapperType & Peek() const;
00253 
00254   void Pop();
00255 
00259   bool Update( const ElementWrapperType& element);
00260 
00264   bool DeleteElement( const ElementWrapperType& element);
00265 
00266 protected:
00267 
00268   // One instance of the interface to deal with the functions calls
00269   ElementInterfaceType m_Interface;
00270 
00271   inline ElementWrapperType & GetElementAtLocation( const ElementIdentifierType & identifier )
00272   {
00273     return this->operator[](identifier);
00274   }
00275 
00276   inline const ElementWrapperType & GetElementAtLocation(const ElementIdentifierType & identifier) const
00277   {
00278     return this->operator[](identifier);
00279   }
00280 
00281   inline void SetElementAtLocation(const ElementIdentifierType & identifier,
00282                                    ElementWrapperType& element)
00283   {
00284     this->operator[](identifier) = element;
00285     m_Interface.SetLocation(element, identifier);
00286   }
00287 
00288   inline ElementIdentifierType GetParent(const ElementIdentifierType & identifier) const
00289   {
00290     return ( ( identifier - 1 ) >> 1 );
00291   }
00292 
00293   inline ElementIdentifierType GetLeft(const ElementIdentifierType & identifier) const
00294   {
00295     return ( ( identifier << 1 ) + 1 );
00296   }
00297 
00298   inline ElementIdentifierType GetRight(const ElementIdentifierType & identifier) const
00299   {
00300     return ( ( identifier << 1 ) + 2 );
00301   }
00302 
00303   inline bool HasParent( const ElementIdentifierType& iId ) const
00304     {
00305     return ( iId > 0 );
00306     }
00307 
00308   void UpdateUpTree(const ElementIdentifierType & identifier);
00309 
00310 
00311   void UpdateDownTree(const ElementIdentifierType & identifier);
00312 
00313 };
00314 // ------------------------------------------------------------------------
00315 
00316 }
00317 
00318 #include "itkPriorityQueueContainer.hxx"
00319 #endif
00320