averager.h

Go to the documentation of this file.

#ifndef AVERAGER_CLASS
#define AVERAGER_CLASS
 
/*****************************************************************************\
*                                                                             *
*  Name   : averager                                                          *
*  Author : Chris Koeritz                                                     *
*                                                                             * 
*******************************************************************************
* Copyright (c) 1997-$now By Author.  This program is free software; you can  *
* redistribute it and/or modify it under the terms of the GNU General Public  *
* License as published by the Free Software Foundation; either version 2 of   *
* the License or (at your option) any later version.  This is online at:      *
*     http://www.fsf.org/copyleft/gpl.html                                    *
* Please send any updates to: fred@gruntose.com                               *
\*****************************************************************************/
 
#include <basis/array.h>
#include <basis/functions.h>
 
namespace mathematics {
 
 
template <class contents>
class averager
{
public:
  averager(int entries = 100, bool compacting = true);
 
  void add(contents value, int count = 1);
 
  contents average() const { return average(0, length() - 1); }
 
  int samples() const;
 
  int length() const { return _averages.length(); }
 
  contents average(int start, int end) const;
 
  struct weighted_entry { contents value; int count; };
 
  weighted_entry get(int index) const { return _averages.get(index); }
 
  void compact();
 
  void check_for_compaction();
 
private:
  bool _do_compaction;  
  basis::array<weighted_entry> _averages;  
  int _entries;  
};
 
 
class int_averager : public averager<int>
{
public:
  int_averager(int entries = 100, bool compacting = true)
          : averager<int>(entries, compacting) {}
};
 
 
// implementations below...
 
const int AVERAGER_SIZE_LIMIT = 180000;  // the most items we'll try to handle.
 
template <class contents>
averager<contents>::averager(int entries, bool compacting)
: _do_compaction(compacting), _averages(), _entries(entries)
{
  int unit_size = sizeof(weighted_entry);
  if (basis::negative(_entries) || !_entries)
    _entries = int(AVERAGER_SIZE_LIMIT / unit_size);
}
 
template <class contents>
void averager<contents>::compact()
{
  if (length() < 8) return;  // sorry, you're too short for this wild ride.
  int end_whacking = _averages.length() / 4;
  if (_do_compaction) {
    contents whacked_average = average(0, end_whacking);
    _averages.zap(1, end_whacking);
    _averages[0].value = whacked_average;
    _averages[0].count = end_whacking + 1;
  } else _averages.zap(0, end_whacking);
}
 
template <class contents>
void averager<contents>::check_for_compaction()
{
  // make sure that we don't go over our allotted space.
  int unit_size = sizeof(weighted_entry);
  int limit = basis::minimum(AVERAGER_SIZE_LIMIT, _entries * unit_size);
  if (int(_averages.length() + 2) * unit_size >= limit) compact();
}
 
template <class contents>
void averager<contents>::add(contents value, int count)
{
  weighted_entry to_add;
  to_add.value = value;
  to_add.count = count;
  check_for_compaction();
  _averages += to_add;
}
 
template <class contents>
contents averager<contents>::average(int start, int end) const
{
  bounds_return(start, 0, length() - 1, 0);
  bounds_return(end, start, length() - 1, 0);
  bounds_return(end - start + 1, 1, length(), 0);
 
  contents accum = 0;
  contents count = 0;
  for (int i = start; i <= end; i++) {
    accum += get(i).value * get(i).count;
    count += get(i).count;
  }
  if (!count) count = 1;
  return accum / count;
}
 
template <class contents>
int averager<contents>::samples() const
{
  int to_return = 0;
  for (int i = 0; i < length(); i++) to_return += get(i).count;
  return to_return;
}
 
} //namespace.
 
#endif