ITK  5.3.0
Insight Toolkit
itkPriorityQueueContainer.h
Go to the documentation of this file.
1 /*=========================================================================
2  *
3  * Copyright NumFOCUS
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, typename TElementIdentifier = IdentifierType>
36 class ITK_TEMPLATE_EXPORT ElementWrapperInterface
37 {
38 public:
39  using ElementType = TElement;
40  using ElementIdentifierType = TElementIdentifier;
41 
43 
44  ElementWrapperInterface() = default;
45  virtual ~ElementWrapperInterface() = default;
46 
47  virtual ElementIdentifierType
48  GetLocation(const ElementType & element) const = 0;
49 
50  virtual void
51  SetLocation(ElementType & element, const ElementIdentifierType & identifier) = 0;
52 
53  virtual bool
54  is_less(const ElementType & element1, const ElementType & element2) const = 0;
55 
56  virtual bool
57  is_greater(const ElementType & element1, const ElementType & element2) const = 0;
58 };
59 // ------------------------------------------------------------------------
60 
61 
62 // ------------------------------------------------------------------------
63 // If you want to manage the items outside the queue for example, if you don't
64 // want the queue to manage the items memory, then you can use this wrapper
65 // around pointers to items. It follows the ElementWrapperInterface and thus
66 // can be used in the queue.
67 //
68 template <typename TElementWrapperPointer, typename TElementIdentifier = IdentifierType>
69 class ITK_TEMPLATE_EXPORT ElementWrapperPointerInterface
70 {
71 public:
72  using ElementWrapperPointerType = TElementWrapperPointer;
73  using ElementIdentifierType = TElementIdentifier;
74 
76 
78  virtual ~ElementWrapperPointerInterface() = default;
79 
80  TElementIdentifier
81  GetLocation(const ElementWrapperPointerType & element) const;
82 
83  void
84  SetLocation(ElementWrapperPointerType & element, const ElementIdentifierType & identifier);
85 
86  virtual bool
87  is_less(const ElementWrapperPointerType & element1, const ElementWrapperPointerType & element2) const;
88 
89  virtual bool
90  is_greater(const ElementWrapperPointerType & element1, const ElementWrapperPointerType & element2) const;
91 };
92 // ------------------------------------------------------------------------
93 
94 // ------------------------------------------------------------------------
95 // To follow ITK rule, we template the ElementWrapperType priority and the element
96 // identifier type.
97 // For example, as we want to use this for decimation, the element will be some
98 // kind of cell or point pointer, the priority will be whatever you want it to
99 // be as long as you define the comparison operators, and the identifier will
100 // set according to the size of the vector you want to create.
101 //
102 // this implementation is used for min sorted priorityqueue
103 template <typename TElement, typename TElementPriority = double, typename TElementIdentifier = IdentifierType>
104 class ITK_TEMPLATE_EXPORT MinPriorityQueueElementWrapper
105  : public ElementWrapperInterface<MinPriorityQueueElementWrapper<TElement, TElementPriority, TElementIdentifier>,
106  TElementIdentifier>
107 {
108 public:
110  using ElementType = TElement;
111  using ElementPriorityType = TElementPriority;
112  using ElementIdentifierType = TElementIdentifier;
113 
117 
119 
121 
122  ~MinPriorityQueueElementWrapper() override = default;
123 
124  bool
125  operator>(const MinPriorityQueueElementWrapper & other) const;
126 
127  bool
128  operator<(const MinPriorityQueueElementWrapper & other) const;
129 
130  bool
131  operator==(const MinPriorityQueueElementWrapper & other) const;
132 
134  GetLocation(const MinPriorityQueueElementWrapper & element) const override;
135 
136  void
137  SetLocation(MinPriorityQueueElementWrapper & element, const ElementIdentifierType & identifier) override;
138 
139  // still virtual to be able to overload it in the Max flavor
140  bool
141  is_less(const MinPriorityQueueElementWrapper & element1,
142  const MinPriorityQueueElementWrapper & element2) const override;
143 
144  bool
145  is_greater(const MinPriorityQueueElementWrapper & element1,
146  const MinPriorityQueueElementWrapper & element2) const override;
147 };
148 // ------------------------------------------------------------------------
149 
150 
151 // ------------------------------------------------------------------------
152 // this implementation is used for max sorted priorityqueue
153 // most of the job is already done, just need to overload the less
154 // and greater ops.
155 template <typename TElement, typename TElementPriority = double, typename TElementIdentifier = IdentifierType>
156 class ITK_TEMPLATE_EXPORT MaxPriorityQueueElementWrapper
157  : public MinPriorityQueueElementWrapper<TElement, TElementPriority, TElementIdentifier>
158 {
159 public:
160  using ElementType = TElement;
161  using ElementPriorityType = TElementPriority;
162  using ElementIdentifierType = TElementIdentifier;
163 
166 
168 
169  ~MaxPriorityQueueElementWrapper() override = default;
170 
171  virtual bool
172  is_less(const MaxPriorityQueueElementWrapper & element1, const MaxPriorityQueueElementWrapper & element2) const;
173 
174  bool
175  is_less(const Superclass & element1, const Superclass & element2) const override;
176 
177  virtual bool
178  is_greater(const MaxPriorityQueueElementWrapper & element1, const MaxPriorityQueueElementWrapper & element2) const;
179 
180  bool
181  is_greater(const Superclass & element1, const Superclass & element2) const override;
182 };
183 // ------------------------------------------------------------------------
184 
185 
186 // ------------------------------------------------------------------------
187 // finally, implement the priority queue itself on top of an
188 // itk::VectorContainer
189 template <typename TElementWrapper,
190  typename TElementWrapperInterface,
191  typename TElementPriority = double,
192  typename TElementIdentifier = IdentifierType>
193 class ITK_TEMPLATE_EXPORT PriorityQueueContainer : public VectorContainer<TElementIdentifier, TElementWrapper>
194 {
195 public:
200 
201  using ElementIdentifierType = TElementIdentifier;
202  using ElementWrapperType = TElementWrapper;
203  using ElementInterfaceType = TElementWrapperInterface;
204 
206 
207 public:
209  ~PriorityQueueContainer() override = default;
210 
211  template <typename TInputIterator>
212  PriorityQueueContainer(TInputIterator first, TInputIterator last)
213  : Superclass()
214  {
215  TInputIterator it = first;
216  while (it != last)
217  {
218  this->Push(*it);
219  ++it;
220  }
221  }
222 
223 public:
224  itkNewMacro(Self);
226 
227  // void Reserve( ElementIdentifier NbOfElementsToStore )
228  //{ this->Superclass->Reserve( NbOfElementsToStore ); }
229  // void Squeeze( ) { this->Superclass->Squeeze( ); }
230  void
231  Clear();
232  bool
233  Empty() const;
234  void
235  Push(ElementWrapperType element);
236 
237  const ElementWrapperType &
238  Peek() const;
239 
240  void
241  Pop();
242 
246  bool
247  Update(const ElementWrapperType & element);
248 
252  bool
253  DeleteElement(const ElementWrapperType & element);
254 
255 protected:
256  // One instance of the interface to deal with the functions calls
258 
259  inline ElementWrapperType &
261  {
262  return this->operator[](identifier);
263  }
264 
265  inline const ElementWrapperType &
266  GetElementAtLocation(const ElementIdentifierType & identifier) const
267  {
268  return this->operator[](identifier);
269  }
270 
271  inline void
273  {
274  this->operator[](identifier) = element;
275  m_Interface.SetLocation(element, identifier);
276  }
277 
278  inline ElementIdentifierType
279  GetParent(const ElementIdentifierType & identifier) const
280  {
281  return ((identifier - 1) >> 1);
282  }
283 
284  inline ElementIdentifierType
285  GetLeft(const ElementIdentifierType & identifier) const
286  {
287  return ((identifier << 1) + 1);
288  }
289 
290  inline ElementIdentifierType
291  GetRight(const ElementIdentifierType & identifier) const
292  {
293  return ((identifier << 1) + 2);
294  }
295 
296  inline bool
297  HasParent(const ElementIdentifierType & iId) const
298  {
299  return (iId > 0);
300  }
301 
302  void
303  UpdateUpTree(const ElementIdentifierType & identifier);
304 
305 
306  void
307  UpdateDownTree(const ElementIdentifierType & identifier);
308 };
309 // ------------------------------------------------------------------------
310 
311 } // namespace itk
312 
313 #include "itkPriorityQueueContainer.hxx"
314 #endif
itk::PriorityQueueContainer::ElementWrapperType
TElementWrapper ElementWrapperType
Definition: itkPriorityQueueContainer.h:202
itk::ElementWrapperInterface< MinPriorityQueueElementWrapper< TElement, TElementPriority, TElementIdentifier >, TElementIdentifier >::ElementIdentifierType
TElementIdentifier ElementIdentifierType
Definition: itkPriorityQueueContainer.h:40
itk::operator<
bool operator<(const Index< VDimension > &one, const Index< VDimension > &two)
Definition: itkIndex.h:546
itk::PriorityQueueContainer::GetParent
ElementIdentifierType GetParent(const ElementIdentifierType &identifier) const
Definition: itkPriorityQueueContainer.h:279
itk::MinPriorityQueueElementWrapper::m_Location
ElementIdentifierType m_Location
Definition: itkPriorityQueueContainer.h:116
itk::PriorityQueueContainer::HasParent
bool HasParent(const ElementIdentifierType &iId) const
Definition: itkPriorityQueueContainer.h:297
itk::PriorityQueueContainer::GetElementAtLocation
ElementWrapperType & GetElementAtLocation(const ElementIdentifierType &identifier)
Definition: itkPriorityQueueContainer.h:260
itk::SmartPointer< Self >
itk::PriorityQueueContainer::ElementInterfaceType
TElementWrapperInterface ElementInterfaceType
Definition: itkPriorityQueueContainer.h:203
itk::ElementWrapperInterface
Definition: itkPriorityQueueContainer.h:36
itk::ElementWrapperInterface::m_ElementNotFound
static const ElementIdentifierType m_ElementNotFound
Definition: itkPriorityQueueContainer.h:42
itk::LightObject
Light weight base class for most itk classes.
Definition: itkLightObject.h:59
itk::PriorityQueueContainer::SetElementAtLocation
void SetElementAtLocation(const ElementIdentifierType &identifier, ElementWrapperType &element)
Definition: itkPriorityQueueContainer.h:272
itk::MinPriorityQueueElementWrapper::m_Element
ElementType m_Element
Definition: itkPriorityQueueContainer.h:114
itk::PriorityQueueContainer::GetLeft
ElementIdentifierType GetLeft(const ElementIdentifierType &identifier) const
Definition: itkPriorityQueueContainer.h:285
itk::PriorityQueueContainer::m_Interface
ElementInterfaceType m_Interface
Definition: itkPriorityQueueContainer.h:257
itk::PriorityQueueContainer::GetRight
ElementIdentifierType GetRight(const ElementIdentifierType &identifier) const
Definition: itkPriorityQueueContainer.h:291
itk::operator>
bool operator>(const Index< VDimension > &one, const Index< VDimension > &two)
Definition: itkIndex.h:553
itk::PriorityQueueContainer::PriorityQueueContainer
PriorityQueueContainer(TInputIterator first, TInputIterator last)
Definition: itkPriorityQueueContainer.h:212
itk::operator==
bool operator==(const Index< VDimension > &one, const Index< VDimension > &two)
Definition: itkIndex.h:532
itk::PriorityQueueContainer::GetElementAtLocation
const ElementWrapperType & GetElementAtLocation(const ElementIdentifierType &identifier) const
Definition: itkPriorityQueueContainer.h:266
itkIntTypes.h
itk::ElementWrapperPointerInterface::ElementWrapperPointerType
TElementWrapperPointer ElementWrapperPointerType
Definition: itkPriorityQueueContainer.h:72
itk::PriorityQueueContainer::m_ElementNotFound
static const ElementIdentifierType m_ElementNotFound
Definition: itkPriorityQueueContainer.h:205
itk::ElementWrapperPointerInterface::m_ElementNotFound
static const ElementIdentifierType m_ElementNotFound
Definition: itkPriorityQueueContainer.h:75
itk::MinPriorityQueueElementWrapper::ElementPriorityType
TElementPriority ElementPriorityType
Definition: itkPriorityQueueContainer.h:111
itkVectorContainer.h
itk
The "itk" namespace contains all Insight Segmentation and Registration Toolkit (ITK) classes....
Definition: itkAnnulusOperator.h:24
itk::MinPriorityQueueElementWrapper::ElementType
TElement ElementType
Definition: itkPriorityQueueContainer.h:110
itk::ElementWrapperPointerInterface::ElementIdentifierType
TElementIdentifier ElementIdentifierType
Definition: itkPriorityQueueContainer.h:73
itk::ElementWrapperPointerInterface
Definition: itkPriorityQueueContainer.h:69
itkNumericTraits.h
itk::MinPriorityQueueElementWrapper::m_Priority
ElementPriorityType m_Priority
Definition: itkPriorityQueueContainer.h:115
itk::MinPriorityQueueElementWrapper
Definition: itkPriorityQueueContainer.h:104
itk::PriorityQueueContainer::ElementIdentifierType
TElementIdentifier ElementIdentifierType
Definition: itkPriorityQueueContainer.h:201
itk::IdentifierType
SizeValueType IdentifierType
Definition: itkIntTypes.h:87
itk::VectorContainer
Define a front-end to the STL "vector" container that conforms to the IndexedContainerInterface.
Definition: itkVectorContainer.h:48
itk::MinPriorityQueueElementWrapper::ElementIdentifierType
TElementIdentifier ElementIdentifierType
Definition: itkPriorityQueueContainer.h:112
itk::PriorityQueueContainer
Definition: itkPriorityQueueContainer.h:193
itk::MaxPriorityQueueElementWrapper
Definition: itkPriorityQueueContainer.h:156