summaryrefslogtreecommitdiffstats
path: root/tests/auto/qalgorithms
diff options
context:
space:
mode:
Diffstat (limited to 'tests/auto/qalgorithms')
-rw-r--r--tests/auto/qalgorithms/.gitignore1
-rw-r--r--tests/auto/qalgorithms/q3tl.h212
-rw-r--r--tests/auto/qalgorithms/qalgorithms.pro5
-rw-r--r--tests/auto/qalgorithms/tst_qalgorithms.cpp1223
4 files changed, 1441 insertions, 0 deletions
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 <QtCore/qalgorithms.h>
+
+QT_BEGIN_HEADER
+
+QT_BEGIN_NAMESPACE
+
+QT_MODULE(Qt3SupportLight)
+
+template <typename T, typename LessThan>
+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 <typename BiIterator, typename T, typename LessThan>
+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 <typename BiIterator, typename T>
+inline void qHeapSortHelper(BiIterator begin, BiIterator end, const T &dummy)
+{
+ qHeapSortHelper(begin, end, dummy, qLess<T>());
+}
+
+template <typename BiIterator, typename LessThan>
+inline void qHeapSort(BiIterator begin, BiIterator end, LessThan lessThan)
+{
+ if (begin != end)
+ qHeapSortHelper(begin, end, *begin, lessThan);
+}
+
+template <typename BiIterator>
+inline void qHeapSort(BiIterator begin, BiIterator end)
+{
+ if (begin != end)
+ qHeapSortHelper(begin, end, *begin);
+}
+
+template <typename Container>
+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 <typename BiIterator, typename LessThan>
+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 <typename BiIterator, typename T>
+void qBubbleSortHelper(BiIterator begin, BiIterator end, T)
+{
+ qBubbleSort(begin, end, qLess<T>());
+}
+
+template <typename BiIterator>
+void qBubbleSort(BiIterator begin, BiIterator end)
+{
+ if (begin != end)
+ qBubbleSortHelper(begin, end, *begin);
+}
+
+template <typename Container>
+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 <QtTest/QtTest>
+
+#include <iostream>
+#include <iomanip>
+#include <sstream>
+#include <algorithm>
+#include <qalgorithms.h>
+#include "../../../src/qt3support/tools/q3tl.h"
+#include <QStringList>
+#include <QString>
+#include <QVector>
+
+#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 <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(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 <typename ContainerType, typename Algorithm>
+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 <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<Q_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 << endl;
+}
+
+template <typename ContainerType>
+void print(ContainerType testContainer)
+{
+ typedef typename ContainerType::value_type T;
+
+ foreach(T value, testContainer) {
+ cout << value << " ";
+ }
+
+ cout << 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));
+ Q_ASSERT(isSorted(container));
+ }
+ 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 << 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<char>());
+ QVERIFY(strcmp(array1, "9543211") == 0);
+
+ ::qHeapSort((char *)array1, array1 + strlen(array1), qLess<char>());
+ 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<char>());
+ QVERIFY(strcmp(array1, "9543211") == 0);
+
+ ::qBubbleSort((char *)array1, array1 + strlen(array1), qLess<char>());
+ 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<int> 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<int>)
+
+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>()));
+ }
+}
+
+Q_DECLARE_METATYPE(QVector<int>)
+
+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()
+{
+ // 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>());
+
+ QList<int *> pointerList;
+ qDeleteAll(pointerList);
+ qDeleteAll(pointerList.begin(), pointerList.end());
+}
+
+template <typename DataType>
+class HeapSortHelper
+{
+public:
+ void operator()(QVector<DataType> list)
+ {
+ ::qHeapSort(list);
+ }
+};
+
+template <typename DataType>
+class BubbleSortHelper
+{
+public:
+ void operator()(QVector<DataType> list)
+ {
+ ::qBubbleSort(list);
+ }
+};
+
+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 << endl << "Quick sort" << endl;
+ testAlgorithm<QuickSortHelper<TestInt>, TestInt>(QuickSortHelper<TestInt>(), dataSetTypes);
+ cout << endl << "stable sort" << endl;
+ testAlgorithm<StableSortHelper<TestInt>, TestInt>(StableSortHelper<TestInt>(), dataSetTypes);
+ cout << endl << "std::sort" << endl;
+ testAlgorithm<StlSortHelper<TestInt>, TestInt>(StlSortHelper<TestInt>(), dataSetTypes);
+ cout << endl << "std::stable_sort" << endl;
+ testAlgorithm<StlStableSortHelper<TestInt>, TestInt>(StlStableSortHelper<TestInt>(), dataSetTypes);
+ cout << "Heap sort" << endl;
+ testAlgorithm<HeapSortHelper<TestInt>, TestInt>(HeapSortHelper<TestInt>(), dataSetTypes);
+ cout << endl << "Bubble sort" << endl;
+ testAlgorithm<BubbleSortHelper<TestInt>, TestInt>(BubbleSortHelper<TestInt>(), dataSetTypes);
+/*
+ cout << endl << "Sorting lists of ints" << endl;
+ cout << "Heap sort" << endl;
+ testAlgorithm<HeapSortHelper<int>, int>(HeapSortHelper<int>(), dataSetTypes);
+ cout << endl << "Quick sort" << endl;
+ testAlgorithm<QuickSortHelper<int>, int>(QuickSortHelper<int>(), dataSetTypes);
+ cout << endl << "std::sort" << endl;
+ testAlgorithm<StlSortHelper<int>, int>(StlSortHelper<int>(), dataSetTypes);
+ cout << endl << "std::stable_sort" << endl;
+ testAlgorithm<StlStableSortHelper<int>, int>(StlStableSortHelper<int>(), dataSetTypes);
+ cout << endl << "Bubble sort" << endl;
+ testAlgorithm<BubbleSortHelper<int>, int>(BubbleSortHelper<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:
+ 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"
+
generated by cgit v1.2.3 (git 2.25.1) at 2024-05-02 11:00:15 +0000