1 //---------------------------------------------------------------------------//
2 // Copyright (c) 2013-2014 Kyle Lutz <kyle.r.lutz@gmail.com>
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
8 // See http://boostorg.github.com/compute for more information.
9 //---------------------------------------------------------------------------//
11 #ifndef BOOST_COMPUTE_ALGORITHM_ADJACENT_FIND_HPP
12 #define BOOST_COMPUTE_ALGORITHM_ADJACENT_FIND_HPP
16 #include <boost/compute/command_queue.hpp>
17 #include <boost/compute/lambda.hpp>
18 #include <boost/compute/system.hpp>
19 #include <boost/compute/container/detail/scalar.hpp>
20 #include <boost/compute/detail/iterator_range_size.hpp>
21 #include <boost/compute/detail/meta_kernel.hpp>
22 #include <boost/compute/functional/operator.hpp>
23 #include <boost/compute/type_traits/vector_size.hpp>
29 template<class InputIterator, class Compare>
31 serial_adjacent_find(InputIterator first,
40 const context &context = queue.get_context();
42 detail::scalar<uint_> output(context);
44 detail::meta_kernel k("serial_adjacent_find");
46 size_t size_arg = k.add_arg<const uint_>("size");
47 size_t output_arg = k.add_arg<uint_ *>(memory_object::global_memory, "output");
49 k << k.decl<uint_>("result") << " = size;\n"
50 << "for(uint i = 0; i < size - 1; i++){\n"
51 << " if(" << compare(first[k.expr<uint_>("i")],
52 first[k.expr<uint_>("i+1")]) << "){\n"
57 << "*output = result;\n";
59 k.set_arg<const uint_>(
60 size_arg, static_cast<uint_>(detail::iterator_range_size(first, last))
62 k.set_arg(output_arg, output.get_buffer());
64 k.exec_1d(queue, 0, 1, 1);
66 return first + output.read(queue);
69 template<class InputIterator, class Compare>
71 adjacent_find_with_atomics(InputIterator first,
80 const context &context = queue.get_context();
81 size_t count = detail::iterator_range_size(first, last);
83 // initialize output to the last index
84 detail::scalar<uint_> output(context);
85 output.write(static_cast<uint_>(count), queue);
87 detail::meta_kernel k("adjacent_find_with_atomics");
89 size_t output_arg = k.add_arg<uint_ *>(memory_object::global_memory, "output");
91 k << "const uint i = get_global_id(0);\n"
92 << "if(" << compare(first[k.expr<uint_>("i")],
93 first[k.expr<uint_>("i+1")]) << "){\n"
94 << " atomic_min(output, i);\n"
97 k.set_arg(output_arg, output.get_buffer());
99 k.exec_1d(queue, 0, count - 1, 1);
101 return first + output.read(queue);
104 } // end detail namespace
106 /// Searches the range [\p first, \p last) for two identical adjacent
107 /// elements and returns an iterator pointing to the first.
109 /// \param first first element in the range to search
110 /// \param last last element in the range to search
111 /// \param compare binary comparison function
112 /// \param queue command queue to perform the operation
114 /// \return \c InputIteratorm to the first element which compares equal
115 /// to the following element. If none are equal, returns \c last.
117 /// \see find(), adjacent_difference()
118 template<class InputIterator, class Compare>
120 adjacent_find(InputIterator first,
123 command_queue &queue = system::default_queue())
125 size_t count = detail::iterator_range_size(first, last);
127 return detail::serial_adjacent_find(first, last, compare, queue);
130 return detail::adjacent_find_with_atomics(first, last, compare, queue);
135 template<class InputIterator>
137 adjacent_find(InputIterator first,
139 command_queue &queue = system::default_queue())
141 typedef typename std::iterator_traits<InputIterator>::value_type value_type;
143 using ::boost::compute::lambda::_1;
144 using ::boost::compute::lambda::_2;
145 using ::boost::compute::lambda::all;
147 if(vector_size<value_type>::value == 1){
148 return ::boost::compute::adjacent_find(
149 first, last, _1 == _2, queue
153 return ::boost::compute::adjacent_find(
154 first, last, all(_1 == _2), queue
159 } // end compute namespace
160 } // end boost namespace
162 #endif // BOOST_COMPUTE_ALGORITHM_ADJACENT_FIND_HPP