| /**************************************************************************** |
| ** |
| ** Copyright (C) 2016 The Qt Company Ltd. |
| ** Contact: https://www.qt.io/licensing/ |
| ** |
| ** This file is part of the test suite of the Qt Toolkit. |
| ** |
| ** $QT_BEGIN_LICENSE:GPL-EXCEPT$ |
| ** Commercial License Usage |
| ** Licensees holding valid commercial Qt licenses may use this file in |
| ** accordance with the commercial license agreement provided with the |
| ** Software or, alternatively, in accordance with the terms contained in |
| ** a written agreement between you and The Qt Company. For licensing terms |
| ** and conditions see https://www.qt.io/terms-conditions. For further |
| ** information use the contact form at https://www.qt.io/contact-us. |
| ** |
| ** GNU General Public License Usage |
| ** Alternatively, this file may be used under the terms of the GNU |
| ** General Public License version 3 as published by the Free Software |
| ** Foundation with exceptions as appearing in the file LICENSE.GPL3-EXCEPT |
| ** included in the packaging of this file. Please review the following |
| ** information to ensure the GNU General Public License requirements will |
| ** be met: https://www.gnu.org/licenses/gpl-3.0.html. |
| ** |
| ** $QT_END_LICENSE$ |
| ** |
| ****************************************************************************/ |
| |
| #include "../../../../../src/corelib/tools/qalgorithms.h" |
| #include <QtTest/QtTest> |
| |
| #include <iostream> |
| #include <iomanip> |
| #include <sstream> |
| #include <iterator> |
| #include <algorithm> |
| #include <qalgorithms.h> |
| #include <QStringList> |
| #include <QString> |
| #include <QRandomGenerator> |
| #include <QVector> |
| |
| #define Q_TEST_PERFORMANCE 0 |
| |
| using namespace std; |
| |
| class tst_QAlgorithms : public QObject |
| { |
| Q_OBJECT |
| private slots: |
| void swap(); |
| void swap2(); |
| void convenienceAPI(); |
| |
| #if QT_DEPRECATED_SINCE(5, 2) |
| void test_qLowerBound_data(); |
| void test_qLowerBound(); |
| void test_qUpperBound_data(); |
| void test_qUpperBound(); |
| void test_qBinaryFind_data(); |
| void test_qBinaryFind(); |
| void qBinaryFindOneEntry(); |
| void sortEmptyList(); |
| void sortedList(); |
| void sortAPItest(); |
| void stableSortTest(); |
| void stableSortCorrectnessTest_data(); |
| void stableSortCorrectnessTest(); |
| void convenienceAPI_deprecated(); |
| void qCountIterators() const; |
| void qCountContainer() const; |
| void binaryFindOnLargeContainer() const; |
| |
| #if Q_TEST_PERFORMANCE |
| void performance(); |
| #endif |
| |
| #endif // QT_DEPRECATED_SINCE(5, 2) |
| |
| void popCount08_data() { popCount_data_impl(sizeof(quint8 )); } |
| void popCount16_data() { popCount_data_impl(sizeof(quint16)); } |
| void popCount32_data() { popCount_data_impl(sizeof(quint32)); } |
| void popCount64_data() { popCount_data_impl(sizeof(quint64)); } |
| void popCount08() { popCount_impl<quint8 >(); } |
| void popCount16() { popCount_impl<quint16>(); } |
| void popCount32() { popCount_impl<quint32>(); } |
| void popCount64() { popCount_impl<quint64>(); } |
| |
| void countTrailing08_data() { countTrailing_data_impl(sizeof(quint8 )); } |
| void countTrailing16_data() { countTrailing_data_impl(sizeof(quint16)); } |
| void countTrailing32_data() { countTrailing_data_impl(sizeof(quint32)); } |
| void countTrailing64_data() { countTrailing_data_impl(sizeof(quint64)); } |
| void countTrailing08() { countTrailing_impl<quint8 >(); } |
| void countTrailing16() { countTrailing_impl<quint16>(); } |
| void countTrailing32() { countTrailing_impl<quint32>(); } |
| void countTrailing64() { countTrailing_impl<quint64>(); } |
| |
| void countLeading08_data() { countLeading_data_impl(sizeof(quint8 )); } |
| void countLeading16_data() { countLeading_data_impl(sizeof(quint16)); } |
| void countLeading32_data() { countLeading_data_impl(sizeof(quint32)); } |
| void countLeading64_data() { countLeading_data_impl(sizeof(quint64)); } |
| void countLeading08() { countLeading_impl<quint8 >(); } |
| void countLeading16() { countLeading_impl<quint16>(); } |
| void countLeading32() { countLeading_impl<quint32>(); } |
| void countLeading64() { countLeading_impl<quint64>(); } |
| |
| private: |
| void popCount_data_impl(size_t sizeof_T_Int); |
| template <typename T_Int> |
| void popCount_impl(); |
| |
| void countTrailing_data_impl(size_t sizeof_T_Int); |
| template <typename T_Int> |
| void countTrailing_impl(); |
| |
| void countLeading_data_impl(size_t sizeof_T_Int); |
| template <typename T_Int> |
| void countLeading_impl(); |
| }; |
| |
| #if QT_DEPRECATED_SINCE(5, 2) |
| |
| class TestInt |
| { |
| public: |
| TestInt(int number) :m_number(number) {} ; |
| TestInt() : m_number(0) {}; |
| bool operator<(const TestInt &other) const { ++TestInt::lessThanRefCount; return (m_number < other.m_number); } |
| int m_number; |
| static long int lessThanRefCount; |
| }; |
| |
| long int TestInt::lessThanRefCount; |
| |
| |
| QStringList dataSetTypes = QStringList() << "Random" << "Ascending" |
| << "Descending" << "Equal" << "Duplicates" << "Almost Sorted" ; |
| |
| template <typename DataType> |
| QVector<DataType> generateData(QString dataSetType, const int length) |
| { |
| QVector<DataType> container; |
| if (dataSetType == "Random") { |
| for (int i = 0; i < length; ++i) |
| container.append(QRandomGenerator::global()->generate()); |
| } else if (dataSetType == "Ascending") { |
| for (int i = 0; i < length; ++i) |
| container.append(i); |
| } else if (dataSetType == "Descending") { |
| for (int i = 0; i < length; ++i) |
| container.append(length - i); |
| } else if (dataSetType == "Equal") { |
| for (int i = 0; i < length; ++i) |
| container.append(43); |
| } else if (dataSetType == "Duplicates") { |
| for (int i = 0; i < length; ++i) |
| container.append(i % 10); |
| } else if (dataSetType == "Almost Sorted") { |
| for (int i = 0; i < length; ++i) |
| container.append(i); |
| for (int i = 0; i <= length / 10; ++i) { |
| const int iswap = i * 9; |
| DataType tmp = container.at(iswap); |
| container[iswap] = container.at(iswap + 1); |
| container[iswap + 1] = tmp; |
| } |
| } |
| return container; |
| } |
| |
| struct ResultSet |
| { |
| int numSorts; |
| long int lessThanRefCount; |
| }; |
| |
| |
| template <typename ContainerType, typename Algorithm> |
| ResultSet testRun(ContainerType &container, Algorithm &algorithm, int millisecs) |
| { |
| TestInt::lessThanRefCount = 0; |
| int count = 0; |
| QElapsedTimer t; |
| t.start(); |
| while(t.elapsed() < millisecs) { |
| ++count; |
| algorithm(container); |
| } |
| ResultSet result; |
| result.numSorts = count; |
| result.lessThanRefCount = TestInt::lessThanRefCount; |
| return result; |
| } |
| |
| template <typename ContainerType, typename LessThan> |
| bool isSorted(ContainerType &container, LessThan lessThan) |
| { |
| for (int i=0; i < container.count() - 1; ++i) |
| if (lessThan(container.at(i+1), container.at(i))) { |
| return false; |
| } |
| return true; |
| } |
| |
| template <typename ContainerType> |
| bool isSorted(ContainerType &container) |
| { |
| return isSorted(container, qLess<typename ContainerType::value_type>()); |
| } |
| |
| |
| #if Q_TEST_PERFORMANCE |
| void printHeader(QStringList &headers) |
| { |
| cout << setw(10) << setiosflags(ios_base::left) << " "; |
| for (int h = 0; h < headers.count(); ++h) { |
| cout << setw(20) << setiosflags(ios_base::left) << headers.at(h).toLatin1().constData(); |
| } |
| cout << Qt::endl; |
| } |
| |
| template <typename ContainerType> |
| void print(ContainerType testContainer) |
| { |
| typedef typename ContainerType::value_type T; |
| |
| foreach(T value, testContainer) { |
| cout << value << " "; |
| } |
| |
| cout << Qt::endl; |
| } |
| |
| template <typename Algorithm, typename DataType> |
| QList<ResultSet> testAlgorithm(Algorithm &algorithm, QStringList dataSetTypes, int size, int time) |
| { |
| QList<ResultSet> results; |
| foreach(QString dataSetType, dataSetTypes) { |
| QVector<DataType> container = generateData<DataType>(dataSetType, size); |
| results.append(testRun(container, algorithm, time)); |
| if (!isSorted(container)) |
| qWarning("%s: container is not sorted after test", Q_FUNC_INFO); |
| } |
| return results; |
| } |
| |
| template <typename Algorithm, typename DataType> |
| void testAlgorithm(Algorithm algorithm, QStringList &dataSetTypes) |
| { |
| QList<int> sizes = QList<int>() << 5 << 15 << 35 << 70 << 200 << 1000 << 10000; |
| printHeader(dataSetTypes); |
| for (int s = 0; s < sizes.count(); ++s){ |
| cout << setw(10) << setiosflags(ios_base::left)<< sizes.at(s); |
| QList<ResultSet> results = |
| testAlgorithm<Algorithm, DataType>(algorithm, dataSetTypes, sizes.at(s), 100); |
| foreach(ResultSet result, results) { |
| stringstream numSorts; |
| numSorts << setiosflags(ios_base::left) << setw(10) << result.numSorts; |
| stringstream lessThan; |
| lessThan << setiosflags(ios_base::left) << setw(10) << result.lessThanRefCount / result.numSorts; |
| cout << numSorts.str() << lessThan.str(); |
| } |
| cout << Qt::endl; |
| } |
| } |
| #endif |
| |
| #endif // QT_DEPRECATED_SINCE(5, 2) |
| |
| void tst_QAlgorithms::swap() |
| { |
| { |
| int a = 1, b = 2; |
| qSwap(a, b); |
| QVERIFY(a == 2); |
| QVERIFY(b == 1); |
| |
| qSwap(a, a); |
| QVERIFY(a == 2); |
| QVERIFY(b == 1); |
| |
| qSwap(b, b); |
| QVERIFY(a == 2); |
| QVERIFY(b == 1); |
| |
| qSwap(a, b); |
| QVERIFY(a == 1); |
| QVERIFY(b == 2); |
| |
| qSwap(b, a); |
| QVERIFY(a == 2); |
| QVERIFY(b == 1); |
| } |
| |
| { |
| double a = 1.0, b = 2.0; |
| qSwap(a, b); |
| QVERIFY(a == 2.0); |
| QVERIFY(b == 1.0); |
| |
| qSwap(a, a); |
| QVERIFY(a == 2.0); |
| QVERIFY(b == 1.0); |
| |
| qSwap(b, b); |
| QVERIFY(a == 2.0); |
| QVERIFY(b == 1.0); |
| |
| qSwap(a, b); |
| QVERIFY(a == 1.0); |
| QVERIFY(b == 2.0); |
| |
| qSwap(b, a); |
| QVERIFY(a == 2.0); |
| QVERIFY(b == 1.0); |
| } |
| |
| { |
| QString a = "1", b = "2"; |
| qSwap(a, b); |
| QCOMPARE(a, QLatin1String("2")); |
| QCOMPARE(b, QLatin1String("1")); |
| |
| qSwap(a, a); |
| QCOMPARE(a, QLatin1String("2")); |
| QCOMPARE(b, QLatin1String("1")); |
| |
| qSwap(b, b); |
| QCOMPARE(a, QLatin1String("2")); |
| QCOMPARE(b, QLatin1String("1")); |
| |
| qSwap(a, b); |
| QCOMPARE(a, QLatin1String("1")); |
| QCOMPARE(b, QLatin1String("2")); |
| |
| qSwap(b, a); |
| QCOMPARE(a, QLatin1String("2")); |
| QCOMPARE(b, QLatin1String("1")); |
| } |
| |
| { |
| void *a = 0, *b = 0; |
| qSwap(a, b); |
| } |
| |
| { |
| const void *a = 0, *b = 0; |
| qSwap(a, b); |
| } |
| |
| { |
| QString *a = 0, *b = 0; |
| qSwap(a, b); |
| } |
| |
| { |
| const QString *a = 0, *b = 0; |
| qSwap(a, b); |
| } |
| |
| { |
| QString **a = 0, **b = 0; |
| qSwap(a, b); |
| } |
| |
| { |
| const QString **a = 0, **b = 0; |
| qSwap(a, b); |
| } |
| |
| { |
| QString * const *a = 0, * const *b = 0; |
| qSwap(a, b); |
| } |
| |
| { |
| const QString * const *a = 0, * const *b = 0; |
| qSwap(a, b); |
| } |
| } |
| |
| namespace SwapTest { |
| struct ST { int i; int j; }; |
| void swap(ST &a, ST &b) { |
| a.i = b.j; |
| b.i = a.j; |
| } |
| } |
| |
| void tst_QAlgorithms::swap2() |
| { |
| { |
| #ifndef QT_NO_SQL |
| //check the namespace lookup works correctly |
| SwapTest::ST a = { 45, 65 }; |
| SwapTest::ST b = { 48, 68 }; |
| qSwap(a, b); |
| QCOMPARE(a.i, 68); |
| QCOMPARE(b.i, 65); |
| #endif |
| } |
| } |
| |
| void tst_QAlgorithms::convenienceAPI() |
| { |
| // Compile-test for QAlgorithm convenience functions. |
| |
| QList<int *> pointerList; |
| qDeleteAll(pointerList); |
| qDeleteAll(pointerList.begin(), pointerList.end()); |
| } |
| |
| #if QT_DEPRECATED_SINCE(5, 2) |
| |
| void tst_QAlgorithms::sortEmptyList() |
| { |
| // Only test if it crashes |
| QStringList stringList; |
| stringList.sort(); |
| QVERIFY(true); |
| } |
| |
| void tst_QAlgorithms::sortedList() |
| { |
| QList<int> list; |
| list << 4 << 3 << 6; |
| |
| ::qSort(list.begin(), list.end()); |
| |
| QCOMPARE(list.count(), 3); |
| QCOMPARE(list.at(0), 3); |
| QCOMPARE(list.at(1), 4); |
| QCOMPARE(list.at(2), 6); |
| |
| list.insert(qUpperBound(list.begin(), list.end(), 5), 5); |
| list.insert(qUpperBound(list.begin(), list.end(), 1), 1); |
| list.insert(qUpperBound(list.begin(), list.end(), 8), 8); |
| |
| QCOMPARE(list.count(), 6); |
| QCOMPARE(list.at(0), 1); |
| QCOMPARE(list.at(1), 3); |
| QCOMPARE(list.at(2), 4); |
| QCOMPARE(list.at(3), 5); |
| QCOMPARE(list.at(4), 6); |
| QCOMPARE(list.at(5), 8); |
| } |
| |
| |
| void tst_QAlgorithms::test_qLowerBound_data() |
| { |
| QTest::addColumn<QList<int> >("data"); |
| QTest::addColumn<int>("resultValue"); |
| QTest::addColumn<int>("resultIndex"); |
| |
| QTest::newRow("sorted-duplicate") << (QList<int>() << 1 << 2 << 2 << 3) << 2 << 1; |
| } |
| |
| void tst_QAlgorithms::test_qLowerBound() |
| { |
| QFETCH(QList<int>, data); |
| QFETCH(int, resultValue); |
| QFETCH(int, resultIndex); |
| |
| |
| QCOMPARE(qLowerBound(data.constBegin(), data.constEnd(), resultValue), data.constBegin() + resultIndex); |
| QCOMPARE(qLowerBound(data.begin(), data.end(), resultValue), data.begin() + resultIndex); |
| QCOMPARE(qLowerBound(data, resultValue), data.constBegin() + resultIndex); |
| QCOMPARE(qLowerBound(data.constBegin(), data.constEnd(), resultValue, qLess<int>()), data.constBegin() + resultIndex); |
| } |
| |
| void tst_QAlgorithms::test_qUpperBound_data() |
| { |
| QTest::addColumn<QList<int> >("data"); |
| QTest::addColumn<int>("resultValue"); |
| QTest::addColumn<int>("resultIndex"); |
| |
| QTest::newRow("sorted-duplicate") << (QList<int>() << 1 << 2 << 2 << 3) << 2 << 3; |
| } |
| |
| void tst_QAlgorithms::test_qUpperBound() |
| { |
| QFETCH(QList<int>, data); |
| QFETCH(int, resultValue); |
| QFETCH(int, resultIndex); |
| |
| QCOMPARE(qUpperBound(data.constBegin(), data.constEnd(), resultValue), data.constBegin() + resultIndex); |
| QCOMPARE(qUpperBound(data.begin(), data.end(), resultValue), data.begin() + resultIndex); |
| QCOMPARE(qUpperBound(data, resultValue), data.constBegin() + resultIndex); |
| QCOMPARE(qUpperBound(data.constBegin(), data.constEnd(), resultValue, qLess<int>()), data.constBegin() + resultIndex); |
| } |
| |
| void tst_QAlgorithms::test_qBinaryFind_data() |
| { |
| QTest::addColumn<QList<int> >("data"); |
| QTest::addColumn<int>("resultValue"); // -42 means not found |
| |
| QTest::newRow("sorted-duplicate") << (QList<int>() << 1 << 2 << 2 << 3) << 2; |
| QTest::newRow("sorted-end") << (QList<int>() << -5 << -2 << 0 << 8) << 8; |
| QTest::newRow("sorted-beginning") << (QList<int>() << -5 << -2 << 0 << 8) << -5; |
| QTest::newRow("sorted-duplicate-beginning") << (QList<int>() << -5 << -5 << -2 << 0 << 8) << -5; |
| QTest::newRow("empty") << (QList<int>()) << -42; |
| QTest::newRow("not found 1 ") << (QList<int>() << 1 << 5 << 8 << 65) << -42; |
| QTest::newRow("not found 2 ") << (QList<int>() << -456 << -5 << 8 << 65) << -42; |
| } |
| |
| void tst_QAlgorithms::test_qBinaryFind() |
| { |
| QFETCH(QList<int>, data); |
| QFETCH(int, resultValue); |
| |
| //-42 means not found |
| if (resultValue == -42) { |
| QVERIFY(qBinaryFind(data.constBegin(), data.constEnd(), resultValue) == data.constEnd()); |
| QVERIFY(qBinaryFind(data, resultValue) == data.constEnd()); |
| QVERIFY(qBinaryFind(data.begin(), data.end(), resultValue) == data.end()); |
| QVERIFY(qBinaryFind(data.begin(), data.end(), resultValue, qLess<int>()) == data.end()); |
| return; |
| } |
| |
| QCOMPARE(*qBinaryFind(data.constBegin(), data.constEnd(), resultValue), resultValue); |
| QCOMPARE(*qBinaryFind(data.begin(), data.end(), resultValue), resultValue); |
| QCOMPARE(*qBinaryFind(data, resultValue), resultValue); |
| QCOMPARE(*qBinaryFind(data.constBegin(), data.constEnd(), resultValue, qLess<int>()), resultValue); |
| } |
| |
| void tst_QAlgorithms::qBinaryFindOneEntry() |
| { |
| QList<int> list; |
| list << 2; |
| |
| QVERIFY(::qBinaryFind(list.constBegin(), list.constEnd(), 2) != list.constEnd()); |
| } |
| |
| |
| void tst_QAlgorithms::sortAPItest() |
| { |
| QVector<int> testVector = generateData<int>("Random", 101); |
| qSort(testVector); |
| QVERIFY(isSorted(testVector)); |
| qSort(testVector.begin(), testVector.end()); |
| QVERIFY(isSorted(testVector)); |
| qSort(testVector.begin(), testVector.end(), qLess<int>()); |
| QVERIFY(isSorted(testVector)); |
| |
| testVector = generateData<int>("Random", 71); |
| qStableSort(testVector); |
| QVERIFY(isSorted(testVector)); |
| qStableSort(testVector.begin(), testVector.end()); |
| QVERIFY(isSorted(testVector)); |
| qStableSort(testVector.begin(), testVector.end(), qLess<int>()); |
| QVERIFY(isSorted(testVector)); |
| |
| QList<int> testList = generateData<int>("Random", 101).toList(); |
| qSort(testList); |
| QVERIFY(isSorted(testList)); |
| qSort(testList.begin(), testList.end()); |
| QVERIFY(isSorted(testList)); |
| qSort(testList.begin(), testList.end(), qLess<int>()); |
| QVERIFY(isSorted(testList)); |
| |
| testList = generateData<int>("Random", 71).toList(); |
| qStableSort(testList); |
| QVERIFY(isSorted(testList)); |
| qStableSort(testList.begin(), testList.end()); |
| QVERIFY(isSorted(testList)); |
| qStableSort(testList.begin(), testList.end(), qLess<int>()); |
| QVERIFY(isSorted(testList)); |
| } |
| |
| |
| class StableSortTest |
| { |
| public: |
| StableSortTest(){}; |
| StableSortTest(int Major, int Minor) : Major(Major), Minor(Minor) {} |
| bool operator<(const StableSortTest &other) const {return (Major < other.Major); } |
| bool testMinor(const StableSortTest &other) const {return Minor < other.Minor; } |
| |
| int Major; |
| int Minor; |
| }; |
| |
| ostream &operator<<(ostream &out, const StableSortTest& obj) { out << obj.Major << "-" << obj.Minor; return out; } |
| |
| QVector<StableSortTest> createStableTestVector() |
| { |
| QVector<StableSortTest> stableTestVector; |
| for (int i=500; i>=0; --i) { |
| for (int j=0; j<10; ++j) { |
| stableTestVector.append(StableSortTest(i, j)); |
| } |
| } |
| return stableTestVector; |
| } |
| |
| template <typename ContainerType, typename LessThan> |
| bool isStableSorted(ContainerType &container, LessThan lessThan) |
| { |
| for (int i=0; i < container.count() - 1; ++i) { |
| //not sorted? |
| if (lessThan(container.at(i + 1), container.at(i))) |
| return false; |
| // equal? |
| if (lessThan(container.at(i), container.at(i + 1))) |
| continue; |
| // minor version? |
| if(container.at(i + 1).testMinor(container.at(i))) |
| return false; |
| } |
| return true; |
| } |
| |
| void tst_QAlgorithms::stableSortTest() |
| { |
| // Selftests: |
| { |
| QVector<StableSortTest> stableTestVector = createStableTestVector(); |
| qSort(stableTestVector.begin(), stableTestVector.end(), qLess<StableSortTest>()); |
| QVERIFY(isSorted(stableTestVector, qLess<StableSortTest>())); |
| QVERIFY(!isStableSorted(stableTestVector, qLess<StableSortTest>())); |
| } |
| { |
| QVector<StableSortTest> stableTestVector = createStableTestVector(); |
| qSort(stableTestVector.begin(), stableTestVector.end(), qGreater<StableSortTest>()); |
| QVERIFY(isSorted(stableTestVector, qGreater<StableSortTest>())); |
| QVERIFY(!isStableSorted(stableTestVector, qGreater<StableSortTest>())); |
| } |
| { |
| QVector<StableSortTest> stableTestVector = createStableTestVector(); |
| qSort(stableTestVector.begin(), stableTestVector.end(), qGreater<StableSortTest>()); |
| QVERIFY(!isSorted(stableTestVector, qLess<StableSortTest>())); |
| QVERIFY(!isStableSorted(stableTestVector, qGreater<StableSortTest>())); |
| } |
| |
| |
| // Stable sort with qLess |
| { |
| QVector<StableSortTest> stableTestVector = createStableTestVector(); |
| std::stable_sort(stableTestVector.begin(), stableTestVector.end(), qLess<StableSortTest>()); |
| QVERIFY(isSorted(stableTestVector, qLess<StableSortTest>())); |
| QVERIFY(isStableSorted(stableTestVector, qLess<StableSortTest>())); |
| } |
| { |
| QVector<StableSortTest> stableTestVector = createStableTestVector(); |
| qStableSort(stableTestVector.begin(), stableTestVector.end(), qLess<StableSortTest>()); |
| QVERIFY(isSorted(stableTestVector, qLess<StableSortTest>())); |
| QVERIFY(isStableSorted(stableTestVector, qLess<StableSortTest>())); |
| } |
| |
| // Stable sort with qGreater |
| { |
| QVector<StableSortTest> stableTestVector = createStableTestVector(); |
| std::stable_sort(stableTestVector.begin(), stableTestVector.end(), qGreater<StableSortTest>()); |
| QVERIFY(isSorted(stableTestVector, qGreater<StableSortTest>())); |
| QVERIFY(isStableSorted(stableTestVector, qGreater<StableSortTest>())); |
| } |
| |
| { |
| QVector<StableSortTest> stableTestVector = createStableTestVector(); |
| qStableSort(stableTestVector.begin(), stableTestVector.end(), qGreater<StableSortTest>()); |
| QVERIFY(isSorted(stableTestVector, qGreater<StableSortTest>())); |
| QVERIFY(isStableSorted(stableTestVector, qGreater<StableSortTest>())); |
| } |
| } |
| |
| |
| void tst_QAlgorithms::stableSortCorrectnessTest_data() |
| { |
| const int dataSize = 1000; |
| QTest::addColumn<QVector<int> >("unsorted"); |
| QTest::newRow("From documentation") << (QVector<int>() << 33 << 12 << 68 << 6 << 12); |
| QTest::newRow("Equal") << (generateData<int>("Equal", dataSize)); |
| QTest::newRow("Ascending") << (generateData<int>("Ascending", dataSize)); |
| QTest::newRow("Descending") << (generateData<int>("Descending", dataSize)); |
| QTest::newRow("Duplicates") << (generateData<int>("Duplicates", dataSize)); |
| QTest::newRow("Almost Sorted") << (generateData<int>("Almost Sorted", dataSize)); |
| QTest::newRow("Random") << (generateData<int>("Random", dataSize)); |
| } |
| |
| void tst_QAlgorithms::stableSortCorrectnessTest() |
| { |
| QFETCH(QVector<int>, unsorted); |
| |
| QVector<int> sorted = unsorted; |
| qStableSort(sorted.begin(), sorted.end()); |
| |
| // Verify that sorted contains the same numbers as unsorted. |
| foreach(int value, unsorted) { |
| QVERIFY(sorted.contains(value)); |
| int unsortedCount = 0; |
| qCount(unsorted.begin(), unsorted.end(), value, unsortedCount); |
| int sortedCount = 0; |
| qCount(sorted.begin(), sorted.end(), value, sortedCount); |
| QCOMPARE(sortedCount, unsortedCount); |
| } |
| |
| QVERIFY(isSorted(sorted)); |
| } |
| |
| void tst_QAlgorithms::convenienceAPI_deprecated() |
| { |
| // Compile-test for QAlgorithm convenience functions. |
| QList<int> list, list2; |
| |
| qCopy(list.begin(), list.end(), list2.begin()); |
| qCopyBackward(list.begin(), list.end(), list2.begin()); |
| qEqual(list.begin(), list.end(), list2.begin()); |
| |
| qFill(list, 1); |
| qFill(list.begin(), list.end(), 1); |
| |
| qFind(list, 1); |
| qFind(list.begin(), list.end(), 1); |
| |
| int count1 = 0 , count2 = 0, count3 = 0; |
| qCount(list, 1, count1); |
| qCount(list.begin(), list.end(), 1, count2); |
| QCOMPARE(count1, count2); |
| QCOMPARE(count2, count3); |
| |
| qSort(list); |
| qSort(list.begin(), list.end()); |
| qSort(list.begin(), list.end(), qLess<int>()); |
| |
| qStableSort(list); |
| qStableSort(list.begin(), list.end()); |
| qStableSort(list.begin(), list.end(), qLess<int>()); |
| |
| qLowerBound(list, 1);; |
| qLowerBound(list.begin(), list.end(), 1); |
| qLowerBound(list.begin(), list.end(), 1, qLess<int>()); |
| |
| qUpperBound(list, 1); |
| qUpperBound(list.begin(), list.end(), 1); |
| qUpperBound(list.begin(), list.end(), 1, qLess<int>()); |
| |
| qBinaryFind(list, 1); |
| qBinaryFind(list.begin(), list.end(), 1); |
| qBinaryFind(list.begin(), list.end(), 1, qLess<int>()); |
| } |
| |
| template <typename DataType> |
| class QuickSortHelper |
| { |
| public: |
| void operator()(QVector<DataType> list) |
| { |
| ::qSort(list); |
| } |
| }; |
| |
| template <typename DataType> |
| class StableSortHelper |
| { |
| public: |
| void operator()(QVector<DataType> list) |
| { |
| ::qStableSort(list); |
| } |
| }; |
| |
| template <typename DataType> |
| class StlSortHelper |
| { |
| public: |
| void operator()(QVector<DataType> list) |
| { |
| std::sort(list.begin(), list.end()); |
| } |
| }; |
| |
| template <typename DataType> |
| class StlStableSortHelper |
| { |
| public: |
| void operator()(QVector<DataType> list) |
| { |
| std::stable_sort(list.begin(), list.end()); |
| } |
| }; |
| |
| #if Q_TEST_PERFORMANCE |
| void tst_QAlgorithms::performance() |
| { |
| cout << Qt::endl << "Quick sort" << Qt::endl; |
| testAlgorithm<QuickSortHelper<TestInt>, TestInt>(QuickSortHelper<TestInt>(), dataSetTypes); |
| cout << Qt::endl << "stable sort" << Qt::endl; |
| testAlgorithm<StableSortHelper<TestInt>, TestInt>(StableSortHelper<TestInt>(), dataSetTypes); |
| cout << Qt::endl << "std::sort" << Qt::endl; |
| testAlgorithm<StlSortHelper<TestInt>, TestInt>(StlSortHelper<TestInt>(), dataSetTypes); |
| cout << Qt::endl << "std::stable_sort" << Qt::endl; |
| testAlgorithm<StlStableSortHelper<TestInt>, TestInt>(StlStableSortHelper<TestInt>(), dataSetTypes); |
| /* |
| cout << Qt::endl << "Sorting lists of ints" << Qt::endl; |
| cout << Qt::endl << "Quick sort" << Qt::endl; |
| testAlgorithm<QuickSortHelper<int>, int>(QuickSortHelper<int>(), dataSetTypes); |
| cout << Qt::endl << "std::sort" << Qt::endl; |
| testAlgorithm<StlSortHelper<int>, int>(StlSortHelper<int>(), dataSetTypes); |
| cout << Qt::endl << "std::stable_sort" << Qt::endl; |
| testAlgorithm<StlStableSortHelper<int>, int>(StlStableSortHelper<int>(), dataSetTypes); |
| */ |
| } |
| #endif |
| |
| void tst_QAlgorithms::qCountIterators() const |
| { |
| QList<int> list; |
| list << 3 << 3 << 6 << 6 << 6 << 8; |
| |
| { |
| int countOf7 = 0; |
| ::qCount(list.begin(), list.end(), 7, countOf7); |
| QCOMPARE(countOf7, 0); |
| } |
| |
| { |
| int countOf3 = 0; |
| ::qCount(list.begin(), list.end(), 3, countOf3); |
| QCOMPARE(countOf3, 2); |
| } |
| |
| { |
| int countOf6 = 0; |
| ::qCount(list.begin(), list.end(), 6, countOf6); |
| QCOMPARE(countOf6, 3); |
| } |
| |
| { |
| int countOf8 = 0; |
| ::qCount(list.begin(), list.end(), 8, countOf8); |
| QCOMPARE(countOf8, 1); |
| } |
| |
| /* Check that we add to the count, not set it. */ |
| { |
| int countOf8 = 5; |
| ::qCount(list.begin(), list.end(), 8, countOf8); |
| QCOMPARE(countOf8, 6); |
| } |
| } |
| |
| void tst_QAlgorithms::qCountContainer() const |
| { |
| QList<int> list; |
| list << 3 << 3 << 6 << 6 << 6 << 8; |
| |
| { |
| int countOf7 = 0; |
| ::qCount(list, 7, countOf7); |
| QCOMPARE(countOf7, 0); |
| } |
| |
| { |
| int countOf3 = 0; |
| ::qCount(list, 3, countOf3); |
| QCOMPARE(countOf3, 2); |
| } |
| |
| { |
| int countOf6 = 0; |
| ::qCount(list, 6, countOf6); |
| QCOMPARE(countOf6, 3); |
| } |
| |
| { |
| int countOf8 = 0; |
| ::qCount(list, 8, countOf8); |
| QCOMPARE(countOf8, 1); |
| } |
| |
| /* Check that we add to the count, not set it. */ |
| { |
| int countOf8 = 5; |
| ::qCount(list, 8, countOf8); |
| QCOMPARE(countOf8, 6); |
| } |
| } |
| |
| class RAI |
| { |
| public: |
| typedef int difference_type; |
| typedef int value_type; |
| typedef std::random_access_iterator_tag iterator_category; |
| typedef int *pointer; |
| typedef int &reference; |
| |
| RAI(int searched = 5, int hidePos = 4, int len = 10) |
| : curPos_(0) |
| , length_(len) |
| , searchedVal_(searched) |
| , searchedValPos_(hidePos) |
| { |
| } |
| |
| int at(int pos) const |
| { |
| if (pos == searchedValPos_) { |
| return searchedVal_; |
| } |
| else if (pos < searchedValPos_) { |
| return searchedVal_ - 1; |
| } |
| |
| return searchedVal_ + 1; |
| } |
| |
| RAI begin() const |
| { |
| RAI rai = *this; |
| rai.setCurPos(0); |
| return rai; |
| } |
| |
| RAI end() const |
| { |
| RAI rai = *this; |
| rai.setCurPos(length_); |
| return rai; |
| } |
| |
| int pos() const |
| { |
| return curPos(); |
| } |
| |
| int size() const |
| { |
| return length_; |
| } |
| |
| RAI operator+(int i) const |
| { |
| RAI rai = *this; |
| rai.setCurPos( rai.curPos() + i ); |
| if (rai.curPos() > length_) { |
| rai.setCurPos(length_); |
| } |
| return rai; |
| } |
| |
| RAI operator-(int i) const |
| { |
| RAI rai = *this; |
| rai.setCurPos( rai.curPos() - i ); |
| if (rai.curPos() < 0) { |
| rai.setCurPos(0); |
| } |
| return rai; |
| } |
| |
| int operator-(const RAI& it) const |
| { |
| return curPos() - it.curPos(); |
| } |
| |
| RAI& operator+=(int i) |
| { |
| setCurPos( curPos() + i ); |
| if (curPos() > length_) { |
| setCurPos(length_); |
| } |
| return *this; |
| } |
| |
| RAI& operator-=(int i) |
| { |
| setCurPos( curPos() - i); |
| if (curPos() < 0) { |
| setCurPos(0); |
| } |
| return *this; |
| } |
| |
| RAI& operator++() |
| { |
| if (curPos() < length_) { |
| setCurPos( curPos() + 1 ); |
| } |
| return *this; |
| } |
| |
| RAI operator++(int) |
| { |
| RAI rai = *this; |
| |
| if (curPos() < length_) { |
| setCurPos( curPos() + 1 ); |
| } |
| |
| return rai; |
| } |
| |
| RAI& operator--() |
| { |
| if (curPos() > 0) { |
| setCurPos( curPos() - 1 ); |
| } |
| return *this; |
| } |
| |
| RAI operator--(int) |
| { |
| RAI rai = *this; |
| |
| if (curPos() > 0) { |
| setCurPos( curPos() - 1 ); |
| } |
| |
| return rai; |
| } |
| |
| bool operator==(const RAI& rai) const |
| { |
| return rai.curPos() == curPos(); |
| } |
| |
| bool operator!=(const RAI& rai) const |
| { |
| return !operator==(rai); |
| } |
| |
| int operator*() const |
| { |
| return at(curPos()); |
| } |
| |
| int operator[](int i) const |
| { |
| return at(i); |
| } |
| |
| private: |
| |
| int curPos() const |
| { |
| return curPos_; |
| } |
| |
| void setCurPos(int pos) |
| { |
| curPos_ = pos; |
| } |
| |
| int curPos_; |
| int length_; |
| int searchedVal_; |
| int searchedValPos_; |
| }; |
| |
| void tst_QAlgorithms::binaryFindOnLargeContainer() const |
| { |
| const int len = 2 * 1000 * 1000 * 537; |
| const int pos = len - 12345; |
| RAI rai(5, pos, len); |
| |
| RAI foundIt = qBinaryFind(rai.begin(), rai.end(), 5); |
| QCOMPARE(foundIt.pos(), 1073987655); |
| } |
| |
| #endif // QT_DEPRECATED_SINCE(5, 2) |
| |
| // alternative implementation of qPopulationCount for comparison: |
| static Q_DECL_CONSTEXPR const uint bitsSetInNibble[] = { |
| 0, 1, 1, 2, 1, 2, 2, 3, |
| 1, 2, 2, 3, 2, 3, 3, 4, |
| }; |
| Q_STATIC_ASSERT(sizeof bitsSetInNibble / sizeof *bitsSetInNibble == 16); |
| |
| static Q_DECL_CONSTEXPR uint bitsSetInByte(quint8 byte) |
| { |
| return bitsSetInNibble[byte & 0xF] + bitsSetInNibble[byte >> 4]; |
| } |
| static Q_DECL_CONSTEXPR uint bitsSetInShort(quint16 word) |
| { |
| return bitsSetInByte(word & 0xFF) + bitsSetInByte(word >> 8); |
| } |
| static Q_DECL_CONSTEXPR uint bitsSetInInt(quint32 word) |
| { |
| return bitsSetInShort(word & 0xFFFF) + bitsSetInShort(word >> 16); |
| } |
| static Q_DECL_CONSTEXPR uint bitsSetInInt64(quint64 word) |
| { |
| return bitsSetInInt(word & 0xFFFFFFFF) + bitsSetInInt(word >> 32); |
| } |
| |
| |
| void tst_QAlgorithms::popCount_data_impl(size_t sizeof_T_Int) |
| { |
| using namespace QTest; |
| addColumn<quint64>("input"); |
| addColumn<uint>("expected"); |
| |
| for (uint i = 0; i < UCHAR_MAX; ++i) { |
| const uchar byte = static_cast<uchar>(i); |
| const uint bits = bitsSetInByte(byte); |
| const quint64 value = static_cast<quint64>(byte); |
| const quint64 input = value << ((i % sizeof_T_Int) * 8U); |
| QTest::addRow("0x%016llx", input) << input << bits; |
| } |
| |
| // and some random ones: |
| if (sizeof_T_Int >= 8) |
| for (size_t i = 0; i < 1000; ++i) { |
| const quint64 input = QRandomGenerator::global()->generate64(); |
| QTest::addRow("0x%016llx", input) << input << bitsSetInInt64(input); |
| } |
| else if (sizeof_T_Int >= 2) |
| for (size_t i = 0; i < 1000 ; ++i) { |
| const quint32 input = QRandomGenerator::global()->generate(); |
| if (sizeof_T_Int >= 4) |
| QTest::addRow("0x%08x", input) << quint64(input) << bitsSetInInt(input); |
| else |
| QTest::addRow("0x%04x", quint16(input & 0xFFFF)) << quint64(input & 0xFFFF) << bitsSetInShort(input & 0xFFFF); |
| } |
| } |
| |
| template <typename T_Int> |
| void tst_QAlgorithms::popCount_impl() |
| { |
| QFETCH(quint64, input); |
| QFETCH(uint, expected); |
| |
| const T_Int value = static_cast<T_Int>(input); |
| |
| QCOMPARE(qPopulationCount(value), expected); |
| } |
| |
| void tst_QAlgorithms::countTrailing_data_impl(size_t sizeof_T_Int) |
| { |
| using namespace QTest; |
| addColumn<quint64>("input"); |
| addColumn<uint>("expected"); |
| |
| int nibs = sizeof_T_Int*2; |
| |
| newRow(("0x"+QByteArray::number(0,16).rightJustified(nibs,'0')).constData()) << Q_UINT64_C(0) << uint(sizeof_T_Int*8); |
| for (uint i = 0; i < sizeof_T_Int*8; ++i) { |
| const quint64 input = Q_UINT64_C(1) << i; |
| newRow(("0x"+QByteArray::number(input,16).rightJustified(nibs,'0')).constData()) << input << i; |
| } |
| |
| quint64 type_mask; |
| if (sizeof_T_Int>=8) |
| type_mask = ~Q_UINT64_C(0); |
| else |
| type_mask = (Q_UINT64_C(1) << (sizeof_T_Int*8))-1; |
| |
| // and some random ones: |
| for (uint i = 0; i < sizeof_T_Int*8; ++i) { |
| for (uint j = 0; j < sizeof_T_Int*3; ++j) { // 3 is arbitrary |
| const quint64 r = QRandomGenerator::global()->generate64(); |
| const quint64 b = Q_UINT64_C(1) << i; |
| const quint64 mask = ((~(b-1)) ^ b) & type_mask; |
| const quint64 input = (r&mask) | b; |
| newRow(("0x"+QByteArray::number(input,16).rightJustified(nibs,'0')).constData()) << input << i; |
| } |
| } |
| } |
| |
| template <typename T_Int> |
| void tst_QAlgorithms::countTrailing_impl() |
| { |
| QFETCH(quint64, input); |
| QFETCH(uint, expected); |
| |
| const T_Int value = static_cast<T_Int>(input); |
| |
| QCOMPARE(qCountTrailingZeroBits(value), expected); |
| } |
| |
| void tst_QAlgorithms::countLeading_data_impl(size_t sizeof_T_Int) |
| { |
| using namespace QTest; |
| addColumn<quint64>("input"); |
| addColumn<uint>("expected"); |
| |
| int nibs = sizeof_T_Int*2; |
| |
| newRow(("0x"+QByteArray::number(0,16).rightJustified(nibs,'0')).constData()) << Q_UINT64_C(0) << uint(sizeof_T_Int*8); |
| for (uint i = 0; i < sizeof_T_Int*8; ++i) { |
| const quint64 input = Q_UINT64_C(1) << i; |
| newRow(("0x"+QByteArray::number(input,16).rightJustified(nibs,'0')).constData()) << input << uint(sizeof_T_Int*8-i-1); |
| } |
| |
| // and some random ones: |
| for (uint i = 0; i < sizeof_T_Int*8; ++i) { |
| for (uint j = 0; j < sizeof_T_Int*3; ++j) { // 3 is arbitrary |
| const quint64 r = QRandomGenerator::global()->generate64(); |
| const quint64 b = Q_UINT64_C(1) << i; |
| const quint64 mask = b-1; |
| const quint64 input = (r&mask) | b; |
| newRow(("0x"+QByteArray::number(input,16).rightJustified(nibs,'0')).constData()) << input << uint(sizeof_T_Int*8-i-1); |
| } |
| } |
| } |
| |
| template <typename T_Int> |
| void tst_QAlgorithms::countLeading_impl() |
| { |
| QFETCH(quint64, input); |
| QFETCH(uint, expected); |
| |
| const T_Int value = static_cast<T_Int>(input); |
| |
| QCOMPARE(qCountLeadingZeroBits(value), expected); |
| } |
| |
| QTEST_APPLESS_MAIN(tst_QAlgorithms) |
| #include "tst_qalgorithms.moc" |
| |