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