src/kitemviews/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_p.h"
  21
  22 void KFileItemModelSortAlgorithm::sort(KFileItemModel* model,
  23                                        QList<KFileItemModel::ItemData*>::iterator begin,
  24                                        QList<KFileItemModel::ItemData*>::iterator end)
  25 {
  26     // The implementation is based on qStableSortHelper() from qalgorithms.h
  27     // Copyright (C) 2011 Nokia Corporation and/or its subsidiary(-ies).
  28
  29     const int span = end - begin;
  30     if (span < 2) {
  31         return;
  32     }
  33
  34     const QList<KFileItemModel::ItemData*>::iterator middle = begin + span / 2;
  35     sort(model, begin, middle);
  36     sort(model, middle, end);
  37     merge(model, begin, middle, end);
  38 }
  39
  40 void KFileItemModelSortAlgorithm::merge(KFileItemModel* model,
  41                                         QList<KFileItemModel::ItemData*>::iterator begin,
  42                                         QList<KFileItemModel::ItemData*>::iterator pivot,
  43                                         QList<KFileItemModel::ItemData*>::iterator end)
  44 {
  45     // The implementation is based on qMerge() from qalgorithms.h
  46     // Copyright (C) 2011 Nokia Corporation and/or its subsidiary(-ies).
  47
  48     const int len1 = pivot - begin;
  49     const int len2 = end - pivot;
  50
  51     if (len1 == 0 || len2 == 0) {
  52         return;
  53     }
  54
  55     if (len1 + len2 == 2) {
  56         if (model->lessThan(*(begin + 1), *(begin))) {
  57             qSwap(*begin, *(begin + 1));
  58         }
  59         return;
  60     }
  61
  62     QList<KFileItemModel::ItemData*>::iterator firstCut;
  63     QList<KFileItemModel::ItemData*>::iterator secondCut;
  64     int len2Half;
  65     if (len1 > len2) {
  66         const int len1Half = len1 / 2;
  67         firstCut = begin + len1Half;
  68         secondCut = lowerBound(model, pivot, end, *firstCut);
  69         len2Half = secondCut - pivot;
  70     } else {
  71         len2Half = len2 / 2;
  72         secondCut = pivot + len2Half;
  73         firstCut = upperBound(model, begin, pivot, *secondCut);
  74     }
  75
  76     reverse(firstCut, pivot);
  77     reverse(pivot, secondCut);
  78     reverse(firstCut, secondCut);
  79
  80     const QList<KFileItemModel::ItemData*>::iterator newPivot = firstCut + len2Half;
  81     merge(model, begin, firstCut, newPivot);
  82     merge(model, newPivot, secondCut, end);
  83 }
  84
  85
  86 QList<KFileItemModel::ItemData*>::iterator
  87 KFileItemModelSortAlgorithm::lowerBound(KFileItemModel* model,
  88                                         QList<KFileItemModel::ItemData*>::iterator begin,
  89                                         QList<KFileItemModel::ItemData*>::iterator end,
  90                                         const KFileItemModel::ItemData* value)
  91 {
  92     // The implementation is based on qLowerBound() from qalgorithms.h
  93     // Copyright (C) 2011 Nokia Corporation and/or its subsidiary(-ies).
  94
  95     QList<KFileItemModel::ItemData*>::iterator middle;
  96     int n = int(end - begin);
  97     int half;
  98
  99     while (n > 0) {
 100         half = n >> 1;
 101         middle = begin + half;
 102         if (model->lessThan(*middle, value)) {
 103             begin = middle + 1;
 104             n -= half + 1;
 105         } else {
 106             n = half;
 107         }
 108     }
 109     return begin;
 110 }
 111
 112 QList<KFileItemModel::ItemData*>::iterator
 113 KFileItemModelSortAlgorithm::upperBound(KFileItemModel* model,
 114                                         QList<KFileItemModel::ItemData*>::iterator begin,
 115                                         QList<KFileItemModel::ItemData*>::iterator end,
 116                                         const KFileItemModel::ItemData* value)
 117 {
 118     // The implementation is based on qUpperBound() from qalgorithms.h
 119     // Copyright (C) 2011 Nokia Corporation and/or its subsidiary(-ies).
 120
 121     QList<KFileItemModel::ItemData*>::iterator middle;
 122     int n = end - begin;
 123     int half;
 124
 125     while (n > 0) {
 126         half = n >> 1;
 127         middle = begin + half;
 128         if (model->lessThan(value, *middle)) {
 129             n = half;
 130         } else {
 131             begin = middle + 1;
 132             n -= half + 1;
 133         }
 134     }
 135     return begin;
 136 }
 137
 138 void KFileItemModelSortAlgorithm::reverse(QList<KFileItemModel::ItemData*>::iterator begin,
 139                                           QList<KFileItemModel::ItemData*>::iterator end)
 140 {
 141     // The implementation is based on qReverse() from qalgorithms.h
 142     // Copyright (C) 2011 Nokia Corporation and/or its subsidiary(-ies).
 143
 144     --end;
 145     while (begin < end) {
 146         qSwap(*begin++, *end--);
 147     }
 148 }