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//
62struct 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//
73struct 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//
85struct 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//
97struct 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
106template<typename Rng>
107void 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
155template<typename Rng>
156void test_random_algorithms(Rng & rng, std::input_iterator_tag)
157{
158 // no-op
159}
160
161template<typename Rng>
162void 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
346int* addr(int &i) { return &i; }
347bool true_(int) { return true; }
348
349///////////////////////////////////////////////////////////////////////////////
350// test_main
351//
352void 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
467using boost::unit_test::test_suite;
468
469test_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

source code of boost/libs/range/test/algorithm.cpp