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 <QtCore/qvector.h>
48
49#include <algorithm>
50
51QT_BEGIN_NAMESPACE
52
53
54
55namespace QtConcurrent {
56
57template <typename T>
58class Median
59{
60public:
61 Median(int _bufferSize)
62 : currentMedian(), bufferSize(_bufferSize), currentIndex(0), valid(false), dirty(true)
63 {
64 values.resize(bufferSize);
65 }
66
67 void reset()
68 {
69 values.fill(0);
70 currentIndex = 0;
71 valid = false;
72 dirty = true;
73 }
74
75 void addValue(T value)
76 {
77 currentIndex = ((currentIndex + 1) % bufferSize);
78 if (valid == false && currentIndex % bufferSize == 0)
79 valid = true;
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 T 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 T median()
99 {
100 if (dirty) {
101 dirty = false;
102
103// This is a workaround for http://gcc.gnu.org/bugzilla/show_bug.cgi?id=58800
104// Avoid using std::nth_element for the affected stdlibc++ releases 4.7.3 and 4.8.2.
105// Note that the official __GLIBCXX__ value of the releases is not used since that
106// one might be patched on some GNU/Linux distributions.
107#if defined(__GLIBCXX__) && __GLIBCXX__ <= 20140107
108 QVector<T> sorted = values;
109 std::sort(sorted.begin(), sorted.end());
110 currentMedian = sorted.at(bufferSize / 2);
111#else
112 QVector<T> copy = values;
113 typename QVector<T>::iterator begin = copy.begin(), mid = copy.begin() + bufferSize/2, end = copy.end();
114 std::nth_element(begin, mid, end);
115 currentMedian = *mid;
116#endif
117 }
118 return currentMedian;
119 }
120private:
121 QVector<T> values;
122 T currentMedian;
123 int bufferSize;
124 int currentIndex;
125 bool valid;
126 bool dirty;
127};
128
129// ### Qt6: Drop Median<double> in favor of this faster MedianDouble
130class MedianDouble
131{
132public:
133 enum { BufferSize = 7 };
134
135 MedianDouble()
136 : currentMedian(), currentIndex(0), valid(false), dirty(true)
137 {
138 std::fill_n(first: values, n: static_cast<int>(BufferSize), value: 0.0);
139 }
140
141 void reset()
142 {
143 std::fill_n(first: values, n: static_cast<int>(BufferSize), value: 0.0);
144 currentIndex = 0;
145 valid = false;
146 dirty = true;
147 }
148
149 void addValue(double value)
150 {
151 ++currentIndex;
152 if (currentIndex == BufferSize) {
153 currentIndex = 0;
154 valid = true;
155 }
156
157 // Only update the cached median value when we have to, that
158 // is when the new value is on then other side of the median
159 // compared to the current value at the index.
160 const double currentIndexValue = values[currentIndex];
161 if ((currentIndexValue > currentMedian && currentMedian > value)
162 || (currentMedian > currentIndexValue && value > currentMedian)) {
163 dirty = true;
164 }
165
166 values[currentIndex] = value;
167 }
168
169 bool isMedianValid() const
170 {
171 return valid;
172 }
173
174 double median()
175 {
176 if (dirty) {
177 dirty = false;
178
179 double sorted[BufferSize];
180 ::memcpy(dest: &sorted, src: &values, n: sizeof(sorted));
181 std::sort(first: sorted, last: sorted + static_cast<int>(BufferSize));
182 currentMedian = sorted[BufferSize / 2];
183 }
184
185 return currentMedian;
186 }
187
188private:
189 double values[BufferSize];
190 double currentMedian;
191 int currentIndex;
192 bool valid;
193 bool dirty;
194};
195
196} // namespace QtConcurrent
197
198
199QT_END_NAMESPACE
200
201#endif // QT_NO_CONCURRENT
202
203#endif
204

source code of qtbase/src/concurrent/qtconcurrentmedian.h