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
19 #ifndef itkPriorityQueueContainer_hxx
20 #define itkPriorityQueueContainer_hxx
21
22 #include <utility>
23
24 #include "itkNumericTraits.h"
25 #include "itkPriorityQueueContainer.h"
26
27 namespace itk
28 {
29
30 // -----------------------------------------------------------------------------
31 template< typename TElement,
32 typename TElementIdentifier >
33 const
34 typename ElementWrapperInterface< TElement, TElementIdentifier >::ElementIdentifierType
35 ElementWrapperInterface< TElement, TElementIdentifier >::m_ElementNotFound
36 = NumericTraits< TElementIdentifier >::max();
37 // -----------------------------------------------------------------------------
38 // -----------------------------------------------------------------------------
39 // -----------------------------------------------------------------------------
40 // -----------------------------------------------------------------------------
41 template< typename TElementWrapperPointer,
42 typename TElementIdentifier >
43 typename ElementWrapperPointerInterface< TElementWrapperPointer, TElementIdentifier >::
44 ElementIdentifierType
45 ElementWrapperPointerInterface< TElementWrapperPointer, TElementIdentifier >::
GetLocation(const ElementWrapperPointerType & element) const46 GetLocation(const ElementWrapperPointerType & element) const
47 {
48 return ( ( *element ).GetLocation(*element) );
49 }
50 // -----------------------------------------------------------------------------
51
52 // -----------------------------------------------------------------------------
53 template< typename TElementWrapperPointer,
54 typename TElementIdentifier >
55 void
56 ElementWrapperPointerInterface< TElementWrapperPointer, TElementIdentifier >::
SetLocation(ElementWrapperPointerType & element,const ElementIdentifierType & identifier)57 SetLocation(ElementWrapperPointerType & element,
58 const ElementIdentifierType & identifier)
59 {
60 ( *element ).SetLocation(*element, identifier);
61 }
62 // -----------------------------------------------------------------------------
63
64 // -----------------------------------------------------------------------------
65 template< typename TElementWrapperPointer,
66 typename TElementIdentifier >
67 bool
68 ElementWrapperPointerInterface< TElementWrapperPointer, TElementIdentifier >::
is_less(const ElementWrapperPointerType & element1,const ElementWrapperPointerType & element2) const69 is_less(const ElementWrapperPointerType & element1,
70 const ElementWrapperPointerType & element2) const
71 {
72 return ( ( *element1 ).is_less( ( *element1 ), ( *element2 ) ) );
73 }
74 // -----------------------------------------------------------------------------
75
76 // -----------------------------------------------------------------------------
77 template< typename TElementWrapperPointer,
78 typename TElementIdentifier >
79 bool
80 ElementWrapperPointerInterface< TElementWrapperPointer, TElementIdentifier >::
is_greater(const ElementWrapperPointerType & element1,const ElementWrapperPointerType & element2) const81 is_greater(const ElementWrapperPointerType & element1,
82 const ElementWrapperPointerType & element2) const
83 {
84 return ( ( *element1 ).is_greater( ( *element1 ), ( *element2 ) ) );
85 }
86 // -----------------------------------------------------------------------------
87
88 // -----------------------------------------------------------------------------
89 template< typename TElement,
90 typename TElementIdentifier >
91 const TElementIdentifier
92 ElementWrapperPointerInterface< TElement, TElementIdentifier >::m_ElementNotFound
93 = NumericTraits< TElementIdentifier >::max();
94 // -----------------------------------------------------------------------------
95 // -----------------------------------------------------------------------------
96 // -----------------------------------------------------------------------------
97
98
99 // -----------------------------------------------------------------------------
100 // MinPriorityQueueElementWrapper
101 // -----------------------------------------------------------------------------
102 template< typename TElement, typename TElementPriority, typename TElementIdentifier > MinPriorityQueueElementWrapper< TElement, TElementPriority, TElementIdentifier >::
MinPriorityQueueElementWrapper()103 MinPriorityQueueElementWrapper() :
104 m_Element(0),
105 m_Priority(0),
106 m_Location( Superclass::m_ElementNotFound )
107 {}
108 // -----------------------------------------------------------------------------
109
110 // -----------------------------------------------------------------------------
111 template< typename TElement, typename TElementPriority, typename TElementIdentifier > MinPriorityQueueElementWrapper< TElement, TElementPriority, TElementIdentifier >::
MinPriorityQueueElementWrapper(ElementType element,ElementPriorityType priority)112 MinPriorityQueueElementWrapper(ElementType element, ElementPriorityType priority):
113 m_Element(element), m_Priority(std::move(priority)), m_Location( Superclass::m_ElementNotFound )
114 {}
115 // -----------------------------------------------------------------------------
116
117 // -----------------------------------------------------------------------------
118 template< typename TElement, typename TElementPriority, typename TElementIdentifier >
119 bool
120 MinPriorityQueueElementWrapper< TElement, TElementPriority, TElementIdentifier >::
operator >(const MinPriorityQueueElementWrapper & other) const121 operator>(const MinPriorityQueueElementWrapper & other) const
122 {
123 return this->m_Priority > other.m_Priority;
124 }
125 // -----------------------------------------------------------------------------
126
127 // -----------------------------------------------------------------------------
128 template< typename TElement, typename TElementPriority, typename TElementIdentifier >
129 bool
130 MinPriorityQueueElementWrapper< TElement, TElementPriority, TElementIdentifier >::
operator <(const MinPriorityQueueElementWrapper & other) const131 operator<(const MinPriorityQueueElementWrapper & other) const
132 {
133 return this->m_Priority < other.m_Priority;
134 }
135 // -----------------------------------------------------------------------------
136
137 // -----------------------------------------------------------------------------
138 template< typename TElement, typename TElementPriority, typename TElementIdentifier >
139 bool
140 MinPriorityQueueElementWrapper< TElement, TElementPriority, TElementIdentifier >::
operator ==(const MinPriorityQueueElementWrapper & other) const141 operator==(const MinPriorityQueueElementWrapper & other) const
142 {
143 return this->m_Priority == other.m_Priority;
144 }
145 // -----------------------------------------------------------------------------
146
147 // -----------------------------------------------------------------------------
148 template< typename TElement, typename TElementPriority, typename TElementIdentifier >
149 typename
150 MinPriorityQueueElementWrapper< TElement, TElementPriority, TElementIdentifier >::
151 ElementIdentifierType
152 MinPriorityQueueElementWrapper< TElement, TElementPriority, TElementIdentifier >::
GetLocation(const MinPriorityQueueElementWrapper & element) const153 GetLocation(const MinPriorityQueueElementWrapper & element) const
154 {
155 return element.m_Location;
156 }
157 // -----------------------------------------------------------------------------
158
159 // -----------------------------------------------------------------------------
160 template< typename TElement, typename TElementPriority, typename TElementIdentifier >
161 void
162 MinPriorityQueueElementWrapper< TElement, TElementPriority, TElementIdentifier >::
SetLocation(MinPriorityQueueElementWrapper & element,const ElementIdentifierType & identifier)163 SetLocation(MinPriorityQueueElementWrapper & element,
164 const ElementIdentifierType & identifier)
165 {
166 element.m_Location = identifier;
167 }
168 // -----------------------------------------------------------------------------
169
170 // -----------------------------------------------------------------------------
171 template< typename TElement, typename TElementPriority, typename TElementIdentifier >
172 bool
173 MinPriorityQueueElementWrapper< TElement, TElementPriority, TElementIdentifier >::
is_less(const MinPriorityQueueElementWrapper & element1,const MinPriorityQueueElementWrapper & element2) const174 is_less(const MinPriorityQueueElementWrapper & element1,
175 const MinPriorityQueueElementWrapper & element2) const
176 {
177 return ( element1 < element2 );
178 }
179 // -----------------------------------------------------------------------------
180
181 // -----------------------------------------------------------------------------
182 template< typename TElement, typename TElementPriority, typename TElementIdentifier >
183 bool
184 MinPriorityQueueElementWrapper< TElement, TElementPriority, TElementIdentifier >::
is_greater(const MinPriorityQueueElementWrapper & element1,const MinPriorityQueueElementWrapper & element2) const185 is_greater(const MinPriorityQueueElementWrapper & element1,
186 const MinPriorityQueueElementWrapper & element2) const
187 {
188 return ( element1 > element2 );
189 }
190 // -----------------------------------------------------------------------------
191 // -----------------------------------------------------------------------------
192 // -----------------------------------------------------------------------------
193
194
195 // -----------------------------------------------------------------------------
196 // MaxPriorityQueueElementWrapper
197 // -----------------------------------------------------------------------------
198 template< typename TElement, typename TElementPriority, typename TElementIdentifier > MaxPriorityQueueElementWrapper< TElement, TElementPriority, TElementIdentifier >::
MaxPriorityQueueElementWrapper()199 MaxPriorityQueueElementWrapper() : Superclass()
200 {}
201 // -----------------------------------------------------------------------------
202
203 // -----------------------------------------------------------------------------
204 template< typename TElement, typename TElementPriority, typename TElementIdentifier > MaxPriorityQueueElementWrapper< TElement, TElementPriority, TElementIdentifier >::
MaxPriorityQueueElementWrapper(ElementType element,ElementPriorityType priority)205 MaxPriorityQueueElementWrapper(ElementType element, ElementPriorityType priority):
206 Superclass( element, priority )
207 {}
208 // -----------------------------------------------------------------------------
209
210 // -----------------------------------------------------------------------------
211 template< typename TElement, typename TElementPriority, typename TElementIdentifier >
212 bool
213 MaxPriorityQueueElementWrapper< TElement, TElementPriority, TElementIdentifier >::
is_less(const MaxPriorityQueueElementWrapper & element1,const MaxPriorityQueueElementWrapper & element2) const214 is_less(const MaxPriorityQueueElementWrapper & element1,
215 const MaxPriorityQueueElementWrapper & element2) const
216 {
217 return ( element1 > element2 );
218 }
219 // -----------------------------------------------------------------------------
220
221 // -----------------------------------------------------------------------------
222 template< typename TElement, typename TElementPriority, typename TElementIdentifier >
223 bool
224 MaxPriorityQueueElementWrapper< TElement, TElementPriority, TElementIdentifier >::
is_less(const Superclass & element1,const Superclass & element2) const225 is_less(const Superclass & element1,
226 const Superclass & element2) const
227 {
228 return Superclass::is_less(element1, element2);
229 }
230 // -----------------------------------------------------------------------------
231
232 // -----------------------------------------------------------------------------
233 template< typename TElement, typename TElementPriority, typename TElementIdentifier >
234 bool
235 MaxPriorityQueueElementWrapper< TElement, TElementPriority, TElementIdentifier >::
is_greater(const MaxPriorityQueueElementWrapper & element1,const MaxPriorityQueueElementWrapper & element2) const236 is_greater(const MaxPriorityQueueElementWrapper & element1,
237 const MaxPriorityQueueElementWrapper & element2) const
238 {
239 return ( element1 < element2 );
240 }
241 // -----------------------------------------------------------------------------
242
243 // -----------------------------------------------------------------------------
244 template< typename TElement, typename TElementPriority, typename TElementIdentifier >
245 bool
246 MaxPriorityQueueElementWrapper< TElement, TElementPriority, TElementIdentifier >::
is_greater(const Superclass & element1,const Superclass & element2) const247 is_greater(const Superclass & element1,
248 const Superclass & element2) const
249 {
250 return Superclass::is_greater(element1, element2);
251 }
252 // -----------------------------------------------------------------------------
253 // -----------------------------------------------------------------------------
254 // -----------------------------------------------------------------------------
255
256
257 // -----------------------------------------------------------------------------
258 // PriorityQueueContainer
259 // -----------------------------------------------------------------------------
260 template<
261 typename TElementWrapper,
262 typename TElementWrapperInterface,
263 typename TElementPriority,
264 typename TElementIdentifier
265 >
266 const TElementIdentifier
267 PriorityQueueContainer< TElementWrapper, TElementWrapperInterface,
268 TElementPriority, TElementIdentifier >::m_ElementNotFound
269 = NumericTraits< TElementIdentifier >::max();
270 // -----------------------------------------------------------------------------
271
272 // -----------------------------------------------------------------------------
273 template<
274 typename TElementWrapper,
275 typename TElementWrapperInterface,
276 typename TElementPriority,
277 typename TElementIdentifier
278 >
279 PriorityQueueContainer< TElementWrapper, TElementWrapperInterface,
280 TElementPriority, TElementIdentifier >::
PriorityQueueContainer()281 PriorityQueueContainer() : Superclass() {}
282 // -----------------------------------------------------------------------------
283
284 // -----------------------------------------------------------------------------
285 template<
286 typename TElementWrapper,
287 typename TElementWrapperInterface,
288 typename TElementPriority,
289 typename TElementIdentifier
290 >
291 void
292 PriorityQueueContainer< TElementWrapper, TElementWrapperInterface,
293 TElementPriority, TElementIdentifier >::
Clear()294 Clear()
295 {
296 this->Initialize();
297 }
298 // -----------------------------------------------------------------------------
299
300 // -----------------------------------------------------------------------------
301 template<
302 typename TElementWrapper,
303 typename TElementWrapperInterface,
304 typename TElementPriority,
305 typename TElementIdentifier
306 >
307 bool
308 PriorityQueueContainer< TElementWrapper, TElementWrapperInterface,
309 TElementPriority, TElementIdentifier >::
Empty() const310 Empty() const
311 {
312 return ( this->empty() );
313 }
314 // -----------------------------------------------------------------------------
315
316 // -----------------------------------------------------------------------------
317 template<
318 typename TElementWrapper,
319 typename TElementWrapperInterface,
320 typename TElementPriority,
321 typename TElementIdentifier
322 >
323 void
324 PriorityQueueContainer< TElementWrapper, TElementWrapperInterface,
325 TElementPriority, TElementIdentifier >::
Push(ElementWrapperType element)326 Push( ElementWrapperType element)
327 {
328 this->push_back(element);
329 this->UpdateUpTree( this->Size() - 1);
330 }
331 // -----------------------------------------------------------------------------
332
333 // -----------------------------------------------------------------------------
334 template<
335 typename TElementWrapper,
336 typename TElementWrapperInterface,
337 typename TElementPriority,
338 typename TElementIdentifier
339 >
340 const typename
341 PriorityQueueContainer< TElementWrapper, TElementWrapperInterface,
342 TElementPriority, TElementIdentifier >::
343 ElementWrapperType &
344 PriorityQueueContainer< TElementWrapper, TElementWrapperInterface,
345 TElementPriority, TElementIdentifier >::
Peek() const346 Peek() const
347 {
348 if( Empty() )
349 {
350 itkGenericExceptionMacro( <<"Empty PriorityQueueContainer" );
351 }
352 return ( GetElementAtLocation(0) );
353 }
354 // -----------------------------------------------------------------------------
355
356 // -----------------------------------------------------------------------------
357 template<
358 typename TElementWrapper,
359 typename TElementWrapperInterface,
360 typename TElementPriority,
361 typename TElementIdentifier
362 >
363 void
364 PriorityQueueContainer< TElementWrapper, TElementWrapperInterface,
365 TElementPriority, TElementIdentifier >::
Pop()366 Pop()
367 {
368 m_Interface.SetLocation(this->front(), //GetElementAtLocation(0),
369 m_ElementNotFound);
370 if ( this->Size() > 1 )
371 {
372 SetElementAtLocation( 0, this->back() );// GetElementAtLocation( this->Size() - 1 ) );
373 this->pop_back();
374 UpdateDownTree(0);
375 }
376 else
377 {
378 if ( this->Size() == 1 )
379 {
380 this->pop_back();
381 }
382 }
383 }
384 // -----------------------------------------------------------------------------
385
386 // -----------------------------------------------------------------------------
387 template<
388 typename TElementWrapper,
389 typename TElementWrapperInterface,
390 typename TElementPriority,
391 typename TElementIdentifier
392 >
393 bool
394 PriorityQueueContainer< TElementWrapper, TElementWrapperInterface,
395 TElementPriority, TElementIdentifier >::
Update(const ElementWrapperType & element)396 Update( const ElementWrapperType& element)
397 {
398 ElementIdentifierType location = m_Interface.GetLocation(element);
399
400 if( location != m_ElementNotFound )
401 {
402 if( location >= this->Size() )
403 {
404 itkGenericExceptionMacro( <<" ElementWrapperType location is out of range" );
405 }
406 UpdateDownTree(location);
407 UpdateUpTree(location);
408
409 return true;
410 }
411 return false;
412 }
413 // -----------------------------------------------------------------------------
414
415 // -----------------------------------------------------------------------------
416 template<
417 typename TElementWrapper,
418 typename TElementWrapperInterface,
419 typename TElementPriority,
420 typename TElementIdentifier
421 >
422 bool
423 PriorityQueueContainer< TElementWrapper, TElementWrapperInterface,
424 TElementPriority, TElementIdentifier >::
DeleteElement(const ElementWrapperType & element)425 DeleteElement(const ElementWrapperType & element)
426 {
427 ElementIdentifierType location = m_Interface.GetLocation(element);
428
429 if( location != m_ElementNotFound )
430 {
431 // m_Interface.SetLocation(element, m_ElementNotFound);
432
433 ElementIdentifierType tsize = this->Size();
434
435 if( location >= tsize )
436 {
437 itkGenericExceptionMacro( <<" ElementWrapperType location is out of range" );
438 }
439 else
440 {
441 if ( location == tsize - 1 )
442 {
443 this->pop_back();
444 }
445 else
446 {
447 SetElementAtLocation( location, GetElementAtLocation( tsize - 1 ) );
448 this->pop_back();
449 UpdateDownTree(location);
450 UpdateUpTree(location);
451 }
452 }
453 return true;
454 }
455 return false;
456 }
457 // -----------------------------------------------------------------------------
458
459 // -----------------------------------------------------------------------------
460 template<
461 typename TElementWrapper,
462 typename TElementWrapperInterface,
463 typename TElementPriority,
464 typename TElementIdentifier
465 >
466 void
467 PriorityQueueContainer< TElementWrapper, TElementWrapperInterface,
468 TElementPriority, TElementIdentifier >::
UpdateUpTree(const ElementIdentifierType & identifier)469 UpdateUpTree(const ElementIdentifierType & identifier)
470 {
471 if ( HasParent( identifier ) )
472 {
473 ElementIdentifierType id(identifier);
474 ElementWrapperType element = GetElementAtLocation(id);
475 ElementIdentifierType parentIdentifier = GetParent(id);
476 ElementWrapperType parent_element = GetElementAtLocation(parentIdentifier);
477
478 while ( HasParent( id )
479 && m_Interface.is_less(element, parent_element) )
480 {
481 SetElementAtLocation(id, parent_element);
482 id = parentIdentifier;
483 if ( HasParent( id ) )
484 {
485 parentIdentifier = GetParent(id);
486 parent_element = GetElementAtLocation(parentIdentifier);
487 }
488 }
489 SetElementAtLocation(id, element);
490 }
491 }
492 // -----------------------------------------------------------------------------
493
494 // -----------------------------------------------------------------------------
495 template<
496 typename TElementWrapper,
497 typename TElementWrapperInterface,
498 typename TElementPriority,
499 typename TElementIdentifier
500 >
501 void
502 PriorityQueueContainer< TElementWrapper, TElementWrapperInterface,
503 TElementPriority, TElementIdentifier >::
UpdateDownTree(const ElementIdentifierType & identifier)504 UpdateDownTree(const ElementIdentifierType & identifier)
505 {
506 ElementIdentifierType id(identifier);
507 ElementWrapperType element = GetElementAtLocation(id);
508
509 ElementIdentifierType queueSize = this->Size();
510
511 while ( id < queueSize )
512 {
513 ElementIdentifierType childIdentifier = GetLeft(id);
514 if ( childIdentifier >= queueSize )
515 {
516 break;
517 }
518 if ( ( childIdentifier + 1 < queueSize )
519 && ( m_Interface.is_less( GetElementAtLocation(childIdentifier + 1),
520 GetElementAtLocation(childIdentifier) ) ) )
521 {
522 ++childIdentifier;
523 }
524 ElementWrapperType temp = GetElementAtLocation(childIdentifier);
525 if ( m_Interface.is_less(element, temp) )
526 {
527 break;
528 }
529
530 SetElementAtLocation(id, temp);
531 id = childIdentifier;
532 }
533
534 SetElementAtLocation(id, element);
535 }
536 // -----------------------------------------------------------------------------
537 }
538
539 #endif // itkPriorityQueueContainer_hxx
540