← Back to branch summary

~ubuntu-branches/ubuntu/utopic/libthrust/utopic

« back to all changes in this revision

Viewing changes to binary_search.h

  • Committer: Package Import Robot
  • Author(s): Andreas Beckmann
  • Date: 2013-07-10 12:57:33 UTC
  • mfrom: (1.1.4)
  • Revision ID: package-import@ubuntu.com-20130710125733-my19jic71sqsabaj
Tags: 1.7.0-1
http://bugs.debian.org/715362
* New upstream release.  (Closes: #715362)
* Update watch file.

Show diffs side-by-side

added added

removed removed

Lines of Context:
binary_search.h
22
22
#pragma once
23
23
 
24
24
#include <thrust/detail/config.h>
 
25
#include <thrust/detail/execution_policy.h>
25
26
#include <thrust/pair.h>
26
27
 
27
28
namespace thrust
31
32
/*! \addtogroup algorithms
32
33
 */
33
34
 
 
35
 
34
36
/*! \addtogroup searching
35
37
 *  \ingroup algorithms
36
38
 *  \{
37
39
 */
38
40
 
 
41
 
39
42
/*! \addtogroup binary_search Binary Search
40
43
 *  \ingroup searching
41
44
 *  \{
42
45
 */
43
46
 
 
47
 
44
48
//////////////////////   
45
49
// Scalar Functions //
46
50
//////////////////////
54
58
 * the furthermost iterator \c i in <tt>[first, last)</tt> such that,
55
59
 * for every iterator \c j in <tt>[first, i)</tt>, <tt>*j < value</tt>. 
56
60
 *
 
61
 * The algorithm's execution is parallelized as determined by \p exec.
 
62
 *
 
63
 *  \param exec The execution policy to use for parallelization.
 
64
 *  \param first The beginning of the ordered sequence.
 
65
 *  \param last The end of the ordered sequence.
 
66
 *  \param value The value to be searched.
 
67
 *  \return The furthermost iterator \c i, such that <tt>*i < value</tt>.
 
68
 * 
 
69
 *  \tparam DerivedPolicy The name of the derived execution policy.
 
70
 *  \tparam ForwardIterator is a model of <a href="http://www.sgi.com/tech/stl/ForwardIterator">Forward Iterator</a>.
 
71
 *  \tparam LessThanComparable is a model of <a href="http://www.sgi.com/tech/stl/LessThanComparable.html">LessThanComparable</a>. 
 
72
 *
 
73
 *  The following code snippet demonstrates how to use \p lower_bound
 
74
 *  to search for values in a ordered range using the \p thrust::device execution policy for parallelization:
 
75
 *
 
76
 *  \code
 
77
 *  #include <thrust/binary_search.h>
 
78
 *  #include <thrust/device_vector.h>
 
79
 *  #include <thrust/execution_policy.h>
 
80
 *  ...
 
81
 *  thrust::device_vector<int> input(5);
 
82
 *
 
83
 *  input[0] = 0;
 
84
 *  input[1] = 2;
 
85
 *  input[2] = 5;
 
86
 *  input[3] = 7;
 
87
 *  input[4] = 8;
 
88
 *
 
89
 *  thrust::lower_bound(thrust::device, input.begin(), input.end(), 0); // returns input.begin()
 
90
 *  thrust::lower_bound(thrust::device, input.begin(), input.end(), 1); // returns input.begin() + 1
 
91
 *  thrust::lower_bound(thrust::device, input.begin(), input.end(), 2); // returns input.begin() + 1
 
92
 *  thrust::lower_bound(thrust::device, input.begin(), input.end(), 3); // returns input.begin() + 2
 
93
 *  thrust::lower_bound(thrust::device, input.begin(), input.end(), 8); // returns input.begin() + 4
 
94
 *  thrust::lower_bound(thrust::device, input.begin(), input.end(), 9); // returns input.end()
 
95
 *  \endcode
 
96
 *
 
97
 *  \see http://www.sgi.com/tech/stl/lower_bound.html
 
98
 *  \see \p upper_bound
 
99
 *  \see \p equal_range
 
100
 *  \see \p binary_search
 
101
 */
 
102
template<typename DerivedPolicy, typename ForwardIterator, typename LessThanComparable>
 
103
ForwardIterator lower_bound(const thrust::detail::execution_policy_base<DerivedPolicy> &exec,
 
104
                            ForwardIterator first,
 
105
                            ForwardIterator last,
 
106
                            const LessThanComparable &value);
 
107
 
 
108
 
 
109
/*! \p lower_bound is a version of binary search: it attempts to find
 
110
 * the element value in an ordered range <tt>[first, last)</tt>. 
 
111
 * Specifically, it returns the first position where value could be
 
112
 * inserted without violating the ordering. This version of 
 
113
 * \p lower_bound uses <tt>operator<</tt> for comparison and returns
 
114
 * the furthermost iterator \c i in <tt>[first, last)</tt> such that,
 
115
 * for every iterator \c j in <tt>[first, i)</tt>, <tt>*j < value</tt>. 
 
116
 *
57
117
 *  \param first The beginning of the ordered sequence.
58
118
 *  \param last The end of the ordered sequence.
59
119
 *  \param value The value to be searched.
105
165
 * such that, for every iterator \c j in <tt>[first, i)</tt>, 
106
166
 * <tt>comp(*j, value)</tt> is \c true. 
107
167
 *
 
168
 * The algorithm's execution is parallelized as determined by \p exec.
 
169
 *
 
170
 *  \param exec The execution policy to use for parallelization.
 
171
 *  \param first The beginning of the ordered sequence.
 
172
 *  \param last The end of the ordered sequence.
 
173
 *  \param value The value to be searched.
 
174
 *  \param comp The comparison operator.
 
175
 *  \return The furthermost iterator \c i, such that <tt>comp(*i, value)</tt> is \c true.
 
176
 * 
 
177
 *  \tparam DerivedPolicy The name of the derived execution policy.
 
178
 *  \tparam ForwardIterator is a model of <a href="http://www.sgi.com/tech/stl/ForwardIterator">Forward Iterator</a>.
 
179
 *  \tparam T is comparable to \p ForwardIterator's \c value_type.
 
180
 *  \tparam StrictWeakOrdering is a model of <a href="http://www.sgi.com/tech/stl/StrictWeakOrdering.html">Strict Weak Ordering</a>.
 
181
 *
 
182
 *  The following code snippet demonstrates how to use \p lower_bound
 
183
 *  to search for values in a ordered range using the \p thrust::device execution policy for parallelization:
 
184
 *
 
185
 *  \code
 
186
 *  #include <thrust/binary_search.h>
 
187
 *  #include <thrust/device_vector.h>
 
188
 *  #include <thrust/functional.h>
 
189
 *  #include <thrust/execution_policy.h>
 
190
 *  ...
 
191
 *  thrust::device_vector<int> input(5);
 
192
 *
 
193
 *  input[0] = 0;
 
194
 *  input[1] = 2;
 
195
 *  input[2] = 5;
 
196
 *  input[3] = 7;
 
197
 *  input[4] = 8;
 
198
 *
 
199
 *  thrust::lower_bound(input.begin(), input.end(), 0, thrust::less<int>()); // returns input.begin()
 
200
 *  thrust::lower_bound(input.begin(), input.end(), 1, thrust::less<int>()); // returns input.begin() + 1
 
201
 *  thrust::lower_bound(input.begin(), input.end(), 2, thrust::less<int>()); // returns input.begin() + 1
 
202
 *  thrust::lower_bound(input.begin(), input.end(), 3, thrust::less<int>()); // returns input.begin() + 2
 
203
 *  thrust::lower_bound(input.begin(), input.end(), 8, thrust::less<int>()); // returns input.begin() + 4
 
204
 *  thrust::lower_bound(input.begin(), input.end(), 9, thrust::less<int>()); // returns input.end()
 
205
 *  \endcode
 
206
 *
 
207
 *  \see http://www.sgi.com/tech/stl/lower_bound.html
 
208
 *  \see \p upper_bound
 
209
 *  \see \p equal_range
 
210
 *  \see \p binary_search
 
211
 */
 
212
template<typename DerivedPolicy, typename ForwardIterator, typename T, typename StrictWeakOrdering>
 
213
ForwardIterator lower_bound(const thrust::detail::execution_policy_base<DerivedPolicy> &exec,
 
214
                            ForwardIterator first,
 
215
                            ForwardIterator last,
 
216
                            const T &value,
 
217
                            StrictWeakOrdering comp);
 
218
 
 
219
 
 
220
/*! \p lower_bound is a version of binary search: it attempts to find
 
221
 * the element value in an ordered range <tt>[first, last)</tt>. 
 
222
 * Specifically, it returns the first position where value could be
 
223
 * inserted without violating the ordering. This version of 
 
224
 * \p lower_bound uses function object \c comp for comparison 
 
225
 * and returns the furthermost iterator \c i in <tt>[first, last)</tt>
 
226
 * such that, for every iterator \c j in <tt>[first, i)</tt>, 
 
227
 * <tt>comp(*j, value)</tt> is \c true. 
 
228
 *
108
229
 *  \param first The beginning of the ordered sequence.
109
230
 *  \param last The end of the ordered sequence.
110
231
 *  \param value The value to be searched.
160
281
 * for every iterator \c j in <tt>[first, i)</tt>, <tt>value < *j</tt>
161
282
 * is \c false.
162
283
 *
 
284
 * The algorithm's execution is parallelized as determined by \p exec.
 
285
 *
 
286
 *  \param exec The execution policy to use for parallelization.
 
287
 *  \param first The beginning of the ordered sequence.
 
288
 *  \param last The end of the ordered sequence.
 
289
 *  \param value The value to be searched.
 
290
 *  \return The furthermost iterator \c i, such that <tt>value < *i</tt> is \c false.
 
291
 * 
 
292
 *  \tparam DerivedPolicy The name of the derived execution policy.
 
293
 *  \tparam ForwardIterator is a model of <a href="http://www.sgi.com/tech/stl/ForwardIterator">Forward Iterator</a>.
 
294
 *  \tparam LessThanComparable is a model of <a href="http://www.sgi.com/tech/stl/LessThanComparable.html">LessThanComparable</a>. 
 
295
 *
 
296
 *  The following code snippet demonstrates how to use \p upper_bound
 
297
 *  to search for values in a ordered range using the \p thrust::device execution policy for parallelism:
 
298
 *
 
299
 *  \code
 
300
 *  #include <thrust/binary_search.h>
 
301
 *  #include <thrust/device_vector.h>
 
302
 *  #include <thrust/execution_policy.h>
 
303
 *  ...
 
304
 *  thrust::device_vector<int> input(5);
 
305
 *
 
306
 *  input[0] = 0;
 
307
 *  input[1] = 2;
 
308
 *  input[2] = 5;
 
309
 *  input[3] = 7;
 
310
 *  input[4] = 8;
 
311
 *
 
312
 *  thrust::upper_bound(thrust::device, input.begin(), input.end(), 0); // returns input.begin() + 1
 
313
 *  thrust::upper_bound(thrust::device, input.begin(), input.end(), 1); // returns input.begin() + 1
 
314
 *  thrust::upper_bound(thrust::device, input.begin(), input.end(), 2); // returns input.begin() + 2
 
315
 *  thrust::upper_bound(thrust::device, input.begin(), input.end(), 3); // returns input.begin() + 2
 
316
 *  thrust::upper_bound(thrust::device, input.begin(), input.end(), 8); // returns input.end()
 
317
 *  thrust::upper_bound(thrust::device, input.begin(), input.end(), 9); // returns input.end()
 
318
 *  \endcode
 
319
 *
 
320
 *  \see http://www.sgi.com/tech/stl/upper_bound.html
 
321
 *  \see \p lower_bound
 
322
 *  \see \p equal_range
 
323
 *  \see \p binary_search
 
324
 */
 
325
template<typename DerivedPolicy, typename ForwardIterator, typename LessThanComparable>
 
326
ForwardIterator upper_bound(const thrust::detail::execution_policy_base<DerivedPolicy> &exec,
 
327
                            ForwardIterator first,
 
328
                            ForwardIterator last,
 
329
                            const LessThanComparable &value);
 
330
 
 
331
 
 
332
/*! \p upper_bound is a version of binary search: it attempts to find
 
333
 * the element value in an ordered range <tt>[first, last)</tt>. 
 
334
 * Specifically, it returns the last position where value could be
 
335
 * inserted without violating the ordering. This version of 
 
336
 * \p upper_bound uses <tt>operator<</tt> for comparison and returns
 
337
 * the furthermost iterator \c i in <tt>[first, last)</tt> such that,
 
338
 * for every iterator \c j in <tt>[first, i)</tt>, <tt>value < *j</tt>
 
339
 * is \c false.
 
340
 *
163
341
 *  \param first The beginning of the ordered sequence.
164
342
 *  \param last The end of the ordered sequence.
165
343
 *  \param value The value to be searched.
201
379
                            ForwardIterator last,
202
380
                            const LessThanComparable& value);
203
381
 
 
382
 
 
383
/*! \p upper_bound is a version of binary search: it attempts to find
 
384
 * the element value in an ordered range <tt>[first, last)</tt>. 
 
385
 * Specifically, it returns the last position where value could be
 
386
 * inserted without violating the ordering. This version of 
 
387
 * \p upper_bound uses function object \c comp for comparison and returns
 
388
 * the furthermost iterator \c i in <tt>[first, last)</tt> such that,
 
389
 * for every iterator \c j in <tt>[first, i)</tt>, <tt>comp(value, *j)</tt>
 
390
 * is \c false.
 
391
 *
 
392
 * The algorithm's execution is parallelized as determined by \p exec.
 
393
 *
 
394
 *  \param exec The execution policy to use for parallelization.
 
395
 *  \param first The beginning of the ordered sequence.
 
396
 *  \param last The end of the ordered sequence.
 
397
 *  \param value The value to be searched.
 
398
 *  \param comp The comparison operator.
 
399
 *  \return The furthermost iterator \c i, such that <tt>comp(value, *i)</tt> is \c false.
 
400
 * 
 
401
 *  \tparam DerivedPolicy The name of the derived execution policy.
 
402
 *  \tparam ForwardIterator is a model of <a href="http://www.sgi.com/tech/stl/ForwardIterator">Forward Iterator</a>.
 
403
 *  \tparam T is comparable to \p ForwardIterator's \c value_type.
 
404
 *  \tparam StrictWeakOrdering is a model of <a href="http://www.sgi.com/tech/stl/StrictWeakOrdering.html">Strict Weak Ordering</a>.
 
405
 *
 
406
 *  The following code snippet demonstrates how to use \p upper_bound
 
407
 *  to search for values in a ordered range using the \p thrust::device execution policy for parallelization:
 
408
 *
 
409
 *  \code
 
410
 *  #include <thrust/binary_search.h>
 
411
 *  #include <thrust/device_vector.h>
 
412
 *  #include <thrust/functional.h>
 
413
 *  #include <thrust/execution_policy.h>
 
414
 *  ...
 
415
 *  thrust::device_vector<int> input(5);
 
416
 *
 
417
 *  input[0] = 0;
 
418
 *  input[1] = 2;
 
419
 *  input[2] = 5;
 
420
 *  input[3] = 7;
 
421
 *  input[4] = 8;
 
422
 *
 
423
 *  thrust::upper_bound(thrust::device, input.begin(), input.end(), 0, thrust::less<int>()); // returns input.begin() + 1
 
424
 *  thrust::upper_bound(thrust::device, input.begin(), input.end(), 1, thrust::less<int>()); // returns input.begin() + 1
 
425
 *  thrust::upper_bound(thrust::device, input.begin(), input.end(), 2, thrust::less<int>()); // returns input.begin() + 2
 
426
 *  thrust::upper_bound(thrust::device, input.begin(), input.end(), 3, thrust::less<int>()); // returns input.begin() + 2
 
427
 *  thrust::upper_bound(thrust::device, input.begin(), input.end(), 8, thrust::less<int>()); // returns input.end()
 
428
 *  thrust::upper_bound(thrust::device, input.begin(), input.end(), 9, thrust::less<int>()); // returns input.end()
 
429
 *  \endcode
 
430
 *
 
431
 *  \see http://www.sgi.com/tech/stl/upper_bound.html
 
432
 *  \see \p lower_bound
 
433
 *  \see \p equal_range
 
434
 *  \see \p binary_search
 
435
 */
 
436
template<typename DerivedPolicy, typename ForwardIterator, typename T, typename StrictWeakOrdering>
 
437
ForwardIterator upper_bound(const thrust::detail::execution_policy_base<DerivedPolicy> &exec,
 
438
                            ForwardIterator first,
 
439
                            ForwardIterator last,
 
440
                            const T &value,
 
441
                            StrictWeakOrdering comp);
 
442
 
204
443
/*! \p upper_bound is a version of binary search: it attempts to find
205
444
 * the element value in an ordered range <tt>[first, last)</tt>. 
206
445
 * Specifically, it returns the last position where value could be
264
503
 * there exists an iterator \c i in <tt>[first, last)</tt> such that 
265
504
 * <tt>*i < value</tt> and <tt>value < *i</tt> are both \c false.
266
505
 *
 
506
 * The algorithm's execution is parallelized as determined by \p exec.
 
507
 *
 
508
 *  \param exec The execution policy to use for parallelization.
 
509
 *  \param first The beginning of the ordered sequence.
 
510
 *  \param last The end of the ordered sequence.
 
511
 *  \param value The value to be searched.
 
512
 *  \return \c true if an equivalent element exists in <tt>[first, last)</tt>, otherwise \c false.
 
513
 * 
 
514
 *  \tparam DerivedPolicy The name of the derived execution policy.
 
515
 *  \tparam ForwardIterator is a model of <a href="http://www.sgi.com/tech/stl/ForwardIterator">Forward Iterator</a>.
 
516
 *  \tparam LessThanComparable is a model of <a href="http://www.sgi.com/tech/stl/LessThanComparable.html">LessThanComparable</a>. 
 
517
 *
 
518
 *  The following code snippet demonstrates how to use \p binary_search
 
519
 *  to search for values in a ordered range using the \p thrust::device execution policy for parallelization:
 
520
 *
 
521
 *  \code
 
522
 *  #include <thrust/binary_search.h>
 
523
 *  #include <thrust/device_vector.h>
 
524
 *  #include <thrust/execution_policy.h>
 
525
 *  ...
 
526
 *  thrust::device_vector<int> input(5);
 
527
 *
 
528
 *  input[0] = 0;
 
529
 *  input[1] = 2;
 
530
 *  input[2] = 5;
 
531
 *  input[3] = 7;
 
532
 *  input[4] = 8;
 
533
 *
 
534
 *  thrust::binary_search(thrust::device, input.begin(), input.end(), 0); // returns true
 
535
 *  thrust::binary_search(thrust::device, input.begin(), input.end(), 1); // returns false
 
536
 *  thrust::binary_search(thrust::device, input.begin(), input.end(), 2); // returns true
 
537
 *  thrust::binary_search(thrust::device, input.begin(), input.end(), 3); // returns false
 
538
 *  thrust::binary_search(thrust::device, input.begin(), input.end(), 8); // returns true
 
539
 *  thrust::binary_search(thrust::device, input.begin(), input.end(), 9); // returns false
 
540
 *  \endcode
 
541
 *
 
542
 *  \see http://www.sgi.com/tech/stl/binary_search.html
 
543
 *  \see \p lower_bound
 
544
 *  \see \p upper_bound
 
545
 *  \see \p equal_range
 
546
 */
 
547
template <typename DerivedPolicy, typename ForwardIterator, typename LessThanComparable>
 
548
bool binary_search(const thrust::detail::execution_policy_base<DerivedPolicy> &exec,
 
549
                   ForwardIterator first, 
 
550
                   ForwardIterator last,
 
551
                   const LessThanComparable& value);
 
552
 
 
553
 
 
554
/*! \p binary_search is a version of binary search: it attempts to find
 
555
 * the element value in an ordered range <tt>[first, last)</tt>. 
 
556
 * It returns \c true if an element that is equivalent to \c value 
 
557
 * is present in <tt>[first, last)</tt> and \c false if no such element
 
558
 * exists.  Specifically, this version returns \c true if and only if 
 
559
 * there exists an iterator \c i in <tt>[first, last)</tt> such that 
 
560
 * <tt>*i < value</tt> and <tt>value < *i</tt> are both \c false.
 
561
 *
267
562
 *  \param first The beginning of the ordered sequence.
268
563
 *  \param last The end of the ordered sequence.
269
564
 *  \param value The value to be searched.
314
609
 * there exists an iterator \c i in <tt>[first, last)</tt> such that 
315
610
 * <tt>comp(*i, value)</tt> and <tt>comp(value, *i)</tt> are both \c false.
316
611
 *
 
612
 * The algorithm's execution is parallelized as determined by \p exec.
 
613
 *
 
614
 *  \param exec The execution policy to use for parallelization.
 
615
 *  \param first The beginning of the ordered sequence.
 
616
 *  \param last The end of the ordered sequence.
 
617
 *  \param value The value to be searched.
 
618
 *  \param comp The comparison operator.
 
619
 *  \return \c true if an equivalent element exists in <tt>[first, last)</tt>, otherwise \c false.
 
620
 * 
 
621
 *  \tparam DerivedPolicy The name of the derived execution policy.
 
622
 *  \tparam ForwardIterator is a model of <a href="http://www.sgi.com/tech/stl/ForwardIterator">Forward Iterator</a>.
 
623
 *  \tparam T is comparable to \p ForwardIterator's \c value_type.
 
624
 *  \tparam StrictWeakOrdering is a model of <a href="http://www.sgi.com/tech/stl/StrictWeakOrdering.html">Strict Weak Ordering</a>.
 
625
 *
 
626
 *  The following code snippet demonstrates how to use \p binary_search
 
627
 *  to search for values in a ordered range using the \p thrust::device execution policy for parallelization:
 
628
 *
 
629
 *  \code
 
630
 *  #include <thrust/binary_search.h>
 
631
 *  #include <thrust/device_vector.h>
 
632
 *  #include <thrust/functional.h>
 
633
 *  #include <thrust/execution_policy.h>
 
634
 *  ...
 
635
 *  thrust::device_vector<int> input(5);
 
636
 *
 
637
 *  input[0] = 0;
 
638
 *  input[1] = 2;
 
639
 *  input[2] = 5;
 
640
 *  input[3] = 7;
 
641
 *  input[4] = 8;
 
642
 *
 
643
 *  thrust::binary_search(thrust::device, input.begin(), input.end(), 0, thrust::less<int>()); // returns true
 
644
 *  thrust::binary_search(thrust::device, input.begin(), input.end(), 1, thrust::less<int>()); // returns false
 
645
 *  thrust::binary_search(thrust::device, input.begin(), input.end(), 2, thrust::less<int>()); // returns true
 
646
 *  thrust::binary_search(thrust::device, input.begin(), input.end(), 3, thrust::less<int>()); // returns false
 
647
 *  thrust::binary_search(thrust::device, input.begin(), input.end(), 8, thrust::less<int>()); // returns true
 
648
 *  thrust::binary_search(thrust::device, input.begin(), input.end(), 9, thrust::less<int>()); // returns false
 
649
 *  \endcode
 
650
 *
 
651
 *  \see http://www.sgi.com/tech/stl/binary_search.html
 
652
 *  \see \p lower_bound
 
653
 *  \see \p upper_bound
 
654
 *  \see \p equal_range
 
655
 */
 
656
template <typename DerivedPolicy, typename ForwardIterator, typename T, typename StrictWeakOrdering>
 
657
bool binary_search(const thrust::detail::execution_policy_base<DerivedPolicy> &exec,
 
658
                   ForwardIterator first,
 
659
                   ForwardIterator last,
 
660
                   const T& value, 
 
661
                   StrictWeakOrdering comp);
 
662
 
 
663
 
 
664
/*! \p binary_search is a version of binary search: it attempts to find
 
665
 * the element value in an ordered range <tt>[first, last)</tt>. 
 
666
 * It returns \c true if an element that is equivalent to \c value 
 
667
 * is present in <tt>[first, last)</tt> and \c false if no such element
 
668
 * exists.  Specifically, this version returns \c true if and only if 
 
669
 * there exists an iterator \c i in <tt>[first, last)</tt> such that 
 
670
 * <tt>comp(*i, value)</tt> and <tt>comp(value, *i)</tt> are both \c false.
 
671
 *
317
672
 *  \param first The beginning of the ordered sequence.
318
673
 *  \param last The end of the ordered sequence.
319
674
 *  \param value The value to be searched.
381
736
 * For every iterator \c k in <tt>[i, j)</tt>, neither 
382
737
 * <tt>value < *k</tt> nor <tt>*k < value</tt> is \c true.
383
738
 *
 
739
 * The algorithm's execution is parallelized as determined by \p exec.
 
740
 *
 
741
 *  \param exec The execution policy to use for parallelization.
 
742
 *  \param first The beginning of the ordered sequence.
 
743
 *  \param last The end of the ordered sequence.
 
744
 *  \param value The value to be searched.
 
745
 *  \return A \p pair of iterators <tt>[i, j)</tt> that define the range of equivalent elements.
 
746
 * 
 
747
 *  \tparam DerivedPolicy The name of the derived execution policy.
 
748
 *  \tparam ForwardIterator is a model of <a href="http://www.sgi.com/tech/stl/ForwardIterator">Forward Iterator</a>.
 
749
 *  \tparam LessThanComparable is a model of <a href="http://www.sgi.com/tech/stl/LessThanComparable.html">LessThanComparable</a>. 
 
750
 *
 
751
 *  The following code snippet demonstrates how to use \p equal_range
 
752
 *  to search for values in a ordered range using the \p thrust::device execution policy for parallelization:
 
753
 *
 
754
 *  \code
 
755
 *  #include <thrust/binary_search.h>
 
756
 *  #include <thrust/device_vector.h>
 
757
 *  #include <thrust/execution_policy.h>
 
758
 *  ...
 
759
 *  thrust::device_vector<int> input(5);
 
760
 *
 
761
 *  input[0] = 0;
 
762
 *  input[1] = 2;
 
763
 *  input[2] = 5;
 
764
 *  input[3] = 7;
 
765
 *  input[4] = 8;
 
766
 *
 
767
 *  thrust::equal_range(thrust::device, input.begin(), input.end(), 0); // returns [input.begin(), input.begin() + 1)
 
768
 *  thrust::equal_range(thrust::device, input.begin(), input.end(), 1); // returns [input.begin() + 1, input.begin() + 1)
 
769
 *  thrust::equal_range(thrust::device, input.begin(), input.end(), 2); // returns [input.begin() + 1, input.begin() + 2)
 
770
 *  thrust::equal_range(thrust::device, input.begin(), input.end(), 3); // returns [input.begin() + 2, input.begin() + 2)
 
771
 *  thrust::equal_range(thrust::device, input.begin(), input.end(), 8); // returns [input.begin() + 4, input.end)
 
772
 *  thrust::equal_range(thrust::device, input.begin(), input.end(), 9); // returns [input.end(), input.end)
 
773
 *  \endcode
 
774
 *
 
775
 *  \see http://www.sgi.com/tech/stl/equal_range.html
 
776
 *  \see \p lower_bound
 
777
 *  \see \p upper_bound
 
778
 *  \see \p binary_search
 
779
 */
 
780
template <typename DerivedPolicy, typename ForwardIterator, typename LessThanComparable>
 
781
thrust::pair<ForwardIterator, ForwardIterator>
 
782
equal_range(const thrust::detail::execution_policy_base<DerivedPolicy> &exec,
 
783
            ForwardIterator first,
 
784
            ForwardIterator last,
 
785
            const LessThanComparable& value);
 
786
 
 
787
 
 
788
/*! \p equal_range is a version of binary search: it attempts to find
 
789
 * the element value in an ordered range <tt>[first, last)</tt>. The 
 
790
 * value returned by \p equal_range is essentially a combination of
 
791
 * the values returned by \p lower_bound and \p upper_bound: it returns
 
792
 * a \p pair of iterators \c i and \c j such that \c i is the first
 
793
 * position where value could be inserted without violating the 
 
794
 * ordering and \c j is the last position where value could be inserted
 
795
 * without violating the ordering. It follows that every element in the
 
796
 * range <tt>[i, j)</tt> is equivalent to value, and that 
 
797
 * <tt>[i, j)</tt> is the largest subrange of <tt>[first, last)</tt> that
 
798
 * has this property. 
 
799
 *
 
800
 * This version of \p equal_range returns a \p pair of iterators 
 
801
 * <tt>[i, j)</tt>, where \c i is the furthermost iterator in 
 
802
 * <tt>[first, last)</tt> such that, for every iterator \c k in 
 
803
 * <tt>[first, i)</tt>, <tt>*k < value</tt>.  \c j is the furthermost
 
804
 * iterator in <tt>[first, last)</tt> such that, for every iterator 
 
805
 * \c k in <tt>[first, j)</tt>, <tt>value < *k</tt> is \c false. 
 
806
 * For every iterator \c k in <tt>[i, j)</tt>, neither 
 
807
 * <tt>value < *k</tt> nor <tt>*k < value</tt> is \c true.
 
808
 *
384
809
 *  \param first The beginning of the ordered sequence.
385
810
 *  \param last The end of the ordered sequence.
386
811
 *  \param value The value to be searched.
423
848
            ForwardIterator last,
424
849
            const LessThanComparable& value);
425
850
 
 
851
 
 
852
/*! \p equal_range is a version of binary search: it attempts to find
 
853
 * the element value in an ordered range <tt>[first, last)</tt>. The 
 
854
 * value returned by \p equal_range is essentially a combination of
 
855
 * the values returned by \p lower_bound and \p upper_bound: it returns
 
856
 * a \p pair of iterators \c i and \c j such that \c i is the first
 
857
 * position where value could be inserted without violating the 
 
858
 * ordering and \c j is the last position where value could be inserted
 
859
 * without violating the ordering. It follows that every element in the
 
860
 * range <tt>[i, j)</tt> is equivalent to value, and that 
 
861
 * <tt>[i, j)</tt> is the largest subrange of <tt>[first, last)</tt> that
 
862
 * has this property. 
 
863
 *
 
864
 * This version of \p equal_range returns a \p pair of iterators 
 
865
 * <tt>[i, j)</tt>. \c i is the furthermost iterator in 
 
866
 * <tt>[first, last)</tt> such that, for every iterator \c k in 
 
867
 * <tt>[first, i)</tt>, <tt>comp(*k, value)</tt> is \c true.
 
868
 * \c j is the furthermost iterator in <tt>[first, last)</tt> such
 
869
 * that, for every iterator \c k in <tt>[first, last)</tt>, 
 
870
 * <tt>comp(value, *k)</tt> is \c false. For every iterator \c k 
 
871
 * in <tt>[i, j)</tt>, neither <tt>comp(value, *k)</tt> nor 
 
872
 * <tt>comp(*k, value)</tt> is \c true.
 
873
 *
 
874
 * The algorithm's execution is parallelized as determined by \p exec.
 
875
 *
 
876
 *  \param exec The execution policy to use for parallelization.
 
877
 *  \param first The beginning of the ordered sequence.
 
878
 *  \param last The end of the ordered sequence.
 
879
 *  \param value The value to be searched.
 
880
 *  \param comp The comparison operator.
 
881
 *  \return A \p pair of iterators <tt>[i, j)</tt> that define the range of equivalent elements.
 
882
 * 
 
883
 *  \tparam DerivedPolicy The name of the derived execution policy.
 
884
 *  \tparam ForwardIterator is a model of <a href="http://www.sgi.com/tech/stl/ForwardIterator">Forward Iterator</a>.
 
885
 *  \tparam T is comparable to \p ForwardIterator's \c value_type.
 
886
 *  \tparam StrictWeakOrdering is a model of <a href="http://www.sgi.com/tech/stl/StrictWeakOrdering.html">Strict Weak Ordering</a>.
 
887
 *
 
888
 *  The following code snippet demonstrates how to use \p equal_range
 
889
 *  to search for values in a ordered range using the \p thrust::device execution policy for parallelization:
 
890
 *
 
891
 *  \code
 
892
 *  #include <thrust/binary_search.h>
 
893
 *  #include <thrust/device_vector.h>
 
894
 *  #include <thrust/functional.h>
 
895
 *  #include <thrust/execution_policy.h>
 
896
 *  ...
 
897
 *  thrust::device_vector<int> input(5);
 
898
 *
 
899
 *  input[0] = 0;
 
900
 *  input[1] = 2;
 
901
 *  input[2] = 5;
 
902
 *  input[3] = 7;
 
903
 *  input[4] = 8;
 
904
 *
 
905
 *  thrust::equal_range(thrust::device, input.begin(), input.end(), 0, thrust::less<int>()); // returns [input.begin(), input.begin() + 1)
 
906
 *  thrust::equal_range(thrust::device, input.begin(), input.end(), 1, thrust::less<int>()); // returns [input.begin() + 1, input.begin() + 1)
 
907
 *  thrust::equal_range(thrust::device, input.begin(), input.end(), 2, thrust::less<int>()); // returns [input.begin() + 1, input.begin() + 2)
 
908
 *  thrust::equal_range(thrust::device, input.begin(), input.end(), 3, thrust::less<int>()); // returns [input.begin() + 2, input.begin() + 2)
 
909
 *  thrust::equal_range(thrust::device, input.begin(), input.end(), 8, thrust::less<int>()); // returns [input.begin() + 4, input.end)
 
910
 *  thrust::equal_range(thrust::device, input.begin(), input.end(), 9, thrust::less<int>()); // returns [input.end(), input.end)
 
911
 *  \endcode
 
912
 *
 
913
 *  \see http://www.sgi.com/tech/stl/equal_range.html
 
914
 *  \see \p lower_bound
 
915
 *  \see \p upper_bound
 
916
 *  \see \p binary_search
 
917
 */
 
918
template <typename DerivedPolicy, typename ForwardIterator, typename T, typename StrictWeakOrdering>
 
919
thrust::pair<ForwardIterator, ForwardIterator>
 
920
equal_range(const thrust::detail::execution_policy_base<DerivedPolicy> &exec,
 
921
            ForwardIterator first,
 
922
            ForwardIterator last,
 
923
            const T& value,
 
924
            StrictWeakOrdering comp);
 
925
 
 
926
 
426
927
/*! \p equal_range is a version of binary search: it attempts to find
427
928
 * the element value in an ordered range <tt>[first, last)</tt>. The 
428
929
 * value returned by \p equal_range is essentially a combination of
491
992
            const T& value,
492
993
            StrictWeakOrdering comp);
493
994
 
 
995
 
494
996
/*! \addtogroup vectorized_binary_search Vectorized Searches
495
997
 *  \ingroup binary_search
496
998
 *  \{
497
999
 */
498
1000
 
 
1001
 
499
1002
//////////////////////
500
1003
// Vector Functions //
501
1004
//////////////////////
502
1005
 
503
 
/*! \p lower_bound is a vectorized version of binary search: for each 
504
 
 * iterator \c v in <tt>[values_first, values_last)</tt> it attempts to
505
 
 * find the value <tt>*v</tt> in an ordered range <tt>[first, last)</tt>.
506
 
 * Specifically, it returns the index of first position where value could
507
 
 * be inserted without violating the ordering.
508
 
 *
509
 
 *  \param first The beginning of the ordered sequence.
510
 
 *  \param last The end of the ordered sequence.
511
 
 *  \param values_first The beginning of the search values sequence.
512
 
 *  \param values_last The end of the search values sequence.
513
 
 *  \param output The beginning of the output sequence.
514
 
 * 
515
 
 *  \tparam ForwardIterator is a model of <a href="http://www.sgi.com/tech/stl/ForwardIterator">Forward Iterator</a>.
516
 
 *  \tparam InputIterator is a model of <a href="http://www.sgi.com/tech/stl/InputIterator.html">Input Iterator</a>.
517
 
 *                        and \c InputIterator's \c value_type is <a href="http://www.sgi.com/tech/stl/LessThanComparable.html">LessThanComparable</a>.
518
 
 *  \tparam OutputIterator is a model of <a href="http://www.sgi.com/tech/stl/OutputIterator.html">Output Iterator</a>.
519
 
 *                        and \c ForwardIterator's difference_type is convertible to \c OutputIterator's \c value_type.
520
 
 *
521
 
 *  The following code snippet demonstrates how to use \p lower_bound
522
 
 *  to search for multiple values in a ordered range.
523
 
 *
524
 
 *  \code
525
 
 *  #include <thrust/binary_search.h>
526
 
 *  #include <thrust/device_vector.h>
527
 
 *  ...
528
 
 *  thrust::device_vector<int> input(5);
529
 
 *
530
 
 *  input[0] = 0;
531
 
 *  input[1] = 2;
532
 
 *  input[2] = 5;
533
 
 *  input[3] = 7;
534
 
 *  input[4] = 8;
535
 
 *
536
 
 *  thrust::device_vector<int> values(6);
537
 
 *  values[0] = 0; 
538
 
 *  values[1] = 1;
539
 
 *  values[2] = 2;
540
 
 *  values[3] = 3;
541
 
 *  values[4] = 8;
542
 
 *  values[5] = 9;
543
 
 *
544
 
 *  thrust::device_vector<unsigned int> output(6);
545
 
 *
546
 
 *  thrust::lower_bound(input.begin(), input.end(),
547
 
 *                      values.begin(), values.end(),
548
 
 *                      output.begin());
549
 
 *
550
 
 *  // output is now [0, 1, 1, 2, 4, 5]
551
 
 *  \endcode
552
 
 *
553
 
 *  \see http://www.sgi.com/tech/stl/lower_bound.html
554
 
 *  \see \p upper_bound
555
 
 *  \see \p equal_range
556
 
 *  \see \p binary_search
557
 
 */
558
 
template <class ForwardIterator, class InputIterator, class OutputIterator>
559
 
OutputIterator lower_bound(ForwardIterator first, 
560
 
                           ForwardIterator last,
561
 
                           InputIterator values_first, 
562
 
                           InputIterator values_last,
563
 
                           OutputIterator output);
564
 
 
565
 
 
566
 
/*! \p lower_bound is a vectorized version of binary search: for each 
567
 
 * iterator \c v in <tt>[values_first, values_last)</tt> it attempts to
568
 
 * find the value <tt>*v</tt> in an ordered range <tt>[first, last)</tt>.
569
 
 * Specifically, it returns the index of first position where value could
570
 
 * be inserted without violating the ordering.  This version of 
571
 
 * \p lower_bound uses function object \c comp for comparison.
572
 
 *
573
 
 *  \param first The beginning of the ordered sequence.
574
 
 *  \param last The end of the ordered sequence.
575
 
 *  \param values_first The beginning of the search values sequence.
576
 
 *  \param values_last The end of the search values sequence.
577
 
 *  \param output The beginning of the output sequence.
578
 
 *  \param comp The comparison operator.
579
 
 * 
580
 
 *  \tparam ForwardIterator is a model of <a href="http://www.sgi.com/tech/stl/ForwardIterator">Forward Iterator</a>.
581
 
 *  \tparam InputIterator is a model of <a href="http://www.sgi.com/tech/stl/InputIterator.html">Input Iterator</a>.
582
 
 *                        and \c InputIterator's \c value_type is comparable to \p ForwardIterator's \c value_type.
583
 
 *  \tparam OutputIterator is a model of <a href="http://www.sgi.com/tech/stl/OutputIterator.html">Output Iterator</a>.
584
 
 *                        and \c ForwardIterator's difference_type is convertible to \c OutputIterator's \c value_type.
585
 
 *  \tparam StrictWeakOrdering is a model of <a href="http://www.sgi.com/tech/stl/StrictWeakOrdering.html">Strict Weak Ordering</a>.
586
 
 *
587
 
 *  The following code snippet demonstrates how to use \p lower_bound
588
 
 *  to search for multiple values in a ordered range.
589
 
 *
590
 
 *  \code
591
 
 *  #include <thrust/binary_search.h>
592
 
 *  #include <thrust/device_vector.h>
593
 
 *  #include <thrust/functional.h>
594
 
 *  ...
595
 
 *  thrust::device_vector<int> input(5);
596
 
 *
597
 
 *  input[0] = 0;
598
 
 *  input[1] = 2;
599
 
 *  input[2] = 5;
600
 
 *  input[3] = 7;
601
 
 *  input[4] = 8;
602
 
 *
603
 
 *  thrust::device_vector<int> values(6);
604
 
 *  values[0] = 0; 
605
 
 *  values[1] = 1;
606
 
 *  values[2] = 2;
607
 
 *  values[3] = 3;
608
 
 *  values[4] = 8;
609
 
 *  values[5] = 9;
610
 
 *
611
 
 *  thrust::device_vector<unsigned int> output(6);
612
 
 *
613
 
 *  thrust::lower_bound(input.begin(), input.end(),
614
 
 *                      values.begin(), values.end(), 
615
 
 *                      output.begin(),
616
 
 *                      thrust::less<int>());
617
 
 *
618
 
 *  // output is now [0, 1, 1, 2, 4, 5]
619
 
 *  \endcode
620
 
 *
621
 
 *  \see http://www.sgi.com/tech/stl/lower_bound.html
622
 
 *  \see \p upper_bound
623
 
 *  \see \p equal_range
624
 
 *  \see \p binary_search
625
 
 */
626
 
template <class ForwardIterator, class InputIterator, class OutputIterator, class StrictWeakOrdering>
627
 
OutputIterator lower_bound(ForwardIterator first, 
628
 
                           ForwardIterator last,
629
 
                           InputIterator values_first, 
630
 
                           InputIterator values_last,
631
 
                           OutputIterator output,
632
 
                           StrictWeakOrdering comp);
633
 
 
634
 
 
635
 
/*! \p upper_bound is a vectorized version of binary search: for each 
636
 
 * iterator \c v in <tt>[values_first, values_last)</tt> it attempts to
637
 
 * find the value <tt>*v</tt> in an ordered range <tt>[first, last)</tt>.
638
 
 * Specifically, it returns the index of last position where value could
639
 
 * be inserted without violating the ordering.
640
 
 *
641
 
 *  \param first The beginning of the ordered sequence.
642
 
 *  \param last The end of the ordered sequence.
643
 
 *  \param values_first The beginning of the search values sequence.
644
 
 *  \param values_last The end of the search values sequence.
645
 
 *  \param output The beginning of the output sequence.
646
 
 * 
647
 
 *  \tparam ForwardIterator is a model of <a href="http://www.sgi.com/tech/stl/ForwardIterator">Forward Iterator</a>.
648
 
 *  \tparam InputIterator is a model of <a href="http://www.sgi.com/tech/stl/InputIterator.html">Input Iterator</a>.
649
 
 *                        and \c InputIterator's \c value_type is <a href="http://www.sgi.com/tech/stl/LessThanComparable.html">LessThanComparable</a>.
650
 
 *  \tparam OutputIterator is a model of <a href="http://www.sgi.com/tech/stl/OutputIterator.html">Output Iterator</a>.
651
 
 *                        and \c ForwardIterator's difference_type is convertible to \c OutputIterator's \c value_type.
652
 
 *
653
 
 *  The following code snippet demonstrates how to use \p lower_bound
654
 
 *  to search for multiple values in a ordered range.
655
 
 *
656
 
 *  \code
657
 
 *  #include <thrust/binary_search.h>
658
 
 *  #include <thrust/device_vector.h>
659
 
 *  ...
660
 
 *  thrust::device_vector<int> input(5);
661
 
 *
662
 
 *  input[0] = 0;
663
 
 *  input[1] = 2;
664
 
 *  input[2] = 5;
665
 
 *  input[3] = 7;
666
 
 *  input[4] = 8;
667
 
 *
668
 
 *  thrust::device_vector<int> values(6);
669
 
 *  values[0] = 0; 
670
 
 *  values[1] = 1;
671
 
 *  values[2] = 2;
672
 
 *  values[3] = 3;
673
 
 *  values[4] = 8;
674
 
 *  values[5] = 9;
675
 
 *
676
 
 *  thrust::device_vector<unsigned int> output(6);
677
 
 *
678
 
 *  thrust::upper_bound(input.begin(), input.end(),
679
 
 *                      values.begin(), values.end(),
680
 
 *                      output.begin());
681
 
 *
682
 
 *  // output is now [1, 1, 2, 2, 5, 5]
683
 
 *  \endcode
684
 
 *
685
 
 *  \see http://www.sgi.com/tech/stl/upper_bound.html
686
 
 *  \see \p upper_bound
687
 
 *  \see \p equal_range
688
 
 *  \see \p binary_search
689
 
 */
690
 
template <class ForwardIterator, class InputIterator, class OutputIterator>
691
 
OutputIterator upper_bound(ForwardIterator first, 
692
 
                           ForwardIterator last,
693
 
                           InputIterator values_first, 
694
 
                           InputIterator values_last,
695
 
                           OutputIterator output);
696
 
 
697
 
 
698
 
/*! \p upper_bound is a vectorized version of binary search: for each 
699
 
 * iterator \c v in <tt>[values_first, values_last)</tt> it attempts to
700
 
 * find the value <tt>*v</tt> in an ordered range <tt>[first, last)</tt>.
701
 
 * Specifically, it returns the index of first position where value could
702
 
 * be inserted without violating the ordering.  This version of 
703
 
 * \p upper_bound uses function object \c comp for comparison.
704
 
 *
705
 
 *  \param first The beginning of the ordered sequence.
706
 
 *  \param last The end of the ordered sequence.
707
 
 *  \param values_first The beginning of the search values sequence.
708
 
 *  \param values_last The end of the search values sequence.
709
 
 *  \param output The beginning of the output sequence.
710
 
 *  \param comp The comparison operator.
711
 
 * 
712
 
 *  \tparam ForwardIterator is a model of <a href="http://www.sgi.com/tech/stl/ForwardIterator">Forward Iterator</a>.
713
 
 *  \tparam InputIterator is a model of <a href="http://www.sgi.com/tech/stl/InputIterator.html">Input Iterator</a>.
714
 
 *                        and \c InputIterator's \c value_type is comparable to \p ForwardIterator's \c value_type.
715
 
 *  \tparam OutputIterator is a model of <a href="http://www.sgi.com/tech/stl/OutputIterator.html">Output Iterator</a>.
716
 
 *                        and \c ForwardIterator's difference_type is convertible to \c OutputIterator's \c value_type.
717
 
 *  \tparam StrictWeakOrdering is a model of <a href="http://www.sgi.com/tech/stl/StrictWeakOrdering.html">Strict Weak Ordering</a>.
718
 
 *
719
 
 *  The following code snippet demonstrates how to use \p lower_bound
720
 
 *  to search for multiple values in a ordered range.
721
 
 *
722
 
 *  \code
723
 
 *  #include <thrust/binary_search.h>
724
 
 *  #include <thrust/device_vector.h>
725
 
 *  #include <thrust/functional.h>
726
 
 *  ...
727
 
 *  thrust::device_vector<int> input(5);
728
 
 *
729
 
 *  input[0] = 0;
730
 
 *  input[1] = 2;
731
 
 *  input[2] = 5;
732
 
 *  input[3] = 7;
733
 
 *  input[4] = 8;
734
 
 *
735
 
 *  thrust::device_vector<int> values(6);
736
 
 *  values[0] = 0; 
737
 
 *  values[1] = 1;
738
 
 *  values[2] = 2;
739
 
 *  values[3] = 3;
740
 
 *  values[4] = 8;
741
 
 *  values[5] = 9;
742
 
 *
743
 
 *  thrust::device_vector<unsigned int> output(6);
744
 
 *
745
 
 *  thrust::upper_bound(input.begin(), input.end(),
746
 
 *                      values.begin(), values.end(), 
747
 
 *                      output.begin(),
748
 
 *                      thrust::less<int>());
749
 
 *
750
 
 *  // output is now [1, 1, 2, 2, 5, 5]
751
 
 *  \endcode
752
 
 *
753
 
 *  \see http://www.sgi.com/tech/stl/upper_bound.html
754
 
 *  \see \p lower_bound
755
 
 *  \see \p equal_range
756
 
 *  \see \p binary_search
757
 
 */
758
 
template <class ForwardIterator, class InputIterator, class OutputIterator, class StrictWeakOrdering>
759
 
OutputIterator upper_bound(ForwardIterator first, 
760
 
                           ForwardIterator last,
761
 
                           InputIterator values_first, 
762
 
                           InputIterator values_last,
763
 
                           OutputIterator output,
764
 
                           StrictWeakOrdering comp);
765
 
 
766
 
 
767
 
/*! \p binary_search is a vectorized version of binary search: for each 
768
 
 * iterator \c v in <tt>[values_first, values_last)</tt> it attempts to
769
 
 * find the value <tt>*v</tt> in an ordered range <tt>[first, last)</tt>.
770
 
 * It returns \c true if an element that is equivalent to \c value 
771
 
 * is present in <tt>[first, last)</tt> and \c false if no such element
772
 
 * exists.
773
 
 *
774
 
 *  \param first The beginning of the ordered sequence.
775
 
 *  \param last The end of the ordered sequence.
776
 
 *  \param values_first The beginning of the search values sequence.
777
 
 *  \param values_last The end of the search values sequence.
778
 
 *  \param output The beginning of the output sequence.
779
 
 * 
780
 
 *  \tparam ForwardIterator is a model of <a href="http://www.sgi.com/tech/stl/ForwardIterator">Forward Iterator</a>.
781
 
 *  \tparam InputIterator is a model of <a href="http://www.sgi.com/tech/stl/InputIterator.html">Input Iterator</a>.
782
 
 *                        and \c InputIterator's \c value_type is <a href="http://www.sgi.com/tech/stl/LessThanComparable.html">LessThanComparable</a>.
783
 
 *  \tparam OutputIterator is a model of <a href="http://www.sgi.com/tech/stl/OutputIterator.html">Output Iterator</a>.
784
 
 *                        and bool is convertible to \c OutputIterator's \c value_type.
785
 
 *
786
 
 *  The following code snippet demonstrates how to use \p binary_search
787
 
 *  to search for multiple values in a ordered range.
788
 
 *
789
 
 *  \code
790
 
 *  #include <thrust/binary_search.h>
791
 
 *  #include <thrust/device_vector.h>
792
 
 *  ...
793
 
 *  thrust::device_vector<int> input(5);
794
 
 *
795
 
 *  input[0] = 0;
796
 
 *  input[1] = 2;
797
 
 *  input[2] = 5;
798
 
 *  input[3] = 7;
799
 
 *  input[4] = 8;
800
 
 *
801
 
 *  thrust::device_vector<int> values(6);
802
 
 *  values[0] = 0; 
803
 
 *  values[1] = 1;
804
 
 *  values[2] = 2;
805
 
 *  values[3] = 3;
806
 
 *  values[4] = 8;
807
 
 *  values[5] = 9;
808
 
 *
809
 
 *  thrust::device_vector<bool> output(6);
810
 
 *
811
 
 *  thrust::binary_search(input.begin(), input.end(),
812
 
 *                        values.begin(), values.end(),
813
 
 *                        output.begin());
814
 
 *
815
 
 *  // output is now [true, false, true, false, true, false]
816
 
 *  \endcode
817
 
 *
818
 
 *  \see http://www.sgi.com/tech/stl/binary_search.html
819
 
 *  \see \p lower_bound
820
 
 *  \see \p upper_bound
821
 
 *  \see \p equal_range
822
 
 */
823
 
template <class ForwardIterator, class InputIterator, class OutputIterator>
824
 
OutputIterator binary_search(ForwardIterator first, 
825
 
                             ForwardIterator last,
826
 
                             InputIterator values_first, 
827
 
                             InputIterator values_last,
828
 
                             OutputIterator output);
829
 
 
830
 
 
831
 
/*! \p binary_search is a vectorized version of binary search: for each 
832
 
 * iterator \c v in <tt>[values_first, values_last)</tt> it attempts to
833
 
 * find the value <tt>*v</tt> in an ordered range <tt>[first, last)</tt>.
834
 
 * It returns \c true if an element that is equivalent to \c value 
835
 
 * is present in <tt>[first, last)</tt> and \c false if no such element
836
 
 * exists.  This version of \p binary_search uses function object 
837
 
 * \c comp for comparison.
838
 
 *
839
 
 *  \param first The beginning of the ordered sequence.
840
 
 *  \param last The end of the ordered sequence.
841
 
 *  \param values_first The beginning of the search values sequence.
842
 
 *  \param values_last The end of the search values sequence.
843
 
 *  \param output The beginning of the output sequence.
844
 
 *  \param comp The comparison operator.
845
 
 * 
846
 
 *  \tparam ForwardIterator is a model of <a href="http://www.sgi.com/tech/stl/ForwardIterator">Forward Iterator</a>.
847
 
 *  \tparam InputIterator is a model of <a href="http://www.sgi.com/tech/stl/InputIterator.html">Input Iterator</a>.
848
 
 *                        and \c InputIterator's \c value_type is <a href="http://www.sgi.com/tech/stl/LessThanComparable.html">LessThanComparable</a>.
849
 
 *  \tparam OutputIterator is a model of <a href="http://www.sgi.com/tech/stl/OutputIterator.html">Output Iterator</a>.
850
 
 *                        and bool is convertible to \c OutputIterator's \c value_type.
851
 
 *  \tparam StrictWeakOrdering is a model of <a href="http://www.sgi.com/tech/stl/StrictWeakOrdering.html">Strict Weak Ordering</a>.
852
 
 *
853
 
 *  The following code snippet demonstrates how to use \p binary_search
854
 
 *  to search for multiple values in a ordered range.
855
 
 *
856
 
 *  \code
857
 
 *  #include <thrust/binary_search.h>
858
 
 *  #include <thrust/device_vector.h>
859
 
 *  #include <thrust/functional.h>
860
 
 *  ...
861
 
 *  thrust::device_vector<int> input(5);
862
 
 *
863
 
 *  input[0] = 0;
864
 
 *  input[1] = 2;
865
 
 *  input[2] = 5;
866
 
 *  input[3] = 7;
867
 
 *  input[4] = 8;
868
 
 *
869
 
 *  thrust::device_vector<int> values(6);
870
 
 *  values[0] = 0; 
871
 
 *  values[1] = 1;
872
 
 *  values[2] = 2;
873
 
 *  values[3] = 3;
874
 
 *  values[4] = 8;
875
 
 *  values[5] = 9;
876
 
 *
877
 
 *  thrust::device_vector<bool> output(6);
878
 
 *
879
 
 *  thrust::binary_search(input.begin(), input.end(),
880
 
 *                        values.begin(), values.end(),
881
 
 *                        output.begin(),
882
 
 *                        thrust::less<T>());
883
 
 *
884
 
 *  // output is now [true, false, true, false, true, false]
885
 
 *  \endcode
886
 
 *
887
 
 *  \see http://www.sgi.com/tech/stl/binary_search.html
888
 
 *  \see \p lower_bound
889
 
 *  \see \p upper_bound
890
 
 *  \see \p equal_range
891
 
 */
892
 
template <class ForwardIterator, class InputIterator, class OutputIterator, class StrictWeakOrdering>
893
 
OutputIterator binary_search(ForwardIterator first, 
894
 
                             ForwardIterator last,
895
 
                             InputIterator values_first, 
896
 
                             InputIterator values_last,
897
 
                             OutputIterator output,
898
 
                             StrictWeakOrdering comp);
 
1006
 
 
1007
/*! \p lower_bound is a vectorized version of binary search: for each 
 
1008
 * iterator \c v in <tt>[values_first, values_last)</tt> it attempts to
 
1009
 * find the value <tt>*v</tt> in an ordered range <tt>[first, last)</tt>.
 
1010
 * Specifically, it returns the index of first position where value could
 
1011
 * be inserted without violating the ordering.
 
1012
 *
 
1013
 * The algorithm's execution is parallelized as determined by \p exec.
 
1014
 *
 
1015
 *  \param exec The execution policy to use for parallelization.
 
1016
 *  \param first The beginning of the ordered sequence.
 
1017
 *  \param last The end of the ordered sequence.
 
1018
 *  \param values_first The beginning of the search values sequence.
 
1019
 *  \param values_last The end of the search values sequence.
 
1020
 *  \param result The beginning of the output sequence.
 
1021
 * 
 
1022
 *  \tparam DerivedPolicy The name of the derived execution policy.
 
1023
 *  \tparam ForwardIterator is a model of <a href="http://www.sgi.com/tech/stl/ForwardIterator">Forward Iterator</a>.
 
1024
 *  \tparam InputIterator is a model of <a href="http://www.sgi.com/tech/stl/InputIterator.html">Input Iterator</a>.
 
1025
 *                        and \c InputIterator's \c value_type is <a href="http://www.sgi.com/tech/stl/LessThanComparable.html">LessThanComparable</a>.
 
1026
 *  \tparam OutputIterator is a model of <a href="http://www.sgi.com/tech/stl/OutputIterator.html">Output Iterator</a>.
 
1027
 *                        and \c ForwardIterator's difference_type is convertible to \c OutputIterator's \c value_type.
 
1028
 *
 
1029
 *  \pre The ranges <tt>[first,last)</tt> and <tt>[result, result + (last - first))</tt> shall not overlap.
 
1030
 *
 
1031
 *  The following code snippet demonstrates how to use \p lower_bound
 
1032
 *  to search for multiple values in a ordered range using the \p thrust::device execution policy for
 
1033
 *  parallelization:
 
1034
 *
 
1035
 *  \code
 
1036
 *  #include <thrust/binary_search.h>
 
1037
 *  #include <thrust/device_vector.h>
 
1038
 *  #include <thrust/execution_policy.h>
 
1039
 *  ...
 
1040
 *  thrust::device_vector<int> input(5);
 
1041
 *
 
1042
 *  input[0] = 0;
 
1043
 *  input[1] = 2;
 
1044
 *  input[2] = 5;
 
1045
 *  input[3] = 7;
 
1046
 *  input[4] = 8;
 
1047
 *
 
1048
 *  thrust::device_vector<int> values(6);
 
1049
 *  values[0] = 0; 
 
1050
 *  values[1] = 1;
 
1051
 *  values[2] = 2;
 
1052
 *  values[3] = 3;
 
1053
 *  values[4] = 8;
 
1054
 *  values[5] = 9;
 
1055
 *
 
1056
 *  thrust::device_vector<unsigned int> output(6);
 
1057
 *
 
1058
 *  thrust::lower_bound(thrust::device,
 
1059
 *                      input.begin(), input.end(),
 
1060
 *                      values.begin(), values.end(),
 
1061
 *                      output.begin());
 
1062
 *
 
1063
 *  // output is now [0, 1, 1, 2, 4, 5]
 
1064
 *  \endcode
 
1065
 *
 
1066
 *  \see http://www.sgi.com/tech/stl/lower_bound.html
 
1067
 *  \see \p upper_bound
 
1068
 *  \see \p equal_range
 
1069
 *  \see \p binary_search
 
1070
 */
 
1071
template <typename DerivedPolicy, typename ForwardIterator, typename InputIterator, typename OutputIterator>
 
1072
OutputIterator lower_bound(const thrust::detail::execution_policy_base<DerivedPolicy> &exec,
 
1073
                           ForwardIterator first, 
 
1074
                           ForwardIterator last,
 
1075
                           InputIterator values_first, 
 
1076
                           InputIterator values_last,
 
1077
                           OutputIterator result);
 
1078
 
 
1079
 
 
1080
/*! \p lower_bound is a vectorized version of binary search: for each 
 
1081
 * iterator \c v in <tt>[values_first, values_last)</tt> it attempts to
 
1082
 * find the value <tt>*v</tt> in an ordered range <tt>[first, last)</tt>.
 
1083
 * Specifically, it returns the index of first position where value could
 
1084
 * be inserted without violating the ordering.
 
1085
 *
 
1086
 *  \param first The beginning of the ordered sequence.
 
1087
 *  \param last The end of the ordered sequence.
 
1088
 *  \param values_first The beginning of the search values sequence.
 
1089
 *  \param values_last The end of the search values sequence.
 
1090
 *  \param result The beginning of the output sequence.
 
1091
 * 
 
1092
 *  \tparam ForwardIterator is a model of <a href="http://www.sgi.com/tech/stl/ForwardIterator">Forward Iterator</a>.
 
1093
 *  \tparam InputIterator is a model of <a href="http://www.sgi.com/tech/stl/InputIterator.html">Input Iterator</a>.
 
1094
 *                        and \c InputIterator's \c value_type is <a href="http://www.sgi.com/tech/stl/LessThanComparable.html">LessThanComparable</a>.
 
1095
 *  \tparam OutputIterator is a model of <a href="http://www.sgi.com/tech/stl/OutputIterator.html">Output Iterator</a>.
 
1096
 *                        and \c ForwardIterator's difference_type is convertible to \c OutputIterator's \c value_type.
 
1097
 *
 
1098
 *  \pre The ranges <tt>[first,last)</tt> and <tt>[result, result + (last - first))</tt> shall not overlap.
 
1099
 *
 
1100
 *  The following code snippet demonstrates how to use \p lower_bound
 
1101
 *  to search for multiple values in a ordered range.
 
1102
 *
 
1103
 *  \code
 
1104
 *  #include <thrust/binary_search.h>
 
1105
 *  #include <thrust/device_vector.h>
 
1106
 *  ...
 
1107
 *  thrust::device_vector<int> input(5);
 
1108
 *
 
1109
 *  input[0] = 0;
 
1110
 *  input[1] = 2;
 
1111
 *  input[2] = 5;
 
1112
 *  input[3] = 7;
 
1113
 *  input[4] = 8;
 
1114
 *
 
1115
 *  thrust::device_vector<int> values(6);
 
1116
 *  values[0] = 0; 
 
1117
 *  values[1] = 1;
 
1118
 *  values[2] = 2;
 
1119
 *  values[3] = 3;
 
1120
 *  values[4] = 8;
 
1121
 *  values[5] = 9;
 
1122
 *
 
1123
 *  thrust::device_vector<unsigned int> output(6);
 
1124
 *
 
1125
 *  thrust::lower_bound(input.begin(), input.end(),
 
1126
 *                      values.begin(), values.end(),
 
1127
 *                      output.begin());
 
1128
 *
 
1129
 *  // output is now [0, 1, 1, 2, 4, 5]
 
1130
 *  \endcode
 
1131
 *
 
1132
 *  \see http://www.sgi.com/tech/stl/lower_bound.html
 
1133
 *  \see \p upper_bound
 
1134
 *  \see \p equal_range
 
1135
 *  \see \p binary_search
 
1136
 */
 
1137
template <class ForwardIterator, class InputIterator, class OutputIterator>
 
1138
OutputIterator lower_bound(ForwardIterator first, 
 
1139
                           ForwardIterator last,
 
1140
                           InputIterator values_first, 
 
1141
                           InputIterator values_last,
 
1142
                           OutputIterator result);
 
1143
 
 
1144
 
 
1145
/*! \p lower_bound is a vectorized version of binary search: for each 
 
1146
 * iterator \c v in <tt>[values_first, values_last)</tt> it attempts to
 
1147
 * find the value <tt>*v</tt> in an ordered range <tt>[first, last)</tt>.
 
1148
 * Specifically, it returns the index of first position where value could
 
1149
 * be inserted without violating the ordering.  This version of 
 
1150
 * \p lower_bound uses function object \c comp for comparison.
 
1151
 *
 
1152
 * The algorithm's execution is parallelized as determined by \p exec.
 
1153
 *
 
1154
 *  \param exec The execution policy to use for parallelization.
 
1155
 *  \param first The beginning of the ordered sequence.
 
1156
 *  \param last The end of the ordered sequence.
 
1157
 *  \param values_first The beginning of the search values sequence.
 
1158
 *  \param values_last The end of the search values sequence.
 
1159
 *  \param result The beginning of the output sequence.
 
1160
 *  \param comp The comparison operator.
 
1161
 * 
 
1162
 *  \tparam DerivedPolicy The name of the derived execution policy.
 
1163
 *  \tparam ForwardIterator is a model of <a href="http://www.sgi.com/tech/stl/ForwardIterator">Forward Iterator</a>.
 
1164
 *  \tparam InputIterator is a model of <a href="http://www.sgi.com/tech/stl/InputIterator.html">Input Iterator</a>.
 
1165
 *                        and \c InputIterator's \c value_type is comparable to \p ForwardIterator's \c value_type.
 
1166
 *  \tparam OutputIterator is a model of <a href="http://www.sgi.com/tech/stl/OutputIterator.html">Output Iterator</a>.
 
1167
 *                        and \c ForwardIterator's difference_type is convertible to \c OutputIterator's \c value_type.
 
1168
 *  \tparam StrictWeakOrdering is a model of <a href="http://www.sgi.com/tech/stl/StrictWeakOrdering.html">Strict Weak Ordering</a>.
 
1169
 *
 
1170
 *  \pre The ranges <tt>[first,last)</tt> and <tt>[result, result + (last - first))</tt> shall not overlap.
 
1171
 *
 
1172
 *  The following code snippet demonstrates how to use \p lower_bound
 
1173
 *  to search for multiple values in a ordered range.
 
1174
 *
 
1175
 *  \code
 
1176
 *  #include <thrust/binary_search.h>
 
1177
 *  #include <thrust/device_vector.h>
 
1178
 *  #include <thrust/functional.h>
 
1179
 *  #include <thrust/execution_policy.h>
 
1180
 *  ...
 
1181
 *  thrust::device_vector<int> input(5);
 
1182
 *
 
1183
 *  input[0] = 0;
 
1184
 *  input[1] = 2;
 
1185
 *  input[2] = 5;
 
1186
 *  input[3] = 7;
 
1187
 *  input[4] = 8;
 
1188
 *
 
1189
 *  thrust::device_vector<int> values(6);
 
1190
 *  values[0] = 0; 
 
1191
 *  values[1] = 1;
 
1192
 *  values[2] = 2;
 
1193
 *  values[3] = 3;
 
1194
 *  values[4] = 8;
 
1195
 *  values[5] = 9;
 
1196
 *
 
1197
 *  thrust::device_vector<unsigned int> output(6);
 
1198
 *
 
1199
 *  thrust::lower_bound(input.begin(), input.end(),
 
1200
 *                      values.begin(), values.end(), 
 
1201
 *                      output.begin(),
 
1202
 *                      thrust::less<int>());
 
1203
 *
 
1204
 *  // output is now [0, 1, 1, 2, 4, 5]
 
1205
 *  \endcode
 
1206
 *
 
1207
 *  \see http://www.sgi.com/tech/stl/lower_bound.html
 
1208
 *  \see \p upper_bound
 
1209
 *  \see \p equal_range
 
1210
 *  \see \p binary_search
 
1211
 */
 
1212
template <typename DerivedPolicy, typename ForwardIterator, typename InputIterator, typename OutputIterator, typename StrictWeakOrdering>
 
1213
OutputIterator lower_bound(const thrust::detail::execution_policy_base<DerivedPolicy> &exec,
 
1214
                           ForwardIterator first, 
 
1215
                           ForwardIterator last,
 
1216
                           InputIterator values_first, 
 
1217
                           InputIterator values_last,
 
1218
                           OutputIterator result,
 
1219
                           StrictWeakOrdering comp);
 
1220
 
 
1221
 
 
1222
/*! \p lower_bound is a vectorized version of binary search: for each 
 
1223
 * iterator \c v in <tt>[values_first, values_last)</tt> it attempts to
 
1224
 * find the value <tt>*v</tt> in an ordered range <tt>[first, last)</tt>.
 
1225
 * Specifically, it returns the index of first position where value could
 
1226
 * be inserted without violating the ordering.  This version of 
 
1227
 * \p lower_bound uses function object \c comp for comparison.
 
1228
 *
 
1229
 *  \param first The beginning of the ordered sequence.
 
1230
 *  \param last The end of the ordered sequence.
 
1231
 *  \param values_first The beginning of the search values sequence.
 
1232
 *  \param values_last The end of the search values sequence.
 
1233
 *  \param result The beginning of the output sequence.
 
1234
 *  \param comp The comparison operator.
 
1235
 * 
 
1236
 *  \tparam ForwardIterator is a model of <a href="http://www.sgi.com/tech/stl/ForwardIterator">Forward Iterator</a>.
 
1237
 *  \tparam InputIterator is a model of <a href="http://www.sgi.com/tech/stl/InputIterator.html">Input Iterator</a>.
 
1238
 *                        and \c InputIterator's \c value_type is comparable to \p ForwardIterator's \c value_type.
 
1239
 *  \tparam OutputIterator is a model of <a href="http://www.sgi.com/tech/stl/OutputIterator.html">Output Iterator</a>.
 
1240
 *                        and \c ForwardIterator's difference_type is convertible to \c OutputIterator's \c value_type.
 
1241
 *  \tparam StrictWeakOrdering is a model of <a href="http://www.sgi.com/tech/stl/StrictWeakOrdering.html">Strict Weak Ordering</a>.
 
1242
 *
 
1243
 *  \pre The ranges <tt>[first,last)</tt> and <tt>[result, result + (last - first))</tt> shall not overlap.
 
1244
 *
 
1245
 *  The following code snippet demonstrates how to use \p lower_bound
 
1246
 *  to search for multiple values in a ordered range.
 
1247
 *
 
1248
 *  \code
 
1249
 *  #include <thrust/binary_search.h>
 
1250
 *  #include <thrust/device_vector.h>
 
1251
 *  #include <thrust/functional.h>
 
1252
 *  ...
 
1253
 *  thrust::device_vector<int> input(5);
 
1254
 *
 
1255
 *  input[0] = 0;
 
1256
 *  input[1] = 2;
 
1257
 *  input[2] = 5;
 
1258
 *  input[3] = 7;
 
1259
 *  input[4] = 8;
 
1260
 *
 
1261
 *  thrust::device_vector<int> values(6);
 
1262
 *  values[0] = 0; 
 
1263
 *  values[1] = 1;
 
1264
 *  values[2] = 2;
 
1265
 *  values[3] = 3;
 
1266
 *  values[4] = 8;
 
1267
 *  values[5] = 9;
 
1268
 *
 
1269
 *  thrust::device_vector<unsigned int> output(6);
 
1270
 *
 
1271
 *  thrust::lower_bound(input.begin(), input.end(),
 
1272
 *                      values.begin(), values.end(), 
 
1273
 *                      output.begin(),
 
1274
 *                      thrust::less<int>());
 
1275
 *
 
1276
 *  // output is now [0, 1, 1, 2, 4, 5]
 
1277
 *  \endcode
 
1278
 *
 
1279
 *  \see http://www.sgi.com/tech/stl/lower_bound.html
 
1280
 *  \see \p upper_bound
 
1281
 *  \see \p equal_range
 
1282
 *  \see \p binary_search
 
1283
 */
 
1284
template <class ForwardIterator, class InputIterator, class OutputIterator, class StrictWeakOrdering>
 
1285
OutputIterator lower_bound(ForwardIterator first, 
 
1286
                           ForwardIterator last,
 
1287
                           InputIterator values_first, 
 
1288
                           InputIterator values_last,
 
1289
                           OutputIterator result,
 
1290
                           StrictWeakOrdering comp);
 
1291
 
 
1292
 
 
1293
/*! \p upper_bound is a vectorized version of binary search: for each 
 
1294
 * iterator \c v in <tt>[values_first, values_last)</tt> it attempts to
 
1295
 * find the value <tt>*v</tt> in an ordered range <tt>[first, last)</tt>.
 
1296
 * Specifically, it returns the index of last position where value could
 
1297
 * be inserted without violating the ordering.
 
1298
 *
 
1299
 * The algorithm's execution is parallelized as determined by \p exec.
 
1300
 *
 
1301
 *  \param exec The execution policy to use for parallelization.
 
1302
 *  \param first The beginning of the ordered sequence.
 
1303
 *  \param last The end of the ordered sequence.
 
1304
 *  \param values_first The beginning of the search values sequence.
 
1305
 *  \param values_last The end of the search values sequence.
 
1306
 *  \param result The beginning of the output sequence.
 
1307
 * 
 
1308
 *  \tparam DerivedPolicy The name of the derived execution policy.
 
1309
 *  \tparam ForwardIterator is a model of <a href="http://www.sgi.com/tech/stl/ForwardIterator">Forward Iterator</a>.
 
1310
 *  \tparam InputIterator is a model of <a href="http://www.sgi.com/tech/stl/InputIterator.html">Input Iterator</a>.
 
1311
 *                        and \c InputIterator's \c value_type is <a href="http://www.sgi.com/tech/stl/LessThanComparable.html">LessThanComparable</a>.
 
1312
 *  \tparam OutputIterator is a model of <a href="http://www.sgi.com/tech/stl/OutputIterator.html">Output Iterator</a>.
 
1313
 *                        and \c ForwardIterator's difference_type is convertible to \c OutputIterator's \c value_type.
 
1314
 *
 
1315
 *  \pre The ranges <tt>[first,last)</tt> and <tt>[result, result + (last - first))</tt> shall not overlap.
 
1316
 *
 
1317
 *  The following code snippet demonstrates how to use \p lower_bound
 
1318
 *  to search for multiple values in a ordered range using the \p thrust::device execution policy for
 
1319
 *  parallelization:
 
1320
 *
 
1321
 *  \code
 
1322
 *  #include <thrust/binary_search.h>
 
1323
 *  #include <thrust/device_vector.h>
 
1324
 *  #include <thrust/execution_policy.h>
 
1325
 *  ...
 
1326
 *  thrust::device_vector<int> input(5);
 
1327
 *
 
1328
 *  input[0] = 0;
 
1329
 *  input[1] = 2;
 
1330
 *  input[2] = 5;
 
1331
 *  input[3] = 7;
 
1332
 *  input[4] = 8;
 
1333
 *
 
1334
 *  thrust::device_vector<int> values(6);
 
1335
 *  values[0] = 0; 
 
1336
 *  values[1] = 1;
 
1337
 *  values[2] = 2;
 
1338
 *  values[3] = 3;
 
1339
 *  values[4] = 8;
 
1340
 *  values[5] = 9;
 
1341
 *
 
1342
 *  thrust::device_vector<unsigned int> output(6);
 
1343
 *
 
1344
 *  thrust::upper_bound(thrust::device,
 
1345
 *                      input.begin(), input.end(),
 
1346
 *                      values.begin(), values.end(),
 
1347
 *                      output.begin());
 
1348
 *
 
1349
 *  // output is now [1, 1, 2, 2, 5, 5]
 
1350
 *  \endcode
 
1351
 *
 
1352
 *  \see http://www.sgi.com/tech/stl/upper_bound.html
 
1353
 *  \see \p upper_bound
 
1354
 *  \see \p equal_range
 
1355
 *  \see \p binary_search
 
1356
 */
 
1357
template <typename DerivedPolicy, typename ForwardIterator, typename InputIterator, typename OutputIterator>
 
1358
OutputIterator upper_bound(const thrust::detail::execution_policy_base<DerivedPolicy> &exec,
 
1359
                           ForwardIterator first, 
 
1360
                           ForwardIterator last,
 
1361
                           InputIterator values_first, 
 
1362
                           InputIterator values_last,
 
1363
                           OutputIterator result);
 
1364
 
 
1365
 
 
1366
/*! \p upper_bound is a vectorized version of binary search: for each 
 
1367
 * iterator \c v in <tt>[values_first, values_last)</tt> it attempts to
 
1368
 * find the value <tt>*v</tt> in an ordered range <tt>[first, last)</tt>.
 
1369
 * Specifically, it returns the index of last position where value could
 
1370
 * be inserted without violating the ordering.
 
1371
 *
 
1372
 *  \param first The beginning of the ordered sequence.
 
1373
 *  \param last The end of the ordered sequence.
 
1374
 *  \param values_first The beginning of the search values sequence.
 
1375
 *  \param values_last The end of the search values sequence.
 
1376
 *  \param result The beginning of the output sequence.
 
1377
 * 
 
1378
 *  \tparam ForwardIterator is a model of <a href="http://www.sgi.com/tech/stl/ForwardIterator">Forward Iterator</a>.
 
1379
 *  \tparam InputIterator is a model of <a href="http://www.sgi.com/tech/stl/InputIterator.html">Input Iterator</a>.
 
1380
 *                        and \c InputIterator's \c value_type is <a href="http://www.sgi.com/tech/stl/LessThanComparable.html">LessThanComparable</a>.
 
1381
 *  \tparam OutputIterator is a model of <a href="http://www.sgi.com/tech/stl/OutputIterator.html">Output Iterator</a>.
 
1382
 *                        and \c ForwardIterator's difference_type is convertible to \c OutputIterator's \c value_type.
 
1383
 *
 
1384
 *  \pre The ranges <tt>[first,last)</tt> and <tt>[result, result + (last - first))</tt> shall not overlap.
 
1385
 *
 
1386
 *  The following code snippet demonstrates how to use \p lower_bound
 
1387
 *  to search for multiple values in a ordered range.
 
1388
 *
 
1389
 *  \code
 
1390
 *  #include <thrust/binary_search.h>
 
1391
 *  #include <thrust/device_vector.h>
 
1392
 *  ...
 
1393
 *  thrust::device_vector<int> input(5);
 
1394
 *
 
1395
 *  input[0] = 0;
 
1396
 *  input[1] = 2;
 
1397
 *  input[2] = 5;
 
1398
 *  input[3] = 7;
 
1399
 *  input[4] = 8;
 
1400
 *
 
1401
 *  thrust::device_vector<int> values(6);
 
1402
 *  values[0] = 0; 
 
1403
 *  values[1] = 1;
 
1404
 *  values[2] = 2;
 
1405
 *  values[3] = 3;
 
1406
 *  values[4] = 8;
 
1407
 *  values[5] = 9;
 
1408
 *
 
1409
 *  thrust::device_vector<unsigned int> output(6);
 
1410
 *
 
1411
 *  thrust::upper_bound(input.begin(), input.end(),
 
1412
 *                      values.begin(), values.end(),
 
1413
 *                      output.begin());
 
1414
 *
 
1415
 *  // output is now [1, 1, 2, 2, 5, 5]
 
1416
 *  \endcode
 
1417
 *
 
1418
 *  \see http://www.sgi.com/tech/stl/upper_bound.html
 
1419
 *  \see \p upper_bound
 
1420
 *  \see \p equal_range
 
1421
 *  \see \p binary_search
 
1422
 */
 
1423
template <class ForwardIterator, class InputIterator, class OutputIterator>
 
1424
OutputIterator upper_bound(ForwardIterator first, 
 
1425
                           ForwardIterator last,
 
1426
                           InputIterator values_first, 
 
1427
                           InputIterator values_last,
 
1428
                           OutputIterator result);
 
1429
 
 
1430
 
 
1431
/*! \p upper_bound is a vectorized version of binary search: for each 
 
1432
 * iterator \c v in <tt>[values_first, values_last)</tt> it attempts to
 
1433
 * find the value <tt>*v</tt> in an ordered range <tt>[first, last)</tt>.
 
1434
 * Specifically, it returns the index of first position where value could
 
1435
 * be inserted without violating the ordering.  This version of 
 
1436
 * \p upper_bound uses function object \c comp for comparison.
 
1437
 *
 
1438
 * The algorithm's execution is parallelized as determined by \p exec.
 
1439
 *
 
1440
 *  \param exec The execution policy to use for parallelization.
 
1441
 *  \param first The beginning of the ordered sequence.
 
1442
 *  \param last The end of the ordered sequence.
 
1443
 *  \param values_first The beginning of the search values sequence.
 
1444
 *  \param values_last The end of the search values sequence.
 
1445
 *  \param result The beginning of the output sequence.
 
1446
 *  \param comp The comparison operator.
 
1447
 * 
 
1448
 *  \tparam DerivedPolicy The name of the derived execution policy.
 
1449
 *  \tparam ForwardIterator is a model of <a href="http://www.sgi.com/tech/stl/ForwardIterator">Forward Iterator</a>.
 
1450
 *  \tparam InputIterator is a model of <a href="http://www.sgi.com/tech/stl/InputIterator.html">Input Iterator</a>.
 
1451
 *                        and \c InputIterator's \c value_type is comparable to \p ForwardIterator's \c value_type.
 
1452
 *  \tparam OutputIterator is a model of <a href="http://www.sgi.com/tech/stl/OutputIterator.html">Output Iterator</a>.
 
1453
 *                        and \c ForwardIterator's difference_type is convertible to \c OutputIterator's \c value_type.
 
1454
 *  \tparam StrictWeakOrdering is a model of <a href="http://www.sgi.com/tech/stl/StrictWeakOrdering.html">Strict Weak Ordering</a>.
 
1455
 *
 
1456
 *  \pre The ranges <tt>[first,last)</tt> and <tt>[result, result + (last - first))</tt> shall not overlap.
 
1457
 *
 
1458
 *  The following code snippet demonstrates how to use \p lower_bound
 
1459
 *  to search for multiple values in a ordered range using the \p thrust::device execution policy for
 
1460
 *  parallelization:
 
1461
 *
 
1462
 *  \code
 
1463
 *  #include <thrust/binary_search.h>
 
1464
 *  #include <thrust/device_vector.h>
 
1465
 *  #include <thrust/functional.h>
 
1466
 *  #include <thrust/execution_policy.h>
 
1467
 *  ...
 
1468
 *  thrust::device_vector<int> input(5);
 
1469
 *
 
1470
 *  input[0] = 0;
 
1471
 *  input[1] = 2;
 
1472
 *  input[2] = 5;
 
1473
 *  input[3] = 7;
 
1474
 *  input[4] = 8;
 
1475
 *
 
1476
 *  thrust::device_vector<int> values(6);
 
1477
 *  values[0] = 0; 
 
1478
 *  values[1] = 1;
 
1479
 *  values[2] = 2;
 
1480
 *  values[3] = 3;
 
1481
 *  values[4] = 8;
 
1482
 *  values[5] = 9;
 
1483
 *
 
1484
 *  thrust::device_vector<unsigned int> output(6);
 
1485
 *
 
1486
 *  thrust::upper_bound(thrust::device,
 
1487
 *                      input.begin(), input.end(),
 
1488
 *                      values.begin(), values.end(), 
 
1489
 *                      output.begin(),
 
1490
 *                      thrust::less<int>());
 
1491
 *
 
1492
 *  // output is now [1, 1, 2, 2, 5, 5]
 
1493
 *  \endcode
 
1494
 *
 
1495
 *  \see http://www.sgi.com/tech/stl/upper_bound.html
 
1496
 *  \see \p lower_bound
 
1497
 *  \see \p equal_range
 
1498
 *  \see \p binary_search
 
1499
 */
 
1500
template <typename DerivedPolicy, typename ForwardIterator, typename InputIterator, typename OutputIterator, typename StrictWeakOrdering>
 
1501
OutputIterator upper_bound(const thrust::detail::execution_policy_base<DerivedPolicy> &exec,
 
1502
                           ForwardIterator first, 
 
1503
                           ForwardIterator last,
 
1504
                           InputIterator values_first, 
 
1505
                           InputIterator values_last,
 
1506
                           OutputIterator result,
 
1507
                           StrictWeakOrdering comp);
 
1508
 
 
1509
 
 
1510
/*! \p upper_bound is a vectorized version of binary search: for each 
 
1511
 * iterator \c v in <tt>[values_first, values_last)</tt> it attempts to
 
1512
 * find the value <tt>*v</tt> in an ordered range <tt>[first, last)</tt>.
 
1513
 * Specifically, it returns the index of first position where value could
 
1514
 * be inserted without violating the ordering.  This version of 
 
1515
 * \p upper_bound uses function object \c comp for comparison.
 
1516
 *
 
1517
 *  \param first The beginning of the ordered sequence.
 
1518
 *  \param last The end of the ordered sequence.
 
1519
 *  \param values_first The beginning of the search values sequence.
 
1520
 *  \param values_last The end of the search values sequence.
 
1521
 *  \param result The beginning of the output sequence.
 
1522
 *  \param comp The comparison operator.
 
1523
 * 
 
1524
 *  \tparam ForwardIterator is a model of <a href="http://www.sgi.com/tech/stl/ForwardIterator">Forward Iterator</a>.
 
1525
 *  \tparam InputIterator is a model of <a href="http://www.sgi.com/tech/stl/InputIterator.html">Input Iterator</a>.
 
1526
 *                        and \c InputIterator's \c value_type is comparable to \p ForwardIterator's \c value_type.
 
1527
 *  \tparam OutputIterator is a model of <a href="http://www.sgi.com/tech/stl/OutputIterator.html">Output Iterator</a>.
 
1528
 *                        and \c ForwardIterator's difference_type is convertible to \c OutputIterator's \c value_type.
 
1529
 *  \tparam StrictWeakOrdering is a model of <a href="http://www.sgi.com/tech/stl/StrictWeakOrdering.html">Strict Weak Ordering</a>.
 
1530
 *
 
1531
 *  \pre The ranges <tt>[first,last)</tt> and <tt>[result, result + (last - first))</tt> shall not overlap.
 
1532
 *
 
1533
 *  The following code snippet demonstrates how to use \p lower_bound
 
1534
 *  to search for multiple values in a ordered range.
 
1535
 *
 
1536
 *  \code
 
1537
 *  #include <thrust/binary_search.h>
 
1538
 *  #include <thrust/device_vector.h>
 
1539
 *  #include <thrust/functional.h>
 
1540
 *  ...
 
1541
 *  thrust::device_vector<int> input(5);
 
1542
 *
 
1543
 *  input[0] = 0;
 
1544
 *  input[1] = 2;
 
1545
 *  input[2] = 5;
 
1546
 *  input[3] = 7;
 
1547
 *  input[4] = 8;
 
1548
 *
 
1549
 *  thrust::device_vector<int> values(6);
 
1550
 *  values[0] = 0; 
 
1551
 *  values[1] = 1;
 
1552
 *  values[2] = 2;
 
1553
 *  values[3] = 3;
 
1554
 *  values[4] = 8;
 
1555
 *  values[5] = 9;
 
1556
 *
 
1557
 *  thrust::device_vector<unsigned int> output(6);
 
1558
 *
 
1559
 *  thrust::upper_bound(input.begin(), input.end(),
 
1560
 *                      values.begin(), values.end(), 
 
1561
 *                      output.begin(),
 
1562
 *                      thrust::less<int>());
 
1563
 *
 
1564
 *  // output is now [1, 1, 2, 2, 5, 5]
 
1565
 *  \endcode
 
1566
 *
 
1567
 *  \see http://www.sgi.com/tech/stl/upper_bound.html
 
1568
 *  \see \p lower_bound
 
1569
 *  \see \p equal_range
 
1570
 *  \see \p binary_search
 
1571
 */
 
1572
template <class ForwardIterator, class InputIterator, class OutputIterator, class StrictWeakOrdering>
 
1573
OutputIterator upper_bound(ForwardIterator first, 
 
1574
                           ForwardIterator last,
 
1575
                           InputIterator values_first, 
 
1576
                           InputIterator values_last,
 
1577
                           OutputIterator result,
 
1578
                           StrictWeakOrdering comp);
 
1579
 
 
1580
 
 
1581
/*! \p binary_search is a vectorized version of binary search: for each 
 
1582
 * iterator \c v in <tt>[values_first, values_last)</tt> it attempts to
 
1583
 * find the value <tt>*v</tt> in an ordered range <tt>[first, last)</tt>.
 
1584
 * It returns \c true if an element that is equivalent to \c value 
 
1585
 * is present in <tt>[first, last)</tt> and \c false if no such element
 
1586
 * exists.
 
1587
 *
 
1588
 * The algorithm's execution is parallelized as determined by \p exec.
 
1589
 *
 
1590
 *  \param exec The execution policy to use for parallelization.
 
1591
 *  \param first The beginning of the ordered sequence.
 
1592
 *  \param last The end of the ordered sequence.
 
1593
 *  \param values_first The beginning of the search values sequence.
 
1594
 *  \param values_last The end of the search values sequence.
 
1595
 *  \param result The beginning of the output sequence.
 
1596
 * 
 
1597
 *  \tparam DerivedPolicy The name of the derived execution policy.
 
1598
 *  \tparam ForwardIterator is a model of <a href="http://www.sgi.com/tech/stl/ForwardIterator">Forward Iterator</a>.
 
1599
 *  \tparam InputIterator is a model of <a href="http://www.sgi.com/tech/stl/InputIterator.html">Input Iterator</a>.
 
1600
 *                        and \c InputIterator's \c value_type is <a href="http://www.sgi.com/tech/stl/LessThanComparable.html">LessThanComparable</a>.
 
1601
 *  \tparam OutputIterator is a model of <a href="http://www.sgi.com/tech/stl/OutputIterator.html">Output Iterator</a>.
 
1602
 *                        and bool is convertible to \c OutputIterator's \c value_type.
 
1603
 *
 
1604
 *  \pre The ranges <tt>[first,last)</tt> and <tt>[result, result + (last - first))</tt> shall not overlap.
 
1605
 *
 
1606
 *  The following code snippet demonstrates how to use \p binary_search
 
1607
 *  to search for multiple values in a ordered range using the \p thrust::device execution policy for
 
1608
 *  parallelization:
 
1609
 *
 
1610
 *  \code
 
1611
 *  #include <thrust/binary_search.h>
 
1612
 *  #include <thrust/device_vector.h>
 
1613
 *  #include <thrust/execution_policy.h>
 
1614
 *  ...
 
1615
 *  thrust::device_vector<int> input(5);
 
1616
 *
 
1617
 *  input[0] = 0;
 
1618
 *  input[1] = 2;
 
1619
 *  input[2] = 5;
 
1620
 *  input[3] = 7;
 
1621
 *  input[4] = 8;
 
1622
 *
 
1623
 *  thrust::device_vector<int> values(6);
 
1624
 *  values[0] = 0; 
 
1625
 *  values[1] = 1;
 
1626
 *  values[2] = 2;
 
1627
 *  values[3] = 3;
 
1628
 *  values[4] = 8;
 
1629
 *  values[5] = 9;
 
1630
 *
 
1631
 *  thrust::device_vector<bool> output(6);
 
1632
 *
 
1633
 *  thrust::binary_search(thrust::device,
 
1634
 *                        input.begin(), input.end(),
 
1635
 *                        values.begin(), values.end(),
 
1636
 *                        output.begin());
 
1637
 *
 
1638
 *  // output is now [true, false, true, false, true, false]
 
1639
 *  \endcode
 
1640
 *
 
1641
 *  \see http://www.sgi.com/tech/stl/binary_search.html
 
1642
 *  \see \p lower_bound
 
1643
 *  \see \p upper_bound
 
1644
 *  \see \p equal_range
 
1645
 */
 
1646
template <typename DerivedPolicy, typename ForwardIterator, typename InputIterator, typename OutputIterator>
 
1647
OutputIterator binary_search(const thrust::detail::execution_policy_base<DerivedPolicy> &exec,
 
1648
                             ForwardIterator first, 
 
1649
                             ForwardIterator last,
 
1650
                             InputIterator values_first, 
 
1651
                             InputIterator values_last,
 
1652
                             OutputIterator result);
 
1653
 
 
1654
 
 
1655
/*! \p binary_search is a vectorized version of binary search: for each 
 
1656
 * iterator \c v in <tt>[values_first, values_last)</tt> it attempts to
 
1657
 * find the value <tt>*v</tt> in an ordered range <tt>[first, last)</tt>.
 
1658
 * It returns \c true if an element that is equivalent to \c value 
 
1659
 * is present in <tt>[first, last)</tt> and \c false if no such element
 
1660
 * exists.
 
1661
 *
 
1662
 *  \param first The beginning of the ordered sequence.
 
1663
 *  \param last The end of the ordered sequence.
 
1664
 *  \param values_first The beginning of the search values sequence.
 
1665
 *  \param values_last The end of the search values sequence.
 
1666
 *  \param result The beginning of the output sequence.
 
1667
 * 
 
1668
 *  \tparam ForwardIterator is a model of <a href="http://www.sgi.com/tech/stl/ForwardIterator">Forward Iterator</a>.
 
1669
 *  \tparam InputIterator is a model of <a href="http://www.sgi.com/tech/stl/InputIterator.html">Input Iterator</a>.
 
1670
 *                        and \c InputIterator's \c value_type is <a href="http://www.sgi.com/tech/stl/LessThanComparable.html">LessThanComparable</a>.
 
1671
 *  \tparam OutputIterator is a model of <a href="http://www.sgi.com/tech/stl/OutputIterator.html">Output Iterator</a>.
 
1672
 *                        and bool is convertible to \c OutputIterator's \c value_type.
 
1673
 *
 
1674
 *  \pre The ranges <tt>[first,last)</tt> and <tt>[result, result + (last - first))</tt> shall not overlap.
 
1675
 *
 
1676
 *  The following code snippet demonstrates how to use \p binary_search
 
1677
 *  to search for multiple values in a ordered range.
 
1678
 *
 
1679
 *  \code
 
1680
 *  #include <thrust/binary_search.h>
 
1681
 *  #include <thrust/device_vector.h>
 
1682
 *  ...
 
1683
 *  thrust::device_vector<int> input(5);
 
1684
 *
 
1685
 *  input[0] = 0;
 
1686
 *  input[1] = 2;
 
1687
 *  input[2] = 5;
 
1688
 *  input[3] = 7;
 
1689
 *  input[4] = 8;
 
1690
 *
 
1691
 *  thrust::device_vector<int> values(6);
 
1692
 *  values[0] = 0; 
 
1693
 *  values[1] = 1;
 
1694
 *  values[2] = 2;
 
1695
 *  values[3] = 3;
 
1696
 *  values[4] = 8;
 
1697
 *  values[5] = 9;
 
1698
 *
 
1699
 *  thrust::device_vector<bool> output(6);
 
1700
 *
 
1701
 *  thrust::binary_search(input.begin(), input.end(),
 
1702
 *                        values.begin(), values.end(),
 
1703
 *                        output.begin());
 
1704
 *
 
1705
 *  // output is now [true, false, true, false, true, false]
 
1706
 *  \endcode
 
1707
 *
 
1708
 *  \see http://www.sgi.com/tech/stl/binary_search.html
 
1709
 *  \see \p lower_bound
 
1710
 *  \see \p upper_bound
 
1711
 *  \see \p equal_range
 
1712
 */
 
1713
template <class ForwardIterator, class InputIterator, class OutputIterator>
 
1714
OutputIterator binary_search(ForwardIterator first, 
 
1715
                             ForwardIterator last,
 
1716
                             InputIterator values_first, 
 
1717
                             InputIterator values_last,
 
1718
                             OutputIterator result);
 
1719
 
 
1720
 
 
1721
/*! \p binary_search is a vectorized version of binary search: for each 
 
1722
 * iterator \c v in <tt>[values_first, values_last)</tt> it attempts to
 
1723
 * find the value <tt>*v</tt> in an ordered range <tt>[first, last)</tt>.
 
1724
 * It returns \c true if an element that is equivalent to \c value 
 
1725
 * is present in <tt>[first, last)</tt> and \c false if no such element
 
1726
 * exists.  This version of \p binary_search uses function object 
 
1727
 * \c comp for comparison.
 
1728
 *
 
1729
 * The algorithm's execution is parallelized as determined by \p exec.
 
1730
 *
 
1731
 *  \param exec The execution policy to use for parallelization.
 
1732
 *  \param first The beginning of the ordered sequence.
 
1733
 *  \param last The end of the ordered sequence.
 
1734
 *  \param values_first The beginning of the search values sequence.
 
1735
 *  \param values_last The end of the search values sequence.
 
1736
 *  \param result The beginning of the output sequence.
 
1737
 *  \param comp The comparison operator.
 
1738
 * 
 
1739
 *  \tparam DerivedPolicy The name of the derived execution policy.
 
1740
 *  \tparam ForwardIterator is a model of <a href="http://www.sgi.com/tech/stl/ForwardIterator">Forward Iterator</a>.
 
1741
 *  \tparam InputIterator is a model of <a href="http://www.sgi.com/tech/stl/InputIterator.html">Input Iterator</a>.
 
1742
 *                        and \c InputIterator's \c value_type is <a href="http://www.sgi.com/tech/stl/LessThanComparable.html">LessThanComparable</a>.
 
1743
 *  \tparam OutputIterator is a model of <a href="http://www.sgi.com/tech/stl/OutputIterator.html">Output Iterator</a>.
 
1744
 *                        and bool is convertible to \c OutputIterator's \c value_type.
 
1745
 *  \tparam StrictWeakOrdering is a model of <a href="http://www.sgi.com/tech/stl/StrictWeakOrdering.html">Strict Weak Ordering</a>.
 
1746
 *
 
1747
 *  \pre The ranges <tt>[first,last)</tt> and <tt>[result, result + (last - first))</tt> shall not overlap.
 
1748
 *
 
1749
 *  The following code snippet demonstrates how to use \p binary_search
 
1750
 *  to search for multiple values in a ordered range using the \p thrust::device execution policy for
 
1751
 *  parallelization:
 
1752
 *
 
1753
 *  \code
 
1754
 *  #include <thrust/binary_search.h>
 
1755
 *  #include <thrust/device_vector.h>
 
1756
 *  #include <thrust/functional.h>
 
1757
 *  #include <thrust/execution_policy.h>
 
1758
 *  ...
 
1759
 *  thrust::device_vector<int> input(5);
 
1760
 *
 
1761
 *  input[0] = 0;
 
1762
 *  input[1] = 2;
 
1763
 *  input[2] = 5;
 
1764
 *  input[3] = 7;
 
1765
 *  input[4] = 8;
 
1766
 *
 
1767
 *  thrust::device_vector<int> values(6);
 
1768
 *  values[0] = 0; 
 
1769
 *  values[1] = 1;
 
1770
 *  values[2] = 2;
 
1771
 *  values[3] = 3;
 
1772
 *  values[4] = 8;
 
1773
 *  values[5] = 9;
 
1774
 *
 
1775
 *  thrust::device_vector<bool> output(6);
 
1776
 *
 
1777
 *  thrust::binary_search(thrust::device,
 
1778
 *                        input.begin(), input.end(),
 
1779
 *                        values.begin(), values.end(),
 
1780
 *                        output.begin(),
 
1781
 *                        thrust::less<T>());
 
1782
 *
 
1783
 *  // output is now [true, false, true, false, true, false]
 
1784
 *  \endcode
 
1785
 *
 
1786
 *  \see http://www.sgi.com/tech/stl/binary_search.html
 
1787
 *  \see \p lower_bound
 
1788
 *  \see \p upper_bound
 
1789
 *  \see \p equal_range
 
1790
 */
 
1791
template <typename DerivedPolicy, typename ForwardIterator, typename InputIterator, typename OutputIterator, typename StrictWeakOrdering>
 
1792
OutputIterator binary_search(const thrust::detail::execution_policy_base<DerivedPolicy> &exec,
 
1793
                             ForwardIterator first, 
 
1794
                             ForwardIterator last,
 
1795
                             InputIterator values_first, 
 
1796
                             InputIterator values_last,
 
1797
                             OutputIterator result,
 
1798
                             StrictWeakOrdering comp);
 
1799
 
 
1800
 
 
1801
/*! \p binary_search is a vectorized version of binary search: for each 
 
1802
 * iterator \c v in <tt>[values_first, values_last)</tt> it attempts to
 
1803
 * find the value <tt>*v</tt> in an ordered range <tt>[first, last)</tt>.
 
1804
 * It returns \c true if an element that is equivalent to \c value 
 
1805
 * is present in <tt>[first, last)</tt> and \c false if no such element
 
1806
 * exists.  This version of \p binary_search uses function object 
 
1807
 * \c comp for comparison.
 
1808
 *
 
1809
 *  \param first The beginning of the ordered sequence.
 
1810
 *  \param last The end of the ordered sequence.
 
1811
 *  \param values_first The beginning of the search values sequence.
 
1812
 *  \param values_last The end of the search values sequence.
 
1813
 *  \param result The beginning of the output sequence.
 
1814
 *  \param comp The comparison operator.
 
1815
 * 
 
1816
 *  \tparam ForwardIterator is a model of <a href="http://www.sgi.com/tech/stl/ForwardIterator">Forward Iterator</a>.
 
1817
 *  \tparam InputIterator is a model of <a href="http://www.sgi.com/tech/stl/InputIterator.html">Input Iterator</a>.
 
1818
 *                        and \c InputIterator's \c value_type is <a href="http://www.sgi.com/tech/stl/LessThanComparable.html">LessThanComparable</a>.
 
1819
 *  \tparam OutputIterator is a model of <a href="http://www.sgi.com/tech/stl/OutputIterator.html">Output Iterator</a>.
 
1820
 *                        and bool is convertible to \c OutputIterator's \c value_type.
 
1821
 *  \tparam StrictWeakOrdering is a model of <a href="http://www.sgi.com/tech/stl/StrictWeakOrdering.html">Strict Weak Ordering</a>.
 
1822
 *
 
1823
 *  \pre The ranges <tt>[first,last)</tt> and <tt>[result, result + (last - first))</tt> shall not overlap.
 
1824
 *
 
1825
 *  The following code snippet demonstrates how to use \p binary_search
 
1826
 *  to search for multiple values in a ordered range.
 
1827
 *
 
1828
 *  \code
 
1829
 *  #include <thrust/binary_search.h>
 
1830
 *  #include <thrust/device_vector.h>
 
1831
 *  #include <thrust/functional.h>
 
1832
 *  ...
 
1833
 *  thrust::device_vector<int> input(5);
 
1834
 *
 
1835
 *  input[0] = 0;
 
1836
 *  input[1] = 2;
 
1837
 *  input[2] = 5;
 
1838
 *  input[3] = 7;
 
1839
 *  input[4] = 8;
 
1840
 *
 
1841
 *  thrust::device_vector<int> values(6);
 
1842
 *  values[0] = 0; 
 
1843
 *  values[1] = 1;
 
1844
 *  values[2] = 2;
 
1845
 *  values[3] = 3;
 
1846
 *  values[4] = 8;
 
1847
 *  values[5] = 9;
 
1848
 *
 
1849
 *  thrust::device_vector<bool> output(6);
 
1850
 *
 
1851
 *  thrust::binary_search(input.begin(), input.end(),
 
1852
 *                        values.begin(), values.end(),
 
1853
 *                        output.begin(),
 
1854
 *                        thrust::less<T>());
 
1855
 *
 
1856
 *  // output is now [true, false, true, false, true, false]
 
1857
 *  \endcode
 
1858
 *
 
1859
 *  \see http://www.sgi.com/tech/stl/binary_search.html
 
1860
 *  \see \p lower_bound
 
1861
 *  \see \p upper_bound
 
1862
 *  \see \p equal_range
 
1863
 */
 
1864
template <class ForwardIterator, class InputIterator, class OutputIterator, class StrictWeakOrdering>
 
1865
OutputIterator binary_search(ForwardIterator first, 
 
1866
                             ForwardIterator last,
 
1867
                             InputIterator values_first, 
 
1868
                             InputIterator values_last,
 
1869
                             OutputIterator result,
 
1870
                             StrictWeakOrdering comp);
 
1871
 
899
1872
 
900
1873
/*! \} // end vectorized_binary_search
901
1874
 */
902
1875
 
 
1876
 
903
1877
/*! \} // end binary_search
904
1878
 */
905
1879
 
 
1880
 
906
1881
/*! \} // end searching
907
1882
 */
908
1883
 
 
1884
 
909
1885
} // end namespace thrust
910
1886
 
911
1887
#include <thrust/detail/binary_search.inl>