1/*
2 *  Copyright 2011 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_ROLLINGACCUMULATOR_H_
12#define WEBRTC_BASE_ROLLINGACCUMULATOR_H_
13
14#include <algorithm>
15#include <vector>
16
17#include "webrtc/base/common.h"
18
19namespace rtc {
20
21// RollingAccumulator stores and reports statistics
22// over N most recent samples.
23//
24// T is assumed to be an int, long, double or float.
25template<typename T>
26class RollingAccumulator {
27 public:
28  explicit RollingAccumulator(size_t max_count)
29    : samples_(max_count) {
30    Reset();
31  }
32  ~RollingAccumulator() {
33  }
34
35  size_t max_count() const {
36    return samples_.size();
37  }
38
39  size_t count() const {
40    return count_;
41  }
42
43  void Reset() {
44    count_ = 0U;
45    next_index_ = 0U;
46    sum_ = 0.0;
47    sum_2_ = 0.0;
48    max_ = T();
49    max_stale_ = false;
50    min_ = T();
51    min_stale_ = false;
52  }
53
54  void AddSample(T sample) {
55    if (count_ == max_count()) {
56      // Remove oldest sample.
57      T sample_to_remove = samples_[next_index_];
58      sum_ -= sample_to_remove;
59      sum_2_ -= sample_to_remove * sample_to_remove;
60      if (sample_to_remove >= max_) {
61        max_stale_ = true;
62      }
63      if (sample_to_remove <= min_) {
64        min_stale_ = true;
65      }
66    } else {
67      // Increase count of samples.
68      ++count_;
69    }
70    // Add new sample.
71    samples_[next_index_] = sample;
72    sum_ += sample;
73    sum_2_ += sample * sample;
74    if (count_ == 1 || sample >= max_) {
75      max_ = sample;
76      max_stale_ = false;
77    }
78    if (count_ == 1 || sample <= min_) {
79      min_ = sample;
80      min_stale_ = false;
81    }
82    // Update next_index_.
83    next_index_ = (next_index_ + 1) % max_count();
84  }
85
86  T ComputeSum() const {
87    return static_cast<T>(sum_);
88  }
89
90  double ComputeMean() const {
91    if (count_ == 0) {
92      return 0.0;
93    }
94    return sum_ / count_;
95  }
96
97  T ComputeMax() const {
98    if (max_stale_) {
99      ASSERT(count_ > 0 &&
100          "It shouldn't be possible for max_stale_ && count_ == 0");
101      max_ = samples_[next_index_];
102      for (size_t i = 1u; i < count_; i++) {
103        max_ = std::max(max_, samples_[(next_index_ + i) % max_count()]);
104      }
105      max_stale_ = false;
106    }
107    return max_;
108  }
109
110  T ComputeMin() const {
111    if (min_stale_) {
112      ASSERT(count_ > 0 &&
113          "It shouldn't be possible for min_stale_ && count_ == 0");
114      min_ = samples_[next_index_];
115      for (size_t i = 1u; i < count_; i++) {
116        min_ = std::min(min_, samples_[(next_index_ + i) % max_count()]);
117      }
118      min_stale_ = false;
119    }
120    return min_;
121  }
122
123  // O(n) time complexity.
124  // Weights nth sample with weight (learning_rate)^n. Learning_rate should be
125  // between (0.0, 1.0], otherwise the non-weighted mean is returned.
126  double ComputeWeightedMean(double learning_rate) const {
127    if (count_ < 1 || learning_rate <= 0.0 || learning_rate >= 1.0) {
128      return ComputeMean();
129    }
130    double weighted_mean = 0.0;
131    double current_weight = 1.0;
132    double weight_sum = 0.0;
133    const size_t max_size = max_count();
134    for (size_t i = 0; i < count_; ++i) {
135      current_weight *= learning_rate;
136      weight_sum += current_weight;
137      // Add max_size to prevent underflow.
138      size_t index = (next_index_ + max_size - i - 1) % max_size;
139      weighted_mean += current_weight * samples_[index];
140    }
141    return weighted_mean / weight_sum;
142  }
143
144  // Compute estimated variance.  Estimation is more accurate
145  // as the number of samples grows.
146  double ComputeVariance() const {
147    if (count_ == 0) {
148      return 0.0;
149    }
150    // Var = E[x^2] - (E[x])^2
151    double count_inv = 1.0 / count_;
152    double mean_2 = sum_2_ * count_inv;
153    double mean = sum_ * count_inv;
154    return mean_2 - (mean * mean);
155  }
156
157 private:
158  size_t count_;
159  size_t next_index_;
160  double sum_;    // Sum(x) - double to avoid overflow
161  double sum_2_;  // Sum(x*x) - double to avoid overflow
162  mutable T max_;
163  mutable bool max_stale_;
164  mutable T min_;
165  mutable bool min_stale_;
166  std::vector<T> samples_;
167
168  RTC_DISALLOW_COPY_AND_ASSIGN(RollingAccumulator);
169};
170
171}  // namespace rtc
172
173#endif  // WEBRTC_BASE_ROLLINGACCUMULATOR_H_
174