]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | //---------------------------------------------------------------------------// |
2 | // Copyright (c) 2015 Jakub Szuppe <j.szuppe@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_REDUCE_BY_KEY_HPP | |
12 | #define BOOST_COMPUTE_ALGORITHM_REDUCE_BY_KEY_HPP | |
13 | ||
14 | #include <iterator> | |
15 | #include <utility> | |
16 | ||
92f5a8d4 TL |
17 | #include <boost/static_assert.hpp> |
18 | ||
7c673cae FG |
19 | #include <boost/compute/command_queue.hpp> |
20 | #include <boost/compute/device.hpp> | |
21 | #include <boost/compute/functional.hpp> | |
22 | #include <boost/compute/system.hpp> | |
23 | #include <boost/compute/algorithm/detail/reduce_by_key.hpp> | |
92f5a8d4 | 24 | #include <boost/compute/type_traits/is_device_iterator.hpp> |
7c673cae FG |
25 | |
26 | namespace boost { | |
27 | namespace compute { | |
28 | ||
29 | /// The \c reduce_by_key() algorithm performs reduction for each contiguous | |
30 | /// subsequence of values determinate by equivalent keys. | |
31 | /// | |
32 | /// Returns a pair of iterators at the end of the ranges [\p keys_result, keys_result_last) | |
33 | /// and [\p values_result, \p values_result_last). | |
34 | /// | |
35 | /// If no function is specified, \c plus will be used. | |
36 | /// If no predicate is specified, \c equal_to will be used. | |
37 | /// | |
38 | /// \param keys_first the first key | |
39 | /// \param keys_last the last key | |
40 | /// \param values_first the first input value | |
41 | /// \param keys_result iterator pointing to the key output | |
42 | /// \param values_result iterator pointing to the reduced value output | |
43 | /// \param function binary reduction function | |
44 | /// \param predicate binary predicate which returns true only if two keys are equal | |
45 | /// \param queue command queue to perform the operation | |
46 | /// | |
47 | /// The \c reduce_by_key() algorithm assumes that the binary reduction function | |
48 | /// is associative. When used with non-associative functions the result may | |
49 | /// be non-deterministic and vary in precision. Notably this affects the | |
50 | /// \c plus<float>() function as floating-point addition is not associative | |
51 | /// and may produce slightly different results than a serial algorithm. | |
52 | /// | |
53 | /// For example, to calculate the sum of the values for each key: | |
54 | /// | |
55 | /// \snippet test/test_reduce_by_key.cpp reduce_by_key_int | |
56 | /// | |
b32b8144 FG |
57 | /// Space complexity on GPUs: \Omega(2n)<br> |
58 | /// Space complexity on CPUs: \Omega(1) | |
59 | /// | |
7c673cae FG |
60 | /// \see reduce() |
61 | template<class InputKeyIterator, class InputValueIterator, | |
62 | class OutputKeyIterator, class OutputValueIterator, | |
63 | class BinaryFunction, class BinaryPredicate> | |
64 | inline std::pair<OutputKeyIterator, OutputValueIterator> | |
65 | reduce_by_key(InputKeyIterator keys_first, | |
66 | InputKeyIterator keys_last, | |
67 | InputValueIterator values_first, | |
68 | OutputKeyIterator keys_result, | |
69 | OutputValueIterator values_result, | |
70 | BinaryFunction function, | |
71 | BinaryPredicate predicate, | |
72 | command_queue &queue = system::default_queue()) | |
73 | { | |
92f5a8d4 TL |
74 | BOOST_STATIC_ASSERT(is_device_iterator<InputKeyIterator>::value); |
75 | BOOST_STATIC_ASSERT(is_device_iterator<InputValueIterator>::value); | |
76 | BOOST_STATIC_ASSERT(is_device_iterator<OutputKeyIterator>::value); | |
77 | BOOST_STATIC_ASSERT(is_device_iterator<OutputValueIterator>::value); | |
78 | ||
7c673cae FG |
79 | return detail::dispatch_reduce_by_key(keys_first, keys_last, values_first, |
80 | keys_result, values_result, | |
81 | function, predicate, | |
82 | queue); | |
83 | } | |
84 | ||
85 | /// \overload | |
86 | template<class InputKeyIterator, class InputValueIterator, | |
87 | class OutputKeyIterator, class OutputValueIterator, | |
88 | class BinaryFunction> | |
89 | inline std::pair<OutputKeyIterator, OutputValueIterator> | |
90 | reduce_by_key(InputKeyIterator keys_first, | |
91 | InputKeyIterator keys_last, | |
92 | InputValueIterator values_first, | |
93 | OutputKeyIterator keys_result, | |
94 | OutputValueIterator values_result, | |
95 | BinaryFunction function, | |
96 | command_queue &queue = system::default_queue()) | |
97 | { | |
92f5a8d4 TL |
98 | BOOST_STATIC_ASSERT(is_device_iterator<InputKeyIterator>::value); |
99 | BOOST_STATIC_ASSERT(is_device_iterator<InputValueIterator>::value); | |
100 | BOOST_STATIC_ASSERT(is_device_iterator<OutputKeyIterator>::value); | |
101 | BOOST_STATIC_ASSERT(is_device_iterator<OutputValueIterator>::value); | |
7c673cae FG |
102 | typedef typename std::iterator_traits<InputKeyIterator>::value_type key_type; |
103 | ||
104 | return reduce_by_key(keys_first, keys_last, values_first, | |
105 | keys_result, values_result, | |
106 | function, equal_to<key_type>(), | |
107 | queue); | |
108 | } | |
109 | ||
110 | /// \overload | |
111 | template<class InputKeyIterator, class InputValueIterator, | |
112 | class OutputKeyIterator, class OutputValueIterator> | |
113 | inline std::pair<OutputKeyIterator, OutputValueIterator> | |
114 | reduce_by_key(InputKeyIterator keys_first, | |
115 | InputKeyIterator keys_last, | |
116 | InputValueIterator values_first, | |
117 | OutputKeyIterator keys_result, | |
118 | OutputValueIterator values_result, | |
119 | command_queue &queue = system::default_queue()) | |
120 | { | |
92f5a8d4 TL |
121 | BOOST_STATIC_ASSERT(is_device_iterator<InputKeyIterator>::value); |
122 | BOOST_STATIC_ASSERT(is_device_iterator<InputValueIterator>::value); | |
123 | BOOST_STATIC_ASSERT(is_device_iterator<OutputKeyIterator>::value); | |
124 | BOOST_STATIC_ASSERT(is_device_iterator<OutputValueIterator>::value); | |
7c673cae FG |
125 | typedef typename std::iterator_traits<InputKeyIterator>::value_type key_type; |
126 | typedef typename std::iterator_traits<InputValueIterator>::value_type value_type; | |
127 | ||
128 | return reduce_by_key(keys_first, keys_last, values_first, | |
129 | keys_result, values_result, | |
130 | plus<value_type>(), equal_to<key_type>(), | |
131 | queue); | |
132 | } | |
133 | ||
134 | } // end compute namespace | |
135 | } // end boost namespace | |
136 | ||
137 | #endif // BOOST_COMPUTE_ALGORITHM_REDUCE_BY_KEY_HPP |