1 | // |
2 | // immer: immutable data structures for C++ |
3 | // Copyright (C) 2016, 2017, 2018 Juan Pedro Bolivar Puente |
4 | // |
5 | // This software is distributed under the Boost Software License, Version 1.0. |
6 | // See accompanying file LICENSE or copy at http://boost.org/LICENSE_1_0.txt |
7 | // |
8 | |
9 | #ifndef MAP_T |
10 | #error "define the map template to use in MAP_T" |
11 | #include <immer/map.hpp> |
12 | #define MAP_T ::immer::map |
13 | #endif |
14 | |
15 | #include <immer/algorithm.hpp> |
16 | |
17 | #include "test/util.hpp" |
18 | #include "test/dada.hpp" |
19 | |
20 | #include <catch.hpp> |
21 | |
22 | #include <unordered_set> |
23 | #include <random> |
24 | |
25 | template <typename T=unsigned> |
26 | auto make_generator() |
27 | { |
28 | auto engine = std::default_random_engine{42}; |
29 | auto dist = std::uniform_int_distribution<T>{}; |
30 | return std::bind(dist, engine); |
31 | } |
32 | |
33 | struct conflictor |
34 | { |
35 | unsigned v1; |
36 | unsigned v2; |
37 | |
38 | bool operator== (const conflictor& x) const |
39 | { return v1 == x.v1 && v2 == x.v2; } |
40 | }; |
41 | |
42 | struct hash_conflictor |
43 | { |
44 | std::size_t operator() (const conflictor& x) const |
45 | { return x.v1; } |
46 | }; |
47 | |
48 | auto make_values_with_collisions(unsigned n) |
49 | { |
50 | auto gen = make_generator(); |
51 | auto vals = std::vector<std::pair<conflictor, unsigned>>{}; |
52 | auto vals_ = std::unordered_set<conflictor, hash_conflictor>{}; |
53 | auto i = 0u; |
54 | generate_n(back_inserter(vals), n, [&] { |
55 | auto newv = conflictor{}; |
56 | do { |
57 | newv = { unsigned(gen() % (n / 2)), gen() }; |
58 | } while (!vals_.insert(newv).second); |
59 | return std::pair<conflictor, unsigned>{newv, i++}; |
60 | }); |
61 | return vals; |
62 | } |
63 | |
64 | auto make_test_map(unsigned n) |
65 | { |
66 | auto s = MAP_T<unsigned, unsigned>{}; |
67 | for (auto i = 0u; i < n; ++i) |
68 | s = s.insert({i, i}); |
69 | return s; |
70 | } |
71 | |
72 | auto make_test_map(const std::vector<std::pair<conflictor, unsigned>>& vals) |
73 | { |
74 | auto s = MAP_T<conflictor, unsigned, hash_conflictor>{}; |
75 | for (auto&& v : vals) |
76 | s = s.insert(v); |
77 | return s; |
78 | } |
79 | |
80 | TEST_CASE("instantiation" ) |
81 | { |
82 | SECTION("default" ) |
83 | { |
84 | auto v = MAP_T<int, int>{}; |
85 | CHECK(v.size() == 0u); |
86 | } |
87 | } |
88 | |
89 | TEST_CASE("basic insertion" ) |
90 | { |
91 | auto v1 = MAP_T<int, int>{}; |
92 | CHECK(v1.count(42) == 0); |
93 | |
94 | auto v2 = v1.insert({42, {}}); |
95 | CHECK(v1.count(42) == 0); |
96 | CHECK(v2.count(42) == 1); |
97 | |
98 | auto v3 = v2.insert({42, {}}); |
99 | CHECK(v1.count(42) == 0); |
100 | CHECK(v2.count(42) == 1); |
101 | CHECK(v3.count(42) == 1); |
102 | } |
103 | |
104 | TEST_CASE("accessor" ) |
105 | { |
106 | const auto n = 666u; |
107 | auto v = make_test_map(n); |
108 | CHECK(v[0] == 0); |
109 | CHECK(v[42] == 42); |
110 | CHECK(v[665] == 665); |
111 | CHECK(v[666] == 0); |
112 | CHECK(v[1234] == 0); |
113 | } |
114 | |
115 | TEST_CASE("at" ) |
116 | { |
117 | const auto n = 666u; |
118 | auto v = make_test_map(n); |
119 | CHECK(v.at(0) == 0); |
120 | CHECK(v.at(42) == 42); |
121 | CHECK(v.at(665) == 665); |
122 | CHECK_THROWS_AS(v.at(666), std::out_of_range&); |
123 | CHECK_THROWS_AS(v.at(1234), std::out_of_range&); |
124 | } |
125 | |
126 | TEST_CASE("find" ) |
127 | { |
128 | const auto n = 666u; |
129 | auto v = make_test_map(n); |
130 | CHECK(*v.find(0) == 0); |
131 | CHECK(*v.find(42) == 42); |
132 | CHECK(*v.find(665) == 665); |
133 | CHECK(v.find(666) == nullptr); |
134 | CHECK(v.find(1234) == nullptr); |
135 | } |
136 | |
137 | TEST_CASE("equals and setting" ) |
138 | { |
139 | const auto n = 666u; |
140 | auto v = make_test_map(n); |
141 | |
142 | CHECK(v == v); |
143 | CHECK(v != v.insert({1234, 42})); |
144 | CHECK(v != v.erase(32)); |
145 | CHECK(v == v.insert({1234, 42}).erase(1234)); |
146 | CHECK(v == v.erase(32).insert({32, 32})); |
147 | |
148 | CHECK(v.set(1234, 42) == v.insert({1234, 42})); |
149 | CHECK(v.update(1234, [] (auto&& x) { return x + 1; }) == |
150 | v.set(1234, 1)); |
151 | CHECK(v.update(42, [] (auto&& x) { return x + 1; }) == |
152 | v.set(42, 43)); |
153 | } |
154 | |
155 | TEST_CASE("iterator" ) |
156 | { |
157 | const auto N = 666u; |
158 | auto v = make_test_map(N); |
159 | |
160 | SECTION("empty set" ) |
161 | { |
162 | auto s = MAP_T<unsigned, unsigned>{}; |
163 | CHECK(s.begin() == s.end()); |
164 | } |
165 | |
166 | SECTION("works with range loop" ) |
167 | { |
168 | auto seen = std::unordered_set<unsigned>{}; |
169 | for (const auto& x : v) |
170 | CHECK(seen.insert(x.first).second); |
171 | CHECK(seen.size() == v.size()); |
172 | } |
173 | |
174 | SECTION("iterator and collisions" ) |
175 | { |
176 | auto vals = make_values_with_collisions(N); |
177 | auto s = make_test_map(vals); |
178 | auto seen = std::unordered_set<conflictor, hash_conflictor>{}; |
179 | for (const auto& x : s) |
180 | CHECK(seen.insert(x.first).second); |
181 | CHECK(seen.size() == s.size()); |
182 | } |
183 | } |
184 | |
185 | TEST_CASE("accumulate" ) |
186 | { |
187 | const auto n = 666u; |
188 | auto v = make_test_map(n); |
189 | |
190 | auto expected_n = |
191 | [] (auto n) { |
192 | return n * (n - 1) / 2; |
193 | }; |
194 | |
195 | SECTION("sum collection" ) |
196 | { |
197 | auto acc = [] (unsigned acc, const std::pair<unsigned, unsigned>& x) { |
198 | return acc + x.first + x.second; |
199 | }; |
200 | auto sum = immer::accumulate(v, 0u, acc); |
201 | CHECK(sum == 2 * expected_n(v.size())); |
202 | } |
203 | |
204 | SECTION("sum collisions" ) { |
205 | auto vals = make_values_with_collisions(n); |
206 | auto s = make_test_map(vals); |
207 | auto acc = [] (unsigned r, std::pair<conflictor, unsigned> x) { |
208 | return r + x.first.v1 + x.first.v2 + x.second; |
209 | }; |
210 | auto sum1 = std::accumulate(vals.begin(), vals.end(), 0u, acc); |
211 | auto sum2 = immer::accumulate(s, 0u, acc); |
212 | CHECK(sum1 == sum2); |
213 | } |
214 | } |
215 | |
216 | TEST_CASE("update a lot" ) |
217 | { |
218 | auto v = make_test_map(666u); |
219 | |
220 | for (decltype(v.size()) i = 0; i < v.size(); ++i) { |
221 | v = v.update(i, [] (auto&& x) { return x + 1; }); |
222 | CHECK(v[i] == i+1); |
223 | } |
224 | } |
225 | |
226 | TEST_CASE("exception safety" ) |
227 | { |
228 | constexpr auto n = 2666u; |
229 | |
230 | using dadaist_map_t = typename dadaist_wrapper<MAP_T<unsigned, unsigned>>::type; |
231 | using dadaist_conflictor_map_t = typename dadaist_wrapper<MAP_T<conflictor, unsigned, hash_conflictor>>::type; |
232 | |
233 | SECTION("update collisions" ) |
234 | { |
235 | auto v = dadaist_map_t{}; |
236 | auto d = dadaism{}; |
237 | for (auto i = 0u; i < n; ++i) |
238 | v = v.set(i, i); |
239 | for (auto i = 0u; i < v.size();) { |
240 | try { |
241 | auto s = d.next(); |
242 | v = v.update(i, [] (auto x) { return x + 1; }); |
243 | ++i; |
244 | } catch (dada_error) {} |
245 | for (auto i : test_irange(0u, i)) |
246 | CHECK(v.at(i) == i + 1); |
247 | for (auto i : test_irange(i, n)) |
248 | CHECK(v.at(i) == i); |
249 | } |
250 | CHECK(d.happenings > 0); |
251 | IMMER_TRACE_E(d.happenings); |
252 | } |
253 | |
254 | SECTION("update collisisions" ) |
255 | { |
256 | auto vals = make_values_with_collisions(n); |
257 | auto v = dadaist_conflictor_map_t{}; |
258 | auto d = dadaism{}; |
259 | for (auto i = 0u; i < n; ++i) |
260 | v = v.insert(vals[i]); |
261 | for (auto i = 0u; i < v.size();) { |
262 | try { |
263 | auto s = d.next(); |
264 | v = v.update(vals[i].first, [] (auto x) { return x + 1; }); |
265 | ++i; |
266 | } catch (dada_error) {} |
267 | for (auto i : test_irange(0u, i)) |
268 | CHECK(v.at(vals[i].first) == vals[i].second + 1); |
269 | for (auto i : test_irange(i, n)) |
270 | CHECK(v.at(vals[i].first) == vals[i].second); |
271 | } |
272 | CHECK(d.happenings > 0); |
273 | IMMER_TRACE_E(d.happenings); |
274 | } |
275 | } |
276 | |