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