1 //---------------------------------------------------------------------------//
2 // Copyright (c) 2013 Kyle Lutz <kyle.r.lutz@gmail.com>
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
8 // See http://boostorg.github.com/compute for more information.
9 //---------------------------------------------------------------------------//
11 #ifndef BOOST_COMPUTE_ALGORITHM_SERIAL_MERGE_HPP
12 #define BOOST_COMPUTE_ALGORITHM_SERIAL_MERGE_HPP
16 #include <boost/compute/command_queue.hpp>
17 #include <boost/compute/detail/meta_kernel.hpp>
18 #include <boost/compute/detail/iterator_range_size.hpp>
24 template<class InputIterator1,
28 inline OutputIterator serial_merge(InputIterator1 first1,
30 InputIterator2 first2,
32 OutputIterator result,
37 std::iterator_traits<InputIterator1>::value_type
40 std::iterator_traits<InputIterator2>::value_type
43 std::iterator_traits<OutputIterator>::difference_type
44 result_difference_type;
46 std::ptrdiff_t size1 = std::distance(first1, last1);
47 std::ptrdiff_t size2 = std::distance(first2, last2);
49 meta_kernel k("serial_merge");
50 k.add_set_arg<uint_>("size1", static_cast<uint_>(size1));
51 k.add_set_arg<uint_>("size2", static_cast<uint_>(size2));
54 "uint i = 0;\n" << // index in result range
55 "uint j = 0;\n" << // index in first input range
56 "uint k = 0;\n" << // index in second input range
58 // fetch initial values from each range
59 k.decl<input_type1>("j_value") << " = " << first1[0] << ";\n" <<
60 k.decl<input_type2>("k_value") << " = " << first2[0] << ";\n" <<
62 // merge values from both input ranges to the result range
63 "while(j < size1 && k < size2){\n" <<
64 " if(" << comp(k.var<input_type1>("j_value"),
65 k.var<input_type2>("k_value")) << "){\n" <<
66 " " << result[k.var<uint_>("i++")] << " = j_value;\n" <<
67 " j_value = " << first1[k.var<uint_>("++j")] << ";\n" <<
70 " " << result[k.var<uint_>("i++")] << " = k_value;\n"
71 " k_value = " << first2[k.var<uint_>("++k")] << ";\n" <<
75 // copy any remaining values from first range
76 "while(j < size1){\n" <<
77 result[k.var<uint_>("i++")] << " = " <<
78 first1[k.var<uint_>("j++")] << ";\n" <<
81 // copy any remaining values from second range
82 "while(k < size2){\n" <<
83 result[k.var<uint_>("i++")] << " = " <<
84 first2[k.var<uint_>("k++")] << ";\n" <<
90 return result + static_cast<result_difference_type>(size1 + size2);
93 } // end detail namespace
94 } // end compute namespace
95 } // end boost namespace
97 #endif // BOOST_COMPUTE_ALGORITHM_SERIAL_MERGE_HPP