src/kitemviews/private/kfileitemmodelsortalgorithm.h

   1 /*
   2  * SPDX-FileCopyrightText: 2012 Peter Penz <peter.penz19@gmail.com>
   3  * SPDX-FileCopyrightText: 2012 Emmanuel Pescosta <emmanuelpescosta099@gmail.com>
   4  * SPDX-FileCopyrightText: 2013 Frank Reininghaus <frank78ac@googlemail.com>
   5  *
   6  * SPDX-License-Identifier: GPL-2.0-or-later
   7  */
   8
   9 #ifndef KFILEITEMMODELSORTALGORITHM_H
  10 #define KFILEITEMMODELSORTALGORITHM_H
  11
  12 #include <QtConcurrentRun>
  13
  14 #include <algorithm>
  15
  16 /**
  17  * Sorts the items using the merge sort algorithm is used to assure a
  18  * worst-case of O(n * log(n)) and to keep the number of comparisons low.
  19  *
  20  * The implementation is based on qStableSortHelper() from qalgorithms.h
  21  * SPDX-FileCopyrightText: 2011 Nokia Corporation and/or its subsidiary(-ies).
  22  */
  23
  24 template<typename RandomAccessIterator, typename LessThan>
  25 static void mergeSort(RandomAccessIterator begin, RandomAccessIterator end, const LessThan &lessThan)
  26 {
  27     // The implementation is based on qStableSortHelper() from qalgorithms.h
  28     // SPDX-FileCopyrightText: 2011 Nokia Corporation and/or its subsidiary(-ies).
  29
  30     const int span = end - begin;
  31     if (span < 2) {
  32         return;
  33     }
  34
  35     const RandomAccessIterator middle = begin + span / 2;
  36     mergeSort(begin, middle, lessThan);
  37     mergeSort(middle, end, lessThan);
  38     merge(begin, middle, end, lessThan);
  39 }
  40
  41 /**
  42  * Uses up to \a numberOfThreads threads to sort the items between
  43  * \a begin and \a end. Only item ranges longer than
  44  * \a parallelMergeSortingThreshold are split to be sorted by two different
  45  * threads.
  46  *
  47  * The comparison function \a lessThan must be reentrant.
  48  */
  49
  50 template<typename RandomAccessIterator, typename LessThan>
  51 static void
  52 parallelMergeSort(RandomAccessIterator begin, RandomAccessIterator end, LessThan lessThan, int numberOfThreads, int parallelMergeSortingThreshold = 100)
  53 {
  54     const int span = end - begin;
  55
  56     if (numberOfThreads > 1 && span > parallelMergeSortingThreshold) {
  57         const int newNumberOfThreads = numberOfThreads / 2;
  58         const RandomAccessIterator middle = begin + span / 2;
  59
  60         QFuture<void> future =
  61             QtConcurrent::run(parallelMergeSort<RandomAccessIterator, LessThan>, begin, middle, lessThan, newNumberOfThreads, parallelMergeSortingThreshold);
  62         parallelMergeSort(middle, end, lessThan, newNumberOfThreads, parallelMergeSortingThreshold);
  63
  64         future.waitForFinished();
  65
  66         merge(begin, middle, end, lessThan);
  67     } else {
  68         mergeSort(begin, end, lessThan);
  69     }
  70 }
  71
  72 /**
  73  * Merges the sorted item ranges between \a begin and \a pivot and
  74  * between \a pivot and \a end into a single sorted range between
  75  * \a begin and \a end.
  76  *
  77  * The implementation is based on qMerge() from qalgorithms.h
  78  * SPDX-FileCopyrightText: 2011 Nokia Corporation and/or its subsidiary(-ies).
  79  */
  80
  81 template<typename RandomAccessIterator, typename LessThan>
  82 static void merge(RandomAccessIterator begin, RandomAccessIterator pivot, RandomAccessIterator end, const LessThan &lessThan)
  83 {
  84     // The implementation is based on qMerge() from qalgorithms.h
  85     // SPDX-FileCopyrightText: 2011 Nokia Corporation and/or its subsidiary(-ies).
  86
  87     const int len1 = pivot - begin;
  88     const int len2 = end - pivot;
  89
  90     if (len1 == 0 || len2 == 0) {
  91         return;
  92     }
  93
  94     if (len1 + len2 == 2) {
  95         if (lessThan(*(begin + 1), *(begin))) {
  96             std::swap(*begin, *(begin + 1));
  97         }
  98         return;
  99     }
 100
 101     RandomAccessIterator firstCut;
 102     RandomAccessIterator secondCut;
 103     int len2Half;
 104     if (len1 > len2) {
 105         const int len1Half = len1 / 2;
 106         firstCut = begin + len1Half;
 107         secondCut = std::lower_bound<RandomAccessIterator, decltype(*firstCut), const LessThan &>(pivot, end, *firstCut, lessThan);
 108         len2Half = secondCut - pivot;
 109     } else {
 110         len2Half = len2 / 2;
 111         secondCut = pivot + len2Half;
 112         firstCut = std::upper_bound<RandomAccessIterator, decltype(*secondCut), const LessThan &>(begin, pivot, *secondCut, lessThan);
 113     }
 114
 115     std::rotate(firstCut, pivot, secondCut);
 116
 117     RandomAccessIterator newPivot = firstCut + len2Half;
 118     merge(begin, firstCut, newPivot, lessThan);
 119     merge(newPivot, secondCut, end, lessThan);
 120 }
 121
 122 #endif