kitemviews/kstandarditemmodel.cpp
kitemviews/private/kfileitemclipboard.cpp
kitemviews/private/kfileitemmodeldirlister.cpp
- kitemviews/private/kfileitemmodelsortalgorithm.cpp
kitemviews/private/kfileitemmodelfilter.cpp
kitemviews/private/kitemlistheaderwidget.cpp
kitemviews/private/kitemlistkeyboardsearchmanager.cpp
m_items.clear();
// Resort the items
- KFileItemModelSortAlgorithm::sort(this, m_itemData.begin(), m_itemData.end());
+ sort(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);
- KFileItemModelSortAlgorithm::sort(this, sortedItems.begin(), sortedItems.end());
+ sort(sortedItems.begin(), sortedItems.end());
#ifdef KFILEITEMMODEL_DEBUG
kDebug() << "[TIME] Sorting:" << timer.elapsed();
sortedItems.append(m_itemData.at(index));
}
}
- KFileItemModelSortAlgorithm::sort(this, sortedItems.begin(), sortedItems.end());
+ sort(sortedItems.begin(), sortedItems.end());
QList<int> indexesToRemove;
indexesToRemove.reserve(items.count());
return (sortOrder() == Qt::AscendingOrder) ? result < 0 : result > 0;
}
+/**
+ * Helper class for KFileItemModel::sort().
+ */
+class KFileItemModelLessThan
+{
+public:
+ KFileItemModelLessThan(const KFileItemModel* model) :
+ m_model(model)
+ {
+ }
+
+ bool operator()(const KFileItemModel::ItemData* a, const KFileItemModel::ItemData* b) const
+ {
+ return m_model->lessThan(a, b);
+ }
+
+private:
+ const KFileItemModel* m_model;
+};
+
+void KFileItemModel::sort(QList<KFileItemModel::ItemData*>::iterator begin,
+ QList<KFileItemModel::ItemData*>::iterator end) const
+{
+ KFileItemModelLessThan lessThan(this);
+
+ if (m_sortRole == NameRole) {
+ // Sorting by name can be expensive, in particular if natural sorting is
+ // enabled. Use all CPU cores to speed up the sorting process.
+ static const int numberOfThreads = QThread::idealThreadCount();
+ parallelMergeSort(begin, end, lessThan, numberOfThreads);
+ } else {
+ // Sorting by other roles is quite fast. Use only one thread to prevent
+ // problems caused by non-reentrant comparison functions, see
+ // https://bugs.kde.org/show_bug.cgi?id=312679
+ mergeSort(begin, end, lessThan);
+ }
+}
+
int KFileItemModel::sortRoleCompare(const ItemData* a, const ItemData* b) const
{
const KFileItem& itemA = a->item;
*/
bool lessThan(const ItemData* a, const ItemData* b) const;
+ /**
+ * Sorts the items between \a begin and \a end using the comparison
+ * function lessThan().
+ */
+ void sort(QList<ItemData*>::iterator begin, QList<ItemData*>::iterator end) const;
+
/**
* Helper method for lessThan() and expandedParentsCountCompare(): Compares
* the passed item-data using m_sortRole as criteria. Both items must
QSet<KUrl> m_urlsToExpand;
friend class KFileItemModelLessThan; // Accesses lessThan() method
- friend class KFileItemModelSortAlgorithm; // Accesses NameRole
friend class KFileItemModelRolesUpdater; // Accesses emitSortProgress() method
friend class KFileItemModelTest; // For unit testing
friend class KFileItemListViewTest; // For unit testing
+++ /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.h"
-
-#include <QThread>
-#include <QtCore>
-
-#include <algorithm>
-
-class KFileItemModelLessThan
-{
-public:
- KFileItemModelLessThan(KFileItemModel* model) :
- m_model(model)
- {
- }
-
- bool operator()(const KFileItemModel::ItemData* a, const KFileItemModel::ItemData* b)
- {
- return m_model->lessThan(a, b);
- }
-
-private:
- KFileItemModel* m_model;
-};
-
-void KFileItemModelSortAlgorithm::sort(KFileItemModel* model,
- QList<KFileItemModel::ItemData*>::iterator begin,
- QList<KFileItemModel::ItemData*>::iterator end)
-{
- KFileItemModelLessThan lessThan(model);
-
- if (model->sortRole() == model->roleForType(KFileItemModel::NameRole)) {
- // Sorting by name can be expensive, in particular if natural sorting is
- // enabled. Use all CPU cores to speed up the sorting process.
- static const int numberOfThreads = QThread::idealThreadCount();
- parallelSort(begin, end, lessThan, numberOfThreads);
- } else {
- // Sorting by other roles is quite fast. Use only one thread to prevent
- // problems caused by non-reentrant comparison functions, see
- // https://bugs.kde.org/show_bug.cgi?id=312679
- sequentialSort(begin, end, lessThan);
- }
-}
-
-template <typename RandomAccessIterator, typename LessThan>
-static void sequentialSort(RandomAccessIterator begin,
- RandomAccessIterator end,
- LessThan lessThan)
-{
- // 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 RandomAccessIterator middle = begin + span / 2;
- sequentialSort(begin, middle, lessThan);
- sequentialSort(middle, end, lessThan);
- merge(begin, middle, end, lessThan);
-}
-
-template <typename RandomAccessIterator, typename LessThan>
-static void parallelSort(RandomAccessIterator begin,
- RandomAccessIterator end,
- LessThan lessThan,
- int numberOfThreads,
- int parallelSortingThreshold)
-{
- const int span = end - begin;
-
- if (numberOfThreads > 1 && span > parallelSortingThreshold) {
- const int newNumberOfThreads = numberOfThreads / 2;
- const RandomAccessIterator middle = begin + span / 2;
-
- QFuture<void> future = QtConcurrent::run(parallelSort<RandomAccessIterator, LessThan>, begin, middle, lessThan, newNumberOfThreads, parallelSortingThreshold);
- parallelSort(middle, end, lessThan, newNumberOfThreads, parallelSortingThreshold);
-
- future.waitForFinished();
-
- merge(begin, middle, end, lessThan);
- } else {
- sequentialSort(begin, end, lessThan);
- }
-}
-
-template <typename RandomAccessIterator, typename LessThan>
-static void merge(RandomAccessIterator begin,
- RandomAccessIterator pivot,
- RandomAccessIterator end,
- LessThan lessThan)
-{
- // 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;
- }
-
- RandomAccessIterator firstCut;
- RandomAccessIterator secondCut;
- int len2Half;
- if (len1 > len2) {
- const int len1Half = len1 / 2;
- firstCut = begin + len1Half;
- secondCut = std::lower_bound(pivot, end, *firstCut, lessThan);
- len2Half = secondCut - pivot;
- } else {
- len2Half = len2 / 2;
- secondCut = pivot + len2Half;
- firstCut = std::upper_bound(begin, pivot, *secondCut, lessThan);
- }
-
- std::rotate(firstCut, pivot, secondCut);
-
- RandomAccessIterator newPivot = firstCut + len2Half;
- merge(begin, firstCut, newPivot, lessThan);
- merge(newPivot, secondCut, end, lessThan);
-}
-/***************************************************************************
- * 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 *
- ***************************************************************************/
+/*****************************************************************************
+ * Copyright (C) 2012 by Peter Penz <peter.penz19@gmail.com> *
+ * Copyright (C) 2012 by Emmanuel Pescosta <emmanuelpescosta099@gmail.com> *
+ * Copyright (C) 2013 by Frank Reininghaus <frank78ac@googlemail.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 <QtCore>
-#include <kitemviews/kfileitemmodel.h>
+#include <algorithm>
/**
- * @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.
+ * Sorts the items using 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);
-};
template <typename RandomAccessIterator, typename LessThan>
-static void sequentialSort(RandomAccessIterator begin,
- RandomAccessIterator end,
- LessThan lessThan);
+static void mergeSort(RandomAccessIterator begin,
+ RandomAccessIterator end,
+ LessThan lessThan)
+{
+ // 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 RandomAccessIterator middle = begin + span / 2;
+ mergeSort(begin, middle, lessThan);
+ mergeSort(middle, end, lessThan);
+ merge(begin, middle, end, lessThan);
+}
+
+/**
+ * Uses up to \a numberOfThreads threads to sort the items between
+ * \a begin and \a end. Only item ranges longer than
+ * \a parallelMergeSortingThreshold are split to be sorted by two different
+ * threads.
+ *
+ * The comparison function \a lessThan must be reentrant.
+ */
template <typename RandomAccessIterator, typename LessThan>
-static void parallelSort(RandomAccessIterator begin,
- RandomAccessIterator end,
- LessThan lessThan,
- int numberOfThreads,
- int parallelSortingThreshold = 100);
+static void parallelMergeSort(RandomAccessIterator begin,
+ RandomAccessIterator end,
+ LessThan lessThan,
+ int numberOfThreads,
+ int parallelMergeSortingThreshold = 100)
+{
+ const int span = end - begin;
+
+ if (numberOfThreads > 1 && span > parallelMergeSortingThreshold) {
+ const int newNumberOfThreads = numberOfThreads / 2;
+ const RandomAccessIterator middle = begin + span / 2;
+
+ QFuture<void> future = QtConcurrent::run(parallelMergeSort<RandomAccessIterator, LessThan>, begin, middle, lessThan, newNumberOfThreads, parallelMergeSortingThreshold);
+ parallelMergeSort(middle, end, lessThan, newNumberOfThreads, parallelMergeSortingThreshold);
+
+ future.waitForFinished();
+
+ merge(begin, middle, end, lessThan);
+ } else {
+ mergeSort(begin, end, lessThan);
+ }
+}
+
+/**
+ * Merges the sorted item ranges between \a begin and \a pivot and
+ * between \a pivot and \a end into a single sorted range between
+ * \a begin and \a end.
+ *
+ * The implementation is based on qMerge() 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.
+ */
template <typename RandomAccessIterator, typename LessThan>
static void merge(RandomAccessIterator begin,
RandomAccessIterator pivot,
RandomAccessIterator end,
- LessThan lessThan);
+ LessThan lessThan)
+{
+ // The implementation is based on qMerge() from qalgorithms.h
+ // Copyright (C) 2011 Nokia Corporation and/or its subsidiary(-ies).
-#endif
+ 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;
+ }
+
+ RandomAccessIterator firstCut;
+ RandomAccessIterator secondCut;
+ int len2Half;
+ if (len1 > len2) {
+ const int len1Half = len1 / 2;
+ firstCut = begin + len1Half;
+ secondCut = std::lower_bound(pivot, end, *firstCut, lessThan);
+ len2Half = secondCut - pivot;
+ } else {
+ len2Half = len2 / 2;
+ secondCut = pivot + len2Half;
+ firstCut = std::upper_bound(begin, pivot, *secondCut, lessThan);
+ }
+ std::rotate(firstCut, pivot, secondCut);
+
+ RandomAccessIterator newPivot = firstCut + len2Half;
+ merge(begin, firstCut, newPivot, lessThan);
+ merge(newPivot, secondCut, end, lessThan);
+}
+
+#endif
projects / dolphin.git / commitdiff