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