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