1 // Copyright 2023 The Chromium Authors
2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file.
5 #ifndef BASE_MOVING_WINDOW_H_
6 #define BASE_MOVING_WINDOW_H_
16 #include "base/check_op.h"
17 #include "base/memory/raw_ref.h"
18 #include "base/time/time.h"
22 // Class to efficiently calculate statistics in a sliding window.
23 // This class isn't thread safe.
24 // Supported statistics are Min/Max/Mean/Deviation.
25 // You can also iterate through the items in the window.
26 // The class is modular: required features must be specified in the template
28 // Non listed features don't consume memory or runtime cycles at all.
31 // base::MovingWindow<int,
32 // base::MovingWindowFeatures::Min,
33 // base::MovingWindowFeatures::Max>
34 // moving_window(window_size);
36 // Following convenience shortcuts are provided with predefined sets of
38 // MovingMax/MovingMin/MovingAverage/MovingAverageDeviation/MovingMinMax.
42 // MovingWindow(size_t window_size);
44 // Window update (available for all templates):
45 // AddSample(T value) const;
46 // size_t Count() const;
49 // Available for MovingWindowFeatures::Min:
52 // Available for MovingWindowFeatures::Max:
55 // Available for MovingWindowFeatures::Mean:
58 // Available for MovingWindowFeatures::Deviation:
59 // U Deviation<U>() const;
61 // Available for MovingWindowFeatures::Iteration. Iterating through the window:
62 // iterator begin() const;
63 // iterator begin() const;
64 // size_t size() const;
66 // Features supported by the class.
67 struct MovingWindowFeatures {
76 // Need to specify a type capable of holding a sum of all elements in the
78 template <typename SumType>
80 static SumType has_mean;
83 // Need to specify a type capable of holding a sum of squares of all elements
85 template <typename SumType>
87 static SumType has_deviation;
91 static bool has_iteration;
96 template <typename T, typename... Features>
99 // Convenience shortcuts.
100 template <typename T>
101 using MovingMax = MovingWindow<T, MovingWindowFeatures::Max>;
103 template <typename T>
104 using MovingMin = MovingWindow<T, MovingWindowFeatures::Min>;
106 template <typename T>
108 MovingWindow<T, MovingWindowFeatures::Min, MovingWindowFeatures::Max>;
110 template <typename T, typename SumType>
111 using MovingAverage = MovingWindow<T, MovingWindowFeatures::Mean<SumType>>;
113 template <typename T>
114 using MovingAverageDeviation =
116 MovingWindowFeatures::Mean<T>,
117 MovingWindowFeatures::Deviation<double>>;
121 // Class responsible only for calculating maximum in the window.
122 // It's reused to calculate both min and max via inverting the comparator.
123 template <typename T, typename Comparator>
124 class MovingExtremumBase {
126 explicit MovingExtremumBase(size_t window_size)
127 : window_size_(window_size),
128 values_(window_size),
129 added_at_(window_size),
130 last_idx_(window_size - 1),
131 compare_(Comparator()) {}
132 ~MovingExtremumBase() = default;
134 // Add new sample to the stream.
135 void AddSample(const T& value, size_t total_added) {
136 // Remove old elements from the back of the window;
137 while (size_ > 0 && added_at_[begin_idx_] + window_size_ <= total_added) {
139 if (begin_idx_ == window_size_) {
144 // Remove small elements from the front of the window because they can never
145 // become the maximum in the window since the currently added element is
146 // bigger than them and will leave the window later.
147 while (size_ > 0 && compare_(values_[last_idx_], value)) {
148 if (last_idx_ == 0) {
149 last_idx_ = window_size_;
154 DCHECK_LT(size_, window_size_);
156 if (last_idx_ == window_size_) {
159 values_[last_idx_] = value;
160 added_at_[last_idx_] = total_added;
164 // Get the maximum of the last `window_size` elements.
166 DCHECK_GT(size_, 0u);
167 return values_[begin_idx_];
170 // Clear all samples.
174 last_idx_ = window_size_ - 1;
178 const size_t window_size_;
179 // Circular buffer with some values in the window.
180 // Only possible candidates for maximum are stored:
181 // values form a non-increasing sequence.
182 std::vector<T> values_;
183 // Circular buffer storing when numbers in `values_` were added.
184 std::vector<size_t> added_at_;
185 // Begin of the circular buffers above.
186 size_t begin_idx_ = 0;
187 // Last occupied position.
189 // How many elements are stored in the circular buffers above.
191 // Template parameter comparator.
192 const Comparator compare_;
195 // Null implementation of the above class to be used when feature is disabled.
196 template <typename T>
197 struct NullExtremumImpl {
198 explicit NullExtremumImpl(size_t) {}
199 ~NullExtremumImpl() = default;
200 void AddSample(const T&, size_t) {}
204 // Class to hold the moving window.
205 // It's used to calculate replaced element for Mean/Deviation calculations.
206 template <typename T>
207 class MovingWindowBase {
209 explicit MovingWindowBase(size_t window_size) : values_(window_size) {}
211 ~MovingWindowBase() = default;
213 void AddSample(const T& sample) {
214 values_[cur_idx_] = sample;
216 if (cur_idx_ == values_.size()) {
221 // Is the window filled integer amount of times.
222 bool IsLastIdx() const { return cur_idx_ + 1 == values_.size(); }
226 std::fill(values_.begin(), values_.end(), T());
229 T GetValue() const { return values_[cur_idx_]; }
231 T operator[](size_t idx) const { return values_[idx]; }
233 size_t Size() const { return values_.size(); }
235 // What index will be overwritten by a new element;
236 size_t CurIdx() const { return cur_idx_; }
240 std::vector<T> values_;
241 // Where the buffer begins.
245 // Null implementation of the above class to be used when feature is disabled.
246 template <typename T>
247 struct NullWindowImpl {
248 explicit NullWindowImpl(size_t) {}
249 ~NullWindowImpl() = default;
250 void AddSample(const T& sample) {}
251 bool IsLastIdx() const { return false; }
253 T GetValue() const { return T(); }
256 // Performs division allowing the class to work with more types.
258 template <typename SumType, typename ReturnType>
259 struct DivideInternal {
260 static ReturnType Compute(const SumType& sum, const size_t count) {
261 return static_cast<ReturnType>(sum) / static_cast<ReturnType>(count);
265 // Class to calculate moving mean.
266 template <typename T, typename SumType, bool IsFloating>
267 class MovingMeanBase {
269 explicit MovingMeanBase(size_t window_size) : sum_() {}
271 ~MovingMeanBase() = default;
273 void AddSample(const T& sample, const T& replaced_value, bool is_last_idx) {
274 sum_ += sample - replaced_value;
277 template <typename ReturnType = SumType>
278 ReturnType Mean(const size_t count) const {
282 return DivideInternal<SumType, ReturnType>::Compute(sum_, count);
284 void Reset() { sum_ = SumType(); }
286 SumType Sum() const { return sum_; }
292 // Class to calculate moving mean.
293 // Variant for float types with running sum to avoid rounding errors
295 template <typename T, typename SumType>
296 class MovingMeanBase<T, SumType, true> {
298 explicit MovingMeanBase(size_t window_size) : sum_(), running_sum_() {}
300 ~MovingMeanBase() = default;
302 void AddSample(const T& sample, const T& replaced_value, bool is_last_idx) {
303 running_sum_ += sample;
305 // Replace sum with running sum to avoid rounding errors accumulation.
307 running_sum_ = SumType();
309 sum_ += sample - replaced_value;
313 template <typename ReturnType = SumType>
314 ReturnType Mean(const size_t count) const {
318 return DivideInternal<SumType, ReturnType>::Compute(sum_, count);
321 void Reset() { sum_ = running_sum_ = SumType(); }
323 SumType Sum() const { return sum_; }
327 SumType running_sum_;
330 // Null implementation of the above class to be used when feature is disabled.
331 template <typename T>
332 struct NullMeanImpl {
333 explicit NullMeanImpl(size_t window_size) {}
334 ~NullMeanImpl() = default;
336 void AddSample(const T& sample, const T&, bool) {}
341 // Computs main Deviation fromula, allowing the class to work with more types.
342 // Deviation is equal to mean of squared values minus squared mean value.
344 template <typename SumType, typename ReturnType>
345 struct DeivationInternal {
346 static ReturnType Compute(const SumType& sum_squares,
347 const SumType& square_of_sum,
348 const size_t count) {
349 return static_cast<ReturnType>(
350 std::sqrt((static_cast<double>(sum_squares) -
351 static_cast<double>(square_of_sum) / count) /
356 // Class to compute square of the number.
358 template <typename T, typename SquareType>
359 struct SquareInternal {
360 static SquareType Compute(const T& sample) {
361 return static_cast<SquareType>(sample) * sample;
365 // Class to calculate moving deviation.
366 template <typename T, typename SumType, bool IsFloating>
367 class MovingDeviationBase {
369 explicit MovingDeviationBase(size_t window_size) : sum_sq_() {}
370 ~MovingDeviationBase() = default;
371 void AddSample(const T& sample, const T& replaced_value, bool is_last_idx) {
372 sum_sq_ += SquareInternal<T, SumType>::Compute(sample) -
373 SquareInternal<T, SumType>::Compute(replaced_value);
376 template <typename ReturnType, typename U>
377 ReturnType Deviation(const size_t count, const U& sum) const {
381 return DeivationInternal<SumType, ReturnType>::Compute(
382 sum_sq_, SquareInternal<U, SumType>::Compute(sum), count);
384 void Reset() { sum_sq_ = SumType(); }
390 // Class to calculate moving deviation.
391 // Variant for float types with running sum to avoid rounding errors
393 template <typename T, typename SumType>
394 class MovingDeviationBase<T, SumType, true> {
396 explicit MovingDeviationBase(size_t window_size)
397 : sum_sq_(), running_sum_() {}
398 ~MovingDeviationBase() = default;
399 void AddSample(const T& sample, const T& replaced_value, bool is_last_idx) {
400 SumType square = SquareInternal<T, SumType>::Compute(sample);
401 running_sum_ += square;
403 // Replace sum with running sum to avoid rounding errors accumulation.
404 sum_sq_ = running_sum_;
405 running_sum_ = SumType();
407 sum_sq_ += square - SquareInternal<T, SumType>::Compute(replaced_value);
411 template <typename ReturnType, typename U>
412 ReturnType Deviation(const size_t count, const U& sum) const {
416 return DeivationInternal<SumType, ReturnType>::Compute(
417 sum_sq_, SquareInternal<U, SumType>::Compute(sum), count);
419 void Reset() { running_sum_ = sum_sq_ = SumType(); }
423 SumType running_sum_;
426 // Null implementation of the above class to be used when feature is disabled.
427 template <typename T>
428 struct NullDeviationImpl {
430 explicit NullDeviationImpl(size_t window_size) {}
431 ~NullDeviationImpl() = default;
432 void AddSample(const T&, const T&, bool) {}
438 // Gets all enabled features in one struct.
439 template <typename... Features>
440 struct EnabledFeatures : public Features... {};
442 // Checks if specific member is present.
443 template <typename T, typename = void>
444 struct has_member_min : std::false_type {};
445 template <typename T>
446 struct has_member_min<T, decltype((void)T::has_min, void())> : std::true_type {
449 template <typename T, typename = void>
450 struct has_member_max : std::false_type {};
451 template <typename T>
452 struct has_member_max<T, decltype((void)T::has_max, void())> : std::true_type {
455 template <typename T, typename = void>
456 struct has_member_mean : std::false_type {};
457 template <typename T>
458 struct has_member_mean<T, decltype((void)T::has_mean, void())>
461 template <typename T, typename = void>
462 struct has_memeber_deviation : std::false_type {};
463 template <typename T>
464 struct has_memeber_deviation<T, decltype((void)T::has_deviation, void())>
467 template <typename T, typename = void>
468 struct has_member_iteration : std::false_type {};
469 template <typename T>
470 struct has_member_iteration<T, decltype((void)T::has_iteration, void())>
473 // Gets the type of the member if present.
474 // Can't just use decltype, because the member might be absent.
475 template <typename T, typename = void>
476 struct get_type_mean {
479 template <typename T>
480 struct get_type_mean<T, decltype((void)T::has_mean, void())> {
481 typedef decltype(T::has_mean) type;
484 template <typename T, typename = void>
485 struct get_type_deviation {
488 template <typename T>
489 struct get_type_deviation<T, decltype((void)T::has_deviation, void())> {
490 typedef decltype(T::has_deviation) type;
493 // Performs division allowing the class to work with more types.
494 // Specific template for TimeDelta.
496 struct DivideInternal<TimeDelta, TimeDelta> {
497 static TimeDelta Compute(const TimeDelta& sum, const size_t count) {
502 // Computs main Deviation fromula, allowing the class to work with more types.
503 // Deviation is equal to mean of squared values minus squared mean value.
504 // Specific template for TimeDelta.
506 struct DeivationInternal<double, TimeDelta> {
507 static TimeDelta Compute(const double sum_squares,
508 const double square_of_sum,
509 const size_t count) {
510 return Seconds(std::sqrt((sum_squares - square_of_sum / count) / count));
514 // Class to compute square of the number.
515 // Specific template for TimeDelta.
517 struct SquareInternal<TimeDelta, double> {
518 static double Compute(const TimeDelta& sample) {
519 return sample.InSecondsF() * sample.InSecondsF();
523 } // namespace internal
525 // Implementation of the main class.
526 template <typename T, typename... Features>
529 // List of all requested features.
530 using EnabledFeatures = internal::EnabledFeatures<Features...>;
532 explicit MovingWindow(size_t window_size)
533 : min_impl_(window_size),
534 max_impl_(window_size),
535 mean_impl_(window_size),
536 deviation_impl_(window_size),
537 window_impl_(window_size) {}
539 // Adds sample to the window.
540 void AddSample(const T& sample) {
542 min_impl_.AddSample(sample, total_added_);
543 max_impl_.AddSample(sample, total_added_);
544 mean_impl_.AddSample(sample, window_impl_.GetValue(),
545 window_impl_.IsLastIdx());
546 deviation_impl_.AddSample(sample, window_impl_.GetValue(),
547 window_impl_.IsLastIdx());
548 window_impl_.AddSample(sample);
551 // Returns amount of elementes so far in the stream (might be bigger than the
553 size_t Count() const { return total_added_; }
555 // Calculates min in the window. Template to disable when feature isn't
557 template <typename U = EnabledFeatures,
558 std::enable_if_t<internal::has_member_min<U>::value, int> = 0>
560 return min_impl_.Value();
563 // Calculates max in the window. Template to disable when feature isn't
565 template <typename U = EnabledFeatures,
566 std::enable_if_t<internal::has_member_max<U>::value, int> = 0>
568 return max_impl_.Value();
571 // Calculates mean in the window. Template to disable when feature isn't
573 template <typename ReturnType = T,
574 typename U = EnabledFeatures,
575 std::enable_if_t<internal::has_member_mean<U>::value, int> = 0>
576 ReturnType Mean() const {
577 return mean_impl_.template Mean<ReturnType>(
578 std::min(total_added_, window_impl_.Size()));
581 // Calculates deviation in the window. Template to disable when feature isn't
584 typename ReturnType = T,
585 typename U = EnabledFeatures,
586 std::enable_if_t<internal::has_memeber_deviation<U>::value, int> = 0>
587 ReturnType Deviation() const {
588 const size_t count = std::min(total_added_, window_impl_.Size());
589 return deviation_impl_.template Deviation<ReturnType>(count,
593 // Resets the state to an empty window.
598 deviation_impl_.Reset();
599 window_impl_.Reset();
603 // iterator implementation.
606 ~iterator() = default;
608 const T operator*() {
609 DCHECK_LT(idx_, window_impl_->Size());
610 return (*window_impl_)[idx_];
613 iterator& operator++() {
615 // Wrap around the circular buffer.
616 if (idx_ == window_impl_->Size()) {
619 // The only way to arrive to the current element is to
620 // come around after iterating through the whole window.
621 if (idx_ == window_impl_->CurIdx()) {
622 idx_ = kInvalidIndex;
627 bool operator==(const iterator& other) const { return idx_ == other.idx_; }
630 iterator(const internal::MovingWindowBase<T>& window, size_t idx)
631 : window_impl_(window), idx_(idx) {}
633 static const size_t kInvalidIndex = std::numeric_limits<size_t>::max();
635 raw_ref<const internal::MovingWindowBase<T>> window_impl_;
638 friend class MovingWindow<T, Features...>;
641 // Begin iterator. Template to enable only if iteration feature is requested.
642 template <typename U = EnabledFeatures,
643 std::enable_if_t<internal::has_member_iteration<U>::value, int> = 0>
644 iterator begin() const {
645 if (total_added_ == 0) {
648 // Before window is fully filled, the oldest element is at the index 0.
650 (total_added_ < window_impl_.Size()) ? 0 : window_impl_.CurIdx();
652 return iterator(window_impl_, idx);
655 // End iterator. Template to enable only if iteration feature is requested.
656 template <typename U = EnabledFeatures,
657 std::enable_if_t<internal::has_member_iteration<U>::value, int> = 0>
658 iterator end() const {
659 return iterator(window_impl_, iterator::kInvalidIndex);
662 // Size of the collection. Template to enable only if iteration feature is
664 template <typename U = EnabledFeatures,
665 std::enable_if_t<internal::has_member_iteration<U>::value, int> = 0>
666 size_t size() const {
667 return std::min(total_added_, window_impl_.Size());
671 // Member for calculating min.
672 // Conditionally enabled on Min feature.
673 typename std::conditional<internal::has_member_min<EnabledFeatures>::value,
674 internal::MovingExtremumBase<T, std::greater<T>>,
675 internal::NullExtremumImpl<T>>::type min_impl_;
677 // Member for calculating min.
678 // Conditionally enabled on Min feature.
679 typename std::conditional<internal::has_member_max<EnabledFeatures>::value,
680 internal::MovingExtremumBase<T, std::less<T>>,
681 internal::NullExtremumImpl<T>>::type max_impl_;
683 // Type for sum value in Mean implementation. Might need to reuse deviation
684 // sum type, because enabling only deviation feature will also enable mean
685 // member (because deviation calculation depends on mean calculation).
686 using MeanSumType = typename std::conditional<
687 internal::has_member_mean<EnabledFeatures>::value,
688 typename internal::get_type_mean<EnabledFeatures>::type,
689 typename internal::get_type_deviation<EnabledFeatures>::type>::type;
690 // Member for calculating mean.
691 // Conditionally enabled on Mean or Deviation feature (because deviation
692 // calculation depends on mean calculation).
693 typename std::conditional<
694 internal::has_member_mean<EnabledFeatures>::value ||
695 internal::has_memeber_deviation<EnabledFeatures>::value,
697 MovingMeanBase<T, MeanSumType, std::is_floating_point_v<MeanSumType>>,
698 internal::NullMeanImpl<T>>::type mean_impl_;
700 // Member for calculating deviation.
701 // Conditionally enabled on Deviation feature.
702 typename std::conditional<
703 internal::has_memeber_deviation<EnabledFeatures>::value,
704 internal::MovingDeviationBase<
706 typename internal::get_type_deviation<EnabledFeatures>::type,
707 std::is_floating_point_v<
708 typename internal::get_type_deviation<EnabledFeatures>::type>>,
709 internal::NullDeviationImpl<T>>::type deviation_impl_;
711 // Member for storing the moving window.
712 // Conditionally enabled on Mean, Deviation or Iteration feature since
713 // they need the elements in the window.
714 // Min and Max features store elements internally so they don't need this.
715 typename std::conditional<
716 internal::has_member_mean<EnabledFeatures>::value ||
717 internal::has_memeber_deviation<EnabledFeatures>::value ||
718 internal::has_member_iteration<EnabledFeatures>::value,
719 internal::MovingWindowBase<T>,
720 internal::NullWindowImpl<T>>::type window_impl_;
721 // Total number of added elements.
722 size_t total_added_ = 0;
727 #endif // BASE_MOVING_WINDOW_H_