/****************************************************************************

**

** Copyright (C) 2010 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 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();