src/kitemviews/private/kfileitemmodelsortalgorithm.h

   1 /*****************************************************************************
   2  *   Copyright (C) 2012 by Peter Penz <peter.penz19@gmail.com>               *
   3  *   Copyright (C) 2012 by Emmanuel Pescosta <emmanuelpescosta099@gmail.com> *
   4  *   Copyright (C) 2013 by Frank Reininghaus <frank78ac@googlemail.com>      *
   5  *                                                                           *
   6  *   This program is free software; you can redistribute it and/or modify    *
   7  *   it under the terms of the GNU General Public License as published by    *
   8  *   the Free Software Foundation; either version 2 of the License, or       *
   9  *   (at your option) any later version.                                     *
  10  *                                                                           *
  11  *   This program is distributed in the hope that it will be useful,         *
  12  *   but WITHOUT ANY WARRANTY; without even the implied warranty of          *
  13  *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the           *
  14  *   GNU General Public License for more details.                            *
  15  *                                                                           *
  16  *   You should have received a copy of the GNU General Public License       *
  17  *   along with this program; if not, write to the                           *
  18  *   Free Software Foundation, Inc.,                                         *
  19  *   51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA              *
  20  *****************************************************************************/
  21
  22 #ifndef KFILEITEMMODELSORTALGORITHM_H
  23 #define KFILEITEMMODELSORTALGORITHM_H
  24
  25 #include <QtConcurrentRun>
  26
  27 #include <algorithm>
  28
  29 /**
  30  * Sorts the items using the merge sort algorithm is used to assure a
  31  * worst-case of O(n * log(n)) and to keep the number of comparisons low.
  32  *
  33  * The implementation is based on qStableSortHelper() from qalgorithms.h
  34  * Copyright (C) 2011 Nokia Corporation and/or its subsidiary(-ies).
  35  */
  36
  37 template <typename RandomAccessIterator, typename LessThan>
  38 static void mergeSort(RandomAccessIterator begin,
  39                       RandomAccessIterator end,
  40                       const LessThan& lessThan)
  41 {
  42     // The implementation is based on qStableSortHelper() from qalgorithms.h
  43     // Copyright (C) 2011 Nokia Corporation and/or its subsidiary(-ies).
  44
  45     const int span = end - begin;
  46     if (span < 2) {
  47         return;
  48     }
  49
  50     const RandomAccessIterator middle = begin + span / 2;
  51     mergeSort(begin, middle, lessThan);
  52     mergeSort(middle, end, lessThan);
  53     merge(begin, middle, end, lessThan);
  54 }
  55
  56 /**
  57  * Uses up to \a numberOfThreads threads to sort the items between
  58  * \a begin and \a end. Only item ranges longer than
  59  * \a parallelMergeSortingThreshold are split to be sorted by two different
  60  * threads.
  61  *
  62  * The comparison function \a lessThan must be reentrant.
  63  */
  64
  65 template <typename RandomAccessIterator, typename LessThan>
  66 static void parallelMergeSort(RandomAccessIterator begin,
  67                               RandomAccessIterator end,
  68                               LessThan lessThan,
  69                               int numberOfThreads,
  70                               int parallelMergeSortingThreshold = 100)
  71 {
  72     const int span = end - begin;
  73
  74     if (numberOfThreads > 1 && span > parallelMergeSortingThreshold) {
  75         const int newNumberOfThreads = numberOfThreads / 2;
  76         const RandomAccessIterator middle = begin + span / 2;
  77
  78         QFuture<void> future = QtConcurrent::run(parallelMergeSort<RandomAccessIterator, LessThan>, begin, middle, lessThan, newNumberOfThreads, parallelMergeSortingThreshold);
  79         parallelMergeSort(middle, end, lessThan, newNumberOfThreads, parallelMergeSortingThreshold);
  80
  81         future.waitForFinished();
  82
  83         merge(begin, middle, end, lessThan);
  84     } else {
  85         mergeSort(begin, end, lessThan);
  86     }
  87 }
  88
  89 /**
  90  * Merges the sorted item ranges between \a begin and \a pivot and
  91  * between \a pivot and \a end into a single sorted range between
  92  * \a begin and \a end.
  93  *
  94  * The implementation is based on qMerge() from qalgorithms.h
  95  * Copyright (C) 2011 Nokia Corporation and/or its subsidiary(-ies).
  96  */
  97
  98 template <typename RandomAccessIterator, typename LessThan>
  99 static void merge(RandomAccessIterator begin,
 100                   RandomAccessIterator pivot,
 101                   RandomAccessIterator end,
 102                   const LessThan& lessThan)
 103 {
 104     // The implementation is based on qMerge() from qalgorithms.h
 105     // Copyright (C) 2011 Nokia Corporation and/or its subsidiary(-ies).
 106
 107     const int len1 = pivot - begin;
 108     const int len2 = end - pivot;
 109
 110     if (len1 == 0 || len2 == 0) {
 111         return;
 112     }
 113
 114     if (len1 + len2 == 2) {
 115         if (lessThan(*(begin + 1), *(begin))) {
 116             qSwap(*begin, *(begin + 1));
 117         }
 118         return;
 119     }
 120
 121     RandomAccessIterator firstCut;
 122     RandomAccessIterator secondCut;
 123     int len2Half;
 124     if (len1 > len2) {
 125         const int len1Half = len1 / 2;
 126         firstCut = begin + len1Half;
 127         secondCut = std::lower_bound<RandomAccessIterator,
 128             decltype(*firstCut), const LessThan&>(pivot, end, *firstCut, lessThan);
 129         len2Half = secondCut - pivot;
 130     } else {
 131         len2Half = len2 / 2;
 132         secondCut = pivot + len2Half;
 133         firstCut = std::upper_bound<RandomAccessIterator,
 134             decltype(*secondCut), const LessThan&>(begin, pivot, *secondCut, lessThan);
 135     }
 136
 137     std::rotate(firstCut, pivot, secondCut);
 138
 139     RandomAccessIterator newPivot = firstCut + len2Half;
 140     merge(begin, firstCut, newPivot, lessThan);
 141     merge(newPivot, secondCut, end, lessThan);
 142 }
 143
 144 #endif
 145