1 2 // Copyright 2006-2009 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_set.hpp> 9 #include <boost/unordered_map.hpp> 10 #include "../helpers/postfix.hpp" 11 // clang-format on 12 13 #include "../helpers/test.hpp" 14 #include "../objects/test.hpp" 15 #include "../helpers/random_values.hpp" 16 #include "../helpers/tracker.hpp" 17 #include "../helpers/helpers.hpp" 18 19 namespace find_tests { 20 21 test::seed_t initialize_seed(78937); 22 find_tests1(X *,test::random_generator generator)23 template <class X> void find_tests1(X*, test::random_generator generator) 24 { 25 typedef typename X::iterator iterator; 26 27 { 28 test::check_instances check_; 29 30 test::random_values<X> v(500, generator); 31 X x(v.begin(), v.end()); 32 X const& x_const = x; 33 test::ordered<X> tracker = test::create_ordered(x); 34 tracker.insert_range(v.begin(), v.end()); 35 36 for (typename test::ordered<X>::const_iterator it1 = tracker.begin(); 37 it1 != tracker.end(); ++it1) { 38 typename X::key_type key = test::get_key<X>(*it1); 39 typename X::const_iterator const_pos = x_const.find(key); 40 iterator pos = x.find(key); 41 BOOST_TEST(const_pos != x_const.end()); 42 BOOST_TEST(const_pos != x_const.end() && 43 x_const.key_eq()(key, test::get_key<X>(*const_pos))); 44 BOOST_TEST(pos != x.end()); 45 BOOST_TEST(pos != x.end() && x.key_eq()(key, test::get_key<X>(*pos))); 46 47 BOOST_TEST(x.count(key) == tracker.count(key)); 48 49 test::compare_pairs(x.equal_range(key), tracker.equal_range(key), 50 (typename X::value_type*)0); 51 test::compare_pairs(x_const.equal_range(key), tracker.equal_range(key), 52 (typename X::value_type*)0); 53 } 54 55 test::random_values<X> v2(500, generator); 56 for (typename test::random_values<X>::const_iterator it2 = v2.begin(); 57 it2 != v2.end(); ++it2) { 58 typename X::key_type key = test::get_key<X>(*it2); 59 if (tracker.find(test::get_key<X>(key)) == tracker.end()) { 60 BOOST_TEST(x.find(key) == x.end()); 61 BOOST_TEST(x_const.find(key) == x_const.end()); 62 BOOST_TEST(x.count(key) == 0); 63 std::pair<iterator, iterator> range = x.equal_range(key); 64 BOOST_TEST(range.first == range.second); 65 } 66 } 67 } 68 69 { 70 test::check_instances check_; 71 72 X x; 73 74 test::random_values<X> v2(5, generator); 75 for (typename test::random_values<X>::const_iterator it3 = v2.begin(); 76 it3 != v2.end(); ++it3) { 77 typename X::key_type key = test::get_key<X>(*it3); 78 BOOST_TEST(x.find(key) == x.end()); 79 BOOST_TEST(x.count(key) == 0); 80 std::pair<iterator, iterator> range = x.equal_range(key); 81 BOOST_TEST(range.first == range.second); 82 } 83 } 84 } 85 86 struct compatible_key 87 { 88 test::object o_; 89 compatible_keyfind_tests::compatible_key90 compatible_key(test::object const& o) : o_(o) {} 91 }; 92 93 struct compatible_hash 94 { 95 test::hash hash_; 96 operator ()find_tests::compatible_hash97 std::size_t operator()(compatible_key const& k) const 98 { 99 return hash_(k.o_); 100 } 101 }; 102 103 struct compatible_predicate 104 { 105 test::equal_to equal_; 106 operator ()find_tests::compatible_predicate107 bool operator()(compatible_key const& k1, compatible_key const& k2) const 108 { 109 return equal_(k1.o_, k2.o_); 110 } 111 }; 112 113 template <class X> find_compatible_keys_test(X *,test::random_generator generator)114 void find_compatible_keys_test(X*, test::random_generator generator) 115 { 116 typedef typename test::random_values<X>::iterator value_iterator; 117 test::random_values<X> v(500, generator); 118 X x(v.begin(), v.end()); 119 120 compatible_hash h; 121 compatible_predicate eq; 122 123 for (value_iterator it = v.begin(), end = v.end(); it != end; ++it) { 124 typename X::key_type key = test::get_key<X>(*it); 125 BOOST_TEST(x.find(key) == x.find(compatible_key(key), h, eq)); 126 } 127 128 test::random_values<X> v2(20, generator); 129 130 for (value_iterator it = v2.begin(), end = v2.end(); it != end; ++it) { 131 typename X::key_type key = test::get_key<X>(*it); 132 BOOST_TEST(x.find(key) == x.find(compatible_key(key), h, eq)); 133 } 134 } 135 136 boost::unordered_set<test::object, test::hash, test::equal_to, 137 test::allocator2<test::object> >* test_set; 138 boost::unordered_multiset<test::object, test::hash, test::equal_to, 139 test::allocator1<test::object> >* test_multiset; 140 boost::unordered_map<test::object, test::object, test::hash, test::equal_to, 141 test::allocator2<test::object> >* test_map; 142 boost::unordered_multimap<test::object, test::object, test::hash, 143 test::equal_to, test::allocator1<test::object> >* test_multimap; 144 145 using test::default_generator; 146 using test::generate_collisions; 147 using test::limited_range; 148 149 UNORDERED_TEST( 150 find_tests1, ((test_set)(test_multiset)(test_map)(test_multimap))( 151 (default_generator)(generate_collisions)(limited_range))) 152 UNORDERED_TEST(find_compatible_keys_test, 153 ((test_set)(test_multiset)(test_map)(test_multimap))( 154 (default_generator)(generate_collisions)(limited_range))) 155 } 156 157 RUN_TESTS() 158