chromium/base/moving_window.h

// Copyright 2023 The Chromium Authors
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#ifndef BASE_MOVING_WINDOW_H_
#define BASE_MOVING_WINDOW_H_

#include <math.h>
#include <stddef.h>

#include <cmath>
#include <functional>
#include <limits>
#include <vector>

#include "base/check_op.h"
#include "base/memory/raw_ref.h"
#include "base/time/time.h"

namespace base {

// Class to efficiently calculate statistics in a sliding window.
// This class isn't thread safe.
// Supported statistics are Min/Max/Mean/Deviation.
// You can also iterate through the items in the window.
// The class is modular: required features must be specified in the template
// arguments.
// Non listed features don't consume memory or runtime cycles at all.
//
// Usage:
// base::MovingWindow<int,
//                    base::MovingWindowFeatures::Min,
//                    base::MovingWindowFeatures::Max>
//                    moving_window(window_size);
//
// Following convenience shortcuts are provided with predefined sets of
// features:
// MovingMax/MovingMin/MovingAverage/MovingAverageDeviation/MovingMinMax.
//
// Methods:
// Constructor:
//   MovingWindow(size_t window_size);
//
// Window update (available for all templates):
//   AddSample(T value) const;
//   size_t Count() const;
//   void Reset();
//
// Available for MovingWindowFeatures::Min:
//    T Min() const;
//
// Available for MovingWindowFeatures::Max:
//    T Max() const;
//
// Available for MovingWindowFeatures::Mean:
//    U Mean<U>() const;
//
// Available for MovingWindowFeatures::Deviation:
//    U Deviation<U>() const;
//
// Available for MovingWindowFeatures::Iteration. Iterating through the window:
//    iterator begin() const;
//    iterator begin() const;
//    size_t size() const;

// Features supported by the class.
struct MovingWindowFeatures { … };

// Main template.
template <typename T, typename... Features>
class MovingWindow;

// Convenience shortcuts.
MovingMax;

MovingMin;

MovingMinMax;

MovingAverage;

MovingAverageDeviation;

namespace internal {

// Class responsible only for calculating maximum in the window.
// It's reused to calculate both min and max via inverting the comparator.
template <typename T, typename Comparator>
class MovingExtremumBase { … };

// Null implementation of the above class to be used when feature is disabled.
template <typename T>
struct NullExtremumImpl { … };

// Class to hold the moving window.
// It's used to calculate replaced element for Mean/Deviation calculations.
template <typename T>
class MovingWindowBase { … };

// Null implementation of the above class to be used when feature is disabled.
template <typename T>
struct NullWindowImpl { … };

// Performs division allowing the class to work with more types.
// General template.
template <typename SumType, typename ReturnType>
struct DivideInternal { … };

// Class to calculate moving mean.
template <typename T, typename SumType, bool IsFloating>
class MovingMeanBase { … };

// Class to calculate moving mean.
// Variant for float types with running sum to avoid rounding errors
// accumulation.
MovingMeanBase<T, SumType, true>;

// Null implementation of the above class to be used when feature is disabled.
template <typename T>
struct NullMeanImpl { … };

// Computs main Deviation fromula, allowing the class to work with more types.
// Deviation is equal to mean of squared values minus squared mean value.
// General template.
template <typename SumType, typename ReturnType>
struct DeivationInternal { … };

// Class to compute square of the number.
// General template
template <typename T, typename SquareType>
struct SquareInternal { … };

// Class to calculate moving deviation.
template <typename T, typename SumType, bool IsFloating>
class MovingDeviationBase { … };

// Class to calculate moving deviation.
// Variant for float types with running sum to avoid rounding errors
// accumulation.
MovingDeviationBase<T, SumType, true>;

// Null implementation of the above class to be used when feature is disabled.
template <typename T>
struct NullDeviationImpl { … };

// Template helpers.

// Gets all enabled features in one struct.
template <typename... Features>
struct EnabledFeatures : public Features... { … };

has_member_min;

has_member_max;

has_member_mean;

has_member_deviation;

has_member_iteration;

// Gets the type of the member if present.
// Can't just use decltype, because the member might be absent.
template <typename T>
struct get_type_mean { … };
get_type_mean<T>;
mean_t;

template <typename T>
struct get_type_deviation { … };
get_type_deviation<T>;
deviation_t;

// Performs division allowing the class to work with more types.
// Specific template for TimeDelta.
template <>
struct DivideInternal<TimeDelta, TimeDelta> { … };

// Computs main Deviation fromula, allowing the class to work with more types.
// Deviation is equal to mean of squared values minus squared mean value.
// Specific template for TimeDelta.
template <>
struct DeivationInternal<double, TimeDelta> { … };

// Class to compute square of the number.
// Specific template for TimeDelta.
template <>
struct SquareInternal<TimeDelta, double> { … };

}  // namespace internal

// Implementation of the main class.
template <typename T, typename... Features>
class MovingWindow { … };

}  // namespace base

#endif  // BASE_MOVING_WINDOW_H_