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 TestBinarySearch
12#include <boost/test/unit_test.hpp>
13
14#include <iterator>
15
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>
22
23#include "context_setup.hpp"
24
25BOOST_AUTO_TEST_CASE(binary_search_int)
26{
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(value: 4, queue); last++;
33 last.write(value: 4, queue); last++;
34 last.write(value: 5, queue); last++;
35 first = last;
36 last = first + 127;
37 boost::compute::fill(first, last, 7, queue);
38 first = last;
39 last = vector.end() - 1;
40 boost::compute::fill(first, last, 9, queue);
41 last.write(value: 10, queue);
42 queue.finish();
43
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);
53}
54
55BOOST_AUTO_TEST_CASE(range_bounds_int)
56{
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, value: int(2), queue);
62 last.write(value: 4, queue); last++; // 1024
63 last.write(value: 4, queue); last++; // 1025
64 last.write(value: 5, queue); last++; // 1026
65 first = last;
66 last = first + 127;
67 boost::compute::fill(first, last, value: 7, queue);
68 first = last;
69 last = vector.end() - 1;
70 boost::compute::fill(first, last, value: 9, queue);
71 last.write(value: 10, queue);
72 queue.finish();
73
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());
76
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);
79
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);
82
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);
85
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);
88
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);
91
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));
94
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);
97
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());
100}
101
102BOOST_AUTO_TEST_SUITE_END()
103

source code of boost/libs/compute/test/test_binary_search.cpp