Ensure stable sort in QListWidget

QlistWidgets with sorting enabled do not sort stable. A re-sort is
triggered when any Qt::ItemDataRole is changed and not only when
Qt::DisplayRole is changed. Due to an unstable optimization, the changed
element gets inserted at the beginning of their respective "equivalence
group".

This patch disables the optimization and ensures stable sorting
with std::stable_sort. Sorting is only performed, if the subset of
changed items in the range [begin, end] is not already sorted in the
whole list. For this purpose, it is assumed that the list has already been sorted before begin and after end. This assumption minimizes the subset to check.

Limits / side effect:
The patch focuses on the most common use case, which is a single item being changed. Replacing the optimization by std:stable_sort can potentially slow down the sorting performance of large data sets.

Task-number: QTBUG-113123
Pick-to: 6.5 6.6
Change-Id: Ib2bd08f21422eb7d6aeff7cdd6a91be7114ebcba
Reviewed-by: Axel Spoerl <axel.spoerl@qt.io>

2 files changed, 83 insertions, 65 deletions

diff --git a/src/widgets/itemviews/qlistwidget.cpp b/src/widgets/itemviews/qlistwidget.cpp
index cc0ccf84da..695cca049e 100644
--- a/src/widgets/itemviews/qlistwidget.cpp
+++ b/src/widgets/itemviews/qlistwidget.cpp
@@ -308,7 +308,7 @@ void QListModel::sort(int column, Qt::SortOrder order)
     }
 
     const auto compare = (order == Qt::AscendingOrder ? &itemLessThan : &itemGreaterThan);
-    std::sort(sorting.begin(), sorting.end(), compare);
+    std::stable_sort(sorting.begin(), sorting.end(), compare);
     QModelIndexList fromIndexes;
     QModelIndexList toIndexes;
     const int sortingCount = sorting.size();
@@ -328,76 +328,34 @@ void QListModel::sort(int column, Qt::SortOrder order)
 /**
  * This function assumes that all items in the model except the items that are between
  * (inclusive) start and end are sorted.
- * With these assumptions, this function can ensure that the model is sorted in a
- * much more efficient way than doing a naive 'sort everything'.
- * (provided that the range is relatively small compared to the total number of items)
  */
 void QListModel::ensureSorted(int column, Qt::SortOrder order, int start, int end)
 {
     if (column != 0)
         return;
 
-    const int count = end - start + 1;
-    QList<QPair<QListWidgetItem *, int>> sorting(count);
-    for (int i = 0; i < count; ++i) {
-        sorting[i].first = items.at(start + i);
-        sorting[i].second = start + i;
-    }
-
-    const auto compare = (order == Qt::AscendingOrder ? &itemLessThan : &itemGreaterThan);
-    std::sort(sorting.begin(), sorting.end(), compare);
-
-    QModelIndexList oldPersistentIndexes = persistentIndexList();
-    QModelIndexList newPersistentIndexes = oldPersistentIndexes;
-    QList<QListWidgetItem*> tmp = items;
-    QList<QListWidgetItem*>::iterator lit = tmp.begin();
-    bool changed = false;
-    for (int i = 0; i < count; ++i) {
-        int oldRow = sorting.at(i).second;
-        int tmpitepos = lit - tmp.begin();
-        QListWidgetItem *item = tmp.takeAt(oldRow);
-        if (tmpitepos > tmp.size())
-            --tmpitepos;
-        lit = tmp.begin() + tmpitepos;
-        lit = sortedInsertionIterator(lit, tmp.end(), order, item);
-        int newRow = qMax<qsizetype>(lit - tmp.begin(), 0);
-        lit = tmp.insert(lit, item);
-        if (newRow != oldRow) {
-            if (!changed) {
-                emit layoutAboutToBeChanged({}, QAbstractItemModel::VerticalSortHint);
-                oldPersistentIndexes = persistentIndexList();
-                newPersistentIndexes = oldPersistentIndexes;
-                changed = true;
-            }
-            for (int j = i + 1; j < count; ++j) {
-                int otherRow = sorting.at(j).second;
-                if (oldRow < otherRow && newRow >= otherRow)
-                    --sorting[j].second;
-                else if (oldRow > otherRow && newRow <= otherRow)
-                    ++sorting[j].second;
-            }
-            for (int k = 0; k < newPersistentIndexes.size(); ++k) {
-                QModelIndex pi = newPersistentIndexes.at(k);
-                int oldPersistentRow = pi.row();
-                int newPersistentRow = oldPersistentRow;
-                if (oldPersistentRow == oldRow)
-                    newPersistentRow = newRow;
-                else if (oldRow < oldPersistentRow && newRow >= oldPersistentRow)
-                    newPersistentRow = oldPersistentRow - 1;
-                else if (oldRow > oldPersistentRow && newRow <= oldPersistentRow)
-                    newPersistentRow = oldPersistentRow + 1;
-                if (newPersistentRow != oldPersistentRow)
-                    newPersistentIndexes[k] = createIndex(newPersistentRow,
-                                                          pi.column(), pi.internalPointer());
-            }
-        }
-    }
-
-    if (changed) {
-        items = tmp;
-        changePersistentIndexList(oldPersistentIndexes, newPersistentIndexes);
-        emit layoutChanged({}, QAbstractItemModel::VerticalSortHint);
-    }
+    const auto compareLt = [](const QListWidgetItem *left, const QListWidgetItem *right) -> bool {
+        return *left < *right;
+    };
+
+    const auto compareGt = [](const QListWidgetItem *left, const QListWidgetItem *right) -> bool {
+        return *right < *left;
+    };
+
+    /** Check if range [start,end] is already in sorted position in list.
+     *  Take for this the assumption, that outside [start,end] the list
+     *  is already sorted. Therefore the sorted check has to be extended
+     *  to the first element that is known to be sorted before the range
+     *  [start, end], which is (start-1) and the first element after the
+     *  range [start, end], which is (end+2) due to end being included.
+    */
+    const auto beginChangedIterator = items.constBegin() + qMax(start - 1, 0);
+    const auto endChangedIterator = items.constBegin() + qMin(end + 2, items.size());
+    const bool needsSorting = !std::is_sorted(beginChangedIterator, endChangedIterator,
+                                              order == Qt::AscendingOrder ? compareLt : compareGt);
+
+    if (needsSorting)
+        sort(column, order);
 }
 
 bool QListModel::itemLessThan(const QPair<QListWidgetItem*,int> &left,
diff --git a/tests/auto/widgets/itemviews/qlistwidget/tst_qlistwidget.cpp b/tests/auto/widgets/itemviews/qlistwidget/tst_qlistwidget.cpp
index 07973d7225..f017e0e06b 100644
--- a/tests/auto/widgets/itemviews/qlistwidget/tst_qlistwidget.cpp
+++ b/tests/auto/widgets/itemviews/qlistwidget/tst_qlistwidget.cpp
@@ -75,6 +75,8 @@ private slots:
     void sortItems();
     void sortHiddenItems();
     void sortHiddenItems_data();
+    void sortCheckStability_data();
+    void sortCheckStability();
     void closeEditor();
     void setData_data();
     void setData();
@@ -1131,6 +1133,64 @@ void tst_QListWidget::sortHiddenItems()
     delete tw;
 }
 
+void tst_QListWidget::sortCheckStability_data() {
+    QTest::addColumn<Qt::SortOrder>("order");
+    QTest::addColumn<QVariantList>("initialList");
+    QTest::addColumn<QVariantList>("expectedList");
+
+    QTest::newRow("ascending strings")
+            << Qt::AscendingOrder
+            << QVariantList{ QString("a"), QString("b"), QString("b"), QString("a")}
+            << QVariantList{ QString("a"), QString("a"), QString("b"), QString("b")};
+
+    QTest::newRow("descending strings")
+            << Qt::DescendingOrder
+            << QVariantList{ QString("a"), QString("b"), QString("b"), QString("a")}
+            << QVariantList{ QString("b"), QString("b"), QString("a"), QString("a")};
+
+    QTest::newRow("ascending numbers")
+            << Qt::AscendingOrder
+            << QVariantList{ 1, 2, 2, 1}
+            << QVariantList{ 1, 1, 2, 2};
+
+    QTest::newRow("descending numbers")
+            << Qt::DescendingOrder
+            << QVariantList{ 1, 2, 2, 1}
+            << QVariantList{ 2, 2, 1, 1};
+}
+
+void tst_QListWidget::sortCheckStability() {
+    QFETCH(Qt::SortOrder, order);
+    QFETCH(const QVariantList, initialList);
+    QFETCH(const QVariantList, expectedList);
+
+    for (const QVariant &data : initialList) {
+        QListWidgetItem *item = new QListWidgetItem(testWidget);
+        item->setData(Qt::DisplayRole, data);
+    }
+
+    QAbstractItemModel *model = testWidget->model();
+    QList<QPersistentModelIndex> persistent;
+    for (int j = 0; j < model->rowCount(QModelIndex()); ++j)
+        persistent << model->index(j, 0, QModelIndex());
+
+    testWidget->sortItems(order);
+
+    QCOMPARE(testWidget->count(), expectedList.size());
+    for (int i = 0; i < testWidget->count(); ++i)
+        QCOMPARE(testWidget->item(i)->text(), expectedList.at(i).toString());
+
+    QVector<QListWidgetItem*> itemOrder(testWidget->count());
+    for (int i = 0; i < testWidget->count(); ++i)
+        itemOrder[i] = testWidget->item(i);
+
+    qobject_cast<QListModel*>(testWidget->model())->ensureSorted(0, order, 1, 1);
+    testWidget->sortItems(order);
+
+    for (int i = 0; i < testWidget->count(); ++i)
+        QCOMPARE(itemOrder[i],testWidget->item(i));
+}
+
 class TestListWidget : public QListWidget
 {
     Q_OBJECT