| 40 | /// Space complexity: \Omega(distance(\p t_first, \p t_last)) |
| 41 | template<class TextIterator, class PatternIterator> |
| 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 |