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 MAP_T
10#error "define the map template to use in MAP_T"
11#include <immer/map.hpp>
12#define MAP_T ::immer::map
13#endif
14
15#include <immer/algorithm.hpp>
16
17#include "test/util.hpp"
18#include "test/dada.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<std::pair<conflictor, unsigned>>{};
52 auto vals_ = std::unordered_set<conflictor, hash_conflictor>{};
53 auto i = 0u;
54 generate_n(back_inserter(vals), n, [&] {
55 auto newv = conflictor{};
56 do {
57 newv = { unsigned(gen() % (n / 2)), gen() };
58 } while (!vals_.insert(newv).second);
59 return std::pair<conflictor, unsigned>{newv, i++};
60 });
61 return vals;
62}
63
64auto make_test_map(unsigned n)
65{
66 auto s = MAP_T<unsigned, unsigned>{};
67 for (auto i = 0u; i < n; ++i)
68 s = s.insert({i, i});
69 return s;
70}
71
72auto make_test_map(const std::vector<std::pair<conflictor, unsigned>>& vals)
73{
74 auto s = MAP_T<conflictor, unsigned, hash_conflictor>{};
75 for (auto&& v : vals)
76 s = s.insert(v);
77 return s;
78}
79
80TEST_CASE("instantiation")
81{
82 SECTION("default")
83 {
84 auto v = MAP_T<int, int>{};
85 CHECK(v.size() == 0u);
86 }
87}
88
89TEST_CASE("basic insertion")
90{
91 auto v1 = MAP_T<int, int>{};
92 CHECK(v1.count(42) == 0);
93
94 auto v2 = v1.insert({42, {}});
95 CHECK(v1.count(42) == 0);
96 CHECK(v2.count(42) == 1);
97
98 auto v3 = v2.insert({42, {}});
99 CHECK(v1.count(42) == 0);
100 CHECK(v2.count(42) == 1);
101 CHECK(v3.count(42) == 1);
102}
103
104TEST_CASE("accessor")
105{
106 const auto n = 666u;
107 auto v = make_test_map(n);
108 CHECK(v[0] == 0);
109 CHECK(v[42] == 42);
110 CHECK(v[665] == 665);
111 CHECK(v[666] == 0);
112 CHECK(v[1234] == 0);
113}
114
115TEST_CASE("at")
116{
117 const auto n = 666u;
118 auto v = make_test_map(n);
119 CHECK(v.at(0) == 0);
120 CHECK(v.at(42) == 42);
121 CHECK(v.at(665) == 665);
122 CHECK_THROWS_AS(v.at(666), std::out_of_range&);
123 CHECK_THROWS_AS(v.at(1234), std::out_of_range&);
124}
125
126TEST_CASE("find")
127{
128 const auto n = 666u;
129 auto v = make_test_map(n);
130 CHECK(*v.find(0) == 0);
131 CHECK(*v.find(42) == 42);
132 CHECK(*v.find(665) == 665);
133 CHECK(v.find(666) == nullptr);
134 CHECK(v.find(1234) == nullptr);
135}
136
137TEST_CASE("equals and setting")
138{
139 const auto n = 666u;
140 auto v = make_test_map(n);
141
142 CHECK(v == v);
143 CHECK(v != v.insert({1234, 42}));
144 CHECK(v != v.erase(32));
145 CHECK(v == v.insert({1234, 42}).erase(1234));
146 CHECK(v == v.erase(32).insert({32, 32}));
147
148 CHECK(v.set(1234, 42) == v.insert({1234, 42}));
149 CHECK(v.update(1234, [] (auto&& x) { return x + 1; }) ==
150 v.set(1234, 1));
151 CHECK(v.update(42, [] (auto&& x) { return x + 1; }) ==
152 v.set(42, 43));
153}
154
155TEST_CASE("iterator")
156{
157 const auto N = 666u;
158 auto v = make_test_map(N);
159
160 SECTION("empty set")
161 {
162 auto s = MAP_T<unsigned, unsigned>{};
163 CHECK(s.begin() == s.end());
164 }
165
166 SECTION("works with range loop")
167 {
168 auto seen = std::unordered_set<unsigned>{};
169 for (const auto& x : v)
170 CHECK(seen.insert(x.first).second);
171 CHECK(seen.size() == v.size());
172 }
173
174 SECTION("iterator and collisions")
175 {
176 auto vals = make_values_with_collisions(N);
177 auto s = make_test_map(vals);
178 auto seen = std::unordered_set<conflictor, hash_conflictor>{};
179 for (const auto& x : s)
180 CHECK(seen.insert(x.first).second);
181 CHECK(seen.size() == s.size());
182 }
183}
184
185TEST_CASE("accumulate")
186{
187 const auto n = 666u;
188 auto v = make_test_map(n);
189
190 auto expected_n =
191 [] (auto n) {
192 return n * (n - 1) / 2;
193 };
194
195 SECTION("sum collection")
196 {
197 auto acc = [] (unsigned acc, const std::pair<unsigned, unsigned>& x) {
198 return acc + x.first + x.second;
199 };
200 auto sum = immer::accumulate(v, 0u, acc);
201 CHECK(sum == 2 * expected_n(v.size()));
202 }
203
204 SECTION("sum collisions") {
205 auto vals = make_values_with_collisions(n);
206 auto s = make_test_map(vals);
207 auto acc = [] (unsigned r, std::pair<conflictor, unsigned> x) {
208 return r + x.first.v1 + x.first.v2 + x.second;
209 };
210 auto sum1 = std::accumulate(vals.begin(), vals.end(), 0u, acc);
211 auto sum2 = immer::accumulate(s, 0u, acc);
212 CHECK(sum1 == sum2);
213 }
214}
215
216TEST_CASE("update a lot")
217{
218 auto v = make_test_map(666u);
219
220 for (decltype(v.size()) i = 0; i < v.size(); ++i) {
221 v = v.update(i, [] (auto&& x) { return x + 1; });
222 CHECK(v[i] == i+1);
223 }
224}
225
226TEST_CASE("exception safety")
227{
228 constexpr auto n = 2666u;
229
230 using dadaist_map_t = typename dadaist_wrapper<MAP_T<unsigned, unsigned>>::type;
231 using dadaist_conflictor_map_t = typename dadaist_wrapper<MAP_T<conflictor, unsigned, hash_conflictor>>::type;
232
233 SECTION("update collisions")
234 {
235 auto v = dadaist_map_t{};
236 auto d = dadaism{};
237 for (auto i = 0u; i < n; ++i)
238 v = v.set(i, i);
239 for (auto i = 0u; i < v.size();) {
240 try {
241 auto s = d.next();
242 v = v.update(i, [] (auto x) { return x + 1; });
243 ++i;
244 } catch (dada_error) {}
245 for (auto i : test_irange(0u, i))
246 CHECK(v.at(i) == i + 1);
247 for (auto i : test_irange(i, n))
248 CHECK(v.at(i) == i);
249 }
250 CHECK(d.happenings > 0);
251 IMMER_TRACE_E(d.happenings);
252 }
253
254 SECTION("update collisisions")
255 {
256 auto vals = make_values_with_collisions(n);
257 auto v = dadaist_conflictor_map_t{};
258 auto d = dadaism{};
259 for (auto i = 0u; i < n; ++i)
260 v = v.insert(vals[i]);
261 for (auto i = 0u; i < v.size();) {
262 try {
263 auto s = d.next();
264 v = v.update(vals[i].first, [] (auto x) { return x + 1; });
265 ++i;
266 } catch (dada_error) {}
267 for (auto i : test_irange(0u, i))
268 CHECK(v.at(vals[i].first) == vals[i].second + 1);
269 for (auto i : test_irange(i, n))
270 CHECK(v.at(vals[i].first) == vals[i].second);
271 }
272 CHECK(d.happenings > 0);
273 IMMER_TRACE_E(d.happenings);
274 }
275}
276