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