src/kitemviews/private/kfileitemmodelsortalgorithm.cpp

   1 /***************************************************************************
   2  *   Copyright (C) 2012 by Peter Penz <peter.penz19@gmail.com>             *
   3  *                                                                         *
   4  *   This program is free software; you can redistribute it and/or modify  *
   5  *   it under the terms of the GNU General Public License as published by  *
   6  *   the Free Software Foundation; either version 2 of the License, or     *
   7  *   (at your option) any later version.                                   *
   8  *                                                                         *
   9  *   This program is distributed in the hope that it will be useful,       *
  10  *   but WITHOUT ANY WARRANTY; without even the implied warranty of        *
  11  *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the         *
  12  *   GNU General Public License for more details.                          *
  13  *                                                                         *
  14  *   You should have received a copy of the GNU General Public License     *
  15  *   along with this program; if not, write to the                         *
  16  *   Free Software Foundation, Inc.,                                       *
  17  *   51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA            *
  18  ***************************************************************************/
  19
  20 #include "kfileitemmodelsortalgorithm.h"
  21
  22 #include <QThread>
  23 #include <QtCore>
  24
  25 void KFileItemModelSortAlgorithm::sort(KFileItemModel* model,
  26                                        QList<KFileItemModel::ItemData*>::iterator begin,
  27                                        QList<KFileItemModel::ItemData*>::iterator end)
  28 {
  29     static const int numberOfThreads = QThread::idealThreadCount();
  30     parallelSort(model, begin, end, numberOfThreads);
  31 }
  32
  33 void KFileItemModelSortAlgorithm::sequentialSort(KFileItemModel* model,
  34                                                  QList< KFileItemModel::ItemData* >::iterator begin,
  35                                                  QList< KFileItemModel::ItemData* >::iterator end)
  36 {
  37     // The implementation is based on qStableSortHelper() from qalgorithms.h
  38     // Copyright (C) 2011 Nokia Corporation and/or its subsidiary(-ies).
  39
  40     const int span = end - begin;
  41     if (span < 2) {
  42         return;
  43     }
  44
  45     const QList<KFileItemModel::ItemData*>::iterator middle = begin + span / 2;
  46     sequentialSort(model, begin, middle);
  47     sequentialSort(model, middle, end);
  48     merge(model, begin, middle, end);
  49 }
  50
  51 void KFileItemModelSortAlgorithm::parallelSort(KFileItemModel* model,
  52                                                QList< KFileItemModel::ItemData* >::iterator begin,
  53                                                QList< KFileItemModel::ItemData* >::iterator end,
  54                                                const int numberOfThreads)
  55 {
  56     const int span = end - begin;
  57
  58     if (numberOfThreads > 1 && span > 100) {
  59         const int newNumberOfThreads = numberOfThreads / 2;
  60         const QList<KFileItemModel::ItemData*>::iterator middle = begin + span / 2;
  61
  62         QFuture<void> future = QtConcurrent::run(parallelSort, model, begin, middle, newNumberOfThreads);
  63         parallelSort(model, middle, end, newNumberOfThreads);
  64
  65         future.waitForFinished();
  66
  67         merge(model, begin, middle, end);
  68     } else {
  69         sequentialSort(model, begin, end);
  70     }
  71 }
  72
  73 void KFileItemModelSortAlgorithm::merge(KFileItemModel* model,
  74                                         QList<KFileItemModel::ItemData*>::iterator begin,
  75                                         QList<KFileItemModel::ItemData*>::iterator pivot,
  76                                         QList<KFileItemModel::ItemData*>::iterator end)
  77 {
  78     // The implementation is based on qMerge() from qalgorithms.h
  79     // Copyright (C) 2011 Nokia Corporation and/or its subsidiary(-ies).
  80
  81     const int len1 = pivot - begin;
  82     const int len2 = end - pivot;
  83
  84     if (len1 == 0 || len2 == 0) {
  85         return;
  86     }
  87
  88     if (len1 + len2 == 2) {
  89         if (model->lessThan(*(begin + 1), *(begin))) {
  90             qSwap(*begin, *(begin + 1));
  91         }
  92         return;
  93     }
  94
  95     QList<KFileItemModel::ItemData*>::iterator firstCut;
  96     QList<KFileItemModel::ItemData*>::iterator secondCut;
  97     int len2Half;
  98     if (len1 > len2) {
  99         const int len1Half = len1 / 2;
 100         firstCut = begin + len1Half;
 101         secondCut = lowerBound(model, pivot, end, *firstCut);
 102         len2Half = secondCut - pivot;
 103     } else {
 104         len2Half = len2 / 2;
 105         secondCut = pivot + len2Half;
 106         firstCut = upperBound(model, begin, pivot, *secondCut);
 107     }
 108
 109     reverse(firstCut, pivot);
 110     reverse(pivot, secondCut);
 111     reverse(firstCut, secondCut);
 112
 113     const QList<KFileItemModel::ItemData*>::iterator newPivot = firstCut + len2Half;
 114     merge(model, begin, firstCut, newPivot);
 115     merge(model, newPivot, secondCut, end);
 116 }
 117
 118
 119 QList<KFileItemModel::ItemData*>::iterator
 120 KFileItemModelSortAlgorithm::lowerBound(KFileItemModel* model,
 121                                         QList<KFileItemModel::ItemData*>::iterator begin,
 122                                         QList<KFileItemModel::ItemData*>::iterator end,
 123                                         const KFileItemModel::ItemData* value)
 124 {
 125     // The implementation is based on qLowerBound() from qalgorithms.h
 126     // Copyright (C) 2011 Nokia Corporation and/or its subsidiary(-ies).
 127
 128     QList<KFileItemModel::ItemData*>::iterator middle;
 129     int n = int(end - begin);
 130     int half;
 131
 132     while (n > 0) {
 133         half = n >> 1;
 134         middle = begin + half;
 135         if (model->lessThan(*middle, value)) {
 136             begin = middle + 1;
 137             n -= half + 1;
 138         } else {
 139             n = half;
 140         }
 141     }
 142     return begin;
 143 }
 144
 145 QList<KFileItemModel::ItemData*>::iterator
 146 KFileItemModelSortAlgorithm::upperBound(KFileItemModel* model,
 147                                         QList<KFileItemModel::ItemData*>::iterator begin,
 148                                         QList<KFileItemModel::ItemData*>::iterator end,
 149                                         const KFileItemModel::ItemData* value)
 150 {
 151     // The implementation is based on qUpperBound() from qalgorithms.h
 152     // Copyright (C) 2011 Nokia Corporation and/or its subsidiary(-ies).
 153
 154     QList<KFileItemModel::ItemData*>::iterator middle;
 155     int n = end - begin;
 156     int half;
 157
 158     while (n > 0) {
 159         half = n >> 1;
 160         middle = begin + half;
 161         if (model->lessThan(value, *middle)) {
 162             n = half;
 163         } else {
 164             begin = middle + 1;
 165             n -= half + 1;
 166         }
 167     }
 168     return begin;
 169 }
 170
 171 void KFileItemModelSortAlgorithm::reverse(QList<KFileItemModel::ItemData*>::iterator begin,
 172                                           QList<KFileItemModel::ItemData*>::iterator end)
 173 {
 174     // The implementation is based on qReverse() from qalgorithms.h
 175     // Copyright (C) 2011 Nokia Corporation and/or its subsidiary(-ies).
 176
 177     --end;
 178     while (begin < end) {
 179         qSwap(*begin++, *end--);
 180     }
 181 }