source: mainline/uspace/lib/cpp/src/internal/test/map.cpp@ 5608106c

lfn serial ticket/834-toolchain-update topic/msim-upgrade topic/simplify-dev-export
Last change on this file since 5608106c was 5608106c, checked in by Dzejrou <dzejrou@…>, 7 years ago

cpp: added map and multimap tests
  • Property mode set to 100644
File size: 15.2 KB
Line 
1/*
2 * Copyright (c) 2018 Jaroslav Jindrak
3 * All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
7 * are met:
8 *
9 * - Redistributions of source code must retain the above copyright
10 * notice, this list of conditions and the following disclaimer.
11 * - Redistributions in binary form must reproduce the above copyright
12 * notice, this list of conditions and the following disclaimer in the
13 * documentation and/or other materials provided with the distribution.
14 * - The name of the author may not be used to endorse or promote products
15 * derived from this software without specific prior written permission.
16 *
17 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
18 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
19 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
20 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
21 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
22 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
23 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
24 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
26 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27 */
28
29#include <initializer_list>
30#include <internal/test/tests.hpp>
31#include <map>
32#include <string>
33#include <sstream>
34#include <utility>
35
36namespace std::test
37{
38 bool map_test::run(bool report)
39 {
40 report_ = report;
41 start();
42
43 test_constructors_and_assignment();
44 test_histogram();
45 test_emplace_insert();
46 test_bounds_and_ranges();
47 test_multi();
48 test_reverse_iterators();
49 test_multi_bounds_and_ranges();
50
51 return end();
52 }
53
54 const char* map_test::name()
55 {
56 return "map";
57 }
58
59 void map_test::test_constructors_and_assignment()
60 {
61 auto check1 = {
62 std::pair<const int, int>{1, 1},
63 std::pair<const int, int>{2, 2},
64 std::pair<const int, int>{3, 3},
65 std::pair<const int, int>{4, 4},
66 std::pair<const int, int>{5, 5},
67 std::pair<const int, int>{6, 6},
68 std::pair<const int, int>{7, 7}
69 };
70 auto src1 = {
71 std::pair<const int, int>{3, 3},
72 std::pair<const int, int>{1, 1},
73 std::pair<const int, int>{5, 5},
74 std::pair<const int, int>{2, 2},
75 std::pair<const int, int>{7, 7},
76 std::pair<const int, int>{6, 6},
77 std::pair<const int, int>{4, 4}
78 };
79
80 std::map<int, int> m1{src1};
81 test_eq(
82 "initializer list initialization",
83 check1.begin(), check1.end(),
84 m1.begin(), m1.end()
85 );
86 test_eq("size", m1.size(), 7U);
87
88 std::map<int, int> m2{src1.begin(), src1.end()};
89 test_eq(
90 "iterator range initialization",
91 check1.begin(), check1.end(),
92 m2.begin(), m2.end()
93 );
94
95 std::map<int, int> m3{m1};
96 test_eq(
97 "copy initialization",
98 check1.begin(), check1.end(),
99 m3.begin(), m3.end()
100 );
101
102 std::map<int, int> m4{std::move(m1)};
103 test_eq(
104 "move initialization",
105 check1.begin(), check1.end(),
106 m4.begin(), m4.end()
107 );
108 test_eq("move initialization - origin empty", m1.size(), 0U);
109 test_eq("empty", m1.empty(), true);
110
111 m1 = m4;
112 test_eq(
113 "copy assignment",
114 check1.begin(), check1.end(),
115 m1.begin(), m1.end()
116 );
117
118 m4 = std::move(m1);
119 test_eq(
120 "move assignment",
121 check1.begin(), check1.end(),
122 m4.begin(), m4.end()
123 );
124 test_eq("move assignment - origin empty", m1.size(), 0U);
125
126 m1 = src1;
127 test_eq(
128 "initializer list assignment",
129 check1.begin(), check1.end(),
130 m1.begin(), m1.end()
131 );
132 }
133
134 void map_test::test_histogram()
135 {
136 std::string str{"a b a a c d b e a b b e d c a e"};
137 std::map<std::string, std::size_t> map{};
138 std::istringstream iss{str};
139 std::string word{};
140
141 while (iss >> word)
142 ++map[word];
143
144 test_eq("histogram pt1", map["a"], 5U);
145 test_eq("histogram pt2", map["b"], 4U);
146 test_eq("histogram pt3", map["c"], 2U);
147 test_eq("histogram pt4", map["d"], 2U);
148 test_eq("histogram pt5", map["e"], 3U);
149 test_eq("histogram pt6", map["f"], 0U);
150 test_eq("at", map.at("a"), 5U);
151 }
152
153 void map_test::test_emplace_insert()
154 {
155 std::map<int, int> map1{};
156
157 auto res1 = map1.emplace(1, 2);
158 test_eq("first emplace succession", res1.second, true);
159 test_eq("first emplace equivalence pt1", res1.first->first, 1);
160 test_eq("first emplace equivalence pt2", res1.first->second, 2);
161
162 auto res2 = map1.emplace(1, 3);
163 test_eq("second emplace failure", res2.second, false);
164 test_eq("second emplace equivalence pt1", res2.first->first, 1);
165 test_eq("second emplace equivalence pt2", res2.first->second, 2);
166
167 auto res3 = map1.emplace_hint(map1.begin(), 2, 4);
168 test_eq("first emplace_hint succession", (res3 != map1.end()), true);
169 test_eq("first emplace_hint equivalence pt1", res3->first, 2);
170 test_eq("first emplace_hint equivalence pt2", res3->second, 4);
171
172 auto res4 = map1.emplace_hint(map1.begin(), 2, 5);
173 test_eq("second emplace_hint failure", (res4 != map1.end()), true);
174 test_eq("second emplace_hint equivalence pt1", res4->first, 2);
175 test_eq("second emplace_hint equivalence pt2", res4->second, 4);
176
177 std::map<int, std::string> map2{};
178 auto res5 = map2.insert(std::pair<const int, const char*>{5, "A"});
179 test_eq("conversion insert succession", res5.second, true);
180 test_eq("conversion insert equivalence pt1", res5.first->first, 5);
181 test_eq("conversion insert equivalence pt2", res5.first->second, std::string{"A"});
182
183 auto res6 = map2.insert(std::pair<const int, std::string>{6, "B"});
184 test_eq("first insert succession", res6.second, true);
185 test_eq("first insert equivalence pt1", res6.first->first, 6);
186 test_eq("first insert equivalence pt2", res6.first->second, std::string{"B"});
187
188 auto res7 = map2.insert(std::pair<const int, std::string>{6, "C"});
189 test_eq("second insert failure", res7.second, false);
190 test_eq("second insert equivalence pt1", res7.first->first, 6);
191 test_eq("second insert equivalence pt2", res7.first->second, std::string{"B"});
192
193 auto res8 = map2.insert_or_assign(6, std::string{"D"});
194 test_eq("insert_or_*assign* result", res8.second, false);
195 test_eq("insert_or_*assign* equivalence pt1", res8.first->first, 6);
196 test_eq("insert_or_*assign* equivalence pt2", res8.first->second, std::string{"D"});
197
198 auto res9 = map2.insert_or_assign(7, std::string{"E"});
199 test_eq("*insert*_or_assign result", res9.second, true);
200 test_eq("*insert*_or_assign equivalence pt1", res9.first->first, 7);
201 test_eq("*insert*_or_assign equivalence pt2", res9.first->second, std::string{"E"});
202
203 auto res10 = map2.erase(map2.find(7));
204 test_eq("erase", map2.find(7), map2.end());
205 test_eq("highest erased", res10, map2.end());
206
207 auto res11 = map2.erase(6);
208 test_eq("erase by key pt1", res11, 1U);
209 auto res12 = map2.erase(6);
210 test_eq("erase by key pt2", res12, 0U);
211
212 std::map<int, int> map3{};
213 map3[1] = 1;
214 auto res13 = map3.erase(1);
215 test_eq("erase root by key pt1", res13, 1U);
216 test_eq("erase root by key pt2", map3.empty(), true);
217
218 map3[2] = 2;
219 auto res14 = map3.erase(map3.begin());
220 test_eq("erase root by iterator pt1", res14, map3.end());
221 test_eq("erase root by iterator pt2", map3.empty(), true);
222
223 map2.clear();
224 test_eq("clear", map2.empty(), true);
225
226 map3[1] = 1;
227 auto res15 = map3.count(1);
228 test_eq("count", res15, 1U);
229 }
230
231 void map_test::test_bounds_and_ranges()
232 {
233 std::map<int, int> map{};
234 for (int i = 0; i < 10; ++i)
235 map[i] = i;
236 for (int i = 15; i < 20; ++i)
237 map[i] = i;
238
239 auto res1 = map.lower_bound(5);
240 test_eq("lower_bound of present key", res1->first, 5);
241
242 auto res2 = map.lower_bound(13);
243 test_eq("lower_bound of absent key", res2->first, 9);
244
245 auto res3 = map.upper_bound(7);
246 test_eq("upper_bound of present key", res3->first, 8);
247
248 auto res4 = map.upper_bound(12);
249 test_eq("upper_bound of absent key", res4->first, 15);
250
251 auto res5 = map.equal_range(4);
252 test_eq("equal_range of present key pt1", res5.first->first, 4);
253 test_eq("equal_range of present key pt2", res5.second->first, 5);
254
255 auto res6 = map.equal_range(14);
256 test_eq("equal_range of absent key pt1", res6.first->first, 9);
257 test_eq("equal_range of absent key pt2", res6.second->first, 15);
258 }
259
260 void map_test::test_multi()
261 {
262 auto check1 = {
263 std::pair<const int, int>{1, 1},
264 std::pair<const int, int>{2, 2},
265 std::pair<const int, int>{3, 3},
266 std::pair<const int, int>{3, 3},
267 std::pair<const int, int>{4, 4},
268 std::pair<const int, int>{5, 5},
269 std::pair<const int, int>{6, 6},
270 std::pair<const int, int>{6, 6},
271 std::pair<const int, int>{6, 6},
272 std::pair<const int, int>{7, 7}
273 };
274 auto src1 = {
275 std::pair<const int, int>{3, 3},
276 std::pair<const int, int>{6, 6},
277 std::pair<const int, int>{1, 1},
278 std::pair<const int, int>{5, 5},
279 std::pair<const int, int>{6, 6},
280 std::pair<const int, int>{3, 3},
281 std::pair<const int, int>{2, 2},
282 std::pair<const int, int>{7, 7},
283 std::pair<const int, int>{6, 6},
284 std::pair<const int, int>{4, 4}
285 };
286
287 std::multimap<int, int> mmap{src1};
288 test_eq(
289 "multi construction",
290 check1.begin(), check1.end(),
291 mmap.begin(), mmap.end()
292 );
293
294 auto res1 = mmap.count(6);
295 test_eq("multi count", res1, 3U);
296
297 auto res2 = mmap.emplace(7, 2);
298 test_eq("multi duplicit emplace pt1", res2->first, 7);
299 test_eq("multi duplicit emplace pt2", res2->second, 2);
300 test_eq("multi duplicit emplace pt3", mmap.count(7), 2U);
301
302 auto res3 = mmap.emplace(8, 5);
303 test_eq("multi unique emplace pt1", res3->first, 8);
304 test_eq("multi unique emplace pt2", res3->second, 5);
305 test_eq("multi unique emplace pt3", mmap.count(8), 1U);
306
307 auto res4 = mmap.insert(std::pair<const int, int>{8, 6});
308 test_eq("multi duplicit insert pt1", res4->first, 8);
309 test_eq("multi duplicit insert pt2", res4->second, 6);
310 test_eq("multi duplicit insert pt3", mmap.count(8), 2U);
311
312 auto res5 = mmap.insert(std::pair<const int, int>{9, 8});
313 test_eq("multi unique insert pt1", res5->first, 9);
314 test_eq("multi unique insert pt2", res5->second, 8);
315 test_eq("multi unique insert pt3", mmap.count(9), 1U);
316
317 auto res6 = mmap.erase(8);
318 test_eq("multi erase by key pt1", res6, 2U);
319 test_eq("multi erase by key pt2", mmap.count(8), 0U);
320
321 auto res7 = mmap.erase(mmap.find(7));
322 test_eq("multi erase by iterator pt1", res7->first, 7);
323 test_eq("multi erase by iterator pt2", mmap.count(7), 1U);
324 }
325
326 void map_test::test_reverse_iterators()
327 {
328 auto check1 = {
329 std::pair<const int, int>{7, 7},
330 std::pair<const int, int>{6, 6},
331 std::pair<const int, int>{6, 6},
332 std::pair<const int, int>{6, 6},
333 std::pair<const int, int>{5, 5},
334 std::pair<const int, int>{4, 4},
335 std::pair<const int, int>{3, 3},
336 std::pair<const int, int>{3, 3},
337 std::pair<const int, int>{2, 2},
338 std::pair<const int, int>{1, 1}
339 };
340 auto src1 = {
341 std::pair<const int, int>{3, 3},
342 std::pair<const int, int>{6, 6},
343 std::pair<const int, int>{1, 1},
344 std::pair<const int, int>{5, 5},
345 std::pair<const int, int>{6, 6},
346 std::pair<const int, int>{3, 3},
347 std::pair<const int, int>{2, 2},
348 std::pair<const int, int>{7, 7},
349 std::pair<const int, int>{6, 6},
350 std::pair<const int, int>{4, 4}
351 };
352
353 std::multimap<int, int> mmap{src1};
354 test_eq(
355 "multi reverse iterators",
356 check1.begin(), check1.end(),
357 mmap.rbegin(), mmap.rend()
358 );
359
360 auto check2 = {
361 std::pair<const int, int>{7, 7},
362 std::pair<const int, int>{6, 6},
363 std::pair<const int, int>{5, 5},
364 std::pair<const int, int>{4, 4},
365 std::pair<const int, int>{3, 3},
366 std::pair<const int, int>{2, 2},
367 std::pair<const int, int>{1, 1}
368 };
369 auto src2 = {
370 std::pair<const int, int>{3, 3},
371 std::pair<const int, int>{1, 1},
372 std::pair<const int, int>{5, 5},
373 std::pair<const int, int>{2, 2},
374 std::pair<const int, int>{7, 7},
375 std::pair<const int, int>{6, 6},
376 std::pair<const int, int>{4, 4}
377 };
378
379 std::map<int, int> map{src2};
380 test_eq(
381 "reverse iterators",
382 check2.begin(), check2.end(),
383 map.rbegin(), map.rend()
384 );
385 }
386
387 void map_test::test_multi_bounds_and_ranges()
388 {
389 auto check1 = {
390 std::pair<const int, int>{1, 1},
391 std::pair<const int, int>{1, 2}
392 };
393 auto check2 = {
394 std::pair<const int, int>{5, 5},
395 std::pair<const int, int>{5, 6},
396 std::pair<const int, int>{5, 7}
397 };
398 auto check3 = {
399 std::pair<const int, int>{6, 6}
400 };
401 auto src = {
402 std::pair<const int, int>{1, 1},
403 std::pair<const int, int>{1, 2},
404 std::pair<const int, int>{2, 2},
405 std::pair<const int, int>{3, 3},
406 std::pair<const int, int>{5, 5},
407 std::pair<const int, int>{5, 6},
408 std::pair<const int, int>{5, 7},
409 std::pair<const int, int>{6, 6}
410 };
411
412 std::multimap<int, int> mmap{src};
413 auto res1 = mmap.equal_range(1);
414 test_eq(
415 "multi equal_range at the start",
416 check1.begin(), check1.end(),
417 res1.first, res1.second
418 );
419
420 auto res2 = mmap.equal_range(5);
421 test_eq(
422 "multi equal_range in the middle",
423 check2.begin(), check2.end(),
424 res2.first, res2.second
425 );
426
427 auto res3 = mmap.equal_range(6);
428 test_eq(
429 "multi equal_range at the end + single element range",
430 check3.begin(), check3.end(),
431 res3.first, res3.second
432 );
433 }
434}
Note: See TracBrowser for help on using the repository browser.