]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
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 | ||
b32b8144 | 6 | // clang-format off |
7c673cae FG |
7 | #include "../helpers/prefix.hpp" |
8 | #include <boost/unordered_set.hpp> | |
9 | #include <boost/unordered_map.hpp> | |
10 | #include "../helpers/postfix.hpp" | |
b32b8144 | 11 | // clang-format on |
7c673cae FG |
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 | ||
b32b8144 | 19 | namespace find_tests { |
7c673cae | 20 | |
b32b8144 | 21 | test::seed_t initialize_seed(78937); |
7c673cae | 22 | |
b32b8144 FG |
23 | template <class X> void find_tests1(X*, test::random_generator generator) |
24 | { | |
11fdf7f2 | 25 | typedef typename X::iterator iterator; |
7c673cae FG |
26 | |
27 | { | |
b32b8144 FG |
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 | ||
11fdf7f2 | 36 | for (typename test::ordered<X>::const_iterator it1 = tracker.begin(); |
b32b8144 | 37 | it1 != tracker.end(); ++it1) { |
11fdf7f2 TL |
38 | typename X::key_type key = test::get_key<X>(*it1); |
39 | typename X::const_iterator const_pos = x_const.find(key); | |
b32b8144 FG |
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), | |
11fdf7f2 | 50 | (typename X::value_type*)0); |
b32b8144 | 51 | test::compare_pairs(x_const.equal_range(key), tracker.equal_range(key), |
11fdf7f2 | 52 | (typename X::value_type*)0); |
b32b8144 FG |
53 | } |
54 | ||
55 | test::random_values<X> v2(500, generator); | |
11fdf7f2 | 56 | for (typename test::random_values<X>::const_iterator it2 = v2.begin(); |
b32b8144 | 57 | it2 != v2.end(); ++it2) { |
11fdf7f2 | 58 | typename X::key_type key = test::get_key<X>(*it2); |
b32b8144 FG |
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); | |
7c673cae | 65 | } |
b32b8144 | 66 | } |
7c673cae FG |
67 | } |
68 | ||
69 | { | |
b32b8144 FG |
70 | test::check_instances check_; |
71 | ||
72 | X x; | |
73 | ||
74 | test::random_values<X> v2(5, generator); | |
11fdf7f2 | 75 | for (typename test::random_values<X>::const_iterator it3 = v2.begin(); |
b32b8144 | 76 | it3 != v2.end(); ++it3) { |
11fdf7f2 | 77 | typename X::key_type key = test::get_key<X>(*it3); |
b32b8144 FG |
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 | } | |
7c673cae | 83 | } |
b32b8144 | 84 | } |
7c673cae | 85 | |
b32b8144 FG |
86 | struct compatible_key |
87 | { | |
7c673cae | 88 | test::object o_; |
b32b8144 | 89 | |
7c673cae | 90 | compatible_key(test::object const& o) : o_(o) {} |
b32b8144 | 91 | }; |
7c673cae | 92 | |
b32b8144 FG |
93 | struct compatible_hash |
94 | { | |
7c673cae FG |
95 | test::hash hash_; |
96 | ||
b32b8144 FG |
97 | std::size_t operator()(compatible_key const& k) const |
98 | { | |
99 | return hash_(k.o_); | |
7c673cae | 100 | } |
b32b8144 | 101 | }; |
7c673cae | 102 | |
b32b8144 FG |
103 | struct compatible_predicate |
104 | { | |
7c673cae FG |
105 | test::equal_to equal_; |
106 | ||
b32b8144 FG |
107 | bool operator()(compatible_key const& k1, compatible_key const& k2) const |
108 | { | |
109 | return equal_(k1.o_, k2.o_); | |
7c673cae | 110 | } |
b32b8144 | 111 | }; |
7c673cae | 112 | |
b32b8144 FG |
113 | template <class X> |
114 | void find_compatible_keys_test(X*, test::random_generator generator) | |
115 | { | |
11fdf7f2 | 116 | typedef typename test::random_values<X>::iterator value_iterator; |
7c673cae FG |
117 | test::random_values<X> v(500, generator); |
118 | X x(v.begin(), v.end()); | |
b32b8144 | 119 | |
7c673cae FG |
120 | compatible_hash h; |
121 | compatible_predicate eq; | |
b32b8144 FG |
122 | |
123 | for (value_iterator it = v.begin(), end = v.end(); it != end; ++it) { | |
11fdf7f2 | 124 | typename X::key_type key = test::get_key<X>(*it); |
b32b8144 | 125 | BOOST_TEST(x.find(key) == x.find(compatible_key(key), h, eq)); |
7c673cae FG |
126 | } |
127 | ||
128 | test::random_values<X> v2(20, generator); | |
b32b8144 FG |
129 | |
130 | for (value_iterator it = v2.begin(), end = v2.end(); it != end; ++it) { | |
11fdf7f2 | 131 | typename X::key_type key = test::get_key<X>(*it); |
b32b8144 | 132 | BOOST_TEST(x.find(key) == x.find(compatible_key(key), h, eq)); |
7c673cae | 133 | } |
b32b8144 | 134 | } |
7c673cae | 135 | |
b32b8144 | 136 | boost::unordered_set<test::object, test::hash, test::equal_to, |
7c673cae | 137 | test::allocator2<test::object> >* test_set; |
b32b8144 | 138 | boost::unordered_multiset<test::object, test::hash, test::equal_to, |
7c673cae | 139 | test::allocator1<test::object> >* test_multiset; |
b32b8144 | 140 | boost::unordered_map<test::object, test::object, test::hash, test::equal_to, |
7c673cae | 141 | test::allocator2<test::object> >* test_map; |
b32b8144 FG |
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))) | |
7c673cae FG |
155 | } |
156 | ||
157 | RUN_TESTS() |