// Author: mikedebo@gmail.com (Michael DiBernardo)
// Copyright Michael DiBernardo 2006
//
// A NibbleCounter acts as a histogram over a range of positive integers.
// It uses a nibble of space to maintain a count for each integer, and so
// you can add at most 15 occurrences to a particular bucket before
// overflowing.
#ifndef __NIBBLECOUNTER_H__
#define __NIBBLECOUNTER_H__

// Data that we use to store our nibbles.
typedef unsigned char Byte;

class NibbleCounter {
 public:
  // Construct a new counter that will maintain counts for the range [0, size),
  // with all counts starting at 0. Note that if size is an odd number, you
  // will actually end up with a counter that maintains size+1 counts, and no
  // assertions will be fired if you access this last count. The 'Size()'
  // method will always return the size that you specify here, though.
  explicit NibbleCounter(int size);

  // Free resources used by this counter.
  ~NibbleCounter();

  // Adds an occurrence of the given number. The number must be in the range
  // [0, size) and getFrequencyOf(number) must be less than 15 before the call,
  // lest you cause overflow. Overflow in the count for a number can corrupt
  // the count for an adjacent number, so don't do it!
  void AddOccurrenceOf(int number);

  // Returns the frequency of the given number. The number must be in the range
  // [0, size).
  int GetFrequencyOf(int number) const;

  // The number of integers that this counter is maintaining counts for.
  int Size() const;

 private:
  // Number of integers that the counter is maintaining counts for.
  int size_;
  // Number of bytes used to store the counts.
  int num_bytes_;
  // The actual bytes used to store the counts.
  Byte* bytes_;
};

#endif