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 #define BOOST_TEST_MODULE TestSort
12 #include <boost/test/unit_test.hpp>
13
14 #include <boost/compute/system.hpp>
15 #include <boost/compute/algorithm/sort.hpp>
16 #include <boost/compute/algorithm/is_sorted.hpp>
17 #include <boost/compute/container/vector.hpp>
18 #include <boost/compute/types/struct.hpp>
19
20 struct Particle
21 {
ParticleParticle22 Particle(): x(0.f), y(0.f) { }
ParticleParticle23 Particle(float _x, float _y): x(_x), y(_y) { }
24
25 float x;
26 float y;
27 };
28
29 // adapt struct for OpenCL
30 BOOST_COMPUTE_ADAPT_STRUCT(Particle, Particle, (x, y))
31
32 #include "check_macros.hpp"
33 #include "context_setup.hpp"
34
35 namespace bc = boost::compute;
36
37 // test trivial sorting of zero and one element vectors
BOOST_AUTO_TEST_CASE(sort_int_0_and_1)38 BOOST_AUTO_TEST_CASE(sort_int_0_and_1)
39 {
40 boost::compute::vector<int> vec(context);
41 BOOST_CHECK_EQUAL(vec.size(), size_t(0));
42 BOOST_CHECK(boost::compute::is_sorted(vec.begin(), vec.end(), queue) == true);
43 boost::compute::sort(vec.begin(), vec.end(), queue);
44
45 vec.push_back(11, queue);
46 BOOST_CHECK_EQUAL(vec.size(), size_t(1));
47 BOOST_CHECK(boost::compute::is_sorted(vec.begin(), vec.end(), queue) == true);
48 boost::compute::sort(vec.begin(), vec.end(), queue);
49 }
50
51 // test sorting of two element int vectors
BOOST_AUTO_TEST_CASE(sort_int_2)52 BOOST_AUTO_TEST_CASE(sort_int_2)
53 {
54 int data[] = { 4, 2 };
55 boost::compute::vector<int> vec(data, data + 2, queue);
56
57 // check that vec is unsorted
58 BOOST_CHECK(boost::compute::is_sorted(vec.begin(), vec.end(), queue) == false);
59
60 // sort vec
61 boost::compute::sort(vec.begin(), vec.end(), queue);
62
63 // check that vec is sorted
64 BOOST_CHECK(boost::compute::is_sorted(vec.begin(), vec.end(), queue) == true);
65
66 // sort already sorted vec and ensure it is still sorted
67 boost::compute::sort(vec.begin(), vec.end());
68 BOOST_CHECK(boost::compute::is_sorted(vec.begin(), vec.end(), queue) == true);
69 }
70
BOOST_AUTO_TEST_CASE(sort_float_3)71 BOOST_AUTO_TEST_CASE(sort_float_3)
72 {
73 float data[] = { 2.3f, 0.1f, 1.2f };
74 boost::compute::vector<float> vec(data, data + 3, queue);
75 boost::compute::sort(vec.begin(), vec.end(), queue);
76 CHECK_RANGE_EQUAL(float, 3, vec, (0.1f, 1.2f, 2.3f));
77 }
78
BOOST_AUTO_TEST_CASE(sort_char_vector)79 BOOST_AUTO_TEST_CASE(sort_char_vector)
80 {
81 using boost::compute::char_;
82
83 char_ data[] = { 'c', 'a', '0', '7', 'B', 'F', '\0', '$' };
84 boost::compute::vector<char_> vector(data, data + 8, queue);
85 BOOST_CHECK_EQUAL(vector.size(), size_t(8));
86 BOOST_CHECK(boost::compute::is_sorted(vector.begin(), vector.end(), queue) == false);
87
88 boost::compute::sort(vector.begin(), vector.end(), queue);
89 BOOST_CHECK(boost::compute::is_sorted(vector.begin(), vector.end(), queue) == true);
90 CHECK_RANGE_EQUAL(char_, 8, vector, ('\0', '$', '0', '7', 'B', 'F', 'a', 'c'));
91 }
92
BOOST_AUTO_TEST_CASE(sort_uchar_vector)93 BOOST_AUTO_TEST_CASE(sort_uchar_vector)
94 {
95 using boost::compute::uchar_;
96
97 uchar_ data[] = { 0x12, 0x00, 0xFF, 0xB4, 0x80, 0x32, 0x64, 0xA2 };
98 boost::compute::vector<uchar_> vector(data, data + 8, queue);
99 BOOST_CHECK_EQUAL(vector.size(), size_t(8));
100 BOOST_CHECK(boost::compute::is_sorted(vector.begin(), vector.end(), queue) == false);
101
102 boost::compute::sort(vector.begin(), vector.end(), queue);
103 BOOST_CHECK(boost::compute::is_sorted(vector.begin(), vector.end(), queue) == true);
104 CHECK_RANGE_EQUAL(uchar_, 8, vector, (0x00, 0x12, 0x32, 0x64, 0x80, 0xA2, 0xB4, 0xFF));
105 }
106
BOOST_AUTO_TEST_CASE(sort_short_vector)107 BOOST_AUTO_TEST_CASE(sort_short_vector)
108 {
109 using boost::compute::short_;
110
111 short_ data[] = { -4, 152, -94, 963, 31002, -456, 0, -2113 };
112 boost::compute::vector<short_> vector(data, data + 8, queue);
113 BOOST_CHECK_EQUAL(vector.size(), size_t(8));
114 BOOST_CHECK(boost::compute::is_sorted(vector.begin(), vector.end(), queue) == false);
115
116 boost::compute::sort(vector.begin(), vector.end(), queue);
117 BOOST_CHECK(boost::compute::is_sorted(vector.begin(), vector.end(), queue) == true);
118 CHECK_RANGE_EQUAL(short_, 8, vector, (-2113, -456, -94, -4, 0, 152, 963, 31002));
119 }
120
BOOST_AUTO_TEST_CASE(sort_ushort_vector)121 BOOST_AUTO_TEST_CASE(sort_ushort_vector)
122 {
123 using boost::compute::ushort_;
124
125 ushort_ data[] = { 4, 152, 94, 963, 63202, 34560, 0, 2113 };
126 boost::compute::vector<ushort_> vector(data, data + 8, queue);
127 BOOST_CHECK_EQUAL(vector.size(), size_t(8));
128 BOOST_CHECK(boost::compute::is_sorted(vector.begin(), vector.end(), queue) == false);
129
130 boost::compute::sort(vector.begin(), vector.end(), queue);
131 BOOST_CHECK(boost::compute::is_sorted(vector.begin(), vector.end(), queue) == true);
132 CHECK_RANGE_EQUAL(ushort_, 8, vector, (0, 4, 94, 152, 963, 2113, 34560, 63202));
133 }
134
BOOST_AUTO_TEST_CASE(sort_int_vector)135 BOOST_AUTO_TEST_CASE(sort_int_vector)
136 {
137 int data[] = { -4, 152, -5000, 963, 75321, -456, 0, 1112 };
138 boost::compute::vector<int> vector(data, data + 8, queue);
139 BOOST_CHECK_EQUAL(vector.size(), size_t(8));
140 BOOST_CHECK(boost::compute::is_sorted(vector.begin(), vector.end(), queue) == false);
141
142 boost::compute::sort(vector.begin(), vector.end(), queue);
143 BOOST_CHECK(boost::compute::is_sorted(vector.begin(), vector.end(), queue) == true);
144 CHECK_RANGE_EQUAL(int, 8, vector, (-5000, -456, -4, 0, 152, 963, 1112, 75321));
145 }
146
BOOST_AUTO_TEST_CASE(sort_uint_vector)147 BOOST_AUTO_TEST_CASE(sort_uint_vector)
148 {
149 using boost::compute::uint_;
150
151 uint_ data[] = { 500, 1988, 123456, 562, 0, 4000000, 9852, 102030 };
152 boost::compute::vector<uint_> vector(data, data + 8, queue);
153 BOOST_CHECK_EQUAL(vector.size(), size_t(8));
154 BOOST_CHECK(boost::compute::is_sorted(vector.begin(), vector.end(), queue) == false);
155
156 boost::compute::sort(vector.begin(), vector.end(), queue);
157 BOOST_CHECK(boost::compute::is_sorted(vector.begin(), vector.end(), queue) == true);
158 CHECK_RANGE_EQUAL(uint_, 8, vector, (0, 500, 562, 1988, 9852, 102030, 123456, 4000000));
159 }
160
BOOST_AUTO_TEST_CASE(sort_long_vector)161 BOOST_AUTO_TEST_CASE(sort_long_vector)
162 {
163 using boost::compute::long_;
164
165 long_ data[] = { 500, 1988, 123456, 562, 0, 4000000, 9852, 102030 };
166 boost::compute::vector<long_> vector(data, data + 8, queue);
167 BOOST_CHECK_EQUAL(vector.size(), size_t(8));
168 BOOST_CHECK(boost::compute::is_sorted(vector.begin(), vector.end(), queue) == false);
169
170 boost::compute::sort(vector.begin(), vector.end(), queue);
171 BOOST_CHECK(boost::compute::is_sorted(vector.begin(), vector.end(), queue) == true);
172 CHECK_RANGE_EQUAL(long_, 8, vector, (0, 500, 562, 1988, 9852, 102030, 123456, 4000000));
173 }
174
BOOST_AUTO_TEST_CASE(sort_ulong_vector)175 BOOST_AUTO_TEST_CASE(sort_ulong_vector)
176 {
177 using boost::compute::ulong_;
178
179 ulong_ data[] = { 500, 1988, 123456, 562, 0, 4000000, 9852, 102030 };
180 boost::compute::vector<ulong_> vector(data, data + 8, queue);
181 BOOST_CHECK_EQUAL(vector.size(), size_t(8));
182 BOOST_CHECK(boost::compute::is_sorted(vector.begin(), vector.end(), queue) == false);
183
184 boost::compute::sort(vector.begin(), vector.end(), queue);
185 BOOST_CHECK(boost::compute::is_sorted(vector.begin(), vector.end(), queue) == true);
186 CHECK_RANGE_EQUAL(ulong_, 8, vector, (0, 500, 562, 1988, 9852, 102030, 123456, 4000000));
187 }
188
BOOST_AUTO_TEST_CASE(sort_float_vector)189 BOOST_AUTO_TEST_CASE(sort_float_vector)
190 {
191 float data[] = { -6023.0f, 152.5f, -63.0f, 1234567.0f, 11.2f,
192 -5000.1f, 0.0f, 14.0f, -8.25f, -0.0f };
193 boost::compute::vector<float> vector(data, data + 10, queue);
194 BOOST_CHECK_EQUAL(vector.size(), size_t(10));
195 BOOST_CHECK(boost::compute::is_sorted(vector.begin(), vector.end(), queue) == false);
196
197 boost::compute::sort(vector.begin(), vector.end(), queue);
198 BOOST_CHECK(boost::compute::is_sorted(vector.begin(), vector.end(), queue) == true);
199 CHECK_RANGE_EQUAL(
200 float, 10, vector,
201 (-6023.0f, -5000.1f, -63.0f, -8.25f, -0.0f, 0.0f, 11.2f, 14.0f, 152.5f, 1234567.0f)
202 );
203 }
204
BOOST_AUTO_TEST_CASE(sort_double_vector)205 BOOST_AUTO_TEST_CASE(sort_double_vector)
206 {
207 if(!device.supports_extension("cl_khr_fp64")){
208 std::cout << "skipping test: device does not support double" << std::endl;
209 return;
210 }
211
212 double data[] = { -6023.0, 152.5, -63.0, 1234567.0, 11.2,
213 -5000.1, 0.0, 14.0, -8.25, -0.0 };
214 boost::compute::vector<double> vector(data, data + 10, queue);
215 BOOST_CHECK_EQUAL(vector.size(), size_t(10));
216 BOOST_CHECK(boost::compute::is_sorted(vector.begin(), vector.end(), queue) == false);
217
218 boost::compute::sort(vector.begin(), vector.end(), queue);
219 BOOST_CHECK(boost::compute::is_sorted(vector.begin(), vector.end(), queue) == true);
220 CHECK_RANGE_EQUAL(
221 double, 10, vector,
222 (-6023.0, -5000.1, -63.0, -8.25, -0.0, 0.0, 11.2, 14.0, 152.5, 1234567.0)
223 );
224
225 }
226
BOOST_AUTO_TEST_CASE(reverse_sort_int_vector)227 BOOST_AUTO_TEST_CASE(reverse_sort_int_vector)
228 {
229 int data[] = { -4, 152, -5000, 963, 75321, -456, 0, 1112 };
230 boost::compute::vector<int> vector(data, data + 8, queue);
231 BOOST_CHECK_EQUAL(vector.size(), size_t(8));
232
233 boost::compute::sort(vector.begin(), vector.end(),
234 boost::compute::greater<int>(), queue);
235 CHECK_RANGE_EQUAL(int, 8, vector, (75321, 1112, 963, 152, 0, -4, -456, -5000));
236 }
237
BOOST_AUTO_TEST_CASE(sort_vectors_by_length)238 BOOST_AUTO_TEST_CASE(sort_vectors_by_length)
239 {
240 using boost::compute::float2_;
241 using boost::compute::lambda::_1;
242 using boost::compute::lambda::_2;
243
244 float data[] = { 1.0f, 0.2f,
245 1.3f, 1.0f,
246 6.7f, 0.0f,
247 5.2f, 3.4f,
248 1.4f, 1.4f };
249
250 // create vector on device containing vectors
251 boost::compute::vector<float2_> vector(
252 reinterpret_cast<float2_ *>(data),
253 reinterpret_cast<float2_ *>(data) + 5,
254 queue
255 );
256
257 // sort vectors by length
258 boost::compute::sort(
259 vector.begin(),
260 vector.end(),
261 length(_1) < length(_2),
262 queue
263 );
264
265 // copy sorted values back to host
266 boost::compute::copy(
267 vector.begin(),
268 vector.end(),
269 reinterpret_cast<float2_ *>(data),
270 queue
271 );
272
273 // check values
274 BOOST_CHECK_EQUAL(data[0], 1.0f);
275 BOOST_CHECK_EQUAL(data[1], 0.2f);
276 BOOST_CHECK_EQUAL(data[2], 1.3f);
277 BOOST_CHECK_EQUAL(data[3], 1.0f);
278 BOOST_CHECK_EQUAL(data[4], 1.4f);
279 BOOST_CHECK_EQUAL(data[5], 1.4f);
280 BOOST_CHECK_EQUAL(data[6], 5.2f);
281 BOOST_CHECK_EQUAL(data[7], 3.4f);
282 BOOST_CHECK_EQUAL(data[8], 6.7f);
283 BOOST_CHECK_EQUAL(data[9], 0.0f);
284 }
285
BOOST_AUTO_TEST_CASE(sort_host_vector)286 BOOST_AUTO_TEST_CASE(sort_host_vector)
287 {
288 int data[] = { 5, 2, 3, 6, 7, 4, 0, 1 };
289 std::vector<int> vector(data, data + 8);
290 boost::compute::sort(vector.begin(), vector.end(), queue);
291 CHECK_RANGE_EQUAL(int, 8, vector, (0, 1, 2, 3, 4, 5, 6, 7));
292 }
293
BOOST_AUTO_TEST_CASE(sort_custom_struct)294 BOOST_AUTO_TEST_CASE(sort_custom_struct)
295 {
296 // function to compare particles by their x-coordinate
297 BOOST_COMPUTE_FUNCTION(bool, sort_by_x, (Particle a, Particle b),
298 {
299 return a.x < b.x;
300 });
301
302 std::vector<Particle> particles;
303 particles.push_back(Particle(0.1f, 0.f));
304 particles.push_back(Particle(-0.4f, 0.f));
305 particles.push_back(Particle(10.0f, 0.f));
306 particles.push_back(Particle(0.001f, 0.f));
307
308 boost::compute::vector<Particle> vector(4, context);
309 boost::compute::copy(particles.begin(), particles.end(), vector.begin(), queue);
310 BOOST_CHECK_EQUAL(vector.size(), size_t(4));
311 BOOST_CHECK(
312 boost::compute::is_sorted(vector.begin(), vector.end(),
313 sort_by_x, queue) == false
314 );
315
316 boost::compute::sort(vector.begin(), vector.end(), sort_by_x, queue);
317 BOOST_CHECK(
318 boost::compute::is_sorted(vector.begin(), vector.end(),
319 sort_by_x, queue) == true
320 );
321 boost::compute::copy(vector.begin(), vector.end(), particles.begin(), queue);
322 BOOST_CHECK_CLOSE(particles[0].x, -0.4f, 0.1);
323 BOOST_CHECK_CLOSE(particles[1].x, 0.001f, 0.1);
324 BOOST_CHECK_CLOSE(particles[2].x, 0.1f, 0.1);
325 BOOST_CHECK_CLOSE(particles[3].x, 10.0f, 0.1);
326 }
327
BOOST_AUTO_TEST_CASE(sort_int2)328 BOOST_AUTO_TEST_CASE(sort_int2)
329 {
330 using bc::int2_;
331
332 BOOST_COMPUTE_FUNCTION(bool, sort_int2, (int2_ a, int2_ b),
333 {
334 return a.x < b.x;
335 });
336
337 const size_t size = 100;
338 std::vector<int2_> host(size, int2_(0, 0));
339 host[0] = int2_(100.f, 0.f);
340 host[size/4] = int2_(20.f, 0.f);
341 host[(size*3)/4] = int2_(9.f, 0.f);
342 host[size-3] = int2_(-10.0f, 0.f);
343 host[size/2+1] = int2_(-10.0f, -1.f);
344
345 boost::compute::vector<int2_> vector(size, context);
346 boost::compute::copy(host.begin(), host.end(), vector.begin(), queue);
347 BOOST_CHECK_EQUAL(vector.size(), size);
348 BOOST_CHECK(
349 boost::compute::is_sorted(vector.begin(), vector.end(),
350 sort_int2, queue) == false
351 );
352
353 boost::compute::sort(vector.begin(), vector.end(), sort_int2, queue);
354 BOOST_CHECK(
355 boost::compute::is_sorted(vector.begin(), vector.end(),
356 sort_int2, queue) == true
357 );
358 boost::compute::copy(vector.begin(), vector.end(), host.begin(), queue);
359 BOOST_CHECK_CLOSE(host[0][0], -10.f, 0.1);
360 BOOST_CHECK_CLOSE(host[1][0], -10.f, 0.1);
361 BOOST_CHECK_CLOSE(host[(size - 3)][0], 9.f, 0.1);
362 BOOST_CHECK_CLOSE(host[(size - 2)][0], 20.f, 0.1);
363 BOOST_CHECK_CLOSE(host[(size - 1)][0], 100.f, 0.1);
364 BOOST_CHECK_NE(host[0], host[1]);
365 }
366
367 BOOST_AUTO_TEST_SUITE_END()
368