]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
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> | |
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 |