src/tests/kitemsettest.cpp

   1 /*
   2  * SPDX-FileCopyrightText: 2013 Frank Reininghaus <frank78ac@googlemail.com>
   3  *
   4  * SPDX-License-Identifier: GPL-2.0-or-later
   5  */
   6
   7 #include "kitemviews/kitemset.h"
   8
   9 #include <QStandardPaths>
  10 #include <QTest>
  11
  12 Q_DECLARE_METATYPE(KItemRangeList)
  13
  14 /**
  15  * Converts a KItemRangeList to a KItemSet.
  16  */
  17 KItemSet KItemRangeList2KItemSet(const KItemRangeList &itemRanges)
  18 {
  19     KItemSet result;
  20     for (const KItemRange &range : itemRanges) {
  21         for (int i = range.index; i < range.index + range.count; ++i) {
  22             result.insert(i);
  23         }
  24     }
  25     return result;
  26 }
  27
  28 /**
  29  * Converts a KItemRangeList to a QSet<int>.
  30  */
  31 QSet<int> KItemRangeList2QSet(const KItemRangeList &itemRanges)
  32 {
  33     QSet<int> result;
  34     for (const KItemRange &range : itemRanges) {
  35         for (int i = range.index; i < range.index + range.count; ++i) {
  36             result.insert(i);
  37         }
  38     }
  39     return result;
  40 }
  41
  42 /**
  43  * Converts a KItemRangeList to a QVector<int>.
  44  */
  45 QVector<int> KItemRangeList2QVector(const KItemRangeList &itemRanges)
  46 {
  47     QVector<int> result;
  48     for (const KItemRange &range : itemRanges) {
  49         for (int i = range.index; i < range.index + range.count; ++i) {
  50             result.append(i);
  51         }
  52     }
  53     return result;
  54 }
  55
  56 /**
  57  * Converts a KItemSet to a QSet<int>.
  58  */
  59 static QSet<int> KItemSet2QSet(const KItemSet &itemSet)
  60 {
  61     QSet<int> result;
  62     for (int i : itemSet) {
  63         result.insert(i);
  64     }
  65
  66     // Check that the conversion was successful.
  67     Q_ASSERT(itemSet.count() == result.count());
  68
  69     for (int i : std::as_const(itemSet)) {
  70         Q_ASSERT(result.contains(i));
  71     }
  72
  73     for (int i : std::as_const(result)) {
  74         Q_ASSERT(itemSet.contains(i));
  75     }
  76
  77     return result;
  78 }
  79
  80 /**
  81  * The main test class.
  82  */
  83 class KItemSetTest : public QObject
  84 {
  85     Q_OBJECT
  86
  87 private Q_SLOTS:
  88     void initTestCase();
  89
  90     void testConstruction_data();
  91     void testConstruction();
  92     void testIterators_data();
  93     void testIterators();
  94     void testFind_data();
  95     void testFind();
  96     void testChangingOneItem_data();
  97     void testChangingOneItem();
  98     void testAddSets_data();
  99     void testAddSets();
 100     /*
 101     void testSubtractSets_data();
 102     void testSubtractSets();
 103     */
 104     void testSymmetricDifference_data();
 105     void testSymmetricDifference();
 106
 107 private:
 108     QHash<const char *, KItemRangeList> m_testCases;
 109 };
 110
 111 void KItemSetTest::initTestCase()
 112 {
 113     QStandardPaths::setTestModeEnabled(true);
 114
 115     m_testCases.insert("empty", KItemRangeList());
 116     m_testCases.insert("[0]", KItemRangeList() << KItemRange(0, 1));
 117     m_testCases.insert("[1]", KItemRangeList() << KItemRange(1, 1));
 118     m_testCases.insert("[1, 2]", KItemRangeList() << KItemRange(1, 2));
 119     m_testCases.insert("[1, 2] [5]", KItemRangeList() << KItemRange(1, 2) << KItemRange(5, 1));
 120     m_testCases.insert("[1] [4, 5]", KItemRangeList() << KItemRange(1, 1) << KItemRange(4, 2));
 121     m_testCases.insert("[1, 2] [4, 5]", KItemRangeList() << KItemRange(1, 2) << KItemRange(4, 2));
 122     m_testCases.insert("[1, 5]", KItemRangeList() << KItemRange(1, 5));
 123     m_testCases.insert("[1, 2] [4, 5] [7] [9, 10] [13] [20, 25] [30]",
 124                        KItemRangeList() << KItemRange(1, 2) << KItemRange(4, 2) << KItemRange(7, 1) << KItemRange(9, 2) << KItemRange(20, 6)
 125                                         << KItemRange(30, 1));
 126     m_testCases.insert("[-10, -1]", KItemRangeList() << KItemRange(-10, 10));
 127     m_testCases.insert("[-10, 0]", KItemRangeList() << KItemRange(-10, 11));
 128     m_testCases.insert("[-10, 1]", KItemRangeList() << KItemRange(-10, 12));
 129     m_testCases.insert("[0, 9]", KItemRangeList() << KItemRange(0, 10));
 130     m_testCases.insert("[0, 19]", KItemRangeList() << KItemRange(0, 10));
 131 }
 132
 133 void KItemSetTest::testConstruction_data()
 134 {
 135     QTest::addColumn<KItemRangeList>("itemRanges");
 136
 137     QHash<const char *, KItemRangeList>::const_iterator it = m_testCases.constBegin();
 138     const QHash<const char *, KItemRangeList>::const_iterator end = m_testCases.constEnd();
 139
 140     while (it != end) {
 141         QTest::newRow(it.key()) << it.value();
 142         ++it;
 143     }
 144 }
 145
 146 void KItemSetTest::testConstruction()
 147 {
 148     QFETCH(KItemRangeList, itemRanges);
 149
 150     KItemSet itemSet = KItemRangeList2KItemSet(itemRanges);
 151     QSet<int> itemsQSet = KItemRangeList2QSet(itemRanges);
 152
 153     QVERIFY(itemSet.isValid());
 154     QVERIFY(itemSet.count() == itemsQSet.count());
 155     QCOMPARE(KItemSet2QSet(itemSet), itemsQSet);
 156
 157     // Test copy constructor.
 158     KItemSet copy(itemSet);
 159     QCOMPARE(itemSet, copy);
 160     copy.clear();
 161     QVERIFY(itemSet != copy || itemSet.isEmpty());
 162
 163     // Clear the set.
 164     itemSet.clear();
 165     QVERIFY(itemSet.isEmpty());
 166     QCOMPARE(itemSet.count(), 0);
 167 }
 168
 169 void KItemSetTest::testIterators_data()
 170 {
 171     QTest::addColumn<KItemRangeList>("itemRanges");
 172
 173     QHash<const char *, KItemRangeList>::const_iterator it = m_testCases.constBegin();
 174     const QHash<const char *, KItemRangeList>::const_iterator end = m_testCases.constEnd();
 175
 176     while (it != end) {
 177         QTest::newRow(it.key()) << it.value();
 178         ++it;
 179     }
 180 }
 181
 182 /**
 183  * Verify that the iterators work exactly like their counterparts for the
 184  * equivalent QVector<int>.
 185  */
 186 void KItemSetTest::testIterators()
 187 {
 188     QFETCH(KItemRangeList, itemRanges);
 189
 190     KItemSet itemSet = KItemRangeList2KItemSet(itemRanges);
 191     QVector<int> itemsQVector = KItemRangeList2QVector(itemRanges);
 192
 193     QVERIFY(itemSet.isValid());
 194     QVERIFY(itemSet.count() == itemsQVector.count());
 195
 196     if (itemSet.isEmpty()) {
 197         QVERIFY(itemSet.isEmpty());
 198         QVERIFY(itemSet.begin() == itemSet.end());
 199         QVERIFY(itemSet.constBegin() == itemSet.constEnd());
 200     } else {
 201         QVERIFY(!itemSet.isEmpty());
 202         QVERIFY(itemSet.begin() != itemSet.end());
 203         QVERIFY(itemSet.constBegin() != itemSet.constEnd());
 204
 205         const int min = itemsQVector.first();
 206         const int max = itemsQVector.last();
 207
 208         QCOMPARE(*itemSet.begin(), min);
 209         QCOMPARE(*itemSet.constBegin(), min);
 210         QCOMPARE(itemSet.first(), min);
 211
 212         QCOMPARE(*(--itemSet.end()), max);
 213         QCOMPARE(*(--itemSet.constEnd()), max);
 214         QCOMPARE(itemSet.last(), max);
 215     }
 216
 217     // Test iterating using the different iterators.
 218     QVector<int> testQVector;
 219     for (KItemSet::iterator it = itemSet.begin(), end = itemSet.end(); it != end; ++it) {
 220         testQVector.append(*it);
 221     }
 222     QCOMPARE(testQVector, itemsQVector);
 223
 224     testQVector.clear();
 225     for (KItemSet::const_iterator it = itemSet.constBegin(), end = itemSet.constEnd(); it != end; ++it) {
 226         testQVector.append(*it);
 227     }
 228     QCOMPARE(testQVector, itemsQVector);
 229
 230     testQVector.clear();
 231     for (int i : itemSet) {
 232         testQVector.append(i);
 233     }
 234     QCOMPARE(testQVector, itemsQVector);
 235
 236     // Verify that both variants of the (const)iterator's operator++ and
 237     // operator-- functions behave exactly like their QVector equivalents.
 238     KItemSet::iterator it1 = itemSet.begin();
 239     KItemSet::iterator it2 = itemSet.begin();
 240     KItemSet::const_iterator constIt1 = itemSet.constBegin();
 241     KItemSet::const_iterator constIt2 = itemSet.constBegin();
 242     QVector<int>::iterator vectorIt1 = itemsQVector.begin();
 243     QVector<int>::iterator vectorIt2 = itemsQVector.begin();
 244     QVector<int>::const_iterator vectorConstIt1 = itemsQVector.constBegin();
 245     QVector<int>::const_iterator vectorConstIt2 = itemsQVector.constBegin();
 246
 247     while (it1 != itemSet.end()) {
 248         if (it1 != --itemSet.end()) {
 249             QCOMPARE(*(++it1), *(++vectorIt1));
 250             QCOMPARE(*(++constIt1), *(++vectorConstIt1));
 251         } else {
 252             QCOMPARE(++it1, itemSet.end());
 253             QCOMPARE(++vectorIt1, itemsQVector.end());
 254             QCOMPARE(++constIt1, itemSet.constEnd());
 255             QCOMPARE(++vectorConstIt1, itemsQVector.constEnd());
 256         }
 257
 258         QCOMPARE(*(it2++), *(vectorIt2++));
 259         QCOMPARE(*(constIt2++), *(vectorConstIt2++));
 260
 261         QCOMPARE(it1, it2);
 262         QCOMPARE(constIt1, constIt2);
 263         QCOMPARE(KItemSet::const_iterator(it1), constIt1);
 264     }
 265
 266     QCOMPARE(it1, itemSet.end());
 267     QCOMPARE(it2, itemSet.end());
 268     QCOMPARE(constIt1, itemSet.constEnd());
 269     QCOMPARE(constIt2, itemSet.constEnd());
 270     QCOMPARE(vectorIt1, itemsQVector.end());
 271     QCOMPARE(vectorIt2, itemsQVector.end());
 272     QCOMPARE(vectorConstIt1, itemsQVector.constEnd());
 273     QCOMPARE(vectorConstIt2, itemsQVector.constEnd());
 274
 275     while (it1 != itemSet.begin()) {
 276         QCOMPARE(*(--it1), *(--vectorIt1));
 277         QCOMPARE(*(--constIt1), *(--vectorConstIt1));
 278
 279         if (it2 != itemSet.end()) {
 280             QCOMPARE(*(it2--), *(vectorIt2--));
 281             QCOMPARE(*(constIt2--), *(vectorConstIt2--));
 282         } else {
 283             QCOMPARE(it2--, itemSet.end());
 284             QCOMPARE(vectorIt2--, itemsQVector.end());
 285             QCOMPARE(constIt2--, itemSet.constEnd());
 286             QCOMPARE(vectorConstIt2--, itemsQVector.constEnd());
 287         }
 288
 289         QCOMPARE(it1, it2);
 290         QCOMPARE(constIt1, constIt2);
 291         QCOMPARE(KItemSet::const_iterator(it1), constIt1);
 292     }
 293
 294     QCOMPARE(it1, itemSet.begin());
 295     QCOMPARE(it2, itemSet.begin());
 296     QCOMPARE(constIt1, itemSet.constBegin());
 297     QCOMPARE(constIt2, itemSet.constBegin());
 298     QCOMPARE(vectorIt1, itemsQVector.begin());
 299     QCOMPARE(vectorIt2, itemsQVector.begin());
 300     QCOMPARE(vectorConstIt1, itemsQVector.constBegin());
 301     QCOMPARE(vectorConstIt2, itemsQVector.constBegin());
 302 }
 303
 304 void KItemSetTest::testFind_data()
 305 {
 306     QTest::addColumn<KItemRangeList>("itemRanges");
 307
 308     QHash<const char *, KItemRangeList>::const_iterator it = m_testCases.constBegin();
 309     const QHash<const char *, KItemRangeList>::const_iterator end = m_testCases.constEnd();
 310
 311     while (it != end) {
 312         QTest::newRow(it.key()) << it.value();
 313         ++it;
 314     }
 315 }
 316
 317 /**
 318  * Test all functions that find items:
 319  * contains(int), find(int), constFind(int)
 320  */
 321 void KItemSetTest::testFind()
 322 {
 323     QFETCH(KItemRangeList, itemRanges);
 324
 325     KItemSet itemSet = KItemRangeList2KItemSet(itemRanges);
 326     QSet<int> itemsQSet = KItemRangeList2QSet(itemRanges);
 327
 328     QVERIFY(itemSet.isValid());
 329     QVERIFY(itemSet.count() == itemsQSet.count());
 330
 331     // Find the minimum and maximum items.
 332     int min;
 333     int max;
 334
 335     if (itemSet.isEmpty()) {
 336         // Use some arbitrary values for the upcoming tests.
 337         min = 0;
 338         max = 5;
 339     } else {
 340         min = *itemSet.begin();
 341         max = *(--itemSet.end());
 342     }
 343
 344     // Test contains(int), find(int), and constFind(int)
 345     // for items between min - 2 and max + 2.
 346     for (int i = min - 2; i <= max + 2; ++i) {
 347         const KItemSet::iterator it = itemSet.find(i);
 348         const KItemSet::const_iterator constIt = itemSet.constFind(i);
 349         QCOMPARE(KItemSet::const_iterator(it), constIt);
 350
 351         if (itemsQSet.contains(i)) {
 352             QVERIFY(itemSet.contains(i));
 353             QCOMPARE(*it, i);
 354             QCOMPARE(*constIt, i);
 355         } else {
 356             QVERIFY(!itemSet.contains(i));
 357             QCOMPARE(it, itemSet.end());
 358             QCOMPARE(constIt, itemSet.constEnd());
 359         }
 360     }
 361 }
 362
 363 void KItemSetTest::testChangingOneItem_data()
 364 {
 365     QTest::addColumn<KItemRangeList>("itemRanges");
 366
 367     QHash<const char *, KItemRangeList>::const_iterator it = m_testCases.constBegin();
 368     const QHash<const char *, KItemRangeList>::const_iterator end = m_testCases.constEnd();
 369
 370     while (it != end) {
 371         QTest::newRow(it.key()) << it.value();
 372         ++it;
 373     }
 374 }
 375
 376 /**
 377  * Test all functions that change a single item:
 378  * insert(int), remove(int), erase(KItemSet::iterator)
 379  */
 380 void KItemSetTest::testChangingOneItem()
 381 {
 382     QFETCH(KItemRangeList, itemRanges);
 383
 384     KItemSet itemSet = KItemRangeList2KItemSet(itemRanges);
 385     QSet<int> itemsQSet = KItemRangeList2QSet(itemRanges);
 386
 387     QVERIFY(itemSet.isValid());
 388     QVERIFY(itemSet.count() == itemsQSet.count());
 389
 390     // Find the minimum and maximum items.
 391     int min;
 392     int max;
 393
 394     if (itemSet.isEmpty()) {
 395         // Use some arbitrary values for the upcoming tests.
 396         min = 0;
 397         max = 5;
 398     } else {
 399         min = *itemSet.begin();
 400         max = *(--itemSet.end());
 401     }
 402
 403     // Test insert(int), remove(int), and erase(KItemSet::iterator)
 404     // for items between min - 2 and max + 2.
 405     for (int i = min - 2; i <= max + 2; ++i) {
 406         // Test insert(int).
 407         {
 408             KItemSet tmp(itemSet);
 409             const KItemSet::iterator insertedIt = tmp.insert(i);
 410             QCOMPARE(*insertedIt, i);
 411
 412             QVERIFY(tmp.isValid());
 413             QVERIFY(tmp.contains(i));
 414
 415             QSet<int> expectedQSet = itemsQSet;
 416             expectedQSet.insert(i);
 417             QCOMPARE(KItemSet2QSet(tmp), expectedQSet);
 418
 419             if (!itemSet.contains(i)) {
 420                 QVERIFY(itemSet != tmp);
 421                 QCOMPARE(tmp.count(), itemSet.count() + 1);
 422             } else {
 423                 QCOMPARE(itemSet, tmp);
 424             }
 425
 426             QCOMPARE(i, *tmp.find(i));
 427             QCOMPARE(i, *tmp.constFind(i));
 428
 429             // Erase the new item and check that we get the old KItemSet back.
 430             tmp.erase(tmp.find(i));
 431             QVERIFY(tmp.isValid());
 432             QVERIFY(!tmp.contains(i));
 433
 434             if (!itemSet.contains(i)) {
 435                 QCOMPARE(itemSet, tmp);
 436             }
 437
 438             expectedQSet.remove(i);
 439             QCOMPARE(KItemSet2QSet(tmp), expectedQSet);
 440         }
 441
 442         // Test remove(int).
 443         {
 444             KItemSet tmp(itemSet);
 445             const bool removed = tmp.remove(i);
 446
 447             QCOMPARE(removed, itemSet.contains(i));
 448
 449             QVERIFY(tmp.isValid());
 450             QVERIFY(!tmp.contains(i));
 451
 452             QSet<int> expectedQSet = itemsQSet;
 453             expectedQSet.remove(i);
 454             QCOMPARE(KItemSet2QSet(tmp), expectedQSet);
 455
 456             if (itemSet.contains(i)) {
 457                 QVERIFY(itemSet != tmp);
 458                 QCOMPARE(tmp.count(), itemSet.count() - 1);
 459             } else {
 460                 QCOMPARE(itemSet, tmp);
 461             }
 462
 463             QCOMPARE(tmp.end(), tmp.find(i));
 464             QCOMPARE(tmp.constEnd(), tmp.constFind(i));
 465         }
 466
 467         // Test erase(KItemSet::iterator).
 468         if (itemSet.contains(i)) {
 469             KItemSet tmp(itemSet);
 470             KItemSet::iterator it = tmp.find(i);
 471             it = tmp.erase(it);
 472
 473             QVERIFY(tmp.isValid());
 474             QVERIFY(!tmp.contains(i));
 475
 476             QSet<int> expectedQSet = itemsQSet;
 477             expectedQSet.remove(i);
 478             QCOMPARE(KItemSet2QSet(tmp), expectedQSet);
 479
 480             if (itemSet.contains(i)) {
 481                 QVERIFY(itemSet != tmp);
 482                 QCOMPARE(tmp.count(), itemSet.count() - 1);
 483             } else {
 484                 QCOMPARE(itemSet, tmp);
 485             }
 486
 487             QCOMPARE(tmp.end(), tmp.find(i));
 488             QCOMPARE(tmp.constEnd(), tmp.constFind(i));
 489
 490             // Check the returned value, now contained in 'it'.
 491             if (i == max) {
 492                 QCOMPARE(it, tmp.end());
 493             } else {
 494                 // it now points to the next item.
 495                 QVERIFY(tmp.contains(*it));
 496                 for (int j = i; j < *it; ++j) {
 497                     QVERIFY(!tmp.contains(j));
 498                 }
 499             }
 500         }
 501     }
 502
 503     // Clear the set.
 504     itemSet.clear();
 505     QVERIFY(itemSet.isEmpty());
 506     QCOMPARE(itemSet.count(), 0);
 507 }
 508
 509 void KItemSetTest::testAddSets_data()
 510 {
 511     QTest::addColumn<KItemRangeList>("itemRanges1");
 512     QTest::addColumn<KItemRangeList>("itemRanges2");
 513
 514     QHash<const char *, KItemRangeList>::const_iterator it1 = m_testCases.constBegin();
 515     const QHash<const char *, KItemRangeList>::const_iterator end = m_testCases.constEnd();
 516
 517     while (it1 != end) {
 518         QHash<const char *, KItemRangeList>::const_iterator it2 = m_testCases.constBegin();
 519
 520         while (it2 != end) {
 521             QByteArray name = it1.key() + QByteArray(" + ") + it2.key();
 522             QTest::newRow(name) << it1.value() << it2.value();
 523             ++it2;
 524         }
 525
 526         ++it1;
 527     }
 528 }
 529
 530 void KItemSetTest::testAddSets()
 531 {
 532     QFETCH(KItemRangeList, itemRanges1);
 533     QFETCH(KItemRangeList, itemRanges2);
 534
 535     KItemSet itemSet1 = KItemRangeList2KItemSet(itemRanges1);
 536     QSet<int> itemsQSet1 = KItemRangeList2QSet(itemRanges1);
 537
 538     KItemSet itemSet2 = KItemRangeList2KItemSet(itemRanges2);
 539     QSet<int> itemsQSet2 = KItemRangeList2QSet(itemRanges2);
 540
 541     KItemSet sum = itemSet1 + itemSet2;
 542     QSet<int> sumQSet = itemsQSet1 + itemsQSet2;
 543
 544     QCOMPARE(sum.count(), sumQSet.count());
 545     QCOMPARE(KItemSet2QSet(sum), sumQSet);
 546 }
 547
 548 void KItemSetTest::testSymmetricDifference_data()
 549 {
 550     QTest::addColumn<KItemRangeList>("itemRanges1");
 551     QTest::addColumn<KItemRangeList>("itemRanges2");
 552
 553     QHash<const char *, KItemRangeList>::const_iterator it1 = m_testCases.constBegin();
 554     const QHash<const char *, KItemRangeList>::const_iterator end = m_testCases.constEnd();
 555
 556     while (it1 != end) {
 557         QHash<const char *, KItemRangeList>::const_iterator it2 = m_testCases.constBegin();
 558
 559         while (it2 != end) {
 560             QByteArray name = it1.key() + QByteArray(" ^ ") + it2.key();
 561             QTest::newRow(name) << it1.value() << it2.value();
 562             ++it2;
 563         }
 564
 565         ++it1;
 566     }
 567 }
 568
 569 void KItemSetTest::testSymmetricDifference()
 570 {
 571     QFETCH(KItemRangeList, itemRanges1);
 572     QFETCH(KItemRangeList, itemRanges2);
 573
 574     KItemSet itemSet1 = KItemRangeList2KItemSet(itemRanges1);
 575     QSet<int> itemsQSet1 = KItemRangeList2QSet(itemRanges1);
 576
 577     KItemSet itemSet2 = KItemRangeList2KItemSet(itemRanges2);
 578     QSet<int> itemsQSet2 = KItemRangeList2QSet(itemRanges2);
 579
 580     KItemSet symmetricDifference = itemSet1 ^ itemSet2;
 581     QSet<int> symmetricDifferenceQSet = (itemsQSet1 - itemsQSet2) + (itemsQSet2 - itemsQSet1);
 582
 583     QCOMPARE(symmetricDifference.count(), symmetricDifferenceQSet.count());
 584     QCOMPARE(KItemSet2QSet(symmetricDifference), symmetricDifferenceQSet);
 585
 586     // Check commutativity.
 587     QCOMPARE(itemSet2 ^ itemSet1, symmetricDifference);
 588
 589     // Some more checks:
 590     // itemSet1 ^ symmetricDifference == itemSet2,
 591     // itemSet2 ^ symmetricDifference == itemSet1.
 592     QCOMPARE(itemSet1 ^ symmetricDifference, itemSet2);
 593     QCOMPARE(itemSet2 ^ symmetricDifference, itemSet1);
 594 }
 595
 596 QTEST_GUILESS_MAIN(KItemSetTest)
 597
 598 #include "kitemsettest.moc"