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