- Main Page
- Related Pages
- Modules
- Namespaces
- Classes
- Files
- Directories
- Examples

- File List
- File Members

# qalgorithms.h

Go to the documentation of this file.

    00001 /****************************************************************************
    00002 **
    00003 ** Copyright (C) 2010 Nokia Corporation and/or its subsidiary(-ies).
    00004 ** All rights reserved.
    00005 ** Contact: Nokia Corporation (qt-info@nokia.com)
    00006 **
    00007 ** This file is part of the QtCore module of the Qt Toolkit.
    00008 **
    00009 ** $QT_BEGIN_LICENSE:LGPL$
    00010 ** Commercial Usage
    00011 ** Licensees holding valid Qt Commercial licenses may use this file in
    00012 ** accordance with the Qt Commercial License Agreement provided with the
    00013 ** Software or, alternatively, in accordance with the terms contained in
    00014 ** a written agreement between you and Nokia.
    00015 **
    00016 ** GNU Lesser General Public License Usage
    00017 ** Alternatively, this file may be used under the terms of the GNU Lesser
    00018 ** General Public License version 2.1 as published by the Free Software
    00019 ** Foundation and appearing in the file LICENSE.LGPL included in the
    00020 ** packaging of this file.  Please review the following information to
    00021 ** ensure the GNU Lesser General Public License version 2.1 requirements
    00022 ** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.
    00023 **
    00024 ** In addition, as a special exception, Nokia gives you certain additional
    00025 ** rights.  These rights are described in the Nokia Qt LGPL Exception
    00026 ** version 1.1, included in the file LGPL_EXCEPTION.txt in this module.
    00027 **
    00028 ** GNU General Public License Usage
    00029 ** Alternatively, this file may be used under the terms of the GNU
    00030 ** General Public License version 3.0 as published by the Free Software
    00031 ** Foundation and appearing in the file LICENSE.GPL included in the
    00032 ** packaging of this file.  Please review the following information to
    00033 ** ensure the GNU General Public License version 3.0 requirements will be
    00034 ** met: http://www.gnu.org/copyleft/gpl.html.
    00035 **
    00036 ** If you have questions regarding the use of this file, please contact
    00037 ** Nokia at qt-info@nokia.com.
    00038 ** $QT_END_LICENSE$
    00039 **
    00040 ****************************************************************************/
    00041
    00042 #ifndef QALGORITHMS_H
    00043 #define QALGORITHMS_H
    00044
    00045 #include <QtCore/qglobal.h>
    00046
    00047 QT_BEGIN_HEADER
    00048
    00049 QT_BEGIN_NAMESPACE
    00050
    00051 QT_MODULE(Core)
    00052
    00053 /*
    00054     Warning: The contents of QAlgorithmsPrivate is not a part of the public Qt API
    00055     and may be changed from version to version or even be completely removed.
    00056 */
    00057 namespace QAlgorithmsPrivate {
    00058
    00059 template <typename RandomAccessIterator, typename T, typename LessThan>
    00060 Q_OUTOFLINE_TEMPLATE void qSortHelper(RandomAccessIterator start, RandomAccessIterator end, const T &t, LessThan lessThan);
    00061 template <typename RandomAccessIterator, typename T>
    00062 inline void qSortHelper(RandomAccessIterator begin, RandomAccessIterator end, const T &dummy);
    00063
    00064 template <typename RandomAccessIterator, typename T, typename LessThan>
    00065 Q_OUTOFLINE_TEMPLATE void qStableSortHelper(RandomAccessIterator start, RandomAccessIterator end, const T &t, LessThan lessThan);
    00066 template <typename RandomAccessIterator, typename T>
    00067 inline void qStableSortHelper(RandomAccessIterator, RandomAccessIterator, const T &);
    00068
    00069 template <typename RandomAccessIterator, typename T, typename LessThan>
    00070 Q_OUTOFLINE_TEMPLATE RandomAccessIterator qLowerBoundHelper(RandomAccessIterator begin, RandomAccessIterator end, const T &value, LessThan lessThan);
    00071 template <typename RandomAccessIterator, typename T, typename LessThan>
    00072 Q_OUTOFLINE_TEMPLATE RandomAccessIterator qUpperBoundHelper(RandomAccessIterator begin, RandomAccessIterator end, const T &value, LessThan lessThan);
    00073 template <typename RandomAccessIterator, typename T, typename LessThan>
    00074 Q_OUTOFLINE_TEMPLATE RandomAccessIterator qBinaryFindHelper(RandomAccessIterator begin, RandomAccessIterator end, const T &value, LessThan lessThan);
    00075
    00076 }
    00077
    00078 template <typename InputIterator, typename OutputIterator>
    00079 inline OutputIterator qCopy(InputIterator begin, InputIterator end, OutputIterator dest)
    00080 {
    00081     while (begin != end)
    00082         *dest++ = *begin++;
    00083     return dest;
    00084 }
    00085
    00086 template <typename BiIterator1, typename BiIterator2>
    00087 inline BiIterator2 qCopyBackward(BiIterator1 begin, BiIterator1 end, BiIterator2 dest)
    00088 {
    00089     while (begin != end)
    00090         *--dest = *--end;
    00091     return dest;
    00092 }
    00093
    00094 template <typename InputIterator1, typename InputIterator2>
    00095 inline bool qEqual(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2)
    00096 {
    00097     for (; first1 != last1; ++first1, ++first2)
    00098         if (!(*first1 == *first2))
    00099             return false;
    00100     return true;
    00101 }
    00102
    00103 template <typename ForwardIterator, typename T>
    00104 inline void qFill(ForwardIterator first, ForwardIterator last, const T &val)
    00105 {
    00106     for (; first != last; ++first)
    00107         *first = val;
    00108 }
    00109
    00110 template <typename Container, typename T>
    00111 inline void qFill(Container &container, const T &val)
    00112 {
    00113     qFill(container.begin(), container.end(), val);
    00114 }
    00115
    00116 template <typename InputIterator, typename T>
    00117 inline InputIterator qFind(InputIterator first, InputIterator last, const T &val)
    00118 {
    00119     while (first != last && !(*first == val))
    00120         ++first;
    00121     return first;
    00122 }
    00123
    00124 template <typename Container, typename T>
    00125 inline typename Container::const_iterator qFind(const Container &container, const T &val)
    00126 {
    00127     return qFind(container.constBegin(), container.constEnd(), val);
    00128 }
    00129
    00130 template <typename InputIterator, typename T, typename Size>
    00131 inline void qCount(InputIterator first, InputIterator last, const T &value, Size &n)
    00132 {
    00133     for (; first != last; ++first)
    00134         if (*first == value)
    00135             ++n;
    00136 }
    00137
    00138 template <typename Container, typename T, typename Size>
    00139 inline void qCount(const Container &container, const T &value, Size &n)
    00140 {
    00141     qCount(container.constBegin(), container.constEnd(), value, n);
    00142 }
    00143
    00144 #ifdef qdoc
    00145 template <typename T>
    00146 LessThan qLess()
    00147 {
    00148 }
    00149
    00150 template <typename T>
    00151 LessThan qGreater()
    00152 {
    00153 }
    00154 #else
    00155 template <typename T>
    00156 class qLess
    00157 {
    00158 public:
    00159     inline bool operator()(const T &t1, const T &t2) const
    00160     {
    00161         return (t1 < t2);
    00162     }
    00163 };
    00164
    00165 template <typename T>
    00166 class qGreater
    00167 {
    00168 public:
    00169     inline bool operator()(const T &t1, const T &t2) const
    00170     {
    00171         return (t2 < t1);
    00172     }
    00173 };
    00174 #endif
    00175
    00176 template <typename RandomAccessIterator>
    00177 inline void qSort(RandomAccessIterator start, RandomAccessIterator end)
    00178 {
    00179     if (start != end)
    00180         QAlgorithmsPrivate::qSortHelper(start, end, *start);
    00181 }
    00182
    00183 template <typename RandomAccessIterator, typename LessThan>
    00184 inline void qSort(RandomAccessIterator start, RandomAccessIterator end, LessThan lessThan)
    00185 {
    00186     if (start != end)
    00187         QAlgorithmsPrivate::qSortHelper(start, end, *start, lessThan);
    00188 }
    00189
    00190 template<typename Container>
    00191 inline void qSort(Container &c)
    00192 {
    00193 #ifdef Q_CC_BOR
    00194     // Work around Borland 5.5 optimizer bug
    00195     c.detach();
    00196 #endif
    00197     if (!c.empty())
    00198         QAlgorithmsPrivate::qSortHelper(c.begin(), c.end(), *c.begin());
    00199 }
    00200
    00201 template <typename RandomAccessIterator>
    00202 inline void qStableSort(RandomAccessIterator start, RandomAccessIterator end)
    00203 {
    00204     if (start != end)
    00205         QAlgorithmsPrivate::qStableSortHelper(start, end, *start);
    00206 }
    00207
    00208 template <typename RandomAccessIterator, typename LessThan>
    00209 inline void qStableSort(RandomAccessIterator start, RandomAccessIterator end, LessThan lessThan)
    00210 {
    00211     if (start != end)
    00212         QAlgorithmsPrivate::qStableSortHelper(start, end, *start, lessThan);
    00213 }
    00214
    00215 template<typename Container>
    00216 inline void qStableSort(Container &c)
    00217 {
    00218 #ifdef Q_CC_BOR
    00219     // Work around Borland 5.5 optimizer bug
    00220     c.detach();
    00221 #endif
    00222     if (!c.empty())
    00223         QAlgorithmsPrivate::qStableSortHelper(c.begin(), c.end(), *c.begin());
    00224 }
    00225
    00226 template <typename RandomAccessIterator, typename T>
    00227 Q_OUTOFLINE_TEMPLATE RandomAccessIterator qLowerBound(RandomAccessIterator begin, RandomAccessIterator end, const T &value)
    00228 {
    00229     // Implementation is duplicated from QAlgorithmsPrivate to keep existing code
    00230     // compiling. We have to allow using *begin and value with different types,
    00231     // and then implementing operator< for those types.
    00232     RandomAccessIterator middle;
    00233     int n = end - begin;
    00234     int half;
    00235
    00236     while (n > 0) {
    00237         half = n >> 1;
    00238         middle = begin + half;
    00239         if (*middle < value) {
    00240             begin = middle + 1;
    00241             n -= half + 1;
    00242         } else {
    00243             n = half;
    00244         }
    00245     }
    00246     return begin;
    00247 }
    00248
    00249 template <typename RandomAccessIterator, typename T, typename LessThan>
    00250 Q_OUTOFLINE_TEMPLATE RandomAccessIterator qLowerBound(RandomAccessIterator begin, RandomAccessIterator end, const T &value, LessThan lessThan)
    00251 {
    00252     return QAlgorithmsPrivate::qLowerBoundHelper(begin, end, value, lessThan);
    00253 }
    00254
    00255 template <typename Container, typename T>
    00256 Q_OUTOFLINE_TEMPLATE typename Container::const_iterator qLowerBound(const Container &container, const T &value)
    00257 {
    00258     return QAlgorithmsPrivate::qLowerBoundHelper(container.constBegin(), container.constEnd(), value, qLess<T>());
    00259 }
    00260
    00261 template <typename RandomAccessIterator, typename T>
    00262 Q_OUTOFLINE_TEMPLATE RandomAccessIterator qUpperBound(RandomAccessIterator begin, RandomAccessIterator end, const T &value)
    00263 {
    00264     // Implementation is duplicated from QAlgorithmsPrivate.
    00265     RandomAccessIterator middle;
    00266     int n = end - begin;
    00267     int half;
    00268
    00269     while (n > 0) {
    00270         half = n >> 1;
    00271         middle = begin + half;
    00272         if (value < *middle) {
    00273             n = half;
    00274         } else {
    00275             begin = middle + 1;
    00276             n -= half + 1;
    00277         }
    00278     }
    00279     return begin;
    00280 }
    00281
    00282 template <typename RandomAccessIterator, typename T, typename LessThan>
    00283 Q_OUTOFLINE_TEMPLATE RandomAccessIterator qUpperBound(RandomAccessIterator begin, RandomAccessIterator end, const T &value, LessThan lessThan)
    00284 {
    00285     return QAlgorithmsPrivate::qUpperBoundHelper(begin, end, value, lessThan);
    00286 }
    00287
    00288 template <typename Container, typename T>
    00289 Q_OUTOFLINE_TEMPLATE typename Container::const_iterator qUpperBound(const Container &container, const T &value)
    00290 {
    00291     return QAlgorithmsPrivate::qUpperBoundHelper(container.constBegin(), container.constEnd(), value, qLess<T>());
    00292 }
    00293
    00294 template <typename RandomAccessIterator, typename T>
    00295 Q_OUTOFLINE_TEMPLATE RandomAccessIterator qBinaryFind(RandomAccessIterator begin, RandomAccessIterator end, const T &value)
    00296 {
    00297     // Implementation is duplicated from QAlgorithmsPrivate.
    00298     RandomAccessIterator it = qLowerBound(begin, end, value);
    00299
    00300     if (it == end || value < *it)
    00301         return end;
    00302
    00303     return it;
    00304 }
    00305
    00306 template <typename RandomAccessIterator, typename T, typename LessThan>
    00307 Q_OUTOFLINE_TEMPLATE RandomAccessIterator qBinaryFind(RandomAccessIterator begin, RandomAccessIterator end, const T &value, LessThan lessThan)
    00308 {
    00309     return QAlgorithmsPrivate::qBinaryFindHelper(begin, end, value, lessThan);
    00310 }
    00311
    00312 template <typename Container, typename T>
    00313 Q_OUTOFLINE_TEMPLATE typename Container::const_iterator qBinaryFind(const Container &container, const T &value)
    00314 {
    00315     return QAlgorithmsPrivate::qBinaryFindHelper(container.constBegin(), container.constEnd(), value, qLess<T>());
    00316 }
    00317
    00318 template <typename ForwardIterator>
    00319 Q_OUTOFLINE_TEMPLATE void qDeleteAll(ForwardIterator begin, ForwardIterator end)
    00320 {
    00321     while (begin != end) {
    00322         delete *begin;
    00323         ++begin;
    00324     }
    00325 }
    00326
    00327 template <typename Container>
    00328 inline void qDeleteAll(const Container &c)
    00329 {
    00330     qDeleteAll(c.begin(), c.end());
    00331 }
    00332
    00333 /*
    00334     Warning: The contents of QAlgorithmsPrivate is not a part of the public Qt API
    00335     and may be changed from version to version or even be completely removed.
    00336 */
    00337 namespace QAlgorithmsPrivate {
    00338
    00339 template <typename RandomAccessIterator, typename T, typename LessThan>
    00340 Q_OUTOFLINE_TEMPLATE void qSortHelper(RandomAccessIterator start, RandomAccessIterator end, const T &t, LessThan lessThan)
    00341 {
    00342 top:
    00343     int span = int(end - start);
    00344     if (span < 2)
    00345         return;
    00346
    00347     --end;
    00348     RandomAccessIterator low = start, high = end - 1;
    00349     RandomAccessIterator pivot = start + span / 2;
    00350
    00351     if (lessThan(*end, *start))
    00352         qSwap(*end, *start);
    00353     if (span == 2)
    00354         return;
    00355
    00356     if (lessThan(*pivot, *start))
    00357         qSwap(*pivot, *start);
    00358     if (lessThan(*end, *pivot))
    00359         qSwap(*end, *pivot);
    00360     if (span == 3)
    00361         return;
    00362
    00363     qSwap(*pivot, *end);
    00364
    00365     while (low < high) {
    00366         while (low < high && lessThan(*low, *end))
    00367             ++low;
    00368
    00369         while (high > low && lessThan(*end, *high))
    00370             --high;
    00371
    00372         if (low < high) {
    00373             qSwap(*low, *high);
    00374             ++low;
    00375             --high;
    00376         } else {
    00377             break;
    00378         }
    00379     }
    00380
    00381     if (lessThan(*low, *end))
    00382         ++low;
    00383
    00384     qSwap(*end, *low);
    00385     qSortHelper(start, low, t, lessThan);
    00386
    00387     start = low + 1;
    00388     ++end;
    00389     goto top;
    00390 }
    00391
    00392 template <typename RandomAccessIterator, typename T>
    00393 inline void qSortHelper(RandomAccessIterator begin, RandomAccessIterator end, const T &dummy)
    00394 {
    00395     qSortHelper(begin, end, dummy, qLess<T>());
    00396 }
    00397
    00398 template <typename RandomAccessIterator>
    00399 Q_OUTOFLINE_TEMPLATE void qReverse(RandomAccessIterator begin, RandomAccessIterator end)
    00400 {
    00401     --end;
    00402     while (begin < end)
    00403         qSwap(*begin++, *end--);
    00404 }
    00405
    00406 template <typename RandomAccessIterator>
    00407 Q_OUTOFLINE_TEMPLATE void qRotate(RandomAccessIterator begin, RandomAccessIterator middle, RandomAccessIterator end)
    00408 {
    00409     qReverse(begin, middle);
    00410     qReverse(middle, end);
    00411     qReverse(begin, end);
    00412 }
    00413
    00414 template <typename RandomAccessIterator, typename T, typename LessThan>
    00415 Q_OUTOFLINE_TEMPLATE void qMerge(RandomAccessIterator begin, RandomAccessIterator pivot, RandomAccessIterator end, T &t, LessThan lessThan)
    00416 {
    00417     const int len1 = pivot - begin;
    00418     const int len2 = end - pivot;
    00419
    00420     if (len1 == 0 || len2 == 0)
    00421         return;
    00422
    00423     if (len1 + len2 == 2) {
    00424         if (lessThan(*(begin + 1), *(begin)))
    00425             qSwap(*begin, *(begin + 1));
    00426         return;
    00427     }
    00428
    00429     RandomAccessIterator firstCut;
    00430     RandomAccessIterator secondCut;
    00431     int len2Half;
    00432     if (len1 > len2) {
    00433         const int len1Half = len1 / 2;
    00434         firstCut = begin + len1Half;
    00435         secondCut = qLowerBound(pivot, end, *firstCut, lessThan);
    00436         len2Half = secondCut - pivot;
    00437     } else {
    00438         len2Half = len2 / 2;
    00439         secondCut = pivot + len2Half;
    00440         firstCut = qUpperBound(begin, pivot, *secondCut, lessThan);
    00441     }
    00442
    00443     qRotate(firstCut, pivot, secondCut);
    00444     const RandomAccessIterator newPivot = firstCut + len2Half;
    00445     qMerge(begin, firstCut, newPivot, t, lessThan);
    00446     qMerge(newPivot, secondCut, end, t, lessThan);
    00447 }
    00448
    00449 template <typename RandomAccessIterator, typename T, typename LessThan>
    00450 Q_OUTOFLINE_TEMPLATE void qStableSortHelper(RandomAccessIterator begin, RandomAccessIterator end, const T &t, LessThan lessThan)
    00451 {
    00452     const int span = end - begin;
    00453     if (span < 2)
    00454        return;
    00455
    00456     const RandomAccessIterator middle = begin + span / 2;
    00457     qStableSortHelper(begin, middle, t, lessThan);
    00458     qStableSortHelper(middle, end, t, lessThan);
    00459     qMerge(begin, middle, end, t, lessThan);
    00460 }
    00461
    00462 template <typename RandomAccessIterator, typename T>
    00463 inline void qStableSortHelper(RandomAccessIterator begin, RandomAccessIterator end, const T &dummy)
    00464 {
    00465     qStableSortHelper(begin, end, dummy, qLess<T>());
    00466 }
    00467
    00468 template <typename RandomAccessIterator, typename T, typename LessThan>
    00469 Q_OUTOFLINE_TEMPLATE RandomAccessIterator qLowerBoundHelper(RandomAccessIterator begin, RandomAccessIterator end, const T &value, LessThan lessThan)
    00470 {
    00471     RandomAccessIterator middle;
    00472     int n = int(end - begin);
    00473     int half;
    00474
    00475     while (n > 0) {
    00476         half = n >> 1;
    00477         middle = begin + half;
    00478         if (lessThan(*middle, value)) {
    00479             begin = middle + 1;
    00480             n -= half + 1;
    00481         } else {
    00482             n = half;
    00483         }
    00484     }
    00485     return begin;
    00486 }
    00487
    00488
    00489 template <typename RandomAccessIterator, typename T, typename LessThan>
    00490 Q_OUTOFLINE_TEMPLATE RandomAccessIterator qUpperBoundHelper(RandomAccessIterator begin, RandomAccessIterator end, const T &value, LessThan lessThan)
    00491 {
    00492     RandomAccessIterator middle;
    00493     int n = end - begin;
    00494     int half;
    00495
    00496     while (n > 0) {
    00497         half = n >> 1;
    00498         middle = begin + half;
    00499         if (lessThan(value, *middle)) {
    00500             n = half;
    00501         } else {
    00502             begin = middle + 1;
    00503             n -= half + 1;
    00504         }
    00505     }
    00506     return begin;
    00507 }
    00508
    00509 template <typename RandomAccessIterator, typename T, typename LessThan>
    00510 Q_OUTOFLINE_TEMPLATE RandomAccessIterator qBinaryFindHelper(RandomAccessIterator begin, RandomAccessIterator end, const T &value, LessThan lessThan)
    00511 {
    00512     RandomAccessIterator it = qLowerBoundHelper(begin, end, value, lessThan);
    00513
    00514     if (it == end || lessThan(value, *it))
    00515         return end;
    00516
    00517     return it;
    00518 }
    00519
    00520 } //namespace QAlgorithmsPrivate
    00521
    00522 QT_END_NAMESPACE
    00523
    00524 QT_END_HEADER
    00525
    00526 #endif // QALGORITHMS_H