]>
Commit | Line | Data |
---|---|---|
1 | // (C) Copyright David Abrahams 2000. | |
2 | // Distributed under the Boost Software License, Version 1.0. (See | |
3 | // accompanying file LICENSE_1_0.txt or copy at | |
4 | // http://www.boost.org/LICENSE_1_0.txt) | |
5 | ||
6 | #include <boost/detail/binary_search.hpp> | |
7 | #include <vector> | |
8 | #include <string> | |
9 | #include <memory> | |
10 | #include <climits> | |
11 | #include <iostream> | |
12 | #include <cstddef> | |
13 | #include <stdlib.h> // for rand(). Would use cstdlib but VC6.4 doesn't put it in std:: | |
14 | #include <list> | |
15 | #include <utility> | |
16 | #include <algorithm> | |
17 | #include <boost/detail/workaround.hpp> | |
18 | #include <boost/core/lightweight_test.hpp> | |
19 | ||
20 | #if defined(__SGI_STL_PORT) ? defined(__SGI_STL_OWN_IOSTREAMS) : (!defined(__GNUC__) || __GNUC__ > 2) | |
21 | # define USE_SSTREAM | |
22 | #endif | |
23 | ||
24 | #ifdef USE_SSTREAM | |
25 | # include <sstream> | |
26 | #else | |
27 | # include <strstream> | |
28 | #endif | |
29 | ||
30 | namespace { | |
31 | ||
32 | // In order to get ADL to find the comparison operators defined below, they have | |
33 | struct mystring : std::string | |
34 | { | |
35 | typedef std::string base; | |
36 | ||
37 | mystring(std::string const& x) | |
38 | : base(x) {} | |
39 | }; | |
40 | ||
41 | typedef std::vector<mystring> string_vector; | |
42 | ||
43 | const std::size_t sequence_length = 1000; | |
44 | ||
45 | unsigned random_number() | |
46 | { | |
47 | return static_cast<unsigned>(::rand()) % sequence_length; | |
48 | } | |
49 | ||
50 | # ifndef USE_SSTREAM | |
51 | class unfreezer { | |
52 | public: | |
53 | unfreezer(std::ostrstream& s) : m_stream(s) {} | |
54 | ~unfreezer() { m_stream.freeze(false); } | |
55 | private: | |
56 | std::ostrstream& m_stream; | |
57 | }; | |
58 | # endif | |
59 | ||
60 | template <class T> | |
61 | void push_back_random_number_string(T& seq) | |
62 | { | |
63 | unsigned value = random_number(); | |
64 | # if defined(__SGI_STL_PORT) ? defined(__SGI_STL_OWN_IOSTREAMS) : (!defined(__GNUC__) || __GNUC__ > 2) | |
65 | std::ostringstream s; | |
66 | s << value; | |
67 | seq.push_back(s.str()); | |
68 | # else | |
69 | std::ostrstream s; | |
70 | auto unfreezer unfreeze(s); | |
71 | s << value << char(0); | |
72 | seq.push_back(std::string(s.str())); | |
73 | # endif | |
74 | } | |
75 | ||
76 | inline unsigned to_int(unsigned x) { return x; } | |
77 | inline unsigned to_int(const std::string& x) { return atoi(x.c_str()); } | |
78 | ||
79 | struct cmp | |
80 | { | |
81 | template <class A1, class A2> | |
82 | inline bool operator()(const A1& a1, const A2& a2) const | |
83 | { | |
84 | return to_int(a1) < to_int(a2); | |
85 | } | |
86 | }; | |
87 | ||
88 | inline bool operator<(const mystring& x, const unsigned y) | |
89 | { | |
90 | return to_int(x) < y; | |
91 | } | |
92 | ||
93 | inline bool operator<(const unsigned y, const mystring& x) | |
94 | { | |
95 | return y < to_int(x); | |
96 | } | |
97 | ||
98 | template <class T> | |
99 | void sort_by_value(T& x); | |
100 | ||
101 | template <class T> | |
102 | void sort_by_value_(T& v, long) | |
103 | { | |
104 | std::sort(v.begin(), v.end(), cmp()); | |
105 | } | |
106 | ||
107 | template <class T> | |
108 | void random_sorted_sequence(T& seq) | |
109 | { | |
110 | seq.clear(); | |
111 | for (std::size_t i = 0; i < sequence_length; ++i) | |
112 | { | |
113 | push_back_random_number_string(seq); | |
114 | } | |
115 | sort_by_value(seq); | |
116 | } | |
117 | ||
118 | template <class T, class A> | |
119 | void sort_by_value_(std::list<T,A>& l, int) | |
120 | { | |
121 | # if BOOST_WORKAROUND(BOOST_DINKUMWARE_STDLIB, == 1) && !defined(__SGI_STL_PORT) | |
122 | // VC6's standard lib doesn't have a template member function for list::sort() | |
123 | std::vector<T> seq; | |
124 | seq.reserve(sequence_length); | |
125 | std::copy(l.begin(), l.end(), std::back_inserter(seq)); | |
126 | sort_by_value(seq); | |
127 | std::copy(seq.begin(), seq.end(), l.begin()); | |
128 | # else | |
129 | l.sort(cmp()); | |
130 | # endif | |
131 | } | |
132 | ||
133 | template <class T> | |
134 | void sort_by_value(T& x) | |
135 | { | |
136 | (sort_by_value_)(x, 1); | |
137 | } | |
138 | ||
139 | // A way to select the comparisons with/without a Compare parameter for testing. | |
140 | template <class Compare> struct searches | |
141 | { | |
142 | template <class Iterator, class Key> | |
143 | static Iterator lower_bound(Iterator start, Iterator finish, Key key, Compare cmp) | |
144 | { return boost::detail::lower_bound(start, finish, key, cmp); } | |
145 | ||
146 | template <class Iterator, class Key> | |
147 | static Iterator upper_bound(Iterator start, Iterator finish, Key key, Compare cmp) | |
148 | { return boost::detail::upper_bound(start, finish, key, cmp); } | |
149 | ||
150 | template <class Iterator, class Key> | |
151 | static std::pair<Iterator, Iterator> equal_range(Iterator start, Iterator finish, Key key, Compare cmp) | |
152 | { return boost::detail::equal_range(start, finish, key, cmp); } | |
153 | ||
154 | template <class Iterator, class Key> | |
155 | static bool binary_search(Iterator start, Iterator finish, Key key, Compare cmp) | |
156 | { return boost::detail::binary_search(start, finish, key, cmp); } | |
157 | }; | |
158 | ||
159 | struct no_compare {}; | |
160 | ||
161 | template <> struct searches<no_compare> | |
162 | { | |
163 | template <class Iterator, class Key> | |
164 | static Iterator lower_bound(Iterator start, Iterator finish, Key key, no_compare) | |
165 | { return boost::detail::lower_bound(start, finish, key); } | |
166 | ||
167 | template <class Iterator, class Key> | |
168 | static Iterator upper_bound(Iterator start, Iterator finish, Key key, no_compare) | |
169 | { return boost::detail::upper_bound(start, finish, key); } | |
170 | ||
171 | template <class Iterator, class Key> | |
172 | static std::pair<Iterator, Iterator> equal_range(Iterator start, Iterator finish, Key key, no_compare) | |
173 | { return boost::detail::equal_range(start, finish, key); } | |
174 | ||
175 | template <class Iterator, class Key> | |
176 | static bool binary_search(Iterator start, Iterator finish, Key key, no_compare) | |
177 | { return boost::detail::binary_search(start, finish, key); } | |
178 | }; | |
179 | ||
180 | template <class Sequence, class Compare> | |
181 | void test_loop(Sequence& x, Compare cmp, unsigned long test_count) | |
182 | { | |
183 | typedef typename Sequence::const_iterator const_iterator; | |
184 | ||
185 | for (unsigned long i = 0; i < test_count; ++i) | |
186 | { | |
187 | random_sorted_sequence(x); | |
188 | const const_iterator start = x.begin(); | |
189 | const const_iterator finish = x.end(); | |
190 | ||
191 | unsigned key = random_number(); | |
192 | const const_iterator l = searches<Compare>::lower_bound(start, finish, key, cmp); | |
193 | const const_iterator u = searches<Compare>::upper_bound(start, finish, key, cmp); | |
194 | ||
195 | bool found_l = false; | |
196 | bool found_u = false; | |
197 | std::size_t index = 0; | |
198 | std::size_t count = 0; | |
199 | unsigned last_value = 0; | |
200 | (void)last_value; | |
201 | for (const_iterator p = start; p != finish; ++p) | |
202 | { | |
203 | if (p == l) | |
204 | found_l = true; | |
205 | ||
206 | if (p == u) | |
207 | { | |
208 | BOOST_TEST(found_l); | |
209 | found_u = true; | |
210 | } | |
211 | ||
212 | unsigned value = to_int(*p); | |
213 | BOOST_TEST(value >= last_value); | |
214 | last_value = value; | |
215 | ||
216 | if (!found_l) | |
217 | { | |
218 | ++index; | |
219 | BOOST_TEST(to_int(*p) < key); | |
220 | } | |
221 | else if (!found_u) | |
222 | { | |
223 | ++count; | |
224 | BOOST_TEST(to_int(*p) == key); | |
225 | } | |
226 | else | |
227 | { | |
228 | BOOST_TEST(to_int(*p) > key); | |
229 | } | |
230 | } | |
231 | BOOST_TEST(found_l || l == finish); | |
232 | BOOST_TEST(found_u || u == finish); | |
233 | ||
234 | std::pair<const_iterator, const_iterator> | |
235 | range = searches<Compare>::equal_range(start, finish, key, cmp); | |
236 | BOOST_TEST(range.first == l); | |
237 | BOOST_TEST(range.second == u); | |
238 | ||
239 | bool found = searches<Compare>::binary_search(start, finish, key, cmp); | |
240 | (void)found; | |
241 | BOOST_TEST(found == (u != l)); | |
242 | std::cout << "found " << count << " copies of " << key << " at index " << index << "\n"; | |
243 | } | |
244 | } | |
245 | ||
246 | } | |
247 | ||
248 | int main() | |
249 | { | |
250 | string_vector x; | |
251 | std::cout << "=== testing random-access iterators with <: ===\n"; | |
252 | test_loop(x, no_compare(), 25); | |
253 | std::cout << "=== testing random-access iterators with compare: ===\n"; | |
254 | test_loop(x, cmp(), 25); | |
255 | ||
256 | std::list<mystring> y; | |
257 | std::cout << "=== testing bidirectional iterators with <: ===\n"; | |
258 | test_loop(y, no_compare(), 25); | |
259 | std::cout << "=== testing bidirectional iterators with compare: ===\n"; | |
260 | test_loop(y, cmp(), 25); | |
261 | std::cerr << "******TEST PASSED******\n"; | |
262 | ||
263 | return boost::report_errors(); | |
264 | } |