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