]>
Commit | Line | Data |
---|---|---|
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_DETAIL_SEARCH_N_HPP | |
12 | #define BOOST_COMPUTE_ALGORITHM_DETAIL_SEARCH_N_HPP | |
13 | ||
14 | #include <iterator> | |
15 | ||
16 | #include <boost/compute/algorithm/find.hpp> | |
17 | #include <boost/compute/container/vector.hpp> | |
18 | #include <boost/compute/detail/iterator_range_size.hpp> | |
19 | #include <boost/compute/detail/meta_kernel.hpp> | |
20 | #include <boost/compute/system.hpp> | |
21 | ||
22 | namespace boost { | |
23 | namespace compute { | |
24 | namespace detail { | |
25 | ||
26 | /// | |
27 | /// \brief Search kernel class | |
28 | /// | |
29 | /// Subclass of meta_kernel which is capable of performing search_n | |
30 | /// | |
31 | template<class TextIterator, class OutputIterator> | |
32 | class search_n_kernel : public meta_kernel | |
33 | { | |
34 | public: | |
35 | typedef typename std::iterator_traits<TextIterator>::value_type value_type; | |
36 | ||
37 | search_n_kernel() : meta_kernel("search_n") | |
38 | {} | |
39 | ||
40 | void set_range(TextIterator t_first, | |
41 | TextIterator t_last, | |
42 | value_type value, | |
43 | size_t n, | |
44 | OutputIterator result) | |
45 | { | |
46 | m_n = n; | |
47 | m_n_arg = add_arg<uint_>("n"); | |
48 | ||
49 | m_value = value; | |
50 | m_value_arg = add_arg<value_type>("value"); | |
51 | ||
52 | m_count = iterator_range_size(t_first, t_last); | |
53 | m_count = m_count + 1 - m_n; | |
54 | ||
55 | *this << | |
56 | "uint i = get_global_id(0);\n" << | |
57 | "uint i1 = i;\n" << | |
58 | "uint j;\n" << | |
59 | "for(j = 0; j<n; j++,i++)\n" << | |
60 | "{\n" << | |
61 | " if(value != " << t_first[expr<uint_>("i")] << ")\n" << | |
62 | " j = n + 1;\n" << | |
63 | "}\n" << | |
64 | "if(j == n)\n" << | |
65 | result[expr<uint_>("i1")] << " = 1;\n" << | |
66 | "else\n" << | |
67 | result[expr<uint_>("i1")] << " = 0;\n"; | |
68 | } | |
69 | ||
70 | event exec(command_queue &queue) | |
71 | { | |
72 | if(m_count == 0) { | |
73 | return event(); | |
74 | } | |
75 | ||
76 | set_arg(m_n_arg, uint_(m_n)); | |
77 | set_arg(m_value_arg, m_value); | |
78 | ||
79 | return exec_1d(queue, 0, m_count); | |
80 | } | |
81 | ||
82 | private: | |
83 | size_t m_n; | |
84 | size_t m_n_arg; | |
85 | size_t m_count; | |
86 | value_type m_value; | |
87 | size_t m_value_arg; | |
88 | }; | |
89 | ||
90 | } //end detail namespace | |
91 | ||
92 | /// | |
93 | /// \brief Substring matching algorithm | |
94 | /// | |
95 | /// Searches for the first occurrence of n consecutive occurrences of | |
96 | /// value in text [t_first, t_last). | |
97 | /// \return Iterator pointing to beginning of first occurrence | |
98 | /// | |
99 | /// \param t_first Iterator pointing to start of text | |
100 | /// \param t_last Iterator pointing to end of text | |
101 | /// \param n Number of times value repeats | |
102 | /// \param value Value which repeats | |
103 | /// \param queue Queue on which to execute | |
104 | /// | |
105 | template<class TextIterator, class ValueType> | |
106 | inline TextIterator search_n(TextIterator t_first, | |
107 | TextIterator t_last, | |
108 | size_t n, | |
109 | ValueType value, | |
110 | command_queue &queue = system::default_queue()) | |
111 | { | |
112 | // there is no need to check if pattern starts at last n - 1 indices | |
113 | vector<uint_> matching_indices( | |
114 | detail::iterator_range_size(t_first, t_last) + 1 - n, | |
115 | queue.get_context() | |
116 | ); | |
117 | ||
118 | // search_n_kernel puts value 1 at every index in vector where pattern | |
119 | // of n values starts at | |
120 | detail::search_n_kernel<TextIterator, | |
121 | vector<uint_>::iterator> kernel; | |
122 | ||
123 | kernel.set_range(t_first, t_last, value, n, matching_indices.begin()); | |
124 | kernel.exec(queue); | |
125 | ||
126 | vector<uint_>::iterator index = ::boost::compute::find( | |
127 | matching_indices.begin(), matching_indices.end(), uint_(1), queue | |
128 | ); | |
129 | ||
130 | // pattern was not found | |
131 | if(index == matching_indices.end()) | |
132 | return t_last; | |
133 | ||
134 | return t_first + detail::iterator_range_size(matching_indices.begin(), index); | |
135 | } | |
136 | ||
137 | } //end compute namespace | |
138 | } //end boost namespace | |
139 | ||
140 | #endif // BOOST_COMPUTE_ALGORITHM_DETAIL_SEARCH_N_HPP |