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