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    : count_(0),
46      next_index_(0),
47      sum_(0.0),
48      sum_2_(0.0),
49      samples_(max_count) {
50  }
51  ~RollingAccumulator() {
52  }
53
54  size_t max_count() const {
55    return samples_.size();
56  }
57
58  size_t count() const {
59    return count_;
60  }
61
62  void AddSample(T sample) {
63    if (count_ == max_count()) {
64      // Remove oldest sample.
65      T sample_to_remove = samples_[next_index_];
66      sum_ -= sample_to_remove;
67      sum_2_ -= sample_to_remove * sample_to_remove;
68    } else {
69      // Increase count of samples.
70      ++count_;
71    }
72    // Add new sample.
73    samples_[next_index_] = sample;
74    sum_ += sample;
75    sum_2_ += sample * sample;
76    // Update next_index_.
77    next_index_ = (next_index_ + 1) % max_count();
78  }
79
80  T ComputeSum() const {
81    return static_cast<T>(sum_);
82  }
83
84  T ComputeMean() const {
85    if (count_ == 0) {
86      return static_cast<T>(0);
87    }
88    return static_cast<T>(sum_ / count_);
89  }
90
91  // O(n) time complexity.
92  // Weights nth sample with weight (learning_rate)^n. Learning_rate should be
93  // between (0.0, 1.0], otherwise the non-weighted mean is returned.
94  T ComputeWeightedMean(double learning_rate) const {
95    if (count_ < 1 || learning_rate <= 0.0 || learning_rate >= 1.0) {
96      return ComputeMean();
97    }
98    double weighted_mean = 0.0;
99    double current_weight = 1.0;
100    double weight_sum = 0.0;
101    const size_t max_size = max_count();
102    for (size_t i = 0; i < count_; ++i) {
103      current_weight *= learning_rate;
104      weight_sum += current_weight;
105      // Add max_size to prevent underflow.
106      size_t index = (next_index_ + max_size - i - 1) % max_size;
107      weighted_mean += current_weight * samples_[index];
108    }
109    return static_cast<T>(weighted_mean / weight_sum);
110  }
111
112  // Compute estimated variance.  Estimation is more accurate
113  // as the number of samples grows.
114  T ComputeVariance() const {
115    if (count_ == 0) {
116      return static_cast<T>(0);
117    }
118    // Var = E[x^2] - (E[x])^2
119    double count_inv = 1.0 / count_;
120    double mean_2 = sum_2_ * count_inv;
121    double mean = sum_ * count_inv;
122    return static_cast<T>(mean_2 - (mean * mean));
123  }
124
125 private:
126  size_t count_;
127  size_t next_index_;
128  double sum_;    // Sum(x)
129  double sum_2_;  // Sum(x*x)
130  std::vector<T> samples_;
131
132  DISALLOW_COPY_AND_ASSIGN(RollingAccumulator);
133};
134
135}  // namespace talk_base
136
137#endif  // TALK_BASE_ROLLINGACCUMULATOR_H_
138