Implement Theil-Sen's method for fitting a line to noisy data (used in bandwidth estimation).

webrtc/base/analytics/percentile_filter.h

Index: webrtc/base/analytics/percentile_filter.h
diff --git a/webrtc/base/analytics/percentile_filter.h b/webrtc/base/analytics/percentile_filter.h
index b3c8f8d1775f8df42b22b9a42d802ce454b9c1cb..d6b36aeb51a9ccafe5e18f267405eb96db969fac 100644
--- a/webrtc/base/analytics/percentile_filter.h
+++ b/webrtc/base/analytics/percentile_filter.h
@@ -33,13 +33,18 @@ class PercentileFilter {
   // the size of the container.
   void Insert(const T& value);
 
-  // Remove one observation. The complexity of this operation is logarithmic in
-  // the size of the container.
-  void Erase(const T& value);
+  // Remove one observation or return false if |value| doesn't exist in the
+  // container. The complexity of this operation is logarithmic in the size of
+  // the container.
+  bool Erase(const T& value);
 
   // Get the percentile value. The complexity of this operation is constant.
   T GetPercentileValue() const;
 
+  // Remove all observations from the container and reset the state to that of
+  // a newly contructed object.
+  void Clear();
+
  private:
   // Update iterator and index to point at target percentile value.
   void UpdatePercentileIterator();
@@ -76,11 +81,11 @@ void PercentileFilter<T>::Insert(const T& value) {
 }
 
 template <typename T>
-void PercentileFilter<T>::Erase(const T& value) {
+bool PercentileFilter<T>::Erase(const T& value) {
   typename std::multiset<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;
+    return false;
   if (it == percentile_it_) {
     // If same iterator, update to the following element. Index is not
     // affected.
@@ -92,6 +97,7 @@ void PercentileFilter<T>::Erase(const T& value) {
       --percentile_index_;
   }
   UpdatePercentileIterator();
+  return true;
 }
 
 template <typename T>
@@ -108,6 +114,13 @@ T PercentileFilter<T>::GetPercentileValue() const {
   return set_.empty() ? 0 : *percentile_it_;
 }
 
+template <typename T>
+void PercentileFilter<T>::Clear() {
+  set_.clear();
+  percentile_index_ = 0;
+  percentile_it_ = set_.begin();
+}
+
 }  // namespace webrtc
 
 #endif  // WEBRTC_BASE_ANALYTICS_PERCENTILE_FILTER_H_