PCL
Sort.h
Go to the documentation of this file.
1 // ____ ______ __
2 // / __ \ / ____// /
3 // / /_/ // / / /
4 // / ____// /___ / /___ PixInsight Class Library
5 // /_/ \____//_____/ PCL 2.4.7
6 // ----------------------------------------------------------------------------
7 // pcl/Sort.h - Released 2020-12-17T15:46:29Z
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-2020 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  {
91  BI x = j, k = j;
92  for ( --k; --x != i; )
93  if ( *x < *--k )
94  Swap( *x, *k );
95  if ( ++x != j )
96  for ( ; ++x != j; )
97  {
98  BI y = x;
99  T v = *x;
100  for ( k = y; v < *--k; y = k )
101  *y = *k;
102  *y = v;
103  }
104  }
105 }
106 
116 template <class BI> inline
117 void InsertionSort( BI i, BI j )
118 {
119  __pcl_insertion_sort__( i, j, ItemType( i ) );
120 }
121 
122 // ----------------------------------------------------------------------------
123 
124 template <class BI, class BP, class T> inline
125 void __pcl_insertion_sort__( BI i, BI j, BP p, const T* )
126 {
127  if ( i != j )
128  {
129  BI x = j, k = j;
130  for ( --k; --x != i; )
131  if ( p( *x, *--k ) )
132  Swap( *x, *k );
133  if ( ++x != j )
134  for ( ; ++x != j; )
135  {
136  BI y = x;
137  T v = *x;
138  for ( k = y; p( v, *--k ); y = k )
139  *y = *k;
140  *y = v;
141  }
142  }
143 }
144 
154 template <class BI, class BP> inline
155 void InsertionSort( BI i, BI j, BP p )
156 {
157  __pcl_insertion_sort__( i, j, p, ItemType( i ) );
158 }
159 
160 // ----------------------------------------------------------------------------
161 
162 template <class RI, class T> inline
163 void __pcl_quick_sort__( RI i, RI j, T* )
164 {
165  distance_type n = j - i;
166  if ( n < 2 )
167  return;
168 
169  distance_type tos[ 2*__PCL_QS_STACK_SIZE ];
170  distance_type* sp = tos;
171 
172  for ( distance_type l = 0, r = n-1; ; )
173  {
174  RI x0 = i + l;
175  RI y = i + r;
176 
177  if ( r-l < __PCL_QS_IS_THRESHOLD )
178  {
179  for ( RI x = x0; ++x <= y; )
180  {
181  T v = *x;
182  RI x1 = x;
183  for ( ; --x1 >= x0 && v < *x1; )
184  *(x1+1) = *x1;
185  *(x1+1) = v;
186  }
187 
188  if ( sp == tos )
189  break;
190 
191  r = *--sp;
192  l = *--sp;
193  }
194  else
195  {
196  RI x = x0;
197 
198  Swap( *++x, *(i + ((l+r) >> 1)) );
199 
200  if ( *y < *x0 )
201  Swap( *x0, *y );
202  if ( *y < *x )
203  Swap( *x, *y );
204  if ( *x < *x0 )
205  Swap( *x, *x0 );
206 
207  T v = *x;
208 
209  for ( ;; )
210  {
211  while ( *++x < v );
212  while ( v < *--y );
213  if ( y < x )
214  break;
215  Swap( *x, *y );
216  }
217 
218  *(x0+1) = *y;
219  *y = v;
220 
221  distance_type dx = x - i;
222  distance_type dy = y - i;
223 
224  if ( r-dx+1 >= dy-l )
225  {
226  *sp++ = dx;
227  *sp++ = r;
228  r = dy-1;
229  }
230  else
231  {
232  *sp++ = l;
233  *sp++ = dy-1;
234  l = dx;
235  }
236  }
237  }
238 }
239 
249 template <class RI> inline
250 void QuickSort( RI i, RI j )
251 {
252  __pcl_quick_sort__( i, j, ItemType( i ) );
253 }
254 
255 // ----------------------------------------------------------------------------
256 
257 template <class RI, class BP, class T> inline
258 void __pcl_quick_sort__( RI i, RI j, BP p, T* )
259 {
260  distance_type n = j - i;
261  if ( n < 2 )
262  return;
263 
264  distance_type tos[ 2*__PCL_QS_STACK_SIZE ];
265  distance_type* sp = tos;
266 
267  for ( distance_type l = 0, r = n-1; ; )
268  {
269  RI x0 = i + l;
270  RI y = i + r;
271 
272  if ( r-l < __PCL_QS_IS_THRESHOLD )
273  {
274  for ( RI x = x0; ++x <= y; )
275  {
276  T v = *x;
277  RI x1 = x;
278  for ( ; --x1 >= x0 && p( v, *x1 ); )
279  *(x1+1) = *x1;
280  *(x1+1) = v;
281  }
282 
283  if ( sp == tos )
284  break;
285 
286  r = *--sp;
287  l = *--sp;
288  }
289  else
290  {
291  RI x = x0;
292 
293  Swap( *++x, *(i + ((l+r) >> 1)) );
294 
295  if ( p( *y, *x0 ) )
296  Swap( *x0, *y );
297  if ( p( *y, *x ) )
298  Swap( *x, *y );
299  if ( p( *x, *x0 ) )
300  Swap( *x, *x0 );
301 
302  T v = *x;
303 
304  for ( ;; )
305  {
306  while ( p( *++x, v ) );
307  while ( p( v, *--y ) );
308  if ( y < x )
309  break;
310  Swap( *x, *y );
311  }
312 
313  *(x0+1) = *y;
314  *y = v;
315 
316  distance_type dx = x - i;
317  distance_type dy = y - i;
318 
319  if ( r-dx+1 >= dy-l )
320  {
321  *sp++ = dx;
322  *sp++ = r;
323  r = dy-1;
324  }
325  else
326  {
327  *sp++ = l;
328  *sp++ = dy-1;
329  l = dx;
330  }
331  }
332  }
333 }
334 
345 template <class RI, class BP> inline
346 void QuickSort( RI i, RI j, BP p )
347 {
348  __pcl_quick_sort__( i, j, p, ItemType( i ) );
349 }
350 
351 // ----------------------------------------------------------------------------
352 
353 template <class RI, class T> inline
354 void __pcl_heap_sort__( RI i, RI j, T* )
355 {
356  distance_type dj = j - i;
357  if ( dj < 2 )
358  return;
359 
360  T v;
361  distance_type di = 1 + (dj >> 1);
362 
363  for ( i += di-1, --j; ; )
364  {
365  if ( di > 1 )
366  {
367  v = *--i;
368  --di;
369  }
370  else
371  {
372  v = *j;
373  *j = *i;
374 
375  if ( --dj == 0 )
376  {
377  *i = v;
378  break;
379  }
380 
381  --j;
382  }
383 
384  RI x = i;
385  RI y = i;
386 
387  for ( distance_type dy2 = di, dy = di; !(dj < (dy <<= 1)); dy2 = dy )
388  {
389  y += dy2;
390 
391  if ( dy < dj && *y < *(y+1) )
392  {
393  ++y;
394  ++dy;
395  }
396 
397  if ( v < *y )
398  {
399  *x = *y;
400  x = y;
401  }
402  else
403  break;
404  }
405 
406  *x = v;
407  }
408 }
409 
419 template <class RI> inline
420 void HeapSort( RI i, RI j )
421 {
422  __pcl_heap_sort__( i, j, ItemType( i ) );
423 }
424 
425 // ----------------------------------------------------------------------------
426 
427 template <class RI, class BP, class T> inline
428 void __pcl_heap_sort__( RI i, RI j, BP p, T* )
429 {
430  distance_type dj = j - i;
431  if ( dj < 2 )
432  return;
433 
434  T v;
435  distance_type di = 1 + (dj >> 1);
436 
437  for ( i += di-1, --j; ; )
438  {
439  if ( di > 1 )
440  {
441  v = *--i;
442  --di;
443  }
444  else
445  {
446  v = *j;
447  *j = *i;
448 
449  if ( --dj == 0 )
450  {
451  *i = v;
452  break;
453  }
454 
455  --j;
456  }
457 
458  RI x = i;
459  RI y = i;
460 
461  for ( distance_type dy2 = di, dy = di; !(dj < (dy <<= 1)); dy2 = dy )
462  {
463  y += dy2;
464 
465  if ( dy < dj && p( *y, *(y+1) ) )
466  {
467  ++y;
468  ++dy;
469  }
470 
471  if ( p( v, *y ) )
472  {
473  *x = *y;
474  x = y;
475  }
476  else
477  break;
478  }
479 
480  *x = v;
481  }
482 }
483 
493 template <class RI, class BP> inline
494 void HeapSort( RI i, RI j, BP p )
495 {
496  __pcl_heap_sort__( i, j, p, ItemType( i ) );
497 }
498 
499 // ----------------------------------------------------------------------------
500 
501 template <class BI> inline
502 void __pcl_sort__( BI i, BI j, BidirectionalIterator )
503 {
504  InsertionSort( i, j );
505 }
506 
507 template <class RI> inline
508 void __pcl_sort__( RI i, RI j, RandomAccessIterator )
509 {
510 #ifdef __PCL_PREFER_HEAPSORT
511  HeapSort( i, j );
512 #else
513  QuickSort( i, j );
514 #endif
515 }
516 
533 template <class BI> inline
534 void Sort( BI i, BI j )
535 {
536  __pcl_sort__( i, j, IteratorClass( i ) );
537 }
538 
539 // ----------------------------------------------------------------------------
540 
541 template <class BI, class BP> inline
542 void __pcl_sort__( BI i, BI j, BP p, BidirectionalIterator )
543 {
544  InsertionSort( i, j, p );
545 }
546 
547 template <class RI, class BP> inline
548 void __pcl_sort__( RI i, RI j, BP p, RandomAccessIterator )
549 {
550 #ifdef __PCL_PREFER_HEAPSORT
551  HeapSort( i, j, p );
552 #else
553  QuickSort( i, j, p );
554 #endif
555 }
556 
574 template <class BI, class BP> inline
575 void Sort( BI i, BI j, BP p )
576 {
577  __pcl_sort__( i, j, p, IteratorClass( i ) );
578 }
579 
580 // ----------------------------------------------------------------------------
581 
582 } // pcl
583 
584 #endif // __PCL_Sort_h
585 
586 // ----------------------------------------------------------------------------
587 // EOF pcl/Sort.h - Released 2020-12-17T15:46:29Z
pcl::RandomAccessIterator
Random access iterator class.
Definition: Iterator.h:93
pcl
PCL root namespace.
Definition: AbstractImage.h:76
pcl::ItemType
T * ItemType(const Iterator< C, T > &)
Definition: Iterator.h:139
pcl::Swap
void Swap(GenericPoint< T > &p1, GenericPoint< T > &p2) noexcept
Definition: Point.h:1404
pcl::Sort
void Sort(BI i, BI j)
Definition: Sort.h:534
pcl::BidirectionalIterator
Bidirectional iterator class.
Definition: Iterator.h:84
pcl::QuickSort
void QuickSort(RI i, RI j)
Definition: Sort.h:250
pcl::InsertionSort
void InsertionSort(BI i, BI j)
Definition: Sort.h:117
pcl::distance_type
ptrdiff_t distance_type
Definition: Defs.h:611
pcl::IteratorClass
C IteratorClass(const Iterator< C, T > &)
Definition: Iterator.h:117
pcl::HeapSort
void HeapSort(RI i, RI j)
Definition: Sort.h:420