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

4 files changed, 775 insertions, 151 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
 )
diff --git a/src/tests/kitemlistcontrollertest.cpp b/src/tests/kitemlistcontrollertest.cpp
index 60e93e539..7dd37bf0a 100644
--- a/src/tests/kitemlistcontrollertest.cpp
+++ b/src/tests/kitemlistcontrollertest.cpp
@@ -41,7 +41,7 @@ namespace {
 Q_DECLARE_METATYPE(KFileItemListView::ItemLayout);
 Q_DECLARE_METATYPE(Qt::Orientation);
 Q_DECLARE_METATYPE(KItemListController::SelectionBehavior);
-Q_DECLARE_METATYPE(QSet<int>);
+Q_DECLARE_METATYPE(KItemSet);
 
 class KItemListControllerTest : public QObject
 {
@@ -81,7 +81,7 @@ private:
  */
 void KItemListControllerTest::initTestCase()
 {
-    qRegisterMetaType<QSet<int> >("QSet<int>");
+    qRegisterMetaType<KItemSet>("KItemSet");
 
     m_testDir = new TestDir();
     m_model = new KFileItemModel();
@@ -159,14 +159,14 @@ struct KeyPress {
  */
 struct ViewState {
 
-    ViewState(int current, const QSet<int> selection, bool activated = false) :
+    ViewState(int current, const KItemSet selection, bool activated = false) :
         m_current(current),
         m_selection(selection),
         m_activated(activated)
     {}
 
     int m_current;
-    QSet<int> m_selection;
+    KItemSet m_selection;
     bool m_activated;
 };
 
@@ -262,34 +262,34 @@ void KItemListControllerTest::testKeyboardNavigation_data()
                     // First, key presses which should have the same effect
                     // for any layout and any number of columns.
                     testList
-                        << qMakePair(KeyPress(nextItemKey), ViewState(1, QSet<int>() << 1))
-                        << qMakePair(KeyPress(Qt::Key_Return), ViewState(1, QSet<int>() << 1, true))
-                        << qMakePair(KeyPress(Qt::Key_Enter), ViewState(1, QSet<int>() << 1, true))
-                        << qMakePair(KeyPress(nextItemKey), ViewState(2, QSet<int>() << 2))
-                        << qMakePair(KeyPress(nextItemKey, Qt::ShiftModifier), ViewState(3, QSet<int>() << 2 << 3))
-                        << qMakePair(KeyPress(Qt::Key_Return), ViewState(3, QSet<int>() << 2 << 3, true))
-                        << qMakePair(KeyPress(previousItemKey, Qt::ShiftModifier), ViewState(2, QSet<int>() << 2))
-                        << qMakePair(KeyPress(nextItemKey, Qt::ShiftModifier), ViewState(3, QSet<int>() << 2 << 3))
-                        << qMakePair(KeyPress(nextItemKey, Qt::ControlModifier), ViewState(4, QSet<int>() << 2 << 3))
-                        << qMakePair(KeyPress(Qt::Key_Return), ViewState(4, QSet<int>() << 2 << 3, true))
-                        << qMakePair(KeyPress(previousItemKey), ViewState(3, QSet<int>() << 3))
-                        << qMakePair(KeyPress(Qt::Key_Home, Qt::ShiftModifier), ViewState(0, QSet<int>() << 0 << 1 << 2 << 3))
-                        << qMakePair(KeyPress(nextItemKey, Qt::ControlModifier), ViewState(1, QSet<int>() << 0 << 1 << 2 << 3))
-                        << qMakePair(KeyPress(Qt::Key_Space, Qt::ControlModifier), ViewState(1, QSet<int>() << 0 << 2 << 3))
-                        << qMakePair(KeyPress(Qt::Key_Space, Qt::ControlModifier), ViewState(1, QSet<int>() << 0 << 1 << 2 << 3))
-                        << qMakePair(KeyPress(Qt::Key_End), ViewState(19, QSet<int>() << 19))
-                        << qMakePair(KeyPress(previousItemKey, Qt::ShiftModifier), ViewState(18, QSet<int>() << 18 << 19))
-                        << qMakePair(KeyPress(Qt::Key_Home), ViewState(0, QSet<int>() << 0))
-                        << qMakePair(KeyPress(Qt::Key_Space, Qt::ControlModifier), ViewState(0, QSet<int>()))
-                        << qMakePair(KeyPress(Qt::Key_Enter), ViewState(0, QSet<int>(), true))
-                        << qMakePair(KeyPress(Qt::Key_Space, Qt::ControlModifier), ViewState(0, QSet<int>() << 0))
-                        << qMakePair(KeyPress(Qt::Key_Space, Qt::ControlModifier), ViewState(0, QSet<int>()))
-                        << qMakePair(KeyPress(Qt::Key_Space), ViewState(0, QSet<int>() << 0))
-                        << qMakePair(KeyPress(Qt::Key_E), ViewState(13, QSet<int>() << 13))
-                        << qMakePair(KeyPress(Qt::Key_Space), ViewState(14, QSet<int>() << 14))
-                        << qMakePair(KeyPress(Qt::Key_3), ViewState(15, QSet<int>() << 15))
-                        << qMakePair(KeyPress(Qt::Key_Home), ViewState(0, QSet<int>() << 0))
-                        << qMakePair(KeyPress(Qt::Key_Escape), ViewState(0, QSet<int>()));
+                        << qMakePair(KeyPress(nextItemKey), ViewState(1, KItemSet() << 1))
+                        << qMakePair(KeyPress(Qt::Key_Return), ViewState(1, KItemSet() << 1, true))
+                        << qMakePair(KeyPress(Qt::Key_Enter), ViewState(1, KItemSet() << 1, true))
+                        << qMakePair(KeyPress(nextItemKey), ViewState(2, KItemSet() << 2))
+                        << qMakePair(KeyPress(nextItemKey, Qt::ShiftModifier), ViewState(3, KItemSet() << 2 << 3))
+                        << qMakePair(KeyPress(Qt::Key_Return), ViewState(3, KItemSet() << 2 << 3, true))
+                        << qMakePair(KeyPress(previousItemKey, Qt::ShiftModifier), ViewState(2, KItemSet() << 2))
+                        << qMakePair(KeyPress(nextItemKey, Qt::ShiftModifier), ViewState(3, KItemSet() << 2 << 3))
+                        << qMakePair(KeyPress(nextItemKey, Qt::ControlModifier), ViewState(4, KItemSet() << 2 << 3))
+                        << qMakePair(KeyPress(Qt::Key_Return), ViewState(4, KItemSet() << 2 << 3, true))
+                        << qMakePair(KeyPress(previousItemKey), ViewState(3, KItemSet() << 3))
+                        << qMakePair(KeyPress(Qt::Key_Home, Qt::ShiftModifier), ViewState(0, KItemSet() << 0 << 1 << 2 << 3))
+                        << qMakePair(KeyPress(nextItemKey, Qt::ControlModifier), ViewState(1, KItemSet() << 0 << 1 << 2 << 3))
+                        << qMakePair(KeyPress(Qt::Key_Space, Qt::ControlModifier), ViewState(1, KItemSet() << 0 << 2 << 3))
+                        << qMakePair(KeyPress(Qt::Key_Space, Qt::ControlModifier), ViewState(1, KItemSet() << 0 << 1 << 2 << 3))
+                        << qMakePair(KeyPress(Qt::Key_End), ViewState(19, KItemSet() << 19))
+                        << qMakePair(KeyPress(previousItemKey, Qt::ShiftModifier), ViewState(18, KItemSet() << 18 << 19))
+                        << qMakePair(KeyPress(Qt::Key_Home), ViewState(0, KItemSet() << 0))
+                        << qMakePair(KeyPress(Qt::Key_Space, Qt::ControlModifier), ViewState(0, KItemSet()))
+                        << qMakePair(KeyPress(Qt::Key_Enter), ViewState(0, KItemSet(), true))
+                        << qMakePair(KeyPress(Qt::Key_Space, Qt::ControlModifier), ViewState(0, KItemSet() << 0))
+                        << qMakePair(KeyPress(Qt::Key_Space, Qt::ControlModifier), ViewState(0, KItemSet()))
+                        << qMakePair(KeyPress(Qt::Key_Space), ViewState(0, KItemSet() << 0))
+                        << qMakePair(KeyPress(Qt::Key_E), ViewState(13, KItemSet() << 13))
+                        << qMakePair(KeyPress(Qt::Key_Space), ViewState(14, KItemSet() << 14))
+                        << qMakePair(KeyPress(Qt::Key_3), ViewState(15, KItemSet() << 15))
+                        << qMakePair(KeyPress(Qt::Key_Home), ViewState(0, KItemSet() << 0))
+                        << qMakePair(KeyPress(Qt::Key_Escape), ViewState(0, KItemSet()));
 
                     // Next, we test combinations of key presses which only work for a
                     // particular number of columns and either enabled or disabled grouping.
@@ -297,12 +297,12 @@ void KItemListControllerTest::testKeyboardNavigation_data()
                     // One column.
                     if (columnCount == 1) {
                         testList
-                            << qMakePair(KeyPress(nextRowKey), ViewState(1, QSet<int>() << 1))
-                            << qMakePair(KeyPress(nextRowKey, Qt::ShiftModifier), ViewState(2, QSet<int>() << 1 << 2))
-                            << qMakePair(KeyPress(nextRowKey, Qt::ControlModifier), ViewState(3, QSet<int>() << 1 << 2))
-                            << qMakePair(KeyPress(previousRowKey), ViewState(2, QSet<int>() << 2))
-                            << qMakePair(KeyPress(previousItemKey), ViewState(1, QSet<int>() << 1))
-                            << qMakePair(KeyPress(Qt::Key_Home), ViewState(0, QSet<int>() << 0));
+                            << qMakePair(KeyPress(nextRowKey), ViewState(1, KItemSet() << 1))
+                            << qMakePair(KeyPress(nextRowKey, Qt::ShiftModifier), ViewState(2, KItemSet() << 1 << 2))
+                            << qMakePair(KeyPress(nextRowKey, Qt::ControlModifier), ViewState(3, KItemSet() << 1 << 2))
+                            << qMakePair(KeyPress(previousRowKey), ViewState(2, KItemSet() << 2))
+                            << qMakePair(KeyPress(previousItemKey), ViewState(1, KItemSet() << 1))
+                            << qMakePair(KeyPress(Qt::Key_Home), ViewState(0, KItemSet() << 0));
                     }
 
                     // Multiple columns: we test both 3 and 5 columns with grouping
@@ -321,26 +321,26 @@ void KItemListControllerTest::testKeyboardNavigation_data()
                         // e3 e4 e5 | 15 16 17
                         // e6 e7    | 18 19
                         testList
-                            << qMakePair(KeyPress(nextRowKey), ViewState(3, QSet<int>() << 3))
-                            << qMakePair(KeyPress(nextItemKey, Qt::ControlModifier), ViewState(4, QSet<int>() << 3))
-                            << qMakePair(KeyPress(nextRowKey), ViewState(7, QSet<int>() << 7))
-                            << qMakePair(KeyPress(nextItemKey, Qt::ShiftModifier), ViewState(8, QSet<int>() << 7 << 8))
-                            << qMakePair(KeyPress(nextItemKey, Qt::ShiftModifier), ViewState(9, QSet<int>() << 7 << 8 << 9))
-                            << qMakePair(KeyPress(previousItemKey, Qt::ShiftModifier), ViewState(8, QSet<int>() << 7 << 8))
-                            << qMakePair(KeyPress(previousItemKey, Qt::ShiftModifier), ViewState(7, QSet<int>() << 7))
-                            << qMakePair(KeyPress(previousItemKey, Qt::ShiftModifier), ViewState(6, QSet<int>() << 6 << 7))
-                            << qMakePair(KeyPress(previousItemKey, Qt::ShiftModifier), ViewState(5, QSet<int>() << 5 << 6 << 7))
-                            << qMakePair(KeyPress(nextItemKey, Qt::ShiftModifier), ViewState(6, QSet<int>() << 6 << 7))
-                            << qMakePair(KeyPress(nextItemKey, Qt::ShiftModifier), ViewState(7, QSet<int>() << 7))
-                            << qMakePair(KeyPress(nextRowKey), ViewState(10, QSet<int>() << 10))
-                            << qMakePair(KeyPress(nextItemKey), ViewState(11, QSet<int>() << 11))
-                            << qMakePair(KeyPress(nextRowKey), ViewState(14, QSet<int>() << 14))
-                            << qMakePair(KeyPress(nextRowKey), ViewState(17, QSet<int>() << 17))
-                            << qMakePair(KeyPress(nextRowKey), ViewState(19, QSet<int>() << 19))
-                            << qMakePair(KeyPress(previousRowKey), ViewState(17, QSet<int>() << 17))
-                            << qMakePair(KeyPress(Qt::Key_End), ViewState(19, QSet<int>() << 19))
-                            << qMakePair(KeyPress(previousRowKey), ViewState(16, QSet<int>() << 16))
-                            << qMakePair(KeyPress(Qt::Key_Home), ViewState(0, QSet<int>() << 0));
+                            << qMakePair(KeyPress(nextRowKey), ViewState(3, KItemSet() << 3))
+                            << qMakePair(KeyPress(nextItemKey, Qt::ControlModifier), ViewState(4, KItemSet() << 3))
+                            << qMakePair(KeyPress(nextRowKey), ViewState(7, KItemSet() << 7))
+                            << qMakePair(KeyPress(nextItemKey, Qt::ShiftModifier), ViewState(8, KItemSet() << 7 << 8))
+                            << qMakePair(KeyPress(nextItemKey, Qt::ShiftModifier), ViewState(9, KItemSet() << 7 << 8 << 9))
+                            << qMakePair(KeyPress(previousItemKey, Qt::ShiftModifier), ViewState(8, KItemSet() << 7 << 8))
+                            << qMakePair(KeyPress(previousItemKey, Qt::ShiftModifier), ViewState(7, KItemSet() << 7))
+                            << qMakePair(KeyPress(previousItemKey, Qt::ShiftModifier), ViewState(6, KItemSet() << 6 << 7))
+                            << qMakePair(KeyPress(previousItemKey, Qt::ShiftModifier), ViewState(5, KItemSet() << 5 << 6 << 7))
+                            << qMakePair(KeyPress(nextItemKey, Qt::ShiftModifier), ViewState(6, KItemSet() << 6 << 7))
+                            << qMakePair(KeyPress(nextItemKey, Qt::ShiftModifier), ViewState(7, KItemSet() << 7))
+                            << qMakePair(KeyPress(nextRowKey), ViewState(10, KItemSet() << 10))
+                            << qMakePair(KeyPress(nextItemKey), ViewState(11, KItemSet() << 11))
+                            << qMakePair(KeyPress(nextRowKey), ViewState(14, KItemSet() << 14))
+                            << qMakePair(KeyPress(nextRowKey), ViewState(17, KItemSet() << 17))
+                            << qMakePair(KeyPress(nextRowKey), ViewState(19, KItemSet() << 19))
+                            << qMakePair(KeyPress(previousRowKey), ViewState(17, KItemSet() << 17))
+                            << qMakePair(KeyPress(Qt::Key_End), ViewState(19, KItemSet() << 19))
+                            << qMakePair(KeyPress(previousRowKey), ViewState(16, KItemSet() << 16))
+                            << qMakePair(KeyPress(Qt::Key_Home), ViewState(0, KItemSet() << 0));
                     }
 
                     if (columnCount == 5 && !groupingEnabled) {
@@ -351,17 +351,17 @@ void KItemListControllerTest::testKeyboardNavigation_data()
                         // d2 d3 d4 e1 e2 | 10 11 12 13 14
                         // e3 e4 e5 e6 e7 | 15 16 17 18 19
                         testList
-                            << qMakePair(KeyPress(nextRowKey), ViewState(5, QSet<int>() << 5))
-                            << qMakePair(KeyPress(nextItemKey, Qt::ControlModifier), ViewState(6, QSet<int>() << 5))
-                            << qMakePair(KeyPress(nextRowKey), ViewState(11, QSet<int>() << 11))
-                            << qMakePair(KeyPress(nextItemKey), ViewState(12, QSet<int>() << 12))
-                            << qMakePair(KeyPress(nextRowKey, Qt::ShiftModifier), ViewState(17, QSet<int>() << 12 << 13 << 14 << 15 << 16 << 17))
-                            << qMakePair(KeyPress(previousRowKey, Qt::ShiftModifier), ViewState(12, QSet<int>() << 12))
-                            << qMakePair(KeyPress(previousRowKey, Qt::ShiftModifier), ViewState(7, QSet<int>() << 7 << 8 << 9 << 10 << 11 << 12))
-                            << qMakePair(KeyPress(nextRowKey, Qt::ShiftModifier), ViewState(12, QSet<int>() << 12))
-                            << qMakePair(KeyPress(Qt::Key_End, Qt::ControlModifier), ViewState(19, QSet<int>() << 12))
-                            << qMakePair(KeyPress(previousRowKey), ViewState(14, QSet<int>() << 14))
-                            << qMakePair(KeyPress(Qt::Key_Home), ViewState(0, QSet<int>() << 0));
+                            << qMakePair(KeyPress(nextRowKey), ViewState(5, KItemSet() << 5))
+                            << qMakePair(KeyPress(nextItemKey, Qt::ControlModifier), ViewState(6, KItemSet() << 5))
+                            << qMakePair(KeyPress(nextRowKey), ViewState(11, KItemSet() << 11))
+                            << qMakePair(KeyPress(nextItemKey), ViewState(12, KItemSet() << 12))
+                            << qMakePair(KeyPress(nextRowKey, Qt::ShiftModifier), ViewState(17, KItemSet() << 12 << 13 << 14 << 15 << 16 << 17))
+                            << qMakePair(KeyPress(previousRowKey, Qt::ShiftModifier), ViewState(12, KItemSet() << 12))
+                            << qMakePair(KeyPress(previousRowKey, Qt::ShiftModifier), ViewState(7, KItemSet() << 7 << 8 << 9 << 10 << 11 << 12))
+                            << qMakePair(KeyPress(nextRowKey, Qt::ShiftModifier), ViewState(12, KItemSet() << 12))
+                            << qMakePair(KeyPress(Qt::Key_End, Qt::ControlModifier), ViewState(19, KItemSet() << 12))
+                            << qMakePair(KeyPress(previousRowKey), ViewState(14, KItemSet() << 14))
+                            << qMakePair(KeyPress(Qt::Key_Home), ViewState(0, KItemSet() << 0));
                     }
 
                     if (columnCount == 3 && groupingEnabled) {
@@ -377,19 +377,19 @@ void KItemListControllerTest::testKeyboardNavigation_data()
                         // e4 e5 e6 | 16 17 18
                         // e7       | 19
                         testList
-                            << qMakePair(KeyPress(nextItemKey), ViewState(1, QSet<int>() << 1))
-                            << qMakePair(KeyPress(nextItemKey), ViewState(2, QSet<int>() << 2))
-                            << qMakePair(KeyPress(nextRowKey, Qt::ShiftModifier), ViewState(3, QSet<int>() << 2 << 3))
-                            << qMakePair(KeyPress(nextRowKey, Qt::ShiftModifier), ViewState(6, QSet<int>() << 2 << 3 << 4 << 5 << 6))
-                            << qMakePair(KeyPress(nextRowKey), ViewState(8, QSet<int>() << 8))
-                            << qMakePair(KeyPress(nextRowKey), ViewState(11, QSet<int>() << 11))
-                            << qMakePair(KeyPress(nextItemKey, Qt::ControlModifier), ViewState(12, QSet<int>() << 11))
-                            << qMakePair(KeyPress(nextRowKey), ViewState(13, QSet<int>() << 13))
-                            << qMakePair(KeyPress(nextRowKey), ViewState(16, QSet<int>() << 16))
-                            << qMakePair(KeyPress(nextItemKey), ViewState(17, QSet<int>() << 17))
-                            << qMakePair(KeyPress(nextRowKey), ViewState(19, QSet<int>() << 19))
-                            << qMakePair(KeyPress(previousRowKey), ViewState(17, QSet<int>() << 17))
-                            << qMakePair(KeyPress(Qt::Key_Home), ViewState(0, QSet<int>() << 0));
+                            << qMakePair(KeyPress(nextItemKey), ViewState(1, KItemSet() << 1))
+                            << qMakePair(KeyPress(nextItemKey), ViewState(2, KItemSet() << 2))
+                            << qMakePair(KeyPress(nextRowKey, Qt::ShiftModifier), ViewState(3, KItemSet() << 2 << 3))
+                            << qMakePair(KeyPress(nextRowKey, Qt::ShiftModifier), ViewState(6, KItemSet() << 2 << 3 << 4 << 5 << 6))
+                            << qMakePair(KeyPress(nextRowKey), ViewState(8, KItemSet() << 8))
+                            << qMakePair(KeyPress(nextRowKey), ViewState(11, KItemSet() << 11))
+                            << qMakePair(KeyPress(nextItemKey, Qt::ControlModifier), ViewState(12, KItemSet() << 11))
+                            << qMakePair(KeyPress(nextRowKey), ViewState(13, KItemSet() << 13))
+                            << qMakePair(KeyPress(nextRowKey), ViewState(16, KItemSet() << 16))
+                            << qMakePair(KeyPress(nextItemKey), ViewState(17, KItemSet() << 17))
+                            << qMakePair(KeyPress(nextRowKey), ViewState(19, KItemSet() << 19))
+                            << qMakePair(KeyPress(previousRowKey), ViewState(17, KItemSet() << 17))
+                            << qMakePair(KeyPress(Qt::Key_Home), ViewState(0, KItemSet() << 0));
                     }
 
                     if (columnCount == 5 && groupingEnabled) {
@@ -402,19 +402,19 @@ void KItemListControllerTest::testKeyboardNavigation_data()
                         // e1 e2 e3 e4 e5 | 13 14 15 16 17
                         // e6 e7          | 18 19
                         testList
-                            << qMakePair(KeyPress(nextItemKey), ViewState(1, QSet<int>() << 1))
-                            << qMakePair(KeyPress(nextRowKey, Qt::ShiftModifier), ViewState(3, QSet<int>() << 1 << 2 << 3))
-                            << qMakePair(KeyPress(nextRowKey, Qt::ShiftModifier), ViewState(5, QSet<int>() << 1 << 2 << 3 << 4 << 5))
-                            << qMakePair(KeyPress(nextItemKey), ViewState(6, QSet<int>() << 6))
-                            << qMakePair(KeyPress(nextItemKey, Qt::ControlModifier), ViewState(7, QSet<int>() << 6))
-                            << qMakePair(KeyPress(nextItemKey, Qt::ControlModifier), ViewState(8, QSet<int>() << 6))
-                            << qMakePair(KeyPress(nextRowKey), ViewState(12, QSet<int>() << 12))
-                            << qMakePair(KeyPress(nextRowKey), ViewState(17, QSet<int>() << 17))
-                            << qMakePair(KeyPress(nextRowKey), ViewState(19, QSet<int>() << 19))
-                            << qMakePair(KeyPress(previousRowKey), ViewState(17, QSet<int>() << 17))
-                            << qMakePair(KeyPress(Qt::Key_End, Qt::ShiftModifier), ViewState(19, QSet<int>() << 17 << 18 << 19))
-                            << qMakePair(KeyPress(previousRowKey, Qt::ShiftModifier), ViewState(14, QSet<int>() << 14 << 15 << 16 << 17))
-                            << qMakePair(KeyPress(Qt::Key_Home), ViewState(0, QSet<int>() << 0));
+                            << qMakePair(KeyPress(nextItemKey), ViewState(1, KItemSet() << 1))
+                            << qMakePair(KeyPress(nextRowKey, Qt::ShiftModifier), ViewState(3, KItemSet() << 1 << 2 << 3))
+                            << qMakePair(KeyPress(nextRowKey, Qt::ShiftModifier), ViewState(5, KItemSet() << 1 << 2 << 3 << 4 << 5))
+                            << qMakePair(KeyPress(nextItemKey), ViewState(6, KItemSet() << 6))
+                            << qMakePair(KeyPress(nextItemKey, Qt::ControlModifier), ViewState(7, KItemSet() << 6))
+                            << qMakePair(KeyPress(nextItemKey, Qt::ControlModifier), ViewState(8, KItemSet() << 6))
+                            << qMakePair(KeyPress(nextRowKey), ViewState(12, KItemSet() << 12))
+                            << qMakePair(KeyPress(nextRowKey), ViewState(17, KItemSet() << 17))
+                            << qMakePair(KeyPress(nextRowKey), ViewState(19, KItemSet() << 19))
+                            << qMakePair(KeyPress(previousRowKey), ViewState(17, KItemSet() << 17))
+                            << qMakePair(KeyPress(Qt::Key_End, Qt::ShiftModifier), ViewState(19, KItemSet() << 17 << 18 << 19))
+                            << qMakePair(KeyPress(previousRowKey, Qt::ShiftModifier), ViewState(14, KItemSet() << 14 << 15 << 16 << 17))
+                            << qMakePair(KeyPress(Qt::Key_Home), ViewState(0, KItemSet() << 0));
                     }
 
                     const QString testName =
@@ -470,14 +470,14 @@ void KItemListControllerTest::testKeyboardNavigation()
     QCOMPARE(m_view->m_layouter->m_columnCount, columnCount);
 
     QSignalSpy spySingleItemActivated(m_controller, SIGNAL(itemActivated(int)));
-    QSignalSpy spyMultipleItemsActivated(m_controller, SIGNAL(itemsActivated(QSet<int>)));
+    QSignalSpy spyMultipleItemsActivated(m_controller, SIGNAL(itemsActivated(KItemSet)));
 
     while (!testList.isEmpty()) {
         const QPair<KeyPress, ViewState> test = testList.takeFirst();
         const Qt::Key key = test.first.m_key;
         const Qt::KeyboardModifiers modifier = test.first.m_modifier;
         const int current = test.second.m_current;
-        const QSet<int> selection = test.second.m_selection;
+        const KItemSet selection = test.second.m_selection;
         const bool activated = test.second.m_activated;
 
         QTest::keyClick(m_container, key, modifier);
@@ -485,7 +485,7 @@ void KItemListControllerTest::testKeyboardNavigation()
         QCOMPARE(m_selectionManager->currentItem(), current);
         switch (selectionBehavior) {
         case KItemListController::NoSelection: QVERIFY(m_selectionManager->selectedItems().isEmpty()); break;
-        case KItemListController::SingleSelection: QCOMPARE(m_selectionManager->selectedItems(), QSet<int>() << current); break;
+        case KItemListController::SingleSelection: QCOMPARE(m_selectionManager->selectedItems(), KItemSet() << current); break;
         case KItemListController::MultiSelection: QCOMPARE(m_selectionManager->selectedItems(), selection); break;
         }
 
@@ -496,12 +496,12 @@ void KItemListControllerTest::testKeyboardNavigation()
                     // The selected items should be activated.
                     if (selection.count() == 1) {
                         QVERIFY(!spySingleItemActivated.isEmpty());
-                        QCOMPARE(qvariant_cast<int>(spySingleItemActivated.takeFirst().at(0)), selection.toList().at(0));
+                        QCOMPARE(qvariant_cast<int>(spySingleItemActivated.takeFirst().at(0)), selection.first());
                         QVERIFY(spyMultipleItemsActivated.isEmpty());
                     } else {
                         QVERIFY(spySingleItemActivated.isEmpty());
                         QVERIFY(!spyMultipleItemsActivated.isEmpty());
-                        QCOMPARE(qvariant_cast<QSet<int> >(spyMultipleItemsActivated.takeFirst().at(0)), selection);
+                        QCOMPARE(qvariant_cast<KItemSet>(spyMultipleItemsActivated.takeFirst().at(0)), selection);
                     }
                     break;
                 }
@@ -641,7 +641,7 @@ void KItemListControllerTest::testMouseClickActivation()
     group.writeEntry("SingleClick", restoreKGlobalSettingsSingleClick, KConfig::Persistent|KConfig::Global);
     config.sync();
     KGlobalSettings::self()->emitChange(KGlobalSettings::SettingsChanged, KGlobalSettings::SETTINGS_MOUSE);
-    
+
     iterations = 0;
     while (KGlobalSettings::singleClick() != restoreKGlobalSettingsSingleClick && iterations < maxIterations) {
         QTest::qWait(50);
diff --git a/src/tests/kitemlistselectionmanagertest.cpp b/src/tests/kitemlistselectionmanagertest.cpp
index 302985a5f..af2610d8c 100644
--- a/src/tests/kitemlistselectionmanagertest.cpp
+++ b/src/tests/kitemlistselectionmanagertest.cpp
@@ -80,7 +80,7 @@ private slots:
     void testDeleteCurrentItem();
 
 private:
-    void verifySelectionChange(QSignalSpy& spy, const QSet<int>& currentSelection, const QSet<int>& previousSelection) const;
+    void verifySelectionChange(QSignalSpy& spy, const KItemSet& currentSelection, const KItemSet& previousSelection) const;
 
     KItemListSelectionManager* m_selectionManager;
     DummyModel* m_model;
@@ -127,7 +127,7 @@ void KItemListSelectionManagerTest::testCurrentItemAnchorItem()
     QCOMPARE(m_selectionManager->m_anchorItem, 5);
 
     // Items between current and anchor should be selected now
-    QCOMPARE(m_selectionManager->selectedItems(), QSet<int>() << 4 << 5);
+    QCOMPARE(m_selectionManager->selectedItems(), KItemSet() << 4 << 5);
     QVERIFY(m_selectionManager->hasSelection());
 
     // Change current item again and check the selection
@@ -138,7 +138,7 @@ void KItemListSelectionManagerTest::testCurrentItemAnchorItem()
     QCOMPARE(qvariant_cast<int>(spyCurrent.at(0).at(1)), 4);
     spyCurrent.takeFirst();
 
-    QCOMPARE(m_selectionManager->selectedItems(), QSet<int>() << 2 << 3 << 4 << 5);
+    QCOMPARE(m_selectionManager->selectedItems(), KItemSet() << 2 << 3 << 4 << 5);
     QVERIFY(m_selectionManager->hasSelection());
 
     // Inserting items should update current item and anchor item.
@@ -155,7 +155,7 @@ void KItemListSelectionManagerTest::testCurrentItemAnchorItem()
 
     QCOMPARE(m_selectionManager->m_anchorItem, 8);
 
-    QCOMPARE(m_selectionManager->selectedItems(), QSet<int>() << 5 << 6 << 7 << 8);
+    QCOMPARE(m_selectionManager->selectedItems(), KItemSet() << 5 << 6 << 7 << 8);
     QVERIFY(m_selectionManager->hasSelection());
 
     // Removing items should update current item and anchor item.
@@ -172,12 +172,12 @@ void KItemListSelectionManagerTest::testCurrentItemAnchorItem()
 
     QCOMPARE(m_selectionManager->m_anchorItem, 5);
 
-    QCOMPARE(m_selectionManager->selectedItems(), QSet<int>() << 2 << 3 << 4 << 5);
+    QCOMPARE(m_selectionManager->selectedItems(), KItemSet() << 2 << 3 << 4 << 5);
     QVERIFY(m_selectionManager->hasSelection());
 
     // Verify that clearSelection() also clears the anchored selection.
     m_selectionManager->clearSelection();
-    QCOMPARE(m_selectionManager->selectedItems(), QSet<int>());
+    QCOMPARE(m_selectionManager->selectedItems(), KItemSet());
     QVERIFY(!m_selectionManager->hasSelection());
 
     m_selectionManager->endAnchoredSelection();
@@ -212,7 +212,7 @@ void KItemListSelectionManagerTest::testItemsInserted()
 {
     // Select items 10 to 12
     m_selectionManager->setSelected(10, 3);
-    QSet<int> selectedItems = m_selectionManager->selectedItems();
+    KItemSet selectedItems = m_selectionManager->selectedItems();
     QCOMPARE(selectedItems.count(), 3);
     QVERIFY(selectedItems.contains(10));
     QVERIFY(selectedItems.contains(11));
@@ -242,7 +242,7 @@ void KItemListSelectionManagerTest::testItemsRemoved()
 {
     // Select items 10 to 15
     m_selectionManager->setSelected(10, 6);
-    QSet<int> selectedItems = m_selectionManager->selectedItems();
+    KItemSet selectedItems = m_selectionManager->selectedItems();
     QCOMPARE(selectedItems.count(), 6);
     for (int i = 10; i <= 15; ++i) {
         QVERIFY(selectedItems.contains(i));
@@ -276,20 +276,20 @@ void KItemListSelectionManagerTest::testAnchoredSelection()
 
     m_selectionManager->setCurrentItem(6);
     QCOMPARE(m_selectionManager->currentItem(), 6);
-    QCOMPARE(m_selectionManager->selectedItems(), QSet<int>() << 5 << 6);
+    QCOMPARE(m_selectionManager->selectedItems(), KItemSet() << 5 << 6);
 
     m_selectionManager->setCurrentItem(4);
     QCOMPARE(m_selectionManager->currentItem(), 4);
-    QCOMPARE(m_selectionManager->selectedItems(), QSet<int>() << 4 << 5);
+    QCOMPARE(m_selectionManager->selectedItems(), KItemSet() << 4 << 5);
 
     m_selectionManager->setCurrentItem(7);
     QCOMPARE(m_selectionManager->currentItem(), 7);
-    QCOMPARE(m_selectionManager->selectedItems(), QSet<int>() << 5 << 6 << 7);
+    QCOMPARE(m_selectionManager->selectedItems(), KItemSet() << 5 << 6 << 7);
 
     // Ending the anchored selection should not change the selected items.
     m_selectionManager->endAnchoredSelection();
     QVERIFY(!m_selectionManager->isAnchoredSelectionActive());
-    QCOMPARE(m_selectionManager->selectedItems(), QSet<int>() << 5 << 6 << 7);
+    QCOMPARE(m_selectionManager->selectedItems(), KItemSet() << 5 << 6 << 7);
 
     // Start a new anchored selection that overlaps the previous one
     m_selectionManager->beginAnchoredSelection(9);
@@ -298,15 +298,15 @@ void KItemListSelectionManagerTest::testAnchoredSelection()
 
     m_selectionManager->setCurrentItem(6);
     QCOMPARE(m_selectionManager->currentItem(), 6);
-    QCOMPARE(m_selectionManager->selectedItems(), QSet<int>() << 5 << 6 << 7 << 8 << 9);
+    QCOMPARE(m_selectionManager->selectedItems(), KItemSet() << 5 << 6 << 7 << 8 << 9);
 
     m_selectionManager->setCurrentItem(10);
     QCOMPARE(m_selectionManager->currentItem(), 10);
-    QCOMPARE(m_selectionManager->selectedItems(), QSet<int>() << 5 << 6 << 7 << 9 << 10);
+    QCOMPARE(m_selectionManager->selectedItems(), KItemSet() << 5 << 6 << 7 << 9 << 10);
 
     m_selectionManager->endAnchoredSelection();
     QVERIFY(!m_selectionManager->isAnchoredSelectionActive());
-    QCOMPARE(m_selectionManager->selectedItems(), QSet<int>() << 5 << 6 << 7 << 9 << 10);
+    QCOMPARE(m_selectionManager->selectedItems(), KItemSet() << 5 << 6 << 7 << 9 << 10);
 }
 
 namespace {
@@ -320,7 +320,7 @@ namespace {
     };
 }
 
-Q_DECLARE_METATYPE(QSet<int>);
+Q_DECLARE_METATYPE(KItemSet);
 Q_DECLARE_METATYPE(ChangeType);
 Q_DECLARE_METATYPE(KItemRange);
 Q_DECLARE_METATYPE(KItemRangeList);
@@ -355,86 +355,86 @@ Q_DECLARE_METATYPE(QList<int>);
 
 void KItemListSelectionManagerTest::testChangeSelection_data()
 {
-    QTest::addColumn<QSet<int> >("initialSelection");
+    QTest::addColumn<KItemSet>("initialSelection");
     QTest::addColumn<int>("anchor");
     QTest::addColumn<int>("current");
-    QTest::addColumn<QSet<int> >("expectedSelection");
+    QTest::addColumn<KItemSet>("expectedSelection");
     QTest::addColumn<ChangeType>("changeType");
     QTest::addColumn<QList<QVariant> >("data");
-    QTest::addColumn<QSet<int> >("finalSelection");
+    QTest::addColumn<KItemSet>("finalSelection");
 
     QTest::newRow("No change")
-        << (QSet<int>() << 5 << 6)
+        << (KItemSet() << 5 << 6)
         << 2 << 3
-        << (QSet<int>() << 2 << 3 << 5 << 6)
+        << (KItemSet() << 2 << 3 << 5 << 6)
         << NoChange
         << QList<QVariant>()
-        << (QSet<int>() << 2 << 3 << 5 << 6);
+        << (KItemSet() << 2 << 3 << 5 << 6);
 
     QTest::newRow("Insert Items")
-        << (QSet<int>() << 5 << 6)
+        << (KItemSet() << 5 << 6)
         << 2 << 3
-        << (QSet<int>() << 2 << 3 << 5 << 6)
+        << (KItemSet() << 2 << 3 << 5 << 6)
         << InsertItems
         << (QList<QVariant>() << QVariant::fromValue(KItemRangeList() << KItemRange(1, 1) << KItemRange(5, 2) << KItemRange(10, 5)))
-        << (QSet<int>() << 3 << 4 << 8 << 9);
+        << (KItemSet() << 3 << 4 << 8 << 9);
 
     QTest::newRow("Remove Items")
-        << (QSet<int>() << 5 << 6)
+        << (KItemSet() << 5 << 6)
         << 2 << 3
-        << (QSet<int>() << 2 << 3 << 5 << 6)
+        << (KItemSet() << 2 << 3 << 5 << 6)
         << RemoveItems
         << (QList<QVariant>() << QVariant::fromValue(KItemRangeList() << KItemRange(1, 1) << KItemRange(3, 1) << KItemRange(10, 5)))
-        << (QSet<int>() << 1 << 2 << 3 << 4);
+        << (KItemSet() << 1 << 2 << 3 << 4);
 
     QTest::newRow("Empty Anchored Selection")
-        << QSet<int>()
+        << KItemSet()
         << 2 << 2
-        << QSet<int>()
+        << KItemSet()
         << EndAnchoredSelection
         << QList<QVariant>()
-        << QSet<int>();
+        << KItemSet();
 
     QTest::newRow("Toggle selection")
-        << (QSet<int>() << 1 << 3 << 4)
+        << (KItemSet() << 1 << 3 << 4)
         << 6 << 8
-        << (QSet<int>() << 1 << 3 << 4 << 6 << 7 << 8)
+        << (KItemSet() << 1 << 3 << 4 << 6 << 7 << 8)
         << SetSelected
         << (QList<QVariant>() << 0 << 10 << QVariant::fromValue(KItemListSelectionManager::Toggle))
-        << (QSet<int>() << 0 << 2 << 5 << 9);
+        << (KItemSet() << 0 << 2 << 5 << 9);
 
     // Swap items 2, 3 and 4, 5
     QTest::newRow("Move items")
-        << (QSet<int>() << 0 << 1 << 2 << 3)
+        << (KItemSet() << 0 << 1 << 2 << 3)
         << -1 << -1
-        << (QSet<int>() << 0 << 1 << 2 << 3)
+        << (KItemSet() << 0 << 1 << 2 << 3)
         << MoveItems
         << (QList<QVariant>() << QVariant::fromValue(KItemRange(2, 4))
                               << QVariant::fromValue(QList<int>() << 4 << 5 << 2 << 3))
-        << (QSet<int>() << 0 << 1 << 4 << 5);
+        << (KItemSet() << 0 << 1 << 4 << 5);
 
     // Revert sort order
     QTest::newRow("Revert sort order")
-        << (QSet<int>() << 0 << 1)
+        << (KItemSet() << 0 << 1)
         << 3 << 4
-        << (QSet<int>() << 0 << 1 << 3 << 4)
+        << (KItemSet() << 0 << 1 << 3 << 4)
         << MoveItems
         << (QList<QVariant>() << QVariant::fromValue(KItemRange(0, 10))
                               << QVariant::fromValue(QList<int>() << 9 << 8 << 7 << 6 << 5 << 4 << 3 << 2 << 1 << 0))
-        << (QSet<int>() << 5 << 6 << 8 << 9);
+        << (KItemSet() << 5 << 6 << 8 << 9);
 }
 
 void KItemListSelectionManagerTest::testChangeSelection()
 {
-    QFETCH(QSet<int>, initialSelection);
+    QFETCH(KItemSet, initialSelection);
     QFETCH(int, anchor);
     QFETCH(int, current);
-    QFETCH(QSet<int>, expectedSelection);
+    QFETCH(KItemSet, expectedSelection);
     QFETCH(ChangeType, changeType);
     QFETCH(QList<QVariant>, data);
-    QFETCH(QSet<int>, finalSelection);
+    QFETCH(KItemSet, finalSelection);
 
-    QSignalSpy spySelectionChanged(m_selectionManager, SIGNAL(selectionChanged(QSet<int>,QSet<int>)));
+    QSignalSpy spySelectionChanged(m_selectionManager, SIGNAL(selectionChanged(KItemSet,KItemSet)));
 
     // Initial selection should be empty
     QVERIFY(!m_selectionManager->hasSelection());
@@ -443,7 +443,7 @@ void KItemListSelectionManagerTest::testChangeSelection()
     // Perform the initial selectiion
     m_selectionManager->setSelectedItems(initialSelection);
 
-    verifySelectionChange(spySelectionChanged, initialSelection, QSet<int>());
+    verifySelectionChange(spySelectionChanged, initialSelection, KItemSet());
 
     // Perform an anchored selection.
     // Note that current and anchor index are equal first because this is the case in typical uses of the
@@ -486,7 +486,7 @@ void KItemListSelectionManagerTest::testChangeSelection()
     // Finally, clear the selection
     m_selectionManager->clearSelection();
 
-    verifySelectionChange(spySelectionChanged, QSet<int>(), finalSelection);
+    verifySelectionChange(spySelectionChanged, KItemSet(), finalSelection);
 }
 
 void KItemListSelectionManagerTest::testDeleteCurrentItem_data()
@@ -520,8 +520,8 @@ void KItemListSelectionManagerTest::testDeleteCurrentItem()
 }
 
 void KItemListSelectionManagerTest::verifySelectionChange(QSignalSpy& spy,
-                                                          const QSet<int>& currentSelection,
-                                                          const QSet<int>& previousSelection) const
+                                                          const KItemSet& currentSelection,
+                                                          const KItemSet& previousSelection) const
 {
     QCOMPARE(m_selectionManager->selectedItems(), currentSelection);
     QCOMPARE(m_selectionManager->hasSelection(), !currentSelection.isEmpty());
@@ -540,8 +540,8 @@ void KItemListSelectionManagerTest::verifySelectionChange(QSignalSpy& spy,
     else {
         QCOMPARE(spy.count(), 1);
         QList<QVariant> arguments = spy.takeFirst();
-        QCOMPARE(qvariant_cast<QSet<int> >(arguments.at(0)), currentSelection);
-        QCOMPARE(qvariant_cast<QSet<int> >(arguments.at(1)), previousSelection);
+        QCOMPARE(qvariant_cast<KItemSet>(arguments.at(0)), currentSelection);
+        QCOMPARE(qvariant_cast<KItemSet>(arguments.at(1)), previousSelection);
     }
 }
 
diff --git a/src/tests/kitemsettest.cpp b/src/tests/kitemsettest.cpp
new file mode 100644
index 000000000..2832596ba
--- /dev/null
+++ b/src/tests/kitemsettest.cpp
@@ -0,0 +1,612 @@
+/***************************************************************************
+ *   Copyright (C) 2013 by Frank Reininghaus <[email protected]>    *
+ *                                                                         *
+ *   This program is free software; you can redistribute it and/or modify  *
+ *   it under the terms of the GNU General Public License as published by  *
+ *   the Free Software Foundation; either version 2 of the License, or     *
+ *   (at your option) any later version.                                   *
+ *                                                                         *
+ *   This program is distributed in the hope that it will be useful,       *
+ *   but WITHOUT ANY WARRANTY; without even the implied warranty of        *
+ *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the         *
+ *   GNU General Public License for more details.                          *
+ *                                                                         *
+ *   You should have received a copy of the GNU General Public License     *
+ *   along with this program; if not, write to the                         *
+ *   Free Software Foundation, Inc.,                                       *
+ *   51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA            *
+ ***************************************************************************/
+
+#include <qtest_kde.h>
+
+#include "kitemviews/kitemset.h"
+
+#include <QVector>
+
+Q_DECLARE_METATYPE(KItemRangeList);
+
+/**
+ * Converts a KItemRangeList to a KItemSet.
+ */
+KItemSet KItemRangeList2KItemSet(const KItemRangeList& itemRanges)
+{
+    KItemSet result;
+    foreach (const KItemRange& range, itemRanges) {
+        for (int i = range.index; i < range.index + range.count; ++i) {
+            result.insert(i);
+        }
+    }
+    return result;
+}
+
+/**
+ * Converts a KItemRangeList to a QSet<int>.
+ */
+QSet<int> KItemRangeList2QSet(const KItemRangeList& itemRanges)
+{
+    QSet<int> result;
+    foreach (const KItemRange& range, itemRanges) {
+        for (int i = range.index; i < range.index + range.count; ++i) {
+            result.insert(i);
+        }
+    }
+    return result;
+}
+
+/**
+ * Converts a KItemRangeList to a QVector<int>.
+ */
+QVector<int> KItemRangeList2QVector(const KItemRangeList& itemRanges)
+{
+    QVector<int> result;
+    foreach (const KItemRange& range, itemRanges) {
+        for (int i = range.index; i < range.index + range.count; ++i) {
+            result.append(i);
+        }
+    }
+    return result;
+}
+
+/**
+ * Converts a KItemSet to a QSet<int>.
+ */
+static QSet<int> KItemSet2QSet(const KItemSet& itemSet)
+{
+    QSet<int> result;
+    foreach (int i, itemSet) {
+        result.insert(i);
+    }
+
+    // Check that the conversion was successful.
+    Q_ASSERT(itemSet.count() == result.count());
+
+    foreach (int i, itemSet) {
+        Q_ASSERT(result.contains(i));
+    }
+
+    foreach (int i, result) {
+        Q_ASSERT(itemSet.contains(i));
+    }
+
+    return result;
+}
+
+
+/**
+ * The main test class.
+ */
+class KItemSetTest : public QObject
+{
+    Q_OBJECT
+
+private slots:
+    void initTestCase();
+
+    void testConstruction_data();
+    void testConstruction();
+    void testIterators_data();
+    void testIterators();
+    void testFind_data();
+    void testFind();
+    void testChangingOneItem_data();
+    void testChangingOneItem();
+    void testAddSets_data();
+    void testAddSets();
+    /*
+    void testSubtractSets_data();
+    void testSubtractSets();
+    */
+    void testSymmetricDifference_data();
+    void testSymmetricDifference();
+
+private:
+    QHash<const char*, KItemRangeList> m_testCases;
+};
+
+void KItemSetTest::initTestCase()
+{
+    m_testCases.insert("empty", KItemRangeList());
+    m_testCases.insert("[0]", KItemRangeList() << KItemRange(0, 1));
+    m_testCases.insert("[1]", KItemRangeList() << KItemRange(1, 1));
+    m_testCases.insert("[1, 2]", KItemRangeList() << KItemRange(1, 2));
+    m_testCases.insert("[1, 2] [5]", KItemRangeList() << KItemRange(1, 2) << KItemRange(5, 1));
+    m_testCases.insert("[1] [4, 5]", KItemRangeList() << KItemRange(1, 1) << KItemRange(4, 2));
+    m_testCases.insert("[1, 2] [4, 5]", KItemRangeList() << KItemRange(1, 2) << KItemRange(4, 2));
+    m_testCases.insert("[1, 5]", KItemRangeList() << KItemRange(1, 5));
+    m_testCases.insert("[1, 2] [4, 5] [7] [9, 10] [13] [20, 25] [30]",
+                       KItemRangeList() << KItemRange(1, 2) << KItemRange(4, 2) << KItemRange(7, 1) << KItemRange(9, 2) << KItemRange(20, 6) << KItemRange(30, 1));
+    m_testCases.insert("[-10, -1]", KItemRangeList() << KItemRange(-10, 10));
+    m_testCases.insert("[-10, 0]", KItemRangeList() << KItemRange(-10, 11));
+    m_testCases.insert("[-10, 1]", KItemRangeList() << KItemRange(-10, 12));
+    m_testCases.insert("[0, 9]", KItemRangeList() << KItemRange(0, 10));
+    m_testCases.insert("[0, 19]", KItemRangeList() << KItemRange(0, 10));
+}
+
+void KItemSetTest::testConstruction_data()
+{
+    QTest::addColumn<KItemRangeList>("itemRanges");
+
+    QHash<const char*, KItemRangeList>::const_iterator it = m_testCases.constBegin();
+    const QHash<const char*, KItemRangeList>::const_iterator end = m_testCases.constEnd();
+
+    while (it != end) {
+        QTest::newRow(it.key()) << it.value();
+        ++it;
+    }
+}
+
+void KItemSetTest::testConstruction()
+{
+    QFETCH(KItemRangeList, itemRanges);
+
+    KItemSet itemSet = KItemRangeList2KItemSet(itemRanges);
+    QSet<int> itemsQSet = KItemRangeList2QSet(itemRanges);
+
+    QVERIFY(itemSet.isValid());
+    QVERIFY(itemSet.count() == itemsQSet.count());
+    QCOMPARE(KItemSet2QSet(itemSet), itemsQSet);
+
+    // Test copy constructor.
+    KItemSet copy(itemSet);
+    QCOMPARE(itemSet, copy);
+    copy.clear();
+    QVERIFY(itemSet != copy || itemSet.isEmpty());
+
+    // Clear the set.
+    itemSet.clear();
+    QVERIFY(itemSet.isEmpty());
+    QCOMPARE(itemSet.count(), 0);
+}
+
+void KItemSetTest::testIterators_data()
+{
+    QTest::addColumn<KItemRangeList>("itemRanges");
+
+    QHash<const char*, KItemRangeList>::const_iterator it = m_testCases.constBegin();
+    const QHash<const char*, KItemRangeList>::const_iterator end = m_testCases.constEnd();
+
+    while (it != end) {
+        QTest::newRow(it.key()) << it.value();
+        ++it;
+    }
+}
+
+/**
+ * Verify that the iterators work exactly like their counterparts for the
+ * equivalent QVector<int>.
+ */
+void KItemSetTest::testIterators()
+{
+    QFETCH(KItemRangeList, itemRanges);
+
+    KItemSet itemSet = KItemRangeList2KItemSet(itemRanges);
+    QVector<int> itemsQVector = KItemRangeList2QVector(itemRanges);
+
+    QVERIFY(itemSet.isValid());
+    QVERIFY(itemSet.count() == itemsQVector.count());
+
+    if (itemSet.count() == 0) {
+        QVERIFY(itemSet.isEmpty());
+        QVERIFY(itemSet.begin() == itemSet.end());
+        QVERIFY(itemSet.constBegin() == itemSet.constEnd());
+    } else {
+        QVERIFY(!itemSet.isEmpty());
+        QVERIFY(itemSet.begin() != itemSet.end());
+        QVERIFY(itemSet.constBegin() != itemSet.constEnd());
+
+        const int min = itemsQVector.first();
+        const int max = itemsQVector.last();
+
+        QCOMPARE(*itemSet.begin(), min);
+        QCOMPARE(*itemSet.constBegin(), min);
+        QCOMPARE(itemSet.first(), min);
+
+        QCOMPARE(*(--itemSet.end()), max);
+        QCOMPARE(*(--itemSet.constEnd()), max);
+        QCOMPARE(itemSet.last(), max);
+    }
+
+    // Test iterating using the different iterators.
+    QVector<int> testQVector;
+    for (KItemSet::iterator it = itemSet.begin(), end = itemSet.end(); it != end; ++it) {
+        testQVector.append(*it);
+    }
+    QCOMPARE(testQVector, itemsQVector);
+
+    testQVector.clear();
+    for (KItemSet::const_iterator it = itemSet.constBegin(), end = itemSet.constEnd(); it != end; ++it) {
+        testQVector.append(*it);
+    }
+    QCOMPARE(testQVector, itemsQVector);
+
+    testQVector.clear();
+    foreach (int i, itemSet) {
+        testQVector.append(i);
+    }
+    QCOMPARE(testQVector, itemsQVector);
+
+    // Verify that both variants of the (const)iterator's operator++ and
+    // operator-- functions behave exactly like their QVector equivalents.
+    KItemSet::iterator it1 = itemSet.begin();
+    KItemSet::iterator it2 = itemSet.begin();
+    KItemSet::const_iterator constIt1 = itemSet.constBegin();
+    KItemSet::const_iterator constIt2 = itemSet.constBegin();
+    QVector<int>::iterator vectorIt1 = itemsQVector.begin();
+    QVector<int>::iterator vectorIt2 = itemsQVector.begin();
+    QVector<int>::const_iterator vectorConstIt1 = itemsQVector.constBegin();
+    QVector<int>::const_iterator vectorConstIt2 = itemsQVector.constBegin();
+
+    while (it1 != itemSet.end()) {
+        if (it1 != --itemSet.end()) {
+            QCOMPARE(*(++it1), *(++vectorIt1));
+            QCOMPARE(*(++constIt1), *(++vectorConstIt1));
+        } else {
+            QCOMPARE(++it1, itemSet.end());
+            QCOMPARE(++vectorIt1, itemsQVector.end());
+            QCOMPARE(++constIt1, itemSet.constEnd());
+            QCOMPARE(++vectorConstIt1, itemsQVector.constEnd());
+        }
+
+        QCOMPARE(*(it2++), *(vectorIt2++));
+        QCOMPARE(*(constIt2++), *(vectorConstIt2++));
+
+        QCOMPARE(it1, it2);
+        QCOMPARE(constIt1, constIt2);
+        QCOMPARE(KItemSet::const_iterator(it1), constIt1);
+    }
+
+    QCOMPARE(it1, itemSet.end());
+    QCOMPARE(it2, itemSet.end());
+    QCOMPARE(constIt1, itemSet.constEnd());
+    QCOMPARE(constIt2, itemSet.constEnd());
+    QCOMPARE(vectorIt1, itemsQVector.end());
+    QCOMPARE(vectorIt2, itemsQVector.end());
+    QCOMPARE(vectorConstIt1, itemsQVector.constEnd());
+    QCOMPARE(vectorConstIt2, itemsQVector.constEnd());
+
+    while (it1 != itemSet.begin()) {
+        QCOMPARE(*(--it1), *(--vectorIt1));
+        QCOMPARE(*(--constIt1), *(--vectorConstIt1));
+
+        if (it2 != itemSet.end()) {
+            QCOMPARE(*(it2--), *(vectorIt2--));
+            QCOMPARE(*(constIt2--), *(vectorConstIt2--));
+        } else {
+            QCOMPARE(it2--, itemSet.end());
+            QCOMPARE(vectorIt2--, itemsQVector.end());
+            QCOMPARE(constIt2--, itemSet.constEnd());
+            QCOMPARE(vectorConstIt2--, itemsQVector.constEnd());
+        }
+
+        QCOMPARE(it1, it2);
+        QCOMPARE(constIt1, constIt2);
+        QCOMPARE(KItemSet::const_iterator(it1), constIt1);
+    }
+
+    QCOMPARE(it1, itemSet.begin());
+    QCOMPARE(it2, itemSet.begin());
+    QCOMPARE(constIt1, itemSet.constBegin());
+    QCOMPARE(constIt2, itemSet.constBegin());
+    QCOMPARE(vectorIt1, itemsQVector.begin());
+    QCOMPARE(vectorIt2, itemsQVector.begin());
+    QCOMPARE(vectorConstIt1, itemsQVector.constBegin());
+    QCOMPARE(vectorConstIt2, itemsQVector.constBegin());
+}
+
+void KItemSetTest::testFind_data()
+{
+    QTest::addColumn<KItemRangeList>("itemRanges");
+
+    QHash<const char*, KItemRangeList>::const_iterator it = m_testCases.constBegin();
+    const QHash<const char*, KItemRangeList>::const_iterator end = m_testCases.constEnd();
+
+    while (it != end) {
+        QTest::newRow(it.key()) << it.value();
+        ++it;
+    }
+}
+
+/**
+ * Test all functions that find items:
+ * contais(int), find(int), constFind(int)
+ */
+void KItemSetTest::testFind()
+{
+    QFETCH(KItemRangeList, itemRanges);
+
+    KItemSet itemSet = KItemRangeList2KItemSet(itemRanges);
+    QSet<int> itemsQSet = KItemRangeList2QSet(itemRanges);
+
+    QVERIFY(itemSet.isValid());
+    QVERIFY(itemSet.count() == itemsQSet.count());
+
+    // Find the minimum and maximum items.
+    int min;
+    int max;
+
+    if (itemSet.count() == 0) {
+        // Use some arbitrary values for the upcoming tests.
+        min = 0;
+        max = 5;
+    } else {
+        min = *itemSet.begin();
+        max = *(--itemSet.end());
+    }
+
+    // Test contains(int), find(int), and constFind(int)
+    // for items between min - 2 and max + 2.
+    for (int i = min - 2; i <= max + 2; ++i) {
+        const KItemSet::iterator it = itemSet.find(i);
+        const KItemSet::const_iterator constIt = itemSet.constFind(i);
+        QCOMPARE(KItemSet::const_iterator(it), constIt);
+
+        if (itemsQSet.contains(i)) {
+            QVERIFY(itemSet.contains(i));
+            QCOMPARE(*it, i);
+            QCOMPARE(*constIt, i);
+        } else {
+            QVERIFY(!itemSet.contains(i));
+            QCOMPARE(it, itemSet.end());
+            QCOMPARE(constIt, itemSet.constEnd());
+        }
+    }
+}
+
+void KItemSetTest::testChangingOneItem_data()
+{
+    QTest::addColumn<KItemRangeList>("itemRanges");
+
+    QHash<const char*, KItemRangeList>::const_iterator it = m_testCases.constBegin();
+    const QHash<const char*, KItemRangeList>::const_iterator end = m_testCases.constEnd();
+
+    while (it != end) {
+        QTest::newRow(it.key()) << it.value();
+        ++it;
+    }
+}
+
+/**
+ * Test all functions that change a single item:
+ * insert(int), remove(int), erase(KItemSet::iterator)
+ */
+void KItemSetTest::testChangingOneItem()
+{
+    QFETCH(KItemRangeList, itemRanges);
+
+    KItemSet itemSet = KItemRangeList2KItemSet(itemRanges);
+    QSet<int> itemsQSet = KItemRangeList2QSet(itemRanges);
+
+    QVERIFY(itemSet.isValid());
+    QVERIFY(itemSet.count() == itemsQSet.count());
+
+    // Find the minimum and maximum items.
+    int min;
+    int max;
+
+    if (itemSet.count() == 0) {
+        // Use some arbitrary values for the upcoming tests.
+        min = 0;
+        max = 5;
+    } else {
+        min = *itemSet.begin();
+        max = *(--itemSet.end());
+    }
+
+    // Test insert(int), remove(int), and erase(KItemSet::iterator)
+    // for items between min - 2 and max + 2.
+    for (int i = min - 2; i <= max + 2; ++i) {
+
+        // Test insert(int).
+        {
+            KItemSet tmp(itemSet);
+            const KItemSet::iterator insertedIt = tmp.insert(i);
+            QCOMPARE(*insertedIt, i);
+
+            QVERIFY(tmp.isValid());
+            QVERIFY(tmp.contains(i));
+
+            QSet<int> expectedQSet = itemsQSet;
+            expectedQSet.insert(i);
+            QCOMPARE(KItemSet2QSet(tmp), expectedQSet);
+
+            if (!itemSet.contains(i)) {
+                QVERIFY(itemSet != tmp);
+                QCOMPARE(tmp.count(), itemSet.count() + 1);
+            } else {
+                QCOMPARE(itemSet, tmp);
+            }
+
+            QCOMPARE(i, *tmp.find(i));
+            QCOMPARE(i, *tmp.constFind(i));
+
+            // Erase the new item and check that we get the old KItemSet back.
+            tmp.erase(tmp.find(i));
+            QVERIFY(tmp.isValid());
+            QVERIFY(!tmp.contains(i));
+
+            if (!itemSet.contains(i)) {
+                QCOMPARE(itemSet, tmp);
+            }
+
+            expectedQSet.remove(i);
+            QCOMPARE(KItemSet2QSet(tmp), expectedQSet);
+        }
+
+        // Test remove(int).
+        {
+            KItemSet tmp(itemSet);
+            const bool removed = tmp.remove(i);
+
+            QCOMPARE(removed, itemSet.contains(i));
+
+            QVERIFY(tmp.isValid());
+            QVERIFY(!tmp.contains(i));
+
+            QSet<int> expectedQSet = itemsQSet;
+            expectedQSet.remove(i);
+            QCOMPARE(KItemSet2QSet(tmp), expectedQSet);
+
+            if (itemSet.contains(i)) {
+                QVERIFY(itemSet != tmp);
+                QCOMPARE(tmp.count(), itemSet.count() - 1);
+            } else {
+                QCOMPARE(itemSet, tmp);
+            }
+
+            QCOMPARE(tmp.end(), tmp.find(i));
+            QCOMPARE(tmp.constEnd(), tmp.constFind(i));
+        }
+
+        // Test erase(KItemSet::iterator).
+        if (itemSet.contains(i)) {
+            KItemSet tmp(itemSet);
+            KItemSet::iterator it = tmp.find(i);
+            it = tmp.erase(it);
+
+            QVERIFY(tmp.isValid());
+            QVERIFY(!tmp.contains(i));
+
+            QSet<int> expectedQSet = itemsQSet;
+            expectedQSet.remove(i);
+            QCOMPARE(KItemSet2QSet(tmp), expectedQSet);
+
+            if (itemSet.contains(i)) {
+                QVERIFY(itemSet != tmp);
+                QCOMPARE(tmp.count(), itemSet.count() - 1);
+            } else {
+                QCOMPARE(itemSet, tmp);
+            }
+
+            QCOMPARE(tmp.end(), tmp.find(i));
+            QCOMPARE(tmp.constEnd(), tmp.constFind(i));
+
+            // Check the returen value, now contained in 'it'.
+            if (i == max) {
+                QCOMPARE(it, tmp.end());
+            } else {
+                // it now points to the next item.
+                QVERIFY(tmp.contains(*it));
+                for (int j = i; j < *it; ++j) {
+                    QVERIFY(!tmp.contains(j));
+                }
+            }
+        }
+    }
+
+    // Clear the set.
+    itemSet.clear();
+    QVERIFY(itemSet.isEmpty());
+    QCOMPARE(itemSet.count(), 0);
+}
+
+void KItemSetTest::testAddSets_data()
+{
+    QTest::addColumn<KItemRangeList>("itemRanges1");
+    QTest::addColumn<KItemRangeList>("itemRanges2");
+
+    QHash<const char*, KItemRangeList>::const_iterator it1 = m_testCases.constBegin();
+    const QHash<const char*, KItemRangeList>::const_iterator end = m_testCases.constEnd();
+
+    while (it1 != end) {
+        QHash<const char*, KItemRangeList>::const_iterator it2 = m_testCases.constBegin();
+
+        while (it2 != end) {
+            QByteArray name = it1.key() + QByteArray(" + ") + it2.key();
+            QTest::newRow(name) << it1.value() << it2.value();
+            ++it2;
+        }
+
+        ++it1;
+    }
+}
+
+void KItemSetTest::testAddSets()
+{
+    QFETCH(KItemRangeList, itemRanges1);
+    QFETCH(KItemRangeList, itemRanges2);
+
+    KItemSet itemSet1 = KItemRangeList2KItemSet(itemRanges1);
+    QSet<int> itemsQSet1 = KItemRangeList2QSet(itemRanges1);
+
+    KItemSet itemSet2 = KItemRangeList2KItemSet(itemRanges2);
+    QSet<int> itemsQSet2 = KItemRangeList2QSet(itemRanges2);
+
+    KItemSet sum = itemSet1 + itemSet2;
+    QSet<int> sumQSet = itemsQSet1 + itemsQSet2;
+
+    QCOMPARE(sum.count(), sumQSet.count());
+    QCOMPARE(KItemSet2QSet(sum), sumQSet);
+}
+
+void KItemSetTest::testSymmetricDifference_data()
+{
+    QTest::addColumn<KItemRangeList>("itemRanges1");
+    QTest::addColumn<KItemRangeList>("itemRanges2");
+
+    QHash<const char*, KItemRangeList>::const_iterator it1 = m_testCases.constBegin();
+    const QHash<const char*, KItemRangeList>::const_iterator end = m_testCases.constEnd();
+
+    while (it1 != end) {
+        QHash<const char*, KItemRangeList>::const_iterator it2 = m_testCases.constBegin();
+
+        while (it2 != end) {
+            QByteArray name = it1.key() + QByteArray(" ^ ") + it2.key();
+            QTest::newRow(name) << it1.value() << it2.value();
+            ++it2;
+        }
+
+        ++it1;
+    }
+}
+
+void KItemSetTest::testSymmetricDifference()
+{
+    QFETCH(KItemRangeList, itemRanges1);
+    QFETCH(KItemRangeList, itemRanges2);
+
+    KItemSet itemSet1 = KItemRangeList2KItemSet(itemRanges1);
+    QSet<int> itemsQSet1 = KItemRangeList2QSet(itemRanges1);
+
+    KItemSet itemSet2 = KItemRangeList2KItemSet(itemRanges2);
+    QSet<int> itemsQSet2 = KItemRangeList2QSet(itemRanges2);
+
+    KItemSet symmetricDifference = itemSet1 ^ itemSet2;
+    QSet<int> symmetricDifferenceQSet = (itemsQSet1 - itemsQSet2) + (itemsQSet2 - itemsQSet1);
+
+    QCOMPARE(symmetricDifference.count(), symmetricDifferenceQSet.count());
+    QCOMPARE(KItemSet2QSet(symmetricDifference), symmetricDifferenceQSet);
+
+    // Check commutativity.
+    QCOMPARE(itemSet2 ^ itemSet1, symmetricDifference);
+
+    // Some more checks:
+    // itemSet1 ^ symmetricDifference == itemSet2,
+    // itemSet2 ^ symmetricDifference == itemSet1.
+    QCOMPARE(itemSet1 ^ symmetricDifference, itemSet2);
+    QCOMPARE(itemSet2 ^ symmetricDifference, itemSet1);
+}
+
+
+QTEST_KDEMAIN(KItemSetTest, NoGUI)
+
+#include "kitemsettest.moc"