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 TestInsertionSort
12 #include <boost/test/unit_test.hpp>
13
14 #include <boost/compute/system.hpp>
15 #include <boost/compute/algorithm/is_sorted.hpp>
16 #include <boost/compute/algorithm/detail/insertion_sort.hpp>
17 #include <boost/compute/container/vector.hpp>
18
19 #include "check_macros.hpp"
20 #include "context_setup.hpp"
21
22 namespace bc = boost::compute;
23
BOOST_AUTO_TEST_CASE(sort_char_vector)24 BOOST_AUTO_TEST_CASE(sort_char_vector)
25 {
26 using boost::compute::char_;
27
28 char_ data[] = { 'c', 'a', '0', '7', 'B', 'F', '\0', '$' };
29 boost::compute::vector<char_> vector(data, data + 8, queue);
30 BOOST_CHECK_EQUAL(vector.size(), size_t(8));
31 BOOST_CHECK(boost::compute::is_sorted(vector.begin(), vector.end(), queue) == false);
32
33 boost::compute::detail::serial_insertion_sort(vector.begin(), vector.end(), queue);
34 BOOST_CHECK(boost::compute::is_sorted(vector.begin(), vector.end(), queue) == true);
35 CHECK_RANGE_EQUAL(char_, 8, vector, ('\0', '$', '0', '7', 'B', 'F', 'a', 'c'));
36 }
37
BOOST_AUTO_TEST_CASE(sort_uchar_vector)38 BOOST_AUTO_TEST_CASE(sort_uchar_vector)
39 {
40 using boost::compute::uchar_;
41
42 uchar_ data[] = { 0x12, 0x00, 0xFF, 0xB4, 0x80, 0x32, 0x64, 0xA2 };
43 boost::compute::vector<uchar_> vector(data, data + 8, queue);
44 BOOST_CHECK_EQUAL(vector.size(), size_t(8));
45 BOOST_CHECK(boost::compute::is_sorted(vector.begin(), vector.end(), queue) == false);
46
47 boost::compute::detail::serial_insertion_sort(vector.begin(), vector.end(), queue);
48 BOOST_CHECK(boost::compute::is_sorted(vector.begin(), vector.end(), queue) == true);
49 CHECK_RANGE_EQUAL(uchar_, 8, vector, (0x00, 0x12, 0x32, 0x64, 0x80, 0xA2, 0xB4, 0xFF));
50 }
51
BOOST_AUTO_TEST_CASE(sort_short_vector)52 BOOST_AUTO_TEST_CASE(sort_short_vector)
53 {
54 using boost::compute::short_;
55
56 short_ data[] = { -4, 152, -94, 963, 31002, -456, 0, -2113 };
57 boost::compute::vector<short_> vector(data, data + 8, queue);
58 BOOST_CHECK_EQUAL(vector.size(), size_t(8));
59 BOOST_CHECK(boost::compute::is_sorted(vector.begin(), vector.end(), queue) == false);
60
61 boost::compute::detail::serial_insertion_sort(vector.begin(), vector.end(), queue);
62 BOOST_CHECK(boost::compute::is_sorted(vector.begin(), vector.end(), queue) == true);
63 CHECK_RANGE_EQUAL(short_, 8, vector, (-2113, -456, -94, -4, 0, 152, 963, 31002));
64 }
65
BOOST_AUTO_TEST_CASE(sort_ushort_vector)66 BOOST_AUTO_TEST_CASE(sort_ushort_vector)
67 {
68 using boost::compute::ushort_;
69
70 ushort_ data[] = { 4, 152, 94, 963, 63202, 34560, 0, 2113 };
71 boost::compute::vector<ushort_> vector(data, data + 8, queue);
72 BOOST_CHECK_EQUAL(vector.size(), size_t(8));
73 BOOST_CHECK(boost::compute::is_sorted(vector.begin(), vector.end(), queue) == false);
74
75 boost::compute::detail::serial_insertion_sort(vector.begin(), vector.end(), queue);
76 BOOST_CHECK(boost::compute::is_sorted(vector.begin(), vector.end(), queue) == true);
77 CHECK_RANGE_EQUAL(ushort_, 8, vector, (0, 4, 94, 152, 963, 2113, 34560, 63202));
78 }
79
BOOST_AUTO_TEST_CASE(sort_int_vector)80 BOOST_AUTO_TEST_CASE(sort_int_vector)
81 {
82 int data[] = { -4, 152, -5000, 963, 75321, -456, 0, 1112 };
83 boost::compute::vector<int> vector(data, data + 8, queue);
84 BOOST_CHECK_EQUAL(vector.size(), size_t(8));
85 BOOST_CHECK(boost::compute::is_sorted(vector.begin(), vector.end(), queue) == false);
86
87 boost::compute::detail::serial_insertion_sort(vector.begin(), vector.end(), queue);
88 BOOST_CHECK(boost::compute::is_sorted(vector.begin(), vector.end(), queue) == true);
89 CHECK_RANGE_EQUAL(int, 8, vector, (-5000, -456, -4, 0, 152, 963, 1112, 75321));
90 }
91
BOOST_AUTO_TEST_CASE(sort_uint_vector)92 BOOST_AUTO_TEST_CASE(sort_uint_vector)
93 {
94 using boost::compute::uint_;
95
96 uint_ data[] = { 500, 1988, 123456, 562, 0, 4000000, 9852, 102030 };
97 boost::compute::vector<uint_> vector(data, data + 8, queue);
98 BOOST_CHECK_EQUAL(vector.size(), size_t(8));
99 BOOST_CHECK(boost::compute::is_sorted(vector.begin(), vector.end(), queue) == false);
100
101 boost::compute::detail::serial_insertion_sort(vector.begin(), vector.end(), queue);
102 BOOST_CHECK(boost::compute::is_sorted(vector.begin(), vector.end(), queue) == true);
103 CHECK_RANGE_EQUAL(uint_, 8, vector, (0, 500, 562, 1988, 9852, 102030, 123456, 4000000));
104 }
105
BOOST_AUTO_TEST_CASE(sort_long_vector)106 BOOST_AUTO_TEST_CASE(sort_long_vector)
107 {
108 using boost::compute::long_;
109
110 long_ data[] = { 500, 1988, 123456, 562, 0, 4000000, 9852, 102030 };
111 boost::compute::vector<long_> vector(data, data + 8, queue);
112 BOOST_CHECK_EQUAL(vector.size(), size_t(8));
113 BOOST_CHECK(boost::compute::is_sorted(vector.begin(), vector.end(), queue) == false);
114
115 boost::compute::detail::serial_insertion_sort(vector.begin(), vector.end(), queue);
116 BOOST_CHECK(boost::compute::is_sorted(vector.begin(), vector.end(), queue) == true);
117 CHECK_RANGE_EQUAL(long_, 8, vector, (0, 500, 562, 1988, 9852, 102030, 123456, 4000000));
118 }
119
BOOST_AUTO_TEST_CASE(sort_ulong_vector)120 BOOST_AUTO_TEST_CASE(sort_ulong_vector)
121 {
122 using boost::compute::ulong_;
123
124 ulong_ data[] = { 500, 1988, 123456, 562, 0, 4000000, 9852, 102030 };
125 boost::compute::vector<ulong_> vector(data, data + 8, queue);
126 BOOST_CHECK_EQUAL(vector.size(), size_t(8));
127 BOOST_CHECK(boost::compute::is_sorted(vector.begin(), vector.end(), queue) == false);
128
129 boost::compute::detail::serial_insertion_sort(vector.begin(), vector.end(), queue);
130 BOOST_CHECK(boost::compute::is_sorted(vector.begin(), vector.end(), queue) == true);
131 CHECK_RANGE_EQUAL(ulong_, 8, vector, (0, 500, 562, 1988, 9852, 102030, 123456, 4000000));
132 }
133
BOOST_AUTO_TEST_CASE(sort_float_vector)134 BOOST_AUTO_TEST_CASE(sort_float_vector)
135 {
136 float data[] = { -6023.0f, 152.5f, -63.0f, 1234567.0f, 11.2f,
137 -5000.1f, 0.0f, 14.0f, -8.25f, -0.0f };
138 boost::compute::vector<float> vector(data, data + 10, queue);
139 BOOST_CHECK_EQUAL(vector.size(), size_t(10));
140 BOOST_CHECK(boost::compute::is_sorted(vector.begin(), vector.end(), queue) == false);
141
142 boost::compute::detail::serial_insertion_sort(vector.begin(), vector.end(), queue);
143 BOOST_CHECK(boost::compute::is_sorted(vector.begin(), vector.end(), queue) == true);
144 CHECK_RANGE_EQUAL(
145 float, 10, vector,
146 (-6023.0f, -5000.1f, -63.0f, -8.25f, -0.0f, 0.0f, 11.2f, 14.0f, 152.5f, 1234567.0f)
147 );
148 }
149
BOOST_AUTO_TEST_CASE(sort_double_vector)150 BOOST_AUTO_TEST_CASE(sort_double_vector)
151 {
152 if(!device.supports_extension("cl_khr_fp64")){
153 std::cout << "skipping test: device does not support double" << std::endl;
154 return;
155 }
156
157 double data[] = { -6023.0, 152.5, -63.0, 1234567.0, 11.2,
158 -5000.1, 0.0, 14.0, -8.25, -0.0 };
159 boost::compute::vector<double> vector(data, data + 10, queue);
160 BOOST_CHECK_EQUAL(vector.size(), size_t(10));
161 BOOST_CHECK(boost::compute::is_sorted(vector.begin(), vector.end(), queue) == false);
162
163 boost::compute::detail::serial_insertion_sort(vector.begin(), vector.end(), queue);
164 BOOST_CHECK(boost::compute::is_sorted(vector.begin(), vector.end(), queue) == true);
165 CHECK_RANGE_EQUAL(
166 double, 10, vector,
167 (-6023.0, -5000.1, -63.0, -8.25, -0.0, 0.0, 11.2, 14.0, 152.5, 1234567.0)
168 );
169 }
170
171 BOOST_AUTO_TEST_SUITE_END()
172