compute/algorithm/mismatch.hpp

0001 //---------------------------------------------------------------------------//
0002 // Copyright (c) 2013 Kyle Lutz <kyle.r.lutz@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_MISMATCH_HPP
0012 #define BOOST_COMPUTE_ALGORITHM_MISMATCH_HPP
0013
0014 #include <iterator>
0015 #include <utility>
0016
0017 #include <boost/static_assert.hpp>
0018
0019 #include <boost/compute/system.hpp>
0020 #include <boost/compute/functional.hpp>
0021 #include <boost/compute/command_queue.hpp>
0022 #include <boost/compute/algorithm/find.hpp>
0023 #include <boost/compute/iterator/transform_iterator.hpp>
0024 #include <boost/compute/iterator/zip_iterator.hpp>
0025 #include <boost/compute/functional/detail/unpack.hpp>
0026 #include <boost/compute/type_traits/is_device_iterator.hpp>
0027
0028 namespace boost {
0029 namespace compute {
0030
0031 /// Returns a pair of iterators pointing to the first position where the
0032 /// range [\p first1, \p last1) and the range starting at \p first2
0033 /// differ.
0034 ///
0035 /// Space complexity: \Omega(1)
0036 template<class InputIterator1, class InputIterator2>
0037 inline std::pair<InputIterator1, InputIterator2>
0038 mismatch(InputIterator1 first1,
0039          InputIterator1 last1,
0040          InputIterator2 first2,
0041          command_queue &queue = system::default_queue())
0042 {
0043     BOOST_STATIC_ASSERT(is_device_iterator<InputIterator1>::value);
0044     BOOST_STATIC_ASSERT(is_device_iterator<InputIterator2>::value);
0045     typedef typename std::iterator_traits<InputIterator1>::value_type value_type;
0046
0047     ::boost::compute::equal_to<value_type> op;
0048
0049     InputIterator2 last2 = first2 + std::distance(first1, last1);
0050
0051     InputIterator1 iter =
0052         boost::get<0>(
0053             ::boost::compute::find(
0054                 ::boost::compute::make_transform_iterator(
0055                     ::boost::compute::make_zip_iterator(
0056                         boost::make_tuple(first1, first2)
0057                     ),
0058                     detail::unpack(op)
0059                 ),
0060                 ::boost::compute::make_transform_iterator(
0061                     ::boost::compute::make_zip_iterator(
0062                         boost::make_tuple(last1, last2)
0063                     ),
0064                     detail::unpack(op)
0065                 ),
0066                 false,
0067                 queue
0068             ).base().get_iterator_tuple()
0069         );
0070
0071     return std::make_pair(iter, first2 + std::distance(first1, iter));
0072 }
0073
0074 /// \overload
0075 template<class InputIterator1, class InputIterator2>
0076 inline std::pair<InputIterator1, InputIterator2>
0077 mismatch(InputIterator1 first1,
0078          InputIterator1 last1,
0079          InputIterator2 first2,
0080          InputIterator2 last2,
0081          command_queue &queue = system::default_queue())
0082 {
0083     BOOST_STATIC_ASSERT(is_device_iterator<InputIterator1>::value);
0084     BOOST_STATIC_ASSERT(is_device_iterator<InputIterator2>::value);
0085     if(std::distance(first1, last1) < std::distance(first2, last2)){
0086         return ::boost::compute::mismatch(first1, last1, first2, queue);
0087     }
0088     else {
0089         return ::boost::compute::mismatch(
0090             first1, first1 + std::distance(first2, last2), first2, queue
0091         );
0092     }
0093 }
0094
0095 } // end compute namespace
0096 } // end boost namespace
0097
0098 #endif // BOOST_COMPUTE_ALGORITHM_MISMATCH_HPP