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, 12 insertions, 0 deletions

diff --git a/src/tests/CMakeLists.txt b/src/tests/CMakeLists.txt
index dd761fc90..9b152ed07 100644
--- a/src/tests/CMakeLists.txt
+++ b/src/tests/CMakeLists.txt
@@ -3,11 +3,21 @@ include_directories( ${CMAKE_CURRENT_SOURCE_DIR}/.. ${CMAKE_CURRENT_BUILD_DIR}/.
 
 # needed on windows to correctly use the files from dolphinprivate
 add_definitions(-DLIBDOLPHINPRIVATE_EXPORT=)
+
+# KItemSetTest
+set(kitemsettest_SRCS
+    kitemsettest.cpp
+    ../kitemviews/kitemset.cpp
+)
+kde4_add_unit_test(kitemsettest TEST ${kitemsettest_SRCS})
+target_link_libraries(kitemsettest dolphinprivate ${KDE4_KIO_LIBS} ${QT_QTTEST_LIBRARY})
+
 # KItemListSelectionManagerTest
 set(kitemlistselectionmanagertest_SRCS
     kitemlistselectionmanagertest.cpp
     ../kitemviews/kitemlistselectionmanager.cpp
     ../kitemviews/kitemmodelbase.cpp
+    ../kitemviews/kitemset.cpp
 )
 kde4_add_unit_test(kitemlistselectionmanagertest TEST ${kitemlistselectionmanagertest_SRCS})
 target_link_libraries(kitemlistselectionmanagertest dolphinprivate ${KDE4_KIO_LIBS} ${QT_QTTEST_LIBRARY})
@@ -24,6 +34,7 @@ set(kitemlistcontrollertest_SRCS
     ../kitemviews/kitemlistcontainer.cpp
     ../kitemviews/kitemlistwidget.cpp
     ../kitemviews/kitemlistviewaccessible.cpp
+    ../kitemviews/kitemset.cpp
     ../kitemviews/kstandarditemlistview.cpp
     ../kitemviews/kstandarditemlistwidget.cpp
 )
@@ -41,6 +52,7 @@ set(kfileitemlistviewtest_SRCS
     ../kitemviews/kitemlistviewaccessible.cpp
     ../kitemviews/kitemlistcontainer.cpp
     ../kitemviews/kitemlistwidget.cpp
+    ../kitemviews/kitemset.cpp
     ../kitemviews/kstandarditemlistview.cpp
     ../kitemviews/kstandarditemlistwidget.cpp
 )