Fix O(N^2) complexity issue in KItemListView::slotItemsRemoved()

If many item ranges are removed, KItemListView::slotItemsRemoved()
could take very long because it looped over all items after the first
removed one for every removed range, even if most of these items are
not visible at all.

This commit improves this by just looping over the visible items (whose
number is limited by the window size) for each range.

Test case (for very large N):

touch {1..N}.png
touch {1..N}.jpg

(wait until all files are shown in the view)

rm *.jpg

REVIEW: 111398

diff --git a/src/kitemviews/kitemlistview.cpp b/src/kitemviews/kitemlistview.cpp
index 347a4e6ea19601d9e88491ac3f31238435589c36..d2b3fa103bf4a43f830f1aae918552e5de8d61e6 100644 (file)
--- a/src/kitemviews/kitemlistview.cpp
+++ b/src/kitemviews/kitemlistview.cpp
@@ -44,6 +44,8 @@
 #include <QStyleOptionRubberBand>
 #include <QTimer>
 
+#include <algorithm>
+
 #include "kitemlistviewaccessible.h"
 
 namespace {
@@ -1063,11 +1065,6 @@ void KItemListView::slotItemsRemoved(const KItemRangeList& itemRanges)
 
     m_layouter->markAsDirty();
 
-    int removedItemsCount = 0;
-    for (int i = 0; i < itemRanges.count(); ++i) {
-        removedItemsCount += itemRanges[i].count;
-    }
-
     m_sizeHintResolver->itemsRemoved(itemRanges);
 
     for (int i = itemRanges.count() - 1; i >= 0; --i) {
@@ -1081,13 +1078,17 @@ void KItemListView::slotItemsRemoved(const KItemRangeList& itemRanges)
 
         const int firstRemovedIndex = index;
         const int lastRemovedIndex = index + count - 1;
-        const int lastIndex = m_model->count() - 1 + removedItemsCount;
-        removedItemsCount -= count;
+
+        // Remeber which items have to be moved because they are behind the removed range.
+        QVector<int> itemsToMove;
 
         // Remove all KItemListWidget instances that got deleted
-        for (int i = firstRemovedIndex; i <= lastRemovedIndex; ++i) {
-            KItemListWidget* widget = m_visibleItems.value(i);
-            if (!widget) {
+        foreach (KItemListWidget* widget, m_visibleItems) {
+            const int i = widget->index();
+            if (i < firstRemovedIndex) {
+                continue;
+            } else if (i > lastRemovedIndex) {
+                itemsToMove.append(i);
                 continue;
             }
 
@@ -1115,17 +1116,18 @@ void KItemListView::slotItemsRemoved(const KItemRangeList& itemRanges)
         }
 
         // Update the indexes of all KItemListWidget instances that are located
-        // after the deleted items
-        for (int i = lastRemovedIndex + 1; i <= lastIndex; ++i) {
+        // after the deleted items. It is important to update them in ascending
+        // order to prevent overlaps when setting the new index.
+        std::sort(itemsToMove.begin(), itemsToMove.end());
+        foreach (int i, itemsToMove) {
             KItemListWidget* widget = m_visibleItems.value(i);
-            if (widget) {
-                const int newIndex = i - count;
-                if (hasMultipleRanges) {
-                    setWidgetIndex(widget, newIndex);
-                } else {
-                    // Try to animate the moving of the item
-                    moveWidgetToIndex(widget, newIndex);
-                }
+            Q_ASSERT(widget);
+            const int newIndex = i - count;
+            if (hasMultipleRanges) {
+                setWidgetIndex(widget, newIndex);
+            } else {
+                // Try to animate the moving of the item
+                moveWidgetToIndex(widget, newIndex);
             }
         }