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
24 bool test = true;
25
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);
29
30 // A comparison, equalivalent to std::greater<int> without the
31 // dependency on <functional>.
32
33 struct gt
34 {
35 bool
operator ()gt36 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
44 void
test01()45 test01()
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
78 void
test02()79 test02()
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
112 void
test03()113 test03()
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
155 void
test04()156 test04()
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
174 int
main(int argc,char * argv[])175 main(int argc, char* argv[])
176 {
177 test01();
178 test02();
179 test03();
180 test04();
181
182 return !test;
183 }
184