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

webrtc/base/analytics/percentile_filter.h

 /*
  *  Copyright (c) 2016 The WebRTC project authors. All Rights Reserved.
  *
  *  Use of this source code is governed by a BSD-style license
  *  that can be found in the LICENSE file in the root of the source
  *  tree. An additional intellectual property rights grant can be found
  *  in the file PATENTS.  All contributing project authors may
  *  be found in the AUTHORS file in the root of the source tree.
  */
 
@@ skipping 15 matching lines @@
 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 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;
 
  private:
   // Update iterator and index to point at target percentile value.
   void UpdatePercentileIterator();
 
   const float percentile_;
   std::multiset<T> set_;
@@ skipping 20 matching lines @@
     percentile_it_ = set_.begin();
     percentile_index_ = 0;
   } else if (value < *percentile_it_) {
     // If new element is before us, increment |percentile_index_|.
     ++percentile_index_;
   }
   UpdatePercentileIterator();
 }
 
 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.
     percentile_it_ = set_.erase(it);
   } else {
     set_.erase(it);
     // If erased element was before us, decrement |percentile_index_|.
     if (value <= *percentile_it_)
       --percentile_index_;
   }
   UpdatePercentileIterator();
+  return true;
 }
 
 template <typename T>
 void PercentileFilter<T>::UpdatePercentileIterator() {
   if (set_.empty())
     return;
   const int64_t index = static_cast<int64_t>(percentile_ * (set_.size() - 1));
   std::advance(percentile_it_, index - percentile_index_);
   percentile_index_ = index;
 }
 
 template <typename T>
 T PercentileFilter<T>::GetPercentileValue() const {
   return set_.empty() ? 0 : *percentile_it_;
 }
 
 }  // namespace webrtc
 
 #endif  // WEBRTC_BASE_ANALYTICS_PERCENTILE_FILTER_H_