Templatize percentile_filter.h and move it to base/analytics.

webrtc/base/analytics/percentile_filter.h

Index: webrtc/base/analytics/percentile_filter.h
diff --git a/webrtc/modules/video_coding/percentile_filter.cc b/webrtc/base/analytics/percentile_filter.h
similarity index 33%
rename from webrtc/modules/video_coding/percentile_filter.cc
rename to webrtc/base/analytics/percentile_filter.h
index 6495567540961c86a721b58de9ba99a51694973e..d730669cf0dcc889aab570d1422c09545296866e 100644
--- a/webrtc/modules/video_coding/percentile_filter.cc
+++ b/webrtc/base/analytics/percentile_filter.h
@@ -8,25 +8,71 @@
  *  be found in the AUTHORS file in the root of the source tree.
  */
 
-#include "webrtc/modules/video_coding/percentile_filter.h"
+#ifndef WEBRTC_BASE_ANALYTICS_PERCENTILE_FILTER_H_
+#define WEBRTC_BASE_ANALYTICS_PERCENTILE_FILTER_H_
+
+#include <stdint.h>
 
 #include <iterator>
+#include <list>
+#include <set>
 
 #include "webrtc/base/checks.h"
 
 namespace webrtc {
 
-PercentileFilter::PercentileFilter(float percentile)
+// Class to efficiently get the percentile value from a group of observations.
+// The percentile is the value below which a given percentage of the
+// observations fall.
+template <typename T>
+class PercentileFilter {
+ public:
+  // Construct filter. |percentile| should be between 0 and 1.
+  explicit PercentileFilter(float percentile);
+
+  // Insert one observation. The complexity of this operation is logarithmic in
+  // the size of the container.
+  void Push(const T& value);
+
+  // Remove the oldest observation. The complexity of this operation is
+  // logarithmic in the size of the container.
+  void Pop();
+
+  // Get the percentile value. The complexity of this operation is constant.
+  T GetPercentileValue() const;
+
+  // Returns the number of observations in the container.
+  size_t Size() const;
+
+ private:
+  // Update iterator and index to point at target percentile value.
+  void UpdatePercentileIterator();
+
+  const float percentile_;
+  std::list<typename std::multiset<T>::iterator> history_;

[magjed_webrtc, 2016/11/30 10:58:25]

An std::queue seems more appropriate. Any reason for not using a queue (e.g.
generated binary size will be bigger)?

+  std::multiset<T> set_;
+  // Maintain iterator and index of current target percentile value.
+  typename std::multiset<T>::iterator percentile_it_;
+  int64_t percentile_index_;
+};
+
+template <typename T>
+PercentileFilter<T>::PercentileFilter(float percentile)
     : percentile_(percentile),
+      history_(),
+      set_(),
       percentile_it_(set_.begin()),
       percentile_index_(0) {
   RTC_CHECK_GE(percentile, 0.0f);
   RTC_CHECK_LE(percentile, 1.0f);
 }
 
-void PercentileFilter::Insert(const int64_t& value) {
-  // Insert element at the upper bound.
-  set_.insert(value);
+template <typename T>
+void PercentileFilter<T>::Push(const T& value) {
+  // Insert element at the upper bound. This means that each range of equal
+  // elements will be stored in the same order that they were inserted.
+  auto it = set_.insert(value);
+  history_.push_back(it);
   if (set_.size() == 1u) {
     // First element inserted - initialize percentile iterator and index.
     percentile_it_ = set_.begin();
@@ -38,24 +84,31 @@ void PercentileFilter::Insert(const int64_t& value) {
   UpdatePercentileIterator();
 }
 
-void PercentileFilter::Erase(const int64_t& value) {
-  std::multiset<int64_t>::const_iterator it = set_.lower_bound(value);
-  // Ignore erase operation if the element is not present in the current set.
-  if (it == set_.end() || *it != value)
-    return;
+template <typename T>
+void PercentileFilter<T>::Pop() {
+  RTC_DCHECK_GT(history_.size(), 0);

[magjed_webrtc, 2016/11/30 10:58:25]

nit: I think this is cleaner and will give the same information:
RTC_DCHECK(!history_.empty());

+  RTC_DCHECK_GT(set_.size(), 0);
+  auto it = history_.front();
+  history_.pop_front();
   if (it == percentile_it_) {
-    // If same iterator, update to the following element. Index is not affected.
-    percentile_it_ = set_.erase(it);
+    // If removing the percentile value, update iterator to the following
+    // element. Index is not affected.
+    percentile_it_ = set_.erase(percentile_it_);
   } else {
-    set_.erase(it);
-    // If erased element was before us, decrement |percentile_index_|.
-    if (value <= *percentile_it_)
+    // If erased element is before percentile, decrement |percentile_index_|.
+    // Note that if the erased element compares equal to the percentile, but
+    // isn't the same iterator, then it has to be before the |percentile_index_|
+    // since each range of equal elements is stored in insertion order and we
+    // are erasing the oldest element.
+    if (*it <= *percentile_it_)
       --percentile_index_;
+    set_.erase(it);
   }
   UpdatePercentileIterator();
 }
 
-void PercentileFilter::UpdatePercentileIterator() {
+template <typename T>
+void PercentileFilter<T>::UpdatePercentileIterator() {
   if (set_.empty())
     return;
   const int64_t index = static_cast<int64_t>(percentile_ * (set_.size() - 1));
@@ -63,8 +116,17 @@ void PercentileFilter::UpdatePercentileIterator() {
   percentile_index_ = index;
 }
 
-int64_t PercentileFilter::GetPercentileValue() const {
+template <typename T>
+T PercentileFilter<T>::GetPercentileValue() const {
   return set_.empty() ? 0 : *percentile_it_;
 }
 
+template <typename T>
+size_t PercentileFilter<T>::Size() const {
+  RTC_DCHECK_EQ(set_.size(), history_.size());
+  return history_.size();
+}
+
 }  // namespace webrtc
+
+#endif  // WEBRTC_BASE_ANALYTICS_PERCENTILE_FILTER_H_