1 | /**************************************************************************** |
2 | ** |
3 | ** Copyright (C) 2016 The Qt Company Ltd. |
4 | ** Contact: https://www.qt.io/licensing/ |
5 | ** |
6 | ** This file is part of the test suite of the Qt Toolkit. |
7 | ** |
8 | ** $QT_BEGIN_LICENSE:GPL-EXCEPT$ |
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 The Qt Company. For licensing terms |
14 | ** and conditions see https://www.qt.io/terms-conditions. For further |
15 | ** information use the contact form at https://www.qt.io/contact-us. |
16 | ** |
17 | ** GNU General Public License Usage |
18 | ** Alternatively, this file may be used under the terms of the GNU |
19 | ** General Public License version 3 as published by the Free Software |
20 | ** Foundation with exceptions as appearing in the file LICENSE.GPL3-EXCEPT |
21 | ** included in the packaging of this file. Please review the following |
22 | ** information to ensure the GNU General Public License requirements will |
23 | ** be met: https://www.gnu.org/licenses/gpl-3.0.html. |
24 | ** |
25 | ** $QT_END_LICENSE$ |
26 | ** |
27 | ****************************************************************************/ |
28 | |
29 | #include "../../../../../src/corelib/tools/qalgorithms.h" |
30 | #include <QtTest/QtTest> |
31 | |
32 | #include <iostream> |
33 | #include <iomanip> |
34 | #include <sstream> |
35 | #include <iterator> |
36 | #include <algorithm> |
37 | #include <qalgorithms.h> |
38 | #include <QStringList> |
39 | #include <QString> |
40 | #include <QRandomGenerator> |
41 | #include <QVector> |
42 | |
43 | #define Q_TEST_PERFORMANCE 0 |
44 | |
45 | using namespace std; |
46 | |
47 | class tst_QAlgorithms : public QObject |
48 | { |
49 | Q_OBJECT |
50 | private slots: |
51 | void swap(); |
52 | void swap2(); |
53 | void convenienceAPI(); |
54 | |
55 | #if QT_DEPRECATED_SINCE(5, 2) |
56 | void test_qLowerBound_data(); |
57 | void test_qLowerBound(); |
58 | void test_qUpperBound_data(); |
59 | void test_qUpperBound(); |
60 | void test_qBinaryFind_data(); |
61 | void test_qBinaryFind(); |
62 | void qBinaryFindOneEntry(); |
63 | void sortEmptyList(); |
64 | void sortedList(); |
65 | void sortAPItest(); |
66 | void stableSortTest(); |
67 | void stableSortCorrectnessTest_data(); |
68 | void stableSortCorrectnessTest(); |
69 | void convenienceAPI_deprecated(); |
70 | void qCountIterators() const; |
71 | void qCountContainer() const; |
72 | void binaryFindOnLargeContainer() const; |
73 | |
74 | #if Q_TEST_PERFORMANCE |
75 | void performance(); |
76 | #endif |
77 | |
78 | #endif // QT_DEPRECATED_SINCE(5, 2) |
79 | |
80 | void popCount08_data() { popCount_data_impl(sizeof_T_Int: sizeof(quint8 )); } |
81 | void popCount16_data() { popCount_data_impl(sizeof_T_Int: sizeof(quint16)); } |
82 | void popCount32_data() { popCount_data_impl(sizeof_T_Int: sizeof(quint32)); } |
83 | void popCount64_data() { popCount_data_impl(sizeof_T_Int: sizeof(quint64)); } |
84 | void popCount08() { popCount_impl<quint8 >(); } |
85 | void popCount16() { popCount_impl<quint16>(); } |
86 | void popCount32() { popCount_impl<quint32>(); } |
87 | void popCount64() { popCount_impl<quint64>(); } |
88 | |
89 | void countTrailing08_data() { countTrailing_data_impl(sizeof_T_Int: sizeof(quint8 )); } |
90 | void countTrailing16_data() { countTrailing_data_impl(sizeof_T_Int: sizeof(quint16)); } |
91 | void countTrailing32_data() { countTrailing_data_impl(sizeof_T_Int: sizeof(quint32)); } |
92 | void countTrailing64_data() { countTrailing_data_impl(sizeof_T_Int: sizeof(quint64)); } |
93 | void countTrailing08() { countTrailing_impl<quint8 >(); } |
94 | void countTrailing16() { countTrailing_impl<quint16>(); } |
95 | void countTrailing32() { countTrailing_impl<quint32>(); } |
96 | void countTrailing64() { countTrailing_impl<quint64>(); } |
97 | |
98 | void countLeading08_data() { countLeading_data_impl(sizeof_T_Int: sizeof(quint8 )); } |
99 | void countLeading16_data() { countLeading_data_impl(sizeof_T_Int: sizeof(quint16)); } |
100 | void countLeading32_data() { countLeading_data_impl(sizeof_T_Int: sizeof(quint32)); } |
101 | void countLeading64_data() { countLeading_data_impl(sizeof_T_Int: sizeof(quint64)); } |
102 | void countLeading08() { countLeading_impl<quint8 >(); } |
103 | void countLeading16() { countLeading_impl<quint16>(); } |
104 | void countLeading32() { countLeading_impl<quint32>(); } |
105 | void countLeading64() { countLeading_impl<quint64>(); } |
106 | |
107 | private: |
108 | void popCount_data_impl(size_t sizeof_T_Int); |
109 | template <typename T_Int> |
110 | void popCount_impl(); |
111 | |
112 | void countTrailing_data_impl(size_t sizeof_T_Int); |
113 | template <typename T_Int> |
114 | void countTrailing_impl(); |
115 | |
116 | void countLeading_data_impl(size_t sizeof_T_Int); |
117 | template <typename T_Int> |
118 | void countLeading_impl(); |
119 | }; |
120 | |
121 | #if QT_DEPRECATED_SINCE(5, 2) |
122 | |
123 | class TestInt |
124 | { |
125 | public: |
126 | TestInt(int number) :m_number(number) {} ; |
127 | TestInt() : m_number(0) {}; |
128 | bool operator<(const TestInt &other) const { ++TestInt::lessThanRefCount; return (m_number < other.m_number); } |
129 | int m_number; |
130 | static long int lessThanRefCount; |
131 | }; |
132 | |
133 | long int TestInt::lessThanRefCount; |
134 | |
135 | |
136 | QStringList dataSetTypes = QStringList() << "Random" << "Ascending" |
137 | << "Descending" << "Equal" << "Duplicates" << "Almost Sorted" ; |
138 | |
139 | template <typename DataType> |
140 | QVector<DataType> generateData(QString dataSetType, const int length) |
141 | { |
142 | QVector<DataType> container; |
143 | if (dataSetType == "Random" ) { |
144 | for (int i = 0; i < length; ++i) |
145 | container.append(QRandomGenerator::global()->generate()); |
146 | } else if (dataSetType == "Ascending" ) { |
147 | for (int i = 0; i < length; ++i) |
148 | container.append(i); |
149 | } else if (dataSetType == "Descending" ) { |
150 | for (int i = 0; i < length; ++i) |
151 | container.append(length - i); |
152 | } else if (dataSetType == "Equal" ) { |
153 | for (int i = 0; i < length; ++i) |
154 | container.append(43); |
155 | } else if (dataSetType == "Duplicates" ) { |
156 | for (int i = 0; i < length; ++i) |
157 | container.append(i % 10); |
158 | } else if (dataSetType == "Almost Sorted" ) { |
159 | for (int i = 0; i < length; ++i) |
160 | container.append(i); |
161 | for (int i = 0; i <= length / 10; ++i) { |
162 | const int iswap = i * 9; |
163 | DataType tmp = container.at(iswap); |
164 | container[iswap] = container.at(iswap + 1); |
165 | container[iswap + 1] = tmp; |
166 | } |
167 | } |
168 | return container; |
169 | } |
170 | |
171 | struct ResultSet |
172 | { |
173 | int numSorts; |
174 | long int lessThanRefCount; |
175 | }; |
176 | |
177 | |
178 | template <typename ContainerType, typename Algorithm> |
179 | ResultSet testRun(ContainerType &container, Algorithm &algorithm, int millisecs) |
180 | { |
181 | TestInt::lessThanRefCount = 0; |
182 | int count = 0; |
183 | QElapsedTimer t; |
184 | t.start(); |
185 | while(t.elapsed() < millisecs) { |
186 | ++count; |
187 | algorithm(container); |
188 | } |
189 | ResultSet result; |
190 | result.numSorts = count; |
191 | result.lessThanRefCount = TestInt::lessThanRefCount; |
192 | return result; |
193 | } |
194 | |
195 | template <typename ContainerType, typename LessThan> |
196 | bool isSorted(ContainerType &container, LessThan lessThan) |
197 | { |
198 | for (int i=0; i < container.count() - 1; ++i) |
199 | if (lessThan(container.at(i+1), container.at(i))) { |
200 | return false; |
201 | } |
202 | return true; |
203 | } |
204 | |
205 | template <typename ContainerType> |
206 | bool isSorted(ContainerType &container) |
207 | { |
208 | return isSorted(container, qLess<typename ContainerType::value_type>()); |
209 | } |
210 | |
211 | |
212 | #if Q_TEST_PERFORMANCE |
213 | void printHeader(QStringList &headers) |
214 | { |
215 | cout << setw(10) << setiosflags(ios_base::left) << " " ; |
216 | for (int h = 0; h < headers.count(); ++h) { |
217 | cout << setw(20) << setiosflags(ios_base::left) << headers.at(h).toLatin1().constData(); |
218 | } |
219 | cout << Qt::endl; |
220 | } |
221 | |
222 | template <typename ContainerType> |
223 | void print(ContainerType testContainer) |
224 | { |
225 | typedef typename ContainerType::value_type T; |
226 | |
227 | foreach(T value, testContainer) { |
228 | cout << value << " " ; |
229 | } |
230 | |
231 | cout << Qt::endl; |
232 | } |
233 | |
234 | template <typename Algorithm, typename DataType> |
235 | QList<ResultSet> testAlgorithm(Algorithm &algorithm, QStringList dataSetTypes, int size, int time) |
236 | { |
237 | QList<ResultSet> results; |
238 | foreach(QString dataSetType, dataSetTypes) { |
239 | QVector<DataType> container = generateData<DataType>(dataSetType, size); |
240 | results.append(testRun(container, algorithm, time)); |
241 | if (!isSorted(container)) |
242 | qWarning("%s: container is not sorted after test" , Q_FUNC_INFO); |
243 | } |
244 | return results; |
245 | } |
246 | |
247 | template <typename Algorithm, typename DataType> |
248 | void testAlgorithm(Algorithm algorithm, QStringList &dataSetTypes) |
249 | { |
250 | QList<int> sizes = QList<int>() << 5 << 15 << 35 << 70 << 200 << 1000 << 10000; |
251 | printHeader(dataSetTypes); |
252 | for (int s = 0; s < sizes.count(); ++s){ |
253 | cout << setw(10) << setiosflags(ios_base::left)<< sizes.at(s); |
254 | QList<ResultSet> results = |
255 | testAlgorithm<Algorithm, DataType>(algorithm, dataSetTypes, sizes.at(s), 100); |
256 | foreach(ResultSet result, results) { |
257 | stringstream numSorts; |
258 | numSorts << setiosflags(ios_base::left) << setw(10) << result.numSorts; |
259 | stringstream lessThan; |
260 | lessThan << setiosflags(ios_base::left) << setw(10) << result.lessThanRefCount / result.numSorts; |
261 | cout << numSorts.str() << lessThan.str(); |
262 | } |
263 | cout << Qt::endl; |
264 | } |
265 | } |
266 | #endif |
267 | |
268 | #endif // QT_DEPRECATED_SINCE(5, 2) |
269 | |
270 | void tst_QAlgorithms::swap() |
271 | { |
272 | { |
273 | int a = 1, b = 2; |
274 | qSwap(value1&: a, value2&: b); |
275 | QVERIFY(a == 2); |
276 | QVERIFY(b == 1); |
277 | |
278 | qSwap(value1&: a, value2&: a); |
279 | QVERIFY(a == 2); |
280 | QVERIFY(b == 1); |
281 | |
282 | qSwap(value1&: b, value2&: b); |
283 | QVERIFY(a == 2); |
284 | QVERIFY(b == 1); |
285 | |
286 | qSwap(value1&: a, value2&: b); |
287 | QVERIFY(a == 1); |
288 | QVERIFY(b == 2); |
289 | |
290 | qSwap(value1&: b, value2&: a); |
291 | QVERIFY(a == 2); |
292 | QVERIFY(b == 1); |
293 | } |
294 | |
295 | { |
296 | double a = 1.0, b = 2.0; |
297 | qSwap(value1&: a, value2&: b); |
298 | QVERIFY(a == 2.0); |
299 | QVERIFY(b == 1.0); |
300 | |
301 | qSwap(value1&: a, value2&: a); |
302 | QVERIFY(a == 2.0); |
303 | QVERIFY(b == 1.0); |
304 | |
305 | qSwap(value1&: b, value2&: b); |
306 | QVERIFY(a == 2.0); |
307 | QVERIFY(b == 1.0); |
308 | |
309 | qSwap(value1&: a, value2&: b); |
310 | QVERIFY(a == 1.0); |
311 | QVERIFY(b == 2.0); |
312 | |
313 | qSwap(value1&: b, value2&: a); |
314 | QVERIFY(a == 2.0); |
315 | QVERIFY(b == 1.0); |
316 | } |
317 | |
318 | { |
319 | QString a = "1" , b = "2" ; |
320 | qSwap(value1&: a, value2&: b); |
321 | QCOMPARE(a, QLatin1String("2" )); |
322 | QCOMPARE(b, QLatin1String("1" )); |
323 | |
324 | qSwap(value1&: a, value2&: a); |
325 | QCOMPARE(a, QLatin1String("2" )); |
326 | QCOMPARE(b, QLatin1String("1" )); |
327 | |
328 | qSwap(value1&: b, value2&: b); |
329 | QCOMPARE(a, QLatin1String("2" )); |
330 | QCOMPARE(b, QLatin1String("1" )); |
331 | |
332 | qSwap(value1&: a, value2&: b); |
333 | QCOMPARE(a, QLatin1String("1" )); |
334 | QCOMPARE(b, QLatin1String("2" )); |
335 | |
336 | qSwap(value1&: b, value2&: a); |
337 | QCOMPARE(a, QLatin1String("2" )); |
338 | QCOMPARE(b, QLatin1String("1" )); |
339 | } |
340 | |
341 | { |
342 | void *a = 0, *b = 0; |
343 | qSwap(value1&: a, value2&: b); |
344 | } |
345 | |
346 | { |
347 | const void *a = 0, *b = 0; |
348 | qSwap(value1&: a, value2&: b); |
349 | } |
350 | |
351 | { |
352 | QString *a = 0, *b = 0; |
353 | qSwap(value1&: a, value2&: b); |
354 | } |
355 | |
356 | { |
357 | const QString *a = 0, *b = 0; |
358 | qSwap(value1&: a, value2&: b); |
359 | } |
360 | |
361 | { |
362 | QString **a = 0, **b = 0; |
363 | qSwap(value1&: a, value2&: b); |
364 | } |
365 | |
366 | { |
367 | const QString **a = 0, **b = 0; |
368 | qSwap(value1&: a, value2&: b); |
369 | } |
370 | |
371 | { |
372 | QString * const *a = 0, * const *b = 0; |
373 | qSwap(value1&: a, value2&: b); |
374 | } |
375 | |
376 | { |
377 | const QString * const *a = 0, * const *b = 0; |
378 | qSwap(value1&: a, value2&: b); |
379 | } |
380 | } |
381 | |
382 | namespace SwapTest { |
383 | struct ST { int i; int j; }; |
384 | void swap(ST &a, ST &b) { |
385 | a.i = b.j; |
386 | b.i = a.j; |
387 | } |
388 | } |
389 | |
390 | void tst_QAlgorithms::swap2() |
391 | { |
392 | { |
393 | #ifndef QT_NO_SQL |
394 | //check the namespace lookup works correctly |
395 | SwapTest::ST a = { .i: 45, .j: 65 }; |
396 | SwapTest::ST b = { .i: 48, .j: 68 }; |
397 | qSwap(value1&: a, value2&: b); |
398 | QCOMPARE(a.i, 68); |
399 | QCOMPARE(b.i, 65); |
400 | #endif |
401 | } |
402 | } |
403 | |
404 | void tst_QAlgorithms::convenienceAPI() |
405 | { |
406 | // Compile-test for QAlgorithm convenience functions. |
407 | |
408 | QList<int *> pointerList; |
409 | qDeleteAll(c: pointerList); |
410 | qDeleteAll(begin: pointerList.begin(), end: pointerList.end()); |
411 | } |
412 | |
413 | #if QT_DEPRECATED_SINCE(5, 2) |
414 | |
415 | void tst_QAlgorithms::sortEmptyList() |
416 | { |
417 | // Only test if it crashes |
418 | QStringList stringList; |
419 | stringList.sort(); |
420 | QVERIFY(true); |
421 | } |
422 | |
423 | void tst_QAlgorithms::sortedList() |
424 | { |
425 | QList<int> list; |
426 | list << 4 << 3 << 6; |
427 | |
428 | ::qSort(start: list.begin(), end: list.end()); |
429 | |
430 | QCOMPARE(list.count(), 3); |
431 | QCOMPARE(list.at(0), 3); |
432 | QCOMPARE(list.at(1), 4); |
433 | QCOMPARE(list.at(2), 6); |
434 | |
435 | list.insert(before: qUpperBound(begin: list.begin(), end: list.end(), value: 5), t: 5); |
436 | list.insert(before: qUpperBound(begin: list.begin(), end: list.end(), value: 1), t: 1); |
437 | list.insert(before: qUpperBound(begin: list.begin(), end: list.end(), value: 8), t: 8); |
438 | |
439 | QCOMPARE(list.count(), 6); |
440 | QCOMPARE(list.at(0), 1); |
441 | QCOMPARE(list.at(1), 3); |
442 | QCOMPARE(list.at(2), 4); |
443 | QCOMPARE(list.at(3), 5); |
444 | QCOMPARE(list.at(4), 6); |
445 | QCOMPARE(list.at(5), 8); |
446 | } |
447 | |
448 | |
449 | void tst_QAlgorithms::test_qLowerBound_data() |
450 | { |
451 | QTest::addColumn<QList<int> >(name: "data" ); |
452 | QTest::addColumn<int>(name: "resultValue" ); |
453 | QTest::addColumn<int>(name: "resultIndex" ); |
454 | |
455 | QTest::newRow(dataTag: "sorted-duplicate" ) << (QList<int>() << 1 << 2 << 2 << 3) << 2 << 1; |
456 | } |
457 | |
458 | void tst_QAlgorithms::test_qLowerBound() |
459 | { |
460 | QFETCH(QList<int>, data); |
461 | QFETCH(int, resultValue); |
462 | QFETCH(int, resultIndex); |
463 | |
464 | |
465 | QCOMPARE(qLowerBound(data.constBegin(), data.constEnd(), resultValue), data.constBegin() + resultIndex); |
466 | QCOMPARE(qLowerBound(data.begin(), data.end(), resultValue), data.begin() + resultIndex); |
467 | QCOMPARE(qLowerBound(data, resultValue), data.constBegin() + resultIndex); |
468 | QCOMPARE(qLowerBound(data.constBegin(), data.constEnd(), resultValue, qLess<int>()), data.constBegin() + resultIndex); |
469 | } |
470 | |
471 | void tst_QAlgorithms::test_qUpperBound_data() |
472 | { |
473 | QTest::addColumn<QList<int> >(name: "data" ); |
474 | QTest::addColumn<int>(name: "resultValue" ); |
475 | QTest::addColumn<int>(name: "resultIndex" ); |
476 | |
477 | QTest::newRow(dataTag: "sorted-duplicate" ) << (QList<int>() << 1 << 2 << 2 << 3) << 2 << 3; |
478 | } |
479 | |
480 | void tst_QAlgorithms::test_qUpperBound() |
481 | { |
482 | QFETCH(QList<int>, data); |
483 | QFETCH(int, resultValue); |
484 | QFETCH(int, resultIndex); |
485 | |
486 | QCOMPARE(qUpperBound(data.constBegin(), data.constEnd(), resultValue), data.constBegin() + resultIndex); |
487 | QCOMPARE(qUpperBound(data.begin(), data.end(), resultValue), data.begin() + resultIndex); |
488 | QCOMPARE(qUpperBound(data, resultValue), data.constBegin() + resultIndex); |
489 | QCOMPARE(qUpperBound(data.constBegin(), data.constEnd(), resultValue, qLess<int>()), data.constBegin() + resultIndex); |
490 | } |
491 | |
492 | void tst_QAlgorithms::test_qBinaryFind_data() |
493 | { |
494 | QTest::addColumn<QList<int> >(name: "data" ); |
495 | QTest::addColumn<int>(name: "resultValue" ); // -42 means not found |
496 | |
497 | QTest::newRow(dataTag: "sorted-duplicate" ) << (QList<int>() << 1 << 2 << 2 << 3) << 2; |
498 | QTest::newRow(dataTag: "sorted-end" ) << (QList<int>() << -5 << -2 << 0 << 8) << 8; |
499 | QTest::newRow(dataTag: "sorted-beginning" ) << (QList<int>() << -5 << -2 << 0 << 8) << -5; |
500 | QTest::newRow(dataTag: "sorted-duplicate-beginning" ) << (QList<int>() << -5 << -5 << -2 << 0 << 8) << -5; |
501 | QTest::newRow(dataTag: "empty" ) << (QList<int>()) << -42; |
502 | QTest::newRow(dataTag: "not found 1 " ) << (QList<int>() << 1 << 5 << 8 << 65) << -42; |
503 | QTest::newRow(dataTag: "not found 2 " ) << (QList<int>() << -456 << -5 << 8 << 65) << -42; |
504 | } |
505 | |
506 | void tst_QAlgorithms::test_qBinaryFind() |
507 | { |
508 | QFETCH(QList<int>, data); |
509 | QFETCH(int, resultValue); |
510 | |
511 | //-42 means not found |
512 | if (resultValue == -42) { |
513 | QVERIFY(qBinaryFind(data.constBegin(), data.constEnd(), resultValue) == data.constEnd()); |
514 | QVERIFY(qBinaryFind(data, resultValue) == data.constEnd()); |
515 | QVERIFY(qBinaryFind(data.begin(), data.end(), resultValue) == data.end()); |
516 | QVERIFY(qBinaryFind(data.begin(), data.end(), resultValue, qLess<int>()) == data.end()); |
517 | return; |
518 | } |
519 | |
520 | QCOMPARE(*qBinaryFind(data.constBegin(), data.constEnd(), resultValue), resultValue); |
521 | QCOMPARE(*qBinaryFind(data.begin(), data.end(), resultValue), resultValue); |
522 | QCOMPARE(*qBinaryFind(data, resultValue), resultValue); |
523 | QCOMPARE(*qBinaryFind(data.constBegin(), data.constEnd(), resultValue, qLess<int>()), resultValue); |
524 | } |
525 | |
526 | void tst_QAlgorithms::qBinaryFindOneEntry() |
527 | { |
528 | QList<int> list; |
529 | list << 2; |
530 | |
531 | QVERIFY(::qBinaryFind(list.constBegin(), list.constEnd(), 2) != list.constEnd()); |
532 | } |
533 | |
534 | |
535 | void tst_QAlgorithms::sortAPItest() |
536 | { |
537 | QVector<int> testVector = generateData<int>(dataSetType: "Random" , length: 101); |
538 | qSort(c&: testVector); |
539 | QVERIFY(isSorted(testVector)); |
540 | qSort(start: testVector.begin(), end: testVector.end()); |
541 | QVERIFY(isSorted(testVector)); |
542 | qSort(start: testVector.begin(), end: testVector.end(), lessThan: qLess<int>()); |
543 | QVERIFY(isSorted(testVector)); |
544 | |
545 | testVector = generateData<int>(dataSetType: "Random" , length: 71); |
546 | qStableSort(c&: testVector); |
547 | QVERIFY(isSorted(testVector)); |
548 | qStableSort(start: testVector.begin(), end: testVector.end()); |
549 | QVERIFY(isSorted(testVector)); |
550 | qStableSort(start: testVector.begin(), end: testVector.end(), lessThan: qLess<int>()); |
551 | QVERIFY(isSorted(testVector)); |
552 | |
553 | QList<int> testList = generateData<int>(dataSetType: "Random" , length: 101).toList(); |
554 | qSort(c&: testList); |
555 | QVERIFY(isSorted(testList)); |
556 | qSort(start: testList.begin(), end: testList.end()); |
557 | QVERIFY(isSorted(testList)); |
558 | qSort(start: testList.begin(), end: testList.end(), lessThan: qLess<int>()); |
559 | QVERIFY(isSorted(testList)); |
560 | |
561 | testList = generateData<int>(dataSetType: "Random" , length: 71).toList(); |
562 | qStableSort(c&: testList); |
563 | QVERIFY(isSorted(testList)); |
564 | qStableSort(start: testList.begin(), end: testList.end()); |
565 | QVERIFY(isSorted(testList)); |
566 | qStableSort(start: testList.begin(), end: testList.end(), lessThan: qLess<int>()); |
567 | QVERIFY(isSorted(testList)); |
568 | } |
569 | |
570 | |
571 | class StableSortTest |
572 | { |
573 | public: |
574 | StableSortTest(){}; |
575 | StableSortTest(int Major, int Minor) : Major(Major), Minor(Minor) {} |
576 | bool operator<(const StableSortTest &other) const {return (Major < other.Major); } |
577 | bool testMinor(const StableSortTest &other) const {return Minor < other.Minor; } |
578 | |
579 | int Major; |
580 | int Minor; |
581 | }; |
582 | |
583 | ostream &operator<<(ostream &out, const StableSortTest& obj) { out << obj.Major << "-" << obj.Minor; return out; } |
584 | |
585 | QVector<StableSortTest> createStableTestVector() |
586 | { |
587 | QVector<StableSortTest> stableTestVector; |
588 | for (int i=500; i>=0; --i) { |
589 | for (int j=0; j<10; ++j) { |
590 | stableTestVector.append(t: StableSortTest(i, j)); |
591 | } |
592 | } |
593 | return stableTestVector; |
594 | } |
595 | |
596 | template <typename ContainerType, typename LessThan> |
597 | bool isStableSorted(ContainerType &container, LessThan lessThan) |
598 | { |
599 | for (int i=0; i < container.count() - 1; ++i) { |
600 | //not sorted? |
601 | if (lessThan(container.at(i + 1), container.at(i))) |
602 | return false; |
603 | // equal? |
604 | if (lessThan(container.at(i), container.at(i + 1))) |
605 | continue; |
606 | // minor version? |
607 | if(container.at(i + 1).testMinor(container.at(i))) |
608 | return false; |
609 | } |
610 | return true; |
611 | } |
612 | |
613 | void tst_QAlgorithms::stableSortTest() |
614 | { |
615 | // Selftests: |
616 | { |
617 | QVector<StableSortTest> stableTestVector = createStableTestVector(); |
618 | qSort(start: stableTestVector.begin(), end: stableTestVector.end(), lessThan: qLess<StableSortTest>()); |
619 | QVERIFY(isSorted(stableTestVector, qLess<StableSortTest>())); |
620 | QVERIFY(!isStableSorted(stableTestVector, qLess<StableSortTest>())); |
621 | } |
622 | { |
623 | QVector<StableSortTest> stableTestVector = createStableTestVector(); |
624 | qSort(start: stableTestVector.begin(), end: stableTestVector.end(), lessThan: qGreater<StableSortTest>()); |
625 | QVERIFY(isSorted(stableTestVector, qGreater<StableSortTest>())); |
626 | QVERIFY(!isStableSorted(stableTestVector, qGreater<StableSortTest>())); |
627 | } |
628 | { |
629 | QVector<StableSortTest> stableTestVector = createStableTestVector(); |
630 | qSort(start: stableTestVector.begin(), end: stableTestVector.end(), lessThan: qGreater<StableSortTest>()); |
631 | QVERIFY(!isSorted(stableTestVector, qLess<StableSortTest>())); |
632 | QVERIFY(!isStableSorted(stableTestVector, qGreater<StableSortTest>())); |
633 | } |
634 | |
635 | |
636 | // Stable sort with qLess |
637 | { |
638 | QVector<StableSortTest> stableTestVector = createStableTestVector(); |
639 | std::stable_sort(first: stableTestVector.begin(), last: stableTestVector.end(), comp: qLess<StableSortTest>()); |
640 | QVERIFY(isSorted(stableTestVector, qLess<StableSortTest>())); |
641 | QVERIFY(isStableSorted(stableTestVector, qLess<StableSortTest>())); |
642 | } |
643 | { |
644 | QVector<StableSortTest> stableTestVector = createStableTestVector(); |
645 | qStableSort(start: stableTestVector.begin(), end: stableTestVector.end(), lessThan: qLess<StableSortTest>()); |
646 | QVERIFY(isSorted(stableTestVector, qLess<StableSortTest>())); |
647 | QVERIFY(isStableSorted(stableTestVector, qLess<StableSortTest>())); |
648 | } |
649 | |
650 | // Stable sort with qGreater |
651 | { |
652 | QVector<StableSortTest> stableTestVector = createStableTestVector(); |
653 | std::stable_sort(first: stableTestVector.begin(), last: stableTestVector.end(), comp: qGreater<StableSortTest>()); |
654 | QVERIFY(isSorted(stableTestVector, qGreater<StableSortTest>())); |
655 | QVERIFY(isStableSorted(stableTestVector, qGreater<StableSortTest>())); |
656 | } |
657 | |
658 | { |
659 | QVector<StableSortTest> stableTestVector = createStableTestVector(); |
660 | qStableSort(start: stableTestVector.begin(), end: stableTestVector.end(), lessThan: qGreater<StableSortTest>()); |
661 | QVERIFY(isSorted(stableTestVector, qGreater<StableSortTest>())); |
662 | QVERIFY(isStableSorted(stableTestVector, qGreater<StableSortTest>())); |
663 | } |
664 | } |
665 | |
666 | |
667 | void tst_QAlgorithms::stableSortCorrectnessTest_data() |
668 | { |
669 | const int dataSize = 1000; |
670 | QTest::addColumn<QVector<int> >(name: "unsorted" ); |
671 | QTest::newRow(dataTag: "From documentation" ) << (QVector<int>() << 33 << 12 << 68 << 6 << 12); |
672 | QTest::newRow(dataTag: "Equal" ) << (generateData<int>(dataSetType: "Equal" , length: dataSize)); |
673 | QTest::newRow(dataTag: "Ascending" ) << (generateData<int>(dataSetType: "Ascending" , length: dataSize)); |
674 | QTest::newRow(dataTag: "Descending" ) << (generateData<int>(dataSetType: "Descending" , length: dataSize)); |
675 | QTest::newRow(dataTag: "Duplicates" ) << (generateData<int>(dataSetType: "Duplicates" , length: dataSize)); |
676 | QTest::newRow(dataTag: "Almost Sorted" ) << (generateData<int>(dataSetType: "Almost Sorted" , length: dataSize)); |
677 | QTest::newRow(dataTag: "Random" ) << (generateData<int>(dataSetType: "Random" , length: dataSize)); |
678 | } |
679 | |
680 | void tst_QAlgorithms::stableSortCorrectnessTest() |
681 | { |
682 | QFETCH(QVector<int>, unsorted); |
683 | |
684 | QVector<int> sorted = unsorted; |
685 | qStableSort(start: sorted.begin(), end: sorted.end()); |
686 | |
687 | // Verify that sorted contains the same numbers as unsorted. |
688 | foreach(int value, unsorted) { |
689 | QVERIFY(sorted.contains(value)); |
690 | int unsortedCount = 0; |
691 | qCount(first: unsorted.begin(), last: unsorted.end(), value, n&: unsortedCount); |
692 | int sortedCount = 0; |
693 | qCount(first: sorted.begin(), last: sorted.end(), value, n&: sortedCount); |
694 | QCOMPARE(sortedCount, unsortedCount); |
695 | } |
696 | |
697 | QVERIFY(isSorted(sorted)); |
698 | } |
699 | |
700 | void tst_QAlgorithms::convenienceAPI_deprecated() |
701 | { |
702 | // Compile-test for QAlgorithm convenience functions. |
703 | QList<int> list, list2; |
704 | |
705 | qCopy(begin: list.begin(), end: list.end(), dest: list2.begin()); |
706 | qCopyBackward(begin: list.begin(), end: list.end(), dest: list2.begin()); |
707 | qEqual(first1: list.begin(), last1: list.end(), first2: list2.begin()); |
708 | |
709 | qFill(container&: list, val: 1); |
710 | qFill(first: list.begin(), last: list.end(), val: 1); |
711 | |
712 | qFind(container: list, val: 1); |
713 | qFind(first: list.begin(), last: list.end(), val: 1); |
714 | |
715 | int count1 = 0 , count2 = 0, count3 = 0; |
716 | qCount(container: list, value: 1, n&: count1); |
717 | qCount(first: list.begin(), last: list.end(), value: 1, n&: count2); |
718 | QCOMPARE(count1, count2); |
719 | QCOMPARE(count2, count3); |
720 | |
721 | qSort(c&: list); |
722 | qSort(start: list.begin(), end: list.end()); |
723 | qSort(start: list.begin(), end: list.end(), lessThan: qLess<int>()); |
724 | |
725 | qStableSort(c&: list); |
726 | qStableSort(start: list.begin(), end: list.end()); |
727 | qStableSort(start: list.begin(), end: list.end(), lessThan: qLess<int>()); |
728 | |
729 | qLowerBound(container: list, value: 1);; |
730 | qLowerBound(begin: list.begin(), end: list.end(), value: 1); |
731 | qLowerBound(begin: list.begin(), end: list.end(), value: 1, lessThan: qLess<int>()); |
732 | |
733 | qUpperBound(container: list, value: 1); |
734 | qUpperBound(begin: list.begin(), end: list.end(), value: 1); |
735 | qUpperBound(begin: list.begin(), end: list.end(), value: 1, lessThan: qLess<int>()); |
736 | |
737 | qBinaryFind(container: list, value: 1); |
738 | qBinaryFind(begin: list.begin(), end: list.end(), value: 1); |
739 | qBinaryFind(begin: list.begin(), end: list.end(), value: 1, lessThan: qLess<int>()); |
740 | } |
741 | |
742 | template <typename DataType> |
743 | class QuickSortHelper |
744 | { |
745 | public: |
746 | void operator()(QVector<DataType> list) |
747 | { |
748 | ::qSort(list); |
749 | } |
750 | }; |
751 | |
752 | template <typename DataType> |
753 | class StableSortHelper |
754 | { |
755 | public: |
756 | void operator()(QVector<DataType> list) |
757 | { |
758 | ::qStableSort(list); |
759 | } |
760 | }; |
761 | |
762 | template <typename DataType> |
763 | class StlSortHelper |
764 | { |
765 | public: |
766 | void operator()(QVector<DataType> list) |
767 | { |
768 | std::sort(list.begin(), list.end()); |
769 | } |
770 | }; |
771 | |
772 | template <typename DataType> |
773 | class StlStableSortHelper |
774 | { |
775 | public: |
776 | void operator()(QVector<DataType> list) |
777 | { |
778 | std::stable_sort(list.begin(), list.end()); |
779 | } |
780 | }; |
781 | |
782 | #if Q_TEST_PERFORMANCE |
783 | void tst_QAlgorithms::performance() |
784 | { |
785 | cout << Qt::endl << "Quick sort" << Qt::endl; |
786 | testAlgorithm<QuickSortHelper<TestInt>, TestInt>(QuickSortHelper<TestInt>(), dataSetTypes); |
787 | cout << Qt::endl << "stable sort" << Qt::endl; |
788 | testAlgorithm<StableSortHelper<TestInt>, TestInt>(StableSortHelper<TestInt>(), dataSetTypes); |
789 | cout << Qt::endl << "std::sort" << Qt::endl; |
790 | testAlgorithm<StlSortHelper<TestInt>, TestInt>(StlSortHelper<TestInt>(), dataSetTypes); |
791 | cout << Qt::endl << "std::stable_sort" << Qt::endl; |
792 | testAlgorithm<StlStableSortHelper<TestInt>, TestInt>(StlStableSortHelper<TestInt>(), dataSetTypes); |
793 | /* |
794 | cout << Qt::endl << "Sorting lists of ints" << Qt::endl; |
795 | cout << Qt::endl << "Quick sort" << Qt::endl; |
796 | testAlgorithm<QuickSortHelper<int>, int>(QuickSortHelper<int>(), dataSetTypes); |
797 | cout << Qt::endl << "std::sort" << Qt::endl; |
798 | testAlgorithm<StlSortHelper<int>, int>(StlSortHelper<int>(), dataSetTypes); |
799 | cout << Qt::endl << "std::stable_sort" << Qt::endl; |
800 | testAlgorithm<StlStableSortHelper<int>, int>(StlStableSortHelper<int>(), dataSetTypes); |
801 | */ |
802 | } |
803 | #endif |
804 | |
805 | void tst_QAlgorithms::qCountIterators() const |
806 | { |
807 | QList<int> list; |
808 | list << 3 << 3 << 6 << 6 << 6 << 8; |
809 | |
810 | { |
811 | int countOf7 = 0; |
812 | ::qCount(first: list.begin(), last: list.end(), value: 7, n&: countOf7); |
813 | QCOMPARE(countOf7, 0); |
814 | } |
815 | |
816 | { |
817 | int countOf3 = 0; |
818 | ::qCount(first: list.begin(), last: list.end(), value: 3, n&: countOf3); |
819 | QCOMPARE(countOf3, 2); |
820 | } |
821 | |
822 | { |
823 | int countOf6 = 0; |
824 | ::qCount(first: list.begin(), last: list.end(), value: 6, n&: countOf6); |
825 | QCOMPARE(countOf6, 3); |
826 | } |
827 | |
828 | { |
829 | int countOf8 = 0; |
830 | ::qCount(first: list.begin(), last: list.end(), value: 8, n&: countOf8); |
831 | QCOMPARE(countOf8, 1); |
832 | } |
833 | |
834 | /* Check that we add to the count, not set it. */ |
835 | { |
836 | int countOf8 = 5; |
837 | ::qCount(first: list.begin(), last: list.end(), value: 8, n&: countOf8); |
838 | QCOMPARE(countOf8, 6); |
839 | } |
840 | } |
841 | |
842 | void tst_QAlgorithms::qCountContainer() const |
843 | { |
844 | QList<int> list; |
845 | list << 3 << 3 << 6 << 6 << 6 << 8; |
846 | |
847 | { |
848 | int countOf7 = 0; |
849 | ::qCount(container: list, value: 7, n&: countOf7); |
850 | QCOMPARE(countOf7, 0); |
851 | } |
852 | |
853 | { |
854 | int countOf3 = 0; |
855 | ::qCount(container: list, value: 3, n&: countOf3); |
856 | QCOMPARE(countOf3, 2); |
857 | } |
858 | |
859 | { |
860 | int countOf6 = 0; |
861 | ::qCount(container: list, value: 6, n&: countOf6); |
862 | QCOMPARE(countOf6, 3); |
863 | } |
864 | |
865 | { |
866 | int countOf8 = 0; |
867 | ::qCount(container: list, value: 8, n&: countOf8); |
868 | QCOMPARE(countOf8, 1); |
869 | } |
870 | |
871 | /* Check that we add to the count, not set it. */ |
872 | { |
873 | int countOf8 = 5; |
874 | ::qCount(container: list, value: 8, n&: countOf8); |
875 | QCOMPARE(countOf8, 6); |
876 | } |
877 | } |
878 | |
879 | class RAI |
880 | { |
881 | public: |
882 | typedef int difference_type; |
883 | typedef int value_type; |
884 | typedef std::random_access_iterator_tag iterator_category; |
885 | typedef int *pointer; |
886 | typedef int &reference; |
887 | |
888 | RAI(int searched = 5, int hidePos = 4, int len = 10) |
889 | : curPos_(0) |
890 | , length_(len) |
891 | , searchedVal_(searched) |
892 | , searchedValPos_(hidePos) |
893 | { |
894 | } |
895 | |
896 | int at(int pos) const |
897 | { |
898 | if (pos == searchedValPos_) { |
899 | return searchedVal_; |
900 | } |
901 | else if (pos < searchedValPos_) { |
902 | return searchedVal_ - 1; |
903 | } |
904 | |
905 | return searchedVal_ + 1; |
906 | } |
907 | |
908 | RAI begin() const |
909 | { |
910 | RAI rai = *this; |
911 | rai.setCurPos(0); |
912 | return rai; |
913 | } |
914 | |
915 | RAI end() const |
916 | { |
917 | RAI rai = *this; |
918 | rai.setCurPos(length_); |
919 | return rai; |
920 | } |
921 | |
922 | int pos() const |
923 | { |
924 | return curPos(); |
925 | } |
926 | |
927 | int size() const |
928 | { |
929 | return length_; |
930 | } |
931 | |
932 | RAI operator+(int i) const |
933 | { |
934 | RAI rai = *this; |
935 | rai.setCurPos( rai.curPos() + i ); |
936 | if (rai.curPos() > length_) { |
937 | rai.setCurPos(length_); |
938 | } |
939 | return rai; |
940 | } |
941 | |
942 | RAI operator-(int i) const |
943 | { |
944 | RAI rai = *this; |
945 | rai.setCurPos( rai.curPos() - i ); |
946 | if (rai.curPos() < 0) { |
947 | rai.setCurPos(0); |
948 | } |
949 | return rai; |
950 | } |
951 | |
952 | int operator-(const RAI& it) const |
953 | { |
954 | return curPos() - it.curPos(); |
955 | } |
956 | |
957 | RAI& operator+=(int i) |
958 | { |
959 | setCurPos( curPos() + i ); |
960 | if (curPos() > length_) { |
961 | setCurPos(length_); |
962 | } |
963 | return *this; |
964 | } |
965 | |
966 | RAI& operator-=(int i) |
967 | { |
968 | setCurPos( curPos() - i); |
969 | if (curPos() < 0) { |
970 | setCurPos(0); |
971 | } |
972 | return *this; |
973 | } |
974 | |
975 | RAI& operator++() |
976 | { |
977 | if (curPos() < length_) { |
978 | setCurPos( curPos() + 1 ); |
979 | } |
980 | return *this; |
981 | } |
982 | |
983 | RAI operator++(int) |
984 | { |
985 | RAI rai = *this; |
986 | |
987 | if (curPos() < length_) { |
988 | setCurPos( curPos() + 1 ); |
989 | } |
990 | |
991 | return rai; |
992 | } |
993 | |
994 | RAI& operator--() |
995 | { |
996 | if (curPos() > 0) { |
997 | setCurPos( curPos() - 1 ); |
998 | } |
999 | return *this; |
1000 | } |
1001 | |
1002 | RAI operator--(int) |
1003 | { |
1004 | RAI rai = *this; |
1005 | |
1006 | if (curPos() > 0) { |
1007 | setCurPos( curPos() - 1 ); |
1008 | } |
1009 | |
1010 | return rai; |
1011 | } |
1012 | |
1013 | bool operator==(const RAI& rai) const |
1014 | { |
1015 | return rai.curPos() == curPos(); |
1016 | } |
1017 | |
1018 | bool operator!=(const RAI& rai) const |
1019 | { |
1020 | return !operator==(rai); |
1021 | } |
1022 | |
1023 | int operator*() const |
1024 | { |
1025 | return at(pos: curPos()); |
1026 | } |
1027 | |
1028 | int operator[](int i) const |
1029 | { |
1030 | return at(pos: i); |
1031 | } |
1032 | |
1033 | private: |
1034 | |
1035 | int curPos() const |
1036 | { |
1037 | return curPos_; |
1038 | } |
1039 | |
1040 | void setCurPos(int pos) |
1041 | { |
1042 | curPos_ = pos; |
1043 | } |
1044 | |
1045 | int curPos_; |
1046 | int length_; |
1047 | int searchedVal_; |
1048 | int searchedValPos_; |
1049 | }; |
1050 | |
1051 | void tst_QAlgorithms::binaryFindOnLargeContainer() const |
1052 | { |
1053 | const int len = 2 * 1000 * 1000 * 537; |
1054 | const int pos = len - 12345; |
1055 | RAI rai(5, pos, len); |
1056 | |
1057 | RAI foundIt = qBinaryFind(begin: rai.begin(), end: rai.end(), value: 5); |
1058 | QCOMPARE(foundIt.pos(), 1073987655); |
1059 | } |
1060 | |
1061 | #endif // QT_DEPRECATED_SINCE(5, 2) |
1062 | |
1063 | // alternative implementation of qPopulationCount for comparison: |
1064 | static Q_DECL_CONSTEXPR const uint bitsSetInNibble[] = { |
1065 | 0, 1, 1, 2, 1, 2, 2, 3, |
1066 | 1, 2, 2, 3, 2, 3, 3, 4, |
1067 | }; |
1068 | Q_STATIC_ASSERT(sizeof bitsSetInNibble / sizeof *bitsSetInNibble == 16); |
1069 | |
1070 | static Q_DECL_CONSTEXPR uint bitsSetInByte(quint8 byte) |
1071 | { |
1072 | return bitsSetInNibble[byte & 0xF] + bitsSetInNibble[byte >> 4]; |
1073 | } |
1074 | static Q_DECL_CONSTEXPR uint bitsSetInShort(quint16 word) |
1075 | { |
1076 | return bitsSetInByte(byte: word & 0xFF) + bitsSetInByte(byte: word >> 8); |
1077 | } |
1078 | static Q_DECL_CONSTEXPR uint bitsSetInInt(quint32 word) |
1079 | { |
1080 | return bitsSetInShort(word: word & 0xFFFF) + bitsSetInShort(word: word >> 16); |
1081 | } |
1082 | static Q_DECL_CONSTEXPR uint bitsSetInInt64(quint64 word) |
1083 | { |
1084 | return bitsSetInInt(word: word & 0xFFFFFFFF) + bitsSetInInt(word: word >> 32); |
1085 | } |
1086 | |
1087 | |
1088 | void tst_QAlgorithms::popCount_data_impl(size_t sizeof_T_Int) |
1089 | { |
1090 | using namespace QTest; |
1091 | addColumn<quint64>(name: "input" ); |
1092 | addColumn<uint>(name: "expected" ); |
1093 | |
1094 | for (uint i = 0; i < UCHAR_MAX; ++i) { |
1095 | const uchar byte = static_cast<uchar>(i); |
1096 | const uint bits = bitsSetInByte(byte); |
1097 | const quint64 value = static_cast<quint64>(byte); |
1098 | const quint64 input = value << ((i % sizeof_T_Int) * 8U); |
1099 | QTest::addRow(format: "0x%016llx" , input) << input << bits; |
1100 | } |
1101 | |
1102 | // and some random ones: |
1103 | if (sizeof_T_Int >= 8) |
1104 | for (size_t i = 0; i < 1000; ++i) { |
1105 | const quint64 input = QRandomGenerator::global()->generate64(); |
1106 | QTest::addRow(format: "0x%016llx" , input) << input << bitsSetInInt64(word: input); |
1107 | } |
1108 | else if (sizeof_T_Int >= 2) |
1109 | for (size_t i = 0; i < 1000 ; ++i) { |
1110 | const quint32 input = QRandomGenerator::global()->generate(); |
1111 | if (sizeof_T_Int >= 4) |
1112 | QTest::addRow(format: "0x%08x" , input) << quint64(input) << bitsSetInInt(word: input); |
1113 | else |
1114 | QTest::addRow(format: "0x%04x" , quint16(input & 0xFFFF)) << quint64(input & 0xFFFF) << bitsSetInShort(word: input & 0xFFFF); |
1115 | } |
1116 | } |
1117 | |
1118 | template <typename T_Int> |
1119 | void tst_QAlgorithms::popCount_impl() |
1120 | { |
1121 | QFETCH(quint64, input); |
1122 | QFETCH(uint, expected); |
1123 | |
1124 | const T_Int value = static_cast<T_Int>(input); |
1125 | |
1126 | QCOMPARE(qPopulationCount(value), expected); |
1127 | } |
1128 | |
1129 | void tst_QAlgorithms::countTrailing_data_impl(size_t sizeof_T_Int) |
1130 | { |
1131 | using namespace QTest; |
1132 | addColumn<quint64>(name: "input" ); |
1133 | addColumn<uint>(name: "expected" ); |
1134 | |
1135 | int nibs = sizeof_T_Int*2; |
1136 | |
1137 | newRow(dataTag: ("0x" +QByteArray::number(0,base: 16).rightJustified(width: nibs,fill: '0')).constData()) << Q_UINT64_C(0) << uint(sizeof_T_Int*8); |
1138 | for (uint i = 0; i < sizeof_T_Int*8; ++i) { |
1139 | const quint64 input = Q_UINT64_C(1) << i; |
1140 | newRow(dataTag: ("0x" +QByteArray::number(input,base: 16).rightJustified(width: nibs,fill: '0')).constData()) << input << i; |
1141 | } |
1142 | |
1143 | quint64 type_mask; |
1144 | if (sizeof_T_Int>=8) |
1145 | type_mask = ~Q_UINT64_C(0); |
1146 | else |
1147 | type_mask = (Q_UINT64_C(1) << (sizeof_T_Int*8))-1; |
1148 | |
1149 | // and some random ones: |
1150 | for (uint i = 0; i < sizeof_T_Int*8; ++i) { |
1151 | for (uint j = 0; j < sizeof_T_Int*3; ++j) { // 3 is arbitrary |
1152 | const quint64 r = QRandomGenerator::global()->generate64(); |
1153 | const quint64 b = Q_UINT64_C(1) << i; |
1154 | const quint64 mask = ((~(b-1)) ^ b) & type_mask; |
1155 | const quint64 input = (r&mask) | b; |
1156 | newRow(dataTag: ("0x" +QByteArray::number(input,base: 16).rightJustified(width: nibs,fill: '0')).constData()) << input << i; |
1157 | } |
1158 | } |
1159 | } |
1160 | |
1161 | template <typename T_Int> |
1162 | void tst_QAlgorithms::countTrailing_impl() |
1163 | { |
1164 | QFETCH(quint64, input); |
1165 | QFETCH(uint, expected); |
1166 | |
1167 | const T_Int value = static_cast<T_Int>(input); |
1168 | |
1169 | QCOMPARE(qCountTrailingZeroBits(value), expected); |
1170 | } |
1171 | |
1172 | void tst_QAlgorithms::countLeading_data_impl(size_t sizeof_T_Int) |
1173 | { |
1174 | using namespace QTest; |
1175 | addColumn<quint64>(name: "input" ); |
1176 | addColumn<uint>(name: "expected" ); |
1177 | |
1178 | int nibs = sizeof_T_Int*2; |
1179 | |
1180 | newRow(dataTag: ("0x" +QByteArray::number(0,base: 16).rightJustified(width: nibs,fill: '0')).constData()) << Q_UINT64_C(0) << uint(sizeof_T_Int*8); |
1181 | for (uint i = 0; i < sizeof_T_Int*8; ++i) { |
1182 | const quint64 input = Q_UINT64_C(1) << i; |
1183 | newRow(dataTag: ("0x" +QByteArray::number(input,base: 16).rightJustified(width: nibs,fill: '0')).constData()) << input << uint(sizeof_T_Int*8-i-1); |
1184 | } |
1185 | |
1186 | // and some random ones: |
1187 | for (uint i = 0; i < sizeof_T_Int*8; ++i) { |
1188 | for (uint j = 0; j < sizeof_T_Int*3; ++j) { // 3 is arbitrary |
1189 | const quint64 r = QRandomGenerator::global()->generate64(); |
1190 | const quint64 b = Q_UINT64_C(1) << i; |
1191 | const quint64 mask = b-1; |
1192 | const quint64 input = (r&mask) | b; |
1193 | newRow(dataTag: ("0x" +QByteArray::number(input,base: 16).rightJustified(width: nibs,fill: '0')).constData()) << input << uint(sizeof_T_Int*8-i-1); |
1194 | } |
1195 | } |
1196 | } |
1197 | |
1198 | template <typename T_Int> |
1199 | void tst_QAlgorithms::countLeading_impl() |
1200 | { |
1201 | QFETCH(quint64, input); |
1202 | QFETCH(uint, expected); |
1203 | |
1204 | const T_Int value = static_cast<T_Int>(input); |
1205 | |
1206 | QCOMPARE(qCountLeadingZeroBits(value), expected); |
1207 | } |
1208 | |
1209 | QTEST_APPLESS_MAIN(tst_QAlgorithms) |
1210 | #include "tst_qalgorithms.moc" |
1211 | |
1212 | |