1/*
2 * libjingle
3 * Copyright 2011, Google Inc.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions are met:
7 *
8 *  1. Redistributions of source code must retain the above copyright notice,
9 *     this list of conditions and the following disclaimer.
10 *  2. Redistributions in binary form must reproduce the above copyright notice,
11 *     this list of conditions and the following disclaimer in the documentation
12 *     and/or other materials provided with the distribution.
13 *  3. The name of the author may not be used to endorse or promote products
14 *     derived from this software without specific prior written permission.
15 *
16 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR IMPLIED
17 * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
18 * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO
19 * EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
20 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
21 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS;
22 * OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
23 * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
24 * OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
25 * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
26 */
27
28#ifndef TALK_BASE_ROLLINGACCUMULATOR_H_
29#define TALK_BASE_ROLLINGACCUMULATOR_H_
30
31#include <vector>
32
33#include "talk/base/common.h"
34
35namespace talk_base {
36
37// RollingAccumulator stores and reports statistics
38// over N most recent samples.
39//
40// T is assumed to be an int, long, double or float.
41template<typename T>
42class RollingAccumulator {
43 public:
44  explicit RollingAccumulator(size_t max_count)
45    : samples_(max_count) {
46    Reset();
47  }
48  ~RollingAccumulator() {
49  }
50
51  size_t max_count() const {
52    return samples_.size();
53  }
54
55  size_t count() const {
56    return count_;
57  }
58
59  void Reset() {
60    count_ = 0U;
61    next_index_ = 0U;
62    sum_ = 0.0;
63    sum_2_ = 0.0;
64    max_ = T();
65    max_stale_ = false;
66    min_ = T();
67    min_stale_ = false;
68  }
69
70  void AddSample(T sample) {
71    if (count_ == max_count()) {
72      // Remove oldest sample.
73      T sample_to_remove = samples_[next_index_];
74      sum_ -= sample_to_remove;
75      sum_2_ -= sample_to_remove * sample_to_remove;
76      if (sample_to_remove >= max_) {
77        max_stale_ = true;
78      }
79      if (sample_to_remove <= min_) {
80        min_stale_ = true;
81      }
82    } else {
83      // Increase count of samples.
84      ++count_;
85    }
86    // Add new sample.
87    samples_[next_index_] = sample;
88    sum_ += sample;
89    sum_2_ += sample * sample;
90    if (count_ == 1 || sample >= max_) {
91      max_ = sample;
92      max_stale_ = false;
93    }
94    if (count_ == 1 || sample <= min_) {
95      min_ = sample;
96      min_stale_ = false;
97    }
98    // Update next_index_.
99    next_index_ = (next_index_ + 1) % max_count();
100  }
101
102  T ComputeSum() const {
103    return static_cast<T>(sum_);
104  }
105
106  double ComputeMean() const {
107    if (count_ == 0) {
108      return 0.0;
109    }
110    return sum_ / count_;
111  }
112
113  T ComputeMax() const {
114    if (max_stale_) {
115      ASSERT(count_ > 0 &&
116          "It shouldn't be possible for max_stale_ && count_ == 0");
117      max_ = samples_[next_index_];
118      for (size_t i = 1u; i < count_; i++) {
119        max_ = _max(max_, samples_[(next_index_ + i) % max_count()]);
120      }
121      max_stale_ = false;
122    }
123    return max_;
124  }
125
126  T ComputeMin() const {
127    if (min_stale_) {
128      ASSERT(count_ > 0 &&
129          "It shouldn't be possible for min_stale_ && count_ == 0");
130      min_ = samples_[next_index_];
131      for (size_t i = 1u; i < count_; i++) {
132        min_ = _min(min_, samples_[(next_index_ + i) % max_count()]);
133      }
134      min_stale_ = false;
135    }
136    return min_;
137  }
138
139  // O(n) time complexity.
140  // Weights nth sample with weight (learning_rate)^n. Learning_rate should be
141  // between (0.0, 1.0], otherwise the non-weighted mean is returned.
142  double ComputeWeightedMean(double learning_rate) const {
143    if (count_ < 1 || learning_rate <= 0.0 || learning_rate >= 1.0) {
144      return ComputeMean();
145    }
146    double weighted_mean = 0.0;
147    double current_weight = 1.0;
148    double weight_sum = 0.0;
149    const size_t max_size = max_count();
150    for (size_t i = 0; i < count_; ++i) {
151      current_weight *= learning_rate;
152      weight_sum += current_weight;
153      // Add max_size to prevent underflow.
154      size_t index = (next_index_ + max_size - i - 1) % max_size;
155      weighted_mean += current_weight * samples_[index];
156    }
157    return weighted_mean / weight_sum;
158  }
159
160  // Compute estimated variance.  Estimation is more accurate
161  // as the number of samples grows.
162  double ComputeVariance() const {
163    if (count_ == 0) {
164      return 0.0;
165    }
166    // Var = E[x^2] - (E[x])^2
167    double count_inv = 1.0 / count_;
168    double mean_2 = sum_2_ * count_inv;
169    double mean = sum_ * count_inv;
170    return mean_2 - (mean * mean);
171  }
172
173 private:
174  size_t count_;
175  size_t next_index_;
176  double sum_;    // Sum(x) - double to avoid overflow
177  double sum_2_;  // Sum(x*x) - double to avoid overflow
178  mutable T max_;
179  mutable bool max_stale_;
180  mutable T min_;
181  mutable bool min_stale_;
182  std::vector<T> samples_;
183
184  DISALLOW_COPY_AND_ASSIGN(RollingAccumulator);
185};
186
187}  // namespace talk_base
188
189#endif  // TALK_BASE_ROLLINGACCUMULATOR_H_
190