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