ITK  4.4.0
Insight Segmentation and Registration Toolkit
itkPriorityQueueContainer.h
Go to the documentation of this file.
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 >
38 {
39 public:
40  typedef TElement ElementType;
41  typedef TElementIdentifier ElementIdentifierType;
42 
44 
46  virtual ~ElementWrapperInterface();
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 >
70 {
71 public:
72  typedef TElementWrapperPointer ElementWrapperPointerType;
73  typedef TElementIdentifier ElementIdentifierType;
74 
76 
79 
80  TElementIdentifier GetLocation(const ElementWrapperPointerType & element) const;
81 
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  >
109  MinPriorityQueueElementWrapper< TElement,
110  TElementPriority,
111  TElementIdentifier >,
112  TElementIdentifier
113  >
114 {
115 public:
116  typedef MinPriorityQueueElementWrapper< TElement,
117  TElementPriority,
118  TElementIdentifier > Superclass;
119  typedef TElement ElementType;
120  typedef TElementPriority ElementPriorityType;
121  typedef TElementIdentifier ElementIdentifierType;
122 
126 
128 
130  ElementPriorityType priority);
131 
133 
134  bool operator>(const MinPriorityQueueElementWrapper & other) const;
135 
136  bool operator<(const MinPriorityQueueElementWrapper & other) const;
137 
138  bool operator==(const MinPriorityQueueElementWrapper & other) const;
139 
141 
143  const ElementIdentifierType & identifier);
144 
145  // still virtual to be able to overload it in the Max flavor
146  virtual bool is_less(const MinPriorityQueueElementWrapper & element1,
147  const MinPriorityQueueElementWrapper & element2) const;
148 
149  virtual bool is_greater(const MinPriorityQueueElementWrapper & element1,
150  const MinPriorityQueueElementWrapper & element2) const;
151 
152 };
153 // ------------------------------------------------------------------------
154 
155 
156 // ------------------------------------------------------------------------
157 // this implementation is used for max sorted priorityqueue
158 // most of the job is already done, just need to overload the less
159 // and greater ops.
160 template<
161  typename TElement,
162  typename TElementPriority = double,
163  typename TElementIdentifier = IdentifierType
164  >
166  public MinPriorityQueueElementWrapper< TElement,
167  TElementPriority,
168  TElementIdentifier >
169 {
170 public:
171  typedef TElement ElementType;
172  typedef TElementPriority ElementPriorityType;
173  typedef TElementIdentifier ElementIdentifierType;
174 
179 
181  ElementPriorityType priority);
182 
184 
185  virtual bool is_less(const MaxPriorityQueueElementWrapper & element1,
186  const MaxPriorityQueueElementWrapper & element2) const;
187 
188  virtual bool is_less(const Superclass & element1,
189  const Superclass & element2) const;
190 
191  virtual bool is_greater(const MaxPriorityQueueElementWrapper & element1,
192  const MaxPriorityQueueElementWrapper & element2) const;
193 
194  virtual bool is_greater(const Superclass & element1,
195  const Superclass & element2) const;
196 
197 };
198 // ------------------------------------------------------------------------
199 
200 
201 // ------------------------------------------------------------------------
202 // finally, implement the priority queue itself on top of an
203 // itk::VectorContainer
204 template<
205  typename TElementWrapper,
206  typename TElementWrapperInterface,
207  typename TElementPriority = double,
208  typename TElementIdentifier = IdentifierType
209  >
211  public VectorContainer< TElementIdentifier, TElementWrapper >
212 {
213 public:
218 
219  typedef TElementIdentifier ElementIdentifierType;
220  typedef TElementWrapper ElementWrapperType;
221  typedef TElementWrapperInterface ElementInterfaceType;
222 
224 
225 public:
228 
229  template< class TInputIterator >
230  PriorityQueueContainer(TInputIterator first, TInputIterator last):
231  Superclass()
232  {
233  TInputIterator it = first;
234  while( it != last )
235  {
236  this->Push( *it );
237  ++it;
238  }
239  }
240 
241 public:
242  itkNewMacro(Self);
244 
245  //void Reserve( ElementIdentifier NbOfElementsToStore )
246  //{ this->Superclass->Reserve( NbOfElementsToStore ); }
247  //void Squeeze( ) { this->Superclass->Squeeze( ); }
248  void Clear();
249  bool Empty() const;
250  void Push(ElementWrapperType element);
251 
252  const ElementWrapperType & Peek() const;
253 
254  void Pop();
255 
259  bool Update( const ElementWrapperType& element);
260 
264  bool DeleteElement( const ElementWrapperType& element);
265 
266 protected:
267 
268  // One instance of the interface to deal with the functions calls
270 
272  {
273  return this->operator[](identifier);
274  }
275 
276  inline const ElementWrapperType & GetElementAtLocation(const ElementIdentifierType & identifier) const
277  {
278  return this->operator[](identifier);
279  }
280 
281  inline void SetElementAtLocation(const ElementIdentifierType & identifier,
282  ElementWrapperType& element)
283  {
284  this->operator[](identifier) = element;
285  m_Interface.SetLocation(element, identifier);
286  }
287 
288  inline ElementIdentifierType GetParent(const ElementIdentifierType & identifier) const
289  {
290  return ( ( identifier - 1 ) >> 1 );
291  }
292 
293  inline ElementIdentifierType GetLeft(const ElementIdentifierType & identifier) const
294  {
295  return ( ( identifier << 1 ) + 1 );
296  }
297 
298  inline ElementIdentifierType GetRight(const ElementIdentifierType & identifier) const
299  {
300  return ( ( identifier << 1 ) + 2 );
301  }
302 
303  inline bool HasParent( const ElementIdentifierType& iId ) const
304  {
305  return ( iId > 0 );
306  }
307 
308  void UpdateUpTree(const ElementIdentifierType & identifier);
309 
310 
311  void UpdateDownTree(const ElementIdentifierType & identifier);
312 
313 };
314 // ------------------------------------------------------------------------
315 
316 }
317 
318 #include "itkPriorityQueueContainer.hxx"
319 #endif
320