diff options
Diffstat (limited to 'src/corelib/tools/qalgorithms.h')
| -rw-r--r-- | src/corelib/tools/qalgorithms.h | 526 |
1 files changed, 526 insertions, 0 deletions
diff --git a/src/corelib/tools/qalgorithms.h b/src/corelib/tools/qalgorithms.h new file mode 100644 index 0000000000..6b870397b6 --- /dev/null +++ b/src/corelib/tools/qalgorithms.h @@ -0,0 +1,526 @@ +/**************************************************************************** +** +** 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$ +** 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 |