PCL
Sort.h
Go to the documentation of this file.
1 // ____ ______ __
2 // / __ \ / ____// /
3 // / /_/ // / / /
4 // / ____// /___ / /___ PixInsight Class Library
5 // /_/ \____//_____/ PCL 2.6.5
6 // ----------------------------------------------------------------------------
7 // pcl/Sort.h - Released 2024-01-13T15:47:58Z
8 // ----------------------------------------------------------------------------
9 // This file is part of the PixInsight Class Library (PCL).
10 // PCL is a multiplatform C++ framework for development of PixInsight modules.
11 //
12 // Copyright (c) 2003-2024 Pleiades Astrophoto S.L. All Rights Reserved.
13 //
14 // Redistribution and use in both source and binary forms, with or without
15 // modification, is permitted provided that the following conditions are met:
16 //
17 // 1. All redistributions of source code must retain the above copyright
18 // notice, this list of conditions and the following disclaimer.
19 //
20 // 2. All redistributions in binary form must reproduce the above copyright
21 // notice, this list of conditions and the following disclaimer in the
22 // documentation and/or other materials provided with the distribution.
23 //
24 // 3. Neither the names "PixInsight" and "Pleiades Astrophoto", nor the names
25 // of their contributors, may be used to endorse or promote products derived
26 // from this software without specific prior written permission. For written
27 // permission, please contact info@pixinsight.com.
28 //
29 // 4. All products derived from this software, in any form whatsoever, must
30 // reproduce the following acknowledgment in the end-user documentation
31 // and/or other materials provided with the product:
32 //
33 // "This product is based on software from the PixInsight project, developed
34 // by Pleiades Astrophoto and its contributors (https://pixinsight.com/)."
35 //
36 // Alternatively, if that is where third-party acknowledgments normally
37 // appear, this acknowledgment must be reproduced in the product itself.
38 //
39 // THIS SOFTWARE IS PROVIDED BY PLEIADES ASTROPHOTO AND ITS CONTRIBUTORS
40 // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
41 // TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
42 // PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL PLEIADES ASTROPHOTO OR ITS
43 // CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
44 // EXEMPLARY OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, BUSINESS
45 // INTERRUPTION; PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; AND LOSS OF USE,
46 // DATA OR PROFITS) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
47 // CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
48 // ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
49 // POSSIBILITY OF SUCH DAMAGE.
50 // ----------------------------------------------------------------------------
51 
52 #ifndef __PCL_Sort_h
53 #define __PCL_Sort_h
54 
56 
57 #include <pcl/Defs.h>
58 
59 #include <pcl/Iterator.h>
60 #include <pcl/Utility.h>
61 
62 #define __PCL_QS_STACK_SIZE 32 // Stack size for the QuickSort algorithms
63 #define __PCL_QS_IS_THRESHOLD 11 // QuickSort/InsertionSort switch threshold
64 
65 namespace pcl
66 {
67 
68 // ----------------------------------------------------------------------------
69 
84 // ----------------------------------------------------------------------------
85 
86 template <class BI, class T> inline
87 void __pcl_insertion_sort__( BI i, BI j, const T* )
88 {
89  if ( i != j )
90  for ( BI k = i; ++k != j; )
91  {
92  T v = *k;
93  BI y = k;
94  for ( BI x = y; y != i && v < *--x; --y )
95  *y = *x;
96  *y = v;
97  }
98 }
99 
109 template <class BI> inline
110 void InsertionSort( BI i, BI j )
111 {
112  __pcl_insertion_sort__( i, j, ItemType( i ) );
113 }
114 
115 // ----------------------------------------------------------------------------
116 
117 template <class BI, class BP, class T> inline
118 void __pcl_insertion_sort__( BI i, BI j, BP p, const T* )
119 {
120  if ( i != j )
121  for ( BI k = i; ++k != j; )
122  {
123  T v = *k;
124  BI y = k;
125  for ( BI x = y; y != i && p( v, *--x ); --y )
126  *y = *x;
127  *y = v;
128  }
129 }
130 
140 template <class BI, class BP> inline
141 void InsertionSort( BI i, BI j, BP p )
142 {
143  __pcl_insertion_sort__( i, j, p, ItemType( i ) );
144 }
145 
146 // ----------------------------------------------------------------------------
147 
148 template <class RI, class T> inline
149 void __pcl_quick_sort__( RI i, RI j, T* )
150 {
151  distance_type n = j - i;
152  if ( n < 2 )
153  return;
154 
155  distance_type tos[ 2*__PCL_QS_STACK_SIZE ];
156  distance_type* sp = tos;
157 
158  for ( distance_type l = 0, r = n-1; ; )
159  {
160  RI x0 = i + l;
161  RI y = i + r;
162 
163  if ( r-l < __PCL_QS_IS_THRESHOLD )
164  {
165  for ( RI x = x0; ++x <= y; )
166  {
167  T v = *x;
168  RI x1 = x;
169  for ( ; --x1 >= x0 && v < *x1; )
170  *(x1+1) = *x1;
171  *(x1+1) = v;
172  }
173 
174  if ( sp == tos )
175  break;
176 
177  r = *--sp;
178  l = *--sp;
179  }
180  else
181  {
182  RI x = x0;
183 
184  Swap( *++x, *(i + ((l+r) >> 1)) );
185 
186  if ( *y < *x0 )
187  Swap( *x0, *y );
188  if ( *y < *x )
189  Swap( *x, *y );
190  if ( *x < *x0 )
191  Swap( *x, *x0 );
192 
193  T v = *x;
194 
195  for ( ;; )
196  {
197  while ( *++x < v );
198  while ( v < *--y );
199  if ( y < x )
200  break;
201  Swap( *x, *y );
202  }
203 
204  *(x0+1) = *y;
205  *y = v;
206 
207  distance_type dx = x - i;
208  distance_type dy = y - i;
209 
210  if ( r-dx+1 >= dy-l )
211  {
212  *sp++ = dx;
213  *sp++ = r;
214  r = dy-1;
215  }
216  else
217  {
218  *sp++ = l;
219  *sp++ = dy-1;
220  l = dx;
221  }
222  }
223  }
224 }
225 
235 template <class RI> inline
236 void QuickSort( RI i, RI j )
237 {
238  __pcl_quick_sort__( i, j, ItemType( i ) );
239 }
240 
241 // ----------------------------------------------------------------------------
242 
243 template <class RI, class BP, class T> inline
244 void __pcl_quick_sort__( RI i, RI j, BP p, T* )
245 {
246  distance_type n = j - i;
247  if ( n < 2 )
248  return;
249 
250  distance_type tos[ 2*__PCL_QS_STACK_SIZE ];
251  distance_type* sp = tos;
252 
253  for ( distance_type l = 0, r = n-1; ; )
254  {
255  RI x0 = i + l;
256  RI y = i + r;
257 
258  if ( r-l < __PCL_QS_IS_THRESHOLD )
259  {
260  for ( RI x = x0; ++x <= y; )
261  {
262  T v = *x;
263  RI x1 = x;
264  for ( ; --x1 >= x0 && p( v, *x1 ); )
265  *(x1+1) = *x1;
266  *(x1+1) = v;
267  }
268 
269  if ( sp == tos )
270  break;
271 
272  r = *--sp;
273  l = *--sp;
274  }
275  else
276  {
277  RI x = x0;
278 
279  Swap( *++x, *(i + ((l+r) >> 1)) );
280 
281  if ( p( *y, *x0 ) )
282  Swap( *x0, *y );
283  if ( p( *y, *x ) )
284  Swap( *x, *y );
285  if ( p( *x, *x0 ) )
286  Swap( *x, *x0 );
287 
288  T v = *x;
289 
290  for ( ;; )
291  {
292  while ( p( *++x, v ) );
293  while ( p( v, *--y ) );
294  if ( y < x )
295  break;
296  Swap( *x, *y );
297  }
298 
299  *(x0+1) = *y;
300  *y = v;
301 
302  distance_type dx = x - i;
303  distance_type dy = y - i;
304 
305  if ( r-dx+1 >= dy-l )
306  {
307  *sp++ = dx;
308  *sp++ = r;
309  r = dy-1;
310  }
311  else
312  {
313  *sp++ = l;
314  *sp++ = dy-1;
315  l = dx;
316  }
317  }
318  }
319 }
320 
331 template <class RI, class BP> inline
332 void QuickSort( RI i, RI j, BP p )
333 {
334  __pcl_quick_sort__( i, j, p, ItemType( i ) );
335 }
336 
337 // ----------------------------------------------------------------------------
338 
339 template <class RI, class T> inline
340 void __pcl_heap_sort__( RI i, RI j, T* )
341 {
342  distance_type dj = j - i;
343  if ( dj < 2 )
344  return;
345 
346  T v;
347  distance_type di = 1 + (dj >> 1);
348 
349  for ( i += di-1, --j; ; )
350  {
351  if ( di > 1 )
352  {
353  v = *--i;
354  --di;
355  }
356  else
357  {
358  v = *j;
359  *j = *i;
360 
361  if ( --dj == 0 )
362  {
363  *i = v;
364  break;
365  }
366 
367  --j;
368  }
369 
370  RI x = i;
371  RI y = i;
372 
373  for ( distance_type dy2 = di, dy = di; !(dj < (dy <<= 1)); dy2 = dy )
374  {
375  y += dy2;
376 
377  if ( dy < dj && *y < *(y+1) )
378  {
379  ++y;
380  ++dy;
381  }
382 
383  if ( v < *y )
384  {
385  *x = *y;
386  x = y;
387  }
388  else
389  break;
390  }
391 
392  *x = v;
393  }
394 }
395 
405 template <class RI> inline
406 void HeapSort( RI i, RI j )
407 {
408  __pcl_heap_sort__( i, j, ItemType( i ) );
409 }
410 
411 // ----------------------------------------------------------------------------
412 
413 template <class RI, class BP, class T> inline
414 void __pcl_heap_sort__( RI i, RI j, BP p, T* )
415 {
416  distance_type dj = j - i;
417  if ( dj < 2 )
418  return;
419 
420  T v;
421  distance_type di = 1 + (dj >> 1);
422 
423  for ( i += di-1, --j; ; )
424  {
425  if ( di > 1 )
426  {
427  v = *--i;
428  --di;
429  }
430  else
431  {
432  v = *j;
433  *j = *i;
434 
435  if ( --dj == 0 )
436  {
437  *i = v;
438  break;
439  }
440 
441  --j;
442  }
443 
444  RI x = i;
445  RI y = i;
446 
447  for ( distance_type dy2 = di, dy = di; !(dj < (dy <<= 1)); dy2 = dy )
448  {
449  y += dy2;
450 
451  if ( dy < dj && p( *y, *(y+1) ) )
452  {
453  ++y;
454  ++dy;
455  }
456 
457  if ( p( v, *y ) )
458  {
459  *x = *y;
460  x = y;
461  }
462  else
463  break;
464  }
465 
466  *x = v;
467  }
468 }
469 
479 template <class RI, class BP> inline
480 void HeapSort( RI i, RI j, BP p )
481 {
482  __pcl_heap_sort__( i, j, p, ItemType( i ) );
483 }
484 
485 // ----------------------------------------------------------------------------
486 
487 template <class BI> inline
488 void __pcl_sort__( BI i, BI j, BidirectionalIterator )
489 {
490  InsertionSort( i, j );
491 }
492 
493 template <class RI> inline
494 void __pcl_sort__( RI i, RI j, RandomAccessIterator )
495 {
496 #ifdef __PCL_PREFER_HEAPSORT
497  HeapSort( i, j );
498 #else
499  QuickSort( i, j );
500 #endif
501 }
502 
519 template <class BI> inline
520 void Sort( BI i, BI j )
521 {
522  __pcl_sort__( i, j, IteratorClass( i ) );
523 }
524 
525 // ----------------------------------------------------------------------------
526 
527 template <class BI, class BP> inline
528 void __pcl_sort__( BI i, BI j, BP p, BidirectionalIterator )
529 {
530  InsertionSort( i, j, p );
531 }
532 
533 template <class RI, class BP> inline
534 void __pcl_sort__( RI i, RI j, BP p, RandomAccessIterator )
535 {
536 #ifdef __PCL_PREFER_HEAPSORT
537  HeapSort( i, j, p );
538 #else
539  QuickSort( i, j, p );
540 #endif
541 }
542 
560 template <class BI, class BP> inline
561 void Sort( BI i, BI j, BP p )
562 {
563  __pcl_sort__( i, j, p, IteratorClass( i ) );
564 }
565 
566 // ----------------------------------------------------------------------------
567 
568 } // pcl
569 
570 #endif // __PCL_Sort_h
571 
572 // ----------------------------------------------------------------------------
573 // EOF pcl/Sort.h - Released 2024-01-13T15:47:58Z
pcl
PCL root namespace.
Definition: AbstractImage.h:76
pcl::ItemType
T * ItemType(const Iterator< C, T > &)
Definition: Iterator.h:139
Utility.h
pcl::QuickSort
void QuickSort(RI i, RI j)
Definition: Sort.h:236
pcl::InsertionSort
void InsertionSort(BI i, BI j)
Definition: Sort.h:110
pcl::HeapSort
void HeapSort(RI i, RI j)
Definition: Sort.h:406
pcl::distance_type
ptrdiff_t distance_type
Definition: Defs.h:618
Iterator.h
pcl::Swap
void Swap(GenericPoint< T > &p1, GenericPoint< T > &p2) noexcept
Definition: Point.h:1459
pcl::Sort
void Sort(BI i, BI j)
Definition: Sort.h:520
pcl::IteratorClass
C IteratorClass(const Iterator< C, T > &)
Definition: Iterator.h:117
Defs.h