/**************************************************************************** | |
** | |
** 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 QtCore module of the Qt Toolkit. | |
** | |
** $QT_BEGIN_LICENSE:LGPL$ | |
** GNU Lesser General Public License Usage | |
** 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. | |
** | |
** GNU General Public License Usage | |
** Alternatively, this file may be used under the terms of the GNU General | |
** Public License version 3.0 as published by the Free Software Foundation | |
** and appearing in the file LICENSE.GPL included in the packaging of this | |
** file. Please review the following information to ensure the GNU General | |
** Public License version 3.0 requirements will be met: | |
** http://www.gnu.org/copyleft/gpl.html. | |
** | |
** Other Usage | |
** Alternatively, this file may be used in accordance with the terms and | |
** conditions contained in a signed written agreement between you and Nokia. | |
** | |
** | |
** | |
** | |
** | |
** $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 |