1// Copyright (C) 2001 Free Software Foundation, Inc.
2//
3// This file is part of the GNU ISO C++ Library.  This library is free
4// software; you can redistribute it and/or modify it under the
5// terms of the GNU General Public License as published by the
6// Free Software Foundation; either version 2, or (at your option)
7// any later version.
8
9// This library is distributed in the hope that it will be useful,
10// but WITHOUT ANY WARRANTY; without even the implied warranty of
11// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
12// GNU General Public License for more details.
13
14// You should have received a copy of the GNU General Public License along
15// with this library; see the file COPYING.  If not, write to the Free
16// Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
17// USA.
18
19// 25.3.3 [lib.alg.binary.search] Binary search algorithms.
20
21#include <algorithm>
22#include <testsuite_hooks.h>
23
24bool test = true;
25
26const int A[] = {1, 2, 3, 3, 3, 5, 8};
27const int C[] = {8, 5, 3, 3, 3, 2, 1};
28const int N = sizeof(A) / sizeof(int);
29
30// A comparison, equalivalent to std::greater<int> without the
31// dependency on <functional>.
32
33struct gt
34{
35    bool
36    operator()(const int& x, const int& y) const
37    { return x > y; }
38};
39
40// Each test performs general-case, bookend, not-found condition,
41// and predicate functional checks.
42
43// 25.3.3.1 lower_bound, with and without comparison predicate
44void
45test01()
46{
47    using std::lower_bound;
48
49    const int first = A[0];
50    const int last = A[N - 1];
51
52    const int* p = lower_bound(A, A + N, 3);
53    VERIFY(p == A + 2);
54
55    const int* q = lower_bound(A, A + N, first);
56    VERIFY(q == A + 0);
57
58    const int* r = lower_bound(A, A + N, last);
59    VERIFY(r == A + N - 1);
60
61    const int* s = lower_bound(A, A + N, 4);
62    VERIFY(s == A + 5);
63
64    const int* t = lower_bound(C, C + N, 3, gt());
65    VERIFY(t == C + 2);
66
67    const int* u = lower_bound(C, C + N, first, gt());
68    VERIFY(u == C + N - 1);
69
70    const int* v = lower_bound(C, C + N, last, gt());
71    VERIFY(v == C + 0);
72
73    const int* w = lower_bound(C, C + N, 4, gt());
74    VERIFY(w == C + 2);
75}
76
77// 25.3.3.2 upper_bound, with and without comparison predicate
78void
79test02()
80{
81    using std::upper_bound;
82
83    const int first = A[0];
84    const int last = A[N - 1];
85
86    const int* p = upper_bound(A, A + N, 3);
87    VERIFY(p == A + 5);
88
89    const int* q = upper_bound(A, A + N, first);
90    VERIFY(q == A + 1);
91
92    const int* r = upper_bound(A, A + N, last);
93    VERIFY(r == A + N);
94
95    const int* s = upper_bound(A, A + N, 4);
96    VERIFY(s == A + 5);
97
98    const int* t = upper_bound(C, C + N, 3, gt());
99    VERIFY(t == C + 5);
100
101    const int* u = upper_bound(C, C + N, first, gt());
102    VERIFY(u == C + N);
103
104    const int* v = upper_bound(C, C + N, last, gt());
105    VERIFY(v == C + 1);
106
107    const int* w = upper_bound(C, C + N, 4, gt());
108    VERIFY(w == C + 2);
109}
110
111// 25.3.3.3 equal_range, with and without comparison predicate
112void
113test03()
114{
115    using std::equal_range;
116    typedef std::pair<const int*, const int*> Ipair;
117
118    const int first = A[0];
119    const int last = A[N - 1];
120
121    Ipair p = equal_range(A, A + N, 3);
122    VERIFY(p.first == A + 2);
123    VERIFY(p.second == A + 5);
124
125    Ipair q = equal_range(A, A + N, first);
126    VERIFY(q.first == A + 0);
127    VERIFY(q.second == A + 1);
128
129    Ipair r = equal_range(A, A + N, last);
130    VERIFY(r.first == A + N - 1);
131    VERIFY(r.second == A + N);
132
133    Ipair s = equal_range(A, A + N, 4);
134    VERIFY(s.first == A + 5);
135    VERIFY(s.second == A + 5);
136
137    Ipair t = equal_range(C, C + N, 3, gt());
138    VERIFY(t.first == C + 2);
139    VERIFY(t.second == C + 5);
140
141    Ipair u = equal_range(C, C + N, first, gt());
142    VERIFY(u.first == C + N - 1);
143    VERIFY(u.second == C + N);
144
145    Ipair v = equal_range(C, C + N, last, gt());
146    VERIFY(v.first == C + 0);
147    VERIFY(v.second == C + 1);
148
149    Ipair w = equal_range(C, C + N, 4, gt());
150    VERIFY(w.first == C + 2);
151    VERIFY(w.second == C + 2);
152}
153
154// 25.3.3.4 binary_search, with and without comparison predicate
155void
156test04()
157{
158    using std::binary_search;
159
160    const int first = A[0];
161    const int last = A[N - 1];
162
163    VERIFY(binary_search(A, A + N, 5));
164    VERIFY(binary_search(A, A + N, first));
165    VERIFY(binary_search(A, A + N, last));
166    VERIFY(!binary_search(A, A + N, 4));
167
168    VERIFY(binary_search(C, C + N, 5, gt()));
169    VERIFY(binary_search(C, C + N, first, gt()));
170    VERIFY(binary_search(C, C + N, last, gt()));
171    VERIFY(!binary_search(C, C + N, 4, gt()));
172}
173
174int
175main(int argc, char* argv[])
176{
177    test01();
178    test02();
179    test03();
180    test04();
181
182    return !test;
183}
184