1 /*========================================================================= 2 * 3 * Copyright Insight Software Consortium 4 * 5 * Licensed under the Apache License, Version 2.0 (the "License"); 6 * you may not use this file except in compliance with the License. 7 * You may obtain a copy of the License at 8 * 9 * http://www.apache.org/licenses/LICENSE-2.0.txt 10 * 11 * Unless required by applicable law or agreed to in writing, software 12 * distributed under the License is distributed on an "AS IS" BASIS, 13 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 14 * See the License for the specific language governing permissions and 15 * limitations under the License. 16 * 17 *=========================================================================*/ 18 #ifndef itkPriorityQueueContainer_h 19 #define itkPriorityQueueContainer_h 20 21 #include "itkVectorContainer.h" 22 #include "itkIntTypes.h" 23 #include "itkNumericTraits.h" 24 25 #include <functional> 26 #include <queue> 27 #include <vector> 28 29 namespace itk 30 { 31 // first define a common interface all the wrapper will have to abide to 32 // this will let us define our own wrapper with different behavior. 33 // As an example we define below a wrapper for a min sorted or max sorted 34 // queue. 35 template< typename TElement, 36 typename TElementIdentifier = IdentifierType > 37 class ITK_TEMPLATE_EXPORT ElementWrapperInterface 38 { 39 public: 40 using ElementType = TElement; 41 using ElementIdentifierType = TElementIdentifier; 42 43 static const ElementIdentifierType m_ElementNotFound; 44 45 ElementWrapperInterface() = default; 46 virtual ~ElementWrapperInterface() = default; 47 48 virtual ElementIdentifierType GetLocation(const ElementType & element) const = 0; 49 50 virtual void SetLocation(ElementType & element, const ElementIdentifierType & identifier) = 0; 51 52 virtual bool is_less(const ElementType & element1, 53 const ElementType & element2) const = 0; 54 55 virtual bool is_greater(const ElementType & element1, 56 const ElementType & element2) const = 0; 57 }; 58 // ------------------------------------------------------------------------ 59 60 61 // ------------------------------------------------------------------------ 62 // If you want to manage the items outside the queue for example, if you don't 63 // want the queue to manage the items memory, then you can use this wrapper 64 // around pointers to items. It follows the ElementWrapperInterface and thus 65 // can be used in the queue. 66 // 67 template< typename TElementWrapperPointer, 68 typename TElementIdentifier = IdentifierType > 69 class ITK_TEMPLATE_EXPORT ElementWrapperPointerInterface 70 { 71 public: 72 using ElementWrapperPointerType = TElementWrapperPointer; 73 using ElementIdentifierType = TElementIdentifier; 74 75 static const ElementIdentifierType m_ElementNotFound; 76 77 ElementWrapperPointerInterface() = default; 78 virtual ~ElementWrapperPointerInterface() = default; 79 80 TElementIdentifier GetLocation(const ElementWrapperPointerType & element) const; 81 82 void SetLocation(ElementWrapperPointerType & element, 83 const ElementIdentifierType & identifier); 84 85 virtual bool is_less(const ElementWrapperPointerType & element1, 86 const ElementWrapperPointerType & element2) const; 87 88 virtual bool is_greater(const ElementWrapperPointerType & element1, 89 const ElementWrapperPointerType & element2) const; 90 }; 91 // ------------------------------------------------------------------------ 92 93 // ------------------------------------------------------------------------ 94 // To follow ITK rule, we template the ElementWrapperType priority and the element 95 // identifier type. 96 // For example, as we want to use this for decimation, the element will be some 97 // kind of cell or point pointer, the priority will be whatever you want it to 98 // be as long as you define the comparison operators, and the identifier will 99 // set according to the size of the vector you want to create. 100 // 101 // this implementation is used for min sorted priorityqueue 102 template< 103 typename TElement, 104 typename TElementPriority = double, 105 typename TElementIdentifier = IdentifierType 106 > 107 class ITK_TEMPLATE_EXPORT MinPriorityQueueElementWrapper: 108 public ElementWrapperInterface< 109 MinPriorityQueueElementWrapper< TElement, 110 TElementPriority, 111 TElementIdentifier >, 112 TElementIdentifier 113 > 114 { 115 public: 116 using Superclass = MinPriorityQueueElementWrapper< TElement, 117 TElementPriority, TElementIdentifier >; 118 using ElementType = TElement; 119 using ElementPriorityType = TElementPriority; 120 using ElementIdentifierType = TElementIdentifier; 121 122 ElementType m_Element; 123 ElementPriorityType m_Priority; 124 ElementIdentifierType m_Location; 125 126 MinPriorityQueueElementWrapper(); 127 128 MinPriorityQueueElementWrapper(ElementType element, 129 ElementPriorityType priority); 130 131 ~MinPriorityQueueElementWrapper() override = default; 132 133 bool operator>(const MinPriorityQueueElementWrapper & other) const; 134 135 bool operator<(const MinPriorityQueueElementWrapper & other) const; 136 137 bool operator==(const MinPriorityQueueElementWrapper & other) const; 138 139 ElementIdentifierType GetLocation(const MinPriorityQueueElementWrapper & element) const override; 140 141 void SetLocation(MinPriorityQueueElementWrapper & element, 142 const ElementIdentifierType & identifier) override; 143 144 // still virtual to be able to overload it in the Max flavor 145 bool is_less(const MinPriorityQueueElementWrapper & element1, 146 const MinPriorityQueueElementWrapper & element2) const override; 147 148 bool is_greater(const MinPriorityQueueElementWrapper & element1, 149 const MinPriorityQueueElementWrapper & element2) const override; 150 151 }; 152 // ------------------------------------------------------------------------ 153 154 155 // ------------------------------------------------------------------------ 156 // this implementation is used for max sorted priorityqueue 157 // most of the job is already done, just need to overload the less 158 // and greater ops. 159 template< 160 typename TElement, 161 typename TElementPriority = double, 162 typename TElementIdentifier = IdentifierType 163 > 164 class ITK_TEMPLATE_EXPORT MaxPriorityQueueElementWrapper: 165 public MinPriorityQueueElementWrapper< TElement, 166 TElementPriority, 167 TElementIdentifier > 168 { 169 public: 170 using ElementType = TElement; 171 using ElementPriorityType = TElementPriority; 172 using ElementIdentifierType = TElementIdentifier; 173 174 using Superclass = MinPriorityQueueElementWrapper< ElementType, 175 ElementPriorityType, 176 ElementIdentifierType >; 177 MaxPriorityQueueElementWrapper(); 178 179 MaxPriorityQueueElementWrapper(ElementType element, 180 ElementPriorityType priority); 181 182 ~MaxPriorityQueueElementWrapper() override = default; 183 184 virtual bool is_less(const MaxPriorityQueueElementWrapper & element1, 185 const MaxPriorityQueueElementWrapper & element2) const; 186 187 bool is_less(const Superclass & element1, 188 const Superclass & element2) const override; 189 190 virtual bool is_greater(const MaxPriorityQueueElementWrapper & element1, 191 const MaxPriorityQueueElementWrapper & element2) const; 192 193 bool is_greater(const Superclass & element1, 194 const Superclass & element2) const override; 195 196 }; 197 // ------------------------------------------------------------------------ 198 199 200 // ------------------------------------------------------------------------ 201 // finally, implement the priority queue itself on top of an 202 // itk::VectorContainer 203 template< 204 typename TElementWrapper, 205 typename TElementWrapperInterface, 206 typename TElementPriority = double, 207 typename TElementIdentifier = IdentifierType 208 > 209 class ITK_TEMPLATE_EXPORT PriorityQueueContainer: 210 public VectorContainer< TElementIdentifier, TElementWrapper > 211 { 212 public: 213 using Self = PriorityQueueContainer; 214 using Superclass = VectorContainer< TElementIdentifier, TElementWrapper >; 215 using Pointer = SmartPointer< Self >; 216 using ConstPointer = SmartPointer< const Self >; 217 218 using ElementIdentifierType = TElementIdentifier; 219 using ElementWrapperType = TElementWrapper; 220 using ElementInterfaceType = TElementWrapperInterface; 221 222 static const ElementIdentifierType m_ElementNotFound; 223 224 public: 225 PriorityQueueContainer(); 226 ~PriorityQueueContainer() override = default; 227 228 template< typename TInputIterator > PriorityQueueContainer(TInputIterator first,TInputIterator last)229 PriorityQueueContainer(TInputIterator first, TInputIterator last): 230 Superclass() 231 { 232 TInputIterator it = first; 233 while( it != last ) 234 { 235 this->Push( *it ); 236 ++it; 237 } 238 } 239 240 public: 241 itkNewMacro(Self); 242 itkTypeMacro(PriorityQueueContainer, VectorContainer); 243 244 //void Reserve( ElementIdentifier NbOfElementsToStore ) 245 //{ this->Superclass->Reserve( NbOfElementsToStore ); } 246 //void Squeeze( ) { this->Superclass->Squeeze( ); } 247 void Clear(); 248 bool Empty() const; 249 void Push(ElementWrapperType element); 250 251 const ElementWrapperType & Peek() const; 252 253 void Pop(); 254 255 /** Update element in container. 256 \return true if the element is in the priority queue 257 \return false else */ 258 bool Update( const ElementWrapperType& element); 259 260 /** Delete element in the container. 261 \return true if the element is in the priority queue 262 \return false else */ 263 bool DeleteElement( const ElementWrapperType& element); 264 265 protected: 266 267 // One instance of the interface to deal with the functions calls 268 ElementInterfaceType m_Interface; 269 GetElementAtLocation(const ElementIdentifierType & identifier)270 inline ElementWrapperType & GetElementAtLocation( const ElementIdentifierType & identifier ) 271 { 272 return this->operator[](identifier); 273 } 274 GetElementAtLocation(const ElementIdentifierType & identifier)275 inline const ElementWrapperType & GetElementAtLocation(const ElementIdentifierType & identifier) const 276 { 277 return this->operator[](identifier); 278 } 279 SetElementAtLocation(const ElementIdentifierType & identifier,ElementWrapperType & element)280 inline void SetElementAtLocation(const ElementIdentifierType & identifier, 281 ElementWrapperType& element) 282 { 283 this->operator[](identifier) = element; 284 m_Interface.SetLocation(element, identifier); 285 } 286 GetParent(const ElementIdentifierType & identifier)287 inline ElementIdentifierType GetParent(const ElementIdentifierType & identifier) const 288 { 289 return ( ( identifier - 1 ) >> 1 ); 290 } 291 GetLeft(const ElementIdentifierType & identifier)292 inline ElementIdentifierType GetLeft(const ElementIdentifierType & identifier) const 293 { 294 return ( ( identifier << 1 ) + 1 ); 295 } 296 GetRight(const ElementIdentifierType & identifier)297 inline ElementIdentifierType GetRight(const ElementIdentifierType & identifier) const 298 { 299 return ( ( identifier << 1 ) + 2 ); 300 } 301 HasParent(const ElementIdentifierType & iId)302 inline bool HasParent( const ElementIdentifierType& iId ) const 303 { 304 return ( iId > 0 ); 305 } 306 307 void UpdateUpTree(const ElementIdentifierType & identifier); 308 309 310 void UpdateDownTree(const ElementIdentifierType & identifier); 311 312 }; 313 // ------------------------------------------------------------------------ 314 315 } 316 317 #include "itkPriorityQueueContainer.hxx" 318 #endif 319