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
32template <typename V=FLEX_VECTOR_T<unsigned>>
33auto 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
41template <typename V=FLEX_VECTOR_T<unsigned>>
42auto 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
50template <std::size_t N>
51auto 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
66template <std::size_t N>
67auto 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
80template <std::size_t N>
81auto 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
96TEST_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
105TEST_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
118TEST_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
148auto 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
163TEST_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
170TEST_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
217TEST_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
234TEST_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
306TEST_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
328TEST_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
372TEST_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
383TEST_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
409TEST_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
423TEST_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
436TEST_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
450TEST_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
462TEST_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
474TEST_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
534TEST_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
545TEST_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