From c9eacfa1c791e2d228a3c8f0c119d02d7f46ee02 Mon Sep 17 00:00:00 2001 From: Thorvald Natvig Date: Tue, 1 Sep 2009 17:13:14 +0200 Subject: Make QTreeModel::ensureSorted() stable sort for items Id you have numerous items with the same value in the sort column, whenever you update one of them, they'll be placed at the head of the list instead of staying in place. For example, assume you have items a b(1) b(2) b(3) b(4) c (where all the b have the same value in the sort column) If you now emitDataChanged from b(3), ensureSorted() will be called. It will place b(3) in a list, and stable sort the list. It's just the one item since there was only one item updated. It than takes each item in the list, removes it's place from the "full" list of items, then reinserts it at the earliest point (using qLowerBound). End result: a b(3) b(1) b(2) b(4) c If you update all the items in the list (doing emitDataChanged() for each), this has the effect of reversing all the items with identical sort key. This patch checks if the old row is within the lower and upper bound of where the item might go, and if it is, simply reinserts it in its old place. Reviewed-by: Olivier Goffart Merge-Request: 1393 --- src/gui/itemviews/qtreewidget.cpp | 6 +- tests/auto/qtreewidget/tst_qtreewidget.cpp | 180 +++++++++++++++++++++++++++++ 2 files changed, 185 insertions(+), 1 deletion(-) diff --git a/src/gui/itemviews/qtreewidget.cpp b/src/gui/itemviews/qtreewidget.cpp index 7d6439f..6a7b27c 100644 --- a/src/gui/itemviews/qtreewidget.cpp +++ b/src/gui/itemviews/qtreewidget.cpp @@ -622,6 +622,10 @@ void QTreeModel::ensureSorted(int column, Qt::SortOrder order, QTreeWidgetItem *item = lst.takeAt(oldRow); lit = sortedInsertionIterator(lit, lst.end(), order, item); int newRow = qMax(lit - lst.begin(), 0); + + if ((newRow < oldRow) && !(*item < *lst.at(oldRow - 1))) + newRow = oldRow; + lit = lst.insert(lit, item); if (newRow != oldRow) { // we are going to change the persistent indexes, so we need to prepare @@ -2074,7 +2078,7 @@ void QTreeWidgetItemPrivate::sortChildren(int column, Qt::SortOrder order, bool { QTreeModel *model = (q->view ? qobject_cast(q->view->model()) : 0); if (!model) - return; + return; model->sortItems(&q->children, column, order); if (climb) { QList::iterator it = q->children.begin(); diff --git a/tests/auto/qtreewidget/tst_qtreewidget.cpp b/tests/auto/qtreewidget/tst_qtreewidget.cpp index 4e750f8..7db74ff 100644 --- a/tests/auto/qtreewidget/tst_qtreewidget.cpp +++ b/tests/auto/qtreewidget/tst_qtreewidget.cpp @@ -126,6 +126,8 @@ private slots: void insertExpandedItemsWithSorting(); void changeDataWithSorting_data(); void changeDataWithSorting(); + void changeDataWithStableSorting_data(); + void changeDataWithStableSorting(); void sortedIndexOfChild_data(); void sortedIndexOfChild(); @@ -2419,6 +2421,184 @@ void tst_QTreeWidget::changeDataWithSorting() QCOMPARE(layoutChangedSpy.count(), reorderingExpected ? 1 : 0); } +void tst_QTreeWidget::changeDataWithStableSorting_data() +{ + QTest::addColumn("sortOrder"); + QTest::addColumn("initialItems"); + QTest::addColumn("itemIndex"); + QTest::addColumn("newValue"); + QTest::addColumn("expectedItems"); + QTest::addColumn("expectedRows"); + QTest::addColumn("reorderingExpected"); + QTest::addColumn("forceChange"); + + QTest::newRow("change a to c in (a, c, c, c, e)") + << static_cast(Qt::AscendingOrder) + << (QStringList() << "a" << "c" << "c" << "c" << "e") + << 0 << "c" + << (QStringList() << "c" << "c" << "c" << "c" << "e") + << (IntList() << 0 << 1 << 2 << 3 << 4) + << false + << false; + QTest::newRow("change e to c in (a, c, c, c, e)") + << static_cast(Qt::AscendingOrder) + << (QStringList() << "a" << "c" << "c" << "c" << "e") + << 4 << "c" + << (QStringList() << "a" << "c" << "c" << "c" << "c") + << (IntList() << 0 << 1 << 2 << 3 << 4) + << false + << false; + QTest::newRow("change 1st c to c in (a, c, c, c, e)") + << static_cast(Qt::AscendingOrder) + << (QStringList() << "a" << "c" << "c" << "c" << "e") + << 1 << "c" + << (QStringList() << "a" << "c" << "c" << "c" << "e") + << (IntList() << 0 << 1 << 2 << 3 << 4) + << false + << true; + QTest::newRow("change 2nd c to c in (a, c, c, c, e)") + << static_cast(Qt::AscendingOrder) + << (QStringList() << "a" << "c" << "c" << "c" << "e") + << 2 << "c" + << (QStringList() << "a" << "c" << "c" << "c" << "e") + << (IntList() << 0 << 1 << 2 << 3 << 4) + << false + << true; + QTest::newRow("change 3rd c to c in (a, c, c, c, e)") + << static_cast(Qt::AscendingOrder) + << (QStringList() << "a" << "c" << "c" << "c" << "e") + << 3 << "c" + << (QStringList() << "a" << "c" << "c" << "c" << "e") + << (IntList() << 0 << 1 << 2 << 3 << 4) + << false + << true; + QTest::newRow("change 1st c to c in (e, c, c, c, a)") + << static_cast(Qt::DescendingOrder) + << (QStringList() << "e" << "c" << "c" << "c" << "a") + << 1 << "c" + << (QStringList() << "e" << "c" << "c" << "c" << "a") + << (IntList() << 0 << 1 << 2 << 3 << 4) + << false + << true; + QTest::newRow("change 2nd c to c in (e, c, c, c, a)") + << static_cast(Qt::DescendingOrder) + << (QStringList() << "e" << "c" << "c" << "c" << "a") + << 2 << "c" + << (QStringList() << "e" << "c" << "c" << "c" << "a") + << (IntList() << 0 << 1 << 2 << 3 << 4) + << false + << true; + QTest::newRow("change 3rd c to c in (e, c, c, c, a)") + << static_cast(Qt::DescendingOrder) + << (QStringList() << "e" << "c" << "c" << "c" << "a") + << 3 << "c" + << (QStringList() << "e" << "c" << "c" << "c" << "a") + << (IntList() << 0 << 1 << 2 << 3 << 4) + << false + << true; + QTest::newRow("change 1st c to b in (a, c, c, c, e)") + << static_cast(Qt::AscendingOrder) + << (QStringList() << "a" << "c" << "c" << "c" << "e") + << 1 << "b" + << (QStringList() << "a" << "b" << "c" << "c" << "e") + << (IntList() << 0 << 1 << 2 << 3 << 4) + << false + << false; + QTest::newRow("change 2nd c to b in (a, c, c, c, e)") + << static_cast(Qt::AscendingOrder) + << (QStringList() << "a" << "c" << "c" << "c" << "e") + << 2 << "b" + << (QStringList() << "a" << "b" << "c" << "c" << "e") + << (IntList() << 0 << 2 << 1 << 3 << 4) + << true + << false; + QTest::newRow("change 3rd c to b in (a, c, c, c, e)") + << static_cast(Qt::AscendingOrder) + << (QStringList() << "a" << "c" << "c" << "c" << "e") + << 3 << "b" + << (QStringList() << "a" << "b" << "c" << "c" << "e") + << (IntList() << 0 << 2 << 3 << 1 << 4) + << true + << false; + QTest::newRow("change 1st c to d in (a, c, c, c, e)") + << static_cast(Qt::AscendingOrder) + << (QStringList() << "a" << "c" << "c" << "c" << "e") + << 1 << "d" + << (QStringList() << "a" << "c" << "c" << "d" << "e") + << (IntList() << 0 << 3 << 1 << 2 << 4) + << true + << false; + QTest::newRow("change 2nd c to d in (a, c, c, c, e)") + << static_cast(Qt::AscendingOrder) + << (QStringList() << "a" << "c" << "c" << "c" << "e") + << 2 << "d" + << (QStringList() << "a" << "c" << "c" << "d" << "e") + << (IntList() << 0 << 1 << 3 << 2 << 4) + << true + << false; + QTest::newRow("change 3rd c to d in (a, c, c, c, e)") + << static_cast(Qt::AscendingOrder) + << (QStringList() << "a" << "c" << "c" << "c" << "e") + << 3 << "d" + << (QStringList() << "a" << "c" << "c" << "d" << "e") + << (IntList() << 0 << 1 << 2 << 3 << 4) + << false + << false; +} + +void tst_QTreeWidget::changeDataWithStableSorting() +{ + QFETCH(int, sortOrder); + QFETCH(QStringList, initialItems); + QFETCH(int, itemIndex); + QFETCH(QString, newValue); + QFETCH(QStringList, expectedItems); + QFETCH(IntList, expectedRows); + QFETCH(bool, reorderingExpected); + QFETCH(bool, forceChange); + + class StableItem : public QTreeWidgetItem + { + public: + StableItem(const QStringList &strings) : QTreeWidgetItem(strings, QTreeWidgetItem::UserType) {} + void forceChangeData() { + emitDataChanged(); + } + }; + + QTreeWidget w; + w.setSortingEnabled(true); + w.sortItems(0, static_cast(sortOrder)); + for (int i = 0; i < initialItems.count(); ++i) + w.addTopLevelItem(new StableItem(QStringList() << initialItems.at(i))); + + QAbstractItemModel *model = w.model(); + QList persistent; + for (int j = 0; j < model->rowCount(QModelIndex()); ++j) + persistent << model->index(j, 0, QModelIndex()); + + QSignalSpy dataChangedSpy(model, SIGNAL(dataChanged(const QModelIndex &, const QModelIndex &))); + QSignalSpy layoutChangedSpy(model, SIGNAL(layoutChanged())); + + StableItem *item = static_cast(w.topLevelItem(itemIndex)); + item->setText(0, newValue); + if (forceChange) + item->forceChangeData(); + for (int i = 0; i < expectedItems.count(); ++i) { + QCOMPARE(w.topLevelItem(i)->text(0), expectedItems.at(i)); + for (int j = 0; j < persistent.count(); ++j) { + if (persistent.at(j).row() == i) // the same toplevel row + QCOMPARE(persistent.at(j).internalPointer(), (void *)w.topLevelItem(i)); + } + } + + for (int k = 0; k < persistent.count(); ++k) + QCOMPARE(persistent.at(k).row(), expectedRows.at(k)); + + QCOMPARE(dataChangedSpy.count(), 1); + QCOMPARE(layoutChangedSpy.count(), reorderingExpected ? 1 : 0); +} + void tst_QTreeWidget::itemOperatorLessThan() { QTreeWidget tw; -- cgit v0.12