1 /* 2 * Copyright (c) 2017 The WebRTC project authors. All Rights Reserved. 3 * 4 * Use of this source code is governed by a BSD-style license 5 * that can be found in the LICENSE file in the root of the source 6 * tree. An additional intellectual property rights grant can be found 7 * in the file PATENTS. All contributing project authors may 8 * be found in the AUTHORS file in the root of the source tree. 9 */ 10 11 #ifndef RTC_BASE_NUMERICS_MOVING_PERCENTILE_FILTER_H_ 12 #define RTC_BASE_NUMERICS_MOVING_PERCENTILE_FILTER_H_ 13 14 #include <stddef.h> 15 16 #include <cstddef> 17 #include <list> 18 19 #include "rtc_base/checks.h" 20 #include "rtc_base/numerics/percentile_filter.h" 21 22 namespace webrtc { 23 24 // Class to efficiently get moving percentile filter from a stream of samples. 25 template <typename T> 26 class MovingPercentileFilter { 27 public: 28 // Construct filter. `percentile` defines what percentile to track and 29 // `window_size` is how many latest samples are stored for finding the 30 // percentile. `percentile` must be between 0.0 and 1.0 (inclusive) and 31 // `window_size` must be greater than 0. 32 MovingPercentileFilter(float percentile, size_t window_size); 33 34 MovingPercentileFilter(const MovingPercentileFilter&) = delete; 35 MovingPercentileFilter& operator=(const MovingPercentileFilter&) = delete; 36 37 // Insert a new sample. 38 void Insert(const T& value); 39 40 // Removes all samples; 41 void Reset(); 42 43 // Get percentile over the latest window. 44 T GetFilteredValue() const; 45 46 // The number of samples that are currently stored. 47 size_t GetNumberOfSamplesStored() const; 48 49 private: 50 PercentileFilter<T> percentile_filter_; 51 std::list<T> samples_; 52 size_t samples_stored_; 53 const size_t window_size_; 54 }; 55 56 // Convenience type for the common median case. 57 template <typename T> 58 class MovingMedianFilter : public MovingPercentileFilter<T> { 59 public: MovingMedianFilter(size_t window_size)60 explicit MovingMedianFilter(size_t window_size) 61 : MovingPercentileFilter<T>(0.5f, window_size) {} 62 }; 63 64 template <typename T> MovingPercentileFilter(float percentile,size_t window_size)65MovingPercentileFilter<T>::MovingPercentileFilter(float percentile, 66 size_t window_size) 67 : percentile_filter_(percentile), 68 samples_stored_(0), 69 window_size_(window_size) { 70 RTC_CHECK_GT(window_size, 0); 71 } 72 73 template <typename T> Insert(const T & value)74void MovingPercentileFilter<T>::Insert(const T& value) { 75 percentile_filter_.Insert(value); 76 samples_.emplace_back(value); 77 ++samples_stored_; 78 if (samples_stored_ > window_size_) { 79 percentile_filter_.Erase(samples_.front()); 80 samples_.pop_front(); 81 --samples_stored_; 82 } 83 } 84 85 template <typename T> GetFilteredValue()86T MovingPercentileFilter<T>::GetFilteredValue() const { 87 return percentile_filter_.GetPercentileValue(); 88 } 89 90 template <typename T> Reset()91void MovingPercentileFilter<T>::Reset() { 92 percentile_filter_.Reset(); 93 samples_.clear(); 94 samples_stored_ = 0; 95 } 96 97 template <typename T> GetNumberOfSamplesStored()98size_t MovingPercentileFilter<T>::GetNumberOfSamplesStored() const { 99 return samples_stored_; 100 } 101 102 } // namespace webrtc 103 #endif // RTC_BASE_NUMERICS_MOVING_PERCENTILE_FILTER_H_ 104