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/util.hpp"
10#include "test/dada.hpp"
11
12#include <immer/algorithm.hpp>
13
14#include <catch.hpp>
15#include <boost/range/adaptors.hpp>
16
17#include <algorithm>
18#include <numeric>
19#include <string>
20#include <vector>
21
22using namespace std::string_literals;
23
24#ifndef VECTOR_T
25#error "define the vector template to use in VECTOR_T"
26#endif
27
28template <typename V=VECTOR_T<unsigned>>
29auto make_test_vector(unsigned min, unsigned max)
30{
31 auto v = V{};
32 for (auto i = min; i < max; ++i)
33 v = v.push_back({i});
34 return v;
35}
36
37struct big_object
38{
39 std::array<std::size_t, 42> v;
40};
41
42struct string_sentinel {};
43
44bool operator==(const char16_t* i, string_sentinel ){
45 return *i == '\0';
46}
47
48bool operator!=(const char16_t* i, string_sentinel ){
49 return *i != '\0';
50}
51
52TEST_CASE("instantiation")
53{
54 SECTION("default")
55 {
56 auto v = VECTOR_T<int>{};
57 CHECK(v.size() == 0u);
58 CHECK(v.empty());
59 }
60
61 SECTION("initializer list")
62 {
63 auto v = VECTOR_T<unsigned>{0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
64 CHECK_VECTOR_EQUALS(v, boost::irange(0u, 10u));
65 CHECK(!v.empty());
66 }
67
68 SECTION("big object")
69 {
70 auto v = VECTOR_T<big_object>{{}, {}, {}, {}};
71 CHECK(v.size() == 4);
72 }
73
74 SECTION("range")
75 {
76 auto r = std::vector<int>{{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}};
77 auto v = VECTOR_T<unsigned>{r.begin(), r.end()};
78 CHECK_VECTOR_EQUALS(v, boost::irange(0u, 10u));
79 }
80
81 SECTION("iterator/sentinel")
82 {
83 auto r = u"012345678";
84 string_sentinel s;
85 auto v = VECTOR_T<unsigned>{r, s};
86 CHECK_VECTOR_EQUALS(v, boost::irange(u'0', u'9'));
87 }
88
89 SECTION("fill")
90 {
91 auto v1 = VECTOR_T<int>(4);
92 CHECK(v1.size() == 4);
93 auto v2 = VECTOR_T<int>(4, 42);
94 CHECK(v2.size() == 4);
95 CHECK(v2[2] == 42);
96 }
97}
98
99TEST_CASE("back and front")
100{
101 auto v = VECTOR_T<unsigned>{0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
102 CHECK(v.front() == 0);
103 CHECK(v.back() == 9);
104}
105
106TEST_CASE("at")
107{
108 auto v = VECTOR_T<unsigned>{0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
109 CHECK(v.at(0) == 0);
110 CHECK(v.at(5) == 5);
111 CHECK_THROWS_AS(v.at(10), const std::out_of_range&);
112 CHECK_THROWS_AS(v.at(11), const std::out_of_range&);
113}
114
115TEST_CASE("push back one element")
116{
117 SECTION("one element")
118 {
119 const auto v1 = VECTOR_T<int>{};
120 auto v2 = v1.push_back(42);
121 CHECK(v1.size() == 0u);
122 CHECK(v2.size() == 1u);
123 CHECK(v2[0] == 42);
124 }
125
126 SECTION("many elements")
127 {
128 const auto n = 666u;
129 auto v = VECTOR_T<unsigned>{};
130 for (auto i = 0u; i < n; ++i) {
131 v = v.push_back(i * 42);
132 CHECK(v.size() == i + 1);
133 for (decltype(v.size()) j = 0; j < v.size(); ++j)
134 CHECK(v[j] == j * 42);
135 }
136 }
137}
138
139TEST_CASE("update")
140{
141 const auto n = 42u;
142 auto v = make_test_vector(0, n);
143
144 SECTION("set")
145 {
146 const auto u = v.set(3u, 13u);
147 CHECK(u.size() == v.size());
148 CHECK(u[2u] == 2u);
149 CHECK(u[3u] == 13u);
150 CHECK(u[4u] == 4u);
151 CHECK(u[40u] == 40u);
152 CHECK(v[3u] == 3u);
153 }
154
155 SECTION("set further")
156 {
157 auto v = make_test_vector(0, 666);
158
159 auto u = v.set(3u, 13u);
160 u = u.set(200u, 7u);
161 CHECK(u.size() == v.size());
162
163 CHECK(u[2u] == 2u);
164 CHECK(u[4u] == 4u);
165 CHECK(u[40u] == 40u);
166 CHECK(u[600u] == 600u);
167
168 CHECK(u[3u] == 13u);
169 CHECK(u[200u] == 7u);
170
171 CHECK(v[3u] == 3u);
172 CHECK(v[200u] == 200u);
173 }
174
175 SECTION("set further more")
176 {
177 auto v = make_test_vector(0, 666u);
178
179 for (decltype(v.size()) i = 0; i < v.size(); ++i) {
180 v = v.set(i, i+1);
181 CHECK(v[i] == i+1);
182 }
183 }
184
185 SECTION("update")
186 {
187 const auto u = v.update(10u, [] (auto x) { return x + 10; });
188 CHECK(u.size() == v.size());
189 CHECK(u[10u] == 20u);
190 CHECK(v[40u] == 40u);
191
192 const auto w = v.update(40u, [] (auto x) { return x - 10; });
193 CHECK(w.size() == v.size());
194 CHECK(w[40u] == 30u);
195 CHECK(v[40u] == 40u);
196 }
197}
198
199TEST_CASE("iterator")
200{
201 const auto n = 666u;
202 auto v = make_test_vector(0, n);
203
204 SECTION("empty vector")
205 {
206 auto v = VECTOR_T<unsigned>{};
207 CHECK(v.begin() == v.end());
208 }
209
210 SECTION("works with range loop")
211 {
212 auto i = 0u;
213 for (const auto& x : v)
214 CHECK(x == i++);
215 CHECK(i == v.size());
216 }
217
218 SECTION("works with standard algorithms")
219 {
220 auto s = std::vector<unsigned>(n);
221 std::iota(s.begin(), s.end(), 0u);
222 std::equal(v.begin(), v.end(), s.begin(), s.end());
223 }
224
225 SECTION("can go back from end")
226 {
227 auto expected = n - 1;
228 auto last = v.end();
229 CHECK(expected == *--last);
230 }
231
232 SECTION("works with reversed range adaptor")
233 {
234 auto r = v | boost::adaptors::reversed;
235 auto i = n;
236 for (const auto& x : r)
237 CHECK(x == --i);
238 }
239
240 SECTION("works with strided range adaptor")
241 {
242 auto r = v | boost::adaptors::strided(5);
243 auto i = 0u;
244 for (const auto& x : r)
245 CHECK(x == 5 * i++);
246 }
247
248 SECTION("works reversed")
249 {
250 auto i = n;
251 for (auto iter = v.rbegin(), last = v.rend(); iter != last; ++iter)
252 CHECK(*iter == --i);
253 }
254
255 SECTION("advance and distance")
256 {
257 auto i1 = v.begin();
258 auto i2 = i1 + 100;
259 CHECK(100u == *i2);
260 CHECK(100 == i2 - i1);
261 CHECK(50u == *(i2 - 50));
262 CHECK(-30 == (i2 - 30) - i2);
263 }
264}
265
266TEST_CASE("equals")
267{
268 const auto n = 666u;
269 auto v = make_test_vector(0, n);
270
271 CHECK(v == v);
272 CHECK(v == v.set(42, 42));
273 CHECK(v != v.set(42, 24));
274 CHECK(v == v.set(42, 24).set(42, 42));
275 CHECK(v.set(42, 24) == v.set(42, 24));
276 CHECK(v != v.push_back(7));
277 CHECK(v.push_back(7) == v.push_back(7));
278 CHECK(v.push_back(5) != v.push_back(7));
279 CHECK(v != v.set(v.size()-2, 24));
280 CHECK(v == v
281 .set(v.size()-2, 24)
282 .set(v.size()-2, v[v.size()-2]));
283}
284
285TEST_CASE("all of")
286{
287 const auto n = 666u;
288 auto v = make_test_vector(0, n);
289
290 SECTION("false")
291 {
292 auto res = immer::all_of(v, [] (auto x) { return x < 100; });
293 CHECK(res == false);
294 }
295 SECTION("true")
296 {
297 auto res = immer::all_of(v, [] (auto x) { return x < 1000; });
298 CHECK(res == true);
299 }
300 SECTION("bounded, true")
301 {
302 auto res = immer::all_of(v.begin() + 101,
303 v.end() - 10,
304 [] (auto x) { return x > 100; });
305 CHECK(res == true);
306 }
307 SECTION("bounded, false")
308 {
309 auto res = immer::all_of(v.begin() + 101,
310 v.end() - 10,
311 [] (auto x) { return x < 600; });
312 CHECK(res == false);
313 }
314}
315
316TEST_CASE("accumulate")
317{
318 const auto n = 666u;
319 auto v = make_test_vector(0, n);
320
321 auto expected_n =
322 [] (auto n) {
323 return n * (n - 1) / 2;
324 };
325 auto expected_i =
326 [&] (auto i, auto n) {
327 return expected_n(n) - expected_n(i);
328 };
329
330 SECTION("sum collection")
331 {
332 auto sum = immer::accumulate(v, 0u);
333 CHECK(sum == expected_n(v.size()));
334 }
335
336 SECTION("sum range")
337 {
338 using namespace std;
339 {
340 auto sum = immer::accumulate(begin(v) + 100,
341 begin(v) + 300,
342 0u);
343 CHECK(sum == expected_i(100, 300));
344 }
345 {
346 auto sum = immer::accumulate(begin(v) + 31,
347 begin(v) + 300, 0u);
348 CHECK(sum == expected_i(31, 300));
349 }
350 {
351 auto sum = immer::accumulate(begin(v), begin(v) + 33, 0u);
352 CHECK(sum == expected_i(0, 33));
353 }
354 {
355 auto sum = immer::accumulate(begin(v) + 100,
356 begin(v) + 660, 0u);
357 CHECK(sum == expected_i(100, 660));
358 }
359 {
360 auto sum = immer::accumulate(begin(v) + 100,
361 begin(v) + 105, 0u);
362 CHECK(sum == expected_i(100, 105));
363 }
364 {
365 auto sum = immer::accumulate(begin(v) + 660,
366 begin(v) + 664, 0u);
367 CHECK(sum == expected_i(660, 664));
368 }
369 }
370}
371
372TEST_CASE("vector of strings")
373{
374 const auto n = 666u;
375
376 auto v = VECTOR_T<std::string>{};
377 for (auto i = 0u; i < n; ++i)
378 v = v.push_back(std::to_string(i));
379
380 for (decltype(v.size()) i = 0; i < v.size(); ++i)
381 CHECK(v[i] == std::to_string(i));
382
383 SECTION("set")
384 {
385 for (auto i = 0u; i < n; ++i)
386 v = v.set(i, "foo " + std::to_string(i));
387 for (auto i = 0u; i < n; ++i)
388 CHECK(v[i] == "foo " + std::to_string(i));
389 }
390}
391
392struct non_default
393{
394 unsigned value;
395 non_default() = delete;
396 operator unsigned() const { return value; }
397
398#if IMMER_DEBUG_PRINT
399 friend std::ostream& operator<< (std::ostream& os, non_default x)
400 {
401 os << "ND{" << x.value << "}";
402 return os;
403 }
404#endif
405};
406
407TEST_CASE("non default")
408{
409 const auto n = 666u;
410
411 auto v = VECTOR_T<non_default>{};
412 for (auto i = 0u; i < n; ++i)
413 v = v.push_back({ i });
414
415 CHECK_VECTOR_EQUALS(v, boost::irange(0u, n));
416
417 SECTION("set")
418 {
419 for (auto i = 0u; i < n; ++i)
420 v = v.set(i, {i + 1});
421
422 CHECK_VECTOR_EQUALS(v, boost::irange(1u, n + 1u));
423 }
424}
425
426TEST_CASE("take")
427{
428 const auto n = 666u;
429
430 SECTION("anywhere")
431 {
432 auto v = make_test_vector(0, n);
433
434 for (auto i : test_irange(0u, n)) {
435 auto vv = v.take(i);
436 CHECK(vv.size() == i);
437 CHECK_VECTOR_EQUALS_RANGE(vv, v.begin(), v.begin() + i);
438 }
439 }
440}
441
442TEST_CASE("exception safety")
443{
444 constexpr auto n = 666u;
445
446 using dadaist_vector_t = typename dadaist_wrapper<VECTOR_T<unsigned>>::type;
447
448 SECTION("push back")
449 {
450 auto v = dadaist_vector_t{};
451 auto d = dadaism{};
452 for (auto i = 0u; v.size() < static_cast<decltype(v.size())>(n);) {
453 auto s = d.next();
454 try {
455 v = v.push_back({i});
456 ++i;
457 } catch (dada_error) {}
458 CHECK_VECTOR_EQUALS(v, boost::irange(0u, i));
459 }
460 CHECK(d.happenings > 0);
461 IMMER_TRACE_E(d.happenings);
462 }
463
464 SECTION("update")
465 {
466 auto v = make_test_vector<dadaist_vector_t>(0, n);
467 auto d = dadaism{};
468 for (auto i = 0u; i < n;) {
469 auto s = d.next();
470 try {
471 v = v.update(i, [] (auto x) { return dada(), x + 1; });
472 ++i;
473 } catch (dada_error) {}
474 CHECK_VECTOR_EQUALS(v, boost::join(
475 boost::irange(1u, 1u + i),
476 boost::irange(i, n)));
477 }
478 CHECK(d.happenings > 0);
479 IMMER_TRACE_E(d.happenings);
480 }
481
482 SECTION("take")
483 {
484 auto v = make_test_vector<dadaist_vector_t>(0, n);
485 auto d = dadaism{};
486 for (auto i = 0u; i < n;) {
487 auto s = d.next();
488 auto r = dadaist_vector_t{};
489 try {
490 r = v.take(i);
491 CHECK_VECTOR_EQUALS(r, boost::irange(0u, i++));
492 } catch (dada_error) {
493 CHECK_VECTOR_EQUALS(r, boost::irange(0u, 0u));
494 }
495 }
496 CHECK(d.happenings > 0);
497 IMMER_TRACE_E(d.happenings);
498 }
499}
500