libs/range/test/join.cpp

   1 // Boost.Range library
   2 //
   3 //  Copyright Neil Groves 2010. 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 //
   9 // For more information, see http://www.boost.org/libs/range/
  10 //
  11 // Credits:
  12 // Trac 7376 - was raised by Leonid Gershanovich and his sample was used to
  13 // make the test case to cover this condition.
  14 //
  15 #include <boost/range/join.hpp>
  16 #include <boost/range/adaptor/transformed.hpp>
  17
  18 #include <boost/foreach.hpp>
  19 #include <boost/test/test_tools.hpp>
  20 #include <boost/test/unit_test.hpp>
  21
  22 #include <boost/assign.hpp>
  23 #include <boost/range/algorithm_ext.hpp>
  24 #include <boost/range/irange.hpp>
  25
  26 #include <boost/iterator/iterator_facade.hpp>
  27
  28 #include <algorithm>
  29 #include <deque>
  30 #include <list>
  31 #include <vector>
  32
  33 namespace boost
  34 {
  35     namespace
  36     {
  37         // This function is a helper function that writes integers
  38         // of increasing value into a range. It is used to test
  39         // that joined ranged may be written to.
  40         //
  41         // Requires:
  42         // - Range uses shallow copy semantics.
  43         template< typename Range >
  44         void fill_with_ints(Range rng)
  45         {
  46             typedef typename range_iterator<Range>::type iterator;
  47             iterator target = boost::begin(rng);
  48             const int count = boost::distance(rng);
  49             for (int i = 0; i < count; ++i)
  50             {
  51                 *target = i;
  52                 ++target;
  53             }
  54         }
  55
  56         // The test_join_traversal function is used to provide additional
  57         // tests based upon the underlying join iterator traversal.
  58         // The join iterator takes care of the appropriate demotion, and
  59         // this demotion.
  60
  61         // test_join_traversal - additional tests for input and forward
  62         // traversal iterators. This is of course a no-op.
  63         template< typename Range1, typename Range2, typename TraversalTag >
  64         void test_join_traversal(Range1& rng1, Range2& rng2, TraversalTag)
  65         {
  66         }
  67
  68         // test_join_traversal - additional tests for bidirectional
  69         // traversal iterators.
  70         template< typename Range1, typename Range2 >
  71         void test_join_traversal(Range1& rng1, Range2& rng2, boost::bidirectional_traversal_tag)
  72         {
  73             typedef typename range_value<Range1>::type value_type;
  74             std::vector<value_type> reference(boost::begin(rng1), boost::end(rng1));
  75             boost::push_back(reference, rng2);
  76             std::reverse(reference.begin(), reference.end());
  77
  78             std::vector<value_type> test_result;
  79             BOOST_REVERSE_FOREACH( value_type x, join(rng1, rng2) )
  80             {
  81                 test_result.push_back(x);
  82             }
  83
  84             BOOST_CHECK_EQUAL_COLLECTIONS( reference.begin(), reference.end(),
  85                                            test_result.begin(), test_result.end() );
  86         }
  87
  88         // Test helper function to implement the additional tests for random
  89         // access traversal iterators. This is used by the test_join_traversal
  90         // function for random access iterators. The reason that the test
  91         // implementation is put into this function is to utilise
  92         // template parameter type deduction for the joined range type.
  93         template< typename Range1, typename Range2, typename JoinedRange >
  94         void test_random_access_join(Range1& rng1, Range2& rng2, JoinedRange joined)
  95         {
  96             BOOST_CHECK_EQUAL( boost::end(joined) - boost::begin(joined), boost::distance(joined) );
  97             BOOST_CHECK( boost::end(joined) <= boost::begin(joined) );
  98             BOOST_CHECK( boost::begin(joined) >= boost::end(joined) );
  99             if (boost::empty(joined))
 100             {
 101                 BOOST_CHECK(!(boost::begin(joined) < boost::end(joined)));
 102                 BOOST_CHECK(!(boost::end(joined) > boost::begin(joined)));
 103             }
 104             else
 105             {
 106                 BOOST_CHECK(boost::begin(joined) < boost::end(joined));
 107                 BOOST_CHECK(boost::end(joined) < boost::begin(joined));
 108             }
 109
 110             typedef typename boost::range_difference<JoinedRange>::type difference_t;
 111             const difference_t count = boost::distance(joined);
 112             BOOST_CHECK( boost::begin(joined) + count == boost::end(joined) );
 113             BOOST_CHECK( boost::end(joined) - count == boost::begin(joined) );
 114
 115             typedef typename boost::range_iterator<JoinedRange>::type iterator_t;
 116             iterator_t it = boost::begin(joined);
 117             it += count;
 118             BOOST_CHECK( it == boost::end(joined) );
 119
 120             it = boost::end(joined);
 121             it -= count;
 122             BOOST_CHECK( it == boost::begin(joined) );
 123         }
 124
 125         // test_join_traversal function for random access traversal joined
 126         // ranges.
 127         template< typename Range1, typename Range2 >
 128         void test_join_traversal(Range1& rng1, Range2& rng2, boost::random_access_traversal_tag)
 129         {
 130             test_join_traversal(rng1, rng2, boost::bidirectional_traversal_tag());
 131             test_random_access_join(rng1, rng2, join(rng1, rng2));
 132         }
 133
 134         // Test the ability to write values into a joined range. This is
 135         // achieved by copying the constant collections, altering them
 136         // and then checking the result. Hence this relies upon both
 137         // rng1 and rng2 having value copy semantics.
 138         template< typename Collection1, typename Collection2 >
 139         void test_write_to_joined_range(const Collection1& rng1, const Collection2& rng2)
 140         {
 141             Collection1 c1(rng1);
 142             Collection2 c2(rng2);
 143
 144             typedef BOOST_DEDUCED_TYPENAME boost::range_value<
 145                 Collection1
 146             >::type value_t BOOST_RANGE_UNUSED;
 147
 148             fill_with_ints(boost::join(c1,c2));
 149
 150             // Ensure that the size of the written range has not been
 151             // altered.
 152             BOOST_CHECK_EQUAL( boost::distance(c1), boost::distance(rng1) );
 153             BOOST_CHECK_EQUAL( boost::distance(c2), boost::distance(rng2) );
 154
 155             // For each element x, in c1 ensure that it has been written to
 156             // with incrementing integers
 157             int x = 0;
 158             typedef typename range_iterator<Collection1>::type iterator1;
 159             iterator1 it1 = boost::begin(c1);
 160             for (; it1 != boost::end(c1); ++it1)
 161             {
 162                 BOOST_CHECK_EQUAL( x, *it1 );
 163                 ++x;
 164             }
 165
 166             // For each element y, in c2 ensure that it has been written to
 167             // with incrementing integers
 168             typedef typename range_iterator<Collection2>::type iterator2;
 169             iterator2 it2 = boost::begin(c2);
 170             for (; it2 != boost::end(c2); ++it2)
 171             {
 172                 BOOST_CHECK_EQUAL( x, *it2 );
 173                 ++x;
 174             }
 175         }
 176
 177         // Perform a unit test of a Boost.Range join() comparing
 178         // it to a reference that is populated by appending
 179         // elements from both source ranges into a vector.
 180         template< typename Collection1, typename Collection2 >
 181         void test_join_impl(Collection1& rng1, Collection2& rng2)
 182         {
 183             typedef typename range_value<Collection1>::type value_type;
 184             std::vector<value_type> reference(boost::begin(rng1), boost::end(rng1));
 185             boost::push_back(reference, rng2);
 186
 187             std::vector<value_type> test_result;
 188             boost::push_back(test_result, join(rng1, rng2));
 189
 190             BOOST_CHECK_EQUAL_COLLECTIONS( reference.begin(), reference.end(),
 191                                            test_result.begin(), test_result.end() );
 192
 193             typedef boost::range_detail::join_iterator<
 194                 typename boost::range_iterator<Collection1>::type,
 195                 typename boost::range_iterator<Collection2>::type
 196                 > join_iterator_t;
 197
 198             typedef boost::iterator_traversal< join_iterator_t > tag_t;
 199
 200            test_join_traversal(rng1, rng2, tag_t());
 201
 202            test_write_to_joined_range(rng1, rng2);
 203         }
 204
 205         // Make a collection filling it with items from the source
 206         // range. This is used to build collections of various
 207         // sizes populated with various values designed to optimize
 208         // the code coverage exercised by the core test function
 209         // test_join_impl.
 210         template<typename Collection, typename Range>
 211         boost::shared_ptr<Collection> makeCollection(const Range& source)
 212         {
 213             boost::shared_ptr<Collection> c(new Collection);
 214             c->insert(c->end(), boost::begin(source), boost::end(source));
 215             return c;
 216         }
 217
 218         // This templatised version of the test_join_impl function
 219         // generates and populates collections which are later
 220         // used as input to the core test function.
 221         // The caller of this function explicitly provides the
 222         // template parameters. This supports the generation
 223         // of testing a large combination of range types to be
 224         // joined. It is of particular importance to remember
 225         // to combine a random_access range with a bidirectional
 226         // range to determine that the correct demotion of
 227         // types occurs in the join_iterator.
 228         template< typename Collection1, typename Collection2 >
 229         void test_join_impl()
 230         {
 231             typedef boost::shared_ptr<Collection1> collection1_ptr;
 232             typedef boost::shared_ptr<Collection2> collection2_ptr;
 233             typedef boost::shared_ptr<const Collection1> collection1_cptr;
 234             typedef boost::shared_ptr<const Collection2> collection2_cptr;
 235             std::vector< collection1_cptr > left_containers;
 236             std::vector< collection2_cptr > right_containers;
 237
 238             left_containers.push_back(collection1_ptr(new Collection1));
 239             left_containers.push_back(makeCollection<Collection1>(irange(0,1)));
 240             left_containers.push_back(makeCollection<Collection1>(irange(0,100)));
 241
 242             right_containers.push_back(collection2_ptr(new Collection2));
 243             right_containers.push_back(makeCollection<Collection2>(irange(0,1)));
 244             right_containers.push_back(makeCollection<Collection2>(irange(0,100)));
 245
 246             BOOST_FOREACH( collection1_cptr left_container, left_containers )
 247             {
 248                 BOOST_FOREACH( collection2_cptr right_container, right_containers )
 249                 {
 250                     test_join_impl(*left_container, *right_container);
 251                 }
 252             }
 253         }
 254
 255         // entry-point into the unit test for the join() function
 256         // this tests a representative sample of combinations of
 257         // source range type.
 258         void join_test()
 259         {
 260             test_join_impl< std::vector<int>, std::vector<int> >();
 261             test_join_impl< std::list<int>,   std::list<int>   >();
 262             test_join_impl< std::deque<int>,  std::deque<int>  >();
 263
 264             test_join_impl< std::vector<int>, std::list<int>   >();
 265             test_join_impl< std::list<int>,   std::vector<int> >();
 266             test_join_impl< std::vector<int>, std::deque<int>  >();
 267             test_join_impl< std::deque<int>,  std::vector<int> >();
 268         }
 269
 270         void test_join_iterator_reference_type_constness_ticket8483()
 271         {
 272             // Just test that this compiles.
 273             // Before the fix for bug 8483, the reference type of the joined
 274             // range's iterator was incorrect ('int&' instead of 'const int&'),
 275             // causing compiler errors.
 276             const std::vector<int> v1;
 277             std::vector<int> v2;
 278             std::vector<int> joined;
 279             boost::push_back(joined, join(v1, v2));
 280         }
 281
 282         namespace trac7376
 283         {
 284             struct base_type
 285             {
 286                 explicit base_type(boost::int32_t value)
 287                     : value(value)
 288                 {
 289                 }
 290
 291                 virtual boost::int32_t get() const = 0;
 292
 293                 boost::int32_t value;
 294             };
 295
 296             struct derived_type1
 297                 : base_type
 298             {
 299                 derived_type1(boost::int32_t value)
 300                     : base_type(value)
 301                 {
 302                 }
 303
 304                 virtual boost::int32_t get() const
 305                 {
 306                     return value * 2;
 307                 }
 308             };
 309
 310             struct derived_type2
 311                 : base_type
 312             {
 313                 derived_type2(boost::int32_t value)
 314                     : base_type(value)
 315                 {
 316                 }
 317
 318                 virtual boost::int32_t get() const
 319                 {
 320                     return value * 4;
 321                 }
 322             };
 323
 324             struct apply_get
 325             {
 326                 typedef boost::int32_t result_type;
 327                 result_type operator()(const base_type& arg) const
 328                 {
 329                     return arg.get();
 330                 }
 331             };
 332
 333             void test_reference_types()
 334             {
 335                 using namespace boost::adaptors;
 336
 337                 typedef boost::range_detail::join_iterator<
 338                         std::vector<derived_type1>::iterator,
 339                         std::vector<derived_type2>::iterator,
 340                         const base_type&,
 341                         const base_type&
 342                 > join_iterator_t;
 343
 344                 std::vector<boost::int32_t> reference_output;
 345
 346                 std::vector<derived_type1> x;
 347                 for (boost::int32_t i = 0; i < 10; ++i)
 348                 {
 349                     x.push_back(derived_type1(i));
 350                     reference_output.push_back(i * 2);
 351                 }
 352
 353                 std::vector<derived_type2> y;
 354                 for (boost::int32_t i = 0; i < 10; ++i)
 355                 {
 356                     y.push_back(derived_type2(i));
 357                     reference_output.push_back(i * 4);
 358                 }
 359
 360                 join_iterator_t it(
 361                     x,
 362                     y,
 363                     boost::range_detail::join_iterator_begin_tag());
 364
 365                 std::vector<boost::int32_t> output;
 366                 boost::push_back(
 367                     output,
 368                     boost::make_iterator_range(
 369                         join_iterator_t(
 370                             x, y,
 371                             boost::range_detail::join_iterator_begin_tag()),
 372                         join_iterator_t(
 373                             x, y,
 374                             boost::range_detail::join_iterator_end_tag()))
 375                         | transformed(apply_get()));
 376
 377                 BOOST_CHECK_EQUAL_COLLECTIONS(
 378                             output.begin(), output.end(),
 379                             reference_output.begin(), reference_output.end());
 380             }
 381         } // namespace trac7376
 382     }
 383 }
 384
 385 boost::unit_test::test_suite*
 386 init_unit_test_suite(int argc, char* argv[])
 387 {
 388     boost::unit_test::test_suite* test
 389         = BOOST_TEST_SUITE( "RangeTestSuite.adaptor.joined" );
 390
 391     test->add( BOOST_TEST_CASE( &boost::join_test ) );
 392     test->add( BOOST_TEST_CASE( &boost::test_join_iterator_reference_type_constness_ticket8483 ) );
 393     test->add( BOOST_TEST_CASE( &boost::trac7376::test_reference_types ) );
 394
 395     return test;
 396 }