Internal KFileItemModel optimizations and cleanups

- Use merge-sort instead of quick-sort. This assures a sane
  worst-case scenario where quick-sort has a runtime complexity of
  O(n*n) (e.g. when changing the sort-order from ascending to
  descending).

- lessThan()-improvements: Change internal data-structures to
  allow a comparison of any role, not only roles available
  in KFileItem

- Don't synchronously move an item if the value has been changed
  of a role defined as sort-role: This is too expensive in case if
  e.g. the sorting is done by "type" and the type is determined
  step by step.

1 files changed, 12 insertions, 6 deletions

diff --git a/src/tests/kfileitemmodeltest.cpp b/src/tests/kfileitemmodeltest.cpp
index 2dbefc6b6..c41fcb6df 100644
--- a/src/tests/kfileitemmodeltest.cpp
+++ b/src/tests/kfileitemmodeltest.cpp
@@ -195,6 +195,7 @@ void KFileItemModelTest::testSetDataWithModifiedSortRole_data()
 {
     QTest::addColumn<int>("changedIndex");
     QTest::addColumn<int>("changedRating");
+    QTest::addColumn<bool>("expectMoveSignal");
     QTest::addColumn<int>("ratingIndex0");
     QTest::addColumn<int>("ratingIndex1");
     QTest::addColumn<int>("ratingIndex2");
@@ -204,19 +205,20 @@ void KFileItemModelTest::testSetDataWithModifiedSortRole_data()
     // Index 1 = rating 4
     // Index 2 = rating 6
 
-    QTest::newRow("Index 0: Rating 3") << 0 << 3 << 3 << 4 << 6;
-    QTest::newRow("Index 0: Rating 5") << 0 << 5 << 4 << 5 << 6;
-    QTest::newRow("Index 0: Rating 8") << 0 << 8 << 4 << 6 << 8;
+    QTest::newRow("Index 0: Rating 3") << 0 << 3 << false << 3 << 4 << 6;
+    QTest::newRow("Index 0: Rating 5") << 0 << 5 << true  << 4 << 5 << 6;
+    QTest::newRow("Index 0: Rating 8") << 0 << 8 << true  << 4 << 6 << 8;
 
-    QTest::newRow("Index 2: Rating 1") << 2 << 1 << 1 << 2 << 4;
-    QTest::newRow("Index 2: Rating 3") << 2 << 3 << 2 << 3 << 4;
-    QTest::newRow("Index 2: Rating 5") << 2 << 5 << 2 << 4 << 5;
+    QTest::newRow("Index 2: Rating 1") << 2 << 1 << true  << 1 << 2 << 4;
+    QTest::newRow("Index 2: Rating 3") << 2 << 3 << true  << 2 << 3 << 4;
+    QTest::newRow("Index 2: Rating 5") << 2 << 5 << false << 2 << 4 << 5;
 }
 
 void KFileItemModelTest::testSetDataWithModifiedSortRole()
 {
     QFETCH(int, changedIndex);
     QFETCH(int, changedRating);
+    QFETCH(bool, expectMoveSignal);
     QFETCH(int, ratingIndex0);
     QFETCH(int, ratingIndex1);
     QFETCH(int, ratingIndex2);
@@ -260,6 +262,10 @@ void KFileItemModelTest::testSetDataWithModifiedSortRole()
     rating.insert("rating", changedRating);
     m_model->setData(changedIndex, rating);
 
+    if (expectMoveSignal) {
+        QVERIFY(QTest::kWaitForSignal(m_model, SIGNAL(itemsMoved(KItemRange,QList<int>)), DefaultTimeout));
+    }
+    
     QCOMPARE(m_model->data(0).value("rating").toInt(), ratingIndex0);
     QCOMPARE(m_model->data(1).value("rating").toInt(), ratingIndex1);
     QCOMPARE(m_model->data(2).value("rating").toInt(), ratingIndex2);