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,
  26                       RandomAccessIterator end,
  27                       const LessThan& lessThan)
  28 {
  29     // The implementation is based on qStableSortHelper() from qalgorithms.h
  30     // SPDX-FileCopyrightText: 2011 Nokia Corporation and/or its subsidiary(-ies).
  31
  32     const int span = end - begin;
  33     if (span < 2) {
  34         return;
  35     }
  36
  37     const RandomAccessIterator middle = begin + span / 2;
  38     mergeSort(begin, middle, lessThan);
  39     mergeSort(middle, end, lessThan);
  40     merge(begin, middle, end, lessThan);
  41 }
  42
  43 /**
  44  * Uses up to \a numberOfThreads threads to sort the items between
  45  * \a begin and \a end. Only item ranges longer than
  46  * \a parallelMergeSortingThreshold are split to be sorted by two different
  47  * threads.
  48  *
  49  * The comparison function \a lessThan must be reentrant.
  50  */
  51
  52 template <typename RandomAccessIterator, typename LessThan>
  53 static void parallelMergeSort(RandomAccessIterator begin,
  54                               RandomAccessIterator end,
  55                               LessThan lessThan,
  56                               int numberOfThreads,
  57                               int parallelMergeSortingThreshold = 100)
  58 {
  59     const int span = end - begin;
  60
  61     if (numberOfThreads > 1 && span > parallelMergeSortingThreshold) {
  62         const int newNumberOfThreads = numberOfThreads / 2;
  63         const RandomAccessIterator middle = begin + span / 2;
  64
  65         QFuture<void> future = QtConcurrent::run(parallelMergeSort<RandomAccessIterator, LessThan>, begin, middle, lessThan, newNumberOfThreads, parallelMergeSortingThreshold);
  66         parallelMergeSort(middle, end, lessThan, newNumberOfThreads, parallelMergeSortingThreshold);
  67
  68         future.waitForFinished();
  69
  70         merge(begin, middle, end, lessThan);
  71     } else {
  72         mergeSort(begin, end, lessThan);
  73     }
  74 }
  75
  76 /**
  77  * Merges the sorted item ranges between \a begin and \a pivot and
  78  * between \a pivot and \a end into a single sorted range between
  79  * \a begin and \a end.
  80  *
  81  * The implementation is based on qMerge() from qalgorithms.h
  82  * SPDX-FileCopyrightText: 2011 Nokia Corporation and/or its subsidiary(-ies).
  83  */
  84
  85 template <typename RandomAccessIterator, typename LessThan>
  86 static void merge(RandomAccessIterator begin,
  87                   RandomAccessIterator pivot,
  88                   RandomAccessIterator end,
  89                   const LessThan& lessThan)
  90 {
  91     // The implementation is based on qMerge() from qalgorithms.h
  92     // SPDX-FileCopyrightText: 2011 Nokia Corporation and/or its subsidiary(-ies).
  93
  94     const int len1 = pivot - begin;
  95     const int len2 = end - pivot;
  96
  97     if (len1 == 0 || len2 == 0) {
  98         return;
  99     }
 100
 101     if (len1 + len2 == 2) {
 102         if (lessThan(*(begin + 1), *(begin))) {
 103             qSwap(*begin, *(begin + 1));
 104         }
 105         return;
 106     }
 107
 108     RandomAccessIterator firstCut;
 109     RandomAccessIterator secondCut;
 110     int len2Half;
 111     if (len1 > len2) {
 112         const int len1Half = len1 / 2;
 113         firstCut = begin + len1Half;
 114         secondCut = std::lower_bound<RandomAccessIterator,
 115             decltype(*firstCut), const LessThan&>(pivot, end, *firstCut, lessThan);
 116         len2Half = secondCut - pivot;
 117     } else {
 118         len2Half = len2 / 2;
 119         secondCut = pivot + len2Half;
 120         firstCut = std::upper_bound<RandomAccessIterator,
 121             decltype(*secondCut), const LessThan&>(begin, pivot, *secondCut, lessThan);
 122     }
 123
 124     std::rotate(firstCut, pivot, secondCut);
 125
 126     RandomAccessIterator newPivot = firstCut + len2Half;
 127     merge(begin, firstCut, newPivot, lessThan);
 128     merge(newPivot, secondCut, end, lessThan);
 129 }
 130
 131 #endif
 132