// Author: mikedebo@gmail.com (Michael DiBernardo)
// Copyright Michael DiBernardo 2006
// Implementation of class NibbleCounter and related constructs.
//
// The NibbleCounter works by maintaining a single byte for every two ints in
// the range. The count for an even integer n is stored in the low-order nibble
// of byte (n/2), and the count for an odd integer n is stored in the
// high-order nibble of the byte (n/2).
//
// There are two basic operations that the NibbleCounter supports: Adding one
// to the frequency of a number, and getting the frequency of a number. I'll
// discuss each of those in turn here.
// 
// -----------------------------------------------------------------------------
// Adding an occurrence.
// -----------------------------------------------------------------------------
// Let's say we have a byte that has the counts 3 and 12 in the low- and high-
// order nibbles, respectively. That means our byte is 0011 1100.
//
// To add 1 to the low-order nibble is easy: We just add 1 :D 
//      0011 1100 (3, 12)
//    + 0000 0001 (0, 1)
//      ---------
//      0011 1101 (3, 13)
//
// To add 1 to high-order nibble, we can just add 2^4 (0x10) which is 0001 0000.
//      0011 1100 (3, 12)
//    + 0001 0000 (1, 0)
//      ---------
//      0100 1101 (4, 13)
//
// -----------------------------------------------------------------------------
// Getting an occurrence.
// -----------------------------------------------------------------------------
// Again, let's say we have a byte that has the counts 3 and 12 in the low- and
// high- order nibbles, respectively: 0011 1100.
//
// To get the low-order nibble, you can mask out the high-order nibble with the
// mask 0000 1111 (0x0F):
//
//      0011 1100 (3, 12 or 60 total)
//    & 0000 1111 (0x0F)
//      ---------
//      0000 1100 (12 total)
//
// To get the high-order nibble, you can right-shift the byte by one nibble:
//
//      0011 1100 (3, 12 or 60 in total)
//   >>         4
//      ---------
//      0000 0011 (3 in total)
//
// That's it! In many ways this is much easier than the bit vector
// implementation from the previous exercises.
//
// See the main() method for a couple of demos that use the NibbleCounter to
// play with a small histogram and to sort a list of numbers with duplicates.
#include "NibbleCounter.h"
#include <math.h>

//------------------------------------------------------------------------------
// Constants
//------------------------------------------------------------------------------
const Byte kHighOrderNibbleMask = 0x0F;
const Byte kLowOrderNibbleIncrement = 0x01;
const Byte kHighOrderNibbleIncrement = 0x10;
const Byte kZeroByte = 0;
const int kSizeOfNibbleInBits = 4;

//------------------------------------------------------------------------------
// NibbleCounter class implementation.
//------------------------------------------------------------------------------
NibbleCounter::NibbleCounter(int size) 
  : size_(size),
    num_bytes_((int) ceil(size/2.0)),
    bytes_(new Byte[num_bytes_]) {
  for (int i = 0; i < num_bytes_; ++i) {
    bytes_[i] = kZeroByte;
  }
}

NibbleCounter::~NibbleCounter() {
  delete [] bytes_;
}

void NibbleCounter::AddOccurrenceOf(int number) {
  // Find the byte that holds the count for the given number.
  int byteIndex = number / 2;

  // Figure out if the nibble is in the high order bits of the
  // byte or the low order bits of the byte.
  bool isHighOrderNibble = ( (number % 2) == 1);

  if (isHighOrderNibble) {
    bytes_[byteIndex] += kHighOrderNibbleIncrement;
  } else {
    bytes_[byteIndex] += kLowOrderNibbleIncrement;
  }
}

int NibbleCounter::GetFrequencyOf(int number) const {
  // Again, find the byte that holds the count for the given number.
  int byteIndex = number / 2;
  Byte byteWithOurNibble = bytes_[byteIndex];

  // Figure out if the nibble is in the high order bits of the
  // byte or the low order bits of the byte.
  bool isHighOrderNibble = ( (number % 2) == 1);
  if (isHighOrderNibble) {
    // If it is, we have to shift the high-order nibble to the low-order
    // bits to get the count.
    byteWithOurNibble >>= kSizeOfNibbleInBits;
  } else {
    // Otherwise, we have to mask out the higher-order bits so that they
    // don't artifically inflate the count.
    byteWithOurNibble &= kHighOrderNibbleMask;
  }

  return byteWithOurNibble;
}

int NibbleCounter::Size() const {
  return num_bytes_;
}

//------------------------------------------------------------------------------
// Cursory demo of how it works.
//------------------------------------------------------------------------------
#include <iostream>
using std::cout;
using std::endl;

const int kSize = 10;

void demoCounting() {
  NibbleCounter counter(kSize);

  cout << "== Counting Demo ==" << endl;
  cout << "Initial state:" << endl;
  for (int i = 0; i < kSize; ++i) {
    cout << "Num: " << i << " Count: " << counter.GetFrequencyOf(i) << endl;
  }

  counter.AddOccurrenceOf(0);

  counter.AddOccurrenceOf(5);
  counter.AddOccurrenceOf(4);

  counter.AddOccurrenceOf(5);
  counter.AddOccurrenceOf(4);
  
  int MAX_NIBBLE_VALUE = 15;

  for (int i = 0; i < MAX_NIBBLE_VALUE; ++i) {
    counter.AddOccurrenceOf(7);
  }

  cout << "After additions:" << endl;
  for (int i = 0; i < kSize; ++i) {
    cout << "Num: " << i << " Count: " << counter.GetFrequencyOf(i) << endl;
  }
}

void demoSorting() {
  NibbleCounter sorter(kSize);

  int unsorted[] = { 1, 2, 4, 1, 5, 4, 3, 1, 2, 4, 1, 3, 4, 5, 3, 2, 4, 6, 7, 4};
  const int kListSize = 20;

  cout << "== Sorting Demo ==" << endl;
  cout << "Unsorted list:" << endl;
  for (int i = 0; i < kListSize; ++i) {
    cout << unsorted[i] << " ";
  } 
  cout << endl;

  for (int i = 0; i < kListSize; ++i) {
    sorter.AddOccurrenceOf(unsorted[i]);
  }

  cout << "Sorted list:" << endl;
  for (int i = 0; i < kSize; ++i) {
    int frequencyOfi = sorter.GetFrequencyOf(i);
    for (int n = 0; n < frequencyOfi; ++n) {
      cout << i << " ";
    }
  }
  cout << endl;
}

int main() {
  demoCounting();
  cout << endl;
  demoSorting();
}