From 1e6031c04debac1accb49ea19912a845f577abee Mon Sep 17 00:00:00 2001 From: Peter Penz Date: Wed, 4 Apr 2012 13:35:34 +0200 Subject: [PATCH] Extract sorting-algorithm from KFileItemModel into custom class --- src/CMakeLists.txt | 1 + src/kitemviews/kfileitemmodel.cpp | 129 +-------------- src/kitemviews/kfileitemmodel.h | 27 +--- .../kfileitemmodelsortalgorithm.cpp | 148 ++++++++++++++++++ .../kfileitemmodelsortalgorithm_p.h | 70 +++++++++ 5 files changed, 225 insertions(+), 150 deletions(-) create mode 100644 src/kitemviews/kfileitemmodelsortalgorithm.cpp create mode 100644 src/kitemviews/kfileitemmodelsortalgorithm_p.h diff --git a/src/CMakeLists.txt b/src/CMakeLists.txt index 45d7c495f..9f9d38653 100644 --- a/src/CMakeLists.txt +++ b/src/CMakeLists.txt @@ -23,6 +23,7 @@ set(dolphinprivate_LIB_SRCS kitemviews/kfileitemlistview.cpp kitemviews/kfileitemlistwidget.cpp kitemviews/kfileitemmodel.cpp + kitemviews/kfileitemmodelsortalgorithm.cpp kitemviews/kfileitemmodelfilter.cpp kitemviews/kfileitemmodelrolesupdater.cpp kitemviews/kitemlistcontainer.cpp diff --git a/src/kitemviews/kfileitemmodel.cpp b/src/kitemviews/kfileitemmodel.cpp index 1d7366cb2..ce4872a85 100644 --- a/src/kitemviews/kfileitemmodel.cpp +++ b/src/kitemviews/kfileitemmodel.cpp @@ -21,6 +21,7 @@ #include #include +#include "kfileitemmodelsortalgorithm_p.h" #include #include #include @@ -613,7 +614,7 @@ void KFileItemModel::resortAllItems() 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); } @@ -887,7 +888,7 @@ void KFileItemModel::insertItems(const KFileItemList& items) m_groups.clear(); QList sortedItems = createItemDataList(items); - sort(sortedItems.begin(), sortedItems.end()); + KFileItemModelSortAlgorithm::sort(this, sortedItems.begin(), sortedItems.end()); #ifdef KFILEITEMMODEL_DEBUG kDebug() << "[TIME] Sorting:" << timer.elapsed(); @@ -966,7 +967,7 @@ void KFileItemModel::removeItems(const KFileItemList& items) sortedItems.append(m_itemData.at(index)); } } - sort(sortedItems.begin(), sortedItems.end()); + KFileItemModelSortAlgorithm::sort(this, sortedItems.begin(), sortedItems.end()); QList indexesToRemove; indexesToRemove.reserve(items.count()); @@ -1386,128 +1387,6 @@ int KFileItemModel::sortRoleCompare(const ItemData* a, const ItemData* b) const return QString::compare(itemA.url().url(), itemB.url().url(), Qt::CaseSensitive); } -void KFileItemModel::sort(QList::iterator begin, - QList::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::iterator middle = begin + span / 2; - sort(begin, middle); - sort(middle, end); - merge(begin, middle, end); -} - -void KFileItemModel::merge(QList::iterator begin, - QList::iterator pivot, - QList::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::iterator firstCut; - QList::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::iterator newPivot = firstCut + len2Half; - merge(begin, firstCut, newPivot); - merge(newPivot, secondCut, end); -} - -QList::iterator KFileItemModel::lowerBound(QList::iterator begin, - QList::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::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::iterator KFileItemModel::upperBound(QList::iterator begin, - QList::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::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::iterator begin, - QList::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.*) diff --git a/src/kitemviews/kfileitemmodel.h b/src/kitemviews/kfileitemmodel.h index 4824dec3d..42cb15403 100644 --- a/src/kitemviews/kfileitemmodel.h +++ b/src/kitemviews/kfileitemmodel.h @@ -274,30 +274,6 @@ private: */ 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::iterator begin, QList::iterator end); - - /** Helper method for sort(). */ - void merge(QList::iterator begin, - QList::iterator pivot, - QList::iterator end); - - /** Helper method for sort(). */ - QList::iterator lowerBound(QList::iterator begin, - QList::iterator end, - const ItemData* value); - - /** Helper method for sort(). */ - QList::iterator upperBound(QList::iterator begin, - QList::iterator end, - const ItemData* value); - /** Helper method for sort(). */ - void reverse(QList::iterator begin, QList::iterator end); - int stringCompare(const QString& a, const QString& b) const; /** @@ -408,7 +384,8 @@ private: // and done step after step in slotCompleted(). QSet 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 diff --git a/src/kitemviews/kfileitemmodelsortalgorithm.cpp b/src/kitemviews/kfileitemmodelsortalgorithm.cpp new file mode 100644 index 000000000..4c2f29dee --- /dev/null +++ b/src/kitemviews/kfileitemmodelsortalgorithm.cpp @@ -0,0 +1,148 @@ +/*************************************************************************** + * Copyright (C) 2012 by Peter Penz * + * * + * 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::iterator begin, + QList::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::iterator middle = begin + span / 2; + sort(model, begin, middle); + sort(model, middle, end); + merge(model, begin, middle, end); +} + +void KFileItemModelSortAlgorithm::merge(KFileItemModel* model, + QList::iterator begin, + QList::iterator pivot, + QList::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::iterator firstCut; + QList::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::iterator newPivot = firstCut + len2Half; + merge(model, begin, firstCut, newPivot); + merge(model, newPivot, secondCut, end); +} + + +QList::iterator +KFileItemModelSortAlgorithm::lowerBound(KFileItemModel* model, + QList::iterator begin, + QList::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::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::iterator +KFileItemModelSortAlgorithm::upperBound(KFileItemModel* model, + QList::iterator begin, + QList::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::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::iterator begin, + QList::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--); + } +} diff --git a/src/kitemviews/kfileitemmodelsortalgorithm_p.h b/src/kitemviews/kfileitemmodelsortalgorithm_p.h new file mode 100644 index 000000000..3a596dff5 --- /dev/null +++ b/src/kitemviews/kfileitemmodelsortalgorithm_p.h @@ -0,0 +1,70 @@ +/*************************************************************************** + * Copyright (C) 2012 by Peter Penz * + * * + * 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 + +#include + +/** + * @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::iterator begin, + QList::iterator end); + +private: + static void merge(KFileItemModel* model, + QList::iterator begin, + QList::iterator pivot, + QList::iterator end); + + static QList::iterator + lowerBound(KFileItemModel* model, + QList::iterator begin, + QList::iterator end, + const KFileItemModel::ItemData* value); + + static QList::iterator + upperBound(KFileItemModel* model, + QList::iterator begin, + QList::iterator end, + const KFileItemModel::ItemData* value); + + static void reverse(QList::iterator begin, + QList::iterator end); +}; + +#endif + + -- 2.47.3