1 // Copyright (C) 2001 Free Software Foundation, Inc.
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)
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.
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,
19 // 25.3.3 [lib.alg.binary.search] Binary search algorithms.
22 #include <testsuite_hooks.h>
24 bool test __attribute__((unused)) = true;
26 const int A[] = {1, 2, 3, 3, 3, 5, 8};
27 const int C[] = {8, 5, 3, 3, 3, 2, 1};
28 const int N = sizeof(A) / sizeof(int);
30 // A comparison, equalivalent to std::greater<int> without the
31 // dependency on <functional>.
36 operator()(const int& x, const int& y) const
40 // Each test performs general-case, bookend, not-found condition,
41 // and predicate functional checks.
43 // 25.3.3.1 lower_bound, with and without comparison predicate
47 using std::lower_bound;
49 const int first = A[0];
50 const int last = A[N - 1];
52 const int* p = lower_bound(A, A + N, 3);
55 const int* q = lower_bound(A, A + N, first);
58 const int* r = lower_bound(A, A + N, last);
59 VERIFY(r == A + N - 1);
61 const int* s = lower_bound(A, A + N, 4);
64 const int* t = lower_bound(C, C + N, 3, gt());
67 const int* u = lower_bound(C, C + N, first, gt());
68 VERIFY(u == C + N - 1);
70 const int* v = lower_bound(C, C + N, last, gt());
73 const int* w = lower_bound(C, C + N, 4, gt());
77 // 25.3.3.2 upper_bound, with and without comparison predicate
81 using std::upper_bound;
83 const int first = A[0];
84 const int last = A[N - 1];
86 const int* p = upper_bound(A, A + N, 3);
89 const int* q = upper_bound(A, A + N, first);
92 const int* r = upper_bound(A, A + N, last);
95 const int* s = upper_bound(A, A + N, 4);
98 const int* t = upper_bound(C, C + N, 3, gt());
101 const int* u = upper_bound(C, C + N, first, gt());
104 const int* v = upper_bound(C, C + N, last, gt());
107 const int* w = upper_bound(C, C + N, 4, gt());
111 // 25.3.3.3 equal_range, with and without comparison predicate
115 using std::equal_range;
116 typedef std::pair<const int*, const int*> Ipair;
118 const int first = A[0];
119 const int last = A[N - 1];
121 Ipair p = equal_range(A, A + N, 3);
122 VERIFY(p.first == A + 2);
123 VERIFY(p.second == A + 5);
125 Ipair q = equal_range(A, A + N, first);
126 VERIFY(q.first == A + 0);
127 VERIFY(q.second == A + 1);
129 Ipair r = equal_range(A, A + N, last);
130 VERIFY(r.first == A + N - 1);
131 VERIFY(r.second == A + N);
133 Ipair s = equal_range(A, A + N, 4);
134 VERIFY(s.first == A + 5);
135 VERIFY(s.second == A + 5);
137 Ipair t = equal_range(C, C + N, 3, gt());
138 VERIFY(t.first == C + 2);
139 VERIFY(t.second == C + 5);
141 Ipair u = equal_range(C, C + N, first, gt());
142 VERIFY(u.first == C + N - 1);
143 VERIFY(u.second == C + N);
145 Ipair v = equal_range(C, C + N, last, gt());
146 VERIFY(v.first == C + 0);
147 VERIFY(v.second == C + 1);
149 Ipair w = equal_range(C, C + N, 4, gt());
150 VERIFY(w.first == C + 2);
151 VERIFY(w.second == C + 2);
154 // 25.3.3.4 binary_search, with and without comparison predicate
158 using std::binary_search;
160 const int first = A[0];
161 const int last = A[N - 1];
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));
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()));