Store the selected items in a more efficient way

Since Dolphin 2.0, we have stored the selected items in a QSet<int>,
which is neither space-efficient nor particularly fast when inserting
many items which are in a consecutive range.

This commit replaces the QSet<int> by a new class "KItemSet", which
stores the items in a sorted list of ranges. For each range, we only
store the first index and the length of the range, so we need a lot
less memory for most common selection patterns, and we also save quite
a few CPU cycles in many situations, because adding an item to the
KItemSet will in many cases not need a memory allocation at all, and
it's particularly easy when inserting sorted items into the KItemSet in
a row.

KItemSet contains a minimal subset of QSet's API which makes it
suitable as a drop-in replacement for our needs. It also has iterators,
such that the items can be iterated through easily, also with foreach.
One advantage of KItemSet compared to QSet<int> is that the items are
always iterated through in ascending order.

REVIEW: 113488

1 files changed, 5 insertions, 4 deletions

diff --git a/src/kitemviews/kitemlistcontroller.h b/src/kitemviews/kitemlistcontroller.h
index bb72856e0..e9b70cdda 100644
--- a/src/kitemviews/kitemlistcontroller.h
+++ b/src/kitemviews/kitemlistcontroller.h
@@ -25,10 +25,11 @@
 
 #include <libdolphin_export.h>
 
+#include "kitemset.h"
+
 #include <QObject>
 #include <QPixmap>
 #include <QPointF>
-#include <QSet>
 
 class KItemModelBase;
 class KItemListKeyboardSearchManager;
@@ -129,7 +130,7 @@ public:
 
     /**
      * If set to true, the signals itemActivated() and itemsActivated() are emitted
-     * after a single-click of the left mouse button. If set to false (the default), 
+     * after a single-click of the left mouse button. If set to false (the default),
      * the setting from KGlobalSettings::singleClick() is used.
      */
     void setSingleClickActivationEnforced(bool singleClick);
@@ -165,7 +166,7 @@ signals:
      * Is emitted if more than one item has been activated by pressing Return/Enter
      * when having a selection.
      */
-    void itemsActivated(const QSet<int>& indexes);
+    void itemsActivated(const KItemSet& indexes);
 
     void itemMiddleClicked(int index);
 
@@ -326,7 +327,7 @@ private:
      * the current selection it is remembered in m_oldSelection before the
      * rubberband gets activated.
      */
-    QSet<int> m_oldSelection;
+    KItemSet m_oldSelection;
 
     /**
      * Assuming a view is given with a vertical scroll-orientation, grouped items and