1 | // Boost.Range library |
2 | // |
3 | // Copyright Thorsten Ottosen 2006. Use, modification and |
4 | // distribution is subject to the Boost Software License, Version |
5 | // 1.0. (See accompanying file LICENSE_1_0.txt or copy at |
6 | // http://www.boost.org/LICENSE_1_0.txt) |
7 | // |
8 | // For more information, see http://www.boost.org/libs/range/ |
9 | // |
10 | // (C) Copyright Eric Niebler 2004. |
11 | // Use, modification and distribution are subject to the |
12 | // Boost Software License, Version 1.0. (See accompanying file |
13 | // LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) |
14 | |
15 | /* |
16 | Revision history: |
17 | 13 December 2004 : Initial version. |
18 | */ |
19 | |
20 | #ifdef _MSC_VER |
21 | // The 'secure' library warnings produce so much noise that it makes it |
22 | // impossible to see more useful warnings. |
23 | #define _SCL_SECURE_NO_WARNINGS |
24 | #endif |
25 | |
26 | #ifdef _MSC_VER |
27 | // counting_iterator generates a warning about truncating an integer |
28 | #pragma warning(push) |
29 | #pragma warning(disable : 4244) |
30 | #endif |
31 | #include <boost/iterator/counting_iterator.hpp> |
32 | #ifdef _MSC_VER |
33 | template ::boost::counting_iterator<int>; |
34 | #pragma warning(pop) |
35 | #endif |
36 | |
37 | #include <boost/assign.hpp> |
38 | #include <boost/config.hpp> |
39 | #include <boost/array.hpp> |
40 | #include <boost/range/numeric.hpp> |
41 | #include <boost/range/algorithm.hpp> |
42 | #include <boost/range/value_type.hpp> |
43 | #include <boost/range/size_type.hpp> |
44 | #include <boost/range/size.hpp> |
45 | |
46 | #include <boost/test/test_tools.hpp> |
47 | #include <boost/test/unit_test.hpp> |
48 | |
49 | #include <boost/iterator/iterator_traits.hpp> |
50 | |
51 | #include <algorithm> |
52 | #include <cstdlib> |
53 | #include <set> |
54 | #include <list> |
55 | #include <vector> |
56 | #include <iterator> |
57 | #include <functional> |
58 | /////////////////////////////////////////////////////////////////////////////// |
59 | // dummy function object, used with algorithms |
60 | // |
61 | struct null_fun |
62 | { |
63 | template<typename T> |
64 | void operator()(T const &t) const |
65 | { |
66 | } |
67 | }; |
68 | |
69 | /////////////////////////////////////////////////////////////////////////////// |
70 | // dummy predicate, used with algorithms |
71 | // |
72 | struct null_pred |
73 | { |
74 | template<typename T> |
75 | bool operator()(T const &t) const |
76 | { |
77 | return t == T(); |
78 | } |
79 | }; |
80 | |
81 | /////////////////////////////////////////////////////////////////////////////// |
82 | // dummy unary op, used with algorithms |
83 | // |
84 | struct null_op1 |
85 | { |
86 | template<typename T> |
87 | T const & operator()(T const & t) const |
88 | { |
89 | return t; |
90 | } |
91 | }; |
92 | |
93 | /////////////////////////////////////////////////////////////////////////////// |
94 | // dummy binary op, used with algorithms |
95 | // |
96 | struct null_op2 |
97 | { |
98 | template<typename T,typename U> |
99 | T const & operator()(T const & t, U const & u) const |
100 | { |
101 | return t; |
102 | } |
103 | }; |
104 | |
105 | template<typename Rng> |
106 | void test_random_algorithms(Rng & rng, std::random_access_iterator_tag) |
107 | { |
108 | typedef BOOST_DEDUCED_TYPENAME boost::range_iterator<Rng>::type iterator; |
109 | |
110 | typedef BOOST_DEDUCED_TYPENAME boost::range_value<Rng>::type value_type; |
111 | |
112 | typedef BOOST_DEDUCED_TYPENAME boost::range_size<Rng>::type |
113 | size_type BOOST_RANGE_UNUSED; |
114 | |
115 | typedef BOOST_DEDUCED_TYPENAME boost::iterator_category<iterator>::type |
116 | iterator_category BOOST_RANGE_UNUSED; |
117 | |
118 | // just make sure these compile (for now) |
119 | if(0) |
120 | { |
121 | boost::random_shuffle(rng); |
122 | |
123 | // Must be a value since random_shuffle must take the generator by |
124 | // reference to match the standard. |
125 | null_op1 rng_generator; |
126 | boost::random_shuffle(rng, rng_generator); |
127 | |
128 | boost::sort(rng); |
129 | boost::sort(rng, std::less<value_type>()); |
130 | |
131 | boost::stable_sort(rng); |
132 | boost::stable_sort(rng, std::less<value_type>()); |
133 | |
134 | boost::partial_sort(rng, boost::begin(rng)); |
135 | boost::partial_sort(rng, boost::begin(rng), std::less<value_type>()); |
136 | |
137 | boost::nth_element(rng, boost::begin(rng)); |
138 | boost::nth_element(rng, boost::begin(rng), std::less<value_type>()); |
139 | |
140 | boost::push_heap(rng); |
141 | boost::push_heap(rng, std::less<value_type>()); |
142 | |
143 | boost::pop_heap(rng); |
144 | boost::pop_heap(rng, std::less<value_type>()); |
145 | |
146 | boost::make_heap(rng); |
147 | boost::make_heap(rng, std::less<value_type>()); |
148 | |
149 | boost::sort_heap(rng); |
150 | boost::sort_heap(rng, std::less<value_type>()); |
151 | } |
152 | } |
153 | |
154 | template<typename Rng> |
155 | void test_random_algorithms(Rng & rng, std::input_iterator_tag) |
156 | { |
157 | // no-op |
158 | } |
159 | |
160 | template<typename Rng> |
161 | void test_algorithms(Rng & rng) |
162 | { |
163 | typedef BOOST_DEDUCED_TYPENAME boost::range_iterator<Rng>::type iterator; |
164 | typedef BOOST_DEDUCED_TYPENAME boost::range_value<Rng>::type value_type; |
165 | typedef BOOST_DEDUCED_TYPENAME boost::range_size<Rng>::type size_type; |
166 | typedef BOOST_DEDUCED_TYPENAME boost::iterator_category<iterator>::type iterator_category; |
167 | |
168 | // just make sure these compile (for now) |
169 | if(0) |
170 | { |
171 | value_type val = value_type(); |
172 | |
173 | value_type rng2[] = {value_type(),value_type(),value_type()}; |
174 | typedef value_type* iterator2; |
175 | |
176 | value_type out[100] = {}; |
177 | typedef value_type* out_iterator; |
178 | |
179 | null_fun f = null_fun(); |
180 | iterator i = iterator(); |
181 | bool b = bool(); |
182 | out_iterator o = out_iterator(); |
183 | size_type s = size_type(); |
184 | |
185 | f = boost::for_each(rng, null_fun()); |
186 | |
187 | i = boost::find(rng, val); |
188 | i = boost::find_if(rng, null_pred()); |
189 | |
190 | i = boost::find_end(rng, rng2); |
191 | i = boost::find_end(rng, rng2, std::equal_to<value_type>()); |
192 | |
193 | i = boost::find_first_of(rng, rng2); |
194 | i = boost::find_first_of(rng, rng2, std::equal_to<value_type>()); |
195 | |
196 | i = boost::adjacent_find(rng); |
197 | i = boost::adjacent_find(rng, std::equal_to<value_type>()); |
198 | |
199 | s = boost::count(rng, val); |
200 | s = boost::count_if(rng, null_pred()); |
201 | |
202 | std::pair<iterator,iterator2> p1; |
203 | p1 = boost::mismatch(rng, rng2); |
204 | p1 = boost::mismatch(rng, rng2, std::equal_to<value_type>()); |
205 | |
206 | b = boost::equal(rng, rng2); |
207 | b = boost::equal(rng, rng2, std::equal_to<value_type>()); |
208 | |
209 | i = boost::search(rng, rng2); |
210 | i = boost::search(rng, rng2, std::equal_to<value_type>()); |
211 | |
212 | o = boost::copy(rng, boost::begin(out)); |
213 | o = boost::copy_backward(rng, boost::end(out)); |
214 | |
215 | o = boost::transform(rng, boost::begin(out), null_op1()); |
216 | o = boost::transform(rng, rng2, boost::begin(out), null_op2()); |
217 | |
218 | boost::replace(rng, val, val); |
219 | boost::replace_if(rng, null_pred(), val); |
220 | |
221 | /* |
222 | o = boost::replace_copy(rng, boost::begin(out), val, val); |
223 | o = boost::replace_copy_if(rng, boost::begin(out), null_pred(), val); |
224 | */ |
225 | |
226 | boost::fill(rng, val); |
227 | // |
228 | // size requires RandomAccess |
229 | // |
230 | //boost::fill_n(rng, boost::size(rng), val); |
231 | //boost::fill_n(rng, std::distance(boost::begin(rng),boost::end(rng)),val); |
232 | |
233 | boost::generate(rng, &std::rand); |
234 | // |
235 | // size requires RandomAccess |
236 | // |
237 | //boost::generate_n(rng, boost::size(rng), &std::rand); |
238 | //boost::generate_n(rng,std::distance(boost::begin(rng),boost::end(rng)), &std::rand); |
239 | |
240 | i = boost::remove(rng, val); |
241 | i = boost::remove_if(rng, null_pred()); |
242 | |
243 | /* |
244 | o = boost::remove_copy(rng, boost::begin(out), val); |
245 | o = boost::remove_copy_if(rng, boost::begin(out), null_pred()); |
246 | */ |
247 | |
248 | typename boost::range_return<Rng, boost::return_begin_found>::type rrng = boost::unique(rng); |
249 | rrng = boost::unique(rng, std::equal_to<value_type>()); |
250 | |
251 | /* |
252 | o = boost::unique_copy(rng, boost::begin(out)); |
253 | o = boost::unique_copy(rng, boost::begin(out), std::equal_to<value_type>()); |
254 | */ |
255 | |
256 | boost::reverse(rng); |
257 | |
258 | /* |
259 | o = boost::reverse_copy(rng, boost::begin(out)); |
260 | */ |
261 | |
262 | boost::rotate(rng, boost::begin(rng)); |
263 | |
264 | /* |
265 | o = boost::rotate_copy(rng, boost::begin(rng), boost::begin(out)); |
266 | */ |
267 | |
268 | i = boost::partition(rng, null_pred()); |
269 | i = boost::stable_partition(rng, null_pred()); |
270 | |
271 | /* |
272 | o = boost::partial_sort_copy(rng, out); |
273 | o = boost::partial_sort_copy(rng, out, std::less<value_type>()); |
274 | */ |
275 | |
276 | i = boost::lower_bound(rng, val); |
277 | i = boost::lower_bound(rng, val, std::less<value_type>()); |
278 | |
279 | i = boost::upper_bound(rng, val); |
280 | i = boost::upper_bound(rng, val, std::less<value_type>()); |
281 | |
282 | std::pair<iterator,iterator> p2; |
283 | p2 = boost::equal_range(rng, val); |
284 | p2 = boost::equal_range(rng, val, std::less<value_type>()); |
285 | |
286 | b = boost::binary_search(rng, val); |
287 | b = boost::binary_search(rng, val, std::less<value_type>()); |
288 | |
289 | boost::inplace_merge(rng, boost::begin(rng)); |
290 | boost::inplace_merge(rng, boost::begin(rng), std::less<value_type>()); |
291 | |
292 | b = boost::includes(rng, rng2); |
293 | b = boost::includes(rng, rng2, std::equal_to<value_type>()); |
294 | |
295 | o = boost::set_union(rng, rng2, boost::begin(out)); |
296 | o = boost::set_union(rng, rng2, boost::begin(out), std::equal_to<value_type>()); |
297 | |
298 | o = boost::set_intersection(rng, rng2, boost::begin(out)); |
299 | o = boost::set_intersection(rng, rng2, boost::begin(out), std::equal_to<value_type>()); |
300 | |
301 | o = boost::set_difference(rng, rng2, boost::begin(out)); |
302 | o = boost::set_difference(rng, rng2, boost::begin(out), std::equal_to<value_type>()); |
303 | |
304 | o = boost::set_symmetric_difference(rng, rng2, boost::begin(out)); |
305 | o = boost::set_symmetric_difference(rng, rng2, boost::begin(out), std::equal_to<value_type>()); |
306 | |
307 | i = boost::min_element(rng); |
308 | i = boost::min_element(rng, std::less<value_type>()); |
309 | |
310 | i = boost::max_element(rng); |
311 | i = boost::max_element(rng, std::less<value_type>()); |
312 | |
313 | b = boost::lexicographical_compare(rng, rng); |
314 | b = boost::lexicographical_compare(rng, rng, std::equal_to<value_type>()); |
315 | |
316 | b = boost::next_permutation(rng); |
317 | b = boost::next_permutation(rng, std::less<value_type>()); |
318 | |
319 | b = boost::prev_permutation(rng); |
320 | b = boost::prev_permutation(rng, std::less<value_type>()); |
321 | |
322 | ///////////////////////////////////////////////////////////////////// |
323 | // numeric algorithms |
324 | ///////////////////////////////////////////////////////////////////// |
325 | |
326 | val = boost::accumulate( rng, val ); |
327 | val = boost::accumulate( rng, val, null_op2() ); |
328 | val = boost::inner_product( rng, rng, val ); |
329 | val = boost::inner_product( rng, rng, val, |
330 | null_op2(), null_op2() ); |
331 | o = boost::partial_sum( rng, boost::begin(out) ); |
332 | o = boost::partial_sum( rng, boost::begin(out), null_op2() ); |
333 | o = boost::adjacent_difference( rng, boost::begin(out) ); |
334 | o = boost::adjacent_difference( rng, boost::begin(out), |
335 | null_op2() ); |
336 | |
337 | boost::ignore_unused_variable_warning(b); |
338 | |
339 | } |
340 | |
341 | // test the algorithms that require a random-access range |
342 | test_random_algorithms(rng, iterator_category()); |
343 | } |
344 | |
345 | int* addr(int &i) { return &i; } |
346 | bool true_(int) { return true; } |
347 | |
348 | /////////////////////////////////////////////////////////////////////////////// |
349 | // test_main |
350 | // |
351 | void simple_compile_test() |
352 | { |
353 | // int_iterator |
354 | typedef ::boost::counting_iterator<int> int_iterator; |
355 | |
356 | // define come containers |
357 | std::list<int> my_list(int_iterator(1),int_iterator(6)); |
358 | |
359 | |
360 | std::vector<int> my_vector(int_iterator(1),int_iterator(6)); |
361 | |
362 | std::pair<std::vector<int>::iterator,std::vector<int>::iterator> my_pair(my_vector.begin(),my_vector.end()); |
363 | |
364 | // test the algorithms with list and const list |
365 | test_algorithms(rng&: my_list); |
366 | test_algorithms(rng&: my_vector); |
367 | test_algorithms(rng&: my_pair); |
368 | |
369 | |
370 | std::vector<int> v; |
371 | std::vector<int>& cv = v; |
372 | |
373 | using namespace boost; |
374 | |
375 | #define BOOST_RANGE_RETURNS_TEST( function_name, cont ) \ |
376 | function_name (cont); \ |
377 | function_name <return_found> (cont); \ |
378 | function_name <return_next> (cont); \ |
379 | function_name <return_prior> (cont); \ |
380 | function_name <return_begin_found> (cont); \ |
381 | function_name <return_begin_next> (cont); \ |
382 | function_name <return_begin_prior> (cont); \ |
383 | function_name <return_found_end> (cont); \ |
384 | function_name <return_next_end>(cont); \ |
385 | function_name <return_prior_end>(cont); |
386 | |
387 | BOOST_RANGE_RETURNS_TEST( adjacent_find, cv ); |
388 | BOOST_RANGE_RETURNS_TEST( adjacent_find, v ); |
389 | BOOST_RANGE_RETURNS_TEST( max_element, cv ); |
390 | BOOST_RANGE_RETURNS_TEST( max_element, v ); |
391 | BOOST_RANGE_RETURNS_TEST( min_element, cv ); |
392 | BOOST_RANGE_RETURNS_TEST( min_element, v ); |
393 | BOOST_RANGE_RETURNS_TEST( unique, v ); |
394 | #undef BOOST_RANGE_RETURNS_TEST |
395 | |
396 | #define BOOST_RANGE_RETURNS_TEST1( function_name, cont, arg1 ) \ |
397 | function_name (cont, arg1); \ |
398 | function_name <return_found> (cont, arg1); \ |
399 | function_name <return_next> (cont, arg1); \ |
400 | function_name <return_prior> (cont, arg1); \ |
401 | function_name <return_begin_found> (cont, arg1); \ |
402 | function_name <return_begin_next> (cont, arg1); \ |
403 | function_name <return_begin_prior> (cont, arg1); \ |
404 | function_name <return_found_end> (cont, arg1); \ |
405 | function_name <return_next_end>(cont, arg1); \ |
406 | function_name <return_prior_end>(cont, arg1); |
407 | |
408 | BOOST_RANGE_RETURNS_TEST1( adjacent_find, cv, std::less<int>() ); |
409 | BOOST_RANGE_RETURNS_TEST1( adjacent_find, v, std::less<int>() ); |
410 | BOOST_RANGE_RETURNS_TEST1( find, cv, 0 ); |
411 | BOOST_RANGE_RETURNS_TEST1( find, v, 0 ); |
412 | BOOST_RANGE_RETURNS_TEST1( find_end, cv, cv ); |
413 | BOOST_RANGE_RETURNS_TEST1( find_end, cv, v ); |
414 | BOOST_RANGE_RETURNS_TEST1( find_end, v, cv ); |
415 | BOOST_RANGE_RETURNS_TEST1( find_end, v, v ); |
416 | BOOST_RANGE_RETURNS_TEST1( find_first_of, cv, cv ); |
417 | BOOST_RANGE_RETURNS_TEST1( find_first_of, cv, v ); |
418 | BOOST_RANGE_RETURNS_TEST1( find_first_of, v, cv ); |
419 | BOOST_RANGE_RETURNS_TEST1( find_first_of, v, v ); |
420 | BOOST_RANGE_RETURNS_TEST1( find_if, cv, std::negate<int>() ); |
421 | BOOST_RANGE_RETURNS_TEST1( find_if, v, std::negate<int>() ); |
422 | BOOST_RANGE_RETURNS_TEST1( search, cv, cv ); |
423 | BOOST_RANGE_RETURNS_TEST1( search, cv, v ); |
424 | BOOST_RANGE_RETURNS_TEST1( search, v, cv ); |
425 | BOOST_RANGE_RETURNS_TEST1( search, v, v ); |
426 | |
427 | BOOST_RANGE_RETURNS_TEST1( remove, v, 0 ); |
428 | BOOST_RANGE_RETURNS_TEST1( remove_if, v, std::negate<int>() ); |
429 | |
430 | BOOST_RANGE_RETURNS_TEST1( lower_bound, cv, 0 ); |
431 | BOOST_RANGE_RETURNS_TEST1( lower_bound, v, 0 ); |
432 | BOOST_RANGE_RETURNS_TEST1( max_element, cv, std::less<int>() ); |
433 | BOOST_RANGE_RETURNS_TEST1( max_element, v, std::less<int>() ); |
434 | BOOST_RANGE_RETURNS_TEST1( min_element, cv, std::less<int>() ); |
435 | BOOST_RANGE_RETURNS_TEST1( min_element, v, std::less<int>() ); |
436 | BOOST_RANGE_RETURNS_TEST1( upper_bound, cv, 0 ); |
437 | BOOST_RANGE_RETURNS_TEST1( upper_bound, v, 0 ); |
438 | BOOST_RANGE_RETURNS_TEST1( partition, cv, std::negate<int>() ); |
439 | BOOST_RANGE_RETURNS_TEST1( partition, v, std::negate<int>() ); |
440 | BOOST_RANGE_RETURNS_TEST1( stable_partition, cv, std::negate<int>() ); |
441 | BOOST_RANGE_RETURNS_TEST1( stable_partition, v, std::negate<int>() ); |
442 | |
443 | #undef BOOST_RANGE_RETURNS_TEST1 |
444 | |
445 | #define BOOST_RANGE_RETURNS_TEST2( function_name, arg1, arg2 ) \ |
446 | function_name (v, arg1, arg2); \ |
447 | function_name <return_found> (v, arg1, arg2); \ |
448 | function_name <return_next> (v, arg1, arg2); \ |
449 | function_name <return_prior> (v, arg1, arg2); \ |
450 | function_name <return_begin_found> (v, arg1, arg2); \ |
451 | function_name <return_begin_next> (v, arg1, arg2); \ |
452 | function_name <return_begin_prior> (v, arg1, arg2); \ |
453 | function_name <return_found_end> (v, arg1, arg2); \ |
454 | function_name <return_next_end>(v, arg1, arg2); \ |
455 | function_name <return_prior_end>(v, arg1, arg2); |
456 | |
457 | BOOST_RANGE_RETURNS_TEST2( find_end, v, std::less<int>() ); |
458 | BOOST_RANGE_RETURNS_TEST2( find_first_of, v, std::less<int>() ); |
459 | BOOST_RANGE_RETURNS_TEST2( boost::search, v, std::less<int>() ); |
460 | BOOST_RANGE_RETURNS_TEST2( lower_bound, 0, std::less<int>() ); |
461 | BOOST_RANGE_RETURNS_TEST2( upper_bound, 0, std::less<int>() ); |
462 | |
463 | #undef BOOST_RANGE_RETURNS_TEST2 |
464 | } |
465 | |
466 | using boost::unit_test::test_suite; |
467 | |
468 | test_suite* init_unit_test_suite( int argc, char* argv[] ) |
469 | { |
470 | using namespace boost; |
471 | |
472 | test_suite* test = BOOST_TEST_SUITE( "Range Test Suite - Algorithm" ); |
473 | |
474 | test->add( BOOST_TEST_CASE( &simple_compile_test ) ); |
475 | |
476 | return test; |
477 | } |
478 | |
479 | |