diff options
Diffstat (limited to 'tests/auto/corelib/tools/qalgorithms/tst_qalgorithms.cpp')
| -rw-r--r-- | tests/auto/corelib/tools/qalgorithms/tst_qalgorithms.cpp | 918 |
1 files changed, 50 insertions, 868 deletions
diff --git a/tests/auto/corelib/tools/qalgorithms/tst_qalgorithms.cpp b/tests/auto/corelib/tools/qalgorithms/tst_qalgorithms.cpp index 44e6bef6f0..8d68a7a270 100644 --- a/tests/auto/corelib/tools/qalgorithms/tst_qalgorithms.cpp +++ b/tests/auto/corelib/tools/qalgorithms/tst_qalgorithms.cpp @@ -1,33 +1,8 @@ -/**************************************************************************** -** -** 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$ -** -****************************************************************************/ +// Copyright (C) 2020 The Qt Company Ltd. +// SPDX-License-Identifier: LicenseRef-Qt-Commercial OR GPL-3.0-only #include "../../../../../src/corelib/tools/qalgorithms.h" -#include <QtTest/QtTest> +#include <QTest> QT_WARNING_DISABLE_DEPRECATED @@ -54,31 +29,6 @@ private slots: 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)); } @@ -120,155 +70,18 @@ private: 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> -QList<DataType> generateData(QString dataSetType, const int length) +template <typename T> struct PrintIfFailed { - QList<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; - } + T value; + PrintIfFailed(T v) : value(v) {} + ~PrintIfFailed() + { + if (!QTest::currentTestFailed()) + return; + qWarning() << "Original value was" << Qt::hex << Qt::showbase << T(value); } - 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) { - QList<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() { { @@ -341,42 +154,42 @@ void tst_QAlgorithms::swap() } { - void *a = 0, *b = 0; + void *a = nullptr, *b = nullptr; qSwap(a, b); } { - const void *a = 0, *b = 0; + const void *a = nullptr, *b = nullptr; qSwap(a, b); } { - QString *a = 0, *b = 0; + QString *a = nullptr, *b = nullptr; qSwap(a, b); } { - const QString *a = 0, *b = 0; + const QString *a = nullptr, *b = nullptr; qSwap(a, b); } { - QString **a = 0, **b = 0; + QString **a = nullptr, **b = nullptr; qSwap(a, b); } { - const QString **a = 0, **b = 0; + const QString **a = nullptr, **b = nullptr; qSwap(a, b); } { - QString * const *a = 0, * const *b = 0; + QString * const *a = nullptr, * const *b = nullptr; qSwap(a, b); } { - const QString * const *a = 0, * const *b = 0; + const QString * const *a = nullptr, * const *b = nullptr; qSwap(a, b); } } @@ -412,639 +225,6 @@ void tst_QAlgorithms::convenienceAPI() 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() -{ - 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; } - -QList<StableSortTest> createStableTestList() -{ - QList<StableSortTest> stableTestList; - for (int i = 500; i >= 0; --i) { - for (int j = 0; j < 10; ++j) - stableTestList.append(StableSortTest(i, j)); - } - return stableTestList; -} - -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: - { - QList<StableSortTest> stableTestList = createStableTestList(); - qSort(stableTestList.begin(), stableTestList.end(), qLess<StableSortTest>()); - QVERIFY(isSorted(stableTestList, qLess<StableSortTest>())); - QVERIFY(!isStableSorted(stableTestList, qLess<StableSortTest>())); - } - { - QList<StableSortTest> stableTestList = createStableTestList(); - qSort(stableTestList.begin(), stableTestList.end(), qGreater<StableSortTest>()); - QVERIFY(isSorted(stableTestList, qGreater<StableSortTest>())); - QVERIFY(!isStableSorted(stableTestList, qGreater<StableSortTest>())); - } - { - QList<StableSortTest> stableTestList = createStableTestList(); - qSort(stableTestList.begin(), stableTestList.end(), qGreater<StableSortTest>()); - QVERIFY(!isSorted(stableTestList, qLess<StableSortTest>())); - QVERIFY(!isStableSorted(stableTestList, qGreater<StableSortTest>())); - } - - - // Stable sort with qLess - { - QList<StableSortTest> stableTestList = createStableTestList(); - std::stable_sort(stableTestList.begin(), stableTestList.end(), qLess<StableSortTest>()); - QVERIFY(isSorted(stableTestList, qLess<StableSortTest>())); - QVERIFY(isStableSorted(stableTestList, qLess<StableSortTest>())); - } - { - QList<StableSortTest> stableTestList = createStableTestList(); - qStableSort(stableTestList.begin(), stableTestList.end(), qLess<StableSortTest>()); - QVERIFY(isSorted(stableTestList, qLess<StableSortTest>())); - QVERIFY(isStableSorted(stableTestList, qLess<StableSortTest>())); - } - - // Stable sort with qGreater - { - QList<StableSortTest> stableTestList = createStableTestList(); - std::stable_sort(stableTestList.begin(), stableTestList.end(), qGreater<StableSortTest>()); - QVERIFY(isSorted(stableTestList, qGreater<StableSortTest>())); - QVERIFY(isStableSorted(stableTestList, qGreater<StableSortTest>())); - } - - { - QList<StableSortTest> stableTestList = createStableTestList(); - qStableSort(stableTestList.begin(), stableTestList.end(), qGreater<StableSortTest>()); - QVERIFY(isSorted(stableTestList, qGreater<StableSortTest>())); - QVERIFY(isStableSorted(stableTestList, qGreater<StableSortTest>())); - } -} - - -void tst_QAlgorithms::stableSortCorrectnessTest_data() -{ - const int dataSize = 1000; - QTest::addColumn<QList<int>>("unsorted"); - QTest::newRow("From documentation") << (QList<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(QList<int>, unsorted); - - QList<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()(QList<DataType> list) - { - ::qSort(list); - } -}; - -template <typename DataType> -class StableSortHelper -{ -public: - void operator()(QList<DataType> list) - { - ::qStableSort(list); - } -}; - -template <typename DataType> -class StlSortHelper -{ -public: - void operator()(QList<DataType> list) - { - std::sort(list.begin(), list.end()); - } -}; - -template <typename DataType> -class StlStableSortHelper -{ -public: - void operator()(QList<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 constexpr const uint bitsSetInNibble[] = { 0, 1, 1, 2, 1, 2, 2, 3, @@ -1081,23 +261,26 @@ void tst_QAlgorithms::popCount_data_impl(size_t sizeof_T_Int) 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; + QTest::addRow("%u-bits", i) << input << bits; } // and some random ones: - if (sizeof_T_Int >= 8) + 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); + QTest::addRow("random-%zu", i) << 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); + } 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("random-%zu", i) << quint64(input) << bitsSetInInt(input); + } else { + QTest::addRow("random-%zu", i) + << quint64(input & 0xFFFF) << bitsSetInShort(input & 0xFFFF); } + } + } } template <typename T_Int> @@ -1107,22 +290,23 @@ void tst_QAlgorithms::popCount_impl() QFETCH(uint, expected); const T_Int value = static_cast<T_Int>(input); - + PrintIfFailed pf(value); QCOMPARE(qPopulationCount(value), expected); } +// Number of test-cases per offset into each size (arbitrary): +static constexpr int casesPerOffset = 3; + 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); + addRow("0") << 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; + addRow("bit-%u", i) << input << i; } quint64 type_mask; @@ -1133,12 +317,12 @@ void tst_QAlgorithms::countTrailing_data_impl(size_t sizeof_T_Int) // 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 b = Q_UINT64_C(1) << i; + const quint64 mask = ((~(b - 1)) ^ b) & type_mask; + for (uint j = 0; j < sizeof_T_Int * casesPerOffset; ++j) { 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; + addRow("%u-bits-random-%u", i, j) << input << i; } } } @@ -1150,7 +334,7 @@ void tst_QAlgorithms::countTrailing_impl() QFETCH(uint, expected); const T_Int value = static_cast<T_Int>(input); - + PrintIfFailed pf(value); QCOMPARE(qCountTrailingZeroBits(value), expected); } @@ -1160,22 +344,20 @@ void tst_QAlgorithms::countLeading_data_impl(size_t sizeof_T_Int) 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); + addRow("0") << 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); + addRow("bit-%u", i) << 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 b = Q_UINT64_C(1) << i; + const quint64 mask = b - 1; + for (uint j = 0; j < sizeof_T_Int * casesPerOffset; ++j) { 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); + addRow("%u-bits-random-%u", i, j) << input << uint(sizeof_T_Int*8-i-1); } } } @@ -1187,7 +369,7 @@ void tst_QAlgorithms::countLeading_impl() QFETCH(uint, expected); const T_Int value = static_cast<T_Int>(input); - + PrintIfFailed pf(value); QCOMPARE(qCountLeadingZeroBits(value), expected); } |