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 TestNthElement
12 #include <boost/test/unit_test.hpp>
13
14 #include <boost/compute/command_queue.hpp>
15 #include <boost/compute/algorithm/copy_n.hpp>
16 #include <boost/compute/algorithm/is_partitioned.hpp>
17 #include <boost/compute/algorithm/nth_element.hpp>
18 #include <boost/compute/algorithm/partition_point.hpp>
19 #include <boost/compute/container/vector.hpp>
20
21 #include "check_macros.hpp"
22 #include "context_setup.hpp"
23
BOOST_AUTO_TEST_CASE(nth_element_int)24 BOOST_AUTO_TEST_CASE(nth_element_int)
25 {
26 int data[] = { 9, 15, 1, 4, 9, 9, 4, 15, 12, 1 };
27 boost::compute::vector<int> vector(10, context);
28
29 boost::compute::copy_n(data, 10, vector.begin(), queue);
30
31 boost::compute::nth_element(
32 vector.begin(), vector.begin() + 5, vector.end(), queue
33 );
34
35 BOOST_CHECK_EQUAL(vector[5], 9);
36 BOOST_VERIFY(boost::compute::is_partitioned(
37 vector.begin(), vector.end(), boost::compute::_1 <= 9, queue
38 ));
39 BOOST_VERIFY(boost::compute::partition_point(
40 vector.begin(), vector.end(), boost::compute::_1 <= 9, queue
41 ) > vector.begin() + 5);
42
43 boost::compute::copy_n(data, 10, vector.begin(), queue);
44
45 boost::compute::nth_element(
46 vector.begin(), vector.end(), vector.end(), queue
47 );
48 CHECK_RANGE_EQUAL(int, 10, vector, (9, 15, 1, 4, 9, 9, 4, 15, 12, 1));
49 }
50
BOOST_AUTO_TEST_CASE(nth_element_median)51 BOOST_AUTO_TEST_CASE(nth_element_median)
52 {
53 int data[] = { 5, 6, 4, 3, 2, 6, 7, 9, 3 };
54 boost::compute::vector<int> v(9, context);
55 boost::compute::copy_n(data, 9, v.begin(), queue);
56
57 boost::compute::nth_element(v.begin(), v.begin() + 4, v.end(), queue);
58
59 BOOST_CHECK_EQUAL(v[4], 5);
60 BOOST_VERIFY(boost::compute::is_partitioned(
61 v.begin(), v.end(), boost::compute::_1 <= 5, queue
62 ));
63 BOOST_VERIFY(boost::compute::partition_point(
64 v.begin(), v.end(), boost::compute::_1 <= 5, queue
65 ) > v.begin() + 4);
66 }
67
BOOST_AUTO_TEST_CASE(nth_element_second_largest)68 BOOST_AUTO_TEST_CASE(nth_element_second_largest)
69 {
70 int data[] = { 5, 6, 4, 3, 2, 6, 7, 9, 3 };
71 boost::compute::vector<int> v(9, context);
72 boost::compute::copy_n(data, 9, v.begin(), queue);
73
74 boost::compute::nth_element(v.begin(), v.begin() + 1, v.end(), queue);
75
76 BOOST_CHECK_EQUAL(v[1], 3);
77 BOOST_VERIFY(boost::compute::is_partitioned(
78 v.begin(), v.end(), boost::compute::_1 <= 3, queue
79 ));
80 BOOST_VERIFY(boost::compute::partition_point(
81 v.begin(), v.end(), boost::compute::_1 <= 3, queue
82 ) > v.begin() + 1);
83 }
84
BOOST_AUTO_TEST_CASE(nth_element_comparator)85 BOOST_AUTO_TEST_CASE(nth_element_comparator)
86 {
87 int data[] = { 9, 15, 1, 4, 9, 9, 4, 15, 12, 1 };
88 boost::compute::vector<int> vector(10, context);
89
90 boost::compute::less<int> less_than;
91
92 boost::compute::copy_n(data, 10, vector.begin(), queue);
93
94 boost::compute::nth_element(
95 vector.begin(), vector.begin() + 5, vector.end(), less_than, queue
96 );
97 BOOST_CHECK_EQUAL(vector[5], 9);
98 BOOST_VERIFY(boost::compute::is_partitioned(
99 vector.begin(), vector.end(), boost::compute::_1 <= 9, queue
100 ));
101 BOOST_VERIFY(boost::compute::partition_point(
102 vector.begin(), vector.end(), boost::compute::_1 <= 9, queue
103 ) > vector.begin() + 5);
104
105 boost::compute::copy_n(data, 10, vector.begin(), queue);
106
107 boost::compute::nth_element(
108 vector.begin(), vector.end(), vector.end(), less_than, queue
109 );
110 CHECK_RANGE_EQUAL(int, 10, vector, (9, 15, 1, 4, 9, 9, 4, 15, 12, 1));
111 }
112
113 BOOST_AUTO_TEST_SUITE_END()
114