1 //---------------------------------------------------------------------------//
2 // Copyright (c) 2016 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 #define BOOST_TEST_MODULE TestRadixSortByKey
12 #include <boost/test/unit_test.hpp>
13
14 #include <iostream>
15
16 #include <boost/compute/system.hpp>
17 #include <boost/compute/algorithm/is_sorted.hpp>
18 #include <boost/compute/algorithm/detail/radix_sort.hpp>
19 #include <boost/compute/container/vector.hpp>
20
21 #include "quirks.hpp"
22 #include "check_macros.hpp"
23 #include "context_setup.hpp"
24
25 namespace compute = boost::compute;
26
27 const bool descending = false;
28
29 // radix_sort_by_key should be stable
BOOST_AUTO_TEST_CASE(stable_radix_sort_int_by_int)30 BOOST_AUTO_TEST_CASE(stable_radix_sort_int_by_int)
31 {
32 if(is_apple_cpu_device(device)) {
33 std::cerr
34 << "skipping all radix_sort_by_key tests due to Apple platform"
35 << " behavior when local memory is used on a CPU device"
36 << std::endl;
37 return;
38 }
39
40 compute::int_ keys_data[] = { 10, 9, 2, 7, 6, -1, 4, 2, 2, 10 };
41 compute::int_ values_data[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
42
43 compute::vector<compute::int_> keys(keys_data, keys_data + 10, queue);
44 compute::vector<compute::int_> values(values_data, values_data + 10, queue);
45
46 BOOST_CHECK(!compute::is_sorted(keys.begin(), keys.end(), queue));
47 compute::detail::radix_sort_by_key(keys.begin(), keys.end(), values.begin(), queue);
48 BOOST_CHECK(compute::is_sorted(keys.begin(), keys.end(), queue));
49
50 CHECK_RANGE_EQUAL(
51 compute::int_, 10, keys,
52 (-1, 2, 2, 2, 4, 6, 7, 9, 10, 10) // keys
53 // ( 6, 3, 8, 9, 7, 5, 4, 2, 1, 10) values
54 );
55 CHECK_RANGE_EQUAL(
56 compute::int_, 10, values,
57 // (-1, 2, 2, 2, 4, 6, 7, 9, 10, 10) keys
58 ( 6, 3, 8, 9, 7, 5, 4, 2, 1, 10) // values
59 );
60 }
61
62 // radix_sort_by_key should be stable
BOOST_AUTO_TEST_CASE(stable_radix_sort_int_by_int_desc)63 BOOST_AUTO_TEST_CASE(stable_radix_sort_int_by_int_desc)
64 {
65 if(is_apple_cpu_device(device)) {
66 return;
67 }
68
69 compute::int_ keys_data[] = { 10, 9, 2, 7, 6, -1, 4, 2, 2, 10 };
70 compute::int_ values_data[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
71
72 compute::vector<compute::int_> keys(keys_data, keys_data + 10, queue);
73 compute::vector<compute::int_> values(values_data, values_data + 10, queue);
74
75 BOOST_CHECK(
76 !compute::is_sorted(
77 keys.begin(), keys.end(), compute::greater<compute::int_>(), queue
78 )
79 );
80 compute::detail::radix_sort_by_key(
81 keys.begin(), keys.end(), values.begin(), descending, queue
82 );
83 BOOST_CHECK(
84 compute::is_sorted(
85 keys.begin(), keys.end(), compute::greater<compute::int_>(), queue
86 )
87 );
88
89 CHECK_RANGE_EQUAL(
90 compute::int_, 10, keys,
91 (10, 10, 9, 7, 6, 4, 2, 2, 2, -1) // keys
92 // ( 1, 10, 2, 4, 5, 7, 3, 8, 9, 6) values
93 );
94 CHECK_RANGE_EQUAL(
95 compute::int_, 10, values,
96 // (10, 10, 9, 7, 6, 4, 2, 2, 2, -1) // keys
97 ( 1, 10, 2, 4, 5, 7, 3, 8, 9, 6) // values
98 );
99 }
100
101 // radix_sort_by_key should be stable
BOOST_AUTO_TEST_CASE(stable_radix_sort_uint_by_uint)102 BOOST_AUTO_TEST_CASE(stable_radix_sort_uint_by_uint)
103 {
104 if(is_apple_cpu_device(device)) {
105 return;
106 }
107
108 compute::uint_ keys_data[] = { 10, 9, 2, 7, 6, 1, 4, 2, 2, 10 };
109 compute::uint_ values_data[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
110
111 compute::vector<compute::uint_> keys(keys_data, keys_data + 10, queue);
112 compute::vector<compute::uint_> values(values_data, values_data + 10, queue);
113
114 BOOST_CHECK(!compute::is_sorted(keys.begin(), keys.end(), queue));
115 compute::detail::radix_sort_by_key(keys.begin(), keys.end(), values.begin(), queue);
116 BOOST_CHECK(compute::is_sorted(keys.begin(), keys.end(), queue));
117
118 CHECK_RANGE_EQUAL(
119 compute::uint_, 10, keys,
120 (1, 2, 2, 2, 4, 6, 7, 9, 10, 10) // keys
121 // (6, 3, 8, 9, 7, 5, 4, 2, 1, 10) values
122 );
123 CHECK_RANGE_EQUAL(
124 compute::uint_, 10, values,
125 // (1, 2, 2, 2, 4, 6, 7, 9, 10, 10) keys
126 (6, 3, 8, 9, 7, 5, 4, 2, 1, 10) // values
127 );
128 }
129
130 // radix_sort_by_key should be stable
BOOST_AUTO_TEST_CASE(stable_radix_sort_uint_by_uint_desc)131 BOOST_AUTO_TEST_CASE(stable_radix_sort_uint_by_uint_desc)
132 {
133 if(is_apple_cpu_device(device)) {
134 return;
135 }
136
137 compute::uint_ keys_data[] = { 10, 9, 2, 7, 6, 1, 4, 2, 2, 10 };
138 compute::uint_ values_data[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
139
140 compute::vector<compute::uint_> keys(keys_data, keys_data + 10, queue);
141 compute::vector<compute::uint_> values(values_data, values_data + 10, queue);
142
143 BOOST_CHECK(
144 !compute::is_sorted(
145 keys.begin(), keys.end(), compute::greater<compute::uint_>(), queue
146 )
147 );
148 compute::detail::radix_sort_by_key(
149 keys.begin(), keys.end(), values.begin(), descending, queue
150 );
151 BOOST_CHECK(
152 compute::is_sorted(
153 keys.begin(), keys.end(), compute::greater<compute::uint_>(), queue
154 )
155 );
156
157 CHECK_RANGE_EQUAL(
158 compute::uint_, 10, keys,
159 (10, 10, 9, 7, 6, 4, 2, 2, 2, 1) // keys
160 // ( 1, 10, 2, 4, 5, 7, 3, 8, 9, 6) values
161 );
162 CHECK_RANGE_EQUAL(
163 compute::uint_, 10, values,
164 // (10, 10, 9, 7, 6, 4, 2, 2, 2, 1) // keys
165 ( 1, 10, 2, 4, 5, 7, 3, 8, 9, 6) // values
166 );
167 }
168
169
170 // radix_sort_by_key should be stable
BOOST_AUTO_TEST_CASE(stable_radix_sort_int_by_float)171 BOOST_AUTO_TEST_CASE(stable_radix_sort_int_by_float)
172 {
173 if(is_apple_cpu_device(device)) {
174 return;
175 }
176
177 compute::float_ keys_data[] = { 10., 5.5, 10., 7., 5.5};
178 compute::int_ values_data[] = { 1, 200, -10, 2, 4 };
179
180 compute::vector<compute::float_> keys(keys_data, keys_data + 5, queue);
181 compute::vector<compute::uint_> values(values_data, values_data + 5, queue);
182
183 BOOST_CHECK(!compute::is_sorted(keys.begin(), keys.end(), queue));
184 compute::detail::radix_sort_by_key(keys.begin(), keys.end(), values.begin(), queue);
185 BOOST_CHECK(compute::is_sorted(keys.begin(), keys.end(), queue));
186
187 CHECK_RANGE_EQUAL(
188 compute::float_, 5, keys,
189 (5.5, 5.5, 7., 10., 10.) // keys
190 // (200, 4, 2, 1, -10) values
191 );
192 CHECK_RANGE_EQUAL(
193 compute::int_, 5, values,
194 // (5.5, 5.5, 7., 10., 10.) keys
195 (200, 4, 2, 1, -10) // values
196 );
197 }
198
199 // radix_sort_by_key should be stable
BOOST_AUTO_TEST_CASE(stable_radix_sort_int_by_float_desc)200 BOOST_AUTO_TEST_CASE(stable_radix_sort_int_by_float_desc)
201 {
202 if(is_apple_cpu_device(device)) {
203 return;
204 }
205
206 compute::float_ keys_data[] = { 10., 5.5, 10., 7., 5.5};
207 compute::int_ values_data[] = { 1, 200, -10, 2, 4 };
208
209 compute::vector<compute::float_> keys(keys_data, keys_data + 5, queue);
210 compute::vector<compute::uint_> values(values_data, values_data + 5, queue);
211
212 BOOST_CHECK(
213 !compute::is_sorted(
214 keys.begin(), keys.end(), compute::greater<compute::float_>(), queue
215 )
216 );
217 compute::detail::radix_sort_by_key(
218 keys.begin(), keys.end(), values.begin(), descending, queue
219 );
220 BOOST_CHECK(
221 compute::is_sorted(
222 keys.begin(), keys.end(), compute::greater<compute::float_>(), queue
223 )
224 );
225
226 CHECK_RANGE_EQUAL(
227 compute::float_, 5, keys,
228 (10., 10., 7., 5.5, 5.5) // keys
229 // ( 1, -10, 2, 200, 4) values
230 );
231 CHECK_RANGE_EQUAL(
232 compute::int_, 5, values,
233 // (10., 10., 7., 5.5, 5.5) // keys
234 ( 1, -10, 2, 200, 4) // values
235 );
236 }
237
238
239 // radix_sort_by_key should be stable
BOOST_AUTO_TEST_CASE(stable_radix_sort_char_by_int)240 BOOST_AUTO_TEST_CASE(stable_radix_sort_char_by_int)
241 {
242 if(is_apple_cpu_device(device)) {
243 return;
244 }
245
246 compute::int_ keys_data[] = { 6, 1, 1, 3, 4, 7, 5, 1 };
247 compute::char_ values_data[] = { 'g', 'c', 'b', 'd', 'e', 'h', 'f', 'a' };
248
249 compute::vector<compute::int_> keys(keys_data, keys_data + 8, queue);
250 compute::vector<compute::char_> values(values_data, values_data + 8, queue);
251
252 BOOST_CHECK(!compute::is_sorted(keys.begin(), keys.end(), queue));
253 compute::detail::radix_sort_by_key(keys.begin(), keys.end(), values.begin(), queue);
254 BOOST_CHECK(compute::is_sorted(keys.begin(), keys.end(), queue));
255
256 CHECK_RANGE_EQUAL(
257 compute::int_, 8, keys,
258 (1, 1, 1, 3, 4, 5, 6, 7)
259 );
260 CHECK_RANGE_EQUAL(
261 compute::char_, 8, values,
262 ('c', 'b', 'a', 'd', 'e', 'f', 'g', 'h')
263 );
264 }
265
266 // radix_sort_by_key should be stable
BOOST_AUTO_TEST_CASE(stable_radix_sort_int2_by_int)267 BOOST_AUTO_TEST_CASE(stable_radix_sort_int2_by_int)
268 {
269 if(is_apple_cpu_device(device)) {
270 return;
271 }
272
273 compute::int_ keys_data[] = { 6, 1, 1, 3, 4, 7, 5, 1 };
274 compute::int2_ values_data[] = {
275 compute::int2_(1, 1), // 6
276 compute::int2_(1, 2), // 1
277 compute::int2_(1, 3), // 1
278 compute::int2_(1, 4), // 3
279 compute::int2_(1, 5), // 4
280 compute::int2_(1, 6), // 7
281 compute::int2_(1, 7), // 5
282 compute::int2_(1, 8) // 1
283 };
284
285 compute::vector<compute::int_> keys(keys_data, keys_data + 8, queue);
286 compute::vector<compute::int2_> values(values_data, values_data + 8, queue);
287
288 BOOST_CHECK(!compute::is_sorted(keys.begin(), keys.end(), queue));
289 compute::detail::radix_sort_by_key(keys.begin(), keys.end(), values.begin(), queue);
290 BOOST_CHECK(compute::is_sorted(keys.begin(), keys.end(), queue));
291
292 CHECK_RANGE_EQUAL(
293 compute::int_, 8, keys,
294 (1, 1, 1, 3, 4, 5, 6, 7)
295 );
296 CHECK_RANGE_EQUAL(
297 compute::int2_, 8, values,
298 (
299 compute::int2_(1, 2),
300 compute::int2_(1, 3),
301 compute::int2_(1, 8),
302 compute::int2_(1, 4),
303 compute::int2_(1, 5),
304 compute::int2_(1, 7),
305 compute::int2_(1, 1),
306 compute::int2_(1, 6)
307 )
308 );
309 }
310
311 BOOST_AUTO_TEST_SUITE_END()
312