1 //---------------------------------------------------------------------------//
2 // Copyright (c) 2013 Kyle Lutz <kyle.r.lutz@gmail.com>
3 //
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
7 //
8 // See http://boostorg.github.com/compute for more information.
9 //---------------------------------------------------------------------------//
10
11 #ifndef BOOST_COMPUTE_ALGORITHM_SERIAL_MERGE_HPP
12 #define BOOST_COMPUTE_ALGORITHM_SERIAL_MERGE_HPP
13
14 #include <iterator>
15
16 #include <boost/compute/command_queue.hpp>
17 #include <boost/compute/detail/meta_kernel.hpp>
18 #include <boost/compute/detail/iterator_range_size.hpp>
19
20 namespace boost {
21 namespace compute {
22 namespace detail {
23
24 template<class InputIterator1,
25 class InputIterator2,
26 class OutputIterator,
27 class Compare>
serial_merge(InputIterator1 first1,InputIterator1 last1,InputIterator2 first2,InputIterator2 last2,OutputIterator result,Compare comp,command_queue & queue)28 inline OutputIterator serial_merge(InputIterator1 first1,
29 InputIterator1 last1,
30 InputIterator2 first2,
31 InputIterator2 last2,
32 OutputIterator result,
33 Compare comp,
34 command_queue &queue)
35 {
36 typedef typename
37 std::iterator_traits<InputIterator1>::value_type
38 input_type1;
39 typedef typename
40 std::iterator_traits<InputIterator2>::value_type
41 input_type2;
42 typedef typename
43 std::iterator_traits<OutputIterator>::difference_type
44 result_difference_type;
45
46 std::ptrdiff_t size1 = std::distance(first1, last1);
47 std::ptrdiff_t size2 = std::distance(first2, last2);
48
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));
52
53 k <<
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
57
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" <<
61
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" <<
68 " }\n" <<
69 " else{\n"
70 " " << result[k.var<uint_>("i++")] << " = k_value;\n"
71 " k_value = " << first2[k.var<uint_>("++k")] << ";\n" <<
72 " }\n"
73 "}\n"
74
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" <<
79 "}\n"
80
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" <<
85 "}\n";
86
87 // run kernel
88 k.exec(queue);
89
90 return result + static_cast<result_difference_type>(size1 + size2);
91 }
92
93 } // end detail namespace
94 } // end compute namespace
95 } // end boost namespace
96
97 #endif // BOOST_COMPUTE_ALGORITHM_SERIAL_MERGE_HPP
98