source: mainline/uspace/lib/cpp/src/__bits/test/map.cpp@ 8624d1f

Last change on this file since 8624d1f was b57ba05, checked in by Jiří Zárevúcky <zarevucky.jiri@…>, 3 years ago

Update headers in C++ files
  • Property mode set to 100644
File size: 13.9 KB
Line 
1/*
2 * SPDX-FileCopyrightText: 2018 Jaroslav Jindrak
3 *
4 * SPDX-License-Identifier: BSD-3-Clause
5 */
6
7#include <__bits/test/tests.hpp>
8#include <initializer_list>
9#include <map>
10#include <string>
11#include <sstream>
12#include <utility>
13
14namespace std::test
15{
16 bool map_test::run(bool report)
17 {
18 report_ = report;
19 start();
20
21 test_constructors_and_assignment();
22 test_histogram();
23 test_emplace_insert();
24 test_bounds_and_ranges();
25 test_multi();
26 test_reverse_iterators();
27 test_multi_bounds_and_ranges();
28
29 return end();
30 }
31
32 const char* map_test::name()
33 {
34 return "map";
35 }
36
37 void map_test::test_constructors_and_assignment()
38 {
39 auto check1 = {
40 std::pair<const int, int>{1, 1},
41 std::pair<const int, int>{2, 2},
42 std::pair<const int, int>{3, 3},
43 std::pair<const int, int>{4, 4},
44 std::pair<const int, int>{5, 5},
45 std::pair<const int, int>{6, 6},
46 std::pair<const int, int>{7, 7}
47 };
48 auto src1 = {
49 std::pair<const int, int>{3, 3},
50 std::pair<const int, int>{1, 1},
51 std::pair<const int, int>{5, 5},
52 std::pair<const int, int>{2, 2},
53 std::pair<const int, int>{7, 7},
54 std::pair<const int, int>{6, 6},
55 std::pair<const int, int>{4, 4}
56 };
57
58 std::map<int, int> m1{src1};
59 test_eq(
60 "initializer list initialization",
61 check1.begin(), check1.end(),
62 m1.begin(), m1.end()
63 );
64 test_eq("size", m1.size(), 7U);
65
66 std::map<int, int> m2{src1.begin(), src1.end()};
67 test_eq(
68 "iterator range initialization",
69 check1.begin(), check1.end(),
70 m2.begin(), m2.end()
71 );
72
73 std::map<int, int> m3{m1};
74 test_eq(
75 "copy initialization",
76 check1.begin(), check1.end(),
77 m3.begin(), m3.end()
78 );
79
80 std::map<int, int> m4{std::move(m1)};
81 test_eq(
82 "move initialization",
83 check1.begin(), check1.end(),
84 m4.begin(), m4.end()
85 );
86 test_eq("move initialization - origin empty", m1.size(), 0U);
87 test_eq("empty", m1.empty(), true);
88
89 m1 = m4;
90 test_eq(
91 "copy assignment",
92 check1.begin(), check1.end(),
93 m1.begin(), m1.end()
94 );
95
96 m4 = std::move(m1);
97 test_eq(
98 "move assignment",
99 check1.begin(), check1.end(),
100 m4.begin(), m4.end()
101 );
102 test_eq("move assignment - origin empty", m1.size(), 0U);
103
104 m1 = src1;
105 test_eq(
106 "initializer list assignment",
107 check1.begin(), check1.end(),
108 m1.begin(), m1.end()
109 );
110 }
111
112 void map_test::test_histogram()
113 {
114 std::string str{"a b a a c d b e a b b e d c a e"};
115 std::map<std::string, std::size_t> map{};
116 std::istringstream iss{str};
117 std::string word{};
118
119 while (iss >> word)
120 ++map[word];
121
122 test_eq("histogram pt1", map["a"], 5U);
123 test_eq("histogram pt2", map["b"], 4U);
124 test_eq("histogram pt3", map["c"], 2U);
125 test_eq("histogram pt4", map["d"], 2U);
126 test_eq("histogram pt5", map["e"], 3U);
127 test_eq("histogram pt6", map["f"], 0U);
128 test_eq("at", map.at("a"), 5U);
129 }
130
131 void map_test::test_emplace_insert()
132 {
133 std::map<int, int> map1{};
134
135 auto res1 = map1.emplace(1, 2);
136 test_eq("first emplace succession", res1.second, true);
137 test_eq("first emplace equivalence pt1", res1.first->first, 1);
138 test_eq("first emplace equivalence pt2", res1.first->second, 2);
139
140 auto res2 = map1.emplace(1, 3);
141 test_eq("second emplace failure", res2.second, false);
142 test_eq("second emplace equivalence pt1", res2.first->first, 1);
143 test_eq("second emplace equivalence pt2", res2.first->second, 2);
144
145 auto res3 = map1.emplace_hint(map1.begin(), 2, 4);
146 test_eq("first emplace_hint succession", (res3 != map1.end()), true);
147 test_eq("first emplace_hint equivalence pt1", res3->first, 2);
148 test_eq("first emplace_hint equivalence pt2", res3->second, 4);
149
150 auto res4 = map1.emplace_hint(map1.begin(), 2, 5);
151 test_eq("second emplace_hint failure", (res4 != map1.end()), true);
152 test_eq("second emplace_hint equivalence pt1", res4->first, 2);
153 test_eq("second emplace_hint equivalence pt2", res4->second, 4);
154
155 std::map<int, std::string> map2{};
156 auto res5 = map2.insert(std::pair<const int, const char*>{5, "A"});
157 test_eq("conversion insert succession", res5.second, true);
158 test_eq("conversion insert equivalence pt1", res5.first->first, 5);
159 test_eq("conversion insert equivalence pt2", res5.first->second, std::string{"A"});
160
161 auto res6 = map2.insert(std::pair<const int, std::string>{6, "B"});
162 test_eq("first insert succession", res6.second, true);
163 test_eq("first insert equivalence pt1", res6.first->first, 6);
164 test_eq("first insert equivalence pt2", res6.first->second, std::string{"B"});
165
166 auto res7 = map2.insert(std::pair<const int, std::string>{6, "C"});
167 test_eq("second insert failure", res7.second, false);
168 test_eq("second insert equivalence pt1", res7.first->first, 6);
169 test_eq("second insert equivalence pt2", res7.first->second, std::string{"B"});
170
171 auto res8 = map2.insert_or_assign(6, std::string{"D"});
172 test_eq("insert_or_*assign* result", res8.second, false);
173 test_eq("insert_or_*assign* equivalence pt1", res8.first->first, 6);
174 test_eq("insert_or_*assign* equivalence pt2", res8.first->second, std::string{"D"});
175
176 auto res9 = map2.insert_or_assign(7, std::string{"E"});
177 test_eq("*insert*_or_assign result", res9.second, true);
178 test_eq("*insert*_or_assign equivalence pt1", res9.first->first, 7);
179 test_eq("*insert*_or_assign equivalence pt2", res9.first->second, std::string{"E"});
180
181 auto res10 = map2.erase(map2.find(7));
182 test_eq("erase", map2.find(7), map2.end());
183 test_eq("highest erased", res10, map2.end());
184
185 auto res11 = map2.erase(6);
186 test_eq("erase by key pt1", res11, 1U);
187 auto res12 = map2.erase(6);
188 test_eq("erase by key pt2", res12, 0U);
189
190 std::map<int, int> map3{};
191 map3[1] = 1;
192 auto res13 = map3.erase(1);
193 test_eq("erase root by key pt1", res13, 1U);
194 test_eq("erase root by key pt2", map3.empty(), true);
195
196 map3[2] = 2;
197 auto res14 = map3.erase(map3.begin());
198 test_eq("erase root by iterator pt1", res14, map3.end());
199 test_eq("erase root by iterator pt2", map3.empty(), true);
200
201 map2.clear();
202 test_eq("clear", map2.empty(), true);
203
204 map3[1] = 1;
205 auto res15 = map3.count(1);
206 test_eq("count", res15, 1U);
207 }
208
209 void map_test::test_bounds_and_ranges()
210 {
211 std::map<int, int> map{};
212 for (int i = 0; i < 10; ++i)
213 map[i] = i;
214 for (int i = 15; i < 20; ++i)
215 map[i] = i;
216
217 auto res1 = map.lower_bound(5);
218 test_eq("lower_bound of present key", res1->first, 5);
219
220 auto res2 = map.lower_bound(13);
221 test_eq("lower_bound of absent key", res2->first, 9);
222
223 auto res3 = map.upper_bound(7);
224 test_eq("upper_bound of present key", res3->first, 8);
225
226 auto res4 = map.upper_bound(12);
227 test_eq("upper_bound of absent key", res4->first, 15);
228
229 auto res5 = map.equal_range(4);
230 test_eq("equal_range of present key pt1", res5.first->first, 4);
231 test_eq("equal_range of present key pt2", res5.second->first, 5);
232
233 auto res6 = map.equal_range(14);
234 test_eq("equal_range of absent key pt1", res6.first->first, 9);
235 test_eq("equal_range of absent key pt2", res6.second->first, 15);
236 }
237
238 void map_test::test_multi()
239 {
240 auto check1 = {
241 std::pair<const int, int>{1, 1},
242 std::pair<const int, int>{2, 2},
243 std::pair<const int, int>{3, 3},
244 std::pair<const int, int>{3, 3},
245 std::pair<const int, int>{4, 4},
246 std::pair<const int, int>{5, 5},
247 std::pair<const int, int>{6, 6},
248 std::pair<const int, int>{6, 6},
249 std::pair<const int, int>{6, 6},
250 std::pair<const int, int>{7, 7}
251 };
252 auto src1 = {
253 std::pair<const int, int>{3, 3},
254 std::pair<const int, int>{6, 6},
255 std::pair<const int, int>{1, 1},
256 std::pair<const int, int>{5, 5},
257 std::pair<const int, int>{6, 6},
258 std::pair<const int, int>{3, 3},
259 std::pair<const int, int>{2, 2},
260 std::pair<const int, int>{7, 7},
261 std::pair<const int, int>{6, 6},
262 std::pair<const int, int>{4, 4}
263 };
264
265 std::multimap<int, int> mmap{src1};
266 test_eq(
267 "multi construction",
268 check1.begin(), check1.end(),
269 mmap.begin(), mmap.end()
270 );
271
272 auto res1 = mmap.count(6);
273 test_eq("multi count", res1, 3U);
274
275 auto res2 = mmap.emplace(7, 2);
276 test_eq("multi duplicit emplace pt1", res2->first, 7);
277 test_eq("multi duplicit emplace pt2", res2->second, 2);
278 test_eq("multi duplicit emplace pt3", mmap.count(7), 2U);
279
280 auto res3 = mmap.emplace(8, 5);
281 test_eq("multi unique emplace pt1", res3->first, 8);
282 test_eq("multi unique emplace pt2", res3->second, 5);
283 test_eq("multi unique emplace pt3", mmap.count(8), 1U);
284
285 auto res4 = mmap.insert(std::pair<const int, int>{8, 6});
286 test_eq("multi duplicit insert pt1", res4->first, 8);
287 test_eq("multi duplicit insert pt2", res4->second, 6);
288 test_eq("multi duplicit insert pt3", mmap.count(8), 2U);
289
290 auto res5 = mmap.insert(std::pair<const int, int>{9, 8});
291 test_eq("multi unique insert pt1", res5->first, 9);
292 test_eq("multi unique insert pt2", res5->second, 8);
293 test_eq("multi unique insert pt3", mmap.count(9), 1U);
294
295 auto res6 = mmap.erase(8);
296 test_eq("multi erase by key pt1", res6, 2U);
297 test_eq("multi erase by key pt2", mmap.count(8), 0U);
298
299 auto res7 = mmap.erase(mmap.find(7));
300 test_eq("multi erase by iterator pt1", res7->first, 7);
301 test_eq("multi erase by iterator pt2", mmap.count(7), 1U);
302 }
303
304 void map_test::test_reverse_iterators()
305 {
306 auto check1 = {
307 std::pair<const int, int>{7, 7},
308 std::pair<const int, int>{6, 6},
309 std::pair<const int, int>{6, 6},
310 std::pair<const int, int>{6, 6},
311 std::pair<const int, int>{5, 5},
312 std::pair<const int, int>{4, 4},
313 std::pair<const int, int>{3, 3},
314 std::pair<const int, int>{3, 3},
315 std::pair<const int, int>{2, 2},
316 std::pair<const int, int>{1, 1}
317 };
318 auto src1 = {
319 std::pair<const int, int>{3, 3},
320 std::pair<const int, int>{6, 6},
321 std::pair<const int, int>{1, 1},
322 std::pair<const int, int>{5, 5},
323 std::pair<const int, int>{6, 6},
324 std::pair<const int, int>{3, 3},
325 std::pair<const int, int>{2, 2},
326 std::pair<const int, int>{7, 7},
327 std::pair<const int, int>{6, 6},
328 std::pair<const int, int>{4, 4}
329 };
330
331 std::multimap<int, int> mmap{src1};
332 test_eq(
333 "multi reverse iterators",
334 check1.begin(), check1.end(),
335 mmap.rbegin(), mmap.rend()
336 );
337
338 auto check2 = {
339 std::pair<const int, int>{7, 7},
340 std::pair<const int, int>{6, 6},
341 std::pair<const int, int>{5, 5},
342 std::pair<const int, int>{4, 4},
343 std::pair<const int, int>{3, 3},
344 std::pair<const int, int>{2, 2},
345 std::pair<const int, int>{1, 1}
346 };
347 auto src2 = {
348 std::pair<const int, int>{3, 3},
349 std::pair<const int, int>{1, 1},
350 std::pair<const int, int>{5, 5},
351 std::pair<const int, int>{2, 2},
352 std::pair<const int, int>{7, 7},
353 std::pair<const int, int>{6, 6},
354 std::pair<const int, int>{4, 4}
355 };
356
357 std::map<int, int> map{src2};
358 test_eq(
359 "reverse iterators",
360 check2.begin(), check2.end(),
361 map.rbegin(), map.rend()
362 );
363 }
364
365 void map_test::test_multi_bounds_and_ranges()
366 {
367 auto check1 = {
368 std::pair<const int, int>{1, 1},
369 std::pair<const int, int>{1, 2}
370 };
371 auto check2 = {
372 std::pair<const int, int>{5, 5},
373 std::pair<const int, int>{5, 6},
374 std::pair<const int, int>{5, 7}
375 };
376 auto check3 = {
377 std::pair<const int, int>{6, 6}
378 };
379 auto src = {
380 std::pair<const int, int>{1, 1},
381 std::pair<const int, int>{1, 2},
382 std::pair<const int, int>{2, 2},
383 std::pair<const int, int>{3, 3},
384 std::pair<const int, int>{5, 5},
385 std::pair<const int, int>{5, 6},
386 std::pair<const int, int>{5, 7},
387 std::pair<const int, int>{6, 6}
388 };
389
390 std::multimap<int, int> mmap{src};
391 auto res1 = mmap.equal_range(1);
392 test_eq(
393 "multi equal_range at the start",
394 check1.begin(), check1.end(),
395 res1.first, res1.second
396 );
397
398 auto res2 = mmap.equal_range(5);
399 test_eq(
400 "multi equal_range in the middle",
401 check2.begin(), check2.end(),
402 res2.first, res2.second
403 );
404
405 auto res3 = mmap.equal_range(6);
406 test_eq(
407 "multi equal_range at the end + single element range",
408 check3.begin(), check3.end(),
409 res3.first, res3.second
410 );
411 }
412}
Note: See TracBrowser for help on using the repository browser.