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

**

** All rights reserved.

** Contact: Nokia Corporation (qt-info@nokia.com)

**

** This file is part of the QtCore 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 QALGORITHMS_H

#define QALGORITHMS_H

#include <QtCore/qglobal.h>

QT_BEGIN_HEADER

QT_BEGIN_NAMESPACE

QT_MODULE(Core)

/*

    Warning: The contents of QAlgorithmsPrivate is not a part of the public Qt API

    and may be changed from version to version or even be completely removed.

*/

namespace QAlgorithmsPrivate {

template <typename RandomAccessIterator, typename T, typename LessThan>

Q_OUTOFLINE_TEMPLATE void qSortHelper(RandomAccessIterator start, RandomAccessIterator end, const T &t, LessThan lessThan);

template <typename RandomAccessIterator, typename T>

inline void qSortHelper(RandomAccessIterator begin, RandomAccessIterator end, const T &dummy);

template <typename RandomAccessIterator, typename T, typename LessThan>

Q_OUTOFLINE_TEMPLATE void qStableSortHelper(RandomAccessIterator start, RandomAccessIterator end, const T &t, LessThan lessThan);

template <typename RandomAccessIterator, typename T>

inline void qStableSortHelper(RandomAccessIterator, RandomAccessIterator, const T &);

template <typename RandomAccessIterator, typename T, typename LessThan>

Q_OUTOFLINE_TEMPLATE RandomAccessIterator qLowerBoundHelper(RandomAccessIterator begin, RandomAccessIterator end, const T &value, LessThan lessThan);

template <typename RandomAccessIterator, typename T, typename LessThan>

Q_OUTOFLINE_TEMPLATE RandomAccessIterator qUpperBoundHelper(RandomAccessIterator begin, RandomAccessIterator end, const T &value, LessThan lessThan);

template <typename RandomAccessIterator, typename T, typename LessThan>

Q_OUTOFLINE_TEMPLATE RandomAccessIterator qBinaryFindHelper(RandomAccessIterator begin, RandomAccessIterator end, const T &value, LessThan lessThan);

}

template <typename InputIterator, typename OutputIterator>

inline OutputIterator qCopy(InputIterator begin, InputIterator end, OutputIterator dest)

{

    while (begin != end)

        *dest++ = *begin++;

    return dest;

}

template <typename BiIterator1, typename BiIterator2>

inline BiIterator2 qCopyBackward(BiIterator1 begin, BiIterator1 end, BiIterator2 dest)

{

    while (begin != end)

        *--dest = *--end;

    return dest;

}

template <typename InputIterator1, typename InputIterator2>

inline bool qEqual(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2)

{

    for (; first1 != last1; ++first1, ++first2)

        if (!(*first1 == *first2))

            return false;

    return true;

}

template <typename ForwardIterator, typename T>

inline void qFill(ForwardIterator first, ForwardIterator last, const T &val)

{

    for (; first != last; ++first)

        *first = val;

}

template <typename Container, typename T>

inline void qFill(Container &container, const T &val)

{

    qFill(container.begin(), container.end(), val);

}

template <typename InputIterator, typename T>

inline InputIterator qFind(InputIterator first, InputIterator last, const T &val)

{

    while (first != last && !(*first == val))

        ++first;

    return first;

}

template <typename Container, typename T>

inline typename Container::const_iterator qFind(const Container &container, const T &val)

{

    return qFind(container.constBegin(), container.constEnd(), val);

}

template <typename InputIterator, typename T, typename Size>

inline void qCount(InputIterator first, InputIterator last, const T &value, Size &n)

{

    for (; first != last; ++first)

        if (*first == value)

            ++n;

}

template <typename Container, typename T, typename Size>

inline void qCount(const Container &container, const T &value, Size &n)

{

    qCount(container.constBegin(), container.constEnd(), value, n);

}

#ifdef qdoc

template <typename T>

LessThan qLess()

{

}

template <typename T>

LessThan qGreater()

{

}

#else

template <typename T>

class qLess

{

public:

    inline bool operator()(const T &t1, const T &t2) const

    {

        return (t1 < t2);

    }

};

template <typename T>

class qGreater

{

public:

    inline bool operator()(const T &t1, const T &t2) const

    {

        return (t2 < t1);

    }

};

#endif

template <typename RandomAccessIterator>

inline void qSort(RandomAccessIterator start, RandomAccessIterator end)

{

    if (start != end)

        QAlgorithmsPrivate::qSortHelper(start, end, *start);

}

template <typename RandomAccessIterator, typename LessThan>

inline void qSort(RandomAccessIterator start, RandomAccessIterator end, LessThan lessThan)

{

    if (start != end)

        QAlgorithmsPrivate::qSortHelper(start, end, *start, lessThan);

}

template<typename Container>

inline void qSort(Container &c)

{

#ifdef Q_CC_BOR

    // Work around Borland 5.5 optimizer bug

    c.detach();

#endif

    if (!c.empty())

        QAlgorithmsPrivate::qSortHelper(c.begin(), c.end(), *c.begin());

}

template <typename RandomAccessIterator>

inline void qStableSort(RandomAccessIterator start, RandomAccessIterator end)

{

    if (start != end)

        QAlgorithmsPrivate::qStableSortHelper(start, end, *start);

}

template <typename RandomAccessIterator, typename LessThan>

inline void qStableSort(RandomAccessIterator start, RandomAccessIterator end, LessThan lessThan)

{

    if (start != end)

        QAlgorithmsPrivate::qStableSortHelper(start, end, *start, lessThan);

}

template<typename Container>

inline void qStableSort(Container &c)

{

#ifdef Q_CC_BOR

    // Work around Borland 5.5 optimizer bug

    c.detach();

#endif

    if (!c.empty())

        QAlgorithmsPrivate::qStableSortHelper(c.begin(), c.end(), *c.begin());

}

template <typename RandomAccessIterator, typename T>

Q_OUTOFLINE_TEMPLATE RandomAccessIterator qLowerBound(RandomAccessIterator begin, RandomAccessIterator end, const T &value)

{

    // Implementation is duplicated from QAlgorithmsPrivate to keep existing code

    // compiling. We have to allow using *begin and value with different types,

    // and then implementing operator< for those types.

    RandomAccessIterator middle;

    int n = end - begin;

    int half;

    while (n > 0) {

        half = n >> 1;

        middle = begin + half;

        if (*middle < value) {

            begin = middle + 1;

            n -= half + 1;

        } else {

            n = half;

        }

    }

    return begin;

}

template <typename RandomAccessIterator, typename T, typename LessThan>

Q_OUTOFLINE_TEMPLATE RandomAccessIterator qLowerBound(RandomAccessIterator begin, RandomAccessIterator end, const T &value, LessThan lessThan)

{

    return QAlgorithmsPrivate::qLowerBoundHelper(begin, end, value, lessThan);

}

template <typename Container, typename T>

Q_OUTOFLINE_TEMPLATE typename Container::const_iterator qLowerBound(const Container &container, const T &value)

{

    return QAlgorithmsPrivate::qLowerBoundHelper(container.constBegin(), container.constEnd(), value, qLess<T>());

}

template <typename RandomAccessIterator, typename T>

Q_OUTOFLINE_TEMPLATE RandomAccessIterator qUpperBound(RandomAccessIterator begin, RandomAccessIterator end, const T &value)

{

    // Implementation is duplicated from QAlgorithmsPrivate.

    RandomAccessIterator middle;

    int n = end - begin;

    int half;

    while (n > 0) {

        half = n >> 1;

        middle = begin + half;

        if (value < *middle) {

            n = half;

        } else {

            begin = middle + 1;

            n -= half + 1;

        }

    }

    return begin;

}

template <typename RandomAccessIterator, typename T, typename LessThan>

Q_OUTOFLINE_TEMPLATE RandomAccessIterator qUpperBound(RandomAccessIterator begin, RandomAccessIterator end, const T &value, LessThan lessThan)

{

    return QAlgorithmsPrivate::qUpperBoundHelper(begin, end, value, lessThan);

}

template <typename Container, typename T>

Q_OUTOFLINE_TEMPLATE typename Container::const_iterator qUpperBound(const Container &container, const T &value)

{

    return QAlgorithmsPrivate::qUpperBoundHelper(container.constBegin(), container.constEnd(), value, qLess<T>());

}

template <typename RandomAccessIterator, typename T>

Q_OUTOFLINE_TEMPLATE RandomAccessIterator qBinaryFind(RandomAccessIterator begin, RandomAccessIterator end, const T &value)

{

    // Implementation is duplicated from QAlgorithmsPrivate.

    RandomAccessIterator it = qLowerBound(begin, end, value);

    if (it == end || value < *it)

        return end;

    return it;

}

template <typename RandomAccessIterator, typename T, typename LessThan>

Q_OUTOFLINE_TEMPLATE RandomAccessIterator qBinaryFind(RandomAccessIterator begin, RandomAccessIterator end, const T &value, LessThan lessThan)

{

    return QAlgorithmsPrivate::qBinaryFindHelper(begin, end, value, lessThan);

}

template <typename Container, typename T>

Q_OUTOFLINE_TEMPLATE typename Container::const_iterator qBinaryFind(const Container &container, const T &value)

{

    return QAlgorithmsPrivate::qBinaryFindHelper(container.constBegin(), container.constEnd(), value, qLess<T>());

}

template <typename ForwardIterator>

Q_OUTOFLINE_TEMPLATE void qDeleteAll(ForwardIterator begin, ForwardIterator end)

{

    while (begin != end) {

        delete *begin;

        ++begin;

    }

}

template <typename Container>

inline void qDeleteAll(const Container &c)

{

    qDeleteAll(c.begin(), c.end());

}

/*

    Warning: The contents of QAlgorithmsPrivate is not a part of the public Qt API

    and may be changed from version to version or even be completely removed.

*/

namespace QAlgorithmsPrivate {

template <typename RandomAccessIterator, typename T, typename LessThan>

Q_OUTOFLINE_TEMPLATE void qSortHelper(RandomAccessIterator start, RandomAccessIterator end, const T &t, LessThan lessThan)

{

top:

    int span = int(end - start);

    if (span < 2)

        return;

    --end;

    RandomAccessIterator low = start, high = end - 1;

    RandomAccessIterator pivot = start + span / 2;

    if (lessThan(*end, *start))

        qSwap(*end, *start);

    if (span == 2)

        return;

    if (lessThan(*pivot, *start))

        qSwap(*pivot, *start);

    if (lessThan(*end, *pivot))

        qSwap(*end, *pivot);

    if (span == 3)

        return;

    qSwap(*pivot, *end);

    while (low < high) {

        while (low < high && lessThan(*low, *end))

            ++low;

        while (high > low && lessThan(*end, *high))

            --high;

        if (low < high) {

            qSwap(*low, *high);

            ++low;

            --high;

        } else {

            break;

        }

    }

    if (lessThan(*low, *end))

        ++low;

    qSwap(*end, *low);

    qSortHelper(start, low, t, lessThan);

    start = low + 1;

    ++end;

    goto top;

}

template <typename RandomAccessIterator, typename T>

inline void qSortHelper(RandomAccessIterator begin, RandomAccessIterator end, const T &dummy)

{

    qSortHelper(begin, end, dummy, qLess<T>());

}

template <typename RandomAccessIterator>

Q_OUTOFLINE_TEMPLATE void qReverse(RandomAccessIterator begin, RandomAccessIterator end)

{

    --end;

    while (begin < end)

        qSwap(*begin++, *end--);

}

template <typename RandomAccessIterator>

Q_OUTOFLINE_TEMPLATE void qRotate(RandomAccessIterator begin, RandomAccessIterator middle, RandomAccessIterator end)

{

    qReverse(begin, middle);

    qReverse(middle, end);

    qReverse(begin, end);

}

template <typename RandomAccessIterator, typename T, typename LessThan>

Q_OUTOFLINE_TEMPLATE void qMerge(RandomAccessIterator begin, RandomAccessIterator pivot, RandomAccessIterator end, T &t, LessThan lessThan)

{

    const int len1 = pivot - begin;

    const int len2 = end - pivot;

    if (len1 == 0 || len2 == 0)

        return;

    if (len1 + len2 == 2) {

        if (lessThan(*(begin + 1), *(begin)))

            qSwap(*begin, *(begin + 1));

        return;

    }

    RandomAccessIterator firstCut;

    RandomAccessIterator secondCut;

    int len2Half;

    if (len1 > len2) {

        const int len1Half = len1 / 2;

        firstCut = begin + len1Half;

        secondCut = qLowerBound(pivot, end, *firstCut, lessThan);

        len2Half = secondCut - pivot;

    } else {

        len2Half = len2 / 2;

        secondCut = pivot + len2Half;

        firstCut = qUpperBound(begin, pivot, *secondCut, lessThan);

    }

    qRotate(firstCut, pivot, secondCut);

    const RandomAccessIterator newPivot = firstCut + len2Half;

    qMerge(begin, firstCut, newPivot, t, lessThan);

    qMerge(newPivot, secondCut, end, t, lessThan);

}

template <typename RandomAccessIterator, typename T, typename LessThan>

Q_OUTOFLINE_TEMPLATE void qStableSortHelper(RandomAccessIterator begin, RandomAccessIterator end, const T &t, LessThan lessThan)

{

    const int span = end - begin;

    if (span < 2)

       return;

    const RandomAccessIterator middle = begin + span / 2;

    qStableSortHelper(begin, middle, t, lessThan);

    qStableSortHelper(middle, end, t, lessThan);

    qMerge(begin, middle, end, t, lessThan);

}

template <typename RandomAccessIterator, typename T>

inline void qStableSortHelper(RandomAccessIterator begin, RandomAccessIterator end, const T &dummy)

{

    qStableSortHelper(begin, end, dummy, qLess<T>());

}

template <typename RandomAccessIterator, typename T, typename LessThan>

Q_OUTOFLINE_TEMPLATE RandomAccessIterator qLowerBoundHelper(RandomAccessIterator begin, RandomAccessIterator end, const T &value, LessThan lessThan)

{

    RandomAccessIterator middle;

    int n = int(end - begin);

    int half;

    while (n > 0) {

        half = n >> 1;

        middle = begin + half;

        if (lessThan(*middle, value)) {

            begin = middle + 1;

            n -= half + 1;

        } else {

            n = half;

        }

    }

    return begin;

}

template <typename RandomAccessIterator, typename T, typename LessThan>

Q_OUTOFLINE_TEMPLATE RandomAccessIterator qUpperBoundHelper(RandomAccessIterator begin, RandomAccessIterator end, const T &value, LessThan lessThan)

{

    RandomAccessIterator middle;

    int n = end - begin;

    int half;

    while (n > 0) {

        half = n >> 1;

        middle = begin + half;

        if (lessThan(value, *middle)) {

            n = half;

        } else {

            begin = middle + 1;

            n -= half + 1;

        }

    }

    return begin;

}

template <typename RandomAccessIterator, typename T, typename LessThan>

Q_OUTOFLINE_TEMPLATE RandomAccessIterator qBinaryFindHelper(RandomAccessIterator begin, RandomAccessIterator end, const T &value, LessThan lessThan)

{

    RandomAccessIterator it = qLowerBoundHelper(begin, end, value, lessThan);

    if (it == end || lessThan(value, *it))

        return end;

    return it;

}

} //namespace QAlgorithmsPrivate

QT_END_NAMESPACE

QT_END_HEADER

#endif // QALGORITHMS_H