rtc_base/numerics/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.
 */

#ifndef RTC_BASE_NUMERICS_PERCENTILE_FILTER_H_
#define RTC_BASE_NUMERICS_PERCENTILE_FILTER_H_

#include <stdint.h>

#include <iterator>
#include <set>

#include "rtc_base/checks.h"

namespace webrtc {

// 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 Insert(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;

  // Removes all the stored observations.
  void Reset();

 private:
  // Update iterator and index to point at target percentile value.
  void UpdatePercentileIterator();

  const float percentile_;
  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),
      percentile_it_(set_.begin()),
      percentile_index_(0) {
  RTC_CHECK_GE(percentile, 0.0f);
  RTC_CHECK_LE(percentile, 1.0f);
}

template <typename T>
void PercentileFilter<T>::Insert(const T& value) {
  // Insert element at the upper bound.
  set_.insert(value);
  if (set_.size() == 1u) {
    // First element inserted - initialize percentile iterator and index.
    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>
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 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_;
}

template <typename T>
void PercentileFilter<T>::Reset() {
  set_.clear();
  percentile_it_ = set_.begin();
  percentile_index_ = 0;
}
}  // namespace webrtc

#endif  // RTC_BASE_NUMERICS_PERCENTILE_FILTER_H_