Use QCollator for sorting in the filesystem model

The old code was extremely inefficient, and QCollator
can provide the same functionality in a much better
and faster way.

Task-number: QTBUG-30902
Change-Id: Iaf5dbe587d9a6ebca26885259fdee74a29d3c84f
Reviewed-by: Edward Welbourne <edward.welbourne@theqtcompany.com>
Reviewed-by: Konstantin Ritt <ritt.ks@gmail.com>
Reviewed-by: Marc Mutz <marc.mutz@kdab.com>
Reviewed-by: Lars Knoll <lars.knoll@theqtcompany.com>

2 files changed, 11 insertions, 160 deletions

diff --git a/src/widgets/dialogs/qfilesystemmodel.cpp b/src/widgets/dialogs/qfilesystemmodel.cpp
index 6bce7e99f5..1b9a1129b2 100644
--- a/src/widgets/dialogs/qfilesystemmodel.cpp
+++ b/src/widgets/dialogs/qfilesystemmodel.cpp
@@ -39,6 +39,7 @@
 #include <qdebug.h>
 #include <qmessagebox.h>
 #include <qapplication.h>
+#include <QtCore/qcollator.h>
 
 #include <algorithm>
 
@@ -979,84 +980,6 @@ void QFileSystemModelPrivate::_q_performDelayedSort()
     q->sort(sortColumn, sortOrder);
 }
 
-static inline QChar getNextChar(const QString &s, int location)
-{
-    return (location < s.length()) ? s.at(location) : QChar();
-}
-
-/*!
-    Natural number sort, skips spaces.
-
-    Examples:
-    1, 2, 10, 55, 100
-    01.jpg, 2.jpg, 10.jpg
-
-    Note on the algorithm:
-    Only as many characters as necessary are looked at and at most they all
-    are looked at once.
-
-    Slower then QString::compare() (of course)
-  */
-int QFileSystemModelPrivate::naturalCompare(const QString &s1, const QString &s2,  Qt::CaseSensitivity cs)
-{
-    for (int l1 = 0, l2 = 0; l1 <= s1.count() && l2 <= s2.count(); ++l1, ++l2) {
-        // skip spaces, tabs and 0's
-        QChar c1 = getNextChar(s1, l1);
-        while (c1.isSpace())
-            c1 = getNextChar(s1, ++l1);
-        QChar c2 = getNextChar(s2, l2);
-        while (c2.isSpace())
-            c2 = getNextChar(s2, ++l2);
-
-        if (c1.isDigit() && c2.isDigit()) {
-            while (c1.digitValue() == 0)
-                c1 = getNextChar(s1, ++l1);
-            while (c2.digitValue() == 0)
-                c2 = getNextChar(s2, ++l2);
-
-            int lookAheadLocation1 = l1;
-            int lookAheadLocation2 = l2;
-            int currentReturnValue = 0;
-            // find the last digit, setting currentReturnValue as we go if it isn't equal
-            for (
-                QChar lookAhead1 = c1, lookAhead2 = c2;
-                (lookAheadLocation1 <= s1.length() && lookAheadLocation2 <= s2.length());
-                lookAhead1 = getNextChar(s1, ++lookAheadLocation1),
-                lookAhead2 = getNextChar(s2, ++lookAheadLocation2)
-                ) {
-                bool is1ADigit = !lookAhead1.isNull() && lookAhead1.isDigit();
-                bool is2ADigit = !lookAhead2.isNull() && lookAhead2.isDigit();
-                if (!is1ADigit && !is2ADigit)
-                    break;
-                if (!is1ADigit)
-                    return -1;
-                if (!is2ADigit)
-                    return 1;
-                if (currentReturnValue == 0) {
-                    if (lookAhead1 < lookAhead2) {
-                        currentReturnValue = -1;
-                    } else if (lookAhead1 > lookAhead2) {
-                        currentReturnValue = 1;
-                    }
-                }
-            }
-            if (currentReturnValue != 0)
-                return currentReturnValue;
-        }
-
-        if (cs == Qt::CaseInsensitive) {
-            if (!c1.isLower()) c1 = c1.toLower();
-            if (!c2.isLower()) c2 = c2.toLower();
-        }
-        int r = QString::localeAwareCompare(c1, c2);
-        if (r < 0)
-            return -1;
-        if (r > 0)
-            return 1;
-    }
-    // The two strings are the same (02 == 2) so fall back to the normal sort
-    return QString::compare(s1, s2, cs);
-}
 
 /*
     \internal
@@ -1065,7 +988,11 @@ int QFileSystemModelPrivate::naturalCompare(const QString &s1, const QString &s2
 class QFileSystemModelSorter
 {
 public:
-    inline QFileSystemModelSorter(int column) : sortColumn(column) {}
+    inline QFileSystemModelSorter(int column) : sortColumn(column)
+    {
+        naturalCompare.setNumericMode(true);
+        naturalCompare.setCaseSensitivity(Qt::CaseInsensitive);
+    }
 
     bool compareNodes(const QFileSystemModelPrivate::QFileSystemNode *l,
                     const QFileSystemModelPrivate::QFileSystemNode *r) const
@@ -1079,8 +1006,7 @@ public:
             if (left ^ right)
                 return left;
 #endif
-            return QFileSystemModelPrivate::naturalCompare(l->fileName,
-                                                r->fileName, Qt::CaseInsensitive) < 0;
+            return naturalCompare.compare(l->fileName, r->fileName) < 0;
                 }
         case 1:
         {
@@ -1092,7 +1018,7 @@ public:
 
             qint64 sizeDifference = l->size() - r->size();
             if (sizeDifference == 0)
-                return QFileSystemModelPrivate::naturalCompare(l->fileName, r->fileName, Qt::CaseInsensitive) < 0;
+                return naturalCompare.compare(l->fileName, r->fileName) < 0;
 
             return sizeDifference < 0;
         }
@@ -1100,14 +1026,14 @@ public:
         {
             int compare = QString::localeAwareCompare(l->type(), r->type());
             if (compare == 0)
-                return QFileSystemModelPrivate::naturalCompare(l->fileName, r->fileName, Qt::CaseInsensitive) < 0;
+                return naturalCompare.compare(l->fileName, r->fileName) < 0;
 
             return compare < 0;
         }
         case 3:
         {
             if (l->lastModified() == r->lastModified())
-                return QFileSystemModelPrivate::naturalCompare(l->fileName, r->fileName, Qt::CaseInsensitive) < 0;
+                return naturalCompare.compare(l->fileName, r->fileName) < 0;
 
             return l->lastModified() < r->lastModified();
         }
@@ -1124,6 +1050,7 @@ public:
 
 
 private:
+    QCollator naturalCompare;
     int sortColumn;
 };
 
diff --git a/tests/auto/widgets/dialogs/qfilesystemmodel/tst_qfilesystemmodel.cpp b/tests/auto/widgets/dialogs/qfilesystemmodel/tst_qfilesystemmodel.cpp
index 209048a853..3252650d12 100644
--- a/tests/auto/widgets/dialogs/qfilesystemmodel/tst_qfilesystemmodel.cpp
+++ b/tests/auto/widgets/dialogs/qfilesystemmodel/tst_qfilesystemmodel.cpp
@@ -78,10 +78,6 @@ private slots:
     void indexPath();
 
     void rootPath();
-#ifdef QT_BUILD_INTERNAL
-    void naturalCompare_data();
-    void naturalCompare();
-#endif
     void readOnly();
     void iconProvider();
 
@@ -242,78 +238,6 @@ void tst_QFileSystemModel::rootPath()
     }
 }
 
-#ifdef QT_BUILD_INTERNAL
-void tst_QFileSystemModel::naturalCompare_data()
-{
-    QTest::addColumn<QString>("s1");
-    QTest::addColumn<QString>("s2");
-    QTest::addColumn<int>("caseSensitive");
-    QTest::addColumn<int>("result");
-    QTest::addColumn<int>("swap");
-
-#define ROWNAME(name) (qPrintable(QString("prefix=%1, postfix=%2, num=%3, i=%4, test=%5").arg(prefix).arg(postfix).arg(num).arg(i).arg(name)))
-
-    for (int j = 0; j < 4; ++j) { // <- set a prefix and a postfix string (not numbers)
-        QString prefix = (j == 0 || j == 1) ? "b" : "";
-        QString postfix = (j == 1 || j == 2) ? "y" : "";
-
-        for (int k = 0; k < 3; ++k) { // <- make 0 not a special case
-            QString num = QString("%1").arg(k);
-            QString nump = QString("%1").arg(k + 1);
-            for (int i = 10; i < 12; ++i) { // <- swap s1 and s2 and reverse the result
-                QTest::newRow(ROWNAME("basic"))          << prefix + "0" + postfix << prefix + "0" + postfix << int(Qt::CaseInsensitive) << 0;
-
-                // s1 should always be less then s2
-                QTest::newRow(ROWNAME("just text"))      << prefix + "fred" + postfix     << prefix + "jane" + postfix << int(Qt::CaseInsensitive) << i;
-                QTest::newRow(ROWNAME("just numbers"))   << prefix + num + postfix        << prefix + "9" + postfix << int(Qt::CaseInsensitive) << i;
-                QTest::newRow(ROWNAME("zero"))           << prefix + num + postfix        << prefix + "0" + nump + postfix << int(Qt::CaseInsensitive) << i;
-                QTest::newRow(ROWNAME("space b"))        << prefix + num + postfix        << prefix + " " + nump + postfix << int(Qt::CaseInsensitive) << i;
-                QTest::newRow(ROWNAME("space a"))        << prefix + num + postfix        << prefix + nump + " " + postfix << int(Qt::CaseInsensitive) << i;
-                QTest::newRow(ROWNAME("tab b"))          << prefix + num + postfix        << prefix + "    " + nump + postfix << int(Qt::CaseInsensitive) << i;
-                QTest::newRow(ROWNAME("tab a"))          << prefix + num + postfix        << prefix + nump + "   " + postfix << int(Qt::CaseInsensitive) << i;
-                QTest::newRow(ROWNAME("10 vs 2"))        << prefix + num + postfix        << prefix + "10" + postfix << int(Qt::CaseInsensitive) << i;
-                QTest::newRow(ROWNAME("diff len"))       << prefix + num + postfix        << prefix + nump + postfix + "x" << int(Qt::CaseInsensitive) << i;
-                QTest::newRow(ROWNAME("01 before 1"))    << prefix + "0" + num + postfix  << prefix + nump + postfix << int(Qt::CaseInsensitive) << i;
-                QTest::newRow(ROWNAME("mul nums 2nd 1")) << prefix + "1-" + num + postfix << prefix + "1-" + nump + postfix << int(Qt::CaseInsensitive) << i;
-                QTest::newRow(ROWNAME("mul nums 2nd 2")) << prefix + "10-" + num + postfix<< prefix + "10-10" + postfix << int(Qt::CaseInsensitive) << i;
-                QTest::newRow(ROWNAME("mul nums 2nd 3")) << prefix + "10-0"+ num + postfix<< prefix + "10-10" + postfix << int(Qt::CaseInsensitive) << i;
-                QTest::newRow(ROWNAME("mul nums 2nd 4")) << prefix + "10-" + num + postfix<< prefix + "10-010" + postfix << int(Qt::CaseInsensitive) << i;
-                QTest::newRow(ROWNAME("mul nums big 1")) << prefix + "10-" + num + postfix<< prefix + "20-0" + postfix << int(Qt::CaseInsensitive) << i;
-                QTest::newRow(ROWNAME("mul nums big 2")) << prefix + "2-" + num + postfix << prefix + "10-0" + postfix << int(Qt::CaseInsensitive) << i;
-                QTest::newRow(ROWNAME("mul alphabet 1")) << prefix + num + "-a" + postfix << prefix + num + "-c" + postfix << int(Qt::CaseInsensitive) << i;
-                QTest::newRow(ROWNAME("mul alphabet 2")) << prefix + num + "-a9" + postfix<< prefix + num + "-c0" + postfix << int(Qt::CaseInsensitive) << i;
-                QTest::newRow(ROWNAME("mul nums w\\0"))  << prefix + num + "-"+ num + postfix<< prefix + num+"-0"+nump + postfix << int(Qt::CaseInsensitive) << i;
-                QTest::newRow(ROWNAME("num first"))      << prefix + num + postfix  << prefix + "a" + postfix << int(Qt::CaseInsensitive) << i;
-            }
-        }
-    }
-#undef ROWNAME
-}
-#endif
-
-#ifdef QT_BUILD_INTERNAL
-void tst_QFileSystemModel::naturalCompare()
-{
-    QFETCH(QString, s1);
-    QFETCH(QString, s2);
-    QFETCH(int, caseSensitive);
-    QFETCH(int, result);
-
-    if (result == 10)
-        QCOMPARE(QFileSystemModelPrivate::naturalCompare(s1, s2, Qt::CaseSensitivity(caseSensitive)), -1);
-    else
-        if (result == 11)
-            QCOMPARE(QFileSystemModelPrivate::naturalCompare(s2, s1, Qt::CaseSensitivity(caseSensitive)), 1);
-    else
-        QCOMPARE(QFileSystemModelPrivate::naturalCompare(s2, s1, Qt::CaseSensitivity(caseSensitive)), result);
-#if defined(Q_OS_WINCE)
-    // On Windows CE we need to wait after each test, otherwise no new threads can be
-    // created. The scheduler takes its time to recognize ended threads.
-    QTest::qWait(300);
-#endif
-}
-#endif
-
 void tst_QFileSystemModel::readOnly()
 {
     QCOMPARE(model->isReadOnly(), true);