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>

1 files changed, 11 insertions, 84 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;
 };