1/****************************************************************************
2**
3** Copyright (C) 2016 The Qt Company Ltd.
4** Contact: https://www.qt.io/licensing/
5**
6** This file is part of the QtConcurrent module of the Qt Toolkit.
7**
8** $QT_BEGIN_LICENSE:LGPL$
9** Commercial License Usage
10** Licensees holding valid commercial Qt licenses may use this file in
11** accordance with the commercial license agreement provided with the
12** Software or, alternatively, in accordance with the terms contained in
13** a written agreement between you and The Qt Company. For licensing terms
14** and conditions see https://www.qt.io/terms-conditions. For further
15** information use the contact form at https://www.qt.io/contact-us.
16**
17** GNU Lesser General Public License Usage
18** Alternatively, this file may be used under the terms of the GNU Lesser
19** General Public License version 3 as published by the Free Software
20** Foundation and appearing in the file LICENSE.LGPL3 included in the
21** packaging of this file. Please review the following information to
22** ensure the GNU Lesser General Public License version 3 requirements
23** will be met: https://www.gnu.org/licenses/lgpl-3.0.html.
24**
25** GNU General Public License Usage
26** Alternatively, this file may be used under the terms of the GNU
27** General Public License version 2.0 or (at your option) the GNU General
28** Public license version 3 or any later version approved by the KDE Free
29** Qt Foundation. The licenses are as published by the Free Software
30** Foundation and appearing in the file LICENSE.GPL2 and LICENSE.GPL3
31** included in the packaging of this file. Please review the following
32** information to ensure the GNU General Public License requirements will
33** be met: https://www.gnu.org/licenses/gpl-2.0.html and
34** https://www.gnu.org/licenses/gpl-3.0.html.
35**
36** $QT_END_LICENSE$
37**
38****************************************************************************/
39
40#ifndef QTCONCURRENT_MEDIAN_H
41#define QTCONCURRENT_MEDIAN_H
42
43#include <QtConcurrent/qtconcurrent_global.h>
44
45#if !defined(QT_NO_CONCURRENT) || defined(Q_CLANG_QDOC)
46
47#include <algorithm>
48#include <cstring>
49
50QT_BEGIN_NAMESPACE
51
52namespace QtConcurrent {
53
54class Median
55{
56public:
57 enum { BufferSize = 7 };
58
59 Median()
60 : currentMedian(), currentIndex(0), valid(false), dirty(true)
61 {
62 std::fill_n(values, static_cast<int>(BufferSize), 0.0);
63 }
64
65 void reset()
66 {
67 std::fill_n(values, static_cast<int>(BufferSize), 0.0);
68 currentIndex = 0;
69 valid = false;
70 dirty = true;
71 }
72
73 void addValue(double value)
74 {
75 ++currentIndex;
76 if (currentIndex == BufferSize) {
77 currentIndex = 0;
78 valid = true;
79 }
80
81 // Only update the cached median value when we have to, that
82 // is when the new value is on then other side of the median
83 // compared to the current value at the index.
84 const double currentIndexValue = values[currentIndex];
85 if ((currentIndexValue > currentMedian && currentMedian > value)
86 || (currentMedian > currentIndexValue && value > currentMedian)) {
87 dirty = true;
88 }
89
90 values[currentIndex] = value;
91 }
92
93 bool isMedianValid() const
94 {
95 return valid;
96 }
97
98 double median()
99 {
100 if (dirty) {
101 dirty = false;
102
103 double sorted[BufferSize];
104 ::memcpy(&sorted, &values, sizeof(sorted));
105 std::sort(sorted, sorted + static_cast<int>(BufferSize));
106 currentMedian = sorted[BufferSize / 2];
107 }
108
109 return currentMedian;
110 }
111
112private:
113 double values[BufferSize];
114 double currentMedian;
115 int currentIndex;
116 bool valid;
117 bool dirty;
118};
119
120} // namespace QtConcurrent
121
122QT_END_NAMESPACE
123
124#endif // QT_NO_CONCURRENT
125
126#endif
127