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 | |
22 | using namespace std::string_literals; |
23 | |
24 | #ifndef VECTOR_T |
25 | #error "define the vector template to use in VECTOR_T" |
26 | #endif |
27 | |
28 | template <typename V=VECTOR_T<unsigned>> |
29 | auto 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 | |
37 | struct big_object |
38 | { |
39 | std::array<std::size_t, 42> v; |
40 | }; |
41 | |
42 | struct string_sentinel {}; |
43 | |
44 | bool operator==(const char16_t* i, string_sentinel ){ |
45 | return *i == '\0'; |
46 | } |
47 | |
48 | bool operator!=(const char16_t* i, string_sentinel ){ |
49 | return *i != '\0'; |
50 | } |
51 | |
52 | TEST_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 | |
99 | TEST_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 | |
106 | TEST_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 | |
115 | TEST_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 | |
139 | TEST_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 | |
199 | TEST_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 | |
266 | TEST_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 | |
285 | TEST_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 | |
316 | TEST_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 | |
372 | TEST_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 | |
392 | struct 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 | |
407 | TEST_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 | |
426 | TEST_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 | |
442 | TEST_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 | |