core/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