ceph/src/boost/libs/compute/include/boost/compute/algorithm/unique_copy.hpp

   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_UNIQUE_COPY_HPP
  12 #define BOOST_COMPUTE_ALGORITHM_UNIQUE_COPY_HPP
  13
  14 #include <boost/compute/command_queue.hpp>
  15 #include <boost/compute/lambda.hpp>
  16 #include <boost/compute/system.hpp>
  17 #include <boost/compute/algorithm/copy_if.hpp>
  18 #include <boost/compute/algorithm/transform.hpp>
  19 #include <boost/compute/algorithm/gather.hpp>
  20 #include <boost/compute/container/vector.hpp>
  21 #include <boost/compute/detail/iterator_range_size.hpp>
  22 #include <boost/compute/detail/meta_kernel.hpp>
  23 #include <boost/compute/functional/operator.hpp>
  24
  25 namespace boost {
  26 namespace compute {
  27 namespace detail {
  28
  29 template<class InputIterator, class OutputIterator, class BinaryPredicate>
  30 inline OutputIterator serial_unique_copy(InputIterator first,
  31                                          InputIterator last,
  32                                          OutputIterator result,
  33                                          BinaryPredicate op,
  34                                          command_queue &queue)
  35 {
  36     if(first == last){
  37         return result;
  38     }
  39
  40     typedef typename std::iterator_traits<InputIterator>::value_type value_type;
  41
  42     const context &context = queue.get_context();
  43
  44     size_t count = detail::iterator_range_size(first, last);
  45
  46     detail::meta_kernel k("serial_unique_copy");
  47
  48     vector<uint_> unique_count_vector(1, context);
  49
  50     size_t size_arg = k.add_arg<const uint_>("size");
  51     size_t unique_count_arg = k.add_arg<uint_ *>(memory_object::global_memory, "unique_count");
  52
  53     k << k.decl<uint_>("index") << " = 0;\n"
  54       << k.decl<value_type>("current") << " = " << first[k.var<uint_>("0")] << ";\n"
  55       << result[k.var<uint_>("0")] << " = current;\n"
  56       << "for(uint i = 1; i < size; i++){\n"
  57       << "    " << k.decl<value_type>("next") << " = " << first[k.var<uint_>("i")] << ";\n"
  58       << "    if(!" << op(k.var<value_type>("current"), k.var<value_type>("next")) << "){\n"
  59       << "        " << result[k.var<uint_>("++index")] << " = next;\n"
  60       << "        " << "current = next;\n"
  61       << "    }\n"
  62       << "}\n"
  63       << "*unique_count = index + 1;\n";
  64
  65     k.set_arg<const uint_>(size_arg, count);
  66     k.set_arg(unique_count_arg, unique_count_vector.get_buffer());
  67
  68     k.exec_1d(queue, 0, 1, 1);
  69
  70     uint_ unique_count;
  71     copy_n(unique_count_vector.begin(), 1, &unique_count, queue);
  72
  73     return result + unique_count;
  74 }
  75
  76 template<class InputIterator, class OutputIterator, class BinaryPredicate>
  77 inline OutputIterator unique_copy(InputIterator first,
  78                                   InputIterator last,
  79                                   OutputIterator result,
  80                                   BinaryPredicate op,
  81                                   command_queue &queue)
  82 {
  83     if(first == last){
  84         return result;
  85     }
  86
  87     const context &context = queue.get_context();
  88     size_t count = detail::iterator_range_size(first, last);
  89
  90     // flags marking unique elements
  91     vector<uint_> flags(count, context);
  92
  93     // find each unique element and mark it with a one
  94     transform(
  95         first, last - 1, first + 1, flags.begin() + 1, not2(op), queue
  96     );
  97
  98     // first element is always unique
  99     fill_n(flags.begin(), 1, 1, queue);
 100
 101     // storage for desination indices
 102     vector<uint_> indices(count, context);
 103
 104     // copy indices for each unique element
 105     vector<uint_>::iterator last_index = detail::copy_index_if(
 106         flags.begin(), flags.end(), indices.begin(), lambda::_1 == 1, queue
 107     );
 108
 109     // copy unique values from input to output using the computed indices
 110     gather(indices.begin(), last_index, first, result, queue);
 111
 112     // return an iterator to the end of the unique output range
 113     return result + std::distance(indices.begin(), last_index);
 114 }
 115
 116 } // end detail namespace
 117
 118 /// Makes a copy of the range [first, last) and removes all consecutive
 119 /// duplicate elements (determined by \p op) from the copy. If \p op is not
 120 /// provided, the equality operator is used.
 121 ///
 122 /// \param first first element in the input range
 123 /// \param last last element in the input range
 124 /// \param result first element in the result range
 125 /// \param op binary operator used to check for uniqueness
 126 /// \param queue command queue to perform the operation
 127 ///
 128 /// \return \c OutputIterator to the end of the result range
 129 ///
 130 /// \see unique()
 131 template<class InputIterator, class OutputIterator, class BinaryPredicate>
 132 inline OutputIterator unique_copy(InputIterator first,
 133                                   InputIterator last,
 134                                   OutputIterator result,
 135                                   BinaryPredicate op,
 136                                   command_queue &queue = system::default_queue())
 137 {
 138     size_t count = detail::iterator_range_size(first, last);
 139     if(count < 32){
 140         return detail::serial_unique_copy(first, last, result, op, queue);
 141     }
 142     else {
 143         return detail::unique_copy(first, last, result, op, queue);
 144     }
 145 }
 146
 147 /// \overload
 148 template<class InputIterator, class OutputIterator>
 149 inline OutputIterator unique_copy(InputIterator first,
 150                                   InputIterator last,
 151                                   OutputIterator result,
 152                                   command_queue &queue = system::default_queue())
 153 {
 154     typedef typename std::iterator_traits<InputIterator>::value_type value_type;
 155
 156     return ::boost::compute::unique_copy(
 157         first, last, result, ::boost::compute::equal_to<value_type>(), queue
 158     );
 159 }
 160
 161 } // end compute namespace
 162 } // end boost namespace
 163
 164 #endif // BOOST_COMPUTE_ALGORITHM_UNIQUE_COPY_HPP