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
33namespace 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
385boost::unit_test::test_suite*
386init_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}
397