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 : qAsConst(itemSet)) {
  70         Q_ASSERT(result.contains(i));
  71     }
  72
  73     for (int i : qAsConst(result)) {
  74         Q_ASSERT(itemSet.contains(i));
  75     }
  76
  77     return result;
  78 }
  79
  80
  81 /**
  82  * The main test class.
  83  */
  84 class KItemSetTest : public QObject
  85 {
  86     Q_OBJECT
  87
  88 private Q_SLOTS:
  89     void initTestCase();
  90
  91     void testConstruction_data();
  92     void testConstruction();
  93     void testIterators_data();
  94     void testIterators();
  95     void testFind_data();
  96     void testFind();
  97     void testChangingOneItem_data();
  98     void testChangingOneItem();
  99     void testAddSets_data();
 100     void testAddSets();
 101     /*
 102     void testSubtractSets_data();
 103     void testSubtractSets();
 104     */
 105     void testSymmetricDifference_data();
 106     void testSymmetricDifference();
 107
 108 private:
 109     QHash<const char*, KItemRangeList> m_testCases;
 110 };
 111
 112 void KItemSetTest::initTestCase()
 113 {
 114     QStandardPaths::setTestModeEnabled(true);
 115
 116     m_testCases.insert("empty", KItemRangeList());
 117     m_testCases.insert("[0]", KItemRangeList() << KItemRange(0, 1));
 118     m_testCases.insert("[1]", KItemRangeList() << KItemRange(1, 1));
 119     m_testCases.insert("[1, 2]", KItemRangeList() << KItemRange(1, 2));
 120     m_testCases.insert("[1, 2] [5]", KItemRangeList() << KItemRange(1, 2) << KItemRange(5, 1));
 121     m_testCases.insert("[1] [4, 5]", KItemRangeList() << KItemRange(1, 1) << KItemRange(4, 2));
 122     m_testCases.insert("[1, 2] [4, 5]", KItemRangeList() << KItemRange(1, 2) << KItemRange(4, 2));
 123     m_testCases.insert("[1, 5]", KItemRangeList() << KItemRange(1, 5));
 124     m_testCases.insert("[1, 2] [4, 5] [7] [9, 10] [13] [20, 25] [30]",
 125                        KItemRangeList() << KItemRange(1, 2) << KItemRange(4, 2) << KItemRange(7, 1) << KItemRange(9, 2) << KItemRange(20, 6) << 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
 407         // Test insert(int).
 408         {
 409             KItemSet tmp(itemSet);
 410             const KItemSet::iterator insertedIt = tmp.insert(i);
 411             QCOMPARE(*insertedIt, i);
 412
 413             QVERIFY(tmp.isValid());
 414             QVERIFY(tmp.contains(i));
 415
 416             QSet<int> expectedQSet = itemsQSet;
 417             expectedQSet.insert(i);
 418             QCOMPARE(KItemSet2QSet(tmp), expectedQSet);
 419
 420             if (!itemSet.contains(i)) {
 421                 QVERIFY(itemSet != tmp);
 422                 QCOMPARE(tmp.count(), itemSet.count() + 1);
 423             } else {
 424                 QCOMPARE(itemSet, tmp);
 425             }
 426
 427             QCOMPARE(i, *tmp.find(i));
 428             QCOMPARE(i, *tmp.constFind(i));
 429
 430             // Erase the new item and check that we get the old KItemSet back.
 431             tmp.erase(tmp.find(i));
 432             QVERIFY(tmp.isValid());
 433             QVERIFY(!tmp.contains(i));
 434
 435             if (!itemSet.contains(i)) {
 436                 QCOMPARE(itemSet, tmp);
 437             }
 438
 439             expectedQSet.remove(i);
 440             QCOMPARE(KItemSet2QSet(tmp), expectedQSet);
 441         }
 442
 443         // Test remove(int).
 444         {
 445             KItemSet tmp(itemSet);
 446             const bool removed = tmp.remove(i);
 447
 448             QCOMPARE(removed, itemSet.contains(i));
 449
 450             QVERIFY(tmp.isValid());
 451             QVERIFY(!tmp.contains(i));
 452
 453             QSet<int> expectedQSet = itemsQSet;
 454             expectedQSet.remove(i);
 455             QCOMPARE(KItemSet2QSet(tmp), expectedQSet);
 456
 457             if (itemSet.contains(i)) {
 458                 QVERIFY(itemSet != tmp);
 459                 QCOMPARE(tmp.count(), itemSet.count() - 1);
 460             } else {
 461                 QCOMPARE(itemSet, tmp);
 462             }
 463
 464             QCOMPARE(tmp.end(), tmp.find(i));
 465             QCOMPARE(tmp.constEnd(), tmp.constFind(i));
 466         }
 467
 468         // Test erase(KItemSet::iterator).
 469         if (itemSet.contains(i)) {
 470             KItemSet tmp(itemSet);
 471             KItemSet::iterator it = tmp.find(i);
 472             it = tmp.erase(it);
 473
 474             QVERIFY(tmp.isValid());
 475             QVERIFY(!tmp.contains(i));
 476
 477             QSet<int> expectedQSet = itemsQSet;
 478             expectedQSet.remove(i);
 479             QCOMPARE(KItemSet2QSet(tmp), expectedQSet);
 480
 481             if (itemSet.contains(i)) {
 482                 QVERIFY(itemSet != tmp);
 483                 QCOMPARE(tmp.count(), itemSet.count() - 1);
 484             } else {
 485                 QCOMPARE(itemSet, tmp);
 486             }
 487
 488             QCOMPARE(tmp.end(), tmp.find(i));
 489             QCOMPARE(tmp.constEnd(), tmp.constFind(i));
 490
 491             // Check the returned value, now contained in 'it'.
 492             if (i == max) {
 493                 QCOMPARE(it, tmp.end());
 494             } else {
 495                 // it now points to the next item.
 496                 QVERIFY(tmp.contains(*it));
 497                 for (int j = i; j < *it; ++j) {
 498                     QVERIFY(!tmp.contains(j));
 499                 }
 500             }
 501         }
 502     }
 503
 504     // Clear the set.
 505     itemSet.clear();
 506     QVERIFY(itemSet.isEmpty());
 507     QCOMPARE(itemSet.count(), 0);
 508 }
 509
 510 void KItemSetTest::testAddSets_data()
 511 {
 512     QTest::addColumn<KItemRangeList>("itemRanges1");
 513     QTest::addColumn<KItemRangeList>("itemRanges2");
 514
 515     QHash<const char*, KItemRangeList>::const_iterator it1 = m_testCases.constBegin();
 516     const QHash<const char*, KItemRangeList>::const_iterator end = m_testCases.constEnd();
 517
 518     while (it1 != end) {
 519         QHash<const char*, KItemRangeList>::const_iterator it2 = m_testCases.constBegin();
 520
 521         while (it2 != end) {
 522             QByteArray name = it1.key() + QByteArray(" + ") + it2.key();
 523             QTest::newRow(name) << it1.value() << it2.value();
 524             ++it2;
 525         }
 526
 527         ++it1;
 528     }
 529 }
 530
 531 void KItemSetTest::testAddSets()
 532 {
 533     QFETCH(KItemRangeList, itemRanges1);
 534     QFETCH(KItemRangeList, itemRanges2);
 535
 536     KItemSet itemSet1 = KItemRangeList2KItemSet(itemRanges1);
 537     QSet<int> itemsQSet1 = KItemRangeList2QSet(itemRanges1);
 538
 539     KItemSet itemSet2 = KItemRangeList2KItemSet(itemRanges2);
 540     QSet<int> itemsQSet2 = KItemRangeList2QSet(itemRanges2);
 541
 542     KItemSet sum = itemSet1 + itemSet2;
 543     QSet<int> sumQSet = itemsQSet1 + itemsQSet2;
 544
 545     QCOMPARE(sum.count(), sumQSet.count());
 546     QCOMPARE(KItemSet2QSet(sum), sumQSet);
 547 }
 548
 549 void KItemSetTest::testSymmetricDifference_data()
 550 {
 551     QTest::addColumn<KItemRangeList>("itemRanges1");
 552     QTest::addColumn<KItemRangeList>("itemRanges2");
 553
 554     QHash<const char*, KItemRangeList>::const_iterator it1 = m_testCases.constBegin();
 555     const QHash<const char*, KItemRangeList>::const_iterator end = m_testCases.constEnd();
 556
 557     while (it1 != end) {
 558         QHash<const char*, KItemRangeList>::const_iterator it2 = m_testCases.constBegin();
 559
 560         while (it2 != end) {
 561             QByteArray name = it1.key() + QByteArray(" ^ ") + it2.key();
 562             QTest::newRow(name) << it1.value() << it2.value();
 563             ++it2;
 564         }
 565
 566         ++it1;
 567     }
 568 }
 569
 570 void KItemSetTest::testSymmetricDifference()
 571 {
 572     QFETCH(KItemRangeList, itemRanges1);
 573     QFETCH(KItemRangeList, itemRanges2);
 574
 575     KItemSet itemSet1 = KItemRangeList2KItemSet(itemRanges1);
 576     QSet<int> itemsQSet1 = KItemRangeList2QSet(itemRanges1);
 577
 578     KItemSet itemSet2 = KItemRangeList2KItemSet(itemRanges2);
 579     QSet<int> itemsQSet2 = KItemRangeList2QSet(itemRanges2);
 580
 581     KItemSet symmetricDifference = itemSet1 ^ itemSet2;
 582     QSet<int> symmetricDifferenceQSet = (itemsQSet1 - itemsQSet2) + (itemsQSet2 - itemsQSet1);
 583
 584     QCOMPARE(symmetricDifference.count(), symmetricDifferenceQSet.count());
 585     QCOMPARE(KItemSet2QSet(symmetricDifference), symmetricDifferenceQSet);
 586
 587     // Check commutativity.
 588     QCOMPARE(itemSet2 ^ itemSet1, symmetricDifference);
 589
 590     // Some more checks:
 591     // itemSet1 ^ symmetricDifference == itemSet2,
 592     // itemSet2 ^ symmetricDifference == itemSet1.
 593     QCOMPARE(itemSet1 ^ symmetricDifference, itemSet2);
 594     QCOMPARE(itemSet2 ^ symmetricDifference, itemSet1);
 595 }
 596
 597
 598 QTEST_GUILESS_MAIN(KItemSetTest)
 599
 600 #include "kitemsettest.moc"