src/corelib/concurrent/qtconcurrentmedian.h

   1 /****************************************************************************
   2 **
   3 ** Copyright (C) 2009 Nokia Corporation and/or its subsidiary(-ies).
   4 ** All rights reserved.
   5 ** Contact: Nokia Corporation (qt-info@nokia.com)
   6 **
   7 ** This file is part of the QtCore module of the Qt Toolkit.
   8 **
   9 ** $QT_BEGIN_LICENSE:LGPL$
  10 ** No Commercial Usage
  11 ** This file contains pre-release code and may not be distributed.
  12 ** You may use this file in accordance with the terms and conditions
  13 ** contained in the Technology Preview License Agreement accompanying
  14 ** this package.
  15 **
  16 ** GNU Lesser General Public License Usage
  17 ** Alternatively, this file may be used under the terms of the GNU Lesser
  18 ** General Public License version 2.1 as published by the Free Software
  19 ** Foundation and appearing in the file LICENSE.LGPL included in the
  20 ** packaging of this file.  Please review the following information to
  21 ** ensure the GNU Lesser General Public License version 2.1 requirements
  22 ** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.
  23 **
  24 ** In addition, as a special exception, Nokia gives you certain additional
  25 ** rights.  These rights are described in the Nokia Qt LGPL Exception
  26 ** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.
  27 **
  28 ** If you have questions regarding the use of this file, please contact
  29 ** Nokia at qt-info@nokia.com.
  30 **
  31 **
  32 **
  33 **
  34 **
  35 **
  36 **
  37 **
  38 ** $QT_END_LICENSE$
  39 **
  40 ****************************************************************************/
  41
  42 #ifndef QTCONCURRENT_MEDIAN_H
  43 #define QTCONCURRENT_MEDIAN_H
  44
  45 #include <QtCore/qglobal.h>
  46
  47 #ifndef QT_NO_CONCURRENT
  48
  49 #include <QtCore/qvector.h>
  50 #include <QtCore/qalgorithms.h>
  51
  52 QT_BEGIN_HEADER
  53 QT_BEGIN_NAMESPACE
  54
  55 QT_MODULE(Core)
  56
  57 #ifndef qdoc
  58
  59 namespace QtConcurrent {
  60
  61 template <typename T>
  62 class Median
  63 {
  64 public:
  65     Median(int _bufferSize)
  66         : currentMedian(), bufferSize(_bufferSize), currentIndex(0), valid(false), dirty(true)
  67     {
  68         values.resize(bufferSize);
  69     }
  70
  71     void reset()
  72     {
  73         values.fill(0);
  74         currentIndex = 0;
  75         valid = false;
  76         dirty = true;
  77     }
  78
  79     void addValue(T value)
  80     {
  81         currentIndex = ((currentIndex + 1) % bufferSize);
  82         if (valid == false && currentIndex % bufferSize == 0)
  83             valid = true;
  84
  85         // Only update the cached median value when we have to, that
  86         // is when the new value is on then other side of the median
  87         // compared to the current value at the index.
  88         const T currentIndexValue = values[currentIndex];
  89         if ((currentIndexValue > currentMedian && currentMedian > value)
  90             || (currentMedian > currentIndexValue && value > currentMedian)) {
  91             dirty = true;
  92         }
  93
  94         values[currentIndex] = value;
  95     }
  96
  97     bool isMedianValid() const
  98     {
  99         return valid;
 100     }
 101
 102     T median()
 103     {
 104         if (dirty) {
 105             dirty = false;
 106             QVector<T> sorted = values;
 107             qSort(sorted);
 108             currentMedian = sorted.at(bufferSize / 2 + 1);
 109         }
 110         return currentMedian;
 111     }
 112 private:
 113     QVector<T> values;
 114     T currentMedian;
 115     int bufferSize;
 116     int currentIndex;
 117     bool valid;
 118     bool dirty;
 119 };
 120
 121 } // namespace QtConcurrent
 122
 123 #endif //qdoc
 124
 125 QT_END_NAMESPACE
 126 QT_END_HEADER
 127
 128 #endif // QT_NO_CONCURRENT
 129
 130 #endif