1 //===----------------------------------------------------------------------===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is dual licensed under the MIT and the University of Illinois Open
6 // Source Licenses. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9
10 // <algorithm>
11
12 // template<ForwardIterator Iter, class T>
13 // requires HasLess<T, Iter::value_type>
14 // && HasLess<Iter::value_type, T>
15 // bool
16 // binary_search(Iter first, Iter last, const T& value);
17
18 #include <algorithm>
19 #include <vector>
20 #include <cassert>
21
22 #include "test_iterators.h"
23
24 template <class Iter, class T>
25 void
test(Iter first,Iter last,const T & value,bool x)26 test(Iter first, Iter last, const T& value, bool x)
27 {
28 assert(std::binary_search(first, last, value) == x);
29 }
30
31 template <class Iter>
32 void
test()33 test()
34 {
35 const unsigned N = 1000;
36 const unsigned M = 10;
37 std::vector<int> v(N);
38 int x = 0;
39 for (int i = 0; i < v.size(); ++i)
40 {
41 v[i] = x;
42 if (++x == M)
43 x = 0;
44 }
45 std::sort(v.begin(), v.end());
46 for (x = 0; x < M; ++x)
47 test(Iter(v.data()), Iter(v.data()+v.size()), x, true);
48 test(Iter(v.data()), Iter(v.data()+v.size()), -1, false);
49 test(Iter(v.data()), Iter(v.data()+v.size()), M, false);
50 }
51
main()52 int main()
53 {
54 int d[] = {0, 2, 4, 6};
55 for (int* e = d; e <= d+4; ++e)
56 for (int x = -1; x <= 7; ++x)
57 test(d, e, x, (x % 2 == 0) && ((e-d)*2 > x));
58
59 test<forward_iterator<const int*> >();
60 test<bidirectional_iterator<const int*> >();
61 test<random_access_iterator<const int*> >();
62 test<const int*>();
63 }
64