Skip to content

HTTPS clone URL

Subversion checkout URL

You can clone with
or
.
Download ZIP
Newer
Older
100644 478 lines (442 sloc) 19.237 kB
25342f7 @jaredhoberock Initial import of Komrade v0.9.
jaredhoberock authored
1 /*
ec3e65c @wnbell updated copyright year to 2012
wnbell authored
2 * Copyright 2008-2012 NVIDIA Corporation
25342f7 @jaredhoberock Initial import of Komrade v0.9.
jaredhoberock authored
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17
18 /*! \file partition.h
742f8c0 @jaredhoberock Ensure all files have a reasonable brief Doxygen description.
jaredhoberock authored
19 * \brief Reorganizes a range based on a predicate
25342f7 @jaredhoberock Initial import of Komrade v0.9.
jaredhoberock authored
20 */
21
22 #pragma once
23
4750e2b @wnbell renamed komrade->thrust
wnbell authored
24 #include <thrust/detail/config.h>
4ada12a @jaredhoberock Port partition, partition_copy, stable_partition, stable_partition_co…
jaredhoberock authored
25 #include <thrust/detail/dispatchable.h>
4bfdb57 @jaredhoberock partition_copy abides by the specification in N3092, taking separate …
jaredhoberock authored
26 #include <thrust/pair.h>
25342f7 @jaredhoberock Initial import of Komrade v0.9.
jaredhoberock authored
27
4750e2b @wnbell renamed komrade->thrust
wnbell authored
28 namespace thrust
25342f7 @jaredhoberock Initial import of Komrade v0.9.
jaredhoberock authored
29 {
30
4ada12a @jaredhoberock Port partition, partition_copy, stable_partition, stable_partition_co…
jaredhoberock authored
31
32 template<typename System,
33 typename ForwardIterator,
34 typename Predicate>
35 ForwardIterator partition(thrust::detail::dispatchable_base<System> &system,
36 ForwardIterator first,
37 ForwardIterator last,
38 Predicate pred);
39
40
41 template<typename System,
42 typename InputIterator,
43 typename OutputIterator1,
44 typename OutputIterator2,
45 typename Predicate>
46 thrust::pair<OutputIterator1,OutputIterator2>
47 partition_copy(thrust::detail::dispatchable_base<System> &system,
48 InputIterator first,
49 InputIterator last,
50 OutputIterator1 out_true,
51 OutputIterator2 out_false,
52 Predicate pred);
53
54
55 template<typename System,
56 typename ForwardIterator,
57 typename Predicate>
58 ForwardIterator stable_partition(thrust::detail::dispatchable_base<System> &system,
59 ForwardIterator first,
60 ForwardIterator last,
61 Predicate pred);
62
63
64 template<typename System,
65 typename InputIterator,
66 typename OutputIterator1,
67 typename OutputIterator2,
68 typename Predicate>
69 thrust::pair<OutputIterator1,OutputIterator2>
70 stable_partition_copy(thrust::detail::dispatchable_base<System> &system,
71 InputIterator first,
72 InputIterator last,
73 OutputIterator1 out_true,
74 OutputIterator2 out_false,
75 Predicate pred);
76
77
78 template<typename System, typename ForwardIterator, typename Predicate>
79 ForwardIterator partition_point(thrust::detail::dispatchable_base<System> &system,
80 ForwardIterator first,
81 ForwardIterator last,
82 Predicate pred);
83
84
85 template<typename System, typename InputIterator, typename Predicate>
86 bool is_partitioned(thrust::detail::dispatchable_base<System> &system,
87 InputIterator first,
88 InputIterator last,
89 Predicate pred);
90
91
92
25342f7 @jaredhoberock Initial import of Komrade v0.9.
jaredhoberock authored
93 /*! \addtogroup reordering
94 * \ingroup algorithms
95 *
9c73166 @wnbell more doxygen tweaking
wnbell authored
96 * \addtogroup partitioning
25342f7 @jaredhoberock Initial import of Komrade v0.9.
jaredhoberock authored
97 * \ingroup reordering
98 * \{
99 */
100
101 /*! \p partition reorders the elements <tt>[first, last)</tt> based on the function
102 * object \p pred, such that all of the elements that satisfy \p pred precede the
103 * elements that fail to satisfy it. The postcondition is that, for some iterator
89a106e @wnbell replaced [begin, end) with [first, last)
wnbell authored
104 * \c middle in the range <tt>[first, last)</tt>, <tt>pred(*i)</tt> is \c true for every
25342f7 @jaredhoberock Initial import of Komrade v0.9.
jaredhoberock authored
105 * iterator \c i in the range <tt>[first,middle)</tt> and \c false for every iterator
89a106e @wnbell replaced [begin, end) with [first, last)
wnbell authored
106 * \c i in the range <tt>[middle, last)</tt>. The return value of \p partition is
25342f7 @jaredhoberock Initial import of Komrade v0.9.
jaredhoberock authored
107 * \c middle.
108 *
109 * Note that the relative order of elements in the two reordered sequences is not
110 * necessarily the same as it was in the original sequence. A different algorithm,
111 * \ref stable_partition, does guarantee to preserve the relative order.
112 *
113 * \param first The beginning of the sequence to reorder.
114 * \param last The end of the sequence to reorder.
115 * \param pred A function object which decides to which partition each element of the
89a106e @wnbell replaced [begin, end) with [first, last)
wnbell authored
116 * sequence <tt>[first, last)</tt> belongs.
25342f7 @jaredhoberock Initial import of Komrade v0.9.
jaredhoberock authored
117 * \return An iterator referring to the first element of the second partition, that is,
118 * the sequence of the elements which do not satisfy \p pred.
119 *
120 * \tparam ForwardIterator is a model of <a href="http://www.sgi.com/tech/stl/ForwardIterator.html">Forward Iterator</a>,
121 * and \p ForwardIterator's \c value_type is convertible to \p Predicate's \c argument_type,
122 * and \p ForwardIterator is mutable.
123 * \tparam Predicate is a model of <a href="http://www.sgi.com/tech/stl/Predicate.html">Predicate</a>.
124 *
125 * The following code snippet demonstrates how to use \p partition to reorder a
126 * sequence so that even numbers precede odd numbers.
127 *
128 * \code
4750e2b @wnbell renamed komrade->thrust
wnbell authored
129 * #include <thrust/partition.h>
25342f7 @jaredhoberock Initial import of Komrade v0.9.
jaredhoberock authored
130 * ...
131 * struct is_even
132 * {
133 * __host__ __device__
134 * bool operator()(const int &x)
135 * {
136 * return (x % 2) == 0;
137 * }
138 * };
139 * ...
140 * int A[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
141 * const int N = sizeof(A)/sizeof(int);
4750e2b @wnbell renamed komrade->thrust
wnbell authored
142 * thrust::partition(A, A + N,
25342f7 @jaredhoberock Initial import of Komrade v0.9.
jaredhoberock authored
143 * is_even());
144 * // A is now {2, 4, 6, 8, 10, 1, 3, 5, 7, 9}
145 * \endcode
146 *
147 * \see http://www.sgi.com/tech/stl/partition.html
148 * \see \p stable_partition
149 * \see \p partition_copy
150 */
151 template<typename ForwardIterator,
152 typename Predicate>
153 ForwardIterator partition(ForwardIterator first,
154 ForwardIterator last,
155 Predicate pred);
156
157 /*! \p partition_copy differs from \ref partition only in that the reordered
4bfdb57 @jaredhoberock partition_copy abides by the specification in N3092, taking separate …
jaredhoberock authored
158 * sequence is written to difference output sequences, rather than in place.
25342f7 @jaredhoberock Initial import of Komrade v0.9.
jaredhoberock authored
159 *
4bfdb57 @jaredhoberock partition_copy abides by the specification in N3092, taking separate …
jaredhoberock authored
160 * \p partition_copy copies the elements <tt>[first, last)</tt> based on the
161 * function object \p pred. All of the elements that satisfy \p pred are copied
162 * to the range beginning at \p out_true and all the elements that fail to satisfy it
163 * are copied to the range beginning at \p out_false.
25342f7 @jaredhoberock Initial import of Komrade v0.9.
jaredhoberock authored
164 *
165 * \param first The beginning of the sequence to reorder.
166 * \param last The end of the sequence to reorder.
4bfdb57 @jaredhoberock partition_copy abides by the specification in N3092, taking separate …
jaredhoberock authored
167 * \param out_true The destination of the resulting sequence of elements which satisfy \p pred.
168 * \param out_false The destination of the resulting sequence of elements which fail to satisfy \p pred.
25342f7 @jaredhoberock Initial import of Komrade v0.9.
jaredhoberock authored
169 * \param pred A function object which decides to which partition each element of the
89a106e @wnbell replaced [begin, end) with [first, last)
wnbell authored
170 * sequence <tt>[first, last)</tt> belongs.
4bfdb57 @jaredhoberock partition_copy abides by the specification in N3092, taking separate …
jaredhoberock authored
171 * \return A \p pair p such that <tt>p.first</tt> is the end of the output range beginning
172 * at \p out_true and <tt>p.second</tt> is the end of the output range beginning at
173 * \p out_false.
174 *
175 * \tparam InputIterator is a model of <a href="http://www.sgi.com/tech/stl/InputIterator.html">Input Iterator</a>,
176 * and \p InputIterator's \c value_type is convertible to \p Predicate's \c argument_type and \p InputIterator's \c value_type
177 * is convertible to \p OutputIterator1 and \p OutputIterator2's \c value_types.
178 * \tparam OutputIterator1 is a model of <a href="http://www.sgi.com/tech/stl/OutputIterator.html">Output Iterator</a>.
179 * \tparam OutputIterator2 is a model of <a href="http://www.sgi.com/tech/stl/OutputIterator.html">Output Iterator</a>.
25342f7 @jaredhoberock Initial import of Komrade v0.9.
jaredhoberock authored
180 * \tparam Predicate is a model of <a href="http://www.sgi.com/tech/stl/Predicate.html">Predicate</a>.
181 *
4bfdb57 @jaredhoberock partition_copy abides by the specification in N3092, taking separate …
jaredhoberock authored
182 * The following code snippet demonstrates how to use \p partition_copy to separate a
183 * sequence into two output sequences of even and odd numbers.
25342f7 @jaredhoberock Initial import of Komrade v0.9.
jaredhoberock authored
184 *
185 * \code
4750e2b @wnbell renamed komrade->thrust
wnbell authored
186 * #include <thrust/partition.h>
25342f7 @jaredhoberock Initial import of Komrade v0.9.
jaredhoberock authored
187 * ...
188 * struct is_even
189 * {
190 * __host__ __device__
191 * bool operator()(const int &x)
192 * {
193 * return (x % 2) == 0;
194 * }
195 * };
196 * ...
197 * int A[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
198 * int result[10];
199 * const int N = sizeof(A)/sizeof(int);
4bfdb57 @jaredhoberock partition_copy abides by the specification in N3092, taking separate …
jaredhoberock authored
200 * int *evens = result;
201 * int *odds = result + 5;
202 * thrust::partition_copy(A, A + N, evens, odds, is_even());
25342f7 @jaredhoberock Initial import of Komrade v0.9.
jaredhoberock authored
203 * // A remains {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
204 * // result is now {2, 4, 6, 8, 10, 1, 3, 5, 7, 9}
4bfdb57 @jaredhoberock partition_copy abides by the specification in N3092, taking separate …
jaredhoberock authored
205 * // evens points to {2, 4, 6, 8, 10}
206 * // odds points to {1, 3, 5, 7, 9}
25342f7 @jaredhoberock Initial import of Komrade v0.9.
jaredhoberock authored
207 * \endcode
208 *
209 * \note The relative order of elements in the two reordered sequences is not
210 * necessarily the same as it was in the original sequence. A different algorithm,
211 * \ref stable_partition_copy, does guarantee to preserve the relative order.
212 *
213 * \see http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2008/n2569.pdf
214 * \see \p stable_partition_copy
215 * \see \p partition
216 */
4bfdb57 @jaredhoberock partition_copy abides by the specification in N3092, taking separate …
jaredhoberock authored
217 template<typename InputIterator,
218 typename OutputIterator1,
219 typename OutputIterator2,
25342f7 @jaredhoberock Initial import of Komrade v0.9.
jaredhoberock authored
220 typename Predicate>
4bfdb57 @jaredhoberock partition_copy abides by the specification in N3092, taking separate …
jaredhoberock authored
221 thrust::pair<OutputIterator1,OutputIterator2>
222 partition_copy(InputIterator first,
223 InputIterator last,
224 OutputIterator1 out_true,
225 OutputIterator2 out_false,
226 Predicate pred);
6445457 @wnbell moved partition_copy and stable_partition_copy to thrust::experimenta…
wnbell authored
227
25342f7 @jaredhoberock Initial import of Komrade v0.9.
jaredhoberock authored
228 /*! \p stable_partition is much like \ref partition : it reorders the elements in the
89a106e @wnbell replaced [begin, end) with [first, last)
wnbell authored
229 * range <tt>[first, last)</tt> based on the function object \p pred, such that all of
25342f7 @jaredhoberock Initial import of Komrade v0.9.
jaredhoberock authored
230 * the elements that satisfy \p pred precede all of the elements that fail to satisfy
231 * it. The postcondition is that, for some iterator \p middle in the range
89a106e @wnbell replaced [begin, end) with [first, last)
wnbell authored
232 * <tt>[first, last)</tt>, <tt>pred(*i)</tt> is \c true for every iterator \c i in the
233 * range <tt>[first,middle)</tt> and \c false for every iterator \c i in the range
234 * <tt>[middle, last)</tt>. The return value of \p stable_partition is \c middle.
25342f7 @jaredhoberock Initial import of Komrade v0.9.
jaredhoberock authored
235 *
236 * \p stable_partition differs from \ref partition in that \p stable_partition is
237 * guaranteed to preserve relative order. That is, if \c x and \c y are elements in
89a106e @wnbell replaced [begin, end) with [first, last)
wnbell authored
238 * <tt>[first, last)</tt>, such that <tt>pred(x) == pred(y)</tt>, and if \c x precedes
25342f7 @jaredhoberock Initial import of Komrade v0.9.
jaredhoberock authored
239 * \c y, then it will still be true after \p stable_partition that \c x precedes \c y.
240 *
89a106e @wnbell replaced [begin, end) with [first, last)
wnbell authored
241 * \param first The first element of the sequence to reorder.
242 * \param last One position past the last element of the sequence to reorder.
25342f7 @jaredhoberock Initial import of Komrade v0.9.
jaredhoberock authored
243 * \param pred A function object which decides to which partition each element of the
89a106e @wnbell replaced [begin, end) with [first, last)
wnbell authored
244 * sequence <tt>[first, last)</tt> belongs.
25342f7 @jaredhoberock Initial import of Komrade v0.9.
jaredhoberock authored
245 * \return An iterator referring to the first element of the second partition, that is,
246 * the sequence of the elements which do not satisfy pred.
247 *
248 * \tparam ForwardIterator is a model of <a href="http://www.sgi.com/tech/stl/ForwardIterator.html">Forward Iterator</a>,
249 * and \p ForwardIterator's \c value_type is convertible to \p Predicate's \c argument_type,
250 * and \p ForwardIterator is mutable.
251 * \tparam Predicate is a model of <a href="http://www.sgi.com/tech/stl/Predicate.html">Predicate</a>.
252 *
253 * The following code snippet demonstrates how to use \p stable_partition to reorder a
254 * sequence so that even numbers precede odd numbers.
255 *
256 * \code
4750e2b @wnbell renamed komrade->thrust
wnbell authored
257 * #include <thrust/partition.h>
25342f7 @jaredhoberock Initial import of Komrade v0.9.
jaredhoberock authored
258 * ...
259 * struct is_even
260 * {
261 * __host__ __device__
262 * bool operator()(const int &x)
263 * {
264 * return (x % 2) == 0;
265 * }
266 * };
267 * ...
268 * int A[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
269 * const int N = sizeof(A)/sizeof(int);
4750e2b @wnbell renamed komrade->thrust
wnbell authored
270 * thrust::stable_partition(A, A + N,
25342f7 @jaredhoberock Initial import of Komrade v0.9.
jaredhoberock authored
271 * is_even());
272 * // A is now {2, 4, 6, 8, 10, 1, 3, 5, 7, 9}
273 * \endcode
274 *
275 * \see http://www.sgi.com/tech/stl/stable_partition.html
276 * \see \p partition
277 * \see \p stable_partition_copy
278 */
279 template<typename ForwardIterator,
280 typename Predicate>
89a106e @wnbell replaced [begin, end) with [first, last)
wnbell authored
281 ForwardIterator stable_partition(ForwardIterator first,
282 ForwardIterator last,
25342f7 @jaredhoberock Initial import of Komrade v0.9.
jaredhoberock authored
283 Predicate pred);
284
6445457 @wnbell moved partition_copy and stable_partition_copy to thrust::experimenta…
wnbell authored
285
471f09c @wnbell fixed doxygen errors in partition.h and remove.h
wnbell authored
286 /*! \p stable_partition_copy differs from \ref stable_partition only in that the reordered
287 * sequence is written to difference output sequences, rather than in place.
288 *
289 * \p stable_partition_copy copies the elements <tt>[first, last)</tt> based on the
290 * function object \p pred. All of the elements that satisfy \p pred are copied
291 * to the range beginning at \p out_true and all the elements that fail to satisfy it
292 * are copied to the range beginning at \p out_false.
25342f7 @jaredhoberock Initial import of Komrade v0.9.
jaredhoberock authored
293 *
294 * \p stable_partition_copy differs from \ref partition_copy in that
295 * \p stable_partition_copy is guaranteed to preserve relative order. That is, if
89a106e @wnbell replaced [begin, end) with [first, last)
wnbell authored
296 * \c x and \c y are elements in <tt>[first, last)</tt>, such that
25342f7 @jaredhoberock Initial import of Komrade v0.9.
jaredhoberock authored
297 * <tt>pred(x) == pred(y)</tt>, and if \c x precedes \c y, then it will still be true
471f09c @wnbell fixed doxygen errors in partition.h and remove.h
wnbell authored
298 * after \p stable_partition_copy that \c x precedes \c y in the output.
25342f7 @jaredhoberock Initial import of Komrade v0.9.
jaredhoberock authored
299 *
89a106e @wnbell replaced [begin, end) with [first, last)
wnbell authored
300 * \param first The first element of the sequence to reorder.
301 * \param last One position past the last element of the sequence to reorder.
471f09c @wnbell fixed doxygen errors in partition.h and remove.h
wnbell authored
302 * \param out_true The destination of the resulting sequence of elements which satisfy \p pred.
303 * \param out_false The destination of the resulting sequence of elements which fail to satisfy \p pred.
25342f7 @jaredhoberock Initial import of Komrade v0.9.
jaredhoberock authored
304 * \param pred A function object which decides to which partition each element of the
471f09c @wnbell fixed doxygen errors in partition.h and remove.h
wnbell authored
305 * sequence <tt>[first, last)</tt> belongs.
306 * \return A \p pair p such that <tt>p.first</tt> is the end of the output range beginning
307 * at \p out_true and <tt>p.second</tt> is the end of the output range beginning at
308 * \p out_false.
25342f7 @jaredhoberock Initial import of Komrade v0.9.
jaredhoberock authored
309 *
471f09c @wnbell fixed doxygen errors in partition.h and remove.h
wnbell authored
310 * \tparam InputIterator is a model of <a href="http://www.sgi.com/tech/stl/InputIterator.html">Input Iterator</a>,
311 * and \p InputIterator's \c value_type is convertible to \p Predicate's \c argument_type and \p InputIterator's \c value_type
312 * is convertible to \p OutputIterator1 and \p OutputIterator2's \c value_types.
313 * \tparam OutputIterator1 is a model of <a href="http://www.sgi.com/tech/stl/OutputIterator.html">Output Iterator</a>.
314 * \tparam OutputIterator2 is a model of <a href="http://www.sgi.com/tech/stl/OutputIterator.html">Output Iterator</a>.
25342f7 @jaredhoberock Initial import of Komrade v0.9.
jaredhoberock authored
315 * \tparam Predicate is a model of <a href="http://www.sgi.com/tech/stl/Predicate.html">Predicate</a>.
316 *
317 * The following code snippet demonstrates how to use \p stable_partition_copy to
318 * reorder a sequence so that even numbers precede odd numbers.
319 *
320 * \code
4750e2b @wnbell renamed komrade->thrust
wnbell authored
321 * #include <thrust/partition.h>
25342f7 @jaredhoberock Initial import of Komrade v0.9.
jaredhoberock authored
322 * ...
323 * struct is_even
324 * {
325 * __host__ __device__
326 * bool operator()(const int &x)
327 * {
328 * return (x % 2) == 0;
329 * }
330 * };
331 * ...
332 * int A[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
333 * int result[10];
334 * const int N = sizeof(A)/sizeof(int);
471f09c @wnbell fixed doxygen errors in partition.h and remove.h
wnbell authored
335 * int *evens = result;
336 * int *odds = result + 5;
337 * thrust::stable_partition_copy(A, A + N, evens, odds, is_even());
338 * // A remains {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
25342f7 @jaredhoberock Initial import of Komrade v0.9.
jaredhoberock authored
339 * // result is now {2, 4, 6, 8, 10, 1, 3, 5, 7, 9}
471f09c @wnbell fixed doxygen errors in partition.h and remove.h
wnbell authored
340 * // evens points to {2, 4, 6, 8, 10}
341 * // odds points to {1, 3, 5, 7, 9}
25342f7 @jaredhoberock Initial import of Komrade v0.9.
jaredhoberock authored
342 * \endcode
343 *
471f09c @wnbell fixed doxygen errors in partition.h and remove.h
wnbell authored
344 * \see http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2008/n2569.pdf
25342f7 @jaredhoberock Initial import of Komrade v0.9.
jaredhoberock authored
345 * \see \p partition_copy
346 * \see \p stable_partition
347 */
a7acc7b @jaredhoberock Make partition_copy's interface match that specified by the standard.
jaredhoberock authored
348 template<typename InputIterator,
349 typename OutputIterator1,
350 typename OutputIterator2,
25342f7 @jaredhoberock Initial import of Komrade v0.9.
jaredhoberock authored
351 typename Predicate>
a7acc7b @jaredhoberock Make partition_copy's interface match that specified by the standard.
jaredhoberock authored
352 thrust::pair<OutputIterator1,OutputIterator2>
353 stable_partition_copy(InputIterator first,
354 InputIterator last,
355 OutputIterator1 out_true,
356 OutputIterator2 out_false,
357 Predicate pred);
6445457 @wnbell moved partition_copy and stable_partition_copy to thrust::experimenta…
wnbell authored
358
25342f7 @jaredhoberock Initial import of Komrade v0.9.
jaredhoberock authored
359 /*! \} // end stream_compaction
360 */
361
362 /*! \} // end reordering
363 */
364
6a512b1 @jaredhoberock Add is_partitioned & partition_point and unit tests for each
jaredhoberock authored
365 /*! \addtogroup searching
366 * \{
367 */
368
369 /*! \p partition_point returns an iterator pointing to the end of the true
370 * partition of a partitioned range. \p partition_point requires the input range
371 * <tt>[first,last)</tt> to be a partition; that is, all elements which satisfy
372 * <tt>pred</tt> shall appear before those that do not.
373 * \param first The beginning of the range to consider.
374 * \param last The end of the range to consider.
375 * \param pred A function object which decides to which partition each element of the
376 * range <tt>[first, last)</tt> belongs.
377 * \return An iterator \c mid such that <tt>all_of(first, mid, pred)</tt>
378 * and <tt>none_of(mid, last, pred)</tt> are both true.
379 *
380 * \tparam ForwardIterator is a model of <a href="http://www.sgi.com/tech/stl/ForwardIterator.html">Forward Iterator</a>,
381 * and \p ForwardIterator's \c value_type is convertible to \p Predicate's \c argument_type.
382 * \tparam Predicate is a model of <a href="http://www.sgi.com/tech/stl/Predicate.html">Predicate</a>.
383 *
384 * \note Though similar, \p partition_point is not redundant with \p find_if_not.
385 * \p partition_point's precondition provides an opportunity for a
386 * faster implemention.
387 *
ce4d3d1 @wnbell added Doxygen \code examples for algorithms
wnbell authored
388 * \code
389 * #include <thrust/partition.h>
390 *
391 * struct is_even
392 * {
393 * __host__ __device__
394 * bool operator()(const int &x)
395 * {
396 * return (x % 2) == 0;
397 * }
398 * };
399 *
400 * ...
401 *
402 * int A[] = {2, 4, 6, 8, 10, 1, 3, 5, 7, 9};
403 * int * B = thrust::partition_point(A, A + 10, is_even());
404 * // B - A is 5
405 * // [A, B) contains only even values
406 * \endcode
407 *
6a512b1 @jaredhoberock Add is_partitioned & partition_point and unit tests for each
jaredhoberock authored
408 * \see \p partition
409 * \see \p find_if_not
410 */
411 template<typename ForwardIterator, typename Predicate>
412 ForwardIterator partition_point(ForwardIterator first,
413 ForwardIterator last,
414 Predicate pred);
415 /*! \} // searching
416 */
417
418 /*! \addtogroup reductions
419 * \{
420 * \addtogroup predicates
421 * \{
422 */
423
424 /*! \p is_partitioned returns \c true if the given range
425 * is partitioned with respect to a predicate, and \c false otherwise.
426 *
427 * Specifically, \p is_partitioned returns \c true if <tt>[first, last)</tt>
428 * is empty of if <tt>[first, last)</tt> is partitioned by \p pred, i.e. if
429 * all elements that satisfy \p pred appear before those that do not.
430 *
431 * \param first The beginning of the range to consider.
432 * \param last The end of the range to consider.
433 * \param pred A function object which decides to which partition each element of the
434 * range <tt>[first, last)</tt> belongs.
435 * \return \c true if the range <tt>[first, last)</tt> is partitioned with respect
436 * to \p pred, or if <tt>[first, last)</tt> is empty. \c false, otherwise.
437 *
438 * \tparam InputIterator is a model of <a href="http://www.sgi.com/tech/stl/ForwardIterator.html">Input Iterator</a>,
439 * and \p InputIterator's \c value_type is convertible to \p Predicate's \c argument_type.
440 * \tparam Predicate is a model of <a href="http://www.sgi.com/tech/stl/Predicate.html">Predicate</a>.
441 *
ce4d3d1 @wnbell added Doxygen \code examples for algorithms
wnbell authored
442 * \code
443 * #include <thrust/partition.h>
444 *
445 * struct is_even
446 * {
447 * __host__ __device__
448 * bool operator()(const int &x)
449 * {
450 * return (x % 2) == 0;
451 * }
452 * };
453 *
454 * ...
455 *
456 * int A[] = {2, 4, 6, 8, 10, 1, 3, 5, 7, 9};
457 * int B[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
458 *
459 * thrust::is_partitioned(A, A + 10); // returns true
460 * thrust::is_partitioned(B, B + 10); // returns false
461 * \endcode
462 *
6a512b1 @jaredhoberock Add is_partitioned & partition_point and unit tests for each
jaredhoberock authored
463 * \see \p partition
464 */
465 template<typename InputIterator, typename Predicate>
466 bool is_partitioned(InputIterator first,
467 InputIterator last,
468 Predicate pred);
469
470 /*! \} // end predicates
471 * \} // end reductions
472 */
473
4750e2b @wnbell renamed komrade->thrust
wnbell authored
474 } // end thrust
25342f7 @jaredhoberock Initial import of Komrade v0.9.
jaredhoberock authored
475
4750e2b @wnbell renamed komrade->thrust
wnbell authored
476 #include <thrust/detail/partition.inl>
25342f7 @jaredhoberock Initial import of Komrade v0.9.
jaredhoberock authored
477
Something went wrong with that request. Please try again.