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