1 //---------------------------------------------------------------------------//
2 // Copyright (c) 2014 Roshan <thisisroshansmail@gmail.com>
3 //
4 // Distributed under the Boost Software License, Version 1.0
5 // See accompanying file LICENSE_1_0.txt or copy at
6 // http://www.boost.org/LICENSE_1_0.txt
7 //
8 // See http://boostorg.github.com/compute for more information.
9 //---------------------------------------------------------------------------//
10
11 #ifndef BOOST_COMPUTE_ALGORITHM_STABLE_PARTITION_HPP
12 #define BOOST_COMPUTE_ALGORITHM_STABLE_PARTITION_HPP
13
14 #include <boost/static_assert.hpp>
15
16 #include <boost/compute/system.hpp>
17 #include <boost/compute/context.hpp>
18 #include <boost/compute/functional.hpp>
19 #include <boost/compute/command_queue.hpp>
20 #include <boost/compute/algorithm/copy_if.hpp>
21 #include <boost/compute/container/vector.hpp>
22 #include <boost/compute/type_traits/is_device_iterator.hpp>
23
24 namespace boost {
25 namespace compute {
26
27 ///
28 /// \brief Partitioning algorithm
29 ///
30 /// Partitions the elements in the range [\p first, \p last) according to
31 /// \p predicate. The order of the elements is preserved.
32 /// \return Iterator pointing to end of true values
33 ///
34 /// \param first Iterator pointing to start of range
35 /// \param last Iterator pointing to end of range
36 /// \param predicate Unary predicate to be applied on each element
37 /// \param queue Queue on which to execute
38 ///
39 /// Space complexity: \Omega(3n)
40 ///
41 /// \see is_partitioned() and partition()
42 ///
43 template<class Iterator, class UnaryPredicate>
stable_partition(Iterator first,Iterator last,UnaryPredicate predicate,command_queue & queue=system::default_queue ())44 inline Iterator stable_partition(Iterator first,
45 Iterator last,
46 UnaryPredicate predicate,
47 command_queue &queue = system::default_queue())
48 {
49 BOOST_STATIC_ASSERT(is_device_iterator<Iterator>::value);
50 typedef typename std::iterator_traits<Iterator>::value_type value_type;
51
52 // make temporary copy of the input
53 ::boost::compute::vector<value_type> tmp(first, last, queue);
54
55 // copy true values
56 Iterator last_true =
57 ::boost::compute::copy_if(tmp.begin(),
58 tmp.end(),
59 first,
60 predicate,
61 queue);
62
63 // copy false values
64 Iterator last_false =
65 ::boost::compute::copy_if(tmp.begin(),
66 tmp.end(),
67 last_true,
68 not1(predicate),
69 queue);
70
71 // return iterator pointing to the last true value
72 return last_true;
73 }
74
75 } // end compute namespace
76 } // end boost namespace
77
78 #endif // BOOST_COMPUTE_ALGORITHM_STABLE_PARTITION_HPP
79