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_SEARCH_HPP
12 #define BOOST_COMPUTE_ALGORITHM_SEARCH_HPP
13
14 #include <boost/static_assert.hpp>
15
16 #include <boost/compute/algorithm/detail/search_all.hpp>
17 #include <boost/compute/algorithm/find.hpp>
18 #include <boost/compute/container/vector.hpp>
19 #include <boost/compute/detail/iterator_range_size.hpp>
20 #include <boost/compute/detail/meta_kernel.hpp>
21 #include <boost/compute/system.hpp>
22 #include <boost/compute/type_traits/is_device_iterator.hpp>
23
24 namespace boost {
25 namespace compute {
26
27 ///
28 /// \brief Substring matching algorithm
29 ///
30 /// Searches for the first match of the pattern [p_first, p_last)
31 /// in text [t_first, t_last).
32 /// \return Iterator pointing to beginning of first occurrence
33 ///
34 /// \param t_first Iterator pointing to start of text
35 /// \param t_last Iterator pointing to end of text
36 /// \param p_first Iterator pointing to start of pattern
37 /// \param p_last Iterator pointing to end of pattern
38 /// \param queue Queue on which to execute
39 ///
40 /// Space complexity: \Omega(distance(\p t_first, \p t_last))
41 template<class TextIterator, class PatternIterator>
search(TextIterator t_first,TextIterator t_last,PatternIterator p_first,PatternIterator p_last,command_queue & queue=system::default_queue ())42 inline TextIterator search(TextIterator t_first,
43 TextIterator t_last,
44 PatternIterator p_first,
45 PatternIterator p_last,
46 command_queue &queue = system::default_queue())
47 {
48 BOOST_STATIC_ASSERT(is_device_iterator<TextIterator>::value);
49 BOOST_STATIC_ASSERT(is_device_iterator<PatternIterator>::value);
50
51 // there is no need to check if pattern starts at last n - 1 indices
52 vector<uint_> matching_indices(
53 detail::iterator_range_size(t_first, t_last)
54 - detail::iterator_range_size(p_first, p_last) + 1,
55 queue.get_context()
56 );
57
58 // search_kernel puts value 1 at every index in vector where pattern starts at
59 detail::search_kernel<PatternIterator,
60 TextIterator,
61 vector<uint_>::iterator> kernel;
62
63 kernel.set_range(p_first, p_last, t_first, t_last, matching_indices.begin());
64 kernel.exec(queue);
65
66 vector<uint_>::iterator index = ::boost::compute::find(
67 matching_indices.begin(), matching_indices.end(), uint_(1), queue
68 );
69
70 // pattern was not found
71 if(index == matching_indices.end())
72 return t_last;
73
74 return t_first + detail::iterator_range_size(matching_indices.begin(), index);
75 }
76
77 } //end compute namespace
78 } //end boost namespace
79
80 #endif // BOOST_COMPUTE_ALGORITHM_SEARCH_HPP
81