File indexing completed on 2024-04-28 05:45:22
0001 /* 0002 * SPDX-FileCopyrightText: 2013 Frank Reininghaus <frank78ac@googlemail.com> 0003 * 0004 * SPDX-License-Identifier: GPL-2.0-or-later 0005 */ 0006 0007 #include "kitemviews/kitemset.h" 0008 0009 #include <QStandardPaths> 0010 #include <QTest> 0011 0012 Q_DECLARE_METATYPE(KItemRangeList) 0013 0014 /** 0015 * Converts a KItemRangeList to a KItemSet. 0016 */ 0017 KItemSet KItemRangeList2KItemSet(const KItemRangeList &itemRanges) 0018 { 0019 KItemSet result; 0020 for (const KItemRange &range : itemRanges) { 0021 for (int i = range.index; i < range.index + range.count; ++i) { 0022 result.insert(i); 0023 } 0024 } 0025 return result; 0026 } 0027 0028 /** 0029 * Converts a KItemRangeList to a QSet<int>. 0030 */ 0031 QSet<int> KItemRangeList2QSet(const KItemRangeList &itemRanges) 0032 { 0033 QSet<int> result; 0034 for (const KItemRange &range : itemRanges) { 0035 for (int i = range.index; i < range.index + range.count; ++i) { 0036 result.insert(i); 0037 } 0038 } 0039 return result; 0040 } 0041 0042 /** 0043 * Converts a KItemRangeList to a QVector<int>. 0044 */ 0045 QVector<int> KItemRangeList2QVector(const KItemRangeList &itemRanges) 0046 { 0047 QVector<int> result; 0048 for (const KItemRange &range : itemRanges) { 0049 for (int i = range.index; i < range.index + range.count; ++i) { 0050 result.append(i); 0051 } 0052 } 0053 return result; 0054 } 0055 0056 /** 0057 * Converts a KItemSet to a QSet<int>. 0058 */ 0059 static QSet<int> KItemSet2QSet(const KItemSet &itemSet) 0060 { 0061 QSet<int> result; 0062 for (int i : itemSet) { 0063 result.insert(i); 0064 } 0065 0066 // Check that the conversion was successful. 0067 Q_ASSERT(itemSet.count() == result.count()); 0068 0069 for (int i : std::as_const(itemSet)) { 0070 Q_ASSERT(result.contains(i)); 0071 } 0072 0073 for (int i : std::as_const(result)) { 0074 Q_ASSERT(itemSet.contains(i)); 0075 } 0076 0077 return result; 0078 } 0079 0080 /** 0081 * The main test class. 0082 */ 0083 class KItemSetTest : public QObject 0084 { 0085 Q_OBJECT 0086 0087 private Q_SLOTS: 0088 void initTestCase(); 0089 0090 void testConstruction_data(); 0091 void testConstruction(); 0092 void testIterators_data(); 0093 void testIterators(); 0094 void testFind_data(); 0095 void testFind(); 0096 void testChangingOneItem_data(); 0097 void testChangingOneItem(); 0098 void testAddSets_data(); 0099 void testAddSets(); 0100 /* 0101 void testSubtractSets_data(); 0102 void testSubtractSets(); 0103 */ 0104 void testSymmetricDifference_data(); 0105 void testSymmetricDifference(); 0106 0107 private: 0108 QHash<const char *, KItemRangeList> m_testCases; 0109 }; 0110 0111 void KItemSetTest::initTestCase() 0112 { 0113 QStandardPaths::setTestModeEnabled(true); 0114 0115 m_testCases.insert("empty", KItemRangeList()); 0116 m_testCases.insert("[0]", KItemRangeList() << KItemRange(0, 1)); 0117 m_testCases.insert("[1]", KItemRangeList() << KItemRange(1, 1)); 0118 m_testCases.insert("[1, 2]", KItemRangeList() << KItemRange(1, 2)); 0119 m_testCases.insert("[1, 2] [5]", KItemRangeList() << KItemRange(1, 2) << KItemRange(5, 1)); 0120 m_testCases.insert("[1] [4, 5]", KItemRangeList() << KItemRange(1, 1) << KItemRange(4, 2)); 0121 m_testCases.insert("[1, 2] [4, 5]", KItemRangeList() << KItemRange(1, 2) << KItemRange(4, 2)); 0122 m_testCases.insert("[1, 5]", KItemRangeList() << KItemRange(1, 5)); 0123 m_testCases.insert("[1, 2] [4, 5] [7] [9, 10] [13] [20, 25] [30]", 0124 KItemRangeList() << KItemRange(1, 2) << KItemRange(4, 2) << KItemRange(7, 1) << KItemRange(9, 2) << KItemRange(20, 6) 0125 << KItemRange(30, 1)); 0126 m_testCases.insert("[-10, -1]", KItemRangeList() << KItemRange(-10, 10)); 0127 m_testCases.insert("[-10, 0]", KItemRangeList() << KItemRange(-10, 11)); 0128 m_testCases.insert("[-10, 1]", KItemRangeList() << KItemRange(-10, 12)); 0129 m_testCases.insert("[0, 9]", KItemRangeList() << KItemRange(0, 10)); 0130 m_testCases.insert("[0, 19]", KItemRangeList() << KItemRange(0, 10)); 0131 } 0132 0133 void KItemSetTest::testConstruction_data() 0134 { 0135 QTest::addColumn<KItemRangeList>("itemRanges"); 0136 0137 QHash<const char *, KItemRangeList>::const_iterator it = m_testCases.constBegin(); 0138 const QHash<const char *, KItemRangeList>::const_iterator end = m_testCases.constEnd(); 0139 0140 while (it != end) { 0141 QTest::newRow(it.key()) << it.value(); 0142 ++it; 0143 } 0144 } 0145 0146 void KItemSetTest::testConstruction() 0147 { 0148 QFETCH(KItemRangeList, itemRanges); 0149 0150 KItemSet itemSet = KItemRangeList2KItemSet(itemRanges); 0151 QSet<int> itemsQSet = KItemRangeList2QSet(itemRanges); 0152 0153 QVERIFY(itemSet.isValid()); 0154 QVERIFY(itemSet.count() == itemsQSet.count()); 0155 QCOMPARE(KItemSet2QSet(itemSet), itemsQSet); 0156 0157 // Test copy constructor. 0158 KItemSet copy(itemSet); 0159 QCOMPARE(itemSet, copy); 0160 copy.clear(); 0161 QVERIFY(itemSet != copy || itemSet.isEmpty()); 0162 0163 // Clear the set. 0164 itemSet.clear(); 0165 QVERIFY(itemSet.isEmpty()); 0166 QCOMPARE(itemSet.count(), 0); 0167 } 0168 0169 void KItemSetTest::testIterators_data() 0170 { 0171 QTest::addColumn<KItemRangeList>("itemRanges"); 0172 0173 QHash<const char *, KItemRangeList>::const_iterator it = m_testCases.constBegin(); 0174 const QHash<const char *, KItemRangeList>::const_iterator end = m_testCases.constEnd(); 0175 0176 while (it != end) { 0177 QTest::newRow(it.key()) << it.value(); 0178 ++it; 0179 } 0180 } 0181 0182 /** 0183 * Verify that the iterators work exactly like their counterparts for the 0184 * equivalent QVector<int>. 0185 */ 0186 void KItemSetTest::testIterators() 0187 { 0188 QFETCH(KItemRangeList, itemRanges); 0189 0190 KItemSet itemSet = KItemRangeList2KItemSet(itemRanges); 0191 QVector<int> itemsQVector = KItemRangeList2QVector(itemRanges); 0192 0193 QVERIFY(itemSet.isValid()); 0194 QVERIFY(itemSet.count() == itemsQVector.count()); 0195 0196 if (itemSet.isEmpty()) { 0197 QVERIFY(itemSet.isEmpty()); 0198 QVERIFY(itemSet.begin() == itemSet.end()); 0199 QVERIFY(itemSet.constBegin() == itemSet.constEnd()); 0200 } else { 0201 QVERIFY(!itemSet.isEmpty()); 0202 QVERIFY(itemSet.begin() != itemSet.end()); 0203 QVERIFY(itemSet.constBegin() != itemSet.constEnd()); 0204 0205 const int min = itemsQVector.first(); 0206 const int max = itemsQVector.last(); 0207 0208 QCOMPARE(*itemSet.begin(), min); 0209 QCOMPARE(*itemSet.constBegin(), min); 0210 QCOMPARE(itemSet.first(), min); 0211 0212 QCOMPARE(*(--itemSet.end()), max); 0213 QCOMPARE(*(--itemSet.constEnd()), max); 0214 QCOMPARE(itemSet.last(), max); 0215 } 0216 0217 // Test iterating using the different iterators. 0218 QVector<int> testQVector; 0219 for (KItemSet::iterator it = itemSet.begin(), end = itemSet.end(); it != end; ++it) { 0220 testQVector.append(*it); 0221 } 0222 QCOMPARE(testQVector, itemsQVector); 0223 0224 testQVector.clear(); 0225 for (KItemSet::const_iterator it = itemSet.constBegin(), end = itemSet.constEnd(); it != end; ++it) { 0226 testQVector.append(*it); 0227 } 0228 QCOMPARE(testQVector, itemsQVector); 0229 0230 testQVector.clear(); 0231 for (int i : itemSet) { 0232 testQVector.append(i); 0233 } 0234 QCOMPARE(testQVector, itemsQVector); 0235 0236 // Verify that both variants of the (const)iterator's operator++ and 0237 // operator-- functions behave exactly like their QVector equivalents. 0238 KItemSet::iterator it1 = itemSet.begin(); 0239 KItemSet::iterator it2 = itemSet.begin(); 0240 KItemSet::const_iterator constIt1 = itemSet.constBegin(); 0241 KItemSet::const_iterator constIt2 = itemSet.constBegin(); 0242 QVector<int>::iterator vectorIt1 = itemsQVector.begin(); 0243 QVector<int>::iterator vectorIt2 = itemsQVector.begin(); 0244 QVector<int>::const_iterator vectorConstIt1 = itemsQVector.constBegin(); 0245 QVector<int>::const_iterator vectorConstIt2 = itemsQVector.constBegin(); 0246 0247 while (it1 != itemSet.end()) { 0248 if (it1 != --itemSet.end()) { 0249 QCOMPARE(*(++it1), *(++vectorIt1)); 0250 QCOMPARE(*(++constIt1), *(++vectorConstIt1)); 0251 } else { 0252 QCOMPARE(++it1, itemSet.end()); 0253 QCOMPARE(++vectorIt1, itemsQVector.end()); 0254 QCOMPARE(++constIt1, itemSet.constEnd()); 0255 QCOMPARE(++vectorConstIt1, itemsQVector.constEnd()); 0256 } 0257 0258 QCOMPARE(*(it2++), *(vectorIt2++)); 0259 QCOMPARE(*(constIt2++), *(vectorConstIt2++)); 0260 0261 QCOMPARE(it1, it2); 0262 QCOMPARE(constIt1, constIt2); 0263 QCOMPARE(KItemSet::const_iterator(it1), constIt1); 0264 } 0265 0266 QCOMPARE(it1, itemSet.end()); 0267 QCOMPARE(it2, itemSet.end()); 0268 QCOMPARE(constIt1, itemSet.constEnd()); 0269 QCOMPARE(constIt2, itemSet.constEnd()); 0270 QCOMPARE(vectorIt1, itemsQVector.end()); 0271 QCOMPARE(vectorIt2, itemsQVector.end()); 0272 QCOMPARE(vectorConstIt1, itemsQVector.constEnd()); 0273 QCOMPARE(vectorConstIt2, itemsQVector.constEnd()); 0274 0275 while (it1 != itemSet.begin()) { 0276 QCOMPARE(*(--it1), *(--vectorIt1)); 0277 QCOMPARE(*(--constIt1), *(--vectorConstIt1)); 0278 0279 if (it2 != itemSet.end()) { 0280 QCOMPARE(*(it2--), *(vectorIt2--)); 0281 QCOMPARE(*(constIt2--), *(vectorConstIt2--)); 0282 } else { 0283 QCOMPARE(it2--, itemSet.end()); 0284 QCOMPARE(vectorIt2--, itemsQVector.end()); 0285 QCOMPARE(constIt2--, itemSet.constEnd()); 0286 QCOMPARE(vectorConstIt2--, itemsQVector.constEnd()); 0287 } 0288 0289 QCOMPARE(it1, it2); 0290 QCOMPARE(constIt1, constIt2); 0291 QCOMPARE(KItemSet::const_iterator(it1), constIt1); 0292 } 0293 0294 QCOMPARE(it1, itemSet.begin()); 0295 QCOMPARE(it2, itemSet.begin()); 0296 QCOMPARE(constIt1, itemSet.constBegin()); 0297 QCOMPARE(constIt2, itemSet.constBegin()); 0298 QCOMPARE(vectorIt1, itemsQVector.begin()); 0299 QCOMPARE(vectorIt2, itemsQVector.begin()); 0300 QCOMPARE(vectorConstIt1, itemsQVector.constBegin()); 0301 QCOMPARE(vectorConstIt2, itemsQVector.constBegin()); 0302 } 0303 0304 void KItemSetTest::testFind_data() 0305 { 0306 QTest::addColumn<KItemRangeList>("itemRanges"); 0307 0308 QHash<const char *, KItemRangeList>::const_iterator it = m_testCases.constBegin(); 0309 const QHash<const char *, KItemRangeList>::const_iterator end = m_testCases.constEnd(); 0310 0311 while (it != end) { 0312 QTest::newRow(it.key()) << it.value(); 0313 ++it; 0314 } 0315 } 0316 0317 /** 0318 * Test all functions that find items: 0319 * contains(int), find(int), constFind(int) 0320 */ 0321 void KItemSetTest::testFind() 0322 { 0323 QFETCH(KItemRangeList, itemRanges); 0324 0325 KItemSet itemSet = KItemRangeList2KItemSet(itemRanges); 0326 QSet<int> itemsQSet = KItemRangeList2QSet(itemRanges); 0327 0328 QVERIFY(itemSet.isValid()); 0329 QVERIFY(itemSet.count() == itemsQSet.count()); 0330 0331 // Find the minimum and maximum items. 0332 int min; 0333 int max; 0334 0335 if (itemSet.isEmpty()) { 0336 // Use some arbitrary values for the upcoming tests. 0337 min = 0; 0338 max = 5; 0339 } else { 0340 min = *itemSet.begin(); 0341 max = *(--itemSet.end()); 0342 } 0343 0344 // Test contains(int), find(int), and constFind(int) 0345 // for items between min - 2 and max + 2. 0346 for (int i = min - 2; i <= max + 2; ++i) { 0347 const KItemSet::iterator it = itemSet.find(i); 0348 const KItemSet::const_iterator constIt = itemSet.constFind(i); 0349 QCOMPARE(KItemSet::const_iterator(it), constIt); 0350 0351 if (itemsQSet.contains(i)) { 0352 QVERIFY(itemSet.contains(i)); 0353 QCOMPARE(*it, i); 0354 QCOMPARE(*constIt, i); 0355 } else { 0356 QVERIFY(!itemSet.contains(i)); 0357 QCOMPARE(it, itemSet.end()); 0358 QCOMPARE(constIt, itemSet.constEnd()); 0359 } 0360 } 0361 } 0362 0363 void KItemSetTest::testChangingOneItem_data() 0364 { 0365 QTest::addColumn<KItemRangeList>("itemRanges"); 0366 0367 QHash<const char *, KItemRangeList>::const_iterator it = m_testCases.constBegin(); 0368 const QHash<const char *, KItemRangeList>::const_iterator end = m_testCases.constEnd(); 0369 0370 while (it != end) { 0371 QTest::newRow(it.key()) << it.value(); 0372 ++it; 0373 } 0374 } 0375 0376 /** 0377 * Test all functions that change a single item: 0378 * insert(int), remove(int), erase(KItemSet::iterator) 0379 */ 0380 void KItemSetTest::testChangingOneItem() 0381 { 0382 QFETCH(KItemRangeList, itemRanges); 0383 0384 KItemSet itemSet = KItemRangeList2KItemSet(itemRanges); 0385 QSet<int> itemsQSet = KItemRangeList2QSet(itemRanges); 0386 0387 QVERIFY(itemSet.isValid()); 0388 QVERIFY(itemSet.count() == itemsQSet.count()); 0389 0390 // Find the minimum and maximum items. 0391 int min; 0392 int max; 0393 0394 if (itemSet.isEmpty()) { 0395 // Use some arbitrary values for the upcoming tests. 0396 min = 0; 0397 max = 5; 0398 } else { 0399 min = *itemSet.begin(); 0400 max = *(--itemSet.end()); 0401 } 0402 0403 // Test insert(int), remove(int), and erase(KItemSet::iterator) 0404 // for items between min - 2 and max + 2. 0405 for (int i = min - 2; i <= max + 2; ++i) { 0406 // Test insert(int). 0407 { 0408 KItemSet tmp(itemSet); 0409 const KItemSet::iterator insertedIt = tmp.insert(i); 0410 QCOMPARE(*insertedIt, i); 0411 0412 QVERIFY(tmp.isValid()); 0413 QVERIFY(tmp.contains(i)); 0414 0415 QSet<int> expectedQSet = itemsQSet; 0416 expectedQSet.insert(i); 0417 QCOMPARE(KItemSet2QSet(tmp), expectedQSet); 0418 0419 if (!itemSet.contains(i)) { 0420 QVERIFY(itemSet != tmp); 0421 QCOMPARE(tmp.count(), itemSet.count() + 1); 0422 } else { 0423 QCOMPARE(itemSet, tmp); 0424 } 0425 0426 QCOMPARE(i, *tmp.find(i)); 0427 QCOMPARE(i, *tmp.constFind(i)); 0428 0429 // Erase the new item and check that we get the old KItemSet back. 0430 tmp.erase(tmp.find(i)); 0431 QVERIFY(tmp.isValid()); 0432 QVERIFY(!tmp.contains(i)); 0433 0434 if (!itemSet.contains(i)) { 0435 QCOMPARE(itemSet, tmp); 0436 } 0437 0438 expectedQSet.remove(i); 0439 QCOMPARE(KItemSet2QSet(tmp), expectedQSet); 0440 } 0441 0442 // Test remove(int). 0443 { 0444 KItemSet tmp(itemSet); 0445 const bool removed = tmp.remove(i); 0446 0447 QCOMPARE(removed, itemSet.contains(i)); 0448 0449 QVERIFY(tmp.isValid()); 0450 QVERIFY(!tmp.contains(i)); 0451 0452 QSet<int> expectedQSet = itemsQSet; 0453 expectedQSet.remove(i); 0454 QCOMPARE(KItemSet2QSet(tmp), expectedQSet); 0455 0456 if (itemSet.contains(i)) { 0457 QVERIFY(itemSet != tmp); 0458 QCOMPARE(tmp.count(), itemSet.count() - 1); 0459 } else { 0460 QCOMPARE(itemSet, tmp); 0461 } 0462 0463 QCOMPARE(tmp.end(), tmp.find(i)); 0464 QCOMPARE(tmp.constEnd(), tmp.constFind(i)); 0465 } 0466 0467 // Test erase(KItemSet::iterator). 0468 if (itemSet.contains(i)) { 0469 KItemSet tmp(itemSet); 0470 KItemSet::iterator it = tmp.find(i); 0471 it = tmp.erase(it); 0472 0473 QVERIFY(tmp.isValid()); 0474 QVERIFY(!tmp.contains(i)); 0475 0476 QSet<int> expectedQSet = itemsQSet; 0477 expectedQSet.remove(i); 0478 QCOMPARE(KItemSet2QSet(tmp), expectedQSet); 0479 0480 if (itemSet.contains(i)) { 0481 QVERIFY(itemSet != tmp); 0482 QCOMPARE(tmp.count(), itemSet.count() - 1); 0483 } else { 0484 QCOMPARE(itemSet, tmp); 0485 } 0486 0487 QCOMPARE(tmp.end(), tmp.find(i)); 0488 QCOMPARE(tmp.constEnd(), tmp.constFind(i)); 0489 0490 // Check the returned value, now contained in 'it'. 0491 if (i == max) { 0492 QCOMPARE(it, tmp.end()); 0493 } else { 0494 // it now points to the next item. 0495 QVERIFY(tmp.contains(*it)); 0496 for (int j = i; j < *it; ++j) { 0497 QVERIFY(!tmp.contains(j)); 0498 } 0499 } 0500 } 0501 } 0502 0503 // Clear the set. 0504 itemSet.clear(); 0505 QVERIFY(itemSet.isEmpty()); 0506 QCOMPARE(itemSet.count(), 0); 0507 } 0508 0509 void KItemSetTest::testAddSets_data() 0510 { 0511 QTest::addColumn<KItemRangeList>("itemRanges1"); 0512 QTest::addColumn<KItemRangeList>("itemRanges2"); 0513 0514 QHash<const char *, KItemRangeList>::const_iterator it1 = m_testCases.constBegin(); 0515 const QHash<const char *, KItemRangeList>::const_iterator end = m_testCases.constEnd(); 0516 0517 while (it1 != end) { 0518 QHash<const char *, KItemRangeList>::const_iterator it2 = m_testCases.constBegin(); 0519 0520 while (it2 != end) { 0521 QByteArray name = it1.key() + QByteArray(" + ") + it2.key(); 0522 QTest::newRow(name) << it1.value() << it2.value(); 0523 ++it2; 0524 } 0525 0526 ++it1; 0527 } 0528 } 0529 0530 void KItemSetTest::testAddSets() 0531 { 0532 QFETCH(KItemRangeList, itemRanges1); 0533 QFETCH(KItemRangeList, itemRanges2); 0534 0535 KItemSet itemSet1 = KItemRangeList2KItemSet(itemRanges1); 0536 QSet<int> itemsQSet1 = KItemRangeList2QSet(itemRanges1); 0537 0538 KItemSet itemSet2 = KItemRangeList2KItemSet(itemRanges2); 0539 QSet<int> itemsQSet2 = KItemRangeList2QSet(itemRanges2); 0540 0541 KItemSet sum = itemSet1 + itemSet2; 0542 QSet<int> sumQSet = itemsQSet1 + itemsQSet2; 0543 0544 QCOMPARE(sum.count(), sumQSet.count()); 0545 QCOMPARE(KItemSet2QSet(sum), sumQSet); 0546 } 0547 0548 void KItemSetTest::testSymmetricDifference_data() 0549 { 0550 QTest::addColumn<KItemRangeList>("itemRanges1"); 0551 QTest::addColumn<KItemRangeList>("itemRanges2"); 0552 0553 QHash<const char *, KItemRangeList>::const_iterator it1 = m_testCases.constBegin(); 0554 const QHash<const char *, KItemRangeList>::const_iterator end = m_testCases.constEnd(); 0555 0556 while (it1 != end) { 0557 QHash<const char *, KItemRangeList>::const_iterator it2 = m_testCases.constBegin(); 0558 0559 while (it2 != end) { 0560 QByteArray name = it1.key() + QByteArray(" ^ ") + it2.key(); 0561 QTest::newRow(name) << it1.value() << it2.value(); 0562 ++it2; 0563 } 0564 0565 ++it1; 0566 } 0567 } 0568 0569 void KItemSetTest::testSymmetricDifference() 0570 { 0571 QFETCH(KItemRangeList, itemRanges1); 0572 QFETCH(KItemRangeList, itemRanges2); 0573 0574 KItemSet itemSet1 = KItemRangeList2KItemSet(itemRanges1); 0575 QSet<int> itemsQSet1 = KItemRangeList2QSet(itemRanges1); 0576 0577 KItemSet itemSet2 = KItemRangeList2KItemSet(itemRanges2); 0578 QSet<int> itemsQSet2 = KItemRangeList2QSet(itemRanges2); 0579 0580 KItemSet symmetricDifference = itemSet1 ^ itemSet2; 0581 QSet<int> symmetricDifferenceQSet = (itemsQSet1 - itemsQSet2) + (itemsQSet2 - itemsQSet1); 0582 0583 QCOMPARE(symmetricDifference.count(), symmetricDifferenceQSet.count()); 0584 QCOMPARE(KItemSet2QSet(symmetricDifference), symmetricDifferenceQSet); 0585 0586 // Check commutativity. 0587 QCOMPARE(itemSet2 ^ itemSet1, symmetricDifference); 0588 0589 // Some more checks: 0590 // itemSet1 ^ symmetricDifference == itemSet2, 0591 // itemSet2 ^ symmetricDifference == itemSet1. 0592 QCOMPARE(itemSet1 ^ symmetricDifference, itemSet2); 0593 QCOMPARE(itemSet2 ^ symmetricDifference, itemSet1); 0594 } 0595 0596 QTEST_GUILESS_MAIN(KItemSetTest) 0597 0598 #include "kitemsettest.moc"