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 | #include "test/dada.hpp" |
10 | #include "test/util.hpp" |
11 | #include "test/transient_tester.hpp" |
12 | |
13 | #include <immer/algorithm.hpp> |
14 | |
15 | #include <catch.hpp> |
16 | #include <boost/range/adaptors.hpp> |
17 | #include <boost/range/irange.hpp> |
18 | |
19 | #include <algorithm> |
20 | #include <numeric> |
21 | #include <vector> |
22 | #include <array> |
23 | |
24 | #ifndef FLEX_VECTOR_T |
25 | #error "define the vector template to use in FLEX_VECTOR_T" |
26 | #endif |
27 | |
28 | #ifndef VECTOR_T |
29 | #error "define the vector template to use in VECTOR_T" |
30 | #endif |
31 | |
32 | template <typename V=FLEX_VECTOR_T<unsigned>> |
33 | auto make_test_flex_vector(unsigned min, unsigned max) |
34 | { |
35 | auto v = V{}; |
36 | for (auto i = min; i < max; ++i) |
37 | v = v.push_back({i}); |
38 | return v; |
39 | } |
40 | |
41 | template <typename V=FLEX_VECTOR_T<unsigned>> |
42 | auto make_test_flex_vector_front(unsigned min, unsigned max) |
43 | { |
44 | auto v = V{}; |
45 | for (auto i = max; i > min;) |
46 | v = v.push_front({--i}); |
47 | return v; |
48 | } |
49 | |
50 | template <std::size_t N> |
51 | auto make_many_test_flex_vector() |
52 | { |
53 | using vektor_t = FLEX_VECTOR_T<unsigned>; |
54 | auto many = std::array<vektor_t, N>{}; |
55 | std::generate_n( |
56 | many.begin(), N, |
57 | [v = vektor_t{}, i = 0u] () mutable |
58 | { |
59 | auto r = v; |
60 | v = v.push_back(i++); |
61 | return r; |
62 | }); |
63 | return many; |
64 | } |
65 | |
66 | template <std::size_t N> |
67 | auto make_many_test_flex_vector_front() |
68 | { |
69 | using vektor_t = FLEX_VECTOR_T<unsigned>; |
70 | auto many = std::array<vektor_t, N>{}; |
71 | std::generate_n( |
72 | many.begin(), N, |
73 | [i = 0u] () mutable |
74 | { |
75 | return make_test_flex_vector_front(0, i++); |
76 | }); |
77 | return many; |
78 | } |
79 | |
80 | template <std::size_t N> |
81 | auto make_many_test_flex_vector_front_remainder() |
82 | { |
83 | using vektor_t = FLEX_VECTOR_T<unsigned>; |
84 | auto many = std::array<vektor_t, N>{}; |
85 | std::generate_n( |
86 | many.begin(), N, |
87 | [v = vektor_t{}, i = N-1] () mutable |
88 | { |
89 | auto r = v; |
90 | v = v.push_front(--i); |
91 | return r; |
92 | }); |
93 | return many; |
94 | } |
95 | |
96 | TEST_CASE("set relaxed" ) |
97 | { |
98 | auto v = make_test_flex_vector_front(0, 666u); |
99 | for (decltype(v.size()) i = 0; i < v.size(); ++i) { |
100 | v = v.set(i, i+1); |
101 | CHECK(v[i] == i+1); |
102 | } |
103 | } |
104 | |
105 | TEST_CASE("push_front" ) |
106 | { |
107 | const auto n = 666u; |
108 | auto v = FLEX_VECTOR_T<unsigned>{}; |
109 | |
110 | for (auto i = 0u; i < n; ++i) { |
111 | v = v.push_front(i); |
112 | CHECK(v.size() == i + 1); |
113 | for (decltype(v.size()) j = 0; j < v.size(); ++j) |
114 | CHECK(v[v.size() - j - 1] == j); |
115 | } |
116 | } |
117 | |
118 | TEST_CASE("concat" ) |
119 | { |
120 | #if IMMER_SLOW_TESTS |
121 | constexpr auto n = 666u; |
122 | #else |
123 | constexpr auto n = 101u; |
124 | #endif |
125 | |
126 | auto all_lhs = make_many_test_flex_vector<n>(); |
127 | auto all_rhs = make_many_test_flex_vector_front_remainder<n>(); |
128 | |
129 | SECTION("regular plus regular" ) |
130 | { |
131 | for (auto i : test_irange(0u, n)) { |
132 | auto c = all_lhs[i] + all_lhs[i]; |
133 | CHECK_VECTOR_EQUALS(c, boost::join( |
134 | boost::irange(0u, i), |
135 | boost::irange(0u, i))); |
136 | } |
137 | } |
138 | |
139 | SECTION("regular plus relaxed" ) |
140 | { |
141 | for (auto i : test_irange(0u, n)) { |
142 | auto c = all_lhs[i] + all_rhs[n - i - 1]; |
143 | CHECK_VECTOR_EQUALS(c, boost::irange(0u, n - 1)); |
144 | } |
145 | } |
146 | } |
147 | |
148 | auto make_flex_vector_concat(std::size_t min, std::size_t max) |
149 | { |
150 | using vektor_t = FLEX_VECTOR_T<unsigned>; |
151 | |
152 | if (max == min) |
153 | return vektor_t{}; |
154 | else if (max == min + 1) |
155 | return vektor_t{}.push_back(min); |
156 | else { |
157 | auto mid = min + (max - min) / 2; |
158 | return make_flex_vector_concat(min, mid) |
159 | + make_flex_vector_concat(mid, max); |
160 | } |
161 | } |
162 | |
163 | TEST_CASE("concat recursive" ) |
164 | { |
165 | const auto n = 666u; |
166 | auto v = make_flex_vector_concat(0, n); |
167 | CHECK_VECTOR_EQUALS(v, boost::irange(0u, n)); |
168 | } |
169 | |
170 | TEST_CASE("insert" ) |
171 | { |
172 | SECTION("normal" ) |
173 | { |
174 | const auto n = 666u; |
175 | auto v = make_test_flex_vector(0, n); |
176 | v = v.insert(42, 100); |
177 | CHECK_VECTOR_EQUALS(v, boost::join( |
178 | boost::irange(0u, 42u), |
179 | boost::join(boost::irange(100u, 101u), |
180 | boost::irange(42u, n)))); |
181 | } |
182 | |
183 | SECTION("move" ) |
184 | { |
185 | const auto n = 666u; |
186 | auto v = make_test_flex_vector(0, n); |
187 | v = std::move(v).insert(42, 100); |
188 | CHECK_VECTOR_EQUALS(v, boost::join( |
189 | boost::irange(0u, 42u), |
190 | boost::join(boost::irange(100u, 101u), |
191 | boost::irange(42u, n)))); |
192 | } |
193 | |
194 | SECTION("vec" ) |
195 | { |
196 | const auto n = 666u; |
197 | auto v = make_test_flex_vector(0, n); |
198 | v = std::move(v).insert(42, {100, 101, 102}); |
199 | CHECK_VECTOR_EQUALS(v, boost::join( |
200 | boost::irange(0u, 42u), |
201 | boost::join(boost::irange(100u, 103u), |
202 | boost::irange(42u, n)))); |
203 | } |
204 | |
205 | SECTION("vec move" ) |
206 | { |
207 | const auto n = 666u; |
208 | auto v = make_test_flex_vector(0, n); |
209 | v = std::move(v).insert(42, {100, 101, 102}); |
210 | CHECK_VECTOR_EQUALS(v, boost::join( |
211 | boost::irange(0u, 42u), |
212 | boost::join(boost::irange(100u, 103u), |
213 | boost::irange(42u, n)))); |
214 | } |
215 | } |
216 | |
217 | TEST_CASE("erase" ) |
218 | { |
219 | const auto n = 666u; |
220 | auto v = make_test_flex_vector(0, n); |
221 | auto vv = v.erase(0); |
222 | CHECK_VECTOR_EQUALS(vv, boost::irange(1u, n)); |
223 | CHECK_VECTOR_EQUALS(v.erase(v.size() - 1), boost::irange(0u, n - 1)); |
224 | CHECK_VECTOR_EQUALS(v.erase(v.size() - 1), boost::irange(0u, n - 1)); |
225 | CHECK_VECTOR_EQUALS(v.erase(42), boost::join(boost::irange(0u, 42u), |
226 | boost::irange(43u, n))); |
227 | CHECK_VECTOR_EQUALS(v.erase(v.size() - 1, v.size()), |
228 | boost::irange(0u, n - 1)); |
229 | CHECK_VECTOR_EQUALS(v.erase(0, 0), boost::irange(0u, n)); |
230 | CHECK_VECTOR_EQUALS(v.erase(42, 50), boost::join(boost::irange(0u, 42u), |
231 | boost::irange(50u, n))); |
232 | } |
233 | |
234 | TEST_CASE("accumulate relaxed" ) |
235 | { |
236 | auto expected_n = |
237 | [] (auto n) { |
238 | return n * (n - 1) / 2; |
239 | }; |
240 | auto expected_i = |
241 | [&] (auto i, auto n) { |
242 | return expected_n(n) - expected_n(i); |
243 | }; |
244 | |
245 | SECTION("sum" ) |
246 | { |
247 | const auto n = 666u; |
248 | auto v = make_test_flex_vector_front(0, n); |
249 | |
250 | auto sum = immer::accumulate(v, 0u); |
251 | auto expected = v.size() * (v.size() - 1) / 2; |
252 | CHECK(sum == expected); |
253 | } |
254 | |
255 | SECTION("sum complex" ) |
256 | { |
257 | const auto n = 20u; |
258 | |
259 | auto v = FLEX_VECTOR_T<unsigned>{}; |
260 | for (auto i = 0u; i < n; ++i) |
261 | v = v.push_front(i) + v; |
262 | |
263 | auto sum = immer::accumulate(v, 0u); |
264 | auto expected = (1 << n) - n - 1; |
265 | CHECK(sum == expected); |
266 | } |
267 | |
268 | SECTION("sum range" ) |
269 | { |
270 | using namespace std; |
271 | const auto n = 666u; |
272 | auto v = make_test_flex_vector_front(0, n); |
273 | { |
274 | auto sum = immer::accumulate(begin(v) + 100, |
275 | begin(v) + 300, |
276 | 0u); |
277 | CHECK(sum == expected_i(100, 300)); |
278 | } |
279 | { |
280 | auto sum = immer::accumulate(begin(v) + 31, |
281 | begin(v) + 300, 0u); |
282 | CHECK(sum == expected_i(31, 300)); |
283 | } |
284 | { |
285 | auto sum = immer::accumulate(begin(v), begin(v) + 33, 0u); |
286 | CHECK(sum == expected_i(0, 33)); |
287 | } |
288 | { |
289 | auto sum = immer::accumulate(begin(v) + 100, |
290 | begin(v) + 660, 0u); |
291 | CHECK(sum == expected_i(100, 660)); |
292 | } |
293 | { |
294 | auto sum = immer::accumulate(begin(v) + 100, |
295 | begin(v) + 105, 0u); |
296 | CHECK(sum == expected_i(100, 105)); |
297 | } |
298 | { |
299 | auto sum = immer::accumulate(begin(v) + 660, |
300 | begin(v) + 664, 0u); |
301 | CHECK(sum == expected_i(660, 664)); |
302 | } |
303 | } |
304 | } |
305 | |
306 | TEST_CASE("equals" ) |
307 | { |
308 | const auto n = 666u; |
309 | auto v = make_test_flex_vector_front(0, n); |
310 | |
311 | CHECK(v == v); |
312 | CHECK(v == v.set(42, 42)); |
313 | CHECK(v != v.set(42, 24)); |
314 | CHECK(v == v.set(42, 24).set(42, 42)); |
315 | CHECK(v.set(42, 24) == v.set(42, 24)); |
316 | CHECK(v != v.push_back(7)); |
317 | CHECK(v.push_back(7) == v.push_back(7)); |
318 | CHECK(v.push_back(5) != v.push_back(7)); |
319 | CHECK(v != v.set(v.size()-2, 24)); |
320 | CHECK(v == v |
321 | .set(v.size()-2, 24) |
322 | .set(v.size()-2, v[v.size()-2])); |
323 | CHECK(v == v.insert(42, 12).erase(42)); |
324 | CHECK(v == v.insert(0, 12).erase(0)); |
325 | } |
326 | |
327 | |
328 | TEST_CASE("equals bugs" ) |
329 | { |
330 | { |
331 | const auto n = 666u; |
332 | auto v = make_test_flex_vector(0, n); |
333 | CHECK(v == v.insert(42, 12).erase(42)); |
334 | CHECK(v == v.insert(0, 12).erase(0)); |
335 | } |
336 | { |
337 | const auto n = 30u; |
338 | auto v = make_test_flex_vector(0, n); |
339 | CHECK(v == v.insert(10, 12).erase(10)); |
340 | CHECK(v == v.insert(0, 12).erase(0)); |
341 | } |
342 | { |
343 | const auto n = 666u; |
344 | auto v = make_test_flex_vector(0, n); |
345 | for (auto i : test_irange(0u, n)) |
346 | CHECK(v == v.insert(i, 42).erase(i)); |
347 | } |
348 | { |
349 | const auto n = 666u; |
350 | auto v = make_test_flex_vector_front(0, n); |
351 | for (auto i : test_irange(0u, n)) |
352 | CHECK(v == v.insert(i, 42).erase(i)); |
353 | } |
354 | { |
355 | const auto n = 666u; |
356 | auto v = FLEX_VECTOR_T<unsigned>{}; |
357 | using size_t = decltype(v.size()); |
358 | for (auto i : test_irange(0u, n)) { |
359 | while (v.size() < i) |
360 | v = std::move(v).push_back(i); |
361 | auto vv = v; |
362 | for (auto j : test_irange(size_t{}, v.size())) { |
363 | auto vz = vv.insert(j, 42).erase(j); |
364 | CHECK(v == vz); |
365 | CHECK(vv == vz); |
366 | vv = vz; |
367 | } |
368 | } |
369 | } |
370 | } |
371 | |
372 | TEST_CASE("take relaxed" ) |
373 | { |
374 | const auto n = 666u; |
375 | auto v = make_test_flex_vector_front(0, n); |
376 | |
377 | for (auto i : test_irange(0u, n)) { |
378 | auto vv = v.take(i); |
379 | CHECK_VECTOR_EQUALS_RANGE(vv, v.begin(), v.begin() + i); |
380 | } |
381 | } |
382 | |
383 | TEST_CASE("drop" ) |
384 | { |
385 | const auto n = 666u; |
386 | |
387 | SECTION("regular" ) |
388 | { |
389 | auto v = make_test_flex_vector(0, n); |
390 | |
391 | for (auto i : test_irange(0u, n)) { |
392 | auto vv = v.drop(i); |
393 | CHECK_VECTOR_EQUALS_RANGE(vv, v.begin() + i, v.end()); |
394 | } |
395 | } |
396 | |
397 | SECTION("relaxed" ) |
398 | { |
399 | auto v = make_test_flex_vector_front(0, n); |
400 | |
401 | for (auto i : test_irange(0u, n)) { |
402 | auto vv = v.drop(i); |
403 | CHECK_VECTOR_EQUALS_RANGE(vv, v.begin() + i, v.end()); |
404 | } |
405 | } |
406 | } |
407 | |
408 | #if IMMER_SLOW_TESTS |
409 | TEST_CASE("reconcat" ) |
410 | { |
411 | constexpr auto n = 666u; |
412 | auto v = make_test_flex_vector_front(0, n); |
413 | auto all_lhs = make_many_test_flex_vector_front<n + 1>(); |
414 | auto all_rhs = make_many_test_flex_vector_front_remainder<n + 1>(); |
415 | |
416 | for (auto i = 0u; i < n; ++i) { |
417 | auto vv = all_lhs[i] + all_rhs[n - i]; |
418 | CHECK_VECTOR_EQUALS(vv, v); |
419 | CHECK_SLOW(vv == v); |
420 | } |
421 | } |
422 | |
423 | TEST_CASE("reconcat drop" ) |
424 | { |
425 | constexpr auto n = 666u; |
426 | auto v = make_test_flex_vector_front(0, n); |
427 | auto all_lhs = make_many_test_flex_vector_front<n + 1>(); |
428 | |
429 | for (auto i = 0u; i < n; ++i) { |
430 | auto vv = all_lhs[i] + v.drop(i); |
431 | CHECK_VECTOR_EQUALS(vv, v); |
432 | CHECK_SLOW(vv == v); |
433 | } |
434 | } |
435 | |
436 | TEST_CASE("reconcat take" ) |
437 | { |
438 | constexpr auto n = 666u; |
439 | auto v = make_test_flex_vector_front(0, n); |
440 | auto all_rhs = make_many_test_flex_vector_front_remainder<n + 1>(); |
441 | |
442 | for (auto i = 0u; i < n; ++i) { |
443 | auto vv = v.take(i) + all_rhs[n - i]; |
444 | CHECK_VECTOR_EQUALS(vv, v); |
445 | CHECK_SLOW(vv == v); |
446 | } |
447 | } |
448 | #endif |
449 | |
450 | TEST_CASE("reconcat take drop" ) |
451 | { |
452 | const auto n = 666u; |
453 | auto v = make_test_flex_vector_front(0, n); |
454 | |
455 | for (auto i : test_irange(0u, n)) { |
456 | auto vv = v.take(i) + v.drop(i); |
457 | CHECK_VECTOR_EQUALS(vv, v); |
458 | CHECK_SLOW(vv == v); |
459 | } |
460 | } |
461 | |
462 | TEST_CASE("reconcat take drop feedback" ) |
463 | { |
464 | const auto n = 666u; |
465 | auto v = make_test_flex_vector_front(0, n); |
466 | auto vv = v; |
467 | for (auto i : test_irange(0u, n)) { |
468 | vv = vv.take(i) + vv.drop(i); |
469 | CHECK_VECTOR_EQUALS(vv, v); |
470 | CHECK_SLOW(vv == v); |
471 | } |
472 | } |
473 | |
474 | TEST_CASE("iterator relaxed" ) |
475 | { |
476 | const auto n = 666u; |
477 | auto v = make_test_flex_vector_front(0, n); |
478 | |
479 | SECTION("works with range loop" ) |
480 | { |
481 | auto i = 0u; |
482 | for (const auto& x : v) |
483 | CHECK(x == i++); |
484 | CHECK(i == v.size()); |
485 | } |
486 | |
487 | SECTION("works with standard algorithms" ) |
488 | { |
489 | auto s = std::vector<unsigned>(n); |
490 | std::iota(s.begin(), s.end(), 0u); |
491 | std::equal(v.begin(), v.end(), s.begin(), s.end()); |
492 | } |
493 | |
494 | SECTION("can go back from end" ) |
495 | { |
496 | auto expected = n - 1; |
497 | CHECK(expected == *--v.end()); |
498 | } |
499 | |
500 | SECTION("works with reversed range adaptor" ) |
501 | { |
502 | auto r = v | boost::adaptors::reversed; |
503 | auto i = n; |
504 | for (const auto& x : r) |
505 | CHECK(x == --i); |
506 | } |
507 | |
508 | SECTION("works with strided range adaptor" ) |
509 | { |
510 | auto r = v | boost::adaptors::strided(5); |
511 | auto i = 0u; |
512 | for (const auto& x : r) |
513 | CHECK(x == 5 * i++); |
514 | } |
515 | |
516 | SECTION("works reversed" ) |
517 | { |
518 | auto i = n; |
519 | for (auto iter = v.rbegin(), last = v.rend(); iter != last; ++iter) |
520 | CHECK(*iter == --i); |
521 | } |
522 | |
523 | SECTION("advance and distance" ) |
524 | { |
525 | auto i1 = v.begin(); |
526 | auto i2 = i1 + 100; |
527 | CHECK(100u == *i2); |
528 | CHECK(100 == i2 - i1); |
529 | CHECK(50u == *(i2 - 50)); |
530 | CHECK(-30 == (i2 - 30) - i2); |
531 | } |
532 | } |
533 | |
534 | TEST_CASE("adopt regular vector contents" ) |
535 | { |
536 | const auto n = 666u; |
537 | auto v = VECTOR_T<unsigned>{}; |
538 | for (auto i = 0u; i < n; ++i) { |
539 | v = v.push_back(i); |
540 | auto fv = FLEX_VECTOR_T<unsigned>{v}; |
541 | CHECK_VECTOR_EQUALS_AUX(v, fv, [] (auto&& v) { return &v; }); |
542 | } |
543 | } |
544 | |
545 | TEST_CASE("exception safety relaxed" ) |
546 | { |
547 | using dadaist_vector_t = typename dadaist_wrapper<FLEX_VECTOR_T<unsigned>>::type; |
548 | constexpr auto n = 666u; |
549 | |
550 | SECTION("push back" ) |
551 | { |
552 | auto half = n / 2; |
553 | auto v = make_test_flex_vector_front<dadaist_vector_t>(0, half); |
554 | auto d = dadaism{}; |
555 | for (auto i = half; v.size() < static_cast<decltype(v.size())>(n);) { |
556 | auto s = d.next(); |
557 | try { |
558 | v = v.push_back({i}); |
559 | ++i; |
560 | } catch (dada_error) {} |
561 | CHECK_VECTOR_EQUALS(v, boost::irange(0u, i)); |
562 | } |
563 | CHECK(d.happenings > 0); |
564 | IMMER_TRACE_E(d.happenings); |
565 | } |
566 | |
567 | SECTION("update" ) |
568 | { |
569 | auto v = make_test_flex_vector_front<dadaist_vector_t>(0, n); |
570 | auto d = dadaism{}; |
571 | for (auto i = 0u; i < n;) { |
572 | auto s = d.next(); |
573 | try { |
574 | v = v.update(i, [] (auto x) { return dada(), x + 1; }); |
575 | ++i; |
576 | } catch (dada_error) {} |
577 | CHECK_VECTOR_EQUALS(v, boost::join( |
578 | boost::irange(1u, 1u + i), |
579 | boost::irange(i, n))); |
580 | } |
581 | CHECK(d.happenings > 0); |
582 | IMMER_TRACE_E(d.happenings); |
583 | } |
584 | |
585 | SECTION("take" ) |
586 | { |
587 | auto v = make_test_flex_vector_front<dadaist_vector_t>(0, n); |
588 | auto d = dadaism{}; |
589 | for (auto i = 0u; i < n;) { |
590 | auto s = d.next(); |
591 | auto r = dadaist_vector_t{}; |
592 | try { |
593 | r = v.take(i); |
594 | CHECK_VECTOR_EQUALS(r, boost::irange(0u, i++)); |
595 | } catch (dada_error) { |
596 | CHECK_VECTOR_EQUALS(r, boost::irange(0u, 0u)); |
597 | } |
598 | } |
599 | CHECK(d.happenings > 0); |
600 | IMMER_TRACE_E(d.happenings); |
601 | } |
602 | |
603 | SECTION("concat" ) |
604 | { |
605 | auto v = make_test_flex_vector<dadaist_vector_t>(0, n); |
606 | auto d = dadaism{}; |
607 | for (auto i = 0u; i < n;) { |
608 | auto lhs = v.take(i); |
609 | auto rhs = v.drop(i); |
610 | auto s = d.next(); |
611 | try { |
612 | v = lhs + rhs; |
613 | ++i; |
614 | } catch (dada_error) {} |
615 | CHECK_VECTOR_EQUALS(v, boost::irange(0u, n)); |
616 | } |
617 | CHECK(d.happenings > 0); |
618 | IMMER_TRACE_E(d.happenings); |
619 | } |
620 | } |
621 | |