FenwickFrequencyTable

FenwickFrequencyTable.cpp

#include <stdexcept>
#include "FenwickFrequencyTable.h"

FenwickFrequencyTable::FenwickFrequencyTable(const std::vector<uint32_t>& freqs) {
	if (freqs.size() > UINT32_MAX - 1)
		throw std::length_error("Too many symbols");
	uint32_t size = static_cast<uint32_t>(freqs.size());
	if (size < 1)
		throw std::invalid_argument("At least 1 symbol needed");

	frequencies = freqs;
	fenwick_cumulative_tree.resize(size + 1);
	total = 0;
	for (int i = 0; i < size - 1; i++)
	{
		fenwick_add(i, frequencies[i]);
		total += frequencies[i];
	}
	total = getHigh(size - 1);
}


FenwickFrequencyTable::FenwickFrequencyTable(const FrequencyTable& freqs) {
	uint32_t size = freqs.getSymbolLimit();
	if (size < 1)
		throw std::invalid_argument("At least 1 symbol needed");
	if (size > UINT32_MAX - 1)
		throw std::length_error("Too many symbols");

	frequencies.reserve(size);
	fenwick_cumulative_tree.resize(size + 1);
	total = 0;
	for (int i = 0; i < size - 1; i++)
	{
		uint32_t freq = freqs.get(i);
		frequencies.push_back(freq);
		fenwick_add(i, freq);
		total += freq;
	}
	total = getHigh(size - 1);
}

#define LSB(i) ((i) & -int32_t(i)) // zeroes all the bits except the least significant one
void FenwickFrequencyTable::fenwick_add(unsigned symbol, unsigned freqadd)
{
	uint32_t size = frequencies.size();
	unsigned slot = symbol + 1;
	while (slot < size)
		fenwick_cumulative_tree[slot] += freqadd, slot += LSB(slot);
}

void FenwickFrequencyTable::fenwick_remove(unsigned symbol, unsigned freqremove)
{
	uint32_t size = frequencies.size();
	unsigned slot = symbol + 1;
	while (slot < size)
		fenwick_cumulative_tree[slot] -= freqremove, slot += LSB(slot);
}

uint32_t FenwickFrequencyTable::getSymbolLimit() const {
	return static_cast<uint32_t>(frequencies.size());
}


uint32_t FenwickFrequencyTable::get(uint32_t symbol) const {
	return frequencies.at(symbol);
}


void FenwickFrequencyTable::set(uint32_t symbol, uint32_t freq) {
	if (total < frequencies.at(symbol))
		throw std::logic_error("Assertion error");
	uint32_t oldFreq = frequencies.at(symbol);
	uint32_t temp = total - oldFreq;
	total = checkedAdd(temp, freq);
	if (freq > oldFreq)
	{
		uint32_t delta = freq - oldFreq;
		fenwick_add(symbol, delta);
	}
	else if (freq < oldFreq)
	{
		uint32_t delta = oldFreq - freq;
		fenwick_remove(symbol, delta);
	}
	frequencies.at(symbol) = freq;	
}


void FenwickFrequencyTable::increment(uint32_t symbol) {
	if (frequencies.at(symbol) == UINT32_MAX)
		throw std::overflow_error("Arithmetic overflow");
	total = checkedAdd(total, 1);
	frequencies.at(symbol)++;
	fenwick_add(symbol, 1);
}

void FenwickFrequencyTable::decrement(uint32_t symbol) {
	if (frequencies.at(symbol) == 0)
		throw std::overflow_error("Already no symbol");
	total -= 1;
	frequencies.at(symbol)--;
	fenwick_remove(symbol, 1);
}


uint32_t FenwickFrequencyTable::getTotal() const {
	return total;
}


uint32_t FenwickFrequencyTable::getLow(uint32_t symbol) const {
	uint32_t sum = 0;
	uint32_t slot = symbol;
	while (slot > 0)
		sum += fenwick_cumulative_tree[slot], slot -= LSB(slot);
	return sum;
}


uint32_t FenwickFrequencyTable::getHigh(uint32_t symbol) const {
	return getLow(symbol) + frequencies[symbol];
	//@todo: zrobić getLowAndHigh	
}

FenwickFrequencyTable.h

#pragma once
#include "FrequencyTable.h"
/*
 * A mutable table of symbol frequencies using Fenwick trees.
 */
class FenwickFrequencyTable :
	public FrequencyTable
{
	/*---- Fields ----*/

// The frequency for each symbol. Its length is at least 1.
private: std::vector<std::uint32_t> frequencies;

// Fenwick tree. 
private: std::vector<std::uint32_t> fenwick_cumulative_tree;

// Always equal to the sum of 'frequencies'.
private: std::uint32_t total;

		 /*---- Constructors ----*/

		 // Constructs a frequency table from the given array of symbol frequencies.
		 // There must be at least 1 symbol, and the total must not exceed UINT32_MAX.
public: explicit FenwickFrequencyTable(const std::vector<std::uint32_t>& freqs);


		// Constructs a frequency table by copying the given frequency table.
public: explicit FenwickFrequencyTable(const FrequencyTable& freqs);

		/*---- Methods ----*/

public: std::uint32_t getSymbolLimit() const override;


public: std::uint32_t get(std::uint32_t symbol) const override;


public: void set(std::uint32_t symbol, std::uint32_t freq) override;


public: void increment(std::uint32_t symbol) override;

public: void decrement(std::uint32_t symbol) override;

public: std::uint32_t getTotal() const override;


public: std::uint32_t getLow(std::uint32_t symbol) const override;


public: std::uint32_t getHigh(std::uint32_t symbol) const override;


		// Recomputes the array of cumulative symbol frequencies.
private: void initCumulative(bool checkTotal = true) const;
		 

		 // add number of freq to Fenwick tree
private: void fenwick_add(unsigned symbol, unsigned freqadd);

		 // remove number of freq from Fenwick tree
private: void fenwick_remove(unsigned symbol, unsigned freqremove);
};