PCL
Selection.h
Go to the documentation of this file.
1 // ____ ______ __
2 // / __ \ / ____// /
3 // / /_/ // / / /
4 // / ____// /___ / /___ PixInsight Class Library
5 // /_/ \____//_____/ PCL 2.1.19
6 // ----------------------------------------------------------------------------
7 // pcl/Selection.h - Released 2019-11-07T10:59:34Z
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-2019 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 (http://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_Selection_h
53 #define __PCL_Selection_h
54 
56 
57 #include <pcl/Defs.h>
58 
59 #include <pcl/Iterator.h>
60 #include <pcl/Utility.h>
61 
62 // Template formal parameters:
63 //
64 // FI Forward iterator
65 // BI Bidirectional iterator
66 // RI Random access iterator
67 // UP Unary predicate
68 // BP Binary predicate
69 // T Item type
70 // F Function
71 
72 namespace pcl
73 {
74 
75 // ----------------------------------------------------------------------------
76 
81 // ----------------------------------------------------------------------------
82 
83 template <class RI, typename T> inline
84 RI __pcl_quick_select__( RI i, RI j, distance_type k, T* )
85 {
86  distance_type n = j - i;
87  if ( k < 0 || n < 1 || n <= k )
88  return j;
89 
90  for ( distance_type l = 0, r = n-1; ; )
91  {
92  RI x0 = i + l;
93  RI y = i + r;
94 
95  if ( r <= l+1 )
96  {
97  if ( r == l+1 && *y < *x0 )
98  Swap( *x0, *y );
99  return i + k;
100  }
101 
102  RI x = x0;
103 
104  Swap( *++x, *(i + ((l+r) >> 1)) );
105 
106  if ( *y < *x0 )
107  Swap( *x0, *y );
108  if ( *y < *x )
109  Swap( *x, *y );
110  if ( *x < *x0 )
111  Swap( *x, *x0 );
112 
113  T v = *x;
114 
115  for ( ;; )
116  {
117  while ( *++x < v );
118  while ( v < *--y );
119  if ( y < x )
120  break;
121  Swap( *x, *y );
122  }
123 
124  *(x0+1) = *y;
125  *y = v;
126 
127  distance_type dy = y - i;
128  if ( dy >= k )
129  r = dy - 1;
130  if ( dy <= k )
131  l = x - i;
132  }
133 }
134 
164 template <class RI> inline
165 RI Select( RI i, RI j, distance_type k )
166 {
167  return __pcl_quick_select__( i, j, k, ItemType( i ) );
168 }
169 
170 // ----------------------------------------------------------------------------
171 
172 template <class RI, class BP, class T> inline
173 RI __pcl_quick_select__( RI i, RI j, distance_type k, BP p, T* )
174 {
175  distance_type n = j - i;
176  if ( k < 0 || n < 1 || n <= k )
177  return j;
178 
179  for ( distance_type l = 0, r = n-1; ; )
180  {
181  RI x0 = i + l;
182  RI y = i + r;
183 
184  if ( r <= l+1 )
185  {
186  if ( r == l+1 && p( *y, *x0 ) )
187  Swap( *x0, *y );
188  return i + k;
189  }
190 
191  RI x = x0;
192 
193  Swap( *++x, *(i + ((l+r) >> 1)) );
194 
195  if ( p( *y, *x0 ) )
196  Swap( *x0, *y );
197  if ( p( *y, *x ) )
198  Swap( *x, *y );
199  if ( p( *x, *x0 ) )
200  Swap( *x, *x0 );
201 
202  T v = *x;
203 
204  for ( ;; )
205  {
206  while ( p( *++x, v ) );
207  while ( p( v, *--y ) );
208  if ( y < x )
209  break;
210  Swap( *x, *y );
211  }
212 
213  *(x0+1) = *y;
214  *y = v;
215 
216  distance_type dy = y - i;
217  if ( dy >= k )
218  r = dy - 1;
219  if ( dy <= k )
220  l = x - i;
221  }
222 }
223 
237 template <class RI, class BP> inline
238 RI Select( RI i, RI j, distance_type k, BP p )
239 {
240  return __pcl_quick_select__( i, j, k, p, ItemType( i ) );
241 }
242 
243 // ----------------------------------------------------------------------------
244 
245 } // pcl
246 
247 #endif // __PCL_Selection_h
248 
249 // ----------------------------------------------------------------------------
250 // EOF pcl/Selection.h - Released 2019-11-07T10:59:34Z
void Swap(GenericPoint< T > &p1, GenericPoint< T > &p2)
Definition: Point.h:1402
PCL root namespace.
Definition: AbstractImage.h:76
T * ItemType(const Iterator< C, T > &)
Definition: Iterator.h:139
RI Select(RI i, RI j, distance_type k)
Definition: Selection.h:165
ptrdiff_t distance_type
Definition: Defs.h:549