]>
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 | ||
6 | // The code for erasing elements from containers with equivalent keys is very | |
7 | // hairy with several tricky edge cases - so explicitly test each one. | |
8 | ||
9 | #include "../helpers/prefix.hpp" | |
10 | #include <boost/unordered_map.hpp> | |
11 | #include "../helpers/postfix.hpp" | |
12 | ||
13 | #include "../helpers/test.hpp" | |
14 | #include "../helpers/list.hpp" | |
15 | #include "../helpers/invariants.hpp" | |
16 | #include "../helpers/helpers.hpp" | |
17 | #include <set> | |
18 | #include <iostream> | |
19 | #include <iterator> | |
20 | #include "../objects/test.hpp" | |
21 | ||
22 | #if BOOST_WORKAROUND(BOOST_MSVC, < 1400) | |
23 | #pragma warning(disable:4267) // conversion from 'size_t' to 'unsigned int', | |
24 | // possible loss of data. | |
25 | #endif | |
26 | ||
27 | struct write_pair_type | |
28 | { | |
29 | template <class X1, class X2> | |
30 | void operator()(std::pair<X1, X2> const& x) const | |
31 | { | |
32 | std::cout<<"("<<x.first<<","<<x.second<<")"; | |
33 | } | |
34 | } write_pair; | |
35 | ||
36 | template <class Container> | |
37 | void write_container(Container const& x) | |
38 | { | |
39 | std::for_each(x.begin(), x.end(), write_pair); | |
40 | std::cout<<"\n"; | |
41 | } | |
42 | ||
43 | // Make everything collide - for testing erase in a single bucket. | |
44 | struct collision_hash | |
45 | { | |
46 | std::size_t operator()(int) const { return 0; } | |
47 | }; | |
48 | ||
49 | // For testing erase in 2 buckets. | |
50 | struct collision2_hash | |
51 | { | |
52 | std::size_t operator()(int x) const { return static_cast<std::size_t>(x & 1); } | |
53 | }; | |
54 | ||
55 | // For testing erase in lots of buckets. | |
56 | struct collision3_hash | |
57 | { | |
58 | std::size_t operator()(int x) const { return static_cast<std::size_t>(x); } | |
59 | }; | |
60 | ||
61 | typedef boost::unordered_multimap<int, int, | |
62 | collision_hash, std::equal_to<int>, | |
63 | test::allocator1<std::pair<int const, int> > > collide_map; | |
64 | typedef boost::unordered_multimap<int, int, | |
65 | collision2_hash, std::equal_to<int>, | |
66 | test::allocator2<std::pair<int const, int> > > collide_map2; | |
67 | typedef boost::unordered_multimap<int, int, | |
68 | collision3_hash, std::equal_to<int>, | |
69 | test::allocator2<std::pair<int const, int> > > collide_map3; | |
70 | typedef collide_map::value_type collide_value; | |
71 | typedef test::list<collide_value> collide_list; | |
72 | ||
73 | UNORDERED_AUTO_TEST(empty_range_tests) | |
74 | { | |
75 | collide_map x; | |
76 | x.erase(x.begin(), x.end()); | |
77 | x.erase(x.begin(), x.begin()); | |
78 | x.erase(x.end(), x.end()); | |
79 | test::check_equivalent_keys(x); | |
80 | } | |
81 | ||
82 | UNORDERED_AUTO_TEST(single_item_tests) | |
83 | { | |
84 | collide_list init; | |
85 | init.push_back(collide_value(1,1)); | |
86 | ||
87 | collide_map x(init.begin(), init.end()); | |
88 | x.erase(x.begin(), x.begin()); | |
89 | BOOST_TEST(x.count(1) == 1 && x.size() == 1); | |
90 | test::check_equivalent_keys(x); | |
91 | x.erase(x.end(), x.end()); | |
92 | BOOST_TEST(x.count(1) == 1 && x.size() == 1); | |
93 | test::check_equivalent_keys(x); | |
94 | x.erase(x.begin(), x.end()); | |
95 | BOOST_TEST(x.count(1) == 0 && x.size() == 0); | |
96 | test::check_equivalent_keys(x); | |
97 | } | |
98 | ||
99 | UNORDERED_AUTO_TEST(two_equivalent_item_tests) | |
100 | { | |
101 | collide_list init; | |
102 | init.push_back(collide_value(1,1)); | |
103 | init.push_back(collide_value(1,2)); | |
104 | ||
105 | { | |
106 | collide_map x(init.begin(), init.end()); | |
107 | x.erase(x.begin(), x.end()); | |
108 | BOOST_TEST(x.count(1) == 0 && x.size() == 0); | |
109 | test::check_equivalent_keys(x); | |
110 | } | |
111 | ||
112 | { | |
113 | collide_map x(init.begin(), init.end()); | |
114 | int value = test::next(x.begin())->second; | |
115 | x.erase(x.begin(), test::next(x.begin())); | |
116 | BOOST_TEST(x.count(1) == 1 && x.size() == 1 && | |
117 | x.begin()->first == 1 && x.begin()->second == value); | |
118 | test::check_equivalent_keys(x); | |
119 | } | |
120 | ||
121 | { | |
122 | collide_map x(init.begin(), init.end()); | |
123 | int value = x.begin()->second; | |
124 | x.erase(test::next(x.begin()), x.end()); | |
125 | BOOST_TEST(x.count(1) == 1 && x.size() == 1 && | |
126 | x.begin()->first == 1 && x.begin()->second == value); | |
127 | test::check_equivalent_keys(x); | |
128 | } | |
129 | } | |
130 | ||
131 | // More automated tests... | |
132 | ||
133 | template<class Range1, class Range2> | |
134 | bool compare(Range1 const& x, Range2 const& y) | |
135 | { | |
136 | collide_list a(x.begin(), x.end()); | |
137 | collide_list b(y.begin(), y.end()); | |
138 | a.sort(); | |
139 | b.sort(); | |
140 | return a == b; | |
141 | } | |
142 | ||
143 | template <class Container> | |
144 | bool general_erase_range_test(Container& x, std::size_t start, std::size_t end) | |
145 | { | |
146 | collide_list l(x.begin(), x.end()); | |
147 | ||
148 | l.erase(test::next(l.begin(), start), test::next(l.begin(), end)); | |
149 | x.erase(test::next(x.begin(), start), test::next(x.begin(), end)); | |
150 | ||
151 | test::check_equivalent_keys(x); | |
152 | return compare(l, x); | |
153 | } | |
154 | ||
155 | template <class Container> | |
156 | void erase_subrange_tests(Container const& x) | |
157 | { | |
158 | for(std::size_t length = 0; length < x.size(); ++length) { | |
159 | for(std::size_t position = 0; position < x.size() - length; ++position) | |
160 | { | |
161 | Container y(x); | |
162 | collide_list init(y.begin(), y.end()); | |
163 | if(!general_erase_range_test(y, position, position + length)) { | |
164 | BOOST_ERROR("general_erase_range_test failed."); | |
165 | std::cout<<"Erase: ["<<position<<","<<position + length<<")\n"; | |
166 | write_container(init); | |
167 | write_container(y); | |
168 | } | |
169 | } | |
170 | } | |
171 | } | |
172 | ||
173 | template <class Container> | |
174 | void x_by_y_erase_range_tests(Container*, int values, int duplicates) | |
175 | { | |
176 | Container y; | |
177 | ||
178 | for(int i = 0; i < values; ++i) { | |
179 | for(int j = 0; j < duplicates; ++j) { | |
180 | y.insert(collide_value(i, j)); | |
181 | } | |
182 | } | |
183 | ||
184 | std::cout<<"Values: "<<values<<", Duplicates: "<<duplicates<<"\n"; | |
185 | erase_subrange_tests(y); | |
186 | } | |
187 | ||
188 | template <class Container> | |
189 | void exhaustive_erase_tests(Container* x, int num_values, | |
190 | int num_duplicated) | |
191 | { | |
192 | for(int i = 0; i < num_values; ++i) { | |
193 | for(int j = 0; j < num_duplicated; ++j) { | |
194 | x_by_y_erase_range_tests(x, i, j); | |
195 | } | |
196 | } | |
197 | } | |
198 | ||
199 | UNORDERED_AUTO_TEST(exhaustive_collide_tests) | |
200 | { | |
201 | std::cout<<"exhaustive_collide_tests:\n"; | |
202 | collide_map m; | |
203 | exhaustive_erase_tests((collide_map*) 0, 4, 4); | |
204 | std::cout<<"\n"; | |
205 | } | |
206 | ||
207 | UNORDERED_AUTO_TEST(exhaustive_collide2_tests) | |
208 | { | |
209 | std::cout<<"exhaustive_collide2_tests:\n"; | |
210 | exhaustive_erase_tests((collide_map2*) 0, 8, 4); | |
211 | std::cout<<"\n"; | |
212 | } | |
213 | ||
214 | UNORDERED_AUTO_TEST(exhaustive_collide3_tests) | |
215 | { | |
216 | std::cout<<"exhaustive_collide3_tests:\n"; | |
217 | exhaustive_erase_tests((collide_map3*) 0, 8, 4); | |
218 | std::cout<<"\n"; | |
219 | } | |
220 | ||
221 | RUN_TESTS() |