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 TestSortByKey
12 #include <boost/test/unit_test.hpp>
13
14 #include <boost/compute/system.hpp>
15 #include <boost/compute/algorithm/sort_by_key.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 custom_struct
21 {
22 boost::compute::int_ x;
23 boost::compute::int_ y;
24 boost::compute::float2_ zw;
25 };
26
27 BOOST_COMPUTE_ADAPT_STRUCT(custom_struct, custom_struct, (x, y, zw))
28
29 #include "check_macros.hpp"
30 #include "context_setup.hpp"
31
32 namespace compute = boost::compute;
33
34 // test trivial sorting of zero element vectors
BOOST_AUTO_TEST_CASE(sort_int_0)35 BOOST_AUTO_TEST_CASE(sort_int_0)
36 {
37 compute::vector<int> keys(context);
38 compute::vector<int> values(context);
39 BOOST_CHECK_EQUAL(keys.size(), size_t(0));
40 BOOST_CHECK_EQUAL(values.size(), size_t(0));
41 BOOST_CHECK(compute::is_sorted(keys.begin(), keys.end()) == true);
42 BOOST_CHECK(compute::is_sorted(values.begin(), values.end()) == true);
43 compute::sort_by_key(keys.begin(), keys.end(), values.begin(), queue);
44 }
45
46 // test trivial sorting of one element vectors
BOOST_AUTO_TEST_CASE(sort_int_1)47 BOOST_AUTO_TEST_CASE(sort_int_1)
48 {
49 int keys_data[] = { 11 };
50 int values_data[] = { 100 };
51
52 compute::vector<int> keys(keys_data, keys_data + 1, queue);
53 compute::vector<int> values(values_data, values_data + 1, queue);
54
55 BOOST_CHECK(compute::is_sorted(keys.begin(), keys.end(), queue) == true);
56 BOOST_CHECK(compute::is_sorted(values.begin(), values.end(), queue) == true);
57
58 compute::sort_by_key(keys.begin(), keys.end(), values.begin(), queue);
59 }
60
61 // test trivial sorting of two element vectors
BOOST_AUTO_TEST_CASE(sort_int_2)62 BOOST_AUTO_TEST_CASE(sort_int_2)
63 {
64 int keys_data[] = { 4, 2 };
65 int values_data[] = { 42, 24 };
66
67 compute::vector<int> keys(keys_data, keys_data + 2, queue);
68 compute::vector<int> values(values_data, values_data + 2, queue);
69
70 BOOST_CHECK(compute::is_sorted(keys.begin(), keys.end(), queue) == false);
71 BOOST_CHECK(compute::is_sorted(values.begin(), values.end(), queue) == false);
72
73 compute::sort_by_key(keys.begin(), keys.end(), values.begin(), queue);
74
75 BOOST_CHECK(compute::is_sorted(keys.begin(), keys.end(), queue) == true);
76 BOOST_CHECK(compute::is_sorted(values.begin(), values.end(), queue) == true);
77 }
78
BOOST_AUTO_TEST_CASE(sort_char_by_int)79 BOOST_AUTO_TEST_CASE(sort_char_by_int)
80 {
81 int keys_data[] = { 6, 2, 1, 3, 4, 7, 5, 0 };
82 compute::char_ values_data[] = { 'g', 'c', 'b', 'd', 'e', 'h', 'f', 'a' };
83
84 compute::vector<int> keys(keys_data, keys_data + 8, queue);
85 compute::vector<compute::char_> values(values_data, values_data + 8, queue);
86
87 compute::sort_by_key(keys.begin(), keys.end(), values.begin(), queue);
88
89 CHECK_RANGE_EQUAL(int, 8, keys, (0, 1, 2, 3, 4, 5, 6, 7));
90 CHECK_RANGE_EQUAL(compute::char_, 8, values, ('a', 'b', 'c', 'd', 'e', 'f', 'g', 'h'));
91 }
92
BOOST_AUTO_TEST_CASE(sort_int_and_float)93 BOOST_AUTO_TEST_CASE(sort_int_and_float)
94 {
95 int n = 1024;
96 std::vector<int> host_keys(n);
97 std::vector<float> host_values(n);
98 for(int i = 0; i < n; i++){
99 host_keys[i] = n - i;
100 host_values[i] = (n - i) / 2.f;
101 }
102
103 compute::vector<int> keys(host_keys.begin(), host_keys.end(), queue);
104 compute::vector<float> values(host_values.begin(), host_values.end(), queue);
105
106 BOOST_CHECK(compute::is_sorted(keys.begin(), keys.end(), queue) == false);
107 BOOST_CHECK(compute::is_sorted(values.begin(), values.end(), queue) == false);
108
109 compute::sort_by_key(keys.begin(), keys.end(), values.begin(), queue);
110
111 BOOST_CHECK(compute::is_sorted(keys.begin(), keys.end(), queue) == true);
112 BOOST_CHECK(compute::is_sorted(values.begin(), values.end(), queue) == true);
113 }
114
BOOST_AUTO_TEST_CASE(sort_int_and_float_custom_comparison_func)115 BOOST_AUTO_TEST_CASE(sort_int_and_float_custom_comparison_func)
116 {
117 using boost::compute::int_;
118 using boost::compute::float_;
119
120 int n = 1024;
121 std::vector<int_> host_keys(n);
122 std::vector<float_> host_values(n);
123 for(int i = 0; i < n; i++){
124 host_keys[i] = n - i;
125 host_values[i] = (n - i) / 2.f;
126 }
127
128 BOOST_COMPUTE_FUNCTION(bool, sort_int, (int_ a, int_ b),
129 {
130 return a < b;
131 });
132
133 compute::vector<int_> keys(host_keys.begin(), host_keys.end(), queue);
134 compute::vector<float_> values(host_values.begin(), host_values.end(), queue);
135
136 BOOST_CHECK(compute::is_sorted(keys.begin(), keys.end(), sort_int, queue) == false);
137 BOOST_CHECK(compute::is_sorted(values.begin(), values.end(), queue) == false);
138
139 compute::sort_by_key(keys.begin(), keys.end(), values.begin(), sort_int, queue);
140
141 BOOST_CHECK(compute::is_sorted(keys.begin(), keys.end(), sort_int, queue) == true);
142 BOOST_CHECK(compute::is_sorted(values.begin(), values.end(), queue) == true);
143 }
144
BOOST_AUTO_TEST_CASE(sort_int_and_float2)145 BOOST_AUTO_TEST_CASE(sort_int_and_float2)
146 {
147 using boost::compute::int_;
148 using boost::compute::float2_;
149
150 int n = 1024;
151 std::vector<int_> host_keys(n);
152 std::vector<float2_> host_values(n);
153 for(int i = 0; i < n; i++){
154 host_keys[i] = n - i;
155 host_values[i] = float2_((n - i) / 2.f);
156 }
157
158 BOOST_COMPUTE_FUNCTION(bool, sort_float2, (float2_ a, float2_ b),
159 {
160 return a.x < b.x;
161 });
162
163 compute::vector<int_> keys(host_keys.begin(), host_keys.end(), queue);
164 compute::vector<float2_> values(host_values.begin(), host_values.end(), queue);
165
166 BOOST_CHECK(compute::is_sorted(keys.begin(), keys.end(), queue) == false);
167 BOOST_CHECK(compute::is_sorted(values.begin(), values.end(), sort_float2, queue) == false);
168
169 compute::sort_by_key(keys.begin(), keys.end(), values.begin(), queue);
170
171 BOOST_CHECK(compute::is_sorted(keys.begin(), keys.end(), queue) == true);
172 BOOST_CHECK(compute::is_sorted(values.begin(), values.end(), sort_float2, queue) == true);
173 }
174
BOOST_AUTO_TEST_CASE(sort_custom_struct_by_int)175 BOOST_AUTO_TEST_CASE(sort_custom_struct_by_int)
176 {
177 using boost::compute::int_;
178 using boost::compute::float2_;
179
180 int_ n = 1024;
181 std::vector<int_> host_keys(n);
182 std::vector<custom_struct> host_values(n);
183 for(int_ i = 0; i < n; i++){
184 host_keys[i] = n - i;
185 host_values[i].x = n - i;
186 host_values[i].y = n - i;
187 host_values[i].zw = float2_((n - i) / 0.5f);
188 }
189
190 BOOST_COMPUTE_FUNCTION(bool, sort_custom_struct, (custom_struct a, custom_struct b),
191 {
192 return a.x < b.x;
193 });
194
195 compute::vector<int_> keys(host_keys.begin(), host_keys.end(), queue);
196 compute::vector<custom_struct> values(host_values.begin(), host_values.end(), queue);
197
198 BOOST_CHECK(compute::is_sorted(keys.begin(), keys.end(), queue) == false);
199 BOOST_CHECK(compute::is_sorted(values.begin(), values.end(), sort_custom_struct, queue) == false);
200
201 compute::sort_by_key(keys.begin(), keys.end(), values.begin(), queue);
202
203 BOOST_CHECK(compute::is_sorted(keys.begin(), keys.end(), queue) == true);
204 BOOST_CHECK(compute::is_sorted(values.begin(), values.end(), sort_custom_struct, queue) == true);
205 }
206
207 BOOST_AUTO_TEST_SUITE_END()
208