compute/algorithm/search_n.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_DETAIL_SEARCH_N_HPP
0012 #define BOOST_COMPUTE_ALGORITHM_DETAIL_SEARCH_N_HPP
0013
0014 #include <iterator>
0015
0016 #include <boost/static_assert.hpp>
0017
0018 #include <boost/compute/algorithm/find.hpp>
0019 #include <boost/compute/container/vector.hpp>
0020 #include <boost/compute/detail/iterator_range_size.hpp>
0021 #include <boost/compute/detail/meta_kernel.hpp>
0022 #include <boost/compute/system.hpp>
0023 #include <boost/compute/type_traits/is_device_iterator.hpp>
0024
0025 namespace boost {
0026 namespace compute {
0027 namespace detail {
0028
0029 ///
0030 /// \brief Search kernel class
0031 ///
0032 /// Subclass of meta_kernel which is capable of performing search_n
0033 ///
0034 template<class TextIterator, class OutputIterator>
0035 class search_n_kernel : public meta_kernel
0036 {
0037 public:
0038     typedef typename std::iterator_traits<TextIterator>::value_type value_type;
0039
0040     search_n_kernel() : meta_kernel("search_n")
0041     {}
0042
0043     void set_range(TextIterator t_first,
0044                    TextIterator t_last,
0045                    value_type value,
0046                    size_t n,
0047                    OutputIterator result)
0048     {
0049         m_n = n;
0050         m_n_arg = add_arg<uint_>("n");
0051
0052         m_value = value;
0053         m_value_arg = add_arg<value_type>("value");
0054
0055         m_count = iterator_range_size(t_first, t_last);
0056         m_count = m_count + 1 - m_n;
0057
0058         *this <<
0059             "uint i = get_global_id(0);\n" <<
0060             "uint i1 = i;\n" <<
0061             "uint j;\n" <<
0062             "for(j = 0; j<n; j++,i++)\n" <<
0063             "{\n" <<
0064             "   if(value != " << t_first[expr<uint_>("i")] << ")\n" <<
0065             "       j = n + 1;\n" <<
0066             "}\n" <<
0067             "if(j == n)\n" <<
0068             result[expr<uint_>("i1")] << " = 1;\n" <<
0069             "else\n" <<
0070             result[expr<uint_>("i1")] << " = 0;\n";
0071     }
0072
0073     event exec(command_queue &queue)
0074     {
0075         if(m_count == 0) {
0076             return event();
0077         }
0078
0079         set_arg(m_n_arg, uint_(m_n));
0080         set_arg(m_value_arg, m_value);
0081
0082         return exec_1d(queue, 0, m_count);
0083     }
0084
0085 private:
0086     size_t m_n;
0087     size_t m_n_arg;
0088     size_t m_count;
0089     value_type m_value;
0090     size_t m_value_arg;
0091 };
0092
0093 } //end detail namespace
0094
0095 ///
0096 /// \brief Substring matching algorithm
0097 ///
0098 /// Searches for the first occurrence of n consecutive occurrences of
0099 /// value in text [t_first, t_last).
0100 /// \return Iterator pointing to beginning of first occurrence
0101 ///
0102 /// \param t_first Iterator pointing to start of text
0103 /// \param t_last Iterator pointing to end of text
0104 /// \param n Number of times value repeats
0105 /// \param value Value which repeats
0106 /// \param queue Queue on which to execute
0107 ///
0108 /// Space complexity: \Omega(distance(\p t_first, \p t_last))
0109 template<class TextIterator, class ValueType>
0110 inline TextIterator search_n(TextIterator t_first,
0111                              TextIterator t_last,
0112                              size_t n,
0113                              ValueType value,
0114                              command_queue &queue = system::default_queue())
0115 {
0116     BOOST_STATIC_ASSERT(is_device_iterator<TextIterator>::value);
0117
0118     // there is no need to check if pattern starts at last n - 1 indices
0119     vector<uint_> matching_indices(
0120         detail::iterator_range_size(t_first, t_last) + 1 - n,
0121         queue.get_context()
0122     );
0123
0124     // search_n_kernel puts value 1 at every index in vector where pattern
0125     // of n values starts at
0126     detail::search_n_kernel<TextIterator,
0127                             vector<uint_>::iterator> kernel;
0128
0129     kernel.set_range(t_first, t_last, value, n, matching_indices.begin());
0130     kernel.exec(queue);
0131
0132     vector<uint_>::iterator index = ::boost::compute::find(
0133         matching_indices.begin(), matching_indices.end(), uint_(1), queue
0134     );
0135
0136     // pattern was not found
0137     if(index == matching_indices.end())
0138         return t_last;
0139
0140     return t_first + detail::iterator_range_size(matching_indices.begin(), index);
0141 }
0142
0143 } //end compute namespace
0144 } //end boost namespace
0145
0146 #endif // BOOST_COMPUTE_ALGORITHM_DETAIL_SEARCH_N_HPP