Line data    Source code

       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 WEBRTC_BASE_NUMERICS_PERCENTILE_FILTER_H_
      12             : #define WEBRTC_BASE_NUMERICS_PERCENTILE_FILTER_H_
      13             : 
      14             : #include <stdint.h>
      15             : 
      16             : #include <iterator>
      17             : #include <set>
      18             : 
      19             : #include "webrtc/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           0 : 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             :  private:
      45             :   // Update iterator and index to point at target percentile value.
      46             :   void UpdatePercentileIterator();
      47             : 
      48             :   const float percentile_;
      49             :   std::multiset<T> set_;
      50             :   // Maintain iterator and index of current target percentile value.
      51             :   typename std::multiset<T>::iterator percentile_it_;
      52             :   int64_t percentile_index_;
      53             : };
      54             : 
      55             : template <typename T>
      56           0 : PercentileFilter<T>::PercentileFilter(float percentile)
      57             :     : percentile_(percentile),
      58             :       percentile_it_(set_.begin()),
      59           0 :       percentile_index_(0) {
      60           0 :   RTC_CHECK_GE(percentile, 0.0f);
      61           0 :   RTC_CHECK_LE(percentile, 1.0f);
      62           0 : }
      63             : 
      64             : template <typename T>
      65           0 : void PercentileFilter<T>::Insert(const T& value) {
      66             :   // Insert element at the upper bound.
      67           0 :   set_.insert(value);
      68           0 :   if (set_.size() == 1u) {
      69             :     // First element inserted - initialize percentile iterator and index.
      70           0 :     percentile_it_ = set_.begin();
      71           0 :     percentile_index_ = 0;
      72           0 :   } else if (value < *percentile_it_) {
      73             :     // If new element is before us, increment |percentile_index_|.
      74           0 :     ++percentile_index_;
      75             :   }
      76           0 :   UpdatePercentileIterator();
      77           0 : }
      78             : 
      79             : template <typename T>
      80           0 : bool PercentileFilter<T>::Erase(const T& value) {
      81           0 :   typename std::multiset<T>::const_iterator it = set_.lower_bound(value);
      82             :   // Ignore erase operation if the element is not present in the current set.
      83           0 :   if (it == set_.end() || *it != value)
      84           0 :     return false;
      85           0 :   if (it == percentile_it_) {
      86             :     // If same iterator, update to the following element. Index is not
      87             :     // affected.
      88           0 :     percentile_it_ = set_.erase(it);
      89             :   } else {
      90           0 :     set_.erase(it);
      91             :     // If erased element was before us, decrement |percentile_index_|.
      92           0 :     if (value <= *percentile_it_)
      93           0 :       --percentile_index_;
      94             :   }
      95           0 :   UpdatePercentileIterator();
      96           0 :   return true;
      97             : }
      98             : 
      99             : template <typename T>
     100           0 : void PercentileFilter<T>::UpdatePercentileIterator() {
     101           0 :   if (set_.empty())
     102           0 :     return;
     103           0 :   const int64_t index = static_cast<int64_t>(percentile_ * (set_.size() - 1));
     104           0 :   std::advance(percentile_it_, index - percentile_index_);
     105           0 :   percentile_index_ = index;
     106             : }
     107             : 
     108             : template <typename T>
     109           0 : T PercentileFilter<T>::GetPercentileValue() const {
     110           0 :   return set_.empty() ? 0 : *percentile_it_;
     111             : }
     112             : 
     113             : }  // namespace webrtc
     114             : 
     115             : #endif  // WEBRTC_BASE_NUMERICS_PERCENTILE_FILTER_H_