]>
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/equivalent.hpp" | |
18 | #include "../helpers/helpers.hpp" | |
19 | #include "../helpers/invariants.hpp" | |
20 | #include <vector> | |
7c673cae FG |
21 | #include <cstdlib> |
22 | ||
b32b8144 | 23 | namespace erase_tests { |
7c673cae | 24 | |
b32b8144 | 25 | test::seed_t initialize_seed(85638); |
7c673cae | 26 | |
b32b8144 FG |
27 | template <class Container> |
28 | void erase_tests1(Container*, test::random_generator generator) | |
29 | { | |
7c673cae FG |
30 | typedef BOOST_DEDUCED_TYPENAME Container::iterator iterator; |
31 | typedef BOOST_DEDUCED_TYPENAME Container::const_iterator c_iterator; | |
32 | ||
b32b8144 | 33 | BOOST_LIGHTWEIGHT_TEST_OSTREAM << "Erase by key.\n"; |
7c673cae | 34 | { |
b32b8144 FG |
35 | test::check_instances check_; |
36 | ||
37 | test::random_values<Container> v(1000, generator); | |
38 | Container x(v.begin(), v.end()); | |
39 | int iterations = 0; | |
40 | for (BOOST_DEDUCED_TYPENAME test::random_values<Container>::iterator it = | |
41 | v.begin(); | |
42 | it != v.end(); ++it) { | |
43 | std::size_t count = x.count(test::get_key<Container>(*it)); | |
44 | std::size_t old_size = x.size(); | |
45 | BOOST_TEST(count == x.erase(test::get_key<Container>(*it))); | |
46 | BOOST_TEST(x.size() == old_size - count); | |
47 | BOOST_TEST(x.count(test::get_key<Container>(*it)) == 0); | |
48 | BOOST_TEST(x.find(test::get_key<Container>(*it)) == x.end()); | |
49 | if (++iterations % 20 == 0) | |
50 | test::check_equivalent_keys(x); | |
51 | } | |
7c673cae FG |
52 | } |
53 | ||
b32b8144 | 54 | BOOST_LIGHTWEIGHT_TEST_OSTREAM << "erase(begin()).\n"; |
7c673cae | 55 | { |
b32b8144 FG |
56 | test::check_instances check_; |
57 | ||
58 | test::random_values<Container> v(1000, generator); | |
59 | Container x(v.begin(), v.end()); | |
60 | std::size_t size = x.size(); | |
61 | int iterations = 0; | |
62 | while (size > 0 && !x.empty()) { | |
63 | BOOST_DEDUCED_TYPENAME Container::key_type key = | |
64 | test::get_key<Container>(*x.begin()); | |
65 | std::size_t count = x.count(key); | |
66 | iterator pos = x.erase(x.begin()); | |
67 | --size; | |
68 | BOOST_TEST(pos == x.begin()); | |
69 | BOOST_TEST(x.count(key) == count - 1); | |
70 | BOOST_TEST(x.size() == size); | |
71 | if (++iterations % 20 == 0) | |
72 | test::check_equivalent_keys(x); | |
73 | } | |
74 | BOOST_TEST(x.empty()); | |
7c673cae FG |
75 | } |
76 | ||
b32b8144 | 77 | BOOST_LIGHTWEIGHT_TEST_OSTREAM << "erase(random position).\n"; |
7c673cae | 78 | { |
b32b8144 FG |
79 | test::check_instances check_; |
80 | ||
81 | test::random_values<Container> v(1000, generator); | |
82 | Container x(v.begin(), v.end()); | |
83 | std::size_t size = x.size(); | |
84 | int iterations = 0; | |
85 | while (size > 0 && !x.empty()) { | |
86 | std::size_t index = test::random_value(x.size()); | |
87 | c_iterator prev, pos, next; | |
88 | if (index == 0) { | |
89 | prev = pos = x.begin(); | |
90 | } else { | |
91 | prev = test::next(x.begin(), index - 1); | |
92 | pos = test::next(prev); | |
7c673cae | 93 | } |
b32b8144 FG |
94 | next = test::next(pos); |
95 | BOOST_DEDUCED_TYPENAME Container::key_type key = | |
96 | test::get_key<Container>(*pos); | |
97 | std::size_t count = x.count(key); | |
98 | BOOST_TEST(count > 0); | |
99 | BOOST_TEST(next == x.erase(pos)); | |
100 | --size; | |
101 | if (size > 0) | |
102 | BOOST_TEST(index == 0 ? next == x.begin() : next == test::next(prev)); | |
103 | BOOST_TEST(x.count(key) == count - 1); | |
104 | if (x.count(key) != count - 1) { | |
105 | BOOST_LIGHTWEIGHT_TEST_OSTREAM << count << " => " << x.count(key) | |
106 | << std::endl; | |
107 | } | |
108 | BOOST_TEST(x.size() == size); | |
109 | if (++iterations % 20 == 0) | |
110 | test::check_equivalent_keys(x); | |
111 | } | |
112 | BOOST_TEST(x.empty()); | |
7c673cae FG |
113 | } |
114 | ||
b32b8144 | 115 | BOOST_LIGHTWEIGHT_TEST_OSTREAM << "erase(ranges).\n"; |
7c673cae | 116 | { |
b32b8144 | 117 | test::check_instances check_; |
7c673cae | 118 | |
b32b8144 FG |
119 | test::random_values<Container> v(500, generator); |
120 | Container x(v.begin(), v.end()); | |
7c673cae | 121 | |
b32b8144 | 122 | std::size_t size = x.size(); |
7c673cae | 123 | |
b32b8144 FG |
124 | // I'm actually stretching it a little here, as the standard says it |
125 | // returns 'the iterator immediately following the erase elements' | |
126 | // and if nothing is erased, then there's nothing to follow. But I | |
127 | // think this is the only sensible option... | |
128 | BOOST_TEST(x.erase(x.end(), x.end()) == x.end()); | |
129 | BOOST_TEST(x.erase(x.begin(), x.begin()) == x.begin()); | |
130 | BOOST_TEST(x.size() == size); | |
131 | test::check_equivalent_keys(x); | |
7c673cae | 132 | |
b32b8144 FG |
133 | BOOST_TEST(x.erase(x.begin(), x.end()) == x.end()); |
134 | BOOST_TEST(x.empty()); | |
135 | BOOST_TEST(x.begin() == x.end()); | |
136 | test::check_equivalent_keys(x); | |
7c673cae | 137 | |
b32b8144 FG |
138 | BOOST_TEST(x.erase(x.begin(), x.end()) == x.begin()); |
139 | test::check_equivalent_keys(x); | |
7c673cae FG |
140 | } |
141 | ||
b32b8144 | 142 | BOOST_LIGHTWEIGHT_TEST_OSTREAM << "erase(random ranges).\n"; |
7c673cae | 143 | { |
b32b8144 FG |
144 | test::check_instances check_; |
145 | Container x; | |
7c673cae | 146 | |
b32b8144 | 147 | for (int i = 0; i < 100; ++i) { |
7c673cae | 148 | test::random_values<Container> v(1000, generator); |
b32b8144 FG |
149 | x.insert(v.begin(), v.end()); |
150 | ||
151 | // Note that erase only invalidates the erased iterators. | |
152 | std::vector<c_iterator> iterators; | |
153 | for (c_iterator it = x.cbegin(); it != x.cend(); ++it) { | |
154 | iterators.push_back(it); | |
155 | } | |
156 | iterators.push_back(x.cend()); | |
157 | ||
158 | while (iterators.size() > 1) { | |
159 | std::size_t start = test::random_value(iterators.size()); | |
160 | std::size_t length = test::random_value(iterators.size() - start); | |
161 | x.erase(iterators[start], iterators[start + length]); | |
162 | iterators.erase(test::next(iterators.begin(), start), | |
163 | test::next(iterators.begin(), start + length)); | |
164 | ||
165 | BOOST_TEST(x.size() == iterators.size() - 1); | |
166 | BOOST_DEDUCED_TYPENAME std::vector<c_iterator>::const_iterator i2 = | |
167 | iterators.begin(); | |
168 | for (c_iterator i1 = x.cbegin(); i1 != x.cend(); ++i1) { | |
169 | BOOST_TEST(i1 == *i2); | |
170 | ++i2; | |
171 | } | |
172 | BOOST_TEST(x.cend() == *i2); | |
173 | ||
174 | test::check_equivalent_keys(x); | |
7c673cae FG |
175 | } |
176 | BOOST_TEST(x.empty()); | |
b32b8144 | 177 | } |
7c673cae FG |
178 | } |
179 | ||
b32b8144 | 180 | BOOST_LIGHTWEIGHT_TEST_OSTREAM << "quick_erase(begin()).\n"; |
7c673cae | 181 | { |
b32b8144 FG |
182 | test::check_instances check_; |
183 | ||
184 | test::random_values<Container> v(1000, generator); | |
185 | Container x(v.begin(), v.end()); | |
186 | std::size_t size = x.size(); | |
187 | int iterations = 0; | |
188 | while (size > 0 && !x.empty()) { | |
189 | BOOST_DEDUCED_TYPENAME Container::key_type key = | |
190 | test::get_key<Container>(*x.begin()); | |
191 | std::size_t count = x.count(key); | |
192 | x.quick_erase(x.begin()); | |
193 | --size; | |
194 | BOOST_TEST(x.count(key) == count - 1); | |
195 | BOOST_TEST(x.size() == size); | |
196 | if (++iterations % 20 == 0) | |
197 | test::check_equivalent_keys(x); | |
198 | } | |
199 | BOOST_TEST(x.empty()); | |
200 | } | |
7c673cae | 201 | |
b32b8144 FG |
202 | BOOST_LIGHTWEIGHT_TEST_OSTREAM << "quick_erase(random position).\n"; |
203 | { | |
204 | test::check_instances check_; | |
205 | ||
206 | test::random_values<Container> v(1000, generator); | |
207 | Container x(v.begin(), v.end()); | |
208 | std::size_t size = x.size(); | |
209 | int iterations = 0; | |
210 | while (size > 0 && !x.empty()) { | |
211 | std::size_t index = test::random_value(x.size()); | |
212 | BOOST_DEDUCED_TYPENAME Container::const_iterator prev, pos, next; | |
213 | if (index == 0) { | |
214 | prev = pos = x.begin(); | |
215 | } else { | |
216 | prev = test::next(x.begin(), index - 1); | |
217 | pos = test::next(prev); | |
7c673cae | 218 | } |
b32b8144 FG |
219 | next = test::next(pos); |
220 | BOOST_DEDUCED_TYPENAME Container::key_type key = | |
221 | test::get_key<Container>(*pos); | |
222 | std::size_t count = x.count(key); | |
223 | BOOST_TEST(count > 0); | |
224 | x.quick_erase(pos); | |
225 | --size; | |
226 | if (size > 0) | |
227 | BOOST_TEST(index == 0 ? next == x.begin() : next == test::next(prev)); | |
228 | BOOST_TEST(x.count(key) == count - 1); | |
229 | if (x.count(key) != count - 1) { | |
230 | BOOST_LIGHTWEIGHT_TEST_OSTREAM << count << " => " << x.count(key) | |
231 | << std::endl; | |
232 | } | |
233 | BOOST_TEST(x.size() == size); | |
234 | if (++iterations % 20 == 0) | |
235 | test::check_equivalent_keys(x); | |
236 | } | |
237 | BOOST_TEST(x.empty()); | |
7c673cae FG |
238 | } |
239 | ||
b32b8144 | 240 | BOOST_LIGHTWEIGHT_TEST_OSTREAM << "clear().\n"; |
7c673cae | 241 | { |
b32b8144 | 242 | test::check_instances check_; |
7c673cae | 243 | |
b32b8144 FG |
244 | test::random_values<Container> v(500, generator); |
245 | Container x(v.begin(), v.end()); | |
246 | x.clear(); | |
247 | BOOST_TEST(x.empty()); | |
248 | BOOST_TEST(x.begin() == x.end()); | |
7c673cae FG |
249 | } |
250 | ||
b32b8144 FG |
251 | BOOST_LIGHTWEIGHT_TEST_OSTREAM << "\n"; |
252 | } | |
7c673cae | 253 | |
b32b8144 | 254 | boost::unordered_set<test::object, test::hash, test::equal_to, |
7c673cae | 255 | test::allocator1<test::object> >* test_set; |
b32b8144 | 256 | boost::unordered_multiset<test::object, test::hash, test::equal_to, |
7c673cae | 257 | test::allocator2<test::object> >* test_multiset; |
b32b8144 | 258 | boost::unordered_map<test::object, test::object, test::hash, test::equal_to, |
7c673cae | 259 | test::allocator1<test::object> >* test_map; |
b32b8144 FG |
260 | boost::unordered_multimap<test::object, test::object, test::hash, |
261 | test::equal_to, test::allocator2<test::object> >* test_multimap; | |
7c673cae | 262 | |
b32b8144 FG |
263 | using test::default_generator; |
264 | using test::generate_collisions; | |
265 | using test::limited_range; | |
7c673cae | 266 | |
b32b8144 FG |
267 | UNORDERED_TEST( |
268 | erase_tests1, ((test_set)(test_multiset)(test_map)(test_multimap))( | |
269 | (default_generator)(generate_collisions)(limited_range))) | |
7c673cae FG |
270 | } |
271 | ||
272 | RUN_TESTS() |