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 SET_T
10#error "define the set template to use in SET_T"
11#include <immer/set.hpp>
12#define SET_T ::immer::set
13#endif
14
15#include "test/util.hpp"
16#include "test/dada.hpp"
17
18#include <immer/algorithm.hpp>
19
20#include <catch.hpp>
21
22#include <unordered_set>
23#include <random>
24
25template <typename T=unsigned>
26auto 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
33struct 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
42struct hash_conflictor
43{
44 std::size_t operator() (const conflictor& x) const
45 { return x.v1; }
46};
47
48auto make_values_with_collisions(unsigned n)
49{
50 auto gen = make_generator();
51 auto vals = std::vector<conflictor>{};
52 auto vals_ = std::unordered_set<conflictor, hash_conflictor>{};
53 generate_n(back_inserter(vals), n, [&] {
54 auto newv = conflictor{};
55 do {
56 newv = { unsigned(gen() % (n / 2)), gen() };
57 } while (!vals_.insert(newv).second);
58 return newv;
59 });
60 return vals;
61}
62
63auto make_test_set(unsigned n)
64{
65 auto s = SET_T<unsigned>{};
66 for (auto i = 0u; i < n; ++i)
67 s = s.insert(i);
68 return s;
69}
70
71auto make_test_set(const std::vector<conflictor>& vals)
72{
73 auto s = SET_T<conflictor, hash_conflictor>{};
74 for (auto&& v : vals)
75 s = s.insert(v);
76 return s;
77}
78
79template <std::size_t BufLen>
80struct unaligned_str
81{
82 std::array<char, BufLen> m_data{};
83
84 unaligned_str() = default;
85 unaligned_str(const std::string& in)
86 {
87 for (std::size_t i = 0; i < std::min(m_data.size() - 1, in.size()); i++)
88 m_data[i] = in[i];
89 }
90 unaligned_str(const char* in)
91 : unaligned_str{std::string{in}}
92 {}
93
94 std::string str() const
95 {
96 return m_data.data();
97 }
98
99 bool operator==(unaligned_str other) const
100 {
101 return m_data == other.m_data;
102 }
103
104 bool operator!=(unaligned_str other) const
105 {
106 return m_data != other.m_data;
107 }
108};
109
110namespace std
111{
112 template<size_t BufLen>
113 struct hash<unaligned_str<BufLen>>
114 {
115 size_t operator()(const unaligned_str<BufLen>& str) const
116 {
117 return std::hash<std::string>{}(str.str());
118 }
119 };
120}
121
122template<size_t BufLen>
123void check_with_len()
124{
125 auto v = SET_T<unaligned_str<BufLen>>{};
126
127 for (int i=0; i < 1; i++)
128 v = v.insert(std::to_string(i));
129
130 CHECK(v.count("0") == 1);
131}
132
133TEST_CASE("insert type with no alignment requirement")
134{
135 check_with_len<1>();
136 check_with_len<9>();
137 check_with_len<15>();
138 check_with_len<17>();
139}
140
141TEST_CASE("instantiation")
142{
143 SECTION("default")
144 {
145 auto v = SET_T<unsigned>{};
146 CHECK(v.size() == 0u);
147 }
148}
149
150TEST_CASE("basic insertion")
151{
152 auto v1 = SET_T<unsigned>{};
153 CHECK(v1.count(42) == 0);
154
155 auto v2 = v1.insert(42);
156 CHECK(v1.count(42) == 0);
157 CHECK(v2.count(42) == 1);
158
159 auto v3 = v2.insert(42);
160 CHECK(v1.count(42) == 0);
161 CHECK(v2.count(42) == 1);
162 CHECK(v3.count(42) == 1);
163}
164
165TEST_CASE("insert a lot")
166{
167 constexpr auto N = 666u;
168
169 auto gen = make_generator();
170 auto vals = std::vector<unsigned>{};
171 generate_n(back_inserter(vals), N, gen);
172 auto s = SET_T<unsigned>{};
173
174 for (auto i = 0u; i < N; ++i) {
175 s = s.insert(vals[i]);
176 CHECK(s.size() == i + 1);
177 for (auto j : test_irange(0u, i+1))
178 CHECK(s.count(vals[j]) == 1);
179 for (auto j : test_irange(i + 1u, N))
180 CHECK(s.count(vals[j]) == 0);
181 }
182}
183
184TEST_CASE("insert conflicts")
185{
186 constexpr auto N = 666u;
187 auto vals = make_values_with_collisions(N);
188 auto s = SET_T<conflictor, hash_conflictor>{};
189 for (auto i = 0u; i < N; ++i) {
190 s = s.insert(vals[i]);
191 CHECK(s.size() == i + 1);
192 for (auto j : test_irange(0u, i+1))
193 CHECK(s.count(vals[j]) == 1);
194 for (auto j : test_irange(i + 1u, N))
195 CHECK(s.count(vals[j]) == 0);
196 }
197}
198
199TEST_CASE("erase a lot")
200{
201 constexpr auto N = 666u;
202 auto gen = make_generator();
203 auto vals = std::vector<unsigned>{};
204 generate_n(back_inserter(vals), N, gen);
205
206 auto s = SET_T<unsigned>{};
207 for (auto i = 0u; i < N; ++i)
208 s = s.insert(vals[i]);
209
210 for (auto i = 0u; i < N; ++i) {
211 s = s.erase(vals[i]);
212 CHECK(s.size() == N - i - 1);
213 for (auto j : test_irange(0u, i+1))
214 CHECK(s.count(vals[j]) == 0);
215 for (auto j : test_irange(i + 1u, N))
216 CHECK(s.count(vals[j]) == 1);
217 }
218}
219
220TEST_CASE("erase conflicts")
221{
222 constexpr auto N = 666u;
223 auto vals = make_values_with_collisions(N);
224 auto s = SET_T<conflictor, hash_conflictor>{};
225 for (auto i = 0u; i < N; ++i)
226 s = s.insert(vals[i]);
227
228 for (auto i = 0u; i < N; ++i) {
229 s = s.erase(vals[i]);
230 CHECK(s.size() == N - i - 1);
231 for (auto j : test_irange(0u, i+1))
232 CHECK(s.count(vals[j]) == 0);
233 for (auto j : test_irange(i + 1u, N))
234 CHECK(s.count(vals[j]) == 1);
235 }
236}
237
238TEST_CASE("accumulate")
239{
240 const auto n = 666u;
241 auto v = make_test_set(n);
242
243 auto expected_n =
244 [] (auto n) {
245 return n * (n - 1) / 2;
246 };
247
248 SECTION("sum collection")
249 {
250 auto sum = immer::accumulate(v, 0u);
251 CHECK(sum == expected_n(v.size()));
252 }
253
254 SECTION("sum collisions") {
255 auto vals = make_values_with_collisions(n);
256 auto s = make_test_set(vals);
257 auto acc = [] (unsigned r, conflictor x) {
258 return r + x.v1 + x.v2;
259 };
260 auto sum1 = std::accumulate(vals.begin(), vals.end(), 0, acc);
261 auto sum2 = immer::accumulate(s, 0u, acc);
262 CHECK(sum1 == sum2);
263 }
264}
265
266TEST_CASE("iterator")
267{
268 const auto N = 666u;
269 auto v = make_test_set(N);
270
271 SECTION("empty set")
272 {
273 auto s = SET_T<unsigned>{};
274 CHECK(s.begin() == s.end());
275 }
276
277 SECTION("works with range loop")
278 {
279 auto seen = std::unordered_set<unsigned>{};
280 for (const auto& x : v)
281 CHECK(seen.insert(x).second);
282 CHECK(seen.size() == v.size());
283 }
284
285 SECTION("works with standard algorithms")
286 {
287 auto s = std::vector<unsigned>(N);
288 std::iota(s.begin(), s.end(), 0u);
289 std::equal(v.begin(), v.end(), s.begin(), s.end());
290 }
291
292 SECTION("iterator and collisions")
293 {
294 auto vals = make_values_with_collisions(N);
295 auto s = make_test_set(vals);
296 auto seen = std::unordered_set<conflictor, hash_conflictor>{};
297 for (const auto& x : s)
298 CHECK(seen.insert(x).second);
299 CHECK(seen.size() == s.size());
300 }
301}
302
303struct non_default
304{
305 unsigned value;
306 non_default() = delete;
307 operator unsigned() const { return value; }
308
309#if IMMER_DEBUG_PRINT
310 friend std::ostream& operator<< (std::ostream& os, non_default x)
311 {
312 os << "ND{" << x.value << "}";
313 return os;
314 }
315#endif
316};
317
318namespace std {
319
320template <>
321struct hash<non_default>
322{
323 std::size_t operator() (const non_default& x)
324 {
325 return std::hash<decltype(x.value)>{}(x.value);
326 }
327};
328
329} // namespace std
330
331TEST_CASE("non default")
332{
333 const auto n = 666u;
334
335 auto v = SET_T<non_default>{};
336 for (auto i = 0u; i < n; ++i)
337 v = v.insert({ i });
338
339 CHECK(v.size() == n);
340}
341
342TEST_CASE("equals")
343{
344 const auto n = 666u;
345 auto v = make_test_set(n);
346
347 CHECK(v == v);
348 CHECK(v != v.insert(1234));
349 CHECK(v == v.erase(1234));
350 CHECK(v == v.insert(1234).erase(1234));
351 CHECK(v == v.erase(64).insert(64));
352 CHECK(v != v.erase(1234).insert(1234));
353}
354
355TEST_CASE("equals collisions")
356{
357 const auto n = 666u;
358 auto vals = make_values_with_collisions(n);
359 auto v = make_test_set(vals);
360
361 CHECK(v == v);
362 CHECK(v != v.erase(vals[42]));
363 CHECK(v == v.erase(vals[42]).insert(vals[42]));
364 CHECK(v == v.erase(vals[42]).erase(vals[13])
365 .insert(vals[42]).insert(vals[13]));
366 CHECK(v == v.erase(vals[42]).erase(vals[13])
367 .insert(vals[13]).insert(vals[42]));
368}
369
370TEST_CASE("exception safety")
371{
372 constexpr auto n = 2666u;
373
374 using dadaist_set_t = typename dadaist_wrapper<SET_T<unsigned>>::type;
375 using dadaist_conflictor_set_t = typename dadaist_wrapper<SET_T<conflictor, hash_conflictor>>::type;
376
377 SECTION("insert")
378 {
379 auto v = dadaist_set_t{};
380 auto d = dadaism{};
381 for (auto i = 0u; v.size() < n;) {
382 try {
383 auto s = d.next();
384 v = v.insert({i});
385 ++i;
386 } catch (dada_error) {}
387 for (auto i : test_irange(0u, i))
388 CHECK(v.count({i}) == 1);
389 }
390 CHECK(d.happenings > 0);
391 IMMER_TRACE_E(d.happenings);
392 }
393
394 SECTION("insert collisions")
395 {
396 auto vals = make_values_with_collisions(n);
397 auto v = dadaist_conflictor_set_t{};
398 auto d = dadaism{};
399 for (auto i = 0u; v.size() < n;) {
400 try {
401 auto s = d.next();
402 v = v.insert({vals[i]});
403 ++i;
404 } catch (dada_error) {}
405 for (auto i : test_irange(0u, i))
406 CHECK(v.count({vals[i]}) == 1);
407 }
408 CHECK(d.happenings > 0);
409 IMMER_TRACE_E(d.happenings);
410 }
411
412 SECTION("erase")
413 {
414 auto v = dadaist_set_t{};
415 auto d = dadaism{};
416 for (auto i = 0u; i < n; ++i)
417 v = v.insert({i});
418 for (auto i = 0u; v.size() > 0;) {
419 try {
420 auto s = d.next();
421 v = v.erase({i});
422 ++i;
423 } catch (dada_error) {}
424 for (auto i : test_irange(0u, i))
425 CHECK(v.count({i}) == 0);
426 for (auto i : test_irange(i, n))
427 CHECK(v.count({i}) == 1);
428 }
429 CHECK(d.happenings > 0);
430 IMMER_TRACE_E(d.happenings);
431 }
432
433 SECTION("erase collisisions")
434 {
435 auto vals = make_values_with_collisions(n);
436 auto v = dadaist_conflictor_set_t{};
437 auto d = dadaism{};
438 for (auto i = 0u; i < n; ++i)
439 v = v.insert({vals[i]});
440 for (auto i = 0u; v.size() > 0;) {
441 try {
442 auto s = d.next();
443 v = v.erase({vals[i]});
444 ++i;
445 } catch (dada_error) {}
446 for (auto i : test_irange(0u, i))
447 CHECK(v.count({vals[i]}) == 0);
448 for (auto i : test_irange(i, n))
449 CHECK(v.count({vals[i]}) == 1);
450 }
451 CHECK(d.happenings > 0);
452 IMMER_TRACE_E(d.happenings);
453 }
454}
455