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