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>
operator ()null_fun64 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>
operator ()null_pred75 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>
operator ()null_op187 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>
operator ()null_op299 T const & operator()(T const & t, U const & u) const
100 {
101 return t;
102 }
103 };
104
105 template<typename Rng>
test_random_algorithms(Rng & rng,std::random_access_iterator_tag)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>
test_random_algorithms(Rng & rng,std::input_iterator_tag)155 void test_random_algorithms(Rng & rng, std::input_iterator_tag)
156 {
157 // no-op
158 }
159
160 template<typename Rng>
test_algorithms(Rng & 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
addr(int & i)345 int* addr(int &i) { return &i; }
true_(int)346 bool true_(int) { return true; }
347
348 ///////////////////////////////////////////////////////////////////////////////
349 // test_main
350 //
simple_compile_test()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(my_list);
366 test_algorithms(my_vector);
367 test_algorithms(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
init_unit_test_suite(int argc,char * argv[])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