/usr/include/boost/compute/algorithm
Edit: /usr/include/boost/compute/algorithm/find_end.hpp (4772B)
//---------------------------------------------------------------------------//
// Copyright (c) 2014 Roshan
//
// Distributed under the Boost Software License, Version 1.0
// See accompanying file LICENSE_1_0.txt or copy at
// http://www.boost.org/LICENSE_1_0.txt
//
// See http://boostorg.github.com/compute for more information.
//---------------------------------------------------------------------------//
#ifndef BOOST_COMPUTE_ALGORITHM_FIND_END_HPP
#define BOOST_COMPUTE_ALGORITHM_FIND_END_HPP
#include
#include
#include
#include
#include
#include
#include
#include
#include
namespace boost {
namespace compute {
namespace detail {
///
/// \brief Helper function for find_end
///
/// Basically a copy of find_if which returns last occurrence
/// instead of first occurrence
///
template
inline InputIterator find_end_helper(InputIterator first,
InputIterator last,
UnaryPredicate predicate,
command_queue &queue)
{
typedef typename std::iterator_traits::value_type value_type;
typedef typename std::iterator_traits::difference_type difference_type;
size_t count = detail::iterator_range_size(first, last);
if(count == 0){
return last;
}
const context &context = queue.get_context();
detail::meta_kernel k("find_end");
size_t index_arg = k.add_arg(memory_object::global_memory, "index");
atomic_max atomic_max_int;
k << k.decl("i") << " = get_global_id(0);\n"
<< k.decl("value") << "="
<< first[k.var("i")] << ";\n"
<< "if(" << predicate(k.var("value")) << "){\n"
<< " " << atomic_max_int(k.var("index"), k.var("i")) << ";\n"
<< "}\n";
kernel kernel = k.compile(context);
scalar index(context);
kernel.set_arg(index_arg, index.get_buffer());
index.write(static_cast(-1), queue);
queue.enqueue_1d_range_kernel(kernel, 0, count, 0);
int result = static_cast(index.read(queue));
if(result == -1){
return last;
}
else {
return first + static_cast(result);
}
}
} // end detail namespace
///
/// \brief Substring matching algorithm
///
/// Searches for the last match of the pattern [p_first, p_last)
/// in text [t_first, t_last).
/// \return Iterator pointing to beginning of last occurence
///
/// \param t_first Iterator pointing to start of text
/// \param t_last Iterator pointing to end of text
/// \param p_first Iterator pointing to start of pattern
/// \param p_last Iterator pointing to end of pattern
/// \param queue Queue on which to execute
///
/// Space complexity: \Omega(n)
///
template
inline TextIterator find_end(TextIterator t_first,
TextIterator t_last,
PatternIterator p_first,
PatternIterator p_last,
command_queue &queue = system::default_queue())
{
BOOST_STATIC_ASSERT(is_device_iterator::value);
BOOST_STATIC_ASSERT(is_device_iterator::value);
const context &context = queue.get_context();
// there is no need to check if pattern starts at last n - 1 indices
vector matching_indices(
detail::iterator_range_size(t_first, t_last)
+ 1 - detail::iterator_range_size(p_first, p_last),
context
);
detail::search_kernel::iterator> kernel;
kernel.set_range(p_first, p_last, t_first, t_last, matching_indices.begin());
kernel.exec(queue);
using boost::compute::_1;
vector::iterator index =
detail::find_end_helper(
matching_indices.begin(),
matching_indices.end(),
_1 == 1,
queue
);
// pattern was not found
if(index == matching_indices.end())
return t_last;
return t_first + detail::iterator_range_size(matching_indices.begin(), index);
}
} //end compute namespace
} //end boost namespace
#endif // BOOST_COMPUTE_ALGORITHM_FIND_END_HPP