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(first: 0,last: 1))); |
240 | left_containers.push_back(makeCollection<Collection1>(irange(first: 0,last: 100))); |
241 | |
242 | right_containers.push_back(collection2_ptr(new Collection2)); |
243 | right_containers.push_back(makeCollection<Collection2>(irange(first: 0,last: 1))); |
244 | right_containers.push_back(makeCollection<Collection2>(irange(first: 0,last: 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(on&: joined, from: join(r1: v1, r2&: 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(x: derived_type1(i)); |
350 | reference_output.push_back(x: 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(x: derived_type2(i)); |
357 | reference_output.push_back(x: 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 | on&: output, |
368 | from: boost::make_iterator_range( |
369 | Begin: join_iterator_t( |
370 | x, y, |
371 | boost::range_detail::join_iterator_begin_tag()), |
372 | End: 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 | } |
397 | |