PCL
Search.h
Go to the documentation of this file.
1 // ____ ______ __
2 // / __ \ / ____// /
3 // / /_/ // / / /
4 // / ____// /___ / /___ PixInsight Class Library
5 // /_/ \____//_____/ PCL 2.1.19
6 // ----------------------------------------------------------------------------
7 // pcl/Search.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_Search_h
53 #define __PCL_Search_h
54 
56 
57 #include <pcl/Defs.h>
58 
59 #include <pcl/Iterator.h>
60 
61 namespace pcl
62 {
63 
64 // ----------------------------------------------------------------------------
65 
80 // ----------------------------------------------------------------------------
81 
90 template <class FI, class T> inline
91 FI LinearSearch( FI i, FI j, const T& v )
92 {
93  for( ; i != j; ++i )
94  if ( *i == v )
95  break;
96  return i;
97 }
98 
99 // ----------------------------------------------------------------------------
100 
109 template <class FI, class T, class BP> inline
110 FI LinearSearch( FI i, FI j, const T& v, BP p )
111 {
112  for( ; i != j; ++i )
113  if ( p( *i, v ) )
114  break;
115  return i;
116 }
117 
118 // ----------------------------------------------------------------------------
119 
128 template <class BI, class T> inline
129 BI LinearSearchLast( BI i, BI j, const T& v )
130 {
131  for( BI k = j; i != k; )
132  if ( *--k == v )
133  return k;
134  return j;
135 }
136 
137 // ----------------------------------------------------------------------------
138 
147 template <class BI, class T, class BP> inline
148 BI LinearSearchLast( BI i, BI j, const T& v, BP p )
149 {
150  for( BI k = j; i != k; )
151  if ( p( *--k, v ) )
152  return k;
153  return j;
154 }
155 
156 // ----------------------------------------------------------------------------
157 
169 template <class FI, class T> inline
170 FI BinarySearch( FI i, FI j, const T& v )
171 {
172  for ( distance_type n = Distance( i, j ); n > 0; )
173  {
174  distance_type h = n >> 1;
175  FI m = i;
176  Advance( m, h );
177 
178  if ( *m < v )
179  {
180  i = ++m;
181  n -= h+1;
182  }
183  else
184  n = h;
185  }
186 
187  return (i != j && !(v < *i)) ? i : j;
188 }
189 
190 // ----------------------------------------------------------------------------
191 
203 template <class FI, class T, class BP> inline
204 FI BinarySearch( FI i, FI j, const T& v, BP p )
205 {
206  for ( distance_type n = Distance( i, j ); n > 0; )
207  {
208  distance_type h = n >> 1;
209  FI m = i;
210  Advance( m, h );
211 
212  if ( p( *m, v ) )
213  {
214  i = ++m;
215  n -= h+1;
216  }
217  else
218  n = h;
219  }
220 
221  return (i != j && !p( v, *i )) ? i : j;
222 }
223 
224 // ----------------------------------------------------------------------------
225 
237 template <class FI, class T> inline
238 FI BinarySearchLast( FI i, FI j, const T& v )
239 {
240  FI k = BinarySearch( i, j, v );
241  if ( k != j )
242  for( FI l = k; ++l != j && *l == v; )
243  ++k;
244  return k;
245 }
246 
247 // ----------------------------------------------------------------------------
248 
260 template <class FI, class T, class BP> inline
261 FI BinarySearchLast( FI i, FI j, const T& v, BP p )
262 {
263  FI k = BinarySearch( i, j, v, p );
264  if ( k != j )
265  for( FI l = k; ++l != j && !p( *l, v ) && !p( v, *l ); )
266  ++k;
267  return k;
268 }
269 
270 // ----------------------------------------------------------------------------
271 
284 template <class FI, class T, class BP1, class BP2> inline
285 FI BinarySearch( FI i, FI j, const T& v, BP1 p1, BP2 p2 )
286 {
287  for ( distance_type n = Distance( i, j ); n > 0; )
288  {
289  distance_type h = n >> 1;
290  FI m = i;
291  Advance( m, h );
292 
293  if ( p1( *m, v ) )
294  {
295  i = ++m;
296  n -= h+1;
297  }
298  else
299  n = h;
300  }
301 
302  return (i != j && !p2( v, *i )) ? i : j;
303 }
304 
305 // ----------------------------------------------------------------------------
306 
325 template <class FI, class T> inline
326 FI InsertionPoint( FI i, FI j, const T& v )
327 {
328  for ( distance_type n = Distance( i, j ); n > 0; )
329  {
330  distance_type h = n >> 1;
331  FI m = i;
332  Advance( m, h );
333 
334  if ( v < *m )
335  n = h;
336  else
337  {
338  i = ++m;
339  n -= h+1;
340  }
341  }
342 
343  return i;
344 }
345 
346 // ----------------------------------------------------------------------------
347 
366 template <class FI, class T, class BP> inline
367 FI InsertionPoint( FI i, FI j, const T& v, BP p )
368 {
369  for ( distance_type n = Distance( i, j ); n > 0; )
370  {
371  distance_type h = n >> 1;
372  FI m = i;
373  Advance( m, h );
374 
375  if ( p( v, *m ) )
376  n = h;
377  else
378  {
379  i = ++m;
380  n -= h+1;
381  }
382  }
383 
384  return i;
385 }
386 
387 // ----------------------------------------------------------------------------
388 
396 template <class FI1, class FI2> inline
397 FI1 Search( FI1 i1, FI1 j1, FI2 i2, FI2 j2 )
398 {
399  distance_type n1 = Distance( i1, j1 );
400  distance_type n2 = Distance( i2, j2 );
401  if ( n1 > 0 && n2 > 0 )
402  for ( ; n2 <= n1; ++i1, --n1 )
403  {
404  FI1 k1 = i1;
405  FI2 k2 = i2;
406  for ( ; *k1 == *k2; ++k1 )
407  if ( ++k2 == j2 )
408  return i1;
409  }
410  return j1;
411 }
412 
413 // ----------------------------------------------------------------------------
414 
422 template <class FI1, class FI2, class BP> inline
423 FI1 Search( FI1 i1, FI1 j1, FI2 i2, FI2 j2, BP p )
424 {
425  distance_type n1 = Distance( i1, j1 );
426  distance_type n2 = Distance( i2, j2 );
427  if ( n1 > 0 && n2 > 0 )
428  for ( ; n2 <= n1; ++i1, --n1 )
429  {
430  FI1 k1 = i1;
431  FI2 k2 = i2;
432  for ( ; p( *k1, *k2 ); ++k1 )
433  if ( ++k2 == j2 )
434  return i1;
435  }
436  return j1;
437 }
438 
439 // ----------------------------------------------------------------------------
440 
448 template <class BI1, class FI2> inline
449 BI1 SearchLast( BI1 i1, BI1 j1, FI2 i2, FI2 j2 )
450 {
451  distance_type n1 = Distance( i1, j1 );
452  distance_type n2 = Distance( i2, j2 );
453  if ( n1 > 0 && n2 > 0 && n2 <= n1 )
454  {
455  i1.Advance( n1 - n2 );
456  for ( ;; )
457  {
458  BI1 k1 = i1;
459  FI2 k2 = i2;
460  for ( ; *k1 == *k2; ++k1 )
461  if ( ++k2 == j2 )
462  return i1;
463  if ( --n1 < n2 )
464  break;
465  --i1;
466  }
467  }
468  return j1;
469 }
470 
471 // ----------------------------------------------------------------------------
472 
480 template <class BI1, class FI2, class BP> inline
481 BI1 SearchLast( BI1 i1, BI1 j1, FI2 i2, FI2 j2, BP p )
482 {
483  distance_type n1 = Distance( i1, j1 );
484  distance_type n2 = Distance( i2, j2 );
485  if ( n1 > 0 && n2 > 0 && n2 <= n1 )
486  {
487  i1.Advance( n1 - n2 );
488  for ( ;; )
489  {
490  BI1 k1 = i1;
491  FI2 k2 = i2;
492  for ( ; p( *k1, *k2 ); ++k1 )
493  if ( ++k2 == j2 )
494  return i1;
495  if ( --n1 < n2 )
496  break;
497  --i1;
498  }
499  }
500  return j1;
501 }
502 
503 // ----------------------------------------------------------------------------
504 
505 } // pcl
506 
507 #endif // __PCL_Search_h
508 
509 // ----------------------------------------------------------------------------
510 // EOF pcl/Search.h - Released 2019-11-07T10:59:34Z
distance_type Distance(FI i, FI j)
Definition: Iterator.h:161
BI LinearSearchLast(BI i, BI j, const T &v)
Definition: Search.h:129
PCL root namespace.
Definition: AbstractImage.h:76
FI BinarySearchLast(FI i, FI j, const T &v)
Definition: Search.h:238
FI LinearSearch(FI i, FI j, const T &v)
Definition: Search.h:91
void Advance(FI &i, distance_type d)
Definition: Iterator.h:186
BI1 SearchLast(BI1 i1, BI1 j1, FI2 i2, FI2 j2)
Definition: Search.h:449
FI InsertionPoint(FI i, FI j, const T &v)
Definition: Search.h:326
FI BinarySearch(FI i, FI j, const T &v)
Definition: Search.h:170
FI1 Search(FI1 i1, FI1 j1, FI2 i2, FI2 j2)
Definition: Search.h:397
ptrdiff_t distance_type
Definition: Defs.h:549