kitemviews/kfileitemlistview.cpp
kitemviews/kfileitemlistwidget.cpp
kitemviews/kfileitemmodel.cpp
+ kitemviews/kfileitemmodelsortalgorithm.cpp
kitemviews/kfileitemmodelfilter.cpp
kitemviews/kfileitemmodelrolesupdater.cpp
kitemviews/kitemlistcontainer.cpp
#include <KDirLister>
#include <KDirModel>
+#include "kfileitemmodelsortalgorithm_p.h"
#include <KGlobalSettings>
#include <KLocale>
#include <KStringHandler>
m_items.clear();
// Resort the items
- sort(m_itemData.begin(), m_itemData.end());
+ KFileItemModelSortAlgorithm::sort(this, m_itemData.begin(), m_itemData.end());
for (int i = 0; i < itemCount; ++i) {
m_items.insert(m_itemData.at(i)->item.url(), i);
}
m_groups.clear();
QList<ItemData*> sortedItems = createItemDataList(items);
- sort(sortedItems.begin(), sortedItems.end());
+ KFileItemModelSortAlgorithm::sort(this, sortedItems.begin(), sortedItems.end());
#ifdef KFILEITEMMODEL_DEBUG
kDebug() << "[TIME] Sorting:" << timer.elapsed();
sortedItems.append(m_itemData.at(index));
}
}
- sort(sortedItems.begin(), sortedItems.end());
+ KFileItemModelSortAlgorithm::sort(this, sortedItems.begin(), sortedItems.end());
QList<int> indexesToRemove;
indexesToRemove.reserve(items.count());
return QString::compare(itemA.url().url(), itemB.url().url(), Qt::CaseSensitive);
}
-void KFileItemModel::sort(QList<ItemData*>::iterator begin,
- QList<ItemData*>::iterator end)
-{
- // The implementation is based on qStableSortHelper() from qalgorithms.h
- // Copyright (C) 2011 Nokia Corporation and/or its subsidiary(-ies).
- // In opposite to qStableSort() it allows to use a member-function for the comparison of elements.
-
- const int span = end - begin;
- if (span < 2) {
- return;
- }
-
- const QList<ItemData*>::iterator middle = begin + span / 2;
- sort(begin, middle);
- sort(middle, end);
- merge(begin, middle, end);
-}
-
-void KFileItemModel::merge(QList<ItemData*>::iterator begin,
- QList<ItemData*>::iterator pivot,
- QList<ItemData*>::iterator end)
-{
- // The implementation is based on qMerge() from qalgorithms.h
- // Copyright (C) 2011 Nokia Corporation and/or its subsidiary(-ies).
-
- const int len1 = pivot - begin;
- const int len2 = end - pivot;
-
- if (len1 == 0 || len2 == 0) {
- return;
- }
-
- if (len1 + len2 == 2) {
- if (lessThan(*(begin + 1), *(begin))) {
- qSwap(*begin, *(begin + 1));
- }
- return;
- }
-
- QList<ItemData*>::iterator firstCut;
- QList<ItemData*>::iterator secondCut;
- int len2Half;
- if (len1 > len2) {
- const int len1Half = len1 / 2;
- firstCut = begin + len1Half;
- secondCut = lowerBound(pivot, end, *firstCut);
- len2Half = secondCut - pivot;
- } else {
- len2Half = len2 / 2;
- secondCut = pivot + len2Half;
- firstCut = upperBound(begin, pivot, *secondCut);
- }
-
- reverse(firstCut, pivot);
- reverse(pivot, secondCut);
- reverse(firstCut, secondCut);
-
- const QList<ItemData*>::iterator newPivot = firstCut + len2Half;
- merge(begin, firstCut, newPivot);
- merge(newPivot, secondCut, end);
-}
-
-QList<KFileItemModel::ItemData*>::iterator KFileItemModel::lowerBound(QList<ItemData*>::iterator begin,
- QList<ItemData*>::iterator end,
- const ItemData* value)
-{
- // The implementation is based on qLowerBound() from qalgorithms.h
- // Copyright (C) 2011 Nokia Corporation and/or its subsidiary(-ies).
-
- QList<ItemData*>::iterator middle;
- int n = int(end - begin);
- int half;
-
- while (n > 0) {
- half = n >> 1;
- middle = begin + half;
- if (lessThan(*middle, value)) {
- begin = middle + 1;
- n -= half + 1;
- } else {
- n = half;
- }
- }
- return begin;
-}
-
-QList<KFileItemModel::ItemData*>::iterator KFileItemModel::upperBound(QList<ItemData*>::iterator begin,
- QList<ItemData*>::iterator end,
- const ItemData* value)
-{
- // The implementation is based on qUpperBound() from qalgorithms.h
- // Copyright (C) 2011 Nokia Corporation and/or its subsidiary(-ies).
-
- QList<ItemData*>::iterator middle;
- int n = end - begin;
- int half;
-
- while (n > 0) {
- half = n >> 1;
- middle = begin + half;
- if (lessThan(value, *middle)) {
- n = half;
- } else {
- begin = middle + 1;
- n -= half + 1;
- }
- }
- return begin;
-}
-
-void KFileItemModel::reverse(QList<ItemData*>::iterator begin,
- QList<ItemData*>::iterator end)
-{
- // The implementation is based on qReverse() from qalgorithms.h
- // Copyright (C) 2011 Nokia Corporation and/or its subsidiary(-ies).
-
- --end;
- while (begin < end) {
- qSwap(*begin++, *end--);
- }
-}
-
int KFileItemModel::stringCompare(const QString& a, const QString& b) const
{
// Taken from KDirSortFilterProxyModel (kdelibs/kfile/kdirsortfilterproxymodel.*)
*/
int sortRoleCompare(const ItemData* a, const ItemData* b) const;
- /**
- * Sorts the items by using lessThan() as comparison criteria.
- * The merge sort algorithm is used to assure a worst-case
- * of O(n * log(n)) and to keep the number of comparisons low.
- */
- void sort(QList<ItemData*>::iterator begin, QList<ItemData*>::iterator end);
-
- /** Helper method for sort(). */
- void merge(QList<ItemData*>::iterator begin,
- QList<ItemData*>::iterator pivot,
- QList<ItemData*>::iterator end);
-
- /** Helper method for sort(). */
- QList<ItemData*>::iterator lowerBound(QList<ItemData*>::iterator begin,
- QList<ItemData*>::iterator end,
- const ItemData* value);
-
- /** Helper method for sort(). */
- QList<ItemData*>::iterator upperBound(QList<ItemData*>::iterator begin,
- QList<ItemData*>::iterator end,
- const ItemData* value);
- /** Helper method for sort(). */
- void reverse(QList<ItemData*>::iterator begin, QList<ItemData*>::iterator end);
-
int stringCompare(const QString& a, const QString& b) const;
/**
// and done step after step in slotCompleted().
QSet<KUrl> m_urlsToExpand;
- friend class KFileItemModelTest; // For unit testing
+ friend class KFileItemModelSortAlgorithm; // Accesses lessThan() method
+ friend class KFileItemModelTest; // For unit testing
};
inline bool KFileItemModel::isChildItem(int index) const
--- /dev/null
+/***************************************************************************
+ * Copyright (C) 2012 by Peter Penz <peter.penz19@gmail.com> *
+ * *
+ * 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 "kfileitemmodelsortalgorithm_p.h"
+
+void KFileItemModelSortAlgorithm::sort(KFileItemModel* model,
+ QList<KFileItemModel::ItemData*>::iterator begin,
+ QList<KFileItemModel::ItemData*>::iterator end)
+{
+ // The implementation is based on qStableSortHelper() from qalgorithms.h
+ // Copyright (C) 2011 Nokia Corporation and/or its subsidiary(-ies).
+
+ const int span = end - begin;
+ if (span < 2) {
+ return;
+ }
+
+ const QList<KFileItemModel::ItemData*>::iterator middle = begin + span / 2;
+ sort(model, begin, middle);
+ sort(model, middle, end);
+ merge(model, begin, middle, end);
+}
+
+void KFileItemModelSortAlgorithm::merge(KFileItemModel* model,
+ QList<KFileItemModel::ItemData*>::iterator begin,
+ QList<KFileItemModel::ItemData*>::iterator pivot,
+ QList<KFileItemModel::ItemData*>::iterator end)
+{
+ // The implementation is based on qMerge() from qalgorithms.h
+ // Copyright (C) 2011 Nokia Corporation and/or its subsidiary(-ies).
+
+ const int len1 = pivot - begin;
+ const int len2 = end - pivot;
+
+ if (len1 == 0 || len2 == 0) {
+ return;
+ }
+
+ if (len1 + len2 == 2) {
+ if (model->lessThan(*(begin + 1), *(begin))) {
+ qSwap(*begin, *(begin + 1));
+ }
+ return;
+ }
+
+ QList<KFileItemModel::ItemData*>::iterator firstCut;
+ QList<KFileItemModel::ItemData*>::iterator secondCut;
+ int len2Half;
+ if (len1 > len2) {
+ const int len1Half = len1 / 2;
+ firstCut = begin + len1Half;
+ secondCut = lowerBound(model, pivot, end, *firstCut);
+ len2Half = secondCut - pivot;
+ } else {
+ len2Half = len2 / 2;
+ secondCut = pivot + len2Half;
+ firstCut = upperBound(model, begin, pivot, *secondCut);
+ }
+
+ reverse(firstCut, pivot);
+ reverse(pivot, secondCut);
+ reverse(firstCut, secondCut);
+
+ const QList<KFileItemModel::ItemData*>::iterator newPivot = firstCut + len2Half;
+ merge(model, begin, firstCut, newPivot);
+ merge(model, newPivot, secondCut, end);
+}
+
+
+QList<KFileItemModel::ItemData*>::iterator
+KFileItemModelSortAlgorithm::lowerBound(KFileItemModel* model,
+ QList<KFileItemModel::ItemData*>::iterator begin,
+ QList<KFileItemModel::ItemData*>::iterator end,
+ const KFileItemModel::ItemData* value)
+{
+ // The implementation is based on qLowerBound() from qalgorithms.h
+ // Copyright (C) 2011 Nokia Corporation and/or its subsidiary(-ies).
+
+ QList<KFileItemModel::ItemData*>::iterator middle;
+ int n = int(end - begin);
+ int half;
+
+ while (n > 0) {
+ half = n >> 1;
+ middle = begin + half;
+ if (model->lessThan(*middle, value)) {
+ begin = middle + 1;
+ n -= half + 1;
+ } else {
+ n = half;
+ }
+ }
+ return begin;
+}
+
+QList<KFileItemModel::ItemData*>::iterator
+KFileItemModelSortAlgorithm::upperBound(KFileItemModel* model,
+ QList<KFileItemModel::ItemData*>::iterator begin,
+ QList<KFileItemModel::ItemData*>::iterator end,
+ const KFileItemModel::ItemData* value)
+{
+ // The implementation is based on qUpperBound() from qalgorithms.h
+ // Copyright (C) 2011 Nokia Corporation and/or its subsidiary(-ies).
+
+ QList<KFileItemModel::ItemData*>::iterator middle;
+ int n = end - begin;
+ int half;
+
+ while (n > 0) {
+ half = n >> 1;
+ middle = begin + half;
+ if (model->lessThan(value, *middle)) {
+ n = half;
+ } else {
+ begin = middle + 1;
+ n -= half + 1;
+ }
+ }
+ return begin;
+}
+
+void KFileItemModelSortAlgorithm::reverse(QList<KFileItemModel::ItemData*>::iterator begin,
+ QList<KFileItemModel::ItemData*>::iterator end)
+{
+ // The implementation is based on qReverse() from qalgorithms.h
+ // Copyright (C) 2011 Nokia Corporation and/or its subsidiary(-ies).
+
+ --end;
+ while (begin < end) {
+ qSwap(*begin++, *end--);
+ }
+}
--- /dev/null
+/***************************************************************************
+ * Copyright (C) 2012 by Peter Penz <peter.penz19@gmail.com> *
+ * *
+ * 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 KFILEITEMMODELSORTALGORITHM_H
+#define KFILEITEMMODELSORTALGORITHM_H
+
+#include <libdolphin_export.h>
+
+#include <kitemviews/kfileitemmodel.h>
+
+/**
+ * @brief Sort algorithm for sorting items of KFileItemModel.
+ *
+ * Sorts the items by using KFileItemModel::lessThan() as comparison criteria.
+ * The merge sort algorithm is used to assure a worst-case
+ * of O(n * log(n)) and to keep the number of comparisons low.
+ *
+ * The implementation is based on qStableSortHelper() from qalgorithms.h
+ * Copyright (C) 2011 Nokia Corporation and/or its subsidiary(-ies).
+ * The sorting implementations of qAlgorithms could not be used as they
+ * don't support having a member-function as comparison criteria.
+ */
+class LIBDOLPHINPRIVATE_EXPORT KFileItemModelSortAlgorithm
+{
+public:
+ static void sort(KFileItemModel* model,
+ QList<KFileItemModel::ItemData*>::iterator begin,
+ QList<KFileItemModel::ItemData*>::iterator end);
+
+private:
+ static void merge(KFileItemModel* model,
+ QList<KFileItemModel::ItemData*>::iterator begin,
+ QList<KFileItemModel::ItemData*>::iterator pivot,
+ QList<KFileItemModel::ItemData*>::iterator end);
+
+ static QList<KFileItemModel::ItemData*>::iterator
+ lowerBound(KFileItemModel* model,
+ QList<KFileItemModel::ItemData*>::iterator begin,
+ QList<KFileItemModel::ItemData*>::iterator end,
+ const KFileItemModel::ItemData* value);
+
+ static QList<KFileItemModel::ItemData*>::iterator
+ upperBound(KFileItemModel* model,
+ QList<KFileItemModel::ItemData*>::iterator begin,
+ QList<KFileItemModel::ItemData*>::iterator end,
+ const KFileItemModel::ItemData* value);
+
+ static void reverse(QList<KFileItemModel::ItemData*>::iterator begin,
+ QList<KFileItemModel::ItemData*>::iterator end);
+};
+
+#endif
+
+
projects / dolphin.git / commitdiff