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 | |
47 | QT_BEGIN_HEADER |
48 | |
49 | QT_BEGIN_NAMESPACE |
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> |
146 | LessThan qLess() |
147 | { |
148 | } |
149 | |
150 | template <typename T> |
151 | LessThan qGreater() |
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 | |
522 | QT_END_NAMESPACE |
523 | |
524 | QT_END_HEADER |
525 | |
526 | #endif // QALGORITHMS_H |
527 | |