1 /* 2 * Copyright (c) 2016 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_PERCENTILE_FILTER_H_ 12 #define RTC_BASE_NUMERICS_PERCENTILE_FILTER_H_ 13 14 #include <stdint.h> 15 16 #include <iterator> 17 #include <set> 18 19 #include "rtc_base/checks.h" 20 21 namespace webrtc { 22 23 // Class to efficiently get the percentile value from a group of observations. 24 // The percentile is the value below which a given percentage of the 25 // observations fall. 26 template <typename T> 27 class PercentileFilter { 28 public: 29 // Construct filter. |percentile| should be between 0 and 1. 30 explicit PercentileFilter(float percentile); 31 32 // Insert one observation. The complexity of this operation is logarithmic in 33 // the size of the container. 34 void Insert(const T& value); 35 36 // Remove one observation or return false if |value| doesn't exist in the 37 // container. The complexity of this operation is logarithmic in the size of 38 // the container. 39 bool Erase(const T& value); 40 41 // Get the percentile value. The complexity of this operation is constant. 42 T GetPercentileValue() const; 43 44 // Removes all the stored observations. 45 void Reset(); 46 47 private: 48 // Update iterator and index to point at target percentile value. 49 void UpdatePercentileIterator(); 50 51 const float percentile_; 52 std::multiset<T> set_; 53 // Maintain iterator and index of current target percentile value. 54 typename std::multiset<T>::iterator percentile_it_; 55 int64_t percentile_index_; 56 }; 57 58 template <typename T> PercentileFilter(float percentile)59PercentileFilter<T>::PercentileFilter(float percentile) 60 : percentile_(percentile), 61 percentile_it_(set_.begin()), 62 percentile_index_(0) { 63 RTC_CHECK_GE(percentile, 0.0f); 64 RTC_CHECK_LE(percentile, 1.0f); 65 } 66 67 template <typename T> Insert(const T & value)68void PercentileFilter<T>::Insert(const T& value) { 69 // Insert element at the upper bound. 70 set_.insert(value); 71 if (set_.size() == 1u) { 72 // First element inserted - initialize percentile iterator and index. 73 percentile_it_ = set_.begin(); 74 percentile_index_ = 0; 75 } else if (value < *percentile_it_) { 76 // If new element is before us, increment |percentile_index_|. 77 ++percentile_index_; 78 } 79 UpdatePercentileIterator(); 80 } 81 82 template <typename T> Erase(const T & value)83bool PercentileFilter<T>::Erase(const T& value) { 84 typename std::multiset<T>::const_iterator it = set_.lower_bound(value); 85 // Ignore erase operation if the element is not present in the current set. 86 if (it == set_.end() || *it != value) 87 return false; 88 if (it == percentile_it_) { 89 // If same iterator, update to the following element. Index is not 90 // affected. 91 percentile_it_ = set_.erase(it); 92 } else { 93 set_.erase(it); 94 // If erased element was before us, decrement |percentile_index_|. 95 if (value <= *percentile_it_) 96 --percentile_index_; 97 } 98 UpdatePercentileIterator(); 99 return true; 100 } 101 102 template <typename T> UpdatePercentileIterator()103void PercentileFilter<T>::UpdatePercentileIterator() { 104 if (set_.empty()) 105 return; 106 const int64_t index = static_cast<int64_t>(percentile_ * (set_.size() - 1)); 107 std::advance(percentile_it_, index - percentile_index_); 108 percentile_index_ = index; 109 } 110 111 template <typename T> GetPercentileValue()112T PercentileFilter<T>::GetPercentileValue() const { 113 return set_.empty() ? 0 : *percentile_it_; 114 } 115 116 template <typename T> Reset()117void PercentileFilter<T>::Reset() { 118 set_.clear(); 119 percentile_it_ = set_.begin(); 120 percentile_index_ = 0; 121 } 122 } // namespace webrtc 123 124 #endif // RTC_BASE_NUMERICS_PERCENTILE_FILTER_H_ 125