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

17 files changed, 825 insertions, 71 deletions

diff --git a/src/kitemviews/kfileitemlistview.cpp b/src/kitemviews/kfileitemlistview.cpp
index 8950c9a1e..fd01f2c4c 100644
--- a/src/kitemviews/kfileitemlistview.cpp
+++ b/src/kitemviews/kfileitemlistview.cpp
@@ -119,7 +119,7 @@ QStringList KFileItemListView::enabledPlugins() const
     return m_modelRolesUpdater ? m_modelRolesUpdater->enabledPlugins() : QStringList();
 }
 
-QPixmap KFileItemListView::createDragPixmap(const QSet<int>& indexes) const
+QPixmap KFileItemListView::createDragPixmap(const KItemSet& indexes) const
 {
     if (!model()) {
         return QPixmap();
@@ -165,10 +165,8 @@ QPixmap KFileItemListView::createDragPixmap(const QSet<int>& indexes) const
     QPainter painter(&dragPixmap);
     int x = 0;
     int y = 0;
-    QSetIterator<int> it(indexes);
-    while (it.hasNext()) {
-        const int index = it.next();
 
+    foreach (int index, indexes) {
         QPixmap pixmap = model()->data(index).value("iconPixmap").value<QPixmap>();
         if (pixmap.isNull()) {
             KIcon icon(model()->data(index).value("iconName").toString());
diff --git a/src/kitemviews/kfileitemlistview.h b/src/kitemviews/kfileitemlistview.h
index bdc63b01b..2fd21edbf 100644
--- a/src/kitemviews/kfileitemlistview.h
+++ b/src/kitemviews/kfileitemlistview.h
@@ -73,7 +73,7 @@ public:
     QStringList enabledPlugins() const;
 
     /** @reimp */
-    virtual QPixmap createDragPixmap(const QSet<int>& indexes) const;
+    virtual QPixmap createDragPixmap(const KItemSet& indexes) const;
 
 protected:
     virtual KItemListWidgetCreatorBase* defaultWidgetCreator() const;
diff --git a/src/kitemviews/kfileitemmodel.cpp b/src/kitemviews/kfileitemmodel.cpp
index e2d0413a2..261b23046 100644
--- a/src/kitemviews/kfileitemmodel.cpp
+++ b/src/kitemviews/kfileitemmodel.cpp
@@ -237,7 +237,7 @@ bool KFileItemModel::showDirectoriesOnly() const
     return m_dirLister->dirOnlyMode();
 }
 
-QMimeData* KFileItemModel::createMimeData(const QSet<int>& indexes) const
+QMimeData* KFileItemModel::createMimeData(const KItemSet& indexes) const
 {
     QMimeData* data = new QMimeData();
 
@@ -248,9 +248,7 @@ QMimeData* KFileItemModel::createMimeData(const QSet<int>& indexes) const
     KUrl::List mostLocalUrls;
     bool canUseMostLocalUrls = true;
 
-    QSetIterator<int> it(indexes);
-    while (it.hasNext()) {
-        const int index = it.next();
+    foreach (int index, indexes) {
         const KFileItem item = fileItem(index);
         if (!item.isNull()) {
             urls << item.targetUrl();
diff --git a/src/kitemviews/kfileitemmodel.h b/src/kitemviews/kfileitemmodel.h
index 4b50477d9..c57329fc8 100644
--- a/src/kitemviews/kfileitemmodel.h
+++ b/src/kitemviews/kfileitemmodel.h
@@ -27,6 +27,7 @@
 #include <kitemviews/private/kfileitemmodelfilter.h>
 
 #include <QHash>
+#include <QSet>
 
 class KFileItemModelDirLister;
 class QTimer;
@@ -99,7 +100,7 @@ public:
     bool showDirectoriesOnly() const;
 
     /** @reimp */
-    virtual QMimeData* createMimeData(const QSet<int>& indexes) const;
+    virtual QMimeData* createMimeData(const KItemSet& indexes) const;
 
     /** @reimp */
     virtual int indexForKeyboardSearch(const QString& text, int startFromIndex = 0) const;
diff --git a/src/kitemviews/kitemlistcontroller.cpp b/src/kitemviews/kitemlistcontroller.cpp
index befb09713..51a1f91b9 100644
--- a/src/kitemviews/kitemlistcontroller.cpp
+++ b/src/kitemviews/kitemlistcontroller.cpp
@@ -364,11 +364,11 @@ bool KItemListController::keyPressEvent(QKeyEvent* event)
 
     case Qt::Key_Enter:
     case Qt::Key_Return: {
-        const QSet<int> selectedItems = m_selectionManager->selectedItems();
+        const KItemSet selectedItems = m_selectionManager->selectedItems();
         if (selectedItems.count() >= 2) {
             emit itemsActivated(selectedItems);
         } else if (selectedItems.count() == 1) {
-            emit itemActivated(selectedItems.toList().first());
+            emit itemActivated(selectedItems.first());
         } else {
             emit itemActivated(index);
         }
@@ -378,14 +378,14 @@ bool KItemListController::keyPressEvent(QKeyEvent* event)
     case Qt::Key_Menu: {
         // Emit the signal itemContextMenuRequested() in case if at least one
         // item is selected. Otherwise the signal viewContextMenuRequested() will be emitted.
-        const QSet<int> selectedItems = m_selectionManager->selectedItems();
+        const KItemSet selectedItems = m_selectionManager->selectedItems();
         int index = -1;
         if (selectedItems.count() >= 2) {
             const int currentItemIndex = m_selectionManager->currentItem();
             index = selectedItems.contains(currentItemIndex)
-                    ? currentItemIndex : selectedItems.toList().first();
+                    ? currentItemIndex : selectedItems.first();
         } else if (selectedItems.count() == 1) {
-            index = selectedItems.toList().first();
+            index = selectedItems.first();
         }
 
         if (index >= 0) {
@@ -1079,7 +1079,7 @@ void KItemListController::slotRubberBandChanged()
         }
     }
 
-    QSet<int> selectedItems;
+    KItemSet selectedItems;
 
     // Select all visible items that intersect with the rubberband
     foreach (const KItemListWidget* widget, m_view->visibleItemListWidgets()) {
@@ -1127,7 +1127,7 @@ void KItemListController::slotRubberBandChanged()
         // Therefore, the new selection contains:
         // 1. All previously selected items which are not inside the rubberband, and
         // 2. all items inside the rubberband which have not been selected previously.
-        m_selectionManager->setSelectedItems((m_oldSelection - selectedItems) + (selectedItems - m_oldSelection));
+        m_selectionManager->setSelectedItems(m_oldSelection ^ selectedItems);
     }
     else {
         m_selectionManager->setSelectedItems(selectedItems + m_oldSelection);
@@ -1140,7 +1140,7 @@ void KItemListController::startDragging()
         return;
     }
 
-    const QSet<int> selectedItems = m_selectionManager->selectedItems();
+    const KItemSet selectedItems = m_selectionManager->selectedItems();
     if (selectedItems.isEmpty()) {
         return;
     }
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
diff --git a/src/kitemviews/kitemlistselectionmanager.cpp b/src/kitemviews/kitemlistselectionmanager.cpp
index 833f7aad0..ebff1a30e 100644
--- a/src/kitemviews/kitemlistselectionmanager.cpp
+++ b/src/kitemviews/kitemlistselectionmanager.cpp
@@ -43,7 +43,7 @@ KItemListSelectionManager::~KItemListSelectionManager()
 void KItemListSelectionManager::setCurrentItem(int current)
 {
     const int previous = m_currentItem;
-    const QSet<int> previousSelection = selectedItems();
+    const KItemSet previousSelection = selectedItems();
 
     if (m_model && current >= 0 && current < m_model->count()) {
         m_currentItem = current;
@@ -55,7 +55,7 @@ void KItemListSelectionManager::setCurrentItem(int current)
         emit currentChanged(m_currentItem, previous);
 
         if (m_isAnchoredSelectionActive) {
-            const QSet<int> selection = selectedItems();
+            const KItemSet selection = selectedItems();
             if (selection != previousSelection) {
                 emit selectionChanged(selection, previousSelection);
             }
@@ -68,18 +68,18 @@ int KItemListSelectionManager::currentItem() const
     return m_currentItem;
 }
 
-void KItemListSelectionManager::setSelectedItems(const QSet<int>& items)
+void KItemListSelectionManager::setSelectedItems(const KItemSet& items)
 {
     if (m_selectedItems != items) {
-        const QSet<int> previous = m_selectedItems;
+        const KItemSet previous = m_selectedItems;
         m_selectedItems = items;
         emit selectionChanged(m_selectedItems, previous);
     }
 }
 
-QSet<int> KItemListSelectionManager::selectedItems() const
+KItemSet KItemListSelectionManager::selectedItems() const
 {
-    QSet<int> selectedItems = m_selectedItems;
+    KItemSet selectedItems = m_selectedItems;
 
     if (m_isAnchoredSelectionActive && m_anchorItem != m_currentItem) {
         Q_ASSERT(m_anchorItem >= 0);
@@ -127,7 +127,7 @@ void KItemListSelectionManager::setSelected(int index, int count, SelectionMode
     }
 
     endAnchoredSelection();
-    const QSet<int> previous = selectedItems();
+    const KItemSet previous = selectedItems();
 
     count = qMin(count, m_model->count() - index);
 
@@ -160,7 +160,7 @@ void KItemListSelectionManager::setSelected(int index, int count, SelectionMode
         break;
     }
 
-    const QSet<int> selection = selectedItems();
+    const KItemSet selection = selectedItems();
     if (selection != previous) {
         emit selectionChanged(selection, previous);
     }
@@ -168,11 +168,11 @@ void KItemListSelectionManager::setSelected(int index, int count, SelectionMode
 
 void KItemListSelectionManager::clearSelection()
 {
-    const QSet<int> previous = selectedItems();
+    const KItemSet previous = selectedItems();
     if (!previous.isEmpty()) {
         m_selectedItems.clear();
         m_isAnchoredSelectionActive = false;
-        emit selectionChanged(QSet<int>(), previous);
+        emit selectionChanged(KItemSet(), previous);
     }
 }
 
@@ -221,7 +221,7 @@ void KItemListSelectionManager::setModel(KItemModelBase* model)
 void KItemListSelectionManager::itemsInserted(const KItemRangeList& itemRanges)
 {
     // Store the current selection (needed in the selectionChanged() signal)
-    const QSet<int> previousSelection = selectedItems();
+    const KItemSet previousSelection = selectedItems();
 
     // Update the current item
     if (m_currentItem < 0) {
@@ -257,12 +257,10 @@ void KItemListSelectionManager::itemsInserted(const KItemRangeList& itemRanges)
 
     // Update the selections
     if (!m_selectedItems.isEmpty()) {
-        const QSet<int> previous = m_selectedItems;
+        const KItemSet previous = m_selectedItems;
         m_selectedItems.clear();
-        m_selectedItems.reserve(previous.count());
-        QSetIterator<int> it(previous);
-        while (it.hasNext()) {
-            const int index = it.next();
+
+        foreach (int index, previous) {
             int inc = 0;
             foreach (const KItemRange& itemRange, itemRanges) {
                 if (index < itemRange.index) {
@@ -274,7 +272,7 @@ void KItemListSelectionManager::itemsInserted(const KItemRangeList& itemRanges)
         }
     }
 
-    const QSet<int> selection = selectedItems();
+    const KItemSet selection = selectedItems();
     if (selection != previousSelection) {
         emit selectionChanged(selection, previousSelection);
     }
@@ -283,7 +281,7 @@ void KItemListSelectionManager::itemsInserted(const KItemRangeList& itemRanges)
 void KItemListSelectionManager::itemsRemoved(const KItemRangeList& itemRanges)
 {
     // Store the current selection (needed in the selectionChanged() signal)
-    const QSet<int> previousSelection = selectedItems();
+    const KItemSet previousSelection = selectedItems();
     const int previousCurrent = m_currentItem;
 
     // Update the current item
@@ -308,19 +306,18 @@ void KItemListSelectionManager::itemsRemoved(const KItemRangeList& itemRanges)
 
     // Update the selections and the anchor item
     if (!m_selectedItems.isEmpty()) {
-        const QSet<int> previous = m_selectedItems;
+        const KItemSet previous = m_selectedItems;
         m_selectedItems.clear();
-        m_selectedItems.reserve(previous.count());
-        QSetIterator<int> it(previous);
-        while (it.hasNext()) {
-            const int index = indexAfterRangesRemoving(it.next(), itemRanges, DiscardRemovedIndex);
+
+        foreach (int oldIndex, previous) {
+            const int index = indexAfterRangesRemoving(oldIndex, itemRanges, DiscardRemovedIndex);
             if (index >= 0)  {
                 m_selectedItems.insert(index);
             }
         }
     }
 
-    const QSet<int> selection = selectedItems();
+    const KItemSet selection = selectedItems();
     if (selection != previousSelection) {
         emit selectionChanged(selection, previousSelection);
     }
@@ -332,7 +329,7 @@ void KItemListSelectionManager::itemsRemoved(const KItemRangeList& itemRanges)
 void KItemListSelectionManager::itemsMoved(const KItemRange& itemRange, const QList<int>& movedToIndexes)
 {
     // Store the current selection (needed in the selectionChanged() signal)
-    const QSet<int> previousSelection = selectedItems();
+    const KItemSet previousSelection = selectedItems();
 
     // Update the current item
     if (m_currentItem >= itemRange.index && m_currentItem < itemRange.index + itemRange.count) {
@@ -352,12 +349,10 @@ void KItemListSelectionManager::itemsMoved(const KItemRange& itemRange, const QL
 
     // Update the selections
     if (!m_selectedItems.isEmpty()) {
-        const QSet<int> previous = m_selectedItems;
+        const KItemSet previous = m_selectedItems;
         m_selectedItems.clear();
-        m_selectedItems.reserve(previous.count());
-        QSetIterator<int> it(previous);
-        while (it.hasNext()) {
-            const int index = it.next();
+
+        foreach (int index, previous) {
             if (index >= itemRange.index && index < itemRange.index + itemRange.count) {
                 m_selectedItems.insert(movedToIndexes.at(index - itemRange.index));
             }
@@ -367,7 +362,7 @@ void KItemListSelectionManager::itemsMoved(const KItemRange& itemRange, const QL
         }
     }
 
-    const QSet<int> selection = selectedItems();
+    const KItemSet selection = selectedItems();
     if (selection != previousSelection) {
         emit selectionChanged(selection, previousSelection);
     }
diff --git a/src/kitemviews/kitemlistselectionmanager.h b/src/kitemviews/kitemlistselectionmanager.h
index c89b8a4b8..c4decd39e 100644
--- a/src/kitemviews/kitemlistselectionmanager.h
+++ b/src/kitemviews/kitemlistselectionmanager.h
@@ -26,9 +26,9 @@
 #include <libdolphin_export.h>
 
 #include <kitemviews/kitemmodelbase.h>
+#include <kitemviews/kitemset.h>
 
 #include <QObject>
-#include <QSet>
 
 class KItemModelBase;
 
@@ -57,8 +57,8 @@ public:
     void setCurrentItem(int current);
     int currentItem() const;
 
-    void setSelectedItems(const QSet<int>& items);
-    QSet<int> selectedItems() const;
+    void setSelectedItems(const KItemSet& items);
+    KItemSet selectedItems() const;
     bool isSelected(int index) const;
     bool hasSelection() const;
 
@@ -73,7 +73,7 @@ public:
 
 signals:
     void currentChanged(int current, int previous);
-    void selectionChanged(const QSet<int>& current, const QSet<int>& previous);
+    void selectionChanged(const KItemSet& current, const KItemSet& previous);
 
 private:
     void setModel(KItemModelBase* model);
@@ -91,7 +91,7 @@ private:
 private:
     int m_currentItem;
     int m_anchorItem;
-    QSet<int> m_selectedItems;
+    KItemSet m_selectedItems;
     bool m_isAnchoredSelectionActive;
 
     KItemModelBase* m_model;
diff --git a/src/kitemviews/kitemlistview.cpp b/src/kitemviews/kitemlistview.cpp
index b3d805a91..7f497210c 100644
--- a/src/kitemviews/kitemlistview.cpp
+++ b/src/kitemviews/kitemlistview.cpp
@@ -609,12 +609,12 @@ KItemListHeader* KItemListView::header() const
     return m_header;
 }
 
-QPixmap KItemListView::createDragPixmap(const QSet<int>& indexes) const
+QPixmap KItemListView::createDragPixmap(const KItemSet& indexes) const
 {
     QPixmap pixmap;
 
     if (indexes.count() == 1) {
-        KItemListWidget* item = m_visibleItems.value(indexes.toList().first());
+        KItemListWidget* item = m_visibleItems.value(indexes.first());
         QGraphicsView* graphicsView = scene()->views()[0];
         if (item && graphicsView) {
             pixmap = item->createDragPixmap(0, graphicsView);
@@ -1305,7 +1305,7 @@ void KItemListView::slotCurrentChanged(int current, int previous)
     QAccessible::updateAccessibility(this, current+1, QAccessible::Focus);
 }
 
-void KItemListView::slotSelectionChanged(const QSet<int>& current, const QSet<int>& previous)
+void KItemListView::slotSelectionChanged(const KItemSet& current, const KItemSet& previous)
 {
     Q_UNUSED(previous);
 
@@ -1502,7 +1502,7 @@ void KItemListView::setController(KItemListController* controller)
         if (previous) {
             KItemListSelectionManager* selectionManager = previous->selectionManager();
             disconnect(selectionManager, SIGNAL(currentChanged(int,int)), this, SLOT(slotCurrentChanged(int,int)));
-            disconnect(selectionManager, SIGNAL(selectionChanged(QSet<int>,QSet<int>)), this, SLOT(slotSelectionChanged(QSet<int>,QSet<int>)));
+            disconnect(selectionManager, SIGNAL(selectionChanged(KItemSet,KItemSet)), this, SLOT(slotSelectionChanged(KItemSet,KItemSet)));
         }
 
         m_controller = controller;
@@ -1510,7 +1510,7 @@ void KItemListView::setController(KItemListController* controller)
         if (controller) {
             KItemListSelectionManager* selectionManager = controller->selectionManager();
             connect(selectionManager, SIGNAL(currentChanged(int,int)), this, SLOT(slotCurrentChanged(int,int)));
-            connect(selectionManager, SIGNAL(selectionChanged(QSet<int>,QSet<int>)), this, SLOT(slotSelectionChanged(QSet<int>,QSet<int>)));
+            connect(selectionManager, SIGNAL(selectionChanged(KItemSet,KItemSet)), this, SLOT(slotSelectionChanged(KItemSet,KItemSet)));
         }
 
         onControllerChanged(controller, previous);
diff --git a/src/kitemviews/kitemlistview.h b/src/kitemviews/kitemlistview.h
index 14360b02b..dbe923086 100644
--- a/src/kitemviews/kitemlistview.h
+++ b/src/kitemviews/kitemlistview.h
@@ -271,7 +271,7 @@ public:
      * @return Pixmap that is used for a drag operation based on the
      *         items given by \a indexes.
      */
-    virtual QPixmap createDragPixmap(const QSet<int>& indexes) const;
+    virtual QPixmap createDragPixmap(const KItemSet& indexes) const;
 
     /**
      * Lets the user edit the role \a role for item with the index \a index.
@@ -400,7 +400,7 @@ protected slots:
     virtual void slotSortOrderChanged(Qt::SortOrder current, Qt::SortOrder previous);
     virtual void slotSortRoleChanged(const QByteArray& current, const QByteArray& previous);
     virtual void slotCurrentChanged(int current, int previous);
-    virtual void slotSelectionChanged(const QSet<int>& current, const QSet<int>& previous);
+    virtual void slotSelectionChanged(const KItemSet& current, const KItemSet& previous);
 
 private slots:
     void slotAnimationFinished(QGraphicsWidget* widget,
diff --git a/src/kitemviews/kitemlistviewaccessible.cpp b/src/kitemviews/kitemlistviewaccessible.cpp
index 565c2151e..d9ddd58f8 100644
--- a/src/kitemviews/kitemlistviewaccessible.cpp
+++ b/src/kitemviews/kitemlistviewaccessible.cpp
@@ -109,7 +109,7 @@ int KItemListViewAccessible::rowCount() const
 
 int KItemListViewAccessible::selectedCellCount() const
 {
-    return view()->controller()->selectionManager()->selectedItems().size();
+    return view()->controller()->selectionManager()->selectedItems().count();
 }
 
 int KItemListViewAccessible::selectedColumnCount() const
diff --git a/src/kitemviews/kitemmodelbase.cpp b/src/kitemviews/kitemmodelbase.cpp
index edce95ece..4312640e4 100644
--- a/src/kitemviews/kitemmodelbase.cpp
+++ b/src/kitemviews/kitemmodelbase.cpp
@@ -123,7 +123,7 @@ int KItemModelBase::expandedParentsCount(int index) const
     return 0;
 }
 
-QMimeData* KItemModelBase::createMimeData(const QSet<int>& indexes) const
+QMimeData* KItemModelBase::createMimeData(const KItemSet& indexes) const
 {
     Q_UNUSED(indexes);
     return 0;
diff --git a/src/kitemviews/kitemmodelbase.h b/src/kitemviews/kitemmodelbase.h
index c5b9a0ca5..283cfa552 100644
--- a/src/kitemviews/kitemmodelbase.h
+++ b/src/kitemviews/kitemmodelbase.h
@@ -26,10 +26,10 @@
 #include <libdolphin_export.h>
 
 #include <kitemviews/kitemrange.h>
+#include <kitemviews/kitemset.h>
 
 #include <QHash>
 #include <QObject>
-#include <QSet>
 #include <QVariant>
 
 class QMimeData;
@@ -149,7 +149,7 @@ public:
      *         caller of this method. The method must be implemented if dragging of
      *         items should be possible.
      */
-    virtual QMimeData* createMimeData(const QSet<int>& indexes) const;
+    virtual QMimeData* createMimeData(const KItemSet& indexes) const;
 
     /**
      * @return Reimplement this to return the index for the first item
diff --git a/src/kitemviews/kitemset.cpp b/src/kitemviews/kitemset.cpp
new file mode 100644
index 000000000..f855368c1
--- /dev/null
+++ b/src/kitemviews/kitemset.cpp
@@ -0,0 +1,348 @@
+/***************************************************************************
+ *   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 "kitemset.h"
+
+#include <QVector>
+
+#include <algorithm>
+
+KItemSet::iterator KItemSet::insert(int i)
+{
+    if (m_itemRanges.empty()) {
+        m_itemRanges.push_back(KItemRange(i, 1));
+        return iterator(m_itemRanges.begin(), 0);
+    }
+
+    KItemRangeList::iterator rangeBegin = m_itemRanges.begin();
+    if (i < rangeBegin->index) {
+        // The inserted index is smaller than all existing items.
+        if (i == rangeBegin->index - 1) {
+            // Move the beginning of the first range one item to the front.
+            --rangeBegin->index;
+            ++rangeBegin->count;
+        } else {
+            // Insert a new range at the beginning.
+            rangeBegin = m_itemRanges.insert(rangeBegin, KItemRange(i, 1));
+        }
+
+        return iterator(rangeBegin, 0);
+    }
+
+    KItemRangeList::iterator rangeEnd = m_itemRanges.end();
+    KItemRangeList::iterator lastRange = rangeEnd - 1;
+    if (i >= lastRange->index) {
+        // i either belongs to the last range, or it is larger than all existing items.
+        const int lastItemPlus1 = lastRange->index + lastRange->count;
+        if (i == lastItemPlus1) {
+            // Move the end of the last range one item to the back.
+            ++lastRange->count;
+        } else if (i > lastItemPlus1) {
+            // Append a new range.
+            lastRange = m_itemRanges.insert(rangeEnd, KItemRange(i, 1));
+        }
+
+        return iterator(lastRange, i - lastRange->index);
+    }
+
+    // We know that i is between the smallest existing item and the first item
+    // of the last range. Find the lowest range whose 'index' is smaller than i.
+    KItemRangeList::iterator low = rangeBegin;
+    KItemRangeList::iterator high = lastRange;
+
+    while (low + 1 != high) {
+        const int span = high - low;
+        Q_ASSERT(span >= 2);
+
+        KItemRangeList::iterator mid = low + span / 2;
+        if (mid->index > i) {
+            high = mid;
+        } else {
+            low = mid;
+        }
+    }
+
+    Q_ASSERT(low->index <= i && high->index > i);
+
+    if (i == low->index + low->count) {
+        // i is just one item behind the range low.
+        if (i == high->index - 1) {
+            // i closes the gap between low and high. Merge the two ranges.
+            const int newRangeCount = low->count + 1 + high->count;
+            KItemRangeList::iterator behindNewRange = m_itemRanges.erase(high);
+            KItemRangeList::iterator newRange = behindNewRange - 1;
+            newRange->count = newRangeCount;
+            return iterator(newRange, i - newRange->index);
+        } else {
+            // Extend low by one item.
+            ++low->count;
+            return iterator(low, low->count - 1);
+        }
+    } else if (i > low->index + low->count) {
+        if (i == high->index - 1) {
+            // Extend high by one item to the front.
+            --high->index;
+            ++high->count;
+            return iterator(high, 0);
+        } else {
+            // Insert a new range between low and high.
+            KItemRangeList::iterator newRange = m_itemRanges.insert(high, KItemRange(i, 1));
+            return iterator(newRange, 0);
+        }
+    } else {
+        // The range low already contains i.
+        return iterator(low, i - low->index);
+    }
+}
+
+KItemSet::iterator KItemSet::erase(iterator it)
+{
+    KItemRangeList::iterator rangeIt = it.m_rangeIt;
+
+    if (it.m_offset == 0) {
+        // Removed index is at the beginning of a range.
+        if (rangeIt->count > 1) {
+            ++rangeIt->index;
+            --rangeIt->count;
+        } else {
+            // The range only contains the removed index.
+            rangeIt = m_itemRanges.erase(rangeIt);
+        }
+        return iterator(rangeIt, 0);
+    } else if (it.m_offset == rangeIt->count - 1) {
+        // Removed index is at the end of a range.
+        --rangeIt->count;
+        ++rangeIt;
+        return iterator(rangeIt, 0);
+    } else {
+        // The removed index is in the middle of a range.
+        const int newRangeIndex = *it + 1;
+        const int newRangeCount = rangeIt->count - it.m_offset - 1;
+        const KItemRange newRange(newRangeIndex, newRangeCount);
+
+        rangeIt->count = it.m_offset;
+        ++rangeIt;
+        rangeIt = m_itemRanges.insert(rangeIt, newRange);
+
+        return iterator(rangeIt, 0);
+    }
+}
+
+KItemSet KItemSet::operator+(const KItemSet& other) const
+{
+    KItemSet sum;
+
+    KItemRangeList::const_iterator it1 = m_itemRanges.constBegin();
+    KItemRangeList::const_iterator it2 = other.m_itemRanges.constBegin();
+
+    const KItemRangeList::const_iterator end1 = m_itemRanges.constEnd();
+    const KItemRangeList::const_iterator end2 = other.m_itemRanges.constEnd();
+
+    while (it1 != end1 || it2 != end2) {
+        if (it1 == end1) {
+            // We are past the end of 'this' already. Append all remaining
+            // item ranges from 'other'.
+            while (it2 != end2) {
+                sum.m_itemRanges.append(*it2);
+                ++it2;
+            }
+        } else if (it2 == end2) {
+            // We are past the end of 'other' already. Append all remaining
+            // item ranges from 'this'.
+            while (it1 != end1) {
+                sum.m_itemRanges.append(*it1);
+                ++it1;
+            }
+        } else {
+            // Find the beginning of the next range.
+            int index = qMin(it1->index, it2->index);
+            int count = 0;
+
+            do {
+                if (it1 != end1 && it1->index <= index + count) {
+                    // The next range from 'this' overlaps with the current range in the sum.
+                    count = qMax(count, it1->index + it1->count - index);
+                    ++it1;
+                }
+
+                if (it2 != end2 && it2->index <= index + count) {
+                    // The next range from 'other' overlaps with the current range in the sum.
+                    count = qMax(count, it2->index + it2->count - index);
+                    ++it2;
+                }
+            } while ((it1 != end1 && it1->index <= index + count)
+                    || (it2 != end2 && it2->index <= index + count));
+
+            sum.m_itemRanges.append(KItemRange(index, count));
+        }
+    }
+
+    return sum;
+}
+
+KItemSet KItemSet::operator^(const KItemSet& other) const
+{
+    // We are looking for all ints which are either in *this or in other,
+    // but not in both.
+    KItemSet result;
+
+    // When we go through all integers from INT_MIN to INT_MAX and start
+    // in the state "do not add to result", every beginning/end of a range
+    // of *this and other toggles the "add/do not add to result" state.
+    // Therefore, we just have to put ints where any range starts/ends to
+    // a sorted array, and then we can calculate the result quite easily.
+    QVector<int> rangeBoundaries;
+    rangeBoundaries.resize(2 * (m_itemRanges.count() + other.m_itemRanges.count()));
+    const QVector<int>::iterator begin = rangeBoundaries.begin();
+    const QVector<int>::iterator end = rangeBoundaries.end();
+    QVector<int>::iterator it = begin;
+
+    foreach (const KItemRange& range, m_itemRanges) {
+        *it++ = range.index;
+        *it++ = range.index + range.count;
+    }
+
+    const QVector<int>::iterator middle = it;
+
+    foreach (const KItemRange& range, other.m_itemRanges) {
+        *it++ = range.index;
+        *it++ = range.index + range.count;
+    }
+    Q_ASSERT(it == end);
+
+    std::inplace_merge(begin, middle, end);
+
+    it = begin;
+    while (it != end) {
+        const int rangeBegin = *it;
+        ++it;
+
+        if (*it == rangeBegin) {
+            // It seems that ranges from both *this and other start at
+            // rangeBegin. Do not start a new range, but read the next int.
+            //
+            // Example: Consider the symmetric difference of the sets
+            // {1, 2, 3, 4} and {1, 2}. The sorted list of range boundaries is
+            // 1 1 3 5. Discarding the duplicate 1 yields the result
+            // rangeBegin = 3, rangeEnd = 5, which corresponds to the set {3, 4}.
+            ++it;
+        } else {
+            // The end of the current range is the next *single* int that we
+            // find. If an int appears twice in rangeBoundaries, the range does
+            // not end.
+            //
+            // Example: Consider the symmetric difference of the sets
+            // {1, 2, 3, 4, 8, 9, 10} and {5, 6, 7}. The sorted list of range
+            // boundaries is 1 5 5 8 8 11, and discarding all duplicates yields
+            // the result rangeBegin = 1, rangeEnd = 11, which corresponds to
+            // the set {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}.
+            bool foundEndOfRange = false;
+            int rangeEnd;
+            do {
+                rangeEnd = *it;
+                ++it;
+
+                if (it == end || *it != rangeEnd) {
+                    foundEndOfRange = true;
+                } else {
+                    ++it;
+                }
+            } while (!foundEndOfRange);
+
+            result.m_itemRanges.append(KItemRange(rangeBegin, rangeEnd - rangeBegin));
+        }
+    }
+
+    return result;
+}
+
+bool KItemSet::isValid() const
+{
+    const KItemRangeList::const_iterator begin = m_itemRanges.constBegin();
+    const KItemRangeList::const_iterator end = m_itemRanges.constEnd();
+
+    for (KItemRangeList::const_iterator it = begin; it != end; ++it) {
+        if (it->count <= 0) {
+            return false;
+        }
+
+        if (it != begin) {
+            const KItemRangeList::const_iterator previous = it - 1;
+            if (previous->index + previous->count >= it->index) {
+                return false;
+            }
+        }
+    }
+
+    return true;
+}
+
+KItemRangeList::iterator KItemSet::rangeForItem(int i)
+{
+    const KItemRangeList::iterator end = m_itemRanges.end();
+    KItemRangeList::iterator low = m_itemRanges.begin();
+    KItemRangeList::iterator high = end;
+
+    if (low == end || low->index > i) {
+        return end;
+    }
+
+    while (low != high && low + 1 != high) {
+        KItemRangeList::iterator mid = low + (high - low) / 2;
+        if (mid->index > i) {
+            high = mid;
+        } else {
+            low = mid;
+        }
+    }
+
+    Q_ASSERT(low->index <= i);
+    if (low->index + low->count > i) {
+        return low;
+    }
+
+    return end;
+}
+
+KItemRangeList::const_iterator KItemSet::constRangeForItem(int i) const
+{
+    const KItemRangeList::const_iterator end = m_itemRanges.constEnd();
+    KItemRangeList::const_iterator low = m_itemRanges.constBegin();
+    KItemRangeList::const_iterator high = end;
+
+    if (low == end || low->index > i) {
+        return end;
+    }
+
+    while (low != high && low + 1 != high) {
+        KItemRangeList::const_iterator mid = low + (high - low) / 2;
+        if (mid->index > i) {
+            high = mid;
+        } else {
+            low = mid;
+        }
+    }
+
+    Q_ASSERT(low->index <= i);
+    if (low->index + low->count > i) {
+        return low;
+    }
+
+    return end;
+}
diff --git a/src/kitemviews/kitemset.h b/src/kitemviews/kitemset.h
new file mode 100644
index 000000000..385010f7d
--- /dev/null
+++ b/src/kitemviews/kitemset.h
@@ -0,0 +1,413 @@
+/***************************************************************************
+ *   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            *
+ ***************************************************************************/
+
+#ifndef KITEMSET_H
+#define KITEMSET_H
+
+#include <kitemviews/kitemrange.h>
+
+/**
+ * @brief Stores a set of integer numbers in a space-efficient way.
+ *
+ * This class is similar to QSet<int>, but it has the following advantages:
+ *
+ * 1. It uses less memory than a QSet<int> if many consecutive numbers are
+ *    stored. This is achieved by not storing each number separately, but
+ *    "ranges" of numbers.
+ *
+ *    Example: The set {1, 2, 3, 4, 5} is represented by a single range which
+ *    starts at 1 and has the length 5.
+ *
+ * 2. When iterating through a KItemSet using KItemSet::iterator or
+ *    KItemSet::const_iterator, the numbers are traversed in ascending order.
+ *
+ * The complexity of most operations depends on the number of ranges.
+ */
+
+class KItemSet
+{
+public:
+    KItemSet();
+    KItemSet(const KItemSet& other);
+
+    /**
+     * Returns the number of items in the set.
+     * Complexity: O(log(number of ranges)).
+     */
+    int count() const;
+
+    bool isEmpty() const;
+    void clear();
+
+    bool operator==(const KItemSet& other) const;
+    bool operator!=(const KItemSet& other) const;
+
+    class iterator
+    {
+        iterator(const KItemRangeList::iterator& rangeIt, int offset) :
+            m_rangeIt(rangeIt),
+            m_offset(offset)
+        {
+        }
+
+    public:
+        iterator(const iterator& other) :
+            m_rangeIt(other.m_rangeIt),
+            m_offset(other.m_offset)
+        {
+        }
+
+        iterator& operator=(const iterator& other)
+        {
+            m_rangeIt = other.m_rangeIt;
+            m_offset = other.m_offset;
+            return *this;
+        }
+
+        int operator*() const
+        {
+            return m_rangeIt->index + m_offset;
+        }
+
+        inline bool operator==(const iterator& other) const
+        {
+            return m_rangeIt == other.m_rangeIt && m_offset == other.m_offset;
+        }
+
+        inline bool operator!=(const iterator& other) const
+        {
+            return !(*this == other);
+        }
+
+        inline iterator& operator++()
+        {
+            ++m_offset;
+
+            if (m_offset == m_rangeIt->count) {
+                ++m_rangeIt;
+                m_offset = 0;
+            }
+
+            return *this;
+        }
+
+        inline iterator operator++(int)
+        {
+            iterator r = *this;
+            ++(*this);
+            return r;
+        }
+
+        inline iterator& operator--()
+        {
+            if (m_offset == 0) {
+                --m_rangeIt;
+                m_offset = m_rangeIt->count - 1;
+            } else {
+                --m_offset;
+            }
+
+            return *this;
+        }
+
+        inline iterator operator--(int)
+        {
+            iterator r = *this;
+            --(*this);
+            return r;
+        }
+
+    private:
+        KItemRangeList::iterator m_rangeIt;
+        int m_offset;
+
+        friend class const_iterator;
+        friend class KItemSet;
+    };
+
+
+    class const_iterator
+    {
+        const_iterator(KItemRangeList::const_iterator rangeIt, int offset) :
+            m_rangeIt(rangeIt),
+            m_offset(offset)
+        {
+        }
+
+    public:
+        const_iterator(const const_iterator& other) :
+            m_rangeIt(other.m_rangeIt),
+            m_offset(other.m_offset)
+        {
+        }
+
+        const_iterator(const iterator& other) :
+            m_rangeIt(other.m_rangeIt),
+            m_offset(other.m_offset)
+        {
+        }
+
+        const_iterator& operator=(const const_iterator& other)
+        {
+            m_rangeIt = other.m_rangeIt;
+            m_offset = other.m_offset;
+            return *this;
+        }
+
+        int operator*() const
+        {
+            return m_rangeIt->index + m_offset;
+        }
+
+        inline bool operator==(const const_iterator& other) const
+        {
+            return m_rangeIt == other.m_rangeIt && m_offset == other.m_offset;
+        }
+
+        inline bool operator!=(const const_iterator& other) const
+        {
+            return !(*this == other);
+        }
+
+        inline const_iterator& operator++()
+        {
+            ++m_offset;
+
+            if (m_offset == m_rangeIt->count) {
+                ++m_rangeIt;
+                m_offset = 0;
+            }
+
+            return *this;
+        }
+
+        inline const_iterator operator++(int)
+        {
+            const_iterator r = *this;
+            ++(*this);
+            return r;
+        }
+
+        inline const_iterator& operator--()
+        {
+            if (m_offset == 0) {
+                --m_rangeIt;
+                m_offset = m_rangeIt->count - 1;
+            } else {
+                --m_offset;
+            }
+
+            return *this;
+        }
+
+        inline const_iterator operator--(int)
+        {
+            const_iterator r = *this;
+            --(*this);
+            return r;
+        }
+
+    private:
+        KItemRangeList::const_iterator m_rangeIt;
+        int m_offset;
+
+        friend class KItemSet;
+    };
+
+    iterator begin();
+    const_iterator begin() const;
+    const_iterator constBegin() const;
+    iterator end();
+    const_iterator end() const;
+    const_iterator constEnd() const;
+
+    int first() const;
+    int last() const;
+
+    bool contains(int i) const;
+    iterator insert(int i);
+    iterator find(int i);
+    const_iterator constFind(int i) const;
+    bool remove(int i);
+    iterator erase(iterator it);
+
+    /**
+     * Returns a new set which contains all items that are contained in this
+     * KItemSet, in \a other, or in both.
+     */
+    KItemSet operator+(const KItemSet& other) const;
+
+    /**
+     * Returns a new set which contains all items that are contained either in
+     * this KItemSet, or in \a other, but not in both (the symmetric difference
+     * of both KItemSets).
+     */
+    KItemSet operator^(const KItemSet& other) const;
+
+    KItemSet& operator<<(int i);
+
+private:
+    /**
+     * Returns true if the KItemSet is valid, and false otherwise.
+     * A valid KItemSet must store the item ranges in ascending order, and
+     * the ranges must not overlap.
+     */
+    bool isValid() const;
+
+    /**
+     * This function returns an iterator that points to the KItemRange which
+     * contains i, or m_itemRanges.end() if no such range exists.
+     */
+    KItemRangeList::iterator rangeForItem(int i);
+
+    /**
+     * This function returns an iterator that points to the KItemRange which
+     * contains i, or m_itemRanges.constEnd() if no such range exists.
+     */
+    KItemRangeList::const_iterator constRangeForItem(int i) const;
+
+    KItemRangeList m_itemRanges;
+
+    friend class KItemSetTest;
+};
+
+inline KItemSet::KItemSet() :
+    m_itemRanges()
+{
+}
+
+inline KItemSet::KItemSet(const KItemSet& other) :
+    m_itemRanges(other.m_itemRanges)
+{
+}
+
+inline int KItemSet::count() const
+{
+    int result = 0;
+    foreach (const KItemRange& range, m_itemRanges) {
+        result += range.count;
+    }
+    return result;
+}
+
+inline bool KItemSet::isEmpty() const
+{
+    return m_itemRanges.isEmpty();
+}
+
+inline void KItemSet::clear()
+{
+    m_itemRanges.clear();
+}
+
+inline bool KItemSet::operator==(const KItemSet& other) const
+{
+    return m_itemRanges == other.m_itemRanges;
+}
+
+inline bool KItemSet::operator!=(const KItemSet& other) const
+{
+    return m_itemRanges != other.m_itemRanges;
+}
+
+inline bool KItemSet::contains(int i) const
+{
+    const KItemRangeList::const_iterator it = constRangeForItem(i);
+    return it != m_itemRanges.end();
+}
+
+inline KItemSet::iterator KItemSet::find(int i)
+{
+    const KItemRangeList::iterator it = rangeForItem(i);
+    if (it != m_itemRanges.end()) {
+        return iterator(it, i - it->index);
+    } else {
+        return end();
+    }
+}
+
+inline KItemSet::const_iterator KItemSet::constFind(int i) const
+{
+    const KItemRangeList::const_iterator it = constRangeForItem(i);
+    if (it != m_itemRanges.constEnd()) {
+        return const_iterator(it, i - it->index);
+    } else {
+        return constEnd();
+    }
+}
+
+inline bool KItemSet::remove(int i)
+{
+    iterator it = find(i);
+    if (it != end()) {
+        erase(it);
+        return true;
+    } else {
+        return false;
+    }
+}
+
+inline KItemSet::iterator KItemSet::begin()
+{
+    return iterator(m_itemRanges.begin(), 0);
+}
+
+inline KItemSet::const_iterator KItemSet::begin() const
+{
+    return const_iterator(m_itemRanges.begin(), 0);
+}
+
+inline KItemSet::const_iterator KItemSet::constBegin() const
+{
+    return const_iterator(m_itemRanges.constBegin(), 0);
+}
+
+inline KItemSet::iterator KItemSet::end()
+{
+    return iterator(m_itemRanges.end(), 0);
+}
+
+inline KItemSet::const_iterator KItemSet::end() const
+{
+    return const_iterator(m_itemRanges.end(), 0);
+}
+
+inline KItemSet::const_iterator KItemSet::constEnd() const
+{
+    return const_iterator(m_itemRanges.constEnd(), 0);
+}
+
+inline int KItemSet::first() const
+{
+    return m_itemRanges.first().index;
+}
+
+inline int KItemSet::last() const
+{
+    const KItemRange& lastRange = m_itemRanges.last();
+    return lastRange.index + lastRange.count - 1;
+}
+
+inline KItemSet& KItemSet::operator<<(int i)
+{
+    insert(i);
+    return *this;
+}
+
+#endif
diff --git a/src/kitemviews/kstandarditemmodel.cpp b/src/kitemviews/kstandarditemmodel.cpp
index 959d62cb8..e8c1b6204 100644
--- a/src/kitemviews/kstandarditemmodel.cpp
+++ b/src/kitemviews/kstandarditemmodel.cpp
@@ -175,7 +175,7 @@ bool KStandardItemModel::setData(int index, const QHash<QByteArray, QVariant>& v
     return true;
 }
 
-QMimeData* KStandardItemModel::createMimeData(const QSet<int>& indexes) const
+QMimeData* KStandardItemModel::createMimeData(const KItemSet& indexes) const
 {
     Q_UNUSED(indexes);
     return 0;
diff --git a/src/kitemviews/kstandarditemmodel.h b/src/kitemviews/kstandarditemmodel.h
index 0debd6a6f..721e15529 100644
--- a/src/kitemviews/kstandarditemmodel.h
+++ b/src/kitemviews/kstandarditemmodel.h
@@ -72,7 +72,7 @@ public:
     virtual int count() const;
     virtual QHash<QByteArray, QVariant> data(int index) const;
     virtual bool setData(int index, const QHash<QByteArray, QVariant>& values);
-    virtual QMimeData* createMimeData(const QSet<int>& indexes) const;
+    virtual QMimeData* createMimeData(const KItemSet& indexes) const;
     virtual int indexForKeyboardSearch(const QString& text, int startFromIndex = 0) const;
     virtual bool supportsDropping(int index) const;
     virtual QString roleDescription(const QByteArray& role) const;