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 // clang-format off 7 #include "../helpers/prefix.hpp" 8 #include <boost/unordered_map.hpp> 9 #include <boost/unordered_set.hpp> 10 #include "../helpers/postfix.hpp" 11 // clang-format on 12 13 #include "../helpers/equivalent.hpp" 14 #include "../helpers/helpers.hpp" 15 #include "../helpers/invariants.hpp" 16 #include "../helpers/random_values.hpp" 17 #include "../helpers/test.hpp" 18 #include "../helpers/tracker.hpp" 19 #include "../objects/test.hpp" 20 21 namespace extract_tests { 22 23 test::seed_t initialize_seed(85638); 24 25 template <class Container> extract_tests1(Container *,test::random_generator generator)26 void extract_tests1(Container*, test::random_generator generator) 27 { 28 BOOST_LIGHTWEIGHT_TEST_OSTREAM << "Extract by key.\n"; 29 { 30 test::check_instances check_; 31 32 test::random_values<Container> v(1000, generator); 33 Container x(v.begin(), v.end()); 34 int iterations = 0; 35 for (typename test::random_values<Container>::iterator it = v.begin(); 36 it != v.end(); ++it) { 37 std::size_t count = x.count(test::get_key<Container>(*it)); 38 std::size_t old_size = x.size(); 39 std::size_t new_count = count ? count - 1 : count; 40 std::size_t new_size = count ? old_size - 1 : old_size; 41 typename Container::node_type n = 42 x.extract(test::get_key<Container>(*it)); 43 BOOST_TEST((n ? true : false) == (count ? true : false)); 44 BOOST_TEST(x.size() == new_size); 45 BOOST_TEST(x.count(test::get_key<Container>(*it)) == new_count); 46 if (!new_count) { 47 BOOST_TEST(x.find(test::get_key<Container>(*it)) == x.end()); 48 } else { 49 BOOST_TEST(x.find(test::get_key<Container>(*it)) != x.end()); 50 } 51 if (++iterations % 20 == 0) 52 test::check_equivalent_keys(x); 53 } 54 BOOST_TEST(x.empty()); 55 } 56 57 BOOST_LIGHTWEIGHT_TEST_OSTREAM << "extract(begin()).\n"; 58 { 59 test::check_instances check_; 60 61 test::random_values<Container> v(1000, generator); 62 Container x(v.begin(), v.end()); 63 std::size_t size = x.size(); 64 int iterations = 0; 65 while (size > 0 && !x.empty()) { 66 typename Container::key_type key = test::get_key<Container>(*x.begin()); 67 std::size_t count = x.count(key); 68 typename Container::node_type n = x.extract(x.begin()); 69 BOOST_TEST(n); 70 --size; 71 BOOST_TEST(x.count(key) == count - 1); 72 BOOST_TEST(x.size() == size); 73 if (++iterations % 20 == 0) 74 test::check_equivalent_keys(x); 75 } 76 BOOST_TEST(x.empty()); 77 } 78 79 BOOST_LIGHTWEIGHT_TEST_OSTREAM << "extract(random position).\n"; 80 { 81 test::check_instances check_; 82 83 test::random_values<Container> v(1000, generator); 84 Container x(v.begin(), v.end()); 85 std::size_t size = x.size(); 86 int iterations = 0; 87 while (size > 0 && !x.empty()) { 88 using namespace std; 89 int index = rand() % (int)x.size(); 90 typename Container::const_iterator prev, pos, next; 91 if (index == 0) { 92 prev = pos = x.begin(); 93 } else { 94 prev = test::next(x.begin(), index - 1); 95 pos = test::next(prev); 96 } 97 next = test::next(pos); 98 typename Container::key_type key = test::get_key<Container>(*pos); 99 std::size_t count = x.count(key); 100 typename Container::node_type n = x.extract(pos); 101 BOOST_TEST(n); 102 --size; 103 if (size > 0) 104 BOOST_TEST(index == 0 ? next == x.begin() : next == test::next(prev)); 105 BOOST_TEST(x.count(key) == count - 1); 106 BOOST_TEST(x.size() == size); 107 if (++iterations % 20 == 0) 108 test::check_equivalent_keys(x); 109 } 110 BOOST_TEST(x.empty()); 111 } 112 113 BOOST_LIGHTWEIGHT_TEST_OSTREAM << "\n"; 114 } 115 116 boost::unordered_set<test::object, test::hash, test::equal_to, 117 test::allocator1<test::object> >* test_set; 118 boost::unordered_multiset<test::object, test::hash, test::equal_to, 119 test::allocator2<test::object> >* test_multiset; 120 boost::unordered_map<test::object, test::object, test::hash, test::equal_to, 121 test::allocator1<test::object> >* test_map; 122 boost::unordered_multimap<test::object, test::object, test::hash, 123 test::equal_to, test::allocator2<test::object> >* test_multimap; 124 125 using test::default_generator; 126 using test::generate_collisions; 127 128 UNORDERED_TEST( 129 extract_tests1, ((test_set)(test_multiset)(test_map)(test_multimap))( 130 (default_generator)(generate_collisions))) 131 } 132 133 RUN_TESTS() 134