1 /****************************************************************************

     2 **

     3 ** Copyright (C) 2009 Nokia Corporation and/or its subsidiary(-ies).

     4 ** All rights reserved.

     5 ** Contact: Nokia Corporation (qt-info@nokia.com)

     6 **

     7 ** This file is part of the test suite of the Qt Toolkit.

     8 **

     9 ** $QT_BEGIN_LICENSE:LGPL$

    10 ** No Commercial Usage

    11 ** This file contains pre-release code and may not be distributed.

    12 ** You may use this file in accordance with the terms and conditions

    13 ** contained in the Technology Preview License Agreement accompanying

    14 ** this package.

    15 **

    16 ** GNU Lesser General Public License Usage

    17 ** Alternatively, this file may be used under the terms of the GNU Lesser

    18 ** General Public License version 2.1 as published by the Free Software

    19 ** Foundation and appearing in the file LICENSE.LGPL included in the

    20 ** packaging of this file.  Please review the following information to

    21 ** ensure the GNU Lesser General Public License version 2.1 requirements

    22 ** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.

    23 **

    24 ** In addition, as a special exception, Nokia gives you certain additional

    25 ** rights.  These rights are described in the Nokia Qt LGPL Exception

    26 ** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.

    27 **

    28 ** If you have questions regarding the use of this file, please contact

    29 ** Nokia at qt-info@nokia.com.

    30 **

    31 **

    32 **

    33 **

    34 **

    35 **

    36 **

    37 **

    38 ** $QT_END_LICENSE$

    39 **

    40 ****************************************************************************/

    41 

    42 

    43 #include <QtTest/QtTest>

    44 

    45 #include <iostream>

    46 #include <iomanip>

    47 #include <sstream>

    48 #include <algorithm>

    49 #include <qalgorithms.h>

    50 #include "../../../src/qt3support/tools/q3tl.h"

    51 #include <QStringList>

    52 #include <QString>

    53 #include <QVector>

    54 

    55 #define Q_TEST_PERFORMANCE 0

    56 

    57 using namespace std;

    58 

    59 //TESTED_FILES=

    60 

    61 class tst_QAlgorithms : public QObject

    62 {

    63 Q_OBJECT

    64 

    65 public:

    66     tst_QAlgorithms();

    67     ~tst_QAlgorithms();

    68 

    69 public slots:

    70     void init();

    71     void cleanup();

    72 

    73 private slots:

    74     void qBubbleSort();

    75     void qHeapSort();

    76     void test_qLowerBound_data();

    77     void test_qLowerBound();

    78     void test_qUpperBound_data();

    79     void test_qUpperBound();

    80     void test_qBinaryFind_data();

    81     void test_qBinaryFind();

    82     void qBinaryFindOneEntry();

    83     void swap();

    84     void sortEmptyList();

    85     void sortedList();

    86     void sortAPItest();

    87     void stableSortTest();

    88     void stableSortCorrectnessTest_data();

    89     void stableSortCorrectnessTest();

    90     void convenienceAPI();

    91     void qCountIterators() const;

    92     void qCountContainer() const;

    93     void binaryFindOnLargeContainer() const;

    94 

    95 #if Q_TEST_PERFORMANCE

    96 private:

    97     void performance();

    98 #endif

    99 };

   100 

   101 tst_QAlgorithms::tst_QAlgorithms()

   102 

   103 {

   104 }

   105 

   106 tst_QAlgorithms::~tst_QAlgorithms()

   107 {

   108 

   109 }

   110 

   111 void tst_QAlgorithms::init()

   112 {

   113 }

   114 

   115 void tst_QAlgorithms::cleanup()

   116 {

   117 }

   118 

   119 

   120 class TestInt

   121 {

   122 public:

   123     TestInt(int number)  :m_number(number) {} ;

   124     TestInt() : m_number(0) {};

   125     bool operator<(const TestInt &other) const { ++TestInt::lessThanRefCount; return (m_number < other.m_number); }

   126     int m_number;

   127 static long int lessThanRefCount;

   128 };

   129 

   130 long int TestInt::lessThanRefCount;

   131 

   132 

   133 QStringList dataSetTypes = QStringList() << "Random" << "Ascending"

   134                 << "Descending" << "Equal" << "Duplicates" << "Almost Sorted"  ;

   135 

   136 template <typename DataType>

   137 QVector<DataType> generateData(QString dataSetType, const int length)

   138 {

   139     QVector<DataType> container;

   140     if (dataSetType == "Random") {

   141         for(int i=0; i < length; ++i)

   142             container.append(rand());

   143     }

   144     else if (dataSetType == "Ascending") {

   145         for (int i=0; i < length; ++i)

   146             container.append(i);

   147     }

   148     else if (dataSetType == "Descending") {

   149         for (int i=0; i < length; ++i)

   150             container.append(length - i);

   151     }

   152     else if (dataSetType == "Equal") {

   153         for (int i=0; i < length; ++i)

   154             container.append(43);

   155     }

   156     else if (dataSetType == "Duplicates") {

   157         for (int i=0; i < length; ++i)

   158             container.append(i % 10);

   159     }

   160     else if (dataSetType == "Almost Sorted") {

   161         for (int i=0; i < length; ++i)

   162             container.append(i);

   163         for(int i = 0; i<= length / 10; ++i) {

   164             const int iswap = i * 9;

   165             DataType tmp = container.at(iswap);

   166             container[iswap] = container.at(iswap + 1);

   167             container[iswap + 1] = tmp;

   168         }

   169     }

   170     return container;

   171 }

   172 

   173 struct ResultSet

   174 {

   175     int numSorts;

   176     long int lessThanRefCount;

   177 };

   178 

   179 

   180 template <typename ContainerType, typename Algorithm>

   181 ResultSet testRun(ContainerType &container, Algorithm &algorithm, int millisecs)

   182 {

   183     TestInt::lessThanRefCount = 0;

   184     int count = 0;

   185     QTime t;

   186     t.start();

   187     while(t.elapsed() < millisecs) {

   188         ++count;

   189         algorithm(container);

   190     }

   191     ResultSet result;

   192     result.numSorts = count;

   193     result.lessThanRefCount = TestInt::lessThanRefCount;

   194     return result;

   195 }

   196 

   197 template <typename ContainerType, typename LessThan>

   198 bool isSorted(ContainerType &container, LessThan lessThan)

   199 {

   200     for (int i=0; i < container.count() - 1; ++i)

   201         if (lessThan(container.at(i+1), container.at(i))) {

   202             return false;

   203         }

   204     return true;

   205 }

   206 

   207 template <typename ContainerType>

   208 bool isSorted(ContainerType &container)

   209 {

   210     return isSorted(container, qLess<Q_TYPENAME ContainerType::value_type>());

   211 }

   212 

   213 

   214 #if Q_TEST_PERFORMANCE

   215 void printHeader(QStringList &headers)

   216 {

   217     cout << setw(10) << setiosflags(ios_base::left) << " ";

   218     for (int h = 0; h < headers.count(); ++h) {

   219         cout << setw(20) << setiosflags(ios_base::left) << headers.at(h).toLatin1().constData();

   220     }

   221     cout << endl;

   222 }

   223 

   224 template <typename ContainerType>

   225 void print(ContainerType testContainer)

   226 {

   227     typedef typename ContainerType::value_type T;

   228 

   229     foreach(T value, testContainer) {

   230         cout << value << " ";

   231     }

   232 

   233     cout << endl;

   234 }

   235 

   236 template <typename Algorithm, typename DataType>

   237 QList<ResultSet> testAlgorithm(Algorithm &algorithm,  QStringList dataSetTypes,  int size, int time)

   238 {

   239     QList<ResultSet> results;

   240     foreach(QString dataSetType, dataSetTypes) {

   241         QVector<DataType> container = generateData<DataType>(dataSetType, size);

   242         results.append(testRun(container, algorithm, time));

   243         Q_ASSERT(isSorted(container));

   244     }

   245     return results;

   246 }

   247 

   248 template <typename Algorithm, typename DataType>

   249 void testAlgorithm(Algorithm algorithm, QStringList &dataSetTypes)

   250 {

   251     QList<int> sizes = QList<int>() << 5 << 15 << 35 << 70 << 200 << 1000 << 10000;

   252     printHeader(dataSetTypes);

   253     for (int s = 0; s < sizes.count(); ++s){

   254         cout << setw(10) <<  setiosflags(ios_base::left)<< sizes.at(s);

   255         QList<ResultSet> results =

   256             testAlgorithm<Algorithm, DataType>(algorithm, dataSetTypes, sizes.at(s), 100);

   257         foreach(ResultSet result, results) {

   258             stringstream numSorts;

   259             numSorts << setiosflags(ios_base::left) << setw(10) << result.numSorts;

   260             stringstream lessThan;

   261             lessThan << setiosflags(ios_base::left) << setw(10) << result.lessThanRefCount / result.numSorts;

   262             cout << numSorts.str() << lessThan.str();

   263         }

   264         cout << endl;

   265     }

   266 }

   267 #endif

   268 static bool userFunction1(char ch1, char ch2)

   269 {

   270     return (ch1 ^ 1) < (ch2 ^ 1);

   271 }

   272 

   273 bool userFunction2(const char &ch1, char ch2)

   274 {

   275     return (ch1 ^ 1) < (ch2 ^ 1);

   276 }

   277 

   278 static inline bool userFunction3(char ch1, const char &ch2)

   279 {

   280     return (ch1 ^ 1) < (ch2 ^ 1);

   281 }

   282 

   283 inline bool userFunction4(const char &ch1, const char &ch2)

   284 {

   285     return (ch1 ^ 1) < (ch2 ^ 1);

   286 }

   287 

   288 class UserFunctor1

   289 {

   290 public:

   291     UserFunctor1(int x = 1) : y(x) {}

   292 

   293     bool operator()(char ch1, char ch2)

   294     {

   295         return (ch1 ^ y) < (ch2 ^ y);

   296     }

   297 

   298     char y;

   299 };

   300 

   301 void tst_QAlgorithms::qHeapSort()

   302 {

   303     char array1[] = "3141592";

   304     ::qHeapSort((char *)array1, array1 + strlen(array1));

   305     QVERIFY(strcmp(array1, "1123459") == 0);

   306 

   307     ::qHeapSort((char *)array1, array1 + strlen(array1), qGreater<char>());

   308     QVERIFY(strcmp(array1, "9543211") == 0);

   309 

   310     ::qHeapSort((char *)array1, array1 + strlen(array1), qLess<char>());

   311     QVERIFY(strcmp(array1, "1123459") == 0);

   312     {

   313         char array2[] = "0123456789@ABCDE";

   314         ::qHeapSort((char *)array2, array2 + strlen(array2), userFunction1);

   315         QVERIFY(strcmp(array2, "1032547698A@CBED") == 0);

   316     }

   317 

   318     {

   319         char array2[] = "0123456789@ABCDE";

   320         ::qHeapSort((char *)array2, array2 + strlen(array2), userFunction2);

   321         QVERIFY(strcmp(array2, "1032547698A@CBED") == 0);

   322     }

   323 

   324     {

   325         char array2[] = "0123456789@ABCDE";

   326         ::qHeapSort((char *)array2, array2 + strlen(array2), userFunction3);

   327         QVERIFY(strcmp(array2, "1032547698A@CBED") == 0);

   328     }

   329 

   330     {

   331         char array2[] = "0123456789@ABCDE";

   332         ::qHeapSort((char *)array2, array2 + strlen(array2), userFunction4);

   333         QVERIFY(strcmp(array2, "1032547698A@CBED") == 0);

   334     }

   335 

   336     {

   337         UserFunctor1 userFunctor1;

   338         char array2[] = "0123456789@ABCDE";

   339         ::qHeapSort((char *)array2, array2 + strlen(array2), userFunctor1);

   340         QVERIFY(strcmp(array2, "1032547698A@CBED") == 0);

   341     }

   342 

   343     {

   344         char array2[] = "0123456789@ABCDE";

   345         ::qHeapSort((char *)array2, array2 + strlen(array2), UserFunctor1());

   346         QVERIFY(strcmp(array2, "1032547698A@CBED") == 0);

   347         ::qHeapSort((char *)array2, array2 + strlen(array2), UserFunctor1(1));

   348         QVERIFY(strcmp(array2, "1032547698A@CBED") == 0);

   349         ::qHeapSort((char *)array2, array2 + strlen(array2), UserFunctor1(3));

   350         QVERIFY(strcmp(array2, "3210765498CBA@ED") == 0);

   351         ::qHeapSort((char *)array2, array2 + strlen(array2), UserFunctor1(0));

   352         QVERIFY(strcmp(array2, "0123456789@ABCDE") == 0);

   353     }

   354 }

   355 

   356 void tst_QAlgorithms::qBubbleSort()

   357 {

   358     char array1[] = "3141592";

   359     ::qBubbleSort((char *)array1, array1 + strlen(array1));

   360     QVERIFY(strcmp(array1, "1123459") == 0);

   361 

   362     ::qBubbleSort((char *)array1, array1 + strlen(array1), qGreater<char>());

   363     QVERIFY(strcmp(array1, "9543211") == 0);

   364 

   365     ::qBubbleSort((char *)array1, array1 + strlen(array1), qLess<char>());

   366     QVERIFY(strcmp(array1, "1123459") == 0);

   367 

   368     {

   369         char array2[] = "0123456789@ABCDE";

   370         ::qBubbleSort((char *)array2, array2 + strlen(array2), userFunction1);

   371         QVERIFY(strcmp(array2, "1032547698A@CBED") == 0);

   372     }

   373 

   374     {

   375         char array2[] = "0123456789@ABCDE";

   376         ::qBubbleSort((char *)array2, array2 + strlen(array2), userFunction2);

   377         QVERIFY(strcmp(array2, "1032547698A@CBED") == 0);

   378     }

   379 

   380     {

   381         char array2[] = "0123456789@ABCDE";

   382         ::qBubbleSort((char *)array2, array2 + strlen(array2), userFunction3);

   383         QVERIFY(strcmp(array2, "1032547698A@CBED") == 0);

   384     }

   385 

   386     {

   387         char array2[] = "0123456789@ABCDE";

   388         ::qBubbleSort((char *)array2, array2 + strlen(array2), userFunction4);

   389         QVERIFY(strcmp(array2, "1032547698A@CBED") == 0);

   390     }

   391 

   392     {

   393         UserFunctor1 userFunctor1;

   394         char array2[] = "0123456789@ABCDE";

   395         ::qBubbleSort((char *)array2, array2 + strlen(array2), userFunctor1);

   396         QVERIFY(strcmp(array2, "1032547698A@CBED") == 0);

   397     }

   398 

   399     {

   400         char array2[] = "0123456789@ABCDE";

   401         ::qBubbleSort((char *)array2, array2 + strlen(array2), UserFunctor1());

   402         QVERIFY(strcmp(array2, "1032547698A@CBED") == 0);

   403         ::qBubbleSort((char *)array2, array2 + strlen(array2), UserFunctor1(1));

   404         QVERIFY(strcmp(array2, "1032547698A@CBED") == 0);

   405         ::qBubbleSort((char *)array2, array2 + strlen(array2), UserFunctor1(3));

   406         QVERIFY(strcmp(array2, "3210765498CBA@ED") == 0);

   407         ::qBubbleSort((char *)array2, array2 + strlen(array2), UserFunctor1(0));

   408         QVERIFY(strcmp(array2, "0123456789@ABCDE") == 0);

   409     }

   410 }

   411 

   412 void tst_QAlgorithms::swap()

   413 {

   414     {

   415         int a = 1, b = 2;

   416         qSwap(a, b);

   417         QVERIFY(a == 2);

   418         QVERIFY(b == 1);

   419 

   420         qSwap(a, a);

   421         QVERIFY(a == 2);

   422         QVERIFY(b == 1);

   423 

   424         qSwap(b, b);

   425         QVERIFY(a == 2);

   426         QVERIFY(b == 1);

   427 

   428         qSwap(a, b);

   429         QVERIFY(a == 1);

   430         QVERIFY(b == 2);

   431 

   432         qSwap(b, a);

   433         QVERIFY(a == 2);

   434         QVERIFY(b == 1);

   435     }

   436 

   437     {

   438         double a = 1.0, b = 2.0;

   439         qSwap(a, b);

   440         QVERIFY(a == 2.0);

   441         QVERIFY(b == 1.0);

   442 

   443         qSwap(a, a);

   444         QVERIFY(a == 2.0);

   445         QVERIFY(b == 1.0);

   446 

   447         qSwap(b, b);

   448         QVERIFY(a == 2.0);

   449         QVERIFY(b == 1.0);

   450 

   451         qSwap(a, b);

   452         QVERIFY(a == 1.0);

   453         QVERIFY(b == 2.0);

   454 

   455         qSwap(b, a);

   456         QVERIFY(a == 2.0);

   457         QVERIFY(b == 1.0);

   458     }

   459 

   460     {

   461         QString a = "1", b = "2";

   462         qSwap(a, b);

   463         QVERIFY(a == "2");

   464         QVERIFY(b == "1");

   465 

   466         qSwap(a, a);

   467         QVERIFY(a == "2");

   468         QVERIFY(b == "1");

   469 

   470         qSwap(b, b);

   471         QVERIFY(a == "2");

   472         QVERIFY(b == "1");

   473 

   474         qSwap(a, b);

   475         QVERIFY(a == "1");

   476         QVERIFY(b == "2");

   477 

   478         qSwap(b, a);

   479         QVERIFY(a == "2");

   480         QVERIFY(b == "1");

   481     }

   482 

   483     {

   484         void *a = 0, *b = 0;

   485         qSwap(a, b);

   486     }

   487 

   488     {

   489         const void *a = 0, *b = 0;

   490         qSwap(a, b);

   491     }

   492 

   493     {

   494         QString *a = 0, *b = 0;

   495         qSwap(a, b);

   496     }

   497 

   498     {

   499         const QString *a = 0, *b = 0;

   500         qSwap(a, b);

   501     }

   502 

   503     {

   504         QString **a = 0, **b = 0;

   505         qSwap(a, b);

   506     }

   507 

   508     {

   509         const QString **a = 0, **b = 0;

   510         qSwap(a, b);

   511     }

   512 

   513     {

   514         QString * const *a = 0, * const *b = 0;

   515         qSwap(a, b);

   516     }

   517 

   518     {

   519         const QString * const *a = 0, * const *b = 0;

   520         qSwap(a, b);

   521     }

   522 }

   523 

   524 void tst_QAlgorithms::sortEmptyList()

   525 {

   526     // Only test if it crashes

   527     QStringList stringList;

   528     stringList.sort();

   529     QVERIFY(true);

   530 }

   531 

   532 void tst_QAlgorithms::sortedList()

   533 {

   534     QList<int> list;

   535     list << 4 << 3 << 6;

   536 

   537     ::qHeapSort(list.begin(), list.end());

   538 

   539     QCOMPARE(list.count(), 3);

   540     QCOMPARE(list.at(0), 3);

   541     QCOMPARE(list.at(1), 4);

   542     QCOMPARE(list.at(2), 6);

   543 

   544     list.insert(qUpperBound(list.begin(), list.end(), 5), 5);

   545     list.insert(qUpperBound(list.begin(), list.end(), 1), 1);

   546     list.insert(qUpperBound(list.begin(), list.end(), 8), 8);

   547 

   548     QCOMPARE(list.count(), 6);

   549     QCOMPARE(list.at(0), 1);

   550     QCOMPARE(list.at(1), 3);

   551     QCOMPARE(list.at(2), 4);

   552     QCOMPARE(list.at(3), 5);

   553     QCOMPARE(list.at(4), 6);

   554     QCOMPARE(list.at(5), 8);

   555 }

   556 

   557 Q_DECLARE_METATYPE(QList<int>)

   558 

   559 void tst_QAlgorithms::test_qLowerBound_data()

   560 {

   561     QTest::addColumn<QList<int> >("data");

   562     QTest::addColumn<int>("resultValue");

   563     QTest::addColumn<int>("resultIndex");

   564 

   565     QTest::newRow("sorted-duplicate") << (QList<int>() << 1 << 2 << 2 << 3) << 2 << 1;

   566 }

   567 

   568 void tst_QAlgorithms::test_qLowerBound()

   569 {

   570     QFETCH(QList<int>, data);

   571     QFETCH(int, resultValue);

   572     QFETCH(int, resultIndex);

   573 

   574 

   575     QCOMPARE(qLowerBound(data.constBegin(), data.constEnd(), resultValue), data.constBegin() + resultIndex);

   576     QCOMPARE(qLowerBound(data.begin(), data.end(), resultValue), data.begin() + resultIndex);

   577     QCOMPARE(qLowerBound(data, resultValue), data.constBegin() + resultIndex);

   578     QCOMPARE(qLowerBound(data.constBegin(), data.constEnd(), resultValue, qLess<int>()), data.constBegin() + resultIndex);

   579 }

   580 

   581 void tst_QAlgorithms::test_qUpperBound_data()

   582 {

   583     QTest::addColumn<QList<int> >("data");

   584     QTest::addColumn<int>("resultValue");

   585     QTest::addColumn<int>("resultIndex");

   586 

   587     QTest::newRow("sorted-duplicate") << (QList<int>() << 1 << 2 << 2 << 3) << 2 << 3;

   588 }

   589 

   590 void tst_QAlgorithms::test_qUpperBound()

   591 {

   592     QFETCH(QList<int>, data);

   593     QFETCH(int, resultValue);

   594     QFETCH(int, resultIndex);

   595 

   596     QCOMPARE(qUpperBound(data.constBegin(), data.constEnd(), resultValue), data.constBegin() + resultIndex);

   597     QCOMPARE(qUpperBound(data.begin(), data.end(), resultValue), data.begin() + resultIndex);

   598     QCOMPARE(qUpperBound(data, resultValue), data.constBegin() + resultIndex);

   599     QCOMPARE(qUpperBound(data.constBegin(), data.constEnd(), resultValue, qLess<int>()), data.constBegin() + resultIndex);

   600 }

   601 

   602 void tst_QAlgorithms::test_qBinaryFind_data()

   603 {

   604     QTest::addColumn<QList<int> >("data");

   605     QTest::addColumn<int>("resultValue");

   606 

   607     QTest::newRow("sorted-duplicate") << (QList<int>() << 1 << 2 << 2 << 3) << 2;

   608 }

   609 

   610 void tst_QAlgorithms::test_qBinaryFind()

   611 {

   612     QFETCH(QList<int>, data);

   613     QFETCH(int, resultValue);

   614 

   615     QCOMPARE(*qBinaryFind(data.constBegin(), data.constEnd(), resultValue), resultValue);

   616     QCOMPARE(*qBinaryFind(data.begin(), data.end(), resultValue), resultValue);

   617     QCOMPARE(*qBinaryFind(data, resultValue), resultValue);

   618     QCOMPARE(*qBinaryFind(data.constBegin(), data.constEnd(), resultValue, qLess<int>()), resultValue);

   619 }

   620 

   621 void tst_QAlgorithms::qBinaryFindOneEntry()

   622 {

   623     QList<int> list;

   624     list << 2;

   625 

   626     QVERIFY(::qBinaryFind(list.constBegin(), list.constEnd(), 2) != list.constEnd());

   627 }

   628 

   629 

   630 void tst_QAlgorithms::sortAPItest()

   631 {

   632     QVector<int> testVector = generateData<int>("Random", 101);

   633     qSort(testVector);

   634     QVERIFY(isSorted(testVector));

   635     qSort(testVector.begin(), testVector.end());

   636     QVERIFY(isSorted(testVector));

   637     qSort(testVector.begin(), testVector.end(), qLess<int>());

   638     QVERIFY(isSorted(testVector));

   639 

   640     testVector = generateData<int>("Random", 71);

   641     qStableSort(testVector);

   642     QVERIFY(isSorted(testVector));

   643     qStableSort(testVector.begin(), testVector.end());

   644     QVERIFY(isSorted(testVector));

   645     qStableSort(testVector.begin(), testVector.end(), qLess<int>());

   646     QVERIFY(isSorted(testVector));

   647 

   648     QList<int> testList = generateData<int>("Random", 101).toList();

   649     qSort(testList);

   650     QVERIFY(isSorted(testList));

   651     qSort(testList.begin(), testList.end());

   652     QVERIFY(isSorted(testList));

   653     qSort(testList.begin(), testList.end(), qLess<int>());

   654     QVERIFY(isSorted(testList));

   655 

   656     testList = generateData<int>("Random", 71).toList();

   657     qStableSort(testList);

   658     QVERIFY(isSorted(testList));

   659     qStableSort(testList.begin(), testList.end());

   660     QVERIFY(isSorted(testList));

   661     qStableSort(testList.begin(), testList.end(), qLess<int>());

   662     QVERIFY(isSorted(testList));

   663 }

   664 

   665 

   666 class StableSortTest

   667 {

   668 public:

   669     StableSortTest(){};

   670     StableSortTest(int Major, int Minor) : Major(Major), Minor(Minor) {}

   671     bool operator<(const StableSortTest &other) const {return (Major < other.Major); }

   672     bool testMinor(const  StableSortTest &other) const {return  Minor < other.Minor; }

   673 

   674 int Major;

   675 int Minor;

   676 };

   677 

   678 ostream &operator<<(ostream &out, const StableSortTest& obj)  { out << obj.Major << "-" << obj.Minor; return out; }

   679 

   680 QVector<StableSortTest> createStableTestVector()

   681 {

   682     QVector<StableSortTest> stableTestVector;

   683 	for (int i=500; i>=0; --i) {

   684         for (int j=0; j<10; ++j) {

   685             stableTestVector.append(StableSortTest(i, j));

   686         }

   687     }

   688     return stableTestVector;

   689 }

   690 

   691 template <typename ContainerType, typename LessThan>

   692 bool isStableSorted(ContainerType &container, LessThan lessThan)

   693 {

   694     for (int i=0; i < container.count() - 1; ++i) {

   695         //not sorted?

   696         if (lessThan(container.at(i + 1), container.at(i)))

   697             return false;

   698         // equal?

   699         if (lessThan(container.at(i),  container.at(i + 1)))

   700             continue;

   701         // minor version?

   702         if(container.at(i + 1).testMinor(container.at(i)))

   703             return false;

   704     }

   705     return true;

   706 }

   707 

   708 void tst_QAlgorithms::stableSortTest()

   709 {

   710     // Selftests:

   711     {

   712         QVector<StableSortTest> stableTestVector = createStableTestVector();

   713         qSort(stableTestVector.begin(), stableTestVector.end(), qLess<StableSortTest>());

   714         QVERIFY(isSorted(stableTestVector, qLess<StableSortTest>()));

   715         QVERIFY(!isStableSorted(stableTestVector, qLess<StableSortTest>()));

   716     }

   717     {

   718         QVector<StableSortTest> stableTestVector = createStableTestVector();

   719         qSort(stableTestVector.begin(), stableTestVector.end(), qGreater<StableSortTest>());

   720         QVERIFY(isSorted(stableTestVector, qGreater<StableSortTest>()));

   721         QVERIFY(!isStableSorted(stableTestVector, qGreater<StableSortTest>()));

   722     }

   723     {

   724         QVector<StableSortTest> stableTestVector = createStableTestVector();

   725         qSort(stableTestVector.begin(), stableTestVector.end(), qGreater<StableSortTest>());

   726         QVERIFY(!isSorted(stableTestVector, qLess<StableSortTest>()));

   727         QVERIFY(!isStableSorted(stableTestVector, qGreater<StableSortTest>()));

   728     }

   729 

   730 

   731     // Stable sort with qLess

   732     {

   733         QVector<StableSortTest> stableTestVector = createStableTestVector();

   734         std::stable_sort(stableTestVector.begin(), stableTestVector.end(), qLess<StableSortTest>());

   735         QVERIFY(isSorted(stableTestVector, qLess<StableSortTest>()));

   736         QVERIFY(isStableSorted(stableTestVector, qLess<StableSortTest>()));

   737     }

   738     {

   739         QVector<StableSortTest> stableTestVector = createStableTestVector();

   740         qStableSort(stableTestVector.begin(), stableTestVector.end(), qLess<StableSortTest>());

   741         QVERIFY(isSorted(stableTestVector, qLess<StableSortTest>()));

   742         QVERIFY(isStableSorted(stableTestVector, qLess<StableSortTest>()));

   743     }

   744 

   745     // Stable sort with qGreater

   746     {

   747         QVector<StableSortTest> stableTestVector = createStableTestVector();

   748         std::stable_sort(stableTestVector.begin(), stableTestVector.end(), qGreater<StableSortTest>());

   749         QVERIFY(isSorted(stableTestVector, qGreater<StableSortTest>()));

   750         QVERIFY(isStableSorted(stableTestVector, qGreater<StableSortTest>()));

   751     }

   752 

   753     {

   754         QVector<StableSortTest> stableTestVector = createStableTestVector();

   755         qStableSort(stableTestVector.begin(), stableTestVector.end(), qGreater<StableSortTest>());

   756         QVERIFY(isSorted(stableTestVector, qGreater<StableSortTest>()));

   757         QVERIFY(isStableSorted(stableTestVector, qGreater<StableSortTest>()));

   758     }

   759 }

   760 

   761 Q_DECLARE_METATYPE(QVector<int>)

   762 

   763 void tst_QAlgorithms::stableSortCorrectnessTest_data()

   764 {

   765     const int dataSize = 1000;

   766     QTest::addColumn<QVector<int> >("unsorted");

   767     QTest::newRow("From documentation") << (QVector<int>() << 33 << 12 << 68 << 6 << 12);

   768     QTest::newRow("Equal") << (generateData<int>("Equal", dataSize));

   769     QTest::newRow("Ascending") << (generateData<int>("Ascending", dataSize));

   770     QTest::newRow("Descending") << (generateData<int>("Descending", dataSize));

   771     QTest::newRow("Duplicates") << (generateData<int>("Duplicates", dataSize));

   772     QTest::newRow("Almost Sorted") << (generateData<int>("Almost Sorted", dataSize));

   773     QTest::newRow("Random") << (generateData<int>("Random", dataSize));

   774 }

   775 

   776 void tst_QAlgorithms::stableSortCorrectnessTest()

   777 {

   778     QFETCH(QVector<int>, unsorted);

   779 

   780     QVector<int> sorted = unsorted;

   781     qStableSort(sorted.begin(), sorted.end());

   782 

   783     // Verify that sorted contains the same numbers as unsorted.

   784     foreach(int value, unsorted) {

   785         QVERIFY(sorted.contains(value));

   786         int unsortedCount = 0;

   787         qCount(unsorted.begin(), unsorted.end(), value, unsortedCount);

   788         int sortedCount = 0;

   789         qCount(sorted.begin(), sorted.end(), value, sortedCount);

   790         QCOMPARE(sortedCount, unsortedCount);

   791     }

   792 

   793     QVERIFY(isSorted(sorted));

   794 }

   795 

   796 void tst_QAlgorithms::convenienceAPI()

   797 {

   798     // Compile-test for QAlgorithm convenience functions.

   799     QList<int> list, list2;

   800 

   801     qCopy(list.begin(), list.end(), list2.begin());

   802     qCopyBackward(list.begin(), list.end(), list2.begin());

   803     qEqual(list.begin(), list.end(), list2.begin());

   804 

   805     qFill(list, 1);

   806     qFill(list.begin(), list.end(), 1);

   807 

   808     qFind(list, 1);

   809     qFind(list.begin(), list.end(), 1);

   810 

   811     int count1 = 0 , count2 = 0, count3 = 0;

   812     qCount(list, 1, count1);

   813     qCount(list.begin(), list.end(), 1, count2);

   814     QCOMPARE(count1, count2);

   815     QCOMPARE(count2, count3);

   816 

   817     qSort(list);

   818     qSort(list.begin(), list.end());

   819     qSort(list.begin(), list.end(), qLess<int>());

   820 

   821     qStableSort(list);

   822     qStableSort(list.begin(), list.end());

   823     qStableSort(list.begin(), list.end(), qLess<int>());

   824 

   825     qLowerBound(list, 1);;

   826     qLowerBound(list.begin(), list.end(),  1);

   827     qLowerBound(list.begin(), list.end(), 1, qLess<int>());

   828 

   829     qUpperBound(list, 1);

   830     qUpperBound(list.begin(), list.end(),  1);

   831     qUpperBound(list.begin(), list.end(), 1, qLess<int>());

   832 

   833     qBinaryFind(list, 1);

   834     qBinaryFind(list.begin(), list.end(),  1);

   835     qBinaryFind(list.begin(), list.end(), 1, qLess<int>());

   836 

   837     QList<int *> pointerList;

   838     qDeleteAll(pointerList);

   839     qDeleteAll(pointerList.begin(), pointerList.end());

   840 }

   841 

   842 template <typename DataType>

   843 class HeapSortHelper

   844 {

   845 public:

   846     void operator()(QVector<DataType> list)

   847     {

   848         ::qHeapSort(list);

   849     }

   850 };

   851 

   852 template <typename DataType>

   853 class BubbleSortHelper

   854 {

   855 public:

   856     void operator()(QVector<DataType> list)

   857     {

   858         ::qBubbleSort(list);

   859     }

   860 };

   861 

   862 template <typename DataType>

   863 class QuickSortHelper

   864 {

   865 public:

   866     void operator()(QVector<DataType> list)

   867     {

   868         ::qSort(list);

   869     }

   870 };

   871 

   872 template <typename DataType>

   873 class StableSortHelper

   874 {

   875 public:

   876     void operator()(QVector<DataType> list)

   877     {

   878         ::qStableSort(list);

   879     }

   880 };

   881 

   882 template <typename DataType>

   883 class StlSortHelper

   884 {

   885 public:

   886     void operator()(QVector<DataType> list)

   887     {

   888         std::sort(list.begin(), list.end());

   889     }

   890 };

   891 

   892 template <typename DataType>

   893 class StlStableSortHelper

   894 {

   895 public:

   896     void operator()(QVector<DataType> list)

   897     {

   898         std::stable_sort(list.begin(), list.end());

   899     }

   900 };

   901 

   902 #if Q_TEST_PERFORMANCE

   903 void tst_QAlgorithms::performance()

   904 {

   905     cout << endl << "Quick sort" << endl;

   906     testAlgorithm<QuickSortHelper<TestInt>, TestInt>(QuickSortHelper<TestInt>(), dataSetTypes);

   907     cout << endl << "stable sort" << endl;

   908     testAlgorithm<StableSortHelper<TestInt>, TestInt>(StableSortHelper<TestInt>(), dataSetTypes);

   909     cout << endl << "std::sort" << endl;

   910     testAlgorithm<StlSortHelper<TestInt>, TestInt>(StlSortHelper<TestInt>(), dataSetTypes);

   911     cout << endl << "std::stable_sort" << endl;

   912     testAlgorithm<StlStableSortHelper<TestInt>, TestInt>(StlStableSortHelper<TestInt>(), dataSetTypes);

   913     cout << "Heap sort" << endl;

   914     testAlgorithm<HeapSortHelper<TestInt>, TestInt>(HeapSortHelper<TestInt>(), dataSetTypes);

   915     cout << endl << "Bubble sort" << endl;

   916     testAlgorithm<BubbleSortHelper<TestInt>, TestInt>(BubbleSortHelper<TestInt>(), dataSetTypes);

   917 /*

   918     cout << endl << "Sorting lists of ints" << endl;

   919     cout << "Heap sort" << endl;

   920     testAlgorithm<HeapSortHelper<int>, int>(HeapSortHelper<int>(), dataSetTypes);

   921     cout << endl << "Quick sort" << endl;

   922     testAlgorithm<QuickSortHelper<int>, int>(QuickSortHelper<int>(), dataSetTypes);

   923     cout << endl << "std::sort" << endl;

   924     testAlgorithm<StlSortHelper<int>, int>(StlSortHelper<int>(), dataSetTypes);

   925     cout << endl << "std::stable_sort" << endl;

   926     testAlgorithm<StlStableSortHelper<int>, int>(StlStableSortHelper<int>(), dataSetTypes);

   927     cout << endl << "Bubble sort" << endl;

   928     testAlgorithm<BubbleSortHelper<int>, int>(BubbleSortHelper<int>(), dataSetTypes);

   929 */

   930 }

   931 #endif

   932 

   933 void tst_QAlgorithms::qCountIterators() const

   934 {

   935     QList<int> list;

   936     list << 3 << 3 << 6 << 6 << 6 << 8;

   937 

   938     {

   939         int countOf7 = 0;

   940         ::qCount(list.begin(), list.end(), 7, countOf7);

   941         QCOMPARE(countOf7, 0);

   942     }

   943 

   944     {

   945         int countOf3 = 0;

   946         ::qCount(list.begin(), list.end(), 3, countOf3);

   947         QCOMPARE(countOf3, 2);

   948     }

   949 

   950     {

   951         int countOf6 = 0;

   952         ::qCount(list.begin(), list.end(), 6, countOf6);

   953         QCOMPARE(countOf6, 3);

   954     }

   955 

   956     {

   957         int countOf8 = 0;

   958         ::qCount(list.begin(), list.end(), 8, countOf8);

   959         QCOMPARE(countOf8, 1);

   960     }

   961 

   962     /* Check that we add to the count, not set it. */

   963     {

   964         int countOf8 = 5;

   965         ::qCount(list.begin(), list.end(), 8, countOf8);

   966         QCOMPARE(countOf8, 6);

   967     }

   968 }

   969 

   970 void tst_QAlgorithms::qCountContainer() const

   971 {

   972     QList<int> list;

   973     list << 3 << 3 << 6 << 6 << 6 << 8;

   974 

   975     {

   976         int countOf7 = 0;

   977         ::qCount(list, 7, countOf7);

   978         QCOMPARE(countOf7, 0);

   979     }

   980 

   981     {

   982         int countOf3 = 0;

   983         ::qCount(list, 3, countOf3);

   984         QCOMPARE(countOf3, 2);

   985     }

   986 

   987     {

   988         int countOf6 = 0;

   989         ::qCount(list, 6, countOf6);

   990         QCOMPARE(countOf6, 3);

   991     }

   992 

   993     {

   994         int countOf8 = 0;

   995         ::qCount(list, 8, countOf8);

   996         QCOMPARE(countOf8, 1);

   997     }

   998 

   999     /* Check that we add to the count, not set it. */

  1000     {

  1001         int countOf8 = 5;

  1002         ::qCount(list, 8, countOf8);

  1003         QCOMPARE(countOf8, 6);

  1004     }

  1005 }

  1006 

  1007 class RAI

  1008 {

  1009   public:

  1010     RAI(int searched = 5, int hidePos = 4, int len = 10)

  1011         : curPos_(0)

  1012         , length_(len)

  1013         , searchedVal_(searched)

  1014         , searchedValPos_(hidePos)

  1015     {

  1016     }

  1017 

  1018     int at(int pos) const

  1019     {

  1020         if (pos == searchedValPos_) {

  1021             return searchedVal_;

  1022         }

  1023         else if (pos < searchedValPos_) {

  1024             return searchedVal_ - 1;

  1025         }

  1026 

  1027         return searchedVal_ + 1;

  1028     }

  1029 

  1030     RAI begin() const

  1031     {

  1032         RAI rai = *this;

  1033         rai.setCurPos(0);

  1034         return rai;

  1035     }

  1036 

  1037     RAI end() const

  1038     {

  1039         RAI rai = *this;

  1040         rai.setCurPos(length_);

  1041         return rai;

  1042     }

  1043 

  1044     int pos() const

  1045     {

  1046         return curPos();

  1047     }

  1048 

  1049     int size() const

  1050     {

  1051         return length_;

  1052     }

  1053 

  1054     RAI operator+(int i) const

  1055     {

  1056         RAI rai = *this;

  1057         rai.setCurPos( rai.curPos() + i );

  1058         if (rai.curPos() > length_) {

  1059             rai.setCurPos(length_);

  1060         }

  1061         return rai;

  1062     }

  1063 

  1064     RAI operator-(int i) const

  1065     {

  1066         RAI rai = *this;

  1067         rai.setCurPos( rai.curPos() - i );

  1068         if (rai.curPos() < 0) {

  1069             rai.setCurPos(0);

  1070         }

  1071         return rai;

  1072     }

  1073 

  1074     int operator-(const RAI& it) const

  1075     {

  1076         return curPos() - it.curPos();

  1077     }

  1078 

  1079     RAI& operator+=(int i)

  1080     {

  1081         setCurPos( curPos() + i );

  1082         if (curPos() > length_) {

  1083             setCurPos(length_);

  1084         }

  1085         return *this;

  1086     }

  1087 

  1088     RAI& operator-=(int i)

  1089     {

  1090         setCurPos( curPos() - i);

  1091         if (curPos() < 0) {

  1092             setCurPos(0);

  1093         }

  1094         return *this;

  1095     }

  1096 

  1097     RAI& operator++()

  1098     {

  1099         if (curPos() < length_) {

  1100             setCurPos( curPos() + 1 );

  1101         }

  1102         return *this;

  1103     }

  1104 

  1105     RAI operator++(int)

  1106     {

  1107         RAI rai = *this;

  1108 

  1109         if (curPos() < length_) {

  1110             setCurPos( curPos() + 1 );

  1111         }

  1112 

  1113         return rai;

  1114     }

  1115 

  1116     RAI& operator--()

  1117     {

  1118         if (curPos() > 0) {

  1119             setCurPos( curPos() - 1 );

  1120         }

  1121         return *this;

  1122     }

  1123 

  1124     RAI operator--(int)

  1125     {

  1126         RAI rai = *this;

  1127 

  1128         if (curPos() > 0) {

  1129             setCurPos( curPos() - 1 );

  1130         }

  1131 

  1132         return rai;

  1133     }

  1134