src/corelib/tools/qalgorithms.h

   1 /****************************************************************************
   2 **
   3 ** Copyright (C) 2012 Nokia Corporation and/or its subsidiary(-ies).
   4 ** Contact: http://www.qt-project.org/
   5 **
   6 ** This file is part of the QtCore module of the Qt Toolkit.
   7 **
   8 ** $QT_BEGIN_LICENSE:LGPL$
   9 ** GNU Lesser General Public License Usage
  10 ** This file may be used under the terms of the GNU Lesser General Public
  11 ** License version 2.1 as published by the Free Software Foundation and
  12 ** appearing in the file LICENSE.LGPL included in the packaging of this
  13 ** file. Please review the following information to ensure the GNU Lesser
  14 ** General Public License version 2.1 requirements will be met:
  15 ** http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.
  16 **
  17 ** In addition, as a special exception, Nokia gives you certain additional
  18 ** rights. These rights are described in the Nokia Qt LGPL Exception
  19 ** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.
  20 **
  21 ** GNU General Public License Usage
  22 ** Alternatively, this file may be used under the terms of the GNU General
  23 ** Public License version 3.0 as published by the Free Software Foundation
  24 ** and appearing in the file LICENSE.GPL included in the packaging of this
  25 ** file. Please review the following information to ensure the GNU General
  26 ** Public License version 3.0 requirements will be met:
  27 ** http://www.gnu.org/copyleft/gpl.html.
  28 **
  29 ** Other Usage
  30 ** Alternatively, this file may be used in accordance with the terms and
  31 ** conditions contained in a signed written agreement between you and Nokia.
  32 **
  33 **
  34 **
  35 **
  36 **
  37 **
  38 ** $QT_END_LICENSE$
  39 **
  40 ****************************************************************************/
  41
  42 #ifndef QALGORITHMS_H
  43 #define QALGORITHMS_H
  44
  45 #include <QtCore/qglobal.h>
  46
  47 QT_BEGIN_HEADER
  48
  49 QT_BEGIN_NAMESPACE
  50
  51
  52 /*
  53     Warning: The contents of QAlgorithmsPrivate is not a part of the public Qt API
  54     and may be changed from version to version or even be completely removed.
  55 */
  56 namespace QAlgorithmsPrivate {
  57
  58 template <typename RandomAccessIterator, typename T, typename LessThan>
  59 Q_OUTOFLINE_TEMPLATE void qSortHelper(RandomAccessIterator start, RandomAccessIterator end, const T &t, LessThan lessThan);
  60 template <typename RandomAccessIterator, typename T>
  61 inline void qSortHelper(RandomAccessIterator begin, RandomAccessIterator end, const T &dummy);
  62
  63 template <typename RandomAccessIterator, typename T, typename LessThan>
  64 Q_OUTOFLINE_TEMPLATE void qStableSortHelper(RandomAccessIterator start, RandomAccessIterator end, const T &t, LessThan lessThan);
  65 template <typename RandomAccessIterator, typename T>
  66 inline void qStableSortHelper(RandomAccessIterator, RandomAccessIterator, const T &);
  67
  68 template <typename RandomAccessIterator, typename T, typename LessThan>
  69 Q_OUTOFLINE_TEMPLATE RandomAccessIterator qLowerBoundHelper(RandomAccessIterator begin, RandomAccessIterator end, const T &value, LessThan lessThan);
  70 template <typename RandomAccessIterator, typename T, typename LessThan>
  71 Q_OUTOFLINE_TEMPLATE RandomAccessIterator qUpperBoundHelper(RandomAccessIterator begin, RandomAccessIterator end, const T &value, LessThan lessThan);
  72 template <typename RandomAccessIterator, typename T, typename LessThan>
  73 Q_OUTOFLINE_TEMPLATE RandomAccessIterator qBinaryFindHelper(RandomAccessIterator begin, RandomAccessIterator end, const T &value, LessThan lessThan);
  74
  75 }
  76
  77 template <typename InputIterator, typename OutputIterator>
  78 inline OutputIterator qCopy(InputIterator begin, InputIterator end, OutputIterator dest)
  79 {
  80     while (begin != end)
  81         *dest++ = *begin++;
  82     return dest;
  83 }
  84
  85 template <typename BiIterator1, typename BiIterator2>
  86 inline BiIterator2 qCopyBackward(BiIterator1 begin, BiIterator1 end, BiIterator2 dest)
  87 {
  88     while (begin != end)
  89         *--dest = *--end;
  90     return dest;
  91 }
  92
  93 template <typename InputIterator1, typename InputIterator2>
  94 inline bool qEqual(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2)
  95 {
  96     for (; first1 != last1; ++first1, ++first2)
  97         if (!(*first1 == *first2))
  98             return false;
  99     return true;
 100 }
 101
 102 template <typename ForwardIterator, typename T>
 103 inline void qFill(ForwardIterator first, ForwardIterator last, const T &val)
 104 {
 105     for (; first != last; ++first)
 106         *first = val;
 107 }
 108
 109 template <typename Container, typename T>
 110 inline void qFill(Container &container, const T &val)
 111 {
 112     qFill(container.begin(), container.end(), val);
 113 }
 114
 115 template <typename InputIterator, typename T>
 116 inline InputIterator qFind(InputIterator first, InputIterator last, const T &val)
 117 {
 118     while (first != last && !(*first == val))
 119         ++first;
 120     return first;
 121 }
 122
 123 template <typename Container, typename T>
 124 inline typename Container::const_iterator qFind(const Container &container, const T &val)
 125 {
 126     return qFind(container.constBegin(), container.constEnd(), val);
 127 }
 128
 129 template <typename InputIterator, typename T, typename Size>
 130 inline void qCount(InputIterator first, InputIterator last, const T &value, Size &n)
 131 {
 132     for (; first != last; ++first)
 133         if (*first == value)
 134             ++n;
 135 }
 136
 137 template <typename Container, typename T, typename Size>
 138 inline void qCount(const Container &container, const T &value, Size &n)
 139 {
 140     qCount(container.constBegin(), container.constEnd(), value, n);
 141 }
 142
 143 #ifdef qdoc
 144 template <typename T>
 145 LessThan qLess()
 146 {
 147 }
 148
 149 template <typename T>
 150 LessThan qGreater()
 151 {
 152 }
 153 #else
 154 template <typename T>
 155 class qLess
 156 {
 157 public:
 158     inline bool operator()(const T &t1, const T &t2) const
 159     {
 160         return (t1 < t2);
 161     }
 162 };
 163
 164 template <typename T>
 165 class qGreater
 166 {
 167 public:
 168     inline bool operator()(const T &t1, const T &t2) const
 169     {
 170         return (t2 < t1);
 171     }
 172 };
 173 #endif
 174
 175 template <typename RandomAccessIterator>
 176 inline void qSort(RandomAccessIterator start, RandomAccessIterator end)
 177 {
 178     if (start != end)
 179         QAlgorithmsPrivate::qSortHelper(start, end, *start);
 180 }
 181
 182 template <typename RandomAccessIterator, typename LessThan>
 183 inline void qSort(RandomAccessIterator start, RandomAccessIterator end, LessThan lessThan)
 184 {
 185     if (start != end)
 186         QAlgorithmsPrivate::qSortHelper(start, end, *start, lessThan);
 187 }
 188
 189 template<typename Container>
 190 inline void qSort(Container &c)
 191 {
 192 #ifdef Q_CC_BOR
 193     // Work around Borland 5.5 optimizer bug
 194     c.detach();
 195 #endif
 196     if (!c.empty())
 197         QAlgorithmsPrivate::qSortHelper(c.begin(), c.end(), *c.begin());
 198 }
 199
 200 template <typename RandomAccessIterator>
 201 inline void qStableSort(RandomAccessIterator start, RandomAccessIterator end)
 202 {
 203     if (start != end)
 204         QAlgorithmsPrivate::qStableSortHelper(start, end, *start);
 205 }
 206
 207 template <typename RandomAccessIterator, typename LessThan>
 208 inline void qStableSort(RandomAccessIterator start, RandomAccessIterator end, LessThan lessThan)
 209 {
 210     if (start != end)
 211         QAlgorithmsPrivate::qStableSortHelper(start, end, *start, lessThan);
 212 }
 213
 214 template<typename Container>
 215 inline void qStableSort(Container &c)
 216 {
 217 #ifdef Q_CC_BOR
 218     // Work around Borland 5.5 optimizer bug
 219     c.detach();
 220 #endif
 221     if (!c.empty())
 222         QAlgorithmsPrivate::qStableSortHelper(c.begin(), c.end(), *c.begin());
 223 }
 224
 225 template <typename RandomAccessIterator, typename T>
 226 Q_OUTOFLINE_TEMPLATE RandomAccessIterator qLowerBound(RandomAccessIterator begin, RandomAccessIterator end, const T &value)
 227 {
 228     // Implementation is duplicated from QAlgorithmsPrivate to keep existing code
 229     // compiling. We have to allow using *begin and value with different types,
 230     // and then implementing operator< for those types.
 231     RandomAccessIterator middle;
 232     int n = end - begin;
 233     int half;
 234
 235     while (n > 0) {
 236         half = n >> 1;
 237         middle = begin + half;
 238         if (*middle < value) {
 239             begin = middle + 1;
 240             n -= half + 1;
 241         } else {
 242             n = half;
 243         }
 244     }
 245     return begin;
 246 }
 247
 248 template <typename RandomAccessIterator, typename T, typename LessThan>
 249 Q_OUTOFLINE_TEMPLATE RandomAccessIterator qLowerBound(RandomAccessIterator begin, RandomAccessIterator end, const T &value, LessThan lessThan)
 250 {
 251     return QAlgorithmsPrivate::qLowerBoundHelper(begin, end, value, lessThan);
 252 }
 253
 254 template <typename Container, typename T>
 255 Q_OUTOFLINE_TEMPLATE typename Container::const_iterator qLowerBound(const Container &container, const T &value)
 256 {
 257     return QAlgorithmsPrivate::qLowerBoundHelper(container.constBegin(), container.constEnd(), value, qLess<T>());
 258 }
 259
 260 template <typename RandomAccessIterator, typename T>
 261 Q_OUTOFLINE_TEMPLATE RandomAccessIterator qUpperBound(RandomAccessIterator begin, RandomAccessIterator end, const T &value)
 262 {
 263     // Implementation is duplicated from QAlgorithmsPrivate.
 264     RandomAccessIterator middle;
 265     int n = end - begin;
 266     int half;
 267
 268     while (n > 0) {
 269         half = n >> 1;
 270         middle = begin + half;
 271         if (value < *middle) {
 272             n = half;
 273         } else {
 274             begin = middle + 1;
 275             n -= half + 1;
 276         }
 277     }
 278     return begin;
 279 }
 280
 281 template <typename RandomAccessIterator, typename T, typename LessThan>
 282 Q_OUTOFLINE_TEMPLATE RandomAccessIterator qUpperBound(RandomAccessIterator begin, RandomAccessIterator end, const T &value, LessThan lessThan)
 283 {
 284     return QAlgorithmsPrivate::qUpperBoundHelper(begin, end, value, lessThan);
 285 }
 286
 287 template <typename Container, typename T>
 288 Q_OUTOFLINE_TEMPLATE typename Container::const_iterator qUpperBound(const Container &container, const T &value)
 289 {
 290     return QAlgorithmsPrivate::qUpperBoundHelper(container.constBegin(), container.constEnd(), value, qLess<T>());
 291 }
 292
 293 template <typename RandomAccessIterator, typename T>
 294 Q_OUTOFLINE_TEMPLATE RandomAccessIterator qBinaryFind(RandomAccessIterator begin, RandomAccessIterator end, const T &value)
 295 {
 296     // Implementation is duplicated from QAlgorithmsPrivate.
 297     RandomAccessIterator it = qLowerBound(begin, end, value);
 298
 299     if (it == end || value < *it)
 300         return end;
 301
 302     return it;
 303 }
 304
 305 template <typename RandomAccessIterator, typename T, typename LessThan>
 306 Q_OUTOFLINE_TEMPLATE RandomAccessIterator qBinaryFind(RandomAccessIterator begin, RandomAccessIterator end, const T &value, LessThan lessThan)
 307 {
 308     return QAlgorithmsPrivate::qBinaryFindHelper(begin, end, value, lessThan);
 309 }
 310
 311 template <typename Container, typename T>
 312 Q_OUTOFLINE_TEMPLATE typename Container::const_iterator qBinaryFind(const Container &container, const T &value)
 313 {
 314     return QAlgorithmsPrivate::qBinaryFindHelper(container.constBegin(), container.constEnd(), value, qLess<T>());
 315 }
 316
 317 template <typename ForwardIterator>
 318 Q_OUTOFLINE_TEMPLATE void qDeleteAll(ForwardIterator begin, ForwardIterator end)
 319 {
 320     while (begin != end) {
 321         delete *begin;
 322         ++begin;
 323     }
 324 }
 325
 326 template <typename Container>
 327 inline void qDeleteAll(const Container &c)
 328 {
 329     qDeleteAll(c.begin(), c.end());
 330 }
 331
 332 /*
 333     Warning: The contents of QAlgorithmsPrivate is not a part of the public Qt API
 334     and may be changed from version to version or even be completely removed.
 335 */
 336 namespace QAlgorithmsPrivate {
 337
 338 template <typename RandomAccessIterator, typename T, typename LessThan>
 339 Q_OUTOFLINE_TEMPLATE void qSortHelper(RandomAccessIterator start, RandomAccessIterator end, const T &t, LessThan lessThan)
 340 {
 341 top:
 342     int span = int(end - start);
 343     if (span < 2)
 344         return;
 345
 346     --end;
 347     RandomAccessIterator low = start, high = end - 1;
 348     RandomAccessIterator pivot = start + span / 2;
 349
 350     if (lessThan(*end, *start))
 351         qSwap(*end, *start);
 352     if (span == 2)
 353         return;
 354
 355     if (lessThan(*pivot, *start))
 356         qSwap(*pivot, *start);
 357     if (lessThan(*end, *pivot))
 358         qSwap(*end, *pivot);
 359     if (span == 3)
 360         return;
 361
 362     qSwap(*pivot, *end);
 363
 364     while (low < high) {
 365         while (low < high && lessThan(*low, *end))
 366             ++low;
 367
 368         while (high > low && lessThan(*end, *high))
 369             --high;
 370
 371         if (low < high) {
 372             qSwap(*low, *high);
 373             ++low;
 374             --high;
 375         } else {
 376             break;
 377         }
 378     }
 379
 380     if (lessThan(*low, *end))
 381         ++low;
 382
 383     qSwap(*end, *low);
 384     qSortHelper(start, low, t, lessThan);
 385
 386     start = low + 1;
 387     ++end;
 388     goto top;
 389 }
 390
 391 template <typename RandomAccessIterator, typename T>
 392 inline void qSortHelper(RandomAccessIterator begin, RandomAccessIterator end, const T &dummy)
 393 {
 394     qSortHelper(begin, end, dummy, qLess<T>());
 395 }
 396
 397 template <typename RandomAccessIterator>
 398 Q_OUTOFLINE_TEMPLATE void qReverse(RandomAccessIterator begin, RandomAccessIterator end)
 399 {
 400     --end;
 401     while (begin < end)
 402         qSwap(*begin++, *end--);
 403 }
 404
 405 template <typename RandomAccessIterator>
 406 Q_OUTOFLINE_TEMPLATE void qRotate(RandomAccessIterator begin, RandomAccessIterator middle, RandomAccessIterator end)
 407 {
 408     qReverse(begin, middle);
 409     qReverse(middle, end);
 410     qReverse(begin, end);
 411 }
 412
 413 template <typename RandomAccessIterator, typename T, typename LessThan>
 414 Q_OUTOFLINE_TEMPLATE void qMerge(RandomAccessIterator begin, RandomAccessIterator pivot, RandomAccessIterator end, T &t, LessThan lessThan)
 415 {
 416     const int len1 = pivot - begin;
 417     const int len2 = end - pivot;
 418
 419     if (len1 == 0 || len2 == 0)
 420         return;
 421
 422     if (len1 + len2 == 2) {
 423         if (lessThan(*(begin + 1), *(begin)))
 424             qSwap(*begin, *(begin + 1));
 425         return;
 426     }
 427
 428     RandomAccessIterator firstCut;
 429     RandomAccessIterator secondCut;
 430     int len2Half;
 431     if (len1 > len2) {
 432         const int len1Half = len1 / 2;
 433         firstCut = begin + len1Half;
 434         secondCut = qLowerBound(pivot, end, *firstCut, lessThan);
 435         len2Half = secondCut - pivot;
 436     } else {
 437         len2Half = len2 / 2;
 438         secondCut = pivot + len2Half;
 439         firstCut = qUpperBound(begin, pivot, *secondCut, lessThan);
 440     }
 441
 442     qRotate(firstCut, pivot, secondCut);
 443     const RandomAccessIterator newPivot = firstCut + len2Half;
 444     qMerge(begin, firstCut, newPivot, t, lessThan);
 445     qMerge(newPivot, secondCut, end, t, lessThan);
 446 }
 447
 448 template <typename RandomAccessIterator, typename T, typename LessThan>
 449 Q_OUTOFLINE_TEMPLATE void qStableSortHelper(RandomAccessIterator begin, RandomAccessIterator end, const T &t, LessThan lessThan)
 450 {
 451     const int span = end - begin;
 452     if (span < 2)
 453        return;
 454
 455     const RandomAccessIterator middle = begin + span / 2;
 456     qStableSortHelper(begin, middle, t, lessThan);
 457     qStableSortHelper(middle, end, t, lessThan);
 458     qMerge(begin, middle, end, t, lessThan);
 459 }
 460
 461 template <typename RandomAccessIterator, typename T>
 462 inline void qStableSortHelper(RandomAccessIterator begin, RandomAccessIterator end, const T &dummy)
 463 {
 464     qStableSortHelper(begin, end, dummy, qLess<T>());
 465 }
 466
 467 template <typename RandomAccessIterator, typename T, typename LessThan>
 468 Q_OUTOFLINE_TEMPLATE RandomAccessIterator qLowerBoundHelper(RandomAccessIterator begin, RandomAccessIterator end, const T &value, LessThan lessThan)
 469 {
 470     RandomAccessIterator middle;
 471     int n = int(end - begin);
 472     int half;
 473
 474     while (n > 0) {
 475         half = n >> 1;
 476         middle = begin + half;
 477         if (lessThan(*middle, value)) {
 478             begin = middle + 1;
 479             n -= half + 1;
 480         } else {
 481             n = half;
 482         }
 483     }
 484     return begin;
 485 }
 486
 487
 488 template <typename RandomAccessIterator, typename T, typename LessThan>
 489 Q_OUTOFLINE_TEMPLATE RandomAccessIterator qUpperBoundHelper(RandomAccessIterator begin, RandomAccessIterator end, const T &value, LessThan lessThan)
 490 {
 491     RandomAccessIterator middle;
 492     int n = end - begin;
 493     int half;
 494
 495     while (n > 0) {
 496         half = n >> 1;
 497         middle = begin + half;
 498         if (lessThan(value, *middle)) {
 499             n = half;
 500         } else {
 501             begin = middle + 1;
 502             n -= half + 1;
 503         }
 504     }
 505     return begin;
 506 }
 507
 508 template <typename RandomAccessIterator, typename T, typename LessThan>
 509 Q_OUTOFLINE_TEMPLATE RandomAccessIterator qBinaryFindHelper(RandomAccessIterator begin, RandomAccessIterator end, const T &value, LessThan lessThan)
 510 {
 511     RandomAccessIterator it = qLowerBoundHelper(begin, end, value, lessThan);
 512
 513     if (it == end || lessThan(value, *it))
 514         return end;
 515
 516     return it;
 517 }
 518
 519 } //namespace QAlgorithmsPrivate
 520
 521 QT_END_NAMESPACE
 522
 523 QT_END_HEADER
 524
 525 #endif // QALGORITHMS_H