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)59 PercentileFilter<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)68 void 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)83 bool 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()103 void 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()112 T PercentileFilter<T>::GetPercentileValue() const {
113   return set_.empty() ? 0 : *percentile_it_;
114 }
115 
116 template <typename T>
Reset()117 void 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