compute/algorithm/unique_copy.hpp

0001 //---------------------------------------------------------------------------//
0002 // Copyright (c) 2014 Roshan <thisisroshansmail@gmail.com>
0003 //
0004 // Distributed under the Boost Software License, Version 1.0
0005 // See accompanying file LICENSE_1_0.txt or copy at
0006 // http://www.boost.org/LICENSE_1_0.txt
0007 //
0008 // See http://boostorg.github.com/compute for more information.
0009 //---------------------------------------------------------------------------//
0010
0011 #ifndef BOOST_COMPUTE_ALGORITHM_UNIQUE_COPY_HPP
0012 #define BOOST_COMPUTE_ALGORITHM_UNIQUE_COPY_HPP
0013
0014 #include <boost/static_assert.hpp>
0015
0016 #include <boost/compute/command_queue.hpp>
0017 #include <boost/compute/lambda.hpp>
0018 #include <boost/compute/system.hpp>
0019 #include <boost/compute/algorithm/copy_if.hpp>
0020 #include <boost/compute/algorithm/transform.hpp>
0021 #include <boost/compute/algorithm/gather.hpp>
0022 #include <boost/compute/container/vector.hpp>
0023 #include <boost/compute/detail/iterator_range_size.hpp>
0024 #include <boost/compute/detail/meta_kernel.hpp>
0025 #include <boost/compute/functional/operator.hpp>
0026 #include <boost/compute/type_traits/is_device_iterator.hpp>
0027
0028 namespace boost {
0029 namespace compute {
0030 namespace detail {
0031
0032 template<class InputIterator, class OutputIterator, class BinaryPredicate>
0033 inline OutputIterator serial_unique_copy(InputIterator first,
0034                                          InputIterator last,
0035                                          OutputIterator result,
0036                                          BinaryPredicate op,
0037                                          command_queue &queue)
0038 {
0039     if(first == last){
0040         return result;
0041     }
0042
0043     typedef typename std::iterator_traits<InputIterator>::value_type value_type;
0044
0045     const context &context = queue.get_context();
0046
0047     size_t count = detail::iterator_range_size(first, last);
0048
0049     detail::meta_kernel k("serial_unique_copy");
0050
0051     vector<uint_> unique_count_vector(1, context);
0052
0053     size_t size_arg = k.add_arg<const uint_>("size");
0054     size_t unique_count_arg = k.add_arg<uint_ *>(memory_object::global_memory, "unique_count");
0055
0056     k << k.decl<uint_>("index") << " = 0;\n"
0057       << k.decl<value_type>("current") << " = " << first[k.var<uint_>("0")] << ";\n"
0058       << result[k.var<uint_>("0")] << " = current;\n"
0059       << "for(uint i = 1; i < size; i++){\n"
0060       << "    " << k.decl<value_type>("next") << " = " << first[k.var<uint_>("i")] << ";\n"
0061       << "    if(!" << op(k.var<value_type>("current"), k.var<value_type>("next")) << "){\n"
0062       << "        " << result[k.var<uint_>("++index")] << " = next;\n"
0063       << "        " << "current = next;\n"
0064       << "    }\n"
0065       << "}\n"
0066       << "*unique_count = index + 1;\n";
0067
0068     k.set_arg<const uint_>(size_arg, count);
0069     k.set_arg(unique_count_arg, unique_count_vector.get_buffer());
0070
0071     k.exec_1d(queue, 0, 1, 1);
0072
0073     uint_ unique_count;
0074     copy_n(unique_count_vector.begin(), 1, &unique_count, queue);
0075
0076     return result + unique_count;
0077 }
0078
0079 template<class InputIterator, class OutputIterator, class BinaryPredicate>
0080 inline OutputIterator unique_copy(InputIterator first,
0081                                   InputIterator last,
0082                                   OutputIterator result,
0083                                   BinaryPredicate op,
0084                                   command_queue &queue)
0085 {
0086     if(first == last){
0087         return result;
0088     }
0089
0090     const context &context = queue.get_context();
0091     size_t count = detail::iterator_range_size(first, last);
0092
0093     // flags marking unique elements
0094     vector<uint_> flags(count, context);
0095
0096     // find each unique element and mark it with a one
0097     transform(
0098         first, last - 1, first + 1, flags.begin() + 1, not2(op), queue
0099     );
0100
0101     // first element is always unique
0102     fill_n(flags.begin(), 1, 1, queue);
0103
0104     // storage for desination indices
0105     vector<uint_> indices(count, context);
0106
0107     // copy indices for each unique element
0108     vector<uint_>::iterator last_index = detail::copy_index_if(
0109         flags.begin(), flags.end(), indices.begin(), lambda::_1 == 1, queue
0110     );
0111
0112     // copy unique values from input to output using the computed indices
0113     gather(indices.begin(), last_index, first, result, queue);
0114
0115     // return an iterator to the end of the unique output range
0116     return result + std::distance(indices.begin(), last_index);
0117 }
0118
0119 } // end detail namespace
0120
0121 /// Makes a copy of the range [first, last) and removes all consecutive
0122 /// duplicate elements (determined by \p op) from the copy. If \p op is not
0123 /// provided, the equality operator is used.
0124 ///
0125 /// \param first first element in the input range
0126 /// \param last last element in the input range
0127 /// \param result first element in the result range
0128 /// \param op binary operator used to check for uniqueness
0129 /// \param queue command queue to perform the operation
0130 ///
0131 /// \return \c OutputIterator to the end of the result range
0132 ///
0133 /// Space complexity: \Omega(4n)
0134 ///
0135 /// \see unique()
0136 template<class InputIterator, class OutputIterator, class BinaryPredicate>
0137 inline OutputIterator unique_copy(InputIterator first,
0138                                   InputIterator last,
0139                                   OutputIterator result,
0140                                   BinaryPredicate op,
0141                                   command_queue &queue = system::default_queue())
0142 {
0143     BOOST_STATIC_ASSERT(is_device_iterator<InputIterator>::value);
0144     BOOST_STATIC_ASSERT(is_device_iterator<OutputIterator>::value);
0145
0146     size_t count = detail::iterator_range_size(first, last);
0147     if(count < 32){
0148         return detail::serial_unique_copy(first, last, result, op, queue);
0149     }
0150     else {
0151         return detail::unique_copy(first, last, result, op, queue);
0152     }
0153 }
0154
0155 /// \overload
0156 template<class InputIterator, class OutputIterator>
0157 inline OutputIterator unique_copy(InputIterator first,
0158                                   InputIterator last,
0159                                   OutputIterator result,
0160                                   command_queue &queue = system::default_queue())
0161 {
0162     BOOST_STATIC_ASSERT(is_device_iterator<InputIterator>::value);
0163     BOOST_STATIC_ASSERT(is_device_iterator<OutputIterator>::value);
0164
0165     typedef typename std::iterator_traits<InputIterator>::value_type value_type;
0166
0167     return ::boost::compute::unique_copy(
0168         first, last, result, ::boost::compute::equal_to<value_type>(), queue
0169     );
0170 }
0171
0172 } // end compute namespace
0173 } // end boost namespace
0174
0175 #endif // BOOST_COMPUTE_ALGORITHM_UNIQUE_COPY_HPP