]>
git.proxmox.com Git - ceph.git/blob - ceph/src/boost/libs/compute/test/test_binary_search.cpp
1 //---------------------------------------------------------------------------//
2 // Copyright (c) 2013 Kyle Lutz <kyle.r.lutz@gmail.com>
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
8 // See http://boostorg.github.com/compute for more information.
9 //---------------------------------------------------------------------------//
11 #define BOOST_TEST_MODULE TestBinarySearch
12 #include <boost/test/unit_test.hpp>
16 #include <boost/compute/command_queue.hpp>
17 #include <boost/compute/algorithm/binary_search.hpp>
18 #include <boost/compute/algorithm/fill.hpp>
19 #include <boost/compute/algorithm/lower_bound.hpp>
20 #include <boost/compute/algorithm/upper_bound.hpp>
21 #include <boost/compute/container/vector.hpp>
23 #include "context_setup.hpp"
25 BOOST_AUTO_TEST_CASE(binary_search_int
)
27 // test data = { 1, ..., 2, ..., 4, 4, 5, 7, ..., 9, ..., 10 }
28 boost::compute::vector
<int> vector(size_t(4096), int(1), queue
);
29 boost::compute::vector
<int>::iterator first
= vector
.begin() + 128;
30 boost::compute::vector
<int>::iterator last
= first
+ (1024 - 128);
31 boost::compute::fill(first
, last
, int(2), queue
);
32 last
.write(4, queue
); last
++;
33 last
.write(4, queue
); last
++;
34 last
.write(5, queue
); last
++;
37 boost::compute::fill(first
, last
, 7, queue
);
39 last
= vector
.end() - 1;
40 boost::compute::fill(first
, last
, 9, queue
);
41 last
.write(10, queue
);
44 BOOST_CHECK(boost::compute::binary_search(vector
.begin(), vector
.end(), int(0), queue
) == false);
45 BOOST_CHECK(boost::compute::binary_search(vector
.begin(), vector
.end(), int(1), queue
) == true);
46 BOOST_CHECK(boost::compute::binary_search(vector
.begin(), vector
.end(), int(2), queue
) == true);
47 BOOST_CHECK(boost::compute::binary_search(vector
.begin(), vector
.end(), int(3), queue
) == false);
48 BOOST_CHECK(boost::compute::binary_search(vector
.begin(), vector
.end(), int(4), queue
) == true);
49 BOOST_CHECK(boost::compute::binary_search(vector
.begin(), vector
.end(), int(5), queue
) == true);
50 BOOST_CHECK(boost::compute::binary_search(vector
.begin(), vector
.end(), int(6), queue
) == false);
51 BOOST_CHECK(boost::compute::binary_search(vector
.begin(), vector
.end(), int(7), queue
) == true);
52 BOOST_CHECK(boost::compute::binary_search(vector
.begin(), vector
.end(), int(8), queue
) == false);
55 BOOST_AUTO_TEST_CASE(range_bounds_int
)
57 // test data = { 1, ..., 2, ..., 4, 4, 5, 7, ..., 9, ..., 10 }
58 boost::compute::vector
<int> vector(size_t(4096), int(1), queue
);
59 boost::compute::vector
<int>::iterator first
= vector
.begin() + 128;
60 boost::compute::vector
<int>::iterator last
= first
+ (1024 - 128);
61 boost::compute::fill(first
, last
, int(2), queue
);
62 last
.write(4, queue
); last
++; // 1024
63 last
.write(4, queue
); last
++; // 1025
64 last
.write(5, queue
); last
++; // 1026
67 boost::compute::fill(first
, last
, 7, queue
);
69 last
= vector
.end() - 1;
70 boost::compute::fill(first
, last
, 9, queue
);
71 last
.write(10, queue
);
74 BOOST_CHECK(boost::compute::lower_bound(vector
.begin(), vector
.end(), int(0), queue
) == vector
.begin());
75 BOOST_CHECK(boost::compute::upper_bound(vector
.begin(), vector
.end(), int(0), queue
) == vector
.begin());
77 BOOST_CHECK(boost::compute::lower_bound(vector
.begin(), vector
.end(), int(1), queue
) == vector
.begin());
78 BOOST_CHECK(boost::compute::upper_bound(vector
.begin(), vector
.end(), int(1), queue
) == vector
.begin() + 128);
80 BOOST_CHECK(boost::compute::lower_bound(vector
.begin(), vector
.end(), int(2), queue
) == vector
.begin() + 128);
81 BOOST_CHECK(boost::compute::upper_bound(vector
.begin(), vector
.end(), int(2), queue
) == vector
.begin() + 1024);
83 BOOST_CHECK(boost::compute::lower_bound(vector
.begin(), vector
.end(), int(4), queue
) == vector
.begin() + 1024);
84 BOOST_CHECK(boost::compute::upper_bound(vector
.begin(), vector
.end(), int(4), queue
) == vector
.begin() + 1026);
86 BOOST_CHECK(boost::compute::lower_bound(vector
.begin(), vector
.end(), int(5), queue
) == vector
.begin() + 1026);
87 BOOST_CHECK(boost::compute::upper_bound(vector
.begin(), vector
.end(), int(5), queue
) == vector
.begin() + 1027);
89 BOOST_CHECK(boost::compute::lower_bound(vector
.begin(), vector
.end(), int(6), queue
) == vector
.begin() + 1027);
90 BOOST_CHECK(boost::compute::upper_bound(vector
.begin(), vector
.end(), int(6), queue
) == vector
.begin() + 1027);
92 BOOST_CHECK(boost::compute::lower_bound(vector
.begin(), vector
.end(), int(7), queue
) == vector
.begin() + 1027);
93 BOOST_CHECK(boost::compute::upper_bound(vector
.begin(), vector
.end(), int(7), queue
) == vector
.begin() + (1027 + 127));
95 BOOST_CHECK(boost::compute::lower_bound(vector
.begin(), vector
.end(), int(9), queue
) == vector
.begin() + (1027 + 127));
96 BOOST_CHECK(boost::compute::upper_bound(vector
.begin(), vector
.end(), int(9), queue
) == vector
.end() - 1);
98 BOOST_CHECK(boost::compute::lower_bound(vector
.begin(), vector
.end(), int(10), queue
) == vector
.end() - 1);
99 BOOST_CHECK(boost::compute::upper_bound(vector
.begin(), vector
.end(), int(10), queue
) == vector
.end());
102 BOOST_AUTO_TEST_SUITE_END()