algorithm/detail/serial_merge.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_SERIAL_MERGE_HPP
0012 #define BOOST_COMPUTE_ALGORITHM_SERIAL_MERGE_HPP
0013
0014 #include <iterator>
0015
0016 #include <boost/compute/command_queue.hpp>
0017 #include <boost/compute/detail/meta_kernel.hpp>
0018 #include <boost/compute/detail/iterator_range_size.hpp>
0019
0020 namespace boost {
0021 namespace compute {
0022 namespace detail {
0023
0024 template<class InputIterator1,
0025          class InputIterator2,
0026          class OutputIterator,
0027          class Compare>
0028 inline OutputIterator serial_merge(InputIterator1 first1,
0029                                    InputIterator1 last1,
0030                                    InputIterator2 first2,
0031                                    InputIterator2 last2,
0032                                    OutputIterator result,
0033                                    Compare comp,
0034                                    command_queue &queue)
0035 {
0036     typedef typename
0037         std::iterator_traits<InputIterator1>::value_type
0038         input_type1;
0039     typedef typename
0040         std::iterator_traits<InputIterator2>::value_type
0041         input_type2;
0042     typedef typename
0043         std::iterator_traits<OutputIterator>::difference_type
0044         result_difference_type;
0045
0046     std::ptrdiff_t size1 = std::distance(first1, last1);
0047     std::ptrdiff_t size2 = std::distance(first2, last2);
0048
0049     meta_kernel k("serial_merge");
0050     k.add_set_arg<uint_>("size1", static_cast<uint_>(size1));
0051     k.add_set_arg<uint_>("size2", static_cast<uint_>(size2));
0052
0053     k <<
0054         "uint i = 0;\n" << // index in result range
0055         "uint j = 0;\n" << // index in first input range
0056         "uint k = 0;\n" << // index in second input range
0057
0058         // fetch initial values from each range
0059         k.decl<input_type1>("j_value") << " = " << first1[0] << ";\n" <<
0060         k.decl<input_type2>("k_value") << " = " << first2[0] << ";\n" <<
0061
0062         // merge values from both input ranges to the result range
0063         "while(j < size1 && k < size2){\n" <<
0064         "    if(" << comp(k.var<input_type1>("j_value"),
0065                           k.var<input_type2>("k_value")) << "){\n" <<
0066         "        " << result[k.var<uint_>("i++")] << " = j_value;\n" <<
0067         "        j_value = " << first1[k.var<uint_>("++j")] << ";\n" <<
0068         "    }\n" <<
0069         "    else{\n"
0070         "        " << result[k.var<uint_>("i++")] << " = k_value;\n"
0071         "        k_value = " << first2[k.var<uint_>("++k")] << ";\n" <<
0072         "    }\n"
0073         "}\n"
0074
0075         // copy any remaining values from first range
0076         "while(j < size1){\n" <<
0077             result[k.var<uint_>("i++")] << " = " <<
0078                first1[k.var<uint_>("j++")] << ";\n" <<
0079         "}\n"
0080
0081         // copy any remaining values from second range
0082         "while(k < size2){\n" <<
0083             result[k.var<uint_>("i++")] << " = " <<
0084                first2[k.var<uint_>("k++")] << ";\n" <<
0085         "}\n";
0086
0087     // run kernel
0088     k.exec(queue);
0089
0090     return result + static_cast<result_difference_type>(size1 + size2);
0091 }
0092
0093 } // end detail namespace
0094 } // end compute namespace
0095 } // end boost namespace
0096
0097 #endif // BOOST_COMPUTE_ALGORITHM_SERIAL_MERGE_HPP