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 | |
51 | QT_BEGIN_NAMESPACE |
52 | |
53 | |
54 | |
55 | namespace QtConcurrent { |
56 | |
57 | template <typename T> |
58 | class Median |
59 | { |
60 | public: |
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 | } |
120 | private: |
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 |
130 | class MedianDouble |
131 | { |
132 | public: |
133 | enum { BufferSize = 7 }; |
134 | |
135 | MedianDouble() |
136 | : currentMedian(), currentIndex(0), valid(false), dirty(true) |
137 | { |
138 | std::fill_n(values, static_cast<int>(BufferSize), 0.0); |
139 | } |
140 | |
141 | void reset() |
142 | { |
143 | std::fill_n(values, static_cast<int>(BufferSize), 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(&sorted, &values, sizeof(sorted)); |
181 | std::sort(sorted, sorted + static_cast<int>(BufferSize)); |
182 | currentMedian = sorted[BufferSize / 2]; |
183 | } |
184 | |
185 | return currentMedian; |
186 | } |
187 | |
188 | private: |
189 | double values[BufferSize]; |
190 | double currentMedian; |
191 | int currentIndex; |
192 | bool valid; |
193 | bool dirty; |
194 | }; |
195 | |
196 | } // namespace QtConcurrent |
197 | |
198 | |
199 | QT_END_NAMESPACE |
200 | |
201 | #endif // QT_NO_CONCURRENT |
202 | |
203 | #endif |
204 | |