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
47QT_BEGIN_HEADER
48
49QT_BEGIN_NAMESPACE
50
51QT_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*/
57namespace QAlgorithmsPrivate {
58
59template <typename RandomAccessIterator, typename T, typename LessThan>
60Q_OUTOFLINE_TEMPLATE void qSortHelper(RandomAccessIterator start, RandomAccessIterator end, const T &t, LessThan lessThan);
61template <typename RandomAccessIterator, typename T>
62inline void qSortHelper(RandomAccessIterator begin, RandomAccessIterator end, const T &dummy);
63
64template <typename RandomAccessIterator, typename T, typename LessThan>
65Q_OUTOFLINE_TEMPLATE void qStableSortHelper(RandomAccessIterator start, RandomAccessIterator end, const T &t, LessThan lessThan);
66template <typename RandomAccessIterator, typename T>
67inline void qStableSortHelper(RandomAccessIterator, RandomAccessIterator, const T &);
68
69template <typename RandomAccessIterator, typename T, typename LessThan>
70Q_OUTOFLINE_TEMPLATE RandomAccessIterator qLowerBoundHelper(RandomAccessIterator begin, RandomAccessIterator end, const T &value, LessThan lessThan);
71template <typename RandomAccessIterator, typename T, typename LessThan>
72Q_OUTOFLINE_TEMPLATE RandomAccessIterator qUpperBoundHelper(RandomAccessIterator begin, RandomAccessIterator end, const T &value, LessThan lessThan);
73template <typename RandomAccessIterator, typename T, typename LessThan>
74Q_OUTOFLINE_TEMPLATE RandomAccessIterator qBinaryFindHelper(RandomAccessIterator begin, RandomAccessIterator end, const T &value, LessThan lessThan);
75
76}
77
78template <typename InputIterator, typename OutputIterator>
79inline OutputIterator qCopy(InputIterator begin, InputIterator end, OutputIterator dest)
80{
81 while (begin != end)
82 *dest++ = *begin++;
83 return dest;
84}
85
86template <typename BiIterator1, typename BiIterator2>
87inline BiIterator2 qCopyBackward(BiIterator1 begin, BiIterator1 end, BiIterator2 dest)
88{
89 while (begin != end)
90 *--dest = *--end;
91 return dest;
92}
93
94template <typename InputIterator1, typename InputIterator2>
95inline 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
103template <typename ForwardIterator, typename T>
104inline void qFill(ForwardIterator first, ForwardIterator last, const T &val)
105{
106 for (; first != last; ++first)
107 *first = val;
108}
109
110template <typename Container, typename T>
111inline void qFill(Container &container, const T &val)
112{
113 qFill(container.begin(), container.end(), val);
114}
115
116template <typename InputIterator, typename T>
117inline InputIterator qFind(InputIterator first, InputIterator last, const T &val)
118{
119 while (first != last && !(*first == val))
120 ++first;
121 return first;
122}
123
124template <typename Container, typename T>
125inline typename Container::const_iterator qFind(const Container &container, const T &val)
126{
127 return qFind(container.constBegin(), container.constEnd(), val);
128}
129
130template <typename InputIterator, typename T, typename Size>
131inline 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
138template <typename Container, typename T, typename Size>
139inline void qCount(const Container &container, const T &value, Size &n)
140{
141 qCount(container.constBegin(), container.constEnd(), value, n);
142}
143
144#ifdef qdoc
145template <typename T>
146LessThan qLess()
147{
148}
149
150template <typename T>
151LessThan qGreater()
152{
153}
154#else
155template <typename T>
156class qLess
157{
158public:
159 inline bool operator()(const T &t1, const T &t2) const
160 {
161 return (t1 < t2);
162 }
163};
164
165template <typename T>
166class qGreater
167{
168public:
169 inline bool operator()(const T &t1, const T &t2) const
170 {
171 return (t2 < t1);
172 }
173};
174#endif
175
176template <typename RandomAccessIterator>
177inline void qSort(RandomAccessIterator start, RandomAccessIterator end)
178{
179 if (start != end)
180 QAlgorithmsPrivate::qSortHelper(start, end, *start);
181}
182
183template <typename RandomAccessIterator, typename LessThan>
184inline void qSort(RandomAccessIterator start, RandomAccessIterator end, LessThan lessThan)
185{
186 if (start != end)
187 QAlgorithmsPrivate::qSortHelper(start, end, *start, lessThan);
188}
189
190template<typename Container>
191inline 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
201template <typename RandomAccessIterator>
202inline void qStableSort(RandomAccessIterator start, RandomAccessIterator end)
203{
204 if (start != end)
205 QAlgorithmsPrivate::qStableSortHelper(start, end, *start);
206}
207
208template <typename RandomAccessIterator, typename LessThan>
209inline void qStableSort(RandomAccessIterator start, RandomAccessIterator end, LessThan lessThan)
210{
211 if (start != end)
212 QAlgorithmsPrivate::qStableSortHelper(start, end, *start, lessThan);
213}
214
215template<typename Container>
216inline 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
226template <typename RandomAccessIterator, typename T>
227Q_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
249template <typename RandomAccessIterator, typename T, typename LessThan>
250Q_OUTOFLINE_TEMPLATE RandomAccessIterator qLowerBound(RandomAccessIterator begin, RandomAccessIterator end, const T &value, LessThan lessThan)
251{
252 return QAlgorithmsPrivate::qLowerBoundHelper(begin, end, value, lessThan);
253}
254
255template <typename Container, typename T>
256Q_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
261template <typename RandomAccessIterator, typename T>
262Q_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
282template <typename RandomAccessIterator, typename T, typename LessThan>
283Q_OUTOFLINE_TEMPLATE RandomAccessIterator qUpperBound(RandomAccessIterator begin, RandomAccessIterator end, const T &value, LessThan lessThan)
284{
285 return QAlgorithmsPrivate::qUpperBoundHelper(begin, end, value, lessThan);
286}
287
288template <typename Container, typename T>
289Q_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
294template <typename RandomAccessIterator, typename T>
295Q_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
306template <typename RandomAccessIterator, typename T, typename LessThan>
307Q_OUTOFLINE_TEMPLATE RandomAccessIterator qBinaryFind(RandomAccessIterator begin, RandomAccessIterator end, const T &value, LessThan lessThan)
308{
309 return QAlgorithmsPrivate::qBinaryFindHelper(begin, end, value, lessThan);
310}
311
312template <typename Container, typename T>
313Q_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
318template <typename ForwardIterator>
319Q_OUTOFLINE_TEMPLATE void qDeleteAll(ForwardIterator begin, ForwardIterator end)
320{
321 while (begin != end) {
322 delete *begin;
323 ++begin;
324 }
325}
326
327template <typename Container>
328inline 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*/
337namespace QAlgorithmsPrivate {
338
339template <typename RandomAccessIterator, typename T, typename LessThan>
340Q_OUTOFLINE_TEMPLATE void qSortHelper(RandomAccessIterator start, RandomAccessIterator end, const T &t, LessThan lessThan)
341{
342top:
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
392template <typename RandomAccessIterator, typename T>
393inline void qSortHelper(RandomAccessIterator begin, RandomAccessIterator end, const T &dummy)
394{
395 qSortHelper(begin, end, dummy, qLess<T>());
396}
397
398template <typename RandomAccessIterator>
399Q_OUTOFLINE_TEMPLATE void qReverse(RandomAccessIterator begin, RandomAccessIterator end)
400{
401 --end;
402 while (begin < end)
403 qSwap(*begin++, *end--);
404}
405
406template <typename RandomAccessIterator>
407Q_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
414template <typename RandomAccessIterator, typename T, typename LessThan>
415Q_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
449template <typename RandomAccessIterator, typename T, typename LessThan>
450Q_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
462template <typename RandomAccessIterator, typename T>
463inline void qStableSortHelper(RandomAccessIterator begin, RandomAccessIterator end, const T &dummy)
464{
465 qStableSortHelper(begin, end, dummy, qLess<T>());
466}
467
468template <typename RandomAccessIterator, typename T, typename LessThan>
469Q_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
489template <typename RandomAccessIterator, typename T, typename LessThan>
490Q_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
509template <typename RandomAccessIterator, typename T, typename LessThan>
510Q_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
522QT_END_NAMESPACE
523
524QT_END_HEADER
525
526#endif // QALGORITHMS_H
527