ceph/src/boost/libs/range/test/algorithm.cpp

   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(my_list);
 367     test_algorithms(my_vector);
 368     test_algorithms(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