<commit_before>/****************************************************************************
**
** Copyright (C) 2009 Nokia Corporation and/or its subsidiary(-ies).
** All rights reserved.
** Contact: Nokia Corporation (<EMAIL>)
**
** 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 <EMAIL>.
**
**
**
**
**
**
**
**
** $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 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);
    }
}

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");

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

void tst_QAlgorithms::test_qBinaryFind()
{
    QFETCH(QList<int>, data);
    QFETCH(int, resultValue);

    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);
}<commit_msg>Extand test of qBinaryFind<commit_after>/****************************************************************************
**
** Copyright (C) 2009 Nokia Corporation and/or its subsidiary(-ies).
** All rights reserved.
** Contact: Nokia Corporation (<EMAIL>)
**
** 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 <EMAIL>.
**
**
**
**
**
**
**
**
** $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 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);
    }
}

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.end());
        QVERIFY(qBinaryFind(data, resultValue) == data.end());
        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);
}
{'fraction_non_alphanumeric': 0.17209545375370144, 'fraction_numerical': 0.043894791848110085, 'mean_word_length': 3.1412599182495793, 'pattern_counts': {'":': 0, '<': 454, '<?xml version=': 0, '>': 120, 'https://': 0, 'lorem ipsum': 0, 'www.': 2, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '5889382', 'n_tokens_mistral': 13023, 'n_tokens_neox': 12079, 'n_words': 2602}