1/****************************************************************************
2**
3** Copyright (C) 2016 The Qt Company Ltd.
4** Contact: https://www.qt.io/licensing/
5**
6** This file is part of the test suite of the Qt Toolkit.
7**
8** $QT_BEGIN_LICENSE:GPL-EXCEPT$
9** Commercial License Usage
10** Licensees holding valid commercial Qt licenses may use this file in
11** accordance with the commercial license agreement provided with the
12** Software or, alternatively, in accordance with the terms contained in
13** a written agreement between you and The Qt Company. For licensing terms
14** and conditions see https://www.qt.io/terms-conditions. For further
15** information use the contact form at https://www.qt.io/contact-us.
16**
17** GNU General Public License Usage
18** Alternatively, this file may be used under the terms of the GNU
19** General Public License version 3 as published by the Free Software
20** Foundation with exceptions as appearing in the file LICENSE.GPL3-EXCEPT
21** included in the packaging of this file. Please review the following
22** information to ensure the GNU General Public License requirements will
23** be met: https://www.gnu.org/licenses/gpl-3.0.html.
24**
25** $QT_END_LICENSE$
26**
27****************************************************************************/
28
29#include <qmap.h>
30#include <QtTest/QtTest>
31#include <QDebug>
32
33
34class tst_QMap : public QObject
35{
36 Q_OBJECT
37protected:
38 template <class KEY, class VALUE>
39 void sanityCheckTree(const QMap<KEY, VALUE> &m, int calledFromLine);
40public slots:
41 void init();
42private slots:
43 void ctor();
44 void count();
45 void clear();
46 void beginEnd();
47 void firstLast();
48 void key();
49
50 void swap();
51
52 void operator_eq();
53
54 void empty();
55 void contains();
56 void find();
57 void constFind();
58 void lowerUpperBound();
59 void mergeCompare();
60 void take();
61
62 void iterators();
63 void keyIterator();
64 void keyValueIterator();
65 void keys_values_uniqueKeys();
66 void qmultimap_specific();
67
68 void const_shared_null();
69
70 void equal_range();
71 void setSharable();
72
73 void insert();
74 void insertMap();
75 void checkMostLeftNode();
76 void initializerList();
77 void testInsertWithHint();
78 void testInsertMultiWithHint();
79 void eraseValidIteratorOnSharedMap();
80};
81
82struct IdentityTracker {
83 int value, id;
84};
85
86inline bool operator<(IdentityTracker lhs, IdentityTracker rhs) { return lhs.value < rhs.value; }
87
88typedef QMap<QString, QString> StringMap;
89
90class MyClass
91{
92public:
93 MyClass() {
94 ++count;
95 }
96 MyClass( const QString& c) {
97 count++; str = c;
98 }
99 ~MyClass() {
100 count--;
101 }
102 MyClass( const MyClass& c ) {
103 count++; str = c.str;
104 }
105 MyClass &operator =(const MyClass &o) {
106 str = o.str; return *this;
107 }
108
109 QString str;
110 static int count;
111};
112
113int MyClass::count = 0;
114
115typedef QMap<QString, MyClass> MyMap;
116
117QDebug operator << (QDebug d, const MyClass &c) {
118 d << c.str;
119 return d;
120}
121
122template <class KEY, class VALUE>
123void tst_QMap::sanityCheckTree(const QMap<KEY, VALUE> &m, int calledFromLine)
124{
125 QString possibleFrom;
126 possibleFrom.setNum(n: calledFromLine);
127 possibleFrom = "Called from line: " + possibleFrom;
128 int count = 0;
129 typename QMap<KEY, VALUE>::const_iterator oldite = m.constBegin();
130 for (typename QMap<KEY, VALUE>::const_iterator i = m.constBegin(); i != m.constEnd(); ++i) {
131 count++;
132 bool oldIteratorIsLarger = i.key() < oldite.key();
133 QVERIFY2(!oldIteratorIsLarger, possibleFrom.toUtf8());
134 oldite = i;
135 }
136 if (m.size() != count) { // Fail
137 qDebug() << possibleFrom;
138 QCOMPARE(m.size(), count);
139 }
140 if (m.size() == 0)
141 QVERIFY(m.constBegin() == m.constEnd());
142}
143
144void tst_QMap::init()
145{
146 MyClass::count = 0;
147}
148
149void tst_QMap::ctor()
150{
151 std::map<int, int> map;
152 for (int i = 0; i < 100000; ++i)
153 map.insert(x: std::pair<int, int>(i * 3, i * 7));
154
155 QMap<int, int> qmap(map); // ctor.
156
157 // Check that we have the same
158 std::map<int, int>::iterator j = map.begin();
159 QMap<int, int>::const_iterator i = qmap.constBegin();
160
161 while (i != qmap.constEnd()) {
162 QCOMPARE( (*j).first, i.key());
163 QCOMPARE( (*j).second, i.value());
164 ++i;
165 ++j;
166 }
167
168 QCOMPARE( (int) map.size(), qmap.size());
169}
170
171
172
173void tst_QMap::count()
174{
175 {
176 MyMap map;
177 MyMap map2( map );
178 QCOMPARE( map.count(), 0 );
179 QCOMPARE( map2.count(), 0 );
180 QCOMPARE( MyClass::count, int(0) );
181 // detach
182 map2["Hallo"] = MyClass( "Fritz" );
183 QCOMPARE( map.count(), 0 );
184 QCOMPARE( map2.count(), 1 );
185#ifndef Q_CC_SUN
186 QCOMPARE( MyClass::count, 1 );
187#endif
188 }
189 QCOMPARE( MyClass::count, int(0) );
190
191 {
192 typedef QMap<QString, MyClass> Map;
193 Map map;
194 QCOMPARE( map.count(), 0);
195 map.insert( akey: "Torben", avalue: MyClass("Weis") );
196 QCOMPARE( map.count(), 1 );
197 map.insert( akey: "Claudia", avalue: MyClass("Sorg") );
198 QCOMPARE( map.count(), 2 );
199 map.insert( akey: "Lars", avalue: MyClass("Linzbach") );
200 map.insert( akey: "Matthias", avalue: MyClass("Ettrich") );
201 map.insert( akey: "Sue", avalue: MyClass("Paludo") );
202 map.insert( akey: "Eirik", avalue: MyClass("Eng") );
203 map.insert( akey: "Haavard", avalue: MyClass("Nord") );
204 map.insert( akey: "Arnt", avalue: MyClass("Gulbrandsen") );
205 map.insert( akey: "Paul", avalue: MyClass("Tvete") );
206 QCOMPARE( map.count(), 9 );
207 map.insert( akey: "Paul", avalue: MyClass("Tvete 1") );
208 map.insert( akey: "Paul", avalue: MyClass("Tvete 2") );
209 map.insert( akey: "Paul", avalue: MyClass("Tvete 3") );
210 map.insert( akey: "Paul", avalue: MyClass("Tvete 4") );
211 map.insert( akey: "Paul", avalue: MyClass("Tvete 5") );
212 map.insert( akey: "Paul", avalue: MyClass("Tvete 6") );
213
214 QCOMPARE( map.count(), 9 );
215 QCOMPARE( map.count("Paul"), 1 );
216#ifndef Q_CC_SUN
217 QCOMPARE( MyClass::count, 9 );
218#endif
219
220 Map map2( map );
221 QVERIFY( map2.count() == 9 );
222#ifndef Q_CC_SUN
223 QCOMPARE( MyClass::count, 9 );
224#endif
225
226 map2.insert( akey: "Kay", avalue: MyClass("Roemer") );
227 QVERIFY( map2.count() == 10 );
228 QVERIFY( map.count() == 9 );
229#ifndef Q_CC_SUN
230 QCOMPARE( MyClass::count, 19 );
231#endif
232
233 map2 = map;
234 QVERIFY( map.count() == 9 );
235 QVERIFY( map2.count() == 9 );
236#ifndef Q_CC_SUN
237 QCOMPARE( MyClass::count, 9 );
238#endif
239
240 map2.insert( akey: "Kay", avalue: MyClass("Roemer") );
241 QVERIFY( map2.count() == 10 );
242#ifndef Q_CC_SUN
243 QCOMPARE( MyClass::count, 19 );
244#endif
245
246 map2.clear();
247 QVERIFY( map.count() == 9 );
248 QVERIFY( map2.count() == 0 );
249#ifndef Q_CC_SUN
250 QCOMPARE( MyClass::count, 9 );
251#endif
252
253 map2 = map;
254 QVERIFY( map.count() == 9 );
255 QVERIFY( map2.count() == 9 );
256#ifndef Q_CC_SUN
257 QCOMPARE( MyClass::count, 9 );
258#endif
259
260 map2.clear();
261 QVERIFY( map.count() == 9 );
262 QVERIFY( map2.count() == 0 );
263#ifndef Q_CC_SUN
264 QCOMPARE( MyClass::count, 9 );
265#endif
266
267 map.remove( akey: "Lars" );
268 QVERIFY( map.count() == 8 );
269 QVERIFY( map2.count() == 0 );
270#ifndef Q_CC_SUN
271 QCOMPARE( MyClass::count, 8 );
272#endif
273
274 map.remove( akey: "Mist" );
275 QVERIFY( map.count() == 8 );
276 QVERIFY( map2.count() == 0 );
277#ifndef Q_CC_SUN
278 QCOMPARE( MyClass::count, 8 );
279#endif
280 }
281 QVERIFY( MyClass::count == 0 );
282
283 {
284 typedef QMap<QString,MyClass> Map;
285 Map map;
286 map["Torben"] = MyClass("Weis");
287#ifndef Q_CC_SUN
288 QVERIFY( MyClass::count == 1 );
289#endif
290 QVERIFY( map.count() == 1 );
291
292 (void)map["Torben"].str;
293 (void)map["Lars"].str;
294#ifndef Q_CC_SUN
295 QVERIFY( MyClass::count == 2 );
296#endif
297 QVERIFY( map.count() == 2 );
298
299 const Map& cmap = map;
300 (void)cmap["Depp"].str;
301#ifndef Q_CC_SUN
302 QVERIFY( MyClass::count == 2 );
303#endif
304 QVERIFY( map.count() == 2 );
305 QVERIFY( cmap.count() == 2 );
306 }
307 QCOMPARE( MyClass::count, 0 );
308 {
309 for ( int i = 0; i < 100; ++i )
310 {
311 QMap<int, MyClass> map;
312 for (int j = 0; j < i; ++j)
313 map.insert(akey: j, avalue: MyClass(QString::number(j)));
314 }
315 QCOMPARE( MyClass::count, 0 );
316 }
317 QCOMPARE( MyClass::count, 0 );
318}
319
320void tst_QMap::clear()
321{
322 {
323 MyMap map;
324 map.clear();
325 QVERIFY( map.isEmpty() );
326 map.insert( akey: "key", avalue: MyClass( "value" ) );
327 map.clear();
328 QVERIFY( map.isEmpty() );
329 map.insert( akey: "key0", avalue: MyClass( "value0" ) );
330 map.insert( akey: "key0", avalue: MyClass( "value1" ) );
331 map.insert( akey: "key1", avalue: MyClass( "value2" ) );
332 map.clear();
333 sanityCheckTree(m: map, __LINE__);
334 QVERIFY( map.isEmpty() );
335 }
336 QCOMPARE( MyClass::count, int(0) );
337}
338
339void tst_QMap::beginEnd()
340{
341 StringMap m0;
342 QVERIFY( m0.begin() == m0.end() );
343 QVERIFY( m0.begin() == m0.begin() );
344
345 // sample string->string map
346 StringMap map;
347 QVERIFY( map.constBegin() == map.constEnd() );
348 map.insert( akey: "0", avalue: "a" );
349 map.insert( akey: "1", avalue: "b" );
350 QVERIFY( map.constBegin() == map.cbegin() );
351 QVERIFY( map.constEnd() == map.cend() );
352
353 // make a copy. const function shouldn't detach
354 StringMap map2 = map;
355 QVERIFY( map.constBegin() == map2.constBegin() );
356 QVERIFY( map.constEnd() == map2.constEnd() );
357
358 // test iteration
359 QString result;
360 for ( StringMap::ConstIterator it = map.constBegin();
361 it != map.constEnd(); ++it )
362 result += *it;
363 QCOMPARE( result, QString( "ab" ) );
364
365 // maps should still be identical
366 QVERIFY( map.constBegin() == map2.constBegin() );
367 QVERIFY( map.constEnd() == map2.constEnd() );
368
369 // detach
370 map2.insert( akey: "2", avalue: "c" );
371 QVERIFY( map.constBegin() == map.constBegin() );
372 QVERIFY( map.constBegin() != map2.constBegin() );
373}
374
375void tst_QMap::firstLast()
376{
377 // sample string->string map
378 StringMap map;
379 map.insert(akey: "0", avalue: "a");
380 map.insert(akey: "1", avalue: "b");
381 map.insert(akey: "5", avalue: "e");
382
383 QCOMPARE(map.firstKey(), QStringLiteral("0"));
384 QCOMPARE(map.lastKey(), QStringLiteral("5"));
385 QCOMPARE(map.first(), QStringLiteral("a"));
386 QCOMPARE(map.last(), QStringLiteral("e"));
387
388 // const map
389 const StringMap const_map = map;
390 QCOMPARE(map.firstKey(), const_map.firstKey());
391 QCOMPARE(map.lastKey(), const_map.lastKey());
392 QCOMPARE(map.first(), const_map.first());
393 QCOMPARE(map.last(), const_map.last());
394
395 map.take(akey: map.firstKey());
396 QCOMPARE(map.firstKey(), QStringLiteral("1"));
397 QCOMPARE(map.lastKey(), QStringLiteral("5"));
398
399 map.take(akey: map.lastKey());
400 QCOMPARE(map.lastKey(), map.lastKey());
401}
402
403void tst_QMap::key()
404{
405 {
406 QString def("default value");
407
408 QMap<QString, int> map1;
409 QCOMPARE(map1.key(1), QString());
410 QCOMPARE(map1.key(1, def), def);
411
412 map1.insert(akey: "one", avalue: 1);
413 QCOMPARE(map1.key(1), QLatin1String("one"));
414 QCOMPARE(map1.key(1, def), QLatin1String("one"));
415 QCOMPARE(map1.key(2), QString());
416 QCOMPARE(map1.key(2, def), def);
417
418 map1.insert(akey: "two", avalue: 2);
419 QCOMPARE(map1.key(1), QLatin1String("one"));
420 QCOMPARE(map1.key(1, def), QLatin1String("one"));
421 QCOMPARE(map1.key(2), QLatin1String("two"));
422 QCOMPARE(map1.key(2, def), QLatin1String("two"));
423 QCOMPARE(map1.key(3), QString());
424 QCOMPARE(map1.key(3, def), def);
425
426 map1.insert(akey: "deux", avalue: 2);
427 QCOMPARE(map1.key(1), QLatin1String("one"));
428 QCOMPARE(map1.key(1, def), QLatin1String("one"));
429 QVERIFY(map1.key(2) == QLatin1String("deux") || map1.key(2) == QLatin1String("two"));
430 QVERIFY(map1.key(2, def) == QLatin1String("deux") || map1.key(2, def) == QLatin1String("two"));
431 QCOMPARE(map1.key(3), QString());
432 QCOMPARE(map1.key(3, def), def);
433 }
434
435 {
436 int def = 666;
437
438 QMap<int, QString> map2;
439 QCOMPARE(map2.key("one"), 0);
440 QCOMPARE(map2.key("one", def), def);
441
442 map2.insert(akey: 1, avalue: "one");
443 QCOMPARE(map2.key("one"), 1);
444 QCOMPARE(map2.key("one", def), 1);
445 QCOMPARE(map2.key("two"), 0);
446 QCOMPARE(map2.key("two", def), def);
447
448 map2.insert(akey: 2, avalue: "two");
449 QCOMPARE(map2.key("one"), 1);
450 QCOMPARE(map2.key("one", def), 1);
451 QCOMPARE(map2.key("two"), 2);
452 QCOMPARE(map2.key("two", def), 2);
453 QCOMPARE(map2.key("three"), 0);
454 QCOMPARE(map2.key("three", def), def);
455
456 map2.insert(akey: 3, avalue: "two");
457 QCOMPARE(map2.key("one"), 1);
458 QCOMPARE(map2.key("one", def), 1);
459 QCOMPARE(map2.key("two"), 2);
460 QCOMPARE(map2.key("two", def), 2);
461 QCOMPARE(map2.key("three"), 0);
462 QCOMPARE(map2.key("three", def), def);
463
464 map2.insert(akey: -1, avalue: "two");
465 QCOMPARE(map2.key("two"), -1);
466 QCOMPARE(map2.key("two", def), -1);
467
468 map2.insert(akey: 0, avalue: "zero");
469 QCOMPARE(map2.key("zero"), 0);
470 QCOMPARE(map2.key("zero", def), 0);
471 }
472}
473
474void tst_QMap::swap()
475{
476 QMap<int,QString> m1, m2;
477 m1[0] = "m1[0]";
478 m2[1] = "m2[1]";
479 m1.swap(other&: m2);
480 QCOMPARE(m1.value(1),QLatin1String("m2[1]"));
481 QCOMPARE(m2.value(0),QLatin1String("m1[0]"));
482 sanityCheckTree(m: m1, __LINE__);
483 sanityCheckTree(m: m2, __LINE__);
484}
485
486void tst_QMap::operator_eq()
487{
488 {
489 // compare for equality:
490 QMap<int, int> a;
491 QMap<int, int> b;
492
493 QVERIFY(a == b);
494 QVERIFY(!(a != b));
495
496 a.insert(akey: 1,avalue: 1);
497 b.insert(akey: 1,avalue: 1);
498 QVERIFY(a == b);
499 QVERIFY(!(a != b));
500
501 a.insert(akey: 0,avalue: 1);
502 b.insert(akey: 0,avalue: 1);
503 QVERIFY(a == b);
504 QVERIFY(!(a != b));
505
506 // compare for inequality:
507 a.insert(akey: 42,avalue: 0);
508 QVERIFY(a != b);
509 QVERIFY(!(a == b));
510
511 a.insert(akey: 65, avalue: -1);
512 QVERIFY(a != b);
513 QVERIFY(!(a == b));
514
515 b.insert(akey: -1, avalue: -1);
516 QVERIFY(a != b);
517 QVERIFY(!(a == b));
518 }
519
520 {
521 // a more complex map
522 QMap<QString, QString> a;
523 QMap<QString, QString> b;
524
525 QVERIFY(a == b);
526 QVERIFY(!(a != b));
527
528 a.insert(akey: "Hello", avalue: "World");
529 QVERIFY(a != b);
530 QVERIFY(!(a == b));
531
532 b.insert(akey: "Hello", avalue: "World");
533 QVERIFY(a == b);
534 QVERIFY(!(a != b));
535
536 a.insert(akey: "Goodbye", avalue: "cruel world");
537 QVERIFY(a != b);
538 QVERIFY(!(a == b));
539
540 b.insert(akey: "Goodbye", avalue: "cruel world");
541
542 // what happens if we insert nulls?
543 a.insert(akey: QString(), avalue: QString());
544 QVERIFY(a != b);
545 QVERIFY(!(a == b));
546
547 // empty keys and null keys match:
548 b.insert(akey: QString(""), avalue: QString());
549 QVERIFY(a == b);
550 QVERIFY(!(a != b));
551 }
552
553 {
554 QMap<QString, int> a;
555 QMap<QString, int> b;
556
557 a.insert(akey: "otto", avalue: 1);
558 b.insert(akey: "willy", avalue: 1);
559 QVERIFY(a != b);
560 QVERIFY(!(a == b));
561 }
562}
563
564void tst_QMap::empty()
565{
566 QMap<int, QString> map1;
567
568 QVERIFY(map1.isEmpty());
569
570 map1.insert(akey: 1, avalue: "one");
571 QVERIFY(!map1.isEmpty());
572
573 map1.clear();
574 QVERIFY(map1.isEmpty());
575
576}
577
578void tst_QMap::contains()
579{
580 QMap<int, QString> map1;
581 int i;
582
583 map1.insert(akey: 1, avalue: "one");
584 QVERIFY(map1.contains(1));
585
586 for(i=2; i < 100; ++i)
587 map1.insert(akey: i, avalue: "teststring");
588 for(i=99; i > 1; --i)
589 QVERIFY(map1.contains(i));
590
591 map1.remove(akey: 43);
592 QVERIFY(!map1.contains(43));
593}
594
595void tst_QMap::find()
596{
597 QMap<int, QString> map1;
598 QString testString="Teststring %0";
599 QString compareString;
600 int i,count=0;
601
602 QVERIFY(map1.find(1) == map1.end());
603
604 map1.insert(akey: 1,avalue: "Mensch");
605 map1.insert(akey: 1,avalue: "Mayer");
606 map1.insert(akey: 2,avalue: "Hej");
607
608 QCOMPARE(map1.find(1).value(), QLatin1String("Mayer"));
609 QCOMPARE(map1.find(2).value(), QLatin1String("Hej"));
610
611 for(i = 3; i < 10; ++i) {
612 compareString = testString.arg(a: i);
613 map1.insertMulti(key: 4, value: compareString);
614 QCOMPARE(map1.count(4), i - 2);
615 }
616
617 QMap<int, QString>::const_iterator it=map1.constFind(akey: 4);
618
619 for(i = 9; i > 2 && it != map1.constEnd() && it.key() == 4; --i) {
620 compareString = testString.arg(a: i);
621 QVERIFY(it.value() == compareString);
622 ++it;
623 ++count;
624 }
625 QCOMPARE(count, 7);
626}
627
628void tst_QMap::constFind()
629{
630 QMap<int, QString> map1;
631 QString testString="Teststring %0";
632 QString compareString;
633 int i,count=0;
634
635 QVERIFY(map1.constFind(1) == map1.constEnd());
636
637 map1.insert(akey: 1,avalue: "Mensch");
638 map1.insert(akey: 1,avalue: "Mayer");
639 map1.insert(akey: 2,avalue: "Hej");
640
641 QVERIFY(map1.constFind(4) == map1.constEnd());
642
643 QCOMPARE(map1.constFind(1).value(), QLatin1String("Mayer"));
644 QCOMPARE(map1.constFind(2).value(), QLatin1String("Hej"));
645
646 for(i = 3; i < 10; ++i) {
647 compareString = testString.arg(a: i);
648 map1.insertMulti(key: 4, value: compareString);
649 }
650
651 QMap<int, QString>::const_iterator it=map1.constFind(akey: 4);
652
653 for(i = 9; i > 2 && it != map1.constEnd() && it.key() == 4; --i) {
654 compareString = testString.arg(a: i);
655 QVERIFY(it.value() == compareString);
656 ++it;
657 ++count;
658 }
659 QCOMPARE(count, 7);
660}
661
662void tst_QMap::lowerUpperBound()
663{
664 QMap<int, QString> map1;
665
666 map1.insert(akey: 1, avalue: "one");
667 map1.insert(akey: 5, avalue: "five");
668 map1.insert(akey: 10, avalue: "ten");
669
670
671 //Copied from documentation
672
673 QCOMPARE(map1.upperBound(0).key(), 1); // returns iterator to (1, "one")
674 QCOMPARE(map1.upperBound(1).key(), 5); // returns iterator to (5, "five")
675 QCOMPARE(map1.upperBound(2).key(), 5); // returns iterator to (5, "five")
676 QVERIFY(map1.upperBound(10) == map1.end()); // returns end()
677 QVERIFY(map1.upperBound(999) == map1.end()); // returns end()
678
679 QCOMPARE(map1.lowerBound(0).key(), 1); // returns iterator to (1, "one")
680 QCOMPARE(map1.lowerBound(1).key(), 1); // returns iterator to (1, "one")
681 QCOMPARE(map1.lowerBound(2).key(), 5); // returns iterator to (5, "five")
682 QCOMPARE(map1.lowerBound(10).key(), 10); // returns iterator to (10, "ten")
683 QVERIFY(map1.lowerBound(999) == map1.end()); // returns end()
684
685 map1.insert(akey: 3, avalue: "three");
686 map1.insert(akey: 7, avalue: "seven");
687 map1.insertMulti(key: 7, value: "seven_2");
688
689 QCOMPARE(map1.upperBound(0).key(), 1);
690 QCOMPARE(map1.upperBound(1).key(), 3);
691 QCOMPARE(map1.upperBound(2).key(), 3);
692 QCOMPARE(map1.upperBound(3).key(), 5);
693 QCOMPARE(map1.upperBound(7).key(), 10);
694 QVERIFY(map1.upperBound(10) == map1.end());
695 QVERIFY(map1.upperBound(999) == map1.end());
696
697 QCOMPARE(map1.lowerBound(0).key(), 1);
698 QCOMPARE(map1.lowerBound(1).key(), 1);
699 QCOMPARE(map1.lowerBound(2).key(), 3);
700 QCOMPARE(map1.lowerBound(3).key(), 3);
701 QCOMPARE(map1.lowerBound(4).key(), 5);
702 QCOMPARE(map1.lowerBound(5).key(), 5);
703 QCOMPARE(map1.lowerBound(6).key(), 7);
704 QCOMPARE(map1.lowerBound(7).key(), 7);
705 QCOMPARE(map1.lowerBound(6).value(), QLatin1String("seven_2"));
706 QCOMPARE(map1.lowerBound(7).value(), QLatin1String("seven_2"));
707 QCOMPARE((++map1.lowerBound(6)).value(), QLatin1String("seven"));
708 QCOMPARE((++map1.lowerBound(7)).value(), QLatin1String("seven"));
709 QCOMPARE(map1.lowerBound(10).key(), 10);
710 QVERIFY(map1.lowerBound(999) == map1.end());
711}
712
713void tst_QMap::mergeCompare()
714{
715 QMap<int, QString> map1, map2, map3, map1b, map2b;
716
717 map1.insert(akey: 1,avalue: "ett");
718 map1.insert(akey: 3,avalue: "tre");
719 map1.insert(akey: 5,avalue: "fem");
720
721 map2.insert(akey: 2,avalue: "tvo");
722 map2.insert(akey: 4,avalue: "fyra");
723
724 map1.unite(other: map2);
725 sanityCheckTree(m: map1, __LINE__);
726
727 map1b = map1;
728 map2b = map2;
729 map2b.insert(akey: 0, avalue: "nul");
730 map1b.unite(other: map2b);
731 sanityCheckTree(m: map1b, __LINE__);
732
733 QCOMPARE(map1.value(1), QLatin1String("ett"));
734 QCOMPARE(map1.value(2), QLatin1String("tvo"));
735 QCOMPARE(map1.value(3), QLatin1String("tre"));
736 QCOMPARE(map1.value(4), QLatin1String("fyra"));
737 QCOMPARE(map1.value(5), QLatin1String("fem"));
738
739 map3.insert(akey: 1, avalue: "ett");
740 map3.insert(akey: 2, avalue: "tvo");
741 map3.insert(akey: 3, avalue: "tre");
742 map3.insert(akey: 4, avalue: "fyra");
743 map3.insert(akey: 5, avalue: "fem");
744
745 QVERIFY(map1 == map3);
746}
747
748void tst_QMap::take()
749{
750 QMap<int, QString> map;
751
752 map.insert(akey: 2, avalue: "zwei");
753 map.insert(akey: 3, avalue: "drei");
754
755 QCOMPARE(map.take(3), QLatin1String("drei"));
756 QVERIFY(!map.contains(3));
757}
758
759void tst_QMap::iterators()
760{
761 QMap<int, QString> map;
762 QString testString="Teststring %1";
763 int i;
764
765 for(i = 1; i < 100; ++i)
766 map.insert(akey: i, avalue: testString.arg(a: i));
767
768 //STL-Style iterators
769
770 QMap<int, QString>::iterator stlIt = map.begin();
771 QCOMPARE(stlIt.value(), QLatin1String("Teststring 1"));
772
773 stlIt+=5;
774 QCOMPARE(stlIt.value(), QLatin1String("Teststring 6"));
775
776 stlIt++;
777 QCOMPARE(stlIt.value(), QLatin1String("Teststring 7"));
778
779 stlIt-=3;
780 QCOMPARE(stlIt.value(), QLatin1String("Teststring 4"));
781
782 stlIt--;
783 QCOMPARE(stlIt.value(), QLatin1String("Teststring 3"));
784
785 for(stlIt = map.begin(), i = 1; stlIt != map.end(); ++stlIt, ++i)
786 QVERIFY(stlIt.value() == testString.arg(i));
787 QCOMPARE(i, 100);
788
789 //STL-Style const-iterators
790
791 QMap<int, QString>::const_iterator cstlIt = map.constBegin();
792 QCOMPARE(cstlIt.value(), QLatin1String("Teststring 1"));
793
794 cstlIt+=5;
795 QCOMPARE(cstlIt.value(), QLatin1String("Teststring 6"));
796
797 cstlIt++;
798 QCOMPARE(cstlIt.value(), QLatin1String("Teststring 7"));
799
800 cstlIt-=3;
801 QCOMPARE(cstlIt.value(), QLatin1String("Teststring 4"));
802
803 cstlIt--;
804 QCOMPARE(cstlIt.value(), QLatin1String("Teststring 3"));
805
806 for(cstlIt = map.constBegin(), i = 1; cstlIt != map.constEnd(); ++cstlIt, ++i)
807 QVERIFY(cstlIt.value() == testString.arg(i));
808 QCOMPARE(i, 100);
809
810 //Java-Style iterators
811
812 QMapIterator<int, QString> javaIt(map);
813
814 i = 0;
815 while(javaIt.hasNext()) {
816 ++i;
817 javaIt.next();
818 QVERIFY(javaIt.value() == testString.arg(i));
819 }
820
821 ++i;
822 while(javaIt.hasPrevious()) {
823 --i;
824 javaIt.previous();
825 QVERIFY(javaIt.value() == testString.arg(i));
826 }
827
828 i = 51;
829 while(javaIt.hasPrevious()) {
830 --i;
831 javaIt.previous();
832 QVERIFY(javaIt.value() == testString.arg(i));
833 }
834}
835
836void tst_QMap::keyIterator()
837{
838 QMap<int, int> map;
839
840 for (int i = 0; i < 100; ++i)
841 map.insert(akey: i, avalue: i*100);
842
843 QMap<int, int>::key_iterator key_it = map.keyBegin();
844 QMap<int, int>::const_iterator it = map.cbegin();
845 for (int i = 0; i < 100; ++i) {
846 QCOMPARE(*key_it, it.key());
847 ++key_it;
848 ++it;
849 }
850
851 key_it = std::find(first: map.keyBegin(), last: map.keyEnd(), val: 50);
852 it = std::find(first: map.cbegin(), last: map.cend(), val: 50 * 100);
853
854 QVERIFY(key_it != map.keyEnd());
855 QCOMPARE(*key_it, it.key());
856 QCOMPARE(*(key_it++), (it++).key());
857 QCOMPARE(*(key_it--), (it--).key());
858 QCOMPARE(*(++key_it), (++it).key());
859 QCOMPARE(*(--key_it), (--it).key());
860
861 QCOMPARE(std::count(map.keyBegin(), map.keyEnd(), 99), 1);
862
863 // DefaultConstructible test
864 typedef QMap<int, int>::key_iterator keyIterator;
865 Q_STATIC_ASSERT(std::is_default_constructible<keyIterator>::value);
866}
867
868void tst_QMap::keyValueIterator()
869{
870 QMap<int, int> map;
871 typedef QMap<int, int>::const_key_value_iterator::value_type entry_type;
872
873 for (int i = 0; i < 100; ++i)
874 map.insert(akey: i, avalue: i * 100);
875
876 auto key_value_it = map.constKeyValueBegin();
877 auto it = map.cbegin();
878
879 for (int i = 0; i < map.size(); ++i) {
880 QVERIFY(key_value_it != map.constKeyValueEnd());
881 QVERIFY(it != map.cend());
882
883 entry_type pair(it.key(), it.value());
884 QCOMPARE(*key_value_it, pair);
885 QCOMPARE(key_value_it->first, pair.first);
886 QCOMPARE(key_value_it->second, pair.second);
887 QCOMPARE(&(*key_value_it).first, &it.key());
888 QCOMPARE(&key_value_it->first, &it.key());
889 QCOMPARE(&(*key_value_it).second, &it.value());
890 QCOMPARE(&key_value_it->second, &it.value());
891 ++key_value_it;
892 ++it;
893 }
894
895 QVERIFY(key_value_it == map.constKeyValueEnd());
896 QVERIFY(it == map.cend());
897
898 int key = 50;
899 int value = 50 * 100;
900 entry_type pair(key, value);
901 key_value_it = std::find(first: map.constKeyValueBegin(), last: map.constKeyValueEnd(), val: pair);
902 it = std::find(first: map.cbegin(), last: map.cend(), val: value);
903
904 QVERIFY(key_value_it != map.constKeyValueEnd());
905 QCOMPARE(*key_value_it, entry_type(it.key(), it.value()));
906
907 ++it;
908 ++key_value_it;
909 QCOMPARE(*key_value_it, entry_type(it.key(), it.value()));
910
911 --it;
912 --key_value_it;
913 QCOMPARE(*key_value_it, entry_type(it.key(), it.value()));
914
915 ++it;
916 ++key_value_it;
917 QCOMPARE(*key_value_it, entry_type(it.key(), it.value()));
918
919 --it;
920 --key_value_it;
921 QCOMPARE(*key_value_it, entry_type(it.key(), it.value()));
922 key = 99;
923 value = 99 * 100;
924 QCOMPARE(std::count(map.constKeyValueBegin(), map.constKeyValueEnd(), entry_type(key, value)), 1);
925}
926
927void tst_QMap::keys_values_uniqueKeys()
928{
929 QMap<QString, int> map;
930 QVERIFY(map.uniqueKeys().isEmpty());
931 QVERIFY(map.keys().isEmpty());
932 QVERIFY(map.values().isEmpty());
933
934 map.insertMulti(key: "alpha", value: 1);
935 QVERIFY(map.keys() == (QList<QString>() << "alpha"));
936 QVERIFY(map.uniqueKeys() == map.keys());
937 QVERIFY(map.values() == (QList<int>() << 1));
938
939 map.insertMulti(key: "beta", value: -2);
940 QVERIFY(map.keys() == (QList<QString>() << "alpha" << "beta"));
941 QVERIFY(map.keys() == map.uniqueKeys());
942 QVERIFY(map.values() == (QList<int>() << 1 << -2));
943
944 map.insertMulti(key: "alpha", value: 2);
945 QVERIFY(map.uniqueKeys() == (QList<QString>() << "alpha" << "beta"));
946 QVERIFY(map.keys() == (QList<QString>() << "alpha" << "alpha" << "beta"));
947 QVERIFY(map.values() == (QList<int>() << 2 << 1 << -2));
948
949 map.insertMulti(key: "beta", value: 4);
950 QVERIFY(map.uniqueKeys() == (QList<QString>() << "alpha" << "beta"));
951 QVERIFY(map.keys() == (QList<QString>() << "alpha" << "alpha" << "beta" << "beta"));
952 QVERIFY(map.values() == (QList<int>() << 2 << 1 << 4 << -2));
953}
954
955void tst_QMap::qmultimap_specific()
956{
957 QMultiMap<int, int> map1;
958 for (int i = 1; i <= 9; ++i) {
959 for (int j = 1; j <= i; ++j) {
960 int k = i * 10 + j;
961 QVERIFY(!map1.contains(i, k));
962 map1.insert(akey: i, avalue: k);
963 QVERIFY(map1.contains(i, k));
964 }
965 }
966
967 for (int i = 1; i <= 9; ++i) {
968 for (int j = 1; j <= i; ++j) {
969 int k = i * 10 + j;
970 QVERIFY(map1.contains(i, k));
971 }
972 }
973
974 QVERIFY(map1.contains(9, 99));
975 QCOMPARE(map1.count(), 45);
976 map1.remove(key: 9, value: 99);
977 QVERIFY(!map1.contains(9, 99));
978 QCOMPARE(map1.count(), 44);
979
980 map1.remove(key: 9, value: 99);
981 QVERIFY(!map1.contains(9, 99));
982 QCOMPARE(map1.count(), 44);
983
984 map1.remove(key: 1, value: 99);
985 QCOMPARE(map1.count(), 44);
986
987 map1.insert(akey: 1, avalue: 99);
988 map1.insert(akey: 1, avalue: 99);
989
990 QCOMPARE(map1.count(), 46);
991 map1.remove(key: 1, value: 99);
992 QCOMPARE(map1.count(), 44);
993 map1.remove(key: 1, value: 99);
994 QCOMPARE(map1.count(), 44);
995
996 {
997 QMultiMap<int, int>::const_iterator i = map1.constFind(key: 1, value: 11);
998 QVERIFY(i.key() == 1);
999 QVERIFY(i.value() == 11);
1000
1001 i = map1.constFind(key: 2, value: 22);
1002 QVERIFY(i.key() == 2);
1003 QVERIFY(i.value() == 22);
1004
1005 i = map1.constFind(key: 9, value: 98);
1006 QVERIFY(i.key() == 9);
1007 QVERIFY(i.value() == 98);
1008 }
1009
1010 {
1011 const QMultiMap<int, int> map2(map1);
1012 QMultiMap<int, int>::const_iterator i = map2.find(key: 1, value: 11);
1013 QVERIFY(i.key() == 1);
1014 QVERIFY(i.value() == 11);
1015
1016 i = map2.find(key: 2, value: 22);
1017 QVERIFY(i.key() == 2);
1018 QVERIFY(i.value() == 22);
1019
1020 i = map2.find(key: 9, value: 98);
1021 QVERIFY(i.key() == 9);
1022 QVERIFY(i.value() == 98);
1023 }
1024
1025 {
1026 QMultiMap<int, int>::iterator i = map1.find(key: 1, value: 11);
1027 QVERIFY(i.key() == 1);
1028 QVERIFY(i.value() == 11);
1029
1030 i = map1.find(key: 2, value: 22);
1031 QVERIFY(i.key() == 2);
1032 QVERIFY(i.value() == 22);
1033
1034 i = map1.find(key: 9, value: 98);
1035 QVERIFY(i.key() == 9);
1036 QVERIFY(i.value() == 98);
1037 }
1038
1039 {
1040 QMultiMap<int, int> map1;
1041 map1.insert(akey: 42, avalue: 1);
1042 map1.insert(akey: 10, avalue: 2);
1043 map1.insert(akey: 48, avalue: 3);
1044 QMultiMap<int, int> map2;
1045 map2.insert(akey: 8, avalue: 4);
1046 map2.insert(akey: 42, avalue: 5);
1047 map2.insert(akey: 95, avalue: 12);
1048
1049 map1+=map2;
1050 map2.insert(akey: 42, avalue: 1);
1051 map2.insert(akey: 10, avalue: 2);
1052 map2.insert(akey: 48, avalue: 3);
1053 QCOMPARE(map1.count(), map2.count());
1054 QVERIFY(map1.remove(42,5));
1055 QVERIFY(map2.remove(42,5));
1056 QVERIFY(map1 == map2);
1057 }
1058
1059 map1.insert(pos: map1.constBegin(), akey: -1, avalue: -1);
1060 QCOMPARE(map1.size(), 45);
1061 map1.insert(pos: map1.constBegin(), akey: -1, avalue: -1);
1062 QCOMPARE(map1.size(), 46);
1063 map1.insert(pos: map1.constBegin(), akey: -2, avalue: -2);
1064 QCOMPARE(map1.size(), 47);
1065 map1.insert(pos: map1.constBegin(), akey: 5, avalue: 5); // Invald hint
1066 QCOMPARE(map1.size(), 48);
1067 map1.insert(pos: map1.constBegin(), akey: 5, avalue: 5); // Invald hint
1068 QCOMPARE(map1.size(), 49);
1069 sanityCheckTree(m: map1, __LINE__);
1070}
1071
1072void tst_QMap::const_shared_null()
1073{
1074 QMap<int, QString> map2;
1075#if !defined(QT_NO_UNSHARABLE_CONTAINERS)
1076 QMap<int, QString> map1;
1077 map1.setSharable(false);
1078 QVERIFY(map1.isDetached());
1079
1080 map2.setSharable(true);
1081#endif
1082 QVERIFY(!map2.isDetached());
1083}
1084
1085void tst_QMap::equal_range()
1086{
1087 QMap<int, QString> map;
1088 const QMap<int, QString> &cmap = map;
1089
1090 QPair<QMap<int, QString>::iterator, QMap<int, QString>::iterator> result = map.equal_range(akey: 0);
1091 QCOMPARE(result.first, map.end());
1092 QCOMPARE(result.second, map.end());
1093
1094 QPair<QMap<int, QString>::const_iterator, QMap<int, QString>::const_iterator> cresult = cmap.equal_range(akey: 0);
1095 QCOMPARE(cresult.first, cmap.cend());
1096 QCOMPARE(cresult.second, cmap.cend());
1097
1098 map.insert(akey: 1, avalue: "one");
1099
1100 result = map.equal_range(akey: 0);
1101 QCOMPARE(result.first, map.find(1));
1102 QCOMPARE(result.second, map.find(1));
1103
1104 result = map.equal_range(akey: 1);
1105 QCOMPARE(result.first, map.find(1));
1106 QCOMPARE(result.second, map.end());
1107
1108 result = map.equal_range(akey: 2);
1109 QCOMPARE(result.first, map.end());
1110 QCOMPARE(result.second, map.end());
1111
1112 cresult = cmap.equal_range(akey: 0);
1113 QCOMPARE(cresult.first, cmap.find(1));
1114 QCOMPARE(cresult.second, cmap.find(1));
1115
1116 cresult = cmap.equal_range(akey: 1);
1117 QCOMPARE(cresult.first, cmap.find(1));
1118 QCOMPARE(cresult.second, cmap.cend());
1119
1120 cresult = cmap.equal_range(akey: 2);
1121 QCOMPARE(cresult.first, cmap.cend());
1122 QCOMPARE(cresult.second, cmap.cend());
1123
1124 for (int i = -10; i < 10; i += 2)
1125 map.insert(akey: i, avalue: QString::number(i));
1126
1127 result = map.equal_range(akey: 0);
1128 QCOMPARE(result.first, map.find(0));
1129 QCOMPARE(result.second, map.find(1));
1130
1131 result = map.equal_range(akey: 1);
1132 QCOMPARE(result.first, map.find(1));
1133 QCOMPARE(result.second, map.find(2));
1134
1135 result = map.equal_range(akey: 2);
1136 QCOMPARE(result.first, map.find(2));
1137 QCOMPARE(result.second, map.find(4));
1138
1139 cresult = cmap.equal_range(akey: 0);
1140 QCOMPARE(cresult.first, cmap.find(0));
1141 QCOMPARE(cresult.second, cmap.find(1));
1142
1143 cresult = cmap.equal_range(akey: 1);
1144 QCOMPARE(cresult.first, cmap.find(1));
1145 QCOMPARE(cresult.second, cmap.find(2));
1146
1147 cresult = cmap.equal_range(akey: 2);
1148 QCOMPARE(cresult.first, cmap.find(2));
1149 QCOMPARE(cresult.second, cmap.find(4));
1150
1151 map.insertMulti(key: 1, value: "another one");
1152
1153 result = map.equal_range(akey: 1);
1154 QCOMPARE(result.first, map.find(1));
1155 QCOMPARE(result.second, map.find(2));
1156
1157 cresult = cmap.equal_range(akey: 1);
1158 QCOMPARE(cresult.first, cmap.find(1));
1159 QCOMPARE(cresult.second, cmap.find(2));
1160
1161 QCOMPARE(map.count(1), 2);
1162}
1163
1164template <class T>
1165const T &const_(const T &t)
1166{
1167 return t;
1168}
1169
1170void tst_QMap::setSharable()
1171{
1172#if !defined(QT_NO_UNSHARABLE_CONTAINERS)
1173 QMap<int, QString> map;
1174
1175 map.insert(akey: 1, avalue: "um");
1176 map.insert(akey: 2, avalue: "dois");
1177 map.insert(akey: 4, avalue: "quatro");
1178 map.insert(akey: 5, avalue: "cinco");
1179
1180 map.setSharable(true);
1181 QCOMPARE(map.size(), 4);
1182 QCOMPARE(const_(map)[4], QString("quatro"));
1183
1184 {
1185 QMap<int, QString> copy(map);
1186
1187 QVERIFY(!map.isDetached());
1188 QVERIFY(copy.isSharedWith(map));
1189 sanityCheckTree(m: copy, __LINE__);
1190 }
1191
1192 map.setSharable(false);
1193 sanityCheckTree(m: map, __LINE__);
1194 QVERIFY(map.isDetached());
1195 QCOMPARE(map.size(), 4);
1196 QCOMPARE(const_(map)[4], QString("quatro"));
1197
1198 {
1199 QMap<int, QString> copy(map);
1200
1201 QVERIFY(map.isDetached());
1202 QVERIFY(copy.isDetached());
1203
1204 QCOMPARE(copy.size(), 4);
1205 QCOMPARE(const_(copy)[4], QString("quatro"));
1206
1207 QCOMPARE(map, copy);
1208 sanityCheckTree(m: map, __LINE__);
1209 sanityCheckTree(m: copy, __LINE__);
1210 }
1211
1212 map.setSharable(true);
1213 QCOMPARE(map.size(), 4);
1214 QCOMPARE(const_(map)[4], QString("quatro"));
1215
1216 {
1217 QMap<int, QString> copy(map);
1218
1219 QVERIFY(!map.isDetached());
1220 QVERIFY(copy.isSharedWith(map));
1221 }
1222#endif
1223}
1224
1225void tst_QMap::insert()
1226{
1227 QMap<QString, float> map;
1228 map.insert(akey: "cs/key1", avalue: 1);
1229 map.insert(akey: "cs/key2", avalue: 2);
1230 map.insert(akey: "cs/key1", avalue: 3);
1231 QCOMPARE(map.count(), 2);
1232
1233 QMap<int, int> intMap;
1234 for (int i = 0; i < 1000; ++i) {
1235 intMap.insert(akey: i, avalue: i);
1236 }
1237
1238 QCOMPARE(intMap.size(), 1000);
1239
1240 for (int i = 0; i < 1000; ++i) {
1241 QCOMPARE(intMap.value(i), i);
1242 intMap.insert(akey: i, avalue: -1);
1243 QCOMPARE(intMap.size(), 1000);
1244 QCOMPARE(intMap.value(i), -1);
1245 }
1246
1247 {
1248 QMap<IdentityTracker, int> map;
1249 QCOMPARE(map.size(), 0);
1250 const int dummy = -1;
1251 IdentityTracker id00 = {.value: 0, .id: 0}, id01 = {.value: 0, .id: 1}, searchKey = {.value: 0, .id: dummy};
1252 QCOMPARE(map.insert(id00, id00.id).key().id, id00.id);
1253 QCOMPARE(map.size(), 1);
1254 QCOMPARE(map.insert(id01, id01.id).key().id, id00.id); // first key inserted is kept
1255 QCOMPARE(map.size(), 1);
1256 QCOMPARE(map.find(searchKey).value(), id01.id); // last-inserted value
1257 QCOMPARE(map.find(searchKey).key().id, id00.id); // but first-inserted key
1258 }
1259 {
1260 QMultiMap<IdentityTracker, int> map;
1261 QCOMPARE(map.size(), 0);
1262 const int dummy = -1;
1263 IdentityTracker id00 = {.value: 0, .id: 0}, id01 = {.value: 0, .id: 1}, searchKey = {.value: 0, .id: dummy};
1264 QCOMPARE(map.insert(id00, id00.id).key().id, id00.id);
1265 QCOMPARE(map.size(), 1);
1266 QCOMPARE(map.insert(id01, id01.id).key().id, id01.id);
1267 QCOMPARE(map.size(), 2);
1268 QMultiMap<IdentityTracker, int>::const_iterator pos = map.constFind(akey: searchKey);
1269 QCOMPARE(pos.value(), pos.key().id); // key fits to value it was inserted with
1270 ++pos;
1271 QCOMPARE(pos.value(), pos.key().id); // key fits to value it was inserted with
1272 }
1273}
1274
1275void tst_QMap::insertMap()
1276{
1277 {
1278 QMap<int, int> map;
1279 map.insert(akey: 1, avalue: 1);
1280 map.insert(akey: 2, avalue: 2);
1281 map.insert(akey: 0, avalue: -1);
1282
1283 QMap<int, int> map2;
1284 map2.insert(akey: 0, avalue: 0);
1285 map2.insert(akey: 3, avalue: 3);
1286 map2.insert(akey: 4, avalue: 4);
1287
1288 map.insert(map: map2);
1289
1290 QCOMPARE(map.count(), 5);
1291 for (int i = 0; i < 5; ++i)
1292 QCOMPARE(map[i], i);
1293 }
1294 {
1295 QMap<int, int> map;
1296 for (int i = 0; i < 10; ++i)
1297 map.insert(akey: i * 3, avalue: i);
1298
1299 QMap<int, int> map2;
1300 for (int i = 0; i < 10; ++i)
1301 map2.insert(akey: i * 4, avalue: i);
1302
1303 map.insert(map: map2);
1304
1305 QCOMPARE(map.count(), 17);
1306 for (int i = 0; i < 10; ++i) {
1307 // i * 3 == i except for i = 4, 8
1308 QCOMPARE(map[i * 3], (i && i % 4 == 0) ? i - (i / 4) : i);
1309 QCOMPARE(map[i * 4], i);
1310 }
1311
1312 auto it = map.cbegin();
1313 int prev = it.key();
1314 ++it;
1315 for (auto end = map.cend(); it != end; ++it) {
1316 QVERIFY(prev < it.key());
1317 prev = it.key();
1318 }
1319 }
1320 {
1321 QMap<int, int> map;
1322 map.insert(akey: 1, avalue: 1);
1323
1324 QMap<int, int> map2;
1325
1326 map.insert(map: map2);
1327 QCOMPARE(map.count(), 1);
1328 QCOMPARE(map[1], 1);
1329 }
1330 {
1331 QMap<int, int> map;
1332 QMap<int, int> map2;
1333 map2.insert(akey: 1, avalue: 1);
1334
1335 map.insert(map: map2);
1336 QCOMPARE(map.count(), 1);
1337 QCOMPARE(map[1], 1);
1338 }
1339 {
1340 QMap<int, int> map;
1341 map.insert(akey: 0, avalue: 0);
1342 map.insert(akey: 1, avalue: 1);
1343 map.insert(akey: 2, avalue: 2);
1344
1345 // Test inserting into self, nothing should happen
1346 map.insert(map);
1347
1348 QCOMPARE(map.count(), 3);
1349 for (int i = 0; i < 3; ++i)
1350 QCOMPARE(map[i], i);
1351 }
1352 {
1353 // Here we use a QMultiMap and insert that into QMap,
1354 // since it has multiple values with the same key the
1355 // ordering is undefined so we won't test that, but
1356 // make sure this isn't adding multiple entries with the
1357 // same key to the QMap.
1358 QMap<int, int> map;
1359 QMultiMap<int, int> map2;
1360 map2.insert(akey: 0, avalue: 0);
1361 map2.insert(akey: 0, avalue: 1);
1362 map2.insert(akey: 0, avalue: 2);
1363
1364 map.insert(map: map2);
1365
1366 QCOMPARE(map.count(), 1);
1367 }
1368}
1369
1370void tst_QMap::checkMostLeftNode()
1371{
1372 QMap<int, int> map;
1373
1374 map.insert(akey: 100, avalue: 1);
1375 sanityCheckTree(m: map, __LINE__);
1376
1377 // insert
1378 map.insert(akey: 99, avalue: 1);
1379 sanityCheckTree(m: map, __LINE__);
1380 map.insert(akey: 98, avalue: 1);
1381 sanityCheckTree(m: map, __LINE__);
1382 map.insert(akey: 97, avalue: 1);
1383 sanityCheckTree(m: map, __LINE__);
1384 map.insert(akey: 96, avalue: 1);
1385 sanityCheckTree(m: map, __LINE__);
1386 map.insert(akey: 95, avalue: 1);
1387
1388 // remove
1389 sanityCheckTree(m: map, __LINE__);
1390 map.take(akey: 95);
1391 sanityCheckTree(m: map, __LINE__);
1392 map.remove(akey: 96);
1393 sanityCheckTree(m: map, __LINE__);
1394 map.erase(it: map.begin());
1395 sanityCheckTree(m: map, __LINE__);
1396 map.remove(akey: 97);
1397 sanityCheckTree(m: map, __LINE__);
1398 map.remove(akey: 98);
1399 sanityCheckTree(m: map, __LINE__);
1400 map.remove(akey: 99);
1401 sanityCheckTree(m: map, __LINE__);
1402 map.remove(akey: 100);
1403 sanityCheckTree(m: map, __LINE__);
1404 map.insert(akey: 200, avalue: 1);
1405 QCOMPARE(map.constBegin().key(), 200);
1406 sanityCheckTree(m: map, __LINE__);
1407 // remove the non left most node
1408 map.insert(akey: 202, avalue: 2);
1409 map.insert(akey: 203, avalue: 3);
1410 map.insert(akey: 204, avalue: 4);
1411 map.remove(akey: 202);
1412 sanityCheckTree(m: map, __LINE__);
1413 map.remove(akey: 203);
1414 sanityCheckTree(m: map, __LINE__);
1415 map.remove(akey: 204);
1416 sanityCheckTree(m: map, __LINE__);
1417 // erase last item
1418 map.erase(it: map.begin());
1419 sanityCheckTree(m: map, __LINE__);
1420}
1421
1422void tst_QMap::initializerList()
1423{
1424 QMap<int, QString> map = {{1, "bar"}, {1, "hello"}, {2, "initializer_list"}};
1425 QCOMPARE(map.count(), 2);
1426 QCOMPARE(map[1], QString("hello"));
1427 QCOMPARE(map[2], QString("initializer_list"));
1428
1429 // note the difference to std::map:
1430 // std::map<int, QString> stdm = {{1, "bar"}, {1, "hello"}, {2, "initializer_list"}};
1431 // QCOMPARE(stdm.size(), 2UL);
1432 // QCOMPARE(stdm[1], QString("bar"));
1433
1434 QMultiMap<QString, int> multiMap{{"il", 1}, {"il", 2}, {"il", 3}};
1435 QCOMPARE(multiMap.count(), 3);
1436 QList<int> values = multiMap.values(akey: "il");
1437 QCOMPARE(values.count(), 3);
1438
1439 QMap<int, int> emptyMap{};
1440 QVERIFY(emptyMap.isEmpty());
1441
1442 QMap<char, char> emptyPairs{{}, {}};
1443 QVERIFY(!emptyPairs.isEmpty());
1444
1445 QMultiMap<double, double> emptyMultiMap{};
1446 QVERIFY(emptyMultiMap.isEmpty());
1447
1448 QMultiMap<float, float> emptyPairs2{{}, {}};
1449 QVERIFY(!emptyPairs2.isEmpty());
1450}
1451
1452void tst_QMap::testInsertWithHint()
1453{
1454 QMap<int, int> map;
1455
1456 // Check with end hint();
1457 map.insert(pos: map.constEnd(), akey: 3, avalue: 1); // size == 1
1458 sanityCheckTree(m: map, __LINE__);
1459 map.insert(pos: map.constEnd(), akey: 5, avalue: 1); // size = 2
1460 sanityCheckTree(m: map, __LINE__);
1461 map.insert(pos: map.constEnd(), akey: 50, avalue: 1); // size = 3
1462 sanityCheckTree(m: map, __LINE__);
1463 QMap<int, int>::const_iterator key75(map.insert(pos: map.constEnd(), akey: 75, avalue: 1)); // size = 4
1464 sanityCheckTree(m: map, __LINE__);
1465 map.insert(pos: map.constEnd(), akey: 100, avalue: 1); // size = 5
1466 sanityCheckTree(m: map, __LINE__);
1467 map.insert(pos: map.constEnd(), akey: 105, avalue: 1); // size = 6
1468 sanityCheckTree(m: map, __LINE__);
1469 map.insert(pos: map.constEnd(), akey: 10, avalue: 5); // invalid hint and size = 7
1470 sanityCheckTree(m: map, __LINE__);
1471 QMap<int, int>::iterator lastkey = map.insert(pos: map.constEnd(), akey: 105, avalue: 12); // overwrite
1472 sanityCheckTree(m: map, __LINE__);
1473 QCOMPARE(lastkey.value(), 12);
1474 QCOMPARE(lastkey.key(), 105);
1475 QCOMPARE(map.size(), 7);
1476
1477 // With regular hint
1478 map.insert(pos: key75, akey: 75, avalue: 100); // overwrite current key
1479 sanityCheckTree(m: map, __LINE__);
1480 QCOMPARE(map.size(), 7);
1481 QCOMPARE(key75.key(), 75);
1482 QCOMPARE(key75.value(), 100);
1483
1484 map.insert(pos: key75, akey: 50, avalue: 101); // overwrite previous value
1485 QMap<int, int>::const_iterator key50(key75);
1486 --key50;
1487 QCOMPARE(map.size(), 7);
1488 QCOMPARE(key50.key(), 50);
1489 QCOMPARE(key50.value(), 101);
1490
1491 map.insert(pos: key75, akey: 17, avalue: 125); // invalid hint - size 8
1492 sanityCheckTree(m: map, __LINE__);
1493 QCOMPARE(map.size(), 8);
1494
1495 // begin
1496 map.insert(pos: map.constBegin(), akey: 1, avalue: 1); // size 9
1497 sanityCheckTree(m: map, __LINE__);
1498 QCOMPARE(map.size(), 9);
1499
1500 map.insert(pos: map.constBegin(), akey: 1, avalue: 10); // overwrite existing (leftmost) value
1501 QCOMPARE(map.constBegin().value(), 10);
1502
1503 map.insert(pos: map.constBegin(), akey: 47, avalue: 47); // wrong hint - size 10
1504 sanityCheckTree(m: map, __LINE__);
1505 QCOMPARE(map.size(), 10);
1506
1507 // insert with right == 0
1508 QMap<int, int>::const_iterator i1 (map.insert(pos: key75, akey: 70, avalue: 12)); // overwrite
1509 map.insert(pos: i1, akey: 69, avalue: 12); // size 12
1510
1511 sanityCheckTree(m: map, __LINE__);
1512 QCOMPARE(map.size(), 12);
1513}
1514
1515void tst_QMap::testInsertMultiWithHint()
1516{
1517 QMap<int, int> map;
1518
1519 typedef QMap<int, int>::const_iterator cite; // Hack since we define QT_STRICT_ITERATORS
1520 map.insertMulti(pos: cite(map.end()), akey: 64, avalue: 65);
1521 map[128] = 129;
1522 map[256] = 257;
1523 sanityCheckTree(m: map, __LINE__);
1524
1525 map.insertMulti(pos: cite(map.end()), akey: 512, avalue: 513);
1526 map.insertMulti(pos: cite(map.end()), akey: 512, avalue: 513 * 2);
1527 sanityCheckTree(m: map, __LINE__);
1528 QCOMPARE(map.size(), 5);
1529 map.insertMulti(pos: cite(map.end()), akey: 256, avalue: 258); // wrong hint
1530 sanityCheckTree(m: map, __LINE__);
1531 QCOMPARE(map.size(), 6);
1532
1533 QMap<int, int>::iterator i = map.insertMulti(pos: map.constBegin(), akey: 256, avalue: 259); // wrong hint
1534 sanityCheckTree(m: map, __LINE__);
1535 QCOMPARE(map.size(), 7);
1536
1537 QMap<int, int>::iterator j = map.insertMulti(pos: map.constBegin(), akey: 69, avalue: 66);
1538 sanityCheckTree(m: map, __LINE__);
1539 QCOMPARE(map.size(), 8);
1540
1541 j = map.insertMulti(pos: cite(j), akey: 68, avalue: 259);
1542 sanityCheckTree(m: map, __LINE__);
1543 QCOMPARE(map.size(), 9);
1544
1545 j = map.insertMulti(pos: cite(j), akey: 67, avalue: 67);
1546 sanityCheckTree(m: map, __LINE__);
1547 QCOMPARE(map.size(), 10);
1548
1549 i = map.insertMulti(pos: cite(i), akey: 256, avalue: 259);
1550 sanityCheckTree(m: map, __LINE__);
1551 QCOMPARE(map.size(), 11);
1552
1553 i = map.insertMulti(pos: cite(i), akey: 256, avalue: 260);
1554 sanityCheckTree(m: map, __LINE__);
1555 QCOMPARE(map.size(), 12);
1556
1557 map.insertMulti(pos: cite(i), akey: 64, avalue: 67);
1558 sanityCheckTree(m: map, __LINE__);
1559 QCOMPARE(map.size(), 13);
1560
1561 map.insertMulti(pos: map.constBegin(), akey: 20, avalue: 20);
1562 sanityCheckTree(m: map, __LINE__);
1563 QCOMPARE(map.size(), 14);
1564}
1565
1566void tst_QMap::eraseValidIteratorOnSharedMap()
1567{
1568 QMap<int, int> a, b;
1569 a.insert(akey: 10, avalue: 10);
1570 a.insertMulti(key: 10, value: 40);
1571 a.insertMulti(key: 10, value: 25);
1572 a.insertMulti(key: 10, value: 30);
1573 a.insert(akey: 20, avalue: 20);
1574
1575 QMap<int, int>::iterator i = a.begin();
1576 while (i.value() != 25)
1577 ++i;
1578
1579 b = a;
1580 a.erase(it: i);
1581
1582 QCOMPARE(b.size(), 5);
1583 QCOMPARE(a.size(), 4);
1584
1585 for (i = a.begin(); i != a.end(); ++i)
1586 QVERIFY(i.value() != 25);
1587
1588 int itemsWith10 = 0;
1589 for (i = b.begin(); i != b.end(); ++i)
1590 itemsWith10 += (i.key() == 10);
1591
1592 QCOMPARE(itemsWith10, 4);
1593
1594 // Border cases
1595 QMap <QString, QString> ms1, ms2, ms3;
1596 ms1.insert(akey: "foo", avalue: "bar");
1597 ms1.insertMulti(key: "foo", value: "quux");
1598 ms1.insertMulti(key: "foo", value: "bar");
1599
1600 QMap <QString, QString>::iterator si = ms1.begin();
1601 ms2 = ms1;
1602 ms1.erase(it: si);
1603 si = ms1.begin();
1604 QCOMPARE(si.value(), QString("quux"));
1605 ++si;
1606 QCOMPARE(si.value(), QString("bar"));
1607
1608 si = ms2.begin();
1609 ++si;
1610 ++si;
1611 ms3 = ms2;
1612 ms2.erase(it: si);
1613 si = ms2.begin();
1614 QCOMPARE(si.value(), QString("bar"));
1615 ++si;
1616 QCOMPARE(si.value(), QString("quux"));
1617
1618 QCOMPARE(ms1.size(), 2);
1619 QCOMPARE(ms2.size(), 2);
1620 QCOMPARE(ms3.size(), 3);
1621}
1622
1623QTEST_APPLESS_MAIN(tst_QMap)
1624#include "tst_qmap.moc"
1625

source code of qtbase/tests/auto/corelib/tools/qmap/tst_qmap.cpp