Merge remote-tracking branch 'origin/release/21.08'

[dolphin.git] / src / kitemviews / private / kfileitemmodelsortalgorithm.h

diff --git a/src/kitemviews/private/kfileitemmodelsortalgorithm.h b/src/kitemviews/private/kfileitemmodelsortalgorithm.h
index 07e5d4a814d02031cb1667fecaf48e42bddea1df..4ee6095ca3a469cc6d5be6afb58443dd97614f6e 100644 (file)
--- a/src/kitemviews/private/kfileitemmodelsortalgorithm.h
+++ b/src/kitemviews/private/kfileitemmodelsortalgorithm.h
@@ -1,79 +1,132 @@
-/***************************************************************************
- *   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            *
- ***************************************************************************/
+/*
+ * SPDX-FileCopyrightText: 2012 Peter Penz <peter.penz19@gmail.com>
+ * SPDX-FileCopyrightText: 2012 Emmanuel Pescosta <emmanuelpescosta099@gmail.com>
+ * SPDX-FileCopyrightText: 2013 Frank Reininghaus <frank78ac@googlemail.com>
+ *
+ * SPDX-License-Identifier: GPL-2.0-or-later
+ */

 
 #ifndef KFILEITEMMODELSORTALGORITHM_H
 #define KFILEITEMMODELSORTALGORITHM_H
 
 
 #ifndef KFILEITEMMODELSORTALGORITHM_H
 #define KFILEITEMMODELSORTALGORITHM_H
 

-#include <libdolphin_export.h>
+#include <QtConcurrentRun>

 
 

-#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
  *
  * 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.
+ * SPDX-FileCopyrightText: 2011 Nokia Corporation and/or its subsidiary(-ies).

  */
  */

-class LIBDOLPHINPRIVATE_EXPORT KFileItemModelSortAlgorithm
+
+template <typename RandomAccessIterator, typename LessThan>
+static void mergeSort(RandomAccessIterator begin,
+                      RandomAccessIterator end,
+                      const LessThan& lessThan)

 {
 {

-public:
-    static void sort(KFileItemModel* model,
-                     QList<KFileItemModel::ItemData*>::iterator begin,
-                     QList<KFileItemModel::ItemData*>::iterator end);
-
-private:
-    static void sequentialSort(KFileItemModel* model,
-                               QList<KFileItemModel::ItemData*>::iterator begin,
-                               QList<KFileItemModel::ItemData*>::iterator end);
-
-    static void parallelSort(KFileItemModel* model,
-                             QList<KFileItemModel::ItemData*>::iterator begin,
-                             QList<KFileItemModel::ItemData*>::iterator end,
-                             const int numberOfThreads);
-
-    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);
-};
+    // The implementation is based on qStableSortHelper() from qalgorithms.h
+    // SPDX-FileCopyrightText: 2011 Nokia Corporation and/or its subsidiary(-ies).

 
 

-#endif
+    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 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
+ * SPDX-FileCopyrightText: 2011 Nokia Corporation and/or its subsidiary(-ies).
+ */
+
+template <typename RandomAccessIterator, typename LessThan>
+static void merge(RandomAccessIterator begin,
+                  RandomAccessIterator pivot,
+                  RandomAccessIterator end,
+                  const LessThan& lessThan)
+{
+    // The implementation is based on qMerge() from qalgorithms.h
+    // SPDX-FileCopyrightText: 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<RandomAccessIterator,
+            decltype(*firstCut), const LessThan&>(pivot, end, *firstCut, lessThan);
+        len2Half = secondCut - pivot;
+    } else {
+        len2Half = len2 / 2;
+        secondCut = pivot + len2Half;
+        firstCut = std::upper_bound<RandomAccessIterator,
+            decltype(*secondCut), const LessThan&>(begin, pivot, *secondCut, lessThan);
+    }
+
+    std::rotate(firstCut, pivot, secondCut);
+
+    RandomAccessIterator newPivot = firstCut + len2Half;
+    merge(begin, firstCut, newPivot, lessThan);
+    merge(newPivot, secondCut, end, lessThan);
+}
+
+#endif