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