Merge branch 'release-2.140.101'
[feisty_meow.git] / nucleus / library / mathematics / averager.h
1 #ifndef AVERAGER_CLASS
2 #define AVERAGER_CLASS
3
4 /*****************************************************************************\
5 *                                                                             *
6 *  Name   : averager                                                          *
7 *  Author : Chris Koeritz                                                     *
8 *                                                                             * 
9 *******************************************************************************
10 * Copyright (c) 1997-$now By Author.  This program is free software; you can  *
11 * redistribute it and/or modify it under the terms of the GNU General Public  *
12 * License as published by the Free Software Foundation; either version 2 of   *
13 * the License or (at your option) any later version.  This is online at:      *
14 *     http://www.fsf.org/copyleft/gpl.html                                    *
15 * Please send any updates to: fred@gruntose.com                               *
16 \*****************************************************************************/
17
18 #include <basis/array.h>
19 #include <basis/functions.h>
20
21 namespace mathematics {
22
23 //! Maintains a list of numbers and provides the average for them.
24 /*!
25   The list entries can be weighted if desired.  If the list grows too large,
26   the first chunk of the entries is added as a weighted average and the list's
27   size is reduced appropriately.
28 */
29
30 template <class contents>
31 class averager
32 {
33 public:
34   averager(int entries = 100, bool compacting = true);
35     //!< creates an averager whose list length is restricted to "entries".
36     /*!< if "entries" that is zero, then the maximum length is used.  if
37     "compacting" is true, then the entries which need to be removed during
38     a compaction will be added to the list as a weighted average.  if it's
39     false, then the unfortunate entries are just eliminated.  the first style
40     leads to a more steady state version of the average while the other is
41     more recent history.  note that the lowest reasonable value for "entries"
42     is eight due to the compaction algorithm; lower values will work, but the
43     averager will allow the list to grow to eight anyway. */
44
45   void add(contents value, int count = 1);
46     //!< adds a new "value" to the averager, with an optional "count".
47
48   contents average() const { return average(0, length() - 1); }
49     //!< reports the overall average of the whole list.
50
51   int samples() const;
52     //!< returns the total number of samples recorded in the average.
53
54   int length() const { return _averages.length(); }
55     //!< returns the current length of the averages list.
56
57   contents average(int start, int end) const;
58     //!< reports the average over the range from "start" to "end" inclusive.
59
60   struct weighted_entry { contents value; int count; };
61     //!< structure holding a weighted chunk of the average.
62     /*!< an entry in the list of averages has a "value" and a "count" that
63     measures the weight with which that "value" is considered. */
64
65   weighted_entry get(int index) const { return _averages.get(index); }
66     //!< accesses the entry stored at the "index" specified.
67
68   void compact();
69     //!< chops off the oldest portion of the averager.
70     /*!< if this is a compacting style averager, then the older data is
71     coalesced and added as a weighted entry. */
72
73   void check_for_compaction();
74     //!< checks whether the averager needs to be compacted yet or not.
75     /*!< the decision is made according to the maximum allowable size in
76     "entries" passed to the constructor.  if "entries" is zero, the maximum
77     allowable size is used instead. */
78
79 private:
80   bool _do_compaction;  //!< do truncated values coalesce to a weighted entry?
81   basis::array<weighted_entry> _averages;  //!< current list.
82   int _entries;  //!< maximum length of list.
83 };
84
85 //////////////
86
87 //! keeps an average on a stream of integers.
88 class int_averager : public averager<int>
89 {
90 public:
91   int_averager(int entries = 100, bool compacting = true)
92           : averager<int>(entries, compacting) {}
93 };
94
95 //////////////
96
97 // implementations below...
98
99 const int AVERAGER_SIZE_LIMIT = 180000;  // the most items we'll try to handle.
100
101 template <class contents>
102 averager<contents>::averager(int entries, bool compacting)
103 : _do_compaction(compacting), _averages(), _entries(entries)
104 {
105   int unit_size = sizeof(weighted_entry);
106   if (basis::negative(_entries) || !_entries)
107     _entries = int(AVERAGER_SIZE_LIMIT / unit_size);
108 }
109
110 template <class contents>
111 void averager<contents>::compact()
112 {
113   if (length() < 8) return;  // sorry, you're too short for this wild ride.
114   int end_whacking = _averages.length() / 4;
115   if (_do_compaction) {
116     contents whacked_average = average(0, end_whacking);
117     _averages.zap(1, end_whacking);
118     _averages[0].value = whacked_average;
119     _averages[0].count = end_whacking + 1;
120   } else _averages.zap(0, end_whacking);
121 }
122
123 template <class contents>
124 void averager<contents>::check_for_compaction()
125 {
126   // make sure that we don't go over our allotted space.
127   int unit_size = sizeof(weighted_entry);
128   int limit = basis::minimum(AVERAGER_SIZE_LIMIT, _entries * unit_size);
129   if (int(_averages.length() + 2) * unit_size >= limit) compact();
130 }
131
132 template <class contents>
133 void averager<contents>::add(contents value, int count)
134 {
135   weighted_entry to_add;
136   to_add.value = value;
137   to_add.count = count;
138   check_for_compaction();
139   _averages += to_add;
140 }
141
142 template <class contents>
143 contents averager<contents>::average(int start, int end) const
144 {
145   bounds_return(start, 0, length() - 1, 0);
146   bounds_return(end, start, length() - 1, 0);
147   bounds_return(end - start + 1, 1, length(), 0);
148
149   contents accum = 0;
150   contents count = 0;
151   for (int i = start; i <= end; i++) {
152     accum += get(i).value * get(i).count;
153     count += get(i).count;
154   }
155   if (!count) count = 1;
156   return accum / count;
157 }
158
159 template <class contents>
160 int averager<contents>::samples() const
161 {
162   int to_return = 0;
163   for (int i = 0; i < length(); i++) to_return += get(i).count;
164   return to_return;
165 }
166
167 } //namespace.
168
169 #endif
170