From 38be0d13830efd2d98281c645c3a60afe05ffece Mon Sep 17 00:00:00 2001 From: Qt by Nokia Date: Wed, 27 Apr 2011 12:05:43 +0200 Subject: Initial import from the monolithic Qt. This is the beginning of revision history for this module. If you want to look at revision history older than this, please refer to the Qt Git wiki for how to use Git history grafting. At the time of writing, this wiki is located here: http://qt.gitorious.org/qt/pages/GitIntroductionWithQt If you have already performed the grafting and you don't see any history beyond this commit, try running "git log" with the "--follow" argument. Branched from the monolithic repo, Qt master branch, at commit 896db169ea224deb96c59ce8af800d019de63f12 --- tests/auto/qalgorithms/.gitignore | 1 + tests/auto/qalgorithms/q3tl.h | 212 +++++ tests/auto/qalgorithms/qalgorithms.pro | 5 + tests/auto/qalgorithms/tst_qalgorithms.cpp | 1223 ++++++++++++++++++++++++++++ 4 files changed, 1441 insertions(+) create mode 100644 tests/auto/qalgorithms/.gitignore create mode 100644 tests/auto/qalgorithms/q3tl.h create mode 100644 tests/auto/qalgorithms/qalgorithms.pro create mode 100644 tests/auto/qalgorithms/tst_qalgorithms.cpp (limited to 'tests/auto/qalgorithms') diff --git a/tests/auto/qalgorithms/.gitignore b/tests/auto/qalgorithms/.gitignore new file mode 100644 index 0000000000..379c13eb9b --- /dev/null +++ b/tests/auto/qalgorithms/.gitignore @@ -0,0 +1 @@ +tst_qalgorithms diff --git a/tests/auto/qalgorithms/q3tl.h b/tests/auto/qalgorithms/q3tl.h new file mode 100644 index 0000000000..c856cbf533 --- /dev/null +++ b/tests/auto/qalgorithms/q3tl.h @@ -0,0 +1,212 @@ +/**************************************************************************** +** +** Copyright (C) 2011 Nokia Corporation and/or its subsidiary(-ies). +** All rights reserved. +** Contact: Nokia Corporation (qt-info@nokia.com) +** +** This file is part of the Qt3Support module of the Qt Toolkit. +** +** $QT_BEGIN_LICENSE:LGPL$ +** No Commercial Usage +** This file contains pre-release code and may not be distributed. +** You may use this file in accordance with the terms and conditions +** contained in the Technology Preview License Agreement accompanying +** this package. +** +** GNU Lesser General Public License Usage +** Alternatively, this file may be used under the terms of the GNU Lesser +** General Public License version 2.1 as published by the Free Software +** Foundation and appearing in the file LICENSE.LGPL included in the +** packaging of this file. Please review the following information to +** ensure the GNU Lesser General Public License version 2.1 requirements +** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html. +** +** In addition, as a special exception, Nokia gives you certain additional +** rights. These rights are described in the Nokia Qt LGPL Exception +** version 1.1, included in the file LGPL_EXCEPTION.txt in this package. +** +** If you have questions regarding the use of this file, please contact +** Nokia at qt-info@nokia.com. +** +** +** +** +** +** +** +** +** $QT_END_LICENSE$ +** +****************************************************************************/ + +#ifndef Q3TL_H +#define Q3TL_H + +#include + +QT_BEGIN_HEADER + +QT_BEGIN_NAMESPACE + +QT_MODULE(Qt3SupportLight) + +template +Q_OUTOFLINE_TEMPLATE void qHeapSortPushDown(T *heap, int first, int last, LessThan lessThan) +{ + int r = first; + while (r <= last / 2) { + if (last == 2 * r) { + // node r has only one child + if (lessThan(heap[2 * r], heap[r])) + qSwap(heap[r], heap[2 * r]); + r = last; + } else { + // node r has two children + if (lessThan(heap[2 * r], heap[r]) && !lessThan(heap[2 * r + 1], heap[2 * r])) { + // swap with left child + qSwap(heap[r], heap[2 * r]); + r *= 2; + } else if (lessThan(heap[2 * r + 1], heap[r]) + && lessThan(heap[2 * r + 1], heap[2 * r])) { + // swap with right child + qSwap(heap[r], heap[2 * r + 1]); + r = 2 * r + 1; + } else { + r = last; + } + } + } +} + +template +Q_OUTOFLINE_TEMPLATE void qHeapSortHelper(BiIterator begin, BiIterator end, const T & /* dummy */, LessThan lessThan) +{ + BiIterator it = begin; + uint n = 0; + while (it != end) { + ++n; + ++it; + } + if (n == 0) + return; + + // Create the heap + BiIterator insert = begin; + T *realheap = new T[n]; + T *heap = realheap - 1; + int size = 0; + for(; insert != end; ++insert) { + heap[++size] = *insert; + int i = size; + while (i > 1 && lessThan(heap[i], heap[i / 2])) { + qSwap(heap[i], heap[i / 2]); + i /= 2; + } + } + + // Now do the sorting + for (int i = n; i > 0; i--) { + *begin++ = heap[1]; + if (i > 1) { + heap[1] = heap[i]; + qHeapSortPushDown(heap, 1, i - 1, lessThan); + } + } + + delete[] realheap; +} + +template +inline void qHeapSortHelper(BiIterator begin, BiIterator end, const T &dummy) +{ + qHeapSortHelper(begin, end, dummy, qLess()); +} + +template +inline void qHeapSort(BiIterator begin, BiIterator end, LessThan lessThan) +{ + if (begin != end) + qHeapSortHelper(begin, end, *begin, lessThan); +} + +template +inline void qHeapSort(BiIterator begin, BiIterator end) +{ + if (begin != end) + qHeapSortHelper(begin, end, *begin); +} + +template +inline void qHeapSort(Container &c) +{ +#ifdef Q_CC_BOR + // Work around Borland 5.5 optimizer bug + c.detach(); +#endif + if (!c.empty()) + qHeapSortHelper(c.begin(), c.end(), *c.begin()); +} + + +template +void qBubbleSort(BiIterator begin, BiIterator end, LessThan lessThan) +{ + // Goto last element; + BiIterator last = end; + + // empty list + if (begin == end) + return; + + --last; + // only one element ? + if (last == begin) + return; + + // So we have at least two elements in here + while (begin != last) { + bool swapped = false; + BiIterator swapPos = begin; + BiIterator x = end; + BiIterator y = x; + y--; + do { + --x; + --y; + if (lessThan(*x, *y)) { + swapped = true; + qSwap(*x, *y); + swapPos = y; + } + } while (y != begin); + if (!swapped) + return; + begin = swapPos; + ++begin; + } +} + +template +void qBubbleSortHelper(BiIterator begin, BiIterator end, T) +{ + qBubbleSort(begin, end, qLess()); +} + +template +void qBubbleSort(BiIterator begin, BiIterator end) +{ + if (begin != end) + qBubbleSortHelper(begin, end, *begin); +} + +template +inline void qBubbleSort(Container &c) +{ + qBubbleSort(c.begin(), c.end()); +} + +QT_END_NAMESPACE + +QT_END_HEADER + +#endif // Q3TL_H diff --git a/tests/auto/qalgorithms/qalgorithms.pro b/tests/auto/qalgorithms/qalgorithms.pro new file mode 100644 index 0000000000..02af317f60 --- /dev/null +++ b/tests/auto/qalgorithms/qalgorithms.pro @@ -0,0 +1,5 @@ +load(qttest_p4) +SOURCES += tst_qalgorithms.cpp + +QT = core +contains(QT_CONFIG, qt3support): QT += qt3support diff --git a/tests/auto/qalgorithms/tst_qalgorithms.cpp b/tests/auto/qalgorithms/tst_qalgorithms.cpp new file mode 100644 index 0000000000..8dd7cbcc28 --- /dev/null +++ b/tests/auto/qalgorithms/tst_qalgorithms.cpp @@ -0,0 +1,1223 @@ +/**************************************************************************** +** +** Copyright (C) 2011 Nokia Corporation and/or its subsidiary(-ies). +** All rights reserved. +** Contact: Nokia Corporation (qt-info@nokia.com) +** +** This file is part of the test suite of the Qt Toolkit. +** +** $QT_BEGIN_LICENSE:LGPL$ +** No Commercial Usage +** This file contains pre-release code and may not be distributed. +** You may use this file in accordance with the terms and conditions +** contained in the Technology Preview License Agreement accompanying +** this package. +** +** GNU Lesser General Public License Usage +** Alternatively, this file may be used under the terms of the GNU Lesser +** General Public License version 2.1 as published by the Free Software +** Foundation and appearing in the file LICENSE.LGPL included in the +** packaging of this file. Please review the following information to +** ensure the GNU Lesser General Public License version 2.1 requirements +** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html. +** +** In addition, as a special exception, Nokia gives you certain additional +** rights. These rights are described in the Nokia Qt LGPL Exception +** version 1.1, included in the file LGPL_EXCEPTION.txt in this package. +** +** If you have questions regarding the use of this file, please contact +** Nokia at qt-info@nokia.com. +** +** +** +** +** +** +** +** +** $QT_END_LICENSE$ +** +****************************************************************************/ + + +#include + +#include +#include +#include +#include +#include +#include "../../../src/qt3support/tools/q3tl.h" +#include +#include +#include + +#define Q_TEST_PERFORMANCE 0 + +using namespace std; + +//TESTED_FILES= + +class tst_QAlgorithms : public QObject +{ +Q_OBJECT + +public: + tst_QAlgorithms(); + ~tst_QAlgorithms(); + +public slots: + void init(); + void cleanup(); + +private slots: + void qBubbleSort(); + void qHeapSort(); + void test_qLowerBound_data(); + void test_qLowerBound(); + void test_qUpperBound_data(); + void test_qUpperBound(); + void test_qBinaryFind_data(); + void test_qBinaryFind(); + void qBinaryFindOneEntry(); + void swap(); + void swap2(); + void sortEmptyList(); + void sortedList(); + void sortAPItest(); + void stableSortTest(); + void stableSortCorrectnessTest_data(); + void stableSortCorrectnessTest(); + void convenienceAPI(); + void qCountIterators() const; + void qCountContainer() const; + void binaryFindOnLargeContainer() const; + +#if Q_TEST_PERFORMANCE +private: + void performance(); +#endif +}; + +tst_QAlgorithms::tst_QAlgorithms() + +{ +} + +tst_QAlgorithms::~tst_QAlgorithms() +{ + +} + +void tst_QAlgorithms::init() +{ +} + +void tst_QAlgorithms::cleanup() +{ +} + + +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 +QVector generateData(QString dataSetType, const int length) +{ + QVector container; + if (dataSetType == "Random") { + for(int i=0; i < length; ++i) + container.append(rand()); + } + 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 +ResultSet testRun(ContainerType &container, Algorithm &algorithm, int millisecs) +{ + TestInt::lessThanRefCount = 0; + int count = 0; + QTime t; + t.start(); + while(t.elapsed() < millisecs) { + ++count; + algorithm(container); + } + ResultSet result; + result.numSorts = count; + result.lessThanRefCount = TestInt::lessThanRefCount; + return result; +} + +template +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 +bool isSorted(ContainerType &container) +{ + return isSorted(container, qLess()); +} + + +#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 << endl; +} + +template +void print(ContainerType testContainer) +{ + typedef typename ContainerType::value_type T; + + foreach(T value, testContainer) { + cout << value << " "; + } + + cout << endl; +} + +template +QList testAlgorithm(Algorithm &algorithm, QStringList dataSetTypes, int size, int time) +{ + QList results; + foreach(QString dataSetType, dataSetTypes) { + QVector container = generateData(dataSetType, size); + results.append(testRun(container, algorithm, time)); + Q_ASSERT(isSorted(container)); + } + return results; +} + +template +void testAlgorithm(Algorithm algorithm, QStringList &dataSetTypes) +{ + QList sizes = QList() << 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 results = + testAlgorithm(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 << endl; + } +} +#endif +static bool userFunction1(char ch1, char ch2) +{ + return (ch1 ^ 1) < (ch2 ^ 1); +} + +bool userFunction2(const char &ch1, char ch2) +{ + return (ch1 ^ 1) < (ch2 ^ 1); +} + +static inline bool userFunction3(char ch1, const char &ch2) +{ + return (ch1 ^ 1) < (ch2 ^ 1); +} + +inline bool userFunction4(const char &ch1, const char &ch2) +{ + return (ch1 ^ 1) < (ch2 ^ 1); +} + +class UserFunctor1 +{ +public: + UserFunctor1(int x = 1) : y(x) {} + + bool operator()(char ch1, char ch2) + { + return (ch1 ^ y) < (ch2 ^ y); + } + + char y; +}; + +void tst_QAlgorithms::qHeapSort() +{ + char array1[] = "3141592"; + ::qHeapSort((char *)array1, array1 + strlen(array1)); + QVERIFY(strcmp(array1, "1123459") == 0); + + ::qHeapSort((char *)array1, array1 + strlen(array1), qGreater()); + QVERIFY(strcmp(array1, "9543211") == 0); + + ::qHeapSort((char *)array1, array1 + strlen(array1), qLess()); + QVERIFY(strcmp(array1, "1123459") == 0); + { + char array2[] = "0123456789@ABCDE"; + ::qHeapSort((char *)array2, array2 + strlen(array2), userFunction1); + QVERIFY(strcmp(array2, "1032547698A@CBED") == 0); + } + + { + char array2[] = "0123456789@ABCDE"; + ::qHeapSort((char *)array2, array2 + strlen(array2), userFunction2); + QVERIFY(strcmp(array2, "1032547698A@CBED") == 0); + } + + { + char array2[] = "0123456789@ABCDE"; + ::qHeapSort((char *)array2, array2 + strlen(array2), userFunction3); + QVERIFY(strcmp(array2, "1032547698A@CBED") == 0); + } + + { + char array2[] = "0123456789@ABCDE"; + ::qHeapSort((char *)array2, array2 + strlen(array2), userFunction4); + QVERIFY(strcmp(array2, "1032547698A@CBED") == 0); + } + + { + UserFunctor1 userFunctor1; + char array2[] = "0123456789@ABCDE"; + ::qHeapSort((char *)array2, array2 + strlen(array2), userFunctor1); + QVERIFY(strcmp(array2, "1032547698A@CBED") == 0); + } + + { + char array2[] = "0123456789@ABCDE"; + ::qHeapSort((char *)array2, array2 + strlen(array2), UserFunctor1()); + QVERIFY(strcmp(array2, "1032547698A@CBED") == 0); + ::qHeapSort((char *)array2, array2 + strlen(array2), UserFunctor1(1)); + QVERIFY(strcmp(array2, "1032547698A@CBED") == 0); + ::qHeapSort((char *)array2, array2 + strlen(array2), UserFunctor1(3)); + QVERIFY(strcmp(array2, "3210765498CBA@ED") == 0); + ::qHeapSort((char *)array2, array2 + strlen(array2), UserFunctor1(0)); + QVERIFY(strcmp(array2, "0123456789@ABCDE") == 0); + } +} + +void tst_QAlgorithms::qBubbleSort() +{ + char array1[] = "3141592"; + ::qBubbleSort((char *)array1, array1 + strlen(array1)); + QVERIFY(strcmp(array1, "1123459") == 0); + + ::qBubbleSort((char *)array1, array1 + strlen(array1), qGreater()); + QVERIFY(strcmp(array1, "9543211") == 0); + + ::qBubbleSort((char *)array1, array1 + strlen(array1), qLess()); + QVERIFY(strcmp(array1, "1123459") == 0); + + { + char array2[] = "0123456789@ABCDE"; + ::qBubbleSort((char *)array2, array2 + strlen(array2), userFunction1); + QVERIFY(strcmp(array2, "1032547698A@CBED") == 0); + } + + { + char array2[] = "0123456789@ABCDE"; + ::qBubbleSort((char *)array2, array2 + strlen(array2), userFunction2); + QVERIFY(strcmp(array2, "1032547698A@CBED") == 0); + } + + { + char array2[] = "0123456789@ABCDE"; + ::qBubbleSort((char *)array2, array2 + strlen(array2), userFunction3); + QVERIFY(strcmp(array2, "1032547698A@CBED") == 0); + } + + { + char array2[] = "0123456789@ABCDE"; + ::qBubbleSort((char *)array2, array2 + strlen(array2), userFunction4); + QVERIFY(strcmp(array2, "1032547698A@CBED") == 0); + } + + { + UserFunctor1 userFunctor1; + char array2[] = "0123456789@ABCDE"; + ::qBubbleSort((char *)array2, array2 + strlen(array2), userFunctor1); + QVERIFY(strcmp(array2, "1032547698A@CBED") == 0); + } + + { + char array2[] = "0123456789@ABCDE"; + ::qBubbleSort((char *)array2, array2 + strlen(array2), UserFunctor1()); + QVERIFY(strcmp(array2, "1032547698A@CBED") == 0); + ::qBubbleSort((char *)array2, array2 + strlen(array2), UserFunctor1(1)); + QVERIFY(strcmp(array2, "1032547698A@CBED") == 0); + ::qBubbleSort((char *)array2, array2 + strlen(array2), UserFunctor1(3)); + QVERIFY(strcmp(array2, "3210765498CBA@ED") == 0); + ::qBubbleSort((char *)array2, array2 + strlen(array2), UserFunctor1(0)); + QVERIFY(strcmp(array2, "0123456789@ABCDE") == 0); + } +} + +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); + 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"); + } + + { + 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::sortEmptyList() +{ + // Only test if it crashes + QStringList stringList; + stringList.sort(); + QVERIFY(true); +} + +void tst_QAlgorithms::sortedList() +{ + QList list; + list << 4 << 3 << 6; + + ::qHeapSort(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); +} + +Q_DECLARE_METATYPE(QList) + +void tst_QAlgorithms::test_qLowerBound_data() +{ + QTest::addColumn >("data"); + QTest::addColumn("resultValue"); + QTest::addColumn("resultIndex"); + + QTest::newRow("sorted-duplicate") << (QList() << 1 << 2 << 2 << 3) << 2 << 1; +} + +void tst_QAlgorithms::test_qLowerBound() +{ + QFETCH(QList, 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()), data.constBegin() + resultIndex); +} + +void tst_QAlgorithms::test_qUpperBound_data() +{ + QTest::addColumn >("data"); + QTest::addColumn("resultValue"); + QTest::addColumn("resultIndex"); + + QTest::newRow("sorted-duplicate") << (QList() << 1 << 2 << 2 << 3) << 2 << 3; +} + +void tst_QAlgorithms::test_qUpperBound() +{ + QFETCH(QList, 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()), data.constBegin() + resultIndex); +} + +void tst_QAlgorithms::test_qBinaryFind_data() +{ + QTest::addColumn >("data"); + QTest::addColumn("resultValue"); // -42 means not found + + QTest::newRow("sorted-duplicate") << (QList() << 1 << 2 << 2 << 3) << 2; + QTest::newRow("sorted-end") << (QList() << -5 << -2 << 0 << 8) << 8; + QTest::newRow("sorted-beginning") << (QList() << -5 << -2 << 0 << 8) << -5; + QTest::newRow("sorted-duplicate-beginning") << (QList() << -5 << -5 << -2 << 0 << 8) << -5; + QTest::newRow("empty") << (QList()) << -42; + QTest::newRow("not found 1 ") << (QList() << 1 << 5 << 8 << 65) << -42; + QTest::newRow("not found 2 ") << (QList() << -456 << -5 << 8 << 65) << -42; +} + +void tst_QAlgorithms::test_qBinaryFind() +{ + QFETCH(QList, 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()) == 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()), resultValue); +} + +void tst_QAlgorithms::qBinaryFindOneEntry() +{ + QList list; + list << 2; + + QVERIFY(::qBinaryFind(list.constBegin(), list.constEnd(), 2) != list.constEnd()); +} + + +void tst_QAlgorithms::sortAPItest() +{ + QVector testVector = generateData("Random", 101); + qSort(testVector); + QVERIFY(isSorted(testVector)); + qSort(testVector.begin(), testVector.end()); + QVERIFY(isSorted(testVector)); + qSort(testVector.begin(), testVector.end(), qLess()); + QVERIFY(isSorted(testVector)); + + testVector = generateData("Random", 71); + qStableSort(testVector); + QVERIFY(isSorted(testVector)); + qStableSort(testVector.begin(), testVector.end()); + QVERIFY(isSorted(testVector)); + qStableSort(testVector.begin(), testVector.end(), qLess()); + QVERIFY(isSorted(testVector)); + + QList testList = generateData("Random", 101).toList(); + qSort(testList); + QVERIFY(isSorted(testList)); + qSort(testList.begin(), testList.end()); + QVERIFY(isSorted(testList)); + qSort(testList.begin(), testList.end(), qLess()); + QVERIFY(isSorted(testList)); + + testList = generateData("Random", 71).toList(); + qStableSort(testList); + QVERIFY(isSorted(testList)); + qStableSort(testList.begin(), testList.end()); + QVERIFY(isSorted(testList)); + qStableSort(testList.begin(), testList.end(), qLess()); + 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 createStableTestVector() +{ + QVector stableTestVector; + for (int i=500; i>=0; --i) { + for (int j=0; j<10; ++j) { + stableTestVector.append(StableSortTest(i, j)); + } + } + return stableTestVector; +} + +template +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 stableTestVector = createStableTestVector(); + qSort(stableTestVector.begin(), stableTestVector.end(), qLess()); + QVERIFY(isSorted(stableTestVector, qLess())); + QVERIFY(!isStableSorted(stableTestVector, qLess())); + } + { + QVector stableTestVector = createStableTestVector(); + qSort(stableTestVector.begin(), stableTestVector.end(), qGreater()); + QVERIFY(isSorted(stableTestVector, qGreater())); + QVERIFY(!isStableSorted(stableTestVector, qGreater())); + } + { + QVector stableTestVector = createStableTestVector(); + qSort(stableTestVector.begin(), stableTestVector.end(), qGreater()); + QVERIFY(!isSorted(stableTestVector, qLess())); + QVERIFY(!isStableSorted(stableTestVector, qGreater())); + } + + + // Stable sort with qLess + { + QVector stableTestVector = createStableTestVector(); + std::stable_sort(stableTestVector.begin(), stableTestVector.end(), qLess()); + QVERIFY(isSorted(stableTestVector, qLess())); + QVERIFY(isStableSorted(stableTestVector, qLess())); + } + { + QVector stableTestVector = createStableTestVector(); + qStableSort(stableTestVector.begin(), stableTestVector.end(), qLess()); + QVERIFY(isSorted(stableTestVector, qLess())); + QVERIFY(isStableSorted(stableTestVector, qLess())); + } + + // Stable sort with qGreater + { + QVector stableTestVector = createStableTestVector(); + std::stable_sort(stableTestVector.begin(), stableTestVector.end(), qGreater()); + QVERIFY(isSorted(stableTestVector, qGreater())); + QVERIFY(isStableSorted(stableTestVector, qGreater())); + } + + { + QVector stableTestVector = createStableTestVector(); + qStableSort(stableTestVector.begin(), stableTestVector.end(), qGreater()); + QVERIFY(isSorted(stableTestVector, qGreater())); + QVERIFY(isStableSorted(stableTestVector, qGreater())); + } +} + +Q_DECLARE_METATYPE(QVector) + +void tst_QAlgorithms::stableSortCorrectnessTest_data() +{ + const int dataSize = 1000; + QTest::addColumn >("unsorted"); + QTest::newRow("From documentation") << (QVector() << 33 << 12 << 68 << 6 << 12); + QTest::newRow("Equal") << (generateData("Equal", dataSize)); + QTest::newRow("Ascending") << (generateData("Ascending", dataSize)); + QTest::newRow("Descending") << (generateData("Descending", dataSize)); + QTest::newRow("Duplicates") << (generateData("Duplicates", dataSize)); + QTest::newRow("Almost Sorted") << (generateData("Almost Sorted", dataSize)); + QTest::newRow("Random") << (generateData("Random", dataSize)); +} + +void tst_QAlgorithms::stableSortCorrectnessTest() +{ + QFETCH(QVector, unsorted); + + QVector 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() +{ + // Compile-test for QAlgorithm convenience functions. + QList 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()); + + qStableSort(list); + qStableSort(list.begin(), list.end()); + qStableSort(list.begin(), list.end(), qLess()); + + qLowerBound(list, 1);; + qLowerBound(list.begin(), list.end(), 1); + qLowerBound(list.begin(), list.end(), 1, qLess()); + + qUpperBound(list, 1); + qUpperBound(list.begin(), list.end(), 1); + qUpperBound(list.begin(), list.end(), 1, qLess()); + + qBinaryFind(list, 1); + qBinaryFind(list.begin(), list.end(), 1); + qBinaryFind(list.begin(), list.end(), 1, qLess()); + + QList pointerList; + qDeleteAll(pointerList); + qDeleteAll(pointerList.begin(), pointerList.end()); +} + +template +class HeapSortHelper +{ +public: + void operator()(QVector list) + { + ::qHeapSort(list); + } +}; + +template +class BubbleSortHelper +{ +public: + void operator()(QVector list) + { + ::qBubbleSort(list); + } +}; + +template +class QuickSortHelper +{ +public: + void operator()(QVector list) + { + ::qSort(list); + } +}; + +template +class StableSortHelper +{ +public: + void operator()(QVector list) + { + ::qStableSort(list); + } +}; + +template +class StlSortHelper +{ +public: + void operator()(QVector list) + { + std::sort(list.begin(), list.end()); + } +}; + +template +class StlStableSortHelper +{ +public: + void operator()(QVector list) + { + std::stable_sort(list.begin(), list.end()); + } +}; + +#if Q_TEST_PERFORMANCE +void tst_QAlgorithms::performance() +{ + cout << endl << "Quick sort" << endl; + testAlgorithm, TestInt>(QuickSortHelper(), dataSetTypes); + cout << endl << "stable sort" << endl; + testAlgorithm, TestInt>(StableSortHelper(), dataSetTypes); + cout << endl << "std::sort" << endl; + testAlgorithm, TestInt>(StlSortHelper(), dataSetTypes); + cout << endl << "std::stable_sort" << endl; + testAlgorithm, TestInt>(StlStableSortHelper(), dataSetTypes); + cout << "Heap sort" << endl; + testAlgorithm, TestInt>(HeapSortHelper(), dataSetTypes); + cout << endl << "Bubble sort" << endl; + testAlgorithm, TestInt>(BubbleSortHelper(), dataSetTypes); +/* + cout << endl << "Sorting lists of ints" << endl; + cout << "Heap sort" << endl; + testAlgorithm, int>(HeapSortHelper(), dataSetTypes); + cout << endl << "Quick sort" << endl; + testAlgorithm, int>(QuickSortHelper(), dataSetTypes); + cout << endl << "std::sort" << endl; + testAlgorithm, int>(StlSortHelper(), dataSetTypes); + cout << endl << "std::stable_sort" << endl; + testAlgorithm, int>(StlStableSortHelper(), dataSetTypes); + cout << endl << "Bubble sort" << endl; + testAlgorithm, int>(BubbleSortHelper(), dataSetTypes); +*/ +} +#endif + +void tst_QAlgorithms::qCountIterators() const +{ + QList 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 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: + 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); +} + +QTEST_APPLESS_MAIN(tst_QAlgorithms) +#include "tst_qalgorithms.moc" + -- cgit v1.2.3