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
45using namespace std;
46
47class tst_QAlgorithms : public QObject
48{
49 Q_OBJECT
50private 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
107private:
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
123class TestInt
124{
125public:
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;
130static long int lessThanRefCount;
131};
132
133long int TestInt::lessThanRefCount;
134
135
136QStringList dataSetTypes = QStringList() << "Random" << "Ascending"
137 << "Descending" << "Equal" << "Duplicates" << "Almost Sorted" ;
138
139template <typename DataType>
140QVector<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
171struct ResultSet
172{
173 int numSorts;
174 long int lessThanRefCount;
175};
176
177
178template <typename ContainerType, typename Algorithm>
179ResultSet 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
195template <typename ContainerType, typename LessThan>
196bool 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
205template <typename ContainerType>
206bool isSorted(ContainerType &container)
207{
208 return isSorted(container, qLess<typename ContainerType::value_type>());
209}
210
211
212#if Q_TEST_PERFORMANCE
213void 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
222template <typename ContainerType>
223void 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
234template <typename Algorithm, typename DataType>
235QList<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
247template <typename Algorithm, typename DataType>
248void 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
270void 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
382namespace 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
390void 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
404void 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
415void tst_QAlgorithms::sortEmptyList()
416{
417 // Only test if it crashes
418 QStringList stringList;
419 stringList.sort();
420 QVERIFY(true);
421}
422
423void 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
449void 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
458void 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
471void 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
480void 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
492void 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
506void 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
526void 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
535void 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
571class StableSortTest
572{
573public:
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
579int Major;
580int Minor;
581};
582
583ostream &operator<<(ostream &out, const StableSortTest& obj) { out << obj.Major << "-" << obj.Minor; return out; }
584
585QVector<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
596template <typename ContainerType, typename LessThan>
597bool 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
613void 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
667void 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
680void 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
700void 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
742template <typename DataType>
743class QuickSortHelper
744{
745public:
746 void operator()(QVector<DataType> list)
747 {
748 ::qSort(list);
749 }
750};
751
752template <typename DataType>
753class StableSortHelper
754{
755public:
756 void operator()(QVector<DataType> list)
757 {
758 ::qStableSort(list);
759 }
760};
761
762template <typename DataType>
763class StlSortHelper
764{
765public:
766 void operator()(QVector<DataType> list)
767 {
768 std::sort(list.begin(), list.end());
769 }
770};
771
772template <typename DataType>
773class StlStableSortHelper
774{
775public:
776 void operator()(QVector<DataType> list)
777 {
778 std::stable_sort(list.begin(), list.end());
779 }
780};
781
782#if Q_TEST_PERFORMANCE
783void 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
805void 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
842void 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
879class 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
1051void 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:
1064static 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};
1068Q_STATIC_ASSERT(sizeof bitsSetInNibble / sizeof *bitsSetInNibble == 16);
1069
1070static Q_DECL_CONSTEXPR uint bitsSetInByte(quint8 byte)
1071{
1072 return bitsSetInNibble[byte & 0xF] + bitsSetInNibble[byte >> 4];
1073}
1074static Q_DECL_CONSTEXPR uint bitsSetInShort(quint16 word)
1075{
1076 return bitsSetInByte(byte: word & 0xFF) + bitsSetInByte(byte: word >> 8);
1077}
1078static Q_DECL_CONSTEXPR uint bitsSetInInt(quint32 word)
1079{
1080 return bitsSetInShort(word: word & 0xFFFF) + bitsSetInShort(word: word >> 16);
1081}
1082static Q_DECL_CONSTEXPR uint bitsSetInInt64(quint64 word)
1083{
1084 return bitsSetInInt(word: word & 0xFFFFFFFF) + bitsSetInInt(word: word >> 32);
1085}
1086
1087
1088void 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
1118template <typename T_Int>
1119void 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
1129void 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
1161template <typename T_Int>
1162void 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
1172void 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
1198template <typename T_Int>
1199void 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
1209QTEST_APPLESS_MAIN(tst_QAlgorithms)
1210#include "tst_qalgorithms.moc"
1211
1212

source code of qtbase/tests/auto/corelib/tools/qalgorithms/tst_qalgorithms.cpp