histogram.hh

   1 #include <cassert>
   2 #include <cstdio>
   3 #include <cstring>
   4
   5 namespace goir {
   6
   7   class Histogram {
   8   private:
   9     unsigned _steps;
  10     unsigned _max;
  11     unsigned _samples;
  12     unsigned *_data;
  13   public:
  14     Histogram(unsigned steps, unsigned max)
  15       : _steps(steps)
  16       , _max(max)
  17       , _samples(0)
  18       , _data(new unsigned[_steps]) {
  19       memset(_data, 0, _steps*sizeof(unsigned));
  20     }
  21     Histogram(const Histogram & h)
  22       : _steps(h._steps)
  23       , _max(h._max)
  24       , _samples(h._samples)
  25       , _data(new unsigned[_steps]) {
  26       memcpy(_data, h._data, _steps*sizeof(unsigned));
  27     }
  28     ~Histogram() {
  29       delete[] _data;
  30     }
  31
  32     class ValueNotFoundException { };
  33
  34     unsigned samples() { return _samples; }
  35
  36     void record(unsigned value) {
  37       unsigned slot = value * (_steps - 1) / _max;
  38       assert(slot<_steps);
  39       _samples++;
  40       _data[slot] ++;
  41     }
  42
  43     unsigned min_nonempty() const {
  44       for (unsigned i = 0; i<_steps; i++)
  45         if (_data[i] != 0) return i;
  46       throw new ValueNotFoundException;
  47     }
  48
  49     static const unsigned tolerance_base = 1000000;
  50
  51     unsigned max_nonempty(unsigned tolerance = 0) const {
  52       unsigned tolerated = tolerance * _samples / tolerance_base;
  53       for (int i = _steps-1; i>0; i--)
  54         if (_data[i] != 0) {
  55           // return index of non-empty slot as soon as tolerance is over
  56           if (tolerated == 0) return i;
  57           // else decrease tolerance accordingly
  58           if (_data[i] >= tolerated)
  59             tolerated = 0;
  60           else
  61             tolerated -= _data[i];
  62         }
  63       throw new ValueNotFoundException;
  64     }
  65
  66     void display() {
  67       unsigned low, high;
  68       try {
  69         low = min_nonempty();
  70         high = max_nonempty();
  71       } catch (ValueNotFoundException *e) {
  72         printf("(bounds not found!)");
  73         low = 0; high = _steps - 1;
  74       }
  75       printf("RANGE: %u - %u:", low, high);
  76       for (unsigned i = low; i <= high; i++)
  77           printf(" %d", _data[i]);
  78       printf("\n");
  79     }
  80
  81     void display_potential_false_matches() {
  82       printf("0.001: %u - 0.005: %u - 0.01: %u\n",
  83              max_nonempty(1000), max_nonempty(5000), max_nonempty(10000));
  84     }
  85
  86   };
  87
  88 }