1 2 // Copyright 2016 Daniel James. 3 // Distributed under the Boost Software License, Version 1.0. (See accompanying 4 // file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) 5 6 #include "../helpers/postfix.hpp" 7 #include "../helpers/prefix.hpp" 8 #include <boost/unordered_map.hpp> 9 #include <boost/unordered_set.hpp> 10 11 #include "../helpers/count.hpp" 12 #include "../helpers/helpers.hpp" 13 #include "../helpers/invariants.hpp" 14 #include "../helpers/random_values.hpp" 15 #include "../helpers/test.hpp" 16 #include "../helpers/tracker.hpp" 17 #include "../objects/test.hpp" 18 19 namespace merge_tests { 20 UNORDERED_AUTO_TEST(merge_set)21 UNORDERED_AUTO_TEST (merge_set) { 22 boost::unordered_set<int> x; 23 boost::unordered_set<int> y; 24 25 x.merge(y); 26 BOOST_TEST(x.empty()); 27 BOOST_TEST(y.empty()); 28 29 x.insert(10); 30 x.merge(y); 31 BOOST_TEST(x.size() == 1); 32 BOOST_TEST(x.count(10) == 1); 33 BOOST_TEST(y.empty()); 34 35 y.merge(x); 36 BOOST_TEST(x.empty()); 37 BOOST_TEST(y.size() == 1); 38 BOOST_TEST(y.count(10) == 1); 39 40 x.insert(10); 41 x.insert(50); 42 y.insert(70); 43 y.insert(80); 44 x.merge(y); 45 BOOST_TEST_EQ(x.size(), 4u); 46 BOOST_TEST_EQ(y.size(), 1u); 47 BOOST_TEST_EQ(x.count(10), 1u); 48 BOOST_TEST_EQ(x.count(50), 1u); 49 BOOST_TEST_EQ(x.count(70), 1u); 50 BOOST_TEST_EQ(x.count(80), 1u); 51 BOOST_TEST_EQ(y.count(10), 1u); 52 BOOST_TEST_EQ(y.count(50), 0u); 53 BOOST_TEST_EQ(y.count(70), 0u); 54 BOOST_TEST_EQ(y.count(80), 0u); 55 56 test::check_equivalent_keys(x); 57 test::check_equivalent_keys(y); 58 } 59 UNORDERED_AUTO_TEST(merge_multiset)60 UNORDERED_AUTO_TEST (merge_multiset) { 61 boost::unordered_multiset<int> x; 62 boost::unordered_multiset<int> y; 63 64 x.merge(y); 65 BOOST_TEST(x.empty()); 66 BOOST_TEST(y.empty()); 67 68 x.insert(10); 69 x.merge(y); 70 BOOST_TEST(x.size() == 1); 71 BOOST_TEST(x.count(10) == 1); 72 BOOST_TEST(y.empty()); 73 74 y.merge(x); 75 BOOST_TEST(x.empty()); 76 BOOST_TEST(y.size() == 1); 77 BOOST_TEST(y.count(10) == 1); 78 79 x.insert(10); 80 x.insert(50); 81 y.insert(70); 82 y.insert(80); 83 x.merge(y); 84 BOOST_TEST_EQ(x.size(), 5u); 85 BOOST_TEST_EQ(y.size(), 0u); 86 BOOST_TEST_EQ(x.count(10), 2u); 87 BOOST_TEST_EQ(x.count(50), 1u); 88 BOOST_TEST_EQ(x.count(70), 1u); 89 BOOST_TEST_EQ(x.count(80), 1u); 90 BOOST_TEST_EQ(y.count(10), 0u); 91 BOOST_TEST_EQ(y.count(50), 0u); 92 BOOST_TEST_EQ(y.count(70), 0u); 93 BOOST_TEST_EQ(y.count(80), 0u); 94 95 test::check_equivalent_keys(x); 96 test::check_equivalent_keys(y); 97 } 98 UNORDERED_AUTO_TEST(merge_set_and_multiset)99 UNORDERED_AUTO_TEST (merge_set_and_multiset) { 100 boost::unordered_set<int> x; 101 boost::unordered_multiset<int> y; 102 103 x.merge(y); 104 BOOST_TEST(x.empty()); 105 BOOST_TEST(y.empty()); 106 107 x.insert(10); 108 x.merge(y); 109 BOOST_TEST(x.size() == 1); 110 BOOST_TEST(x.count(10) == 1); 111 BOOST_TEST(y.empty()); 112 113 y.merge(x); 114 BOOST_TEST(x.empty()); 115 BOOST_TEST(y.size() == 1); 116 BOOST_TEST(y.count(10) == 1); 117 118 x.insert(10); 119 x.insert(50); 120 y.insert(70); 121 y.insert(80); 122 x.merge(y); 123 BOOST_TEST_EQ(x.size(), 4u); 124 BOOST_TEST_EQ(y.size(), 1u); 125 BOOST_TEST_EQ(x.count(10), 1u); 126 BOOST_TEST_EQ(x.count(50), 1u); 127 BOOST_TEST_EQ(x.count(70), 1u); 128 BOOST_TEST_EQ(x.count(80), 1u); 129 BOOST_TEST_EQ(y.count(10), 1u); 130 BOOST_TEST_EQ(y.count(50), 0u); 131 BOOST_TEST_EQ(y.count(70), 0u); 132 BOOST_TEST_EQ(y.count(80), 0u); 133 134 test::check_equivalent_keys(x); 135 test::check_equivalent_keys(y); 136 } 137 138 template <class X1, class X2> merge_empty_test(X1 *,X2 *,test::random_generator generator)139 void merge_empty_test(X1*, X2*, test::random_generator generator) 140 { 141 test::check_instances check_; 142 143 test::random_values<X1> v(1000, generator); 144 X1 x1(v.begin(), v.end()); 145 X2 x2; 146 x1.merge(x2); 147 test::check_container(x1, v); 148 BOOST_TEST(x2.empty()); 149 test::check_equivalent_keys(x1); 150 test::check_equivalent_keys(x2); 151 } 152 153 template <class X> merge_into_empty_test(X *,test::random_generator generator)154 void merge_into_empty_test(X*, test::random_generator generator) 155 { 156 test::check_instances check_; 157 158 test::random_values<X> v(1000, generator); 159 X x1; 160 X x2(v.begin(), v.end()); 161 x1.merge(x2); 162 test::check_container(x1, v); 163 BOOST_TEST(x2.empty()); 164 test::check_equivalent_keys(x1); 165 test::check_equivalent_keys(x2); 166 } 167 168 template <class X1, class X2> merge_into_unique_keys_test(X1 *,X2 *,int hash_equal1,int hash_equal2,test::random_generator generator)169 void merge_into_unique_keys_test(X1*, X2*, int hash_equal1, int hash_equal2, 170 test::random_generator generator) 171 { 172 test::check_instances check_; 173 174 test::random_values<X1> v1(1000, generator); 175 test::random_values<X2> v2(1000, generator); 176 v1.insert(v2.begin(), test::next(v2.begin(), 100)); 177 v2.insert(v1.begin(), test::next(v1.begin(), 100)); 178 179 X1 x1(v1.begin(), v1.end(), 0, test::hash(hash_equal1), 180 test::equal_to(hash_equal1)); 181 X2 x2(v2.begin(), v2.end(), 0, test::hash(hash_equal2), 182 test::equal_to(hash_equal2)); 183 184 test::ordered<X1> tracker1 = test::create_ordered(x1); 185 test::ordered<X2> tracker2 = test::create_ordered(x2); 186 tracker1.insert(v1.begin(), v1.end()); 187 for (typename X2::iterator it = x2.begin(); it != x2.end(); ++it) { 188 if (!tracker1.insert(*it).second) { 189 tracker2.insert(*it); 190 } 191 } 192 193 x1.merge(x2); 194 195 tracker1.compare(x1); 196 tracker2.compare(x2); 197 test::check_equivalent_keys(x1); 198 test::check_equivalent_keys(x2); 199 } 200 201 template <class X1, class X2> merge_into_equiv_keys_test(X1 *,X2 *,int hash_equal1,int hash_equal2,test::random_generator generator)202 void merge_into_equiv_keys_test(X1*, X2*, int hash_equal1, int hash_equal2, 203 test::random_generator generator) 204 { 205 test::check_instances check_; 206 207 test::random_values<X1> v1(1000, generator); 208 test::random_values<X2> v2(1000, generator); 209 v1.insert(v2.begin(), test::next(v2.begin(), 100)); 210 v2.insert(v1.begin(), test::next(v1.begin(), 100)); 211 212 X1 x1(v1.begin(), v1.end(), 0, test::hash(hash_equal1), 213 test::equal_to(hash_equal1)); 214 X2 x2(v2.begin(), v2.end(), 0, test::hash(hash_equal2), 215 test::equal_to(hash_equal2)); 216 x1.merge(x2); 217 218 test::ordered<X1> tracker1 = test::create_ordered(x1); 219 test::ordered<X2> tracker2 = test::create_ordered(x2); 220 tracker1.insert(v1.begin(), v1.end()); 221 tracker2.insert(v2.begin(), v2.end()); 222 tracker1.insert(tracker2.begin(), tracker2.end()); 223 tracker2.clear(); 224 225 tracker1.compare(x1); 226 tracker2.compare(x2); 227 test::check_equivalent_keys(x1); 228 test::check_equivalent_keys(x2); 229 } 230 231 boost::unordered_set<test::movable, test::hash, test::equal_to, 232 std::allocator<test::movable> >* test_set_std_alloc; 233 boost::unordered_multiset<test::movable, test::hash, test::equal_to, 234 std::allocator<test::movable> >* test_multiset_std_alloc; 235 236 boost::unordered_map<test::object, test::object, test::hash, test::equal_to, 237 std::allocator<test::object> >* test_map_std_alloc; 238 boost::unordered_multimap<test::object, test::object, test::hash, 239 test::equal_to, std::allocator<test::object> >* test_multimap_std_alloc; 240 241 boost::unordered_set<test::object, test::hash, test::equal_to, 242 test::allocator1<test::object> >* test_set; 243 boost::unordered_multiset<test::object, test::hash, test::equal_to, 244 test::allocator1<test::object> >* test_multiset; 245 246 boost::unordered_map<test::movable, test::movable, test::hash, test::equal_to, 247 test::allocator2<test::movable> >* test_map; 248 boost::unordered_multimap<test::movable, test::movable, test::hash, 249 test::equal_to, test::allocator2<test::movable> >* test_multimap; 250 251 using test::default_generator; 252 using test::generate_collisions; 253 254 // clang-format off 255 UNORDERED_TEST(merge_empty_test, 256 ((test_set_std_alloc)(test_multiset_std_alloc)) 257 ((test_set_std_alloc)(test_multiset_std_alloc)) 258 ((default_generator)(generate_collisions))) 259 UNORDERED_TEST(merge_empty_test, 260 ((test_map_std_alloc)(test_multimap_std_alloc)) 261 ((test_map_std_alloc)(test_multimap_std_alloc)) 262 ((default_generator)(generate_collisions))) 263 UNORDERED_TEST(merge_empty_test, 264 ((test_set)(test_multiset)) 265 ((test_set)(test_multiset)) 266 ((default_generator)(generate_collisions))) 267 UNORDERED_TEST(merge_empty_test, 268 ((test_map)(test_multimap)) 269 ((test_map)(test_multimap)) 270 ((default_generator)(generate_collisions))) 271 272 UNORDERED_TEST(merge_into_empty_test, 273 ((test_set_std_alloc)(test_multiset_std_alloc)) 274 ((default_generator)(generate_collisions))) 275 UNORDERED_TEST(merge_into_empty_test, 276 ((test_map_std_alloc)(test_multimap_std_alloc)) 277 ((default_generator)(generate_collisions))) 278 UNORDERED_TEST(merge_into_empty_test, 279 ((test_set)(test_multiset)) 280 ((default_generator)(generate_collisions))) 281 UNORDERED_TEST(merge_into_empty_test, 282 ((test_map)(test_multimap)) 283 ((default_generator)(generate_collisions))) 284 285 UNORDERED_TEST(merge_into_unique_keys_test, 286 ((test_set_std_alloc)) 287 ((test_set_std_alloc)(test_multiset_std_alloc)) 288 ((0)(1)(2)) 289 ((0)(1)(2)) 290 ((default_generator)(generate_collisions))) 291 UNORDERED_TEST(merge_into_unique_keys_test, 292 ((test_map_std_alloc)) 293 ((test_map_std_alloc)(test_multimap_std_alloc)) 294 ((0)(1)(2)) 295 ((0)(1)(2)) 296 ((default_generator)(generate_collisions))) 297 UNORDERED_TEST(merge_into_unique_keys_test, 298 ((test_set)) 299 ((test_set)(test_multiset)) 300 ((0)(1)(2)) 301 ((0)(1)(2)) 302 ((default_generator)(generate_collisions))) 303 UNORDERED_TEST(merge_into_unique_keys_test, 304 ((test_map)) 305 ((test_map)(test_multimap)) 306 ((0)(1)(2)) 307 ((0)(1)(2)) 308 ((default_generator)(generate_collisions))) 309 310 UNORDERED_TEST(merge_into_equiv_keys_test, 311 ((test_multiset_std_alloc)) 312 ((test_set_std_alloc)(test_multiset_std_alloc)) 313 ((0)(1)(2)) 314 ((0)(1)(2)) 315 ((default_generator)(generate_collisions))) 316 UNORDERED_TEST(merge_into_equiv_keys_test, 317 ((test_multimap_std_alloc)) 318 ((test_map_std_alloc)(test_multimap_std_alloc)) 319 ((0)(1)(2)) 320 ((0)(1)(2)) 321 ((default_generator)(generate_collisions))) 322 UNORDERED_TEST(merge_into_equiv_keys_test, 323 ((test_multiset)) 324 ((test_set)(test_multiset)) 325 ((0)(1)(2)) 326 ((0)(1)(2)) 327 ((default_generator)(generate_collisions))) 328 UNORDERED_TEST(merge_into_equiv_keys_test, 329 ((test_multimap)) 330 ((test_map)(test_multimap)) 331 ((0)(1)(2)) 332 ((0)(1)(2)) 333 ((default_generator)(generate_collisions))) 334 // clang-format on 335 } 336 337 RUN_TESTS() 338