1 // Copyright Neil Groves 2009. Use, modification and
2 // distribution is subject to the Boost Software License, Version
3 // 1.0. (See accompanying file LICENSE_1_0.txt or copy at
4 // http://www.boost.org/LICENSE_1_0.txt)
5 //
6 //
7 // For more information, see http://www.boost.org/libs/range/
8 //
9 #include <boost/range/algorithm/merge.hpp>
10
11 #include <boost/test/test_tools.hpp>
12 #include <boost/test/unit_test.hpp>
13
14 #include <boost/assign.hpp>
15 #include <algorithm>
16 #include <functional>
17 #include <list>
18 #include <numeric>
19 #include <deque>
20 #include <vector>
21
22 namespace boost
23 {
24 namespace
25 {
26 template<class Container1, class Container2>
test(Container1 & cont1,Container2 & cont2)27 void test(Container1& cont1, Container2& cont2)
28 {
29 typedef BOOST_DEDUCED_TYPENAME Container1::value_type value_t;
30 typedef BOOST_DEDUCED_TYPENAME std::vector<value_t>::iterator iterator_t;
31
32 std::vector<value_t> reference_target( cont1.size() + cont2.size() );
33
34 iterator_t reference_it
35 = std::merge(cont1.begin(), cont1.end(),
36 cont2.begin(), cont2.end(),
37 reference_target.begin());
38
39 std::vector<value_t> test_target( cont1.size() + cont2.size() );
40
41 iterator_t test_it
42 = boost::merge(cont1, cont2, test_target.begin());
43
44 BOOST_CHECK_EQUAL(
45 std::distance<iterator_t>(reference_target.begin(), reference_it),
46 std::distance<iterator_t>(test_target.begin(), test_it)
47 );
48
49 BOOST_CHECK_EQUAL_COLLECTIONS(
50 reference_target.begin(), reference_target.end(),
51 test_target.begin(), test_target.end()
52 );
53
54 test_it = boost::merge(boost::make_iterator_range(cont1),
55 cont2, test_target.begin());
56
57 BOOST_CHECK_EQUAL(
58 std::distance<iterator_t>(reference_target.begin(), reference_it),
59 std::distance<iterator_t>(test_target.begin(), test_it)
60 );
61
62 BOOST_CHECK_EQUAL_COLLECTIONS(
63 reference_target.begin(), reference_target.end(),
64 test_target.begin(), test_target.end()
65 );
66
67 test_it = boost::merge(cont1, boost::make_iterator_range(cont2),
68 test_target.begin());
69
70 BOOST_CHECK_EQUAL(
71 std::distance<iterator_t>(reference_target.begin(), reference_it),
72 std::distance<iterator_t>(test_target.begin(), test_it)
73 );
74
75 BOOST_CHECK_EQUAL_COLLECTIONS(
76 reference_target.begin(), reference_target.end(),
77 test_target.begin(), test_target.end()
78 );
79
80 test_it = boost::merge(boost::make_iterator_range(cont1),
81 boost::make_iterator_range(cont2),
82 test_target.begin());
83
84 BOOST_CHECK_EQUAL(
85 std::distance<iterator_t>(reference_target.begin(), reference_it),
86 std::distance<iterator_t>(test_target.begin(), test_it)
87 );
88
89 BOOST_CHECK_EQUAL_COLLECTIONS(
90 reference_target.begin(), reference_target.end(),
91 test_target.begin(), test_target.end()
92 );
93 }
94
95 template<class Container, class BinaryPredicate>
sort_container(Container & cont,BinaryPredicate pred)96 void sort_container(Container& cont, BinaryPredicate pred)
97 {
98 typedef BOOST_DEDUCED_TYPENAME Container::value_type value_t;
99
100 std::vector<value_t> temp(cont.begin(), cont.end());
101 std::sort(temp.begin(), temp.end(), pred);
102 cont.assign(temp.begin(), temp.end());
103 }
104
105 template<class Container1,
106 class Container2,
107 class BinaryPredicate>
test_pred(Container1 cont1,Container2 cont2,BinaryPredicate pred)108 void test_pred(Container1 cont1, Container2 cont2, BinaryPredicate pred)
109 {
110 typedef BOOST_DEDUCED_TYPENAME Container1::value_type value_t;
111 typedef BOOST_DEDUCED_TYPENAME std::vector<value_t>::iterator iterator_t;
112
113 sort_container(cont1, pred);
114 sort_container(cont2, pred);
115
116 std::vector<value_t> reference_target( cont1.size() + cont2.size() );
117
118 iterator_t reference_it
119 = std::merge(cont1.begin(), cont1.end(),
120 cont2.begin(), cont2.end(),
121 reference_target.begin(), pred);
122
123 std::vector<value_t> test_target( cont1.size() + cont2.size() );
124
125 iterator_t test_it
126 = boost::merge(cont1, cont2, test_target.begin(), pred);
127
128 BOOST_CHECK_EQUAL(
129 std::distance(reference_target.begin(), reference_it),
130 std::distance(test_target.begin(), test_it)
131 );
132
133 BOOST_CHECK_EQUAL_COLLECTIONS(
134 reference_target.begin(), reference_target.end(),
135 test_target.begin(), test_target.end()
136 );
137
138 test_it = boost::merge(boost::make_iterator_range(cont1), cont2,
139 test_target.begin(), pred);
140
141 BOOST_CHECK_EQUAL(
142 std::distance(reference_target.begin(), reference_it),
143 std::distance(test_target.begin(), test_it)
144 );
145
146 BOOST_CHECK_EQUAL_COLLECTIONS(
147 reference_target.begin(), reference_target.end(),
148 test_target.begin(), test_target.end()
149 );
150
151 test_it = boost::merge(cont1, boost::make_iterator_range(cont2),
152 test_target.begin(), pred);
153
154 BOOST_CHECK_EQUAL(
155 std::distance(reference_target.begin(), reference_it),
156 std::distance(test_target.begin(), test_it)
157 );
158
159 BOOST_CHECK_EQUAL_COLLECTIONS(
160 reference_target.begin(), reference_target.end(),
161 test_target.begin(), test_target.end()
162 );
163
164 test_it = boost::merge(boost::make_iterator_range(cont1),
165 boost::make_iterator_range(cont2),
166 test_target.begin(), pred);
167
168 BOOST_CHECK_EQUAL(
169 std::distance(reference_target.begin(), reference_it),
170 std::distance(test_target.begin(), test_it)
171 );
172
173 BOOST_CHECK_EQUAL_COLLECTIONS(
174 reference_target.begin(), reference_target.end(),
175 test_target.begin(), test_target.end()
176 );
177 }
178
179 template<class Container1, class Container2>
test_merge_impl(Container1 & cont1,Container2 & cont2)180 void test_merge_impl(Container1& cont1, Container2& cont2)
181 {
182 test(cont1, cont2);
183 test_pred(cont1, cont2, std::less<int>());
184 test_pred(cont1, cont2, std::greater<int>());
185 }
186
187 template<class Container1, class Container2>
test_merge_impl()188 void test_merge_impl()
189 {
190 using namespace boost::assign;
191
192 Container1 cont1;
193 Container2 cont2;
194
195 test_merge_impl(cont1, cont2);
196
197 cont1.clear();
198 cont2.clear();
199 cont1 += 1;
200 test_merge_impl(cont1, cont2);
201
202 cont1.clear();
203 cont2.clear();
204 cont2 += 1;
205 test_merge_impl(cont1, cont2);
206
207 cont1.clear();
208 cont2.clear();
209 cont1 += 1,3,5,7,9,11,13,15,17,19;
210 cont2 += 2,4,6,8,10,12,14,16,18,20;
211 test_merge_impl(cont1, cont2);
212 }
213
test_merge()214 void test_merge()
215 {
216 test_merge_impl< std::vector<int>, std::vector<int> >();
217 test_merge_impl< std::list<int>, std::list<int> >();
218 test_merge_impl< std::deque<int>, std::deque<int> >();
219
220 test_merge_impl< std::list<int>, std::vector<int> >();
221 test_merge_impl< std::vector<int>, std::list<int> >();
222 }
223 }
224 }
225
226
227 boost::unit_test::test_suite*
init_unit_test_suite(int argc,char * argv[])228 init_unit_test_suite(int argc, char* argv[])
229 {
230 boost::unit_test::test_suite* test
231 = BOOST_TEST_SUITE( "RangeTestSuite.algorithm.merge" );
232
233 test->add( BOOST_TEST_CASE( &boost::test_merge ) );
234
235 return test;
236 }
237