histogram.h

This file contains implementations for array_histogram and hash_histogram, which are structures that count the number of occurrences of each distinct element in a set. array_histogram implements this using a core::array_map, where the elements are the keys, and the frequencies are the values with type unsigned int. hash_histogram implements this using a core::hash_map.

In the following example, both an array_histogram and a hash_histogram are constructed. The same set of elements are added to both, and the two are printed to stdout. The expected output is {e:1, i:2, r:0, c:3, q:1} {c:3, e:1, i:2, q:1, r:0}.

#include <math/histogram.h>
using namespace core;

template<typename Histogram>
void add_elements(Histogram& h) {
    h.add('c'); h.add('c');
    h.add('e'); h.add('q');
    h.add('r'); h.add('i');
    h.add('i'); h.add('c');
    h.remove('r');
}

int main() {
    hash_histogram<char> first(16);
    add_elements(first);
    print(first, stdout); print("  ", stdout);

    array_histogram<char> second(8);
    add_elements(second);
    print(second, stdout);
}

Classes, functions, and variables in this file
structarray_histogram
boolinit (array_histogram< T > & h, unsigned int initial_capacity)
boolinit (array_histogram< T > & h, const array_histogram< T > & src)
booloperator == (const array_histogram< T > & first, const array_histogram< T > & second)
booloperator != (const array_histogram< T > & first, const array_histogram< T > & second)
boolread (array_histogram< T > & h, FILE * in, Reader &&... reader)
boolwrite (const array_histogram< T > & h, FILE * out, Writer &&... writer)
voidprint (const array_histogram< T > & h, FILE * out, Printer &&... printer)
structhash_histogram
boolinit (hash_histogram< T > & h, unsigned int initial_capacity)
boolread (hash_histogram< T > & h, FILE * in, Reader & reader)
boolwrite (const hash_histogram< T > & h, FILE * out, Writer & writer)
voidprint (const hash_histogram< T > & h, FILE * out, Printer &&... printer)

struct array_histogram

template<typename T>

A histogram structure that keeps track of the number of occurrences of distinct element in a set, implemented using a core::array_map, where the elements are the keys, and the values are their frequencies. The entries in the underlying core::array_map are sorted according to the keys.

hash_histogram implements the same abstract data type using a core::hash_map and should be used if the number of distinct elements is expected to be large.

Template parameters
T

satisfies LessThanComparable and CopyAssignable.

Public members
array_map< T, unsigned int >counts
unsigned intsum
array_histogram (unsigned int initial_capacity)
unsigned inttotal () const
booladd (const T & item, unsigned int count = 1, unsigned int start_index = 0)
booladd_unsorted (const T & item, unsigned int count = 1, unsigned int start_index = 0)
booladd (const array_histogram< T > & items)
unsigned intsubtract (const T & item, unsigned int start_index = 0)
voidsubtract (const array_histogram< T > & items)
voidclear ()
voidremove_zeros (unsigned int start_index = 0)
boolis_sorted () const
static unsigned inthash (const array_histogram< T > & key)
static voidmove (const array_histogram< T > & src, array_histogram< T > & dst)
static voidswap (array_histogram< T > & first, array_histogram< T > & second)
static boolcopy (const array_histogram< T > & src, array_histogram< T > & dst)
static voidfree (array_histogram< T > & h)
array_map< T, unsigned int > array_histogram::counts

The underlying array_map.

unsigned int array_histogram::sum

The sum of the values in array_histogram::counts (i.e. the total number of occurrences of all elements).

array_histogram::array_histogram(
unsigned intinitial_capacity)

Constructs an empty array_histogram with the given initial_capacity for the underlying array_map array_histogram::counts.

unsigned int array_histogram::total()

Returns the total number of occurrences of all elements (array_histogram::sum).

bool array_histogram::add(
const T &item,
unsigned intcount = 1,
unsigned intstart_index = 0)

Adds the given item to the histogram with frequency count. The given start_index may be provided to improve performance. However, this function assumes that if item already exists in this histogram, its underlying index in array_histogram::counts is not smaller than start_index.

This function sorts array_histogram::counts. If the user wishes to add multiple elements, they should consider using add_unsorted or the overload of add that takes an array_histogram as its parameter.

bool array_histogram::add_unsorted(
const T &item,
unsigned intcount = 1,
unsigned intstart_index = 0)

Adds the given item to the histogram with frequency count. The given start_index may be provided to improve performance. However, this function assumes that if item already exists in this histogram, its underlying index in array_histogram::counts is not smaller than start_index.

This function leaves array_histogram::counts unsorted, and so the user must sort array_histogram::counts after all elements are added.

bool array_histogram::add(
const array_histogram< T > &items)

Adds the given histogram items to this histogram.

unsigned int array_histogram::subtract(
const T &item,
unsigned intstart_index = 0)

Removes the given item from the histogram. The given start_index may be provided to improve performance. However, this function assumes that item exists in the histogram with non-zero frequency, and the underlying index of item in array_histogram::counts is not smaller than start_index.

void array_histogram::subtract(
const array_histogram< T > &items)

Removes the given histogram items from this histogram. This function assumes that the given histogram items is a subset of this histogram (i.e. this histogram contains all the keys in items with frequencies at least as large).

void array_histogram::clear()

Removes all elements from this histogram. This function also frees the keys in the underlying array_map by calling core::free on each element.

void array_histogram::remove_zeros(
unsigned intstart_index = 0)

This function removes keys from array_histogram::counts whose recorded frequencies are 0. If the user is frequently removing items from this histogram, this function should be called periodically to clean up the empty entries.

bool array_histogram::is_sorted()

Returns true if and only if the underlying array_map array_histogram::counts is sorted.

static unsigned int array_histogram::hash(
const array_histogram< T > &key)

Returns the hash function evaluated on the given array_histogram key.

static void array_histogram::move(
const array_histogram< T > &src,
array_histogram< T > &dst)

Moves the array_histogram src into dst. Note that this function merely copies pointers, and not contents.

static void array_histogram::swap(
array_histogram< T > &first,
array_histogram< T > &second)

Swaps the contents of the given array_histograms first and second.

static bool array_histogram::copy(
const array_histogram< T > &src,
array_histogram< T > &dst)

Copies the contents of the array_histogram src into dst.

static void array_histogram::free(
array_histogram< T > &h)

Frees the given array_histogram h. This function also frees the keys in the underlying array_map by calling core::free on each element.

template<typename T>
bool init(
array_histogram< T > &h,
unsigned intinitial_capacity)

Initializes an empty array_histogram h with the given initial_capacity for the underlying array_map array_histogram::counts.

template<typename T>
bool init(
array_histogram< T > &h,
const array_histogram< T > &src)

Initializes the given array_histogram h by copying the contents from the given array_histogram src.

template<typename T>
bool operator == (
const array_histogram< T > &first,
const array_histogram< T > &second)

Returns true if and only if the array_histogram first is equivalent to second.

template<typename T>
bool operator != (
const array_histogram< T > &first,
const array_histogram< T > &second)

Returns false if and only if the array_histogram first is equivalent to second.

template<typename T, typename... Reader>
bool read(
array_histogram< T > &h,
FILE *in,
Reader &&...reader)

Reads an array_histogram structure h from in.

Parameters
reader

a scribe that is passed to read for core::array_map.

template<typename T, typename... Writer>
bool write(
const array_histogram< T > &h,
FILE *out,
Writer &&...writer)

Writes the given array_histogram structure h to out.

Parameters
writer

a scribe that is passed to write for core::array_map.

template<typename T, typename... Printer>
void print(
const array_histogram< T > &h,
FILE *out,
Printer &&...printer)

Prints the given array_histogram structure h to out.

Parameters
printer

a scribe that is passed to print for core::array_map.

struct hash_histogram

template<typename T>

A histogram structure that keeps track of the number of occurrences of distinct elements in a set, implemented using a core::hash_map, where the elements are the keys, and the values are their frequencies.

array_histogram implements the same abstract data type using a core::array_map and should be used if the number of distinct elements is expected to be small.

Template parameters
T

the generic type of the elements. T must satisfy either:

  1. is_fundamental,

  2. is_enum,

  3. is_pointer,

  4. implements the public static method unsigned int hash(const T&), the public static method void is_empty(const T&), implements the operators ==, satisfies CopyAssignable, and core::is_moveable. NOTE: The first argument to the == operator may be empty.

Public members
hash_map< T, unsigned int >counts
unsigned intsum
hash_histogram (unsigned int initial_capacity)
unsigned inttotal () const
booladd (const T & item)
booladd (const array_histogram< T > & items)
voidsubtract (const T & item)
voidsubtract (const array_histogram< T > & items)
static voidmove (const hash_histogram< T > & src, hash_histogram< T > & dst)
static boolcopy (const hash_histogram< T > & src, hash_histogram< T > & dst)
static voidfree (hash_histogram< T > & h)
hash_map< T, unsigned int > hash_histogram::counts

The underlying hash_map.

unsigned int hash_histogram::sum

The sum of the values in hash_histogram::counts (i.e. the total number of occurrences of all elements).

hash_histogram::hash_histogram(
unsigned intinitial_capacity)

Constructs an empty hash_histogram with the given initial_capacity for the underlying hash_map hash_histogram::counts.

unsigned int hash_histogram::total()

Returns the total number of occurrences of all elements (hash_histogram::sum).

bool hash_histogram::add(
const T &item)

Adds the given item to the histogram.

bool hash_histogram::add(
const array_histogram< T > &items)

Adds the given histogram of items to this histogram.

void hash_histogram::subtract(
const T &item)

Removes the given item from the histogram. This function assumes that item exists in the histogram with non-zero frequency.

void hash_histogram::subtract(
const array_histogram< T > &items)

Removes the given histogram items from this histogram. This function assumes that the given histogram items is a subset of this histogram (i.e. this histogram contains all the keys in items with frequencies at least as large).

static void hash_histogram::move(
const hash_histogram< T > &src,
hash_histogram< T > &dst)

Moves the hash_histogram src into dst. Note that this function merely copies pointers, and not contents.

static bool hash_histogram::copy(
const hash_histogram< T > &src,
hash_histogram< T > &dst)

Copies the contents of the array_histogram src into dst.

static void hash_histogram::free(
hash_histogram< T > &h)

Frees the given hash_histogram h. This function also frees the keys in the underlying hash_map by calling core::free on each element.

template<typename T>
bool init(
hash_histogram< T > &h,
unsigned intinitial_capacity)

Initializes an empty hash_histogram h with the given initial_capacity for the underlying hash_map hash_histogram::counts.

template<typename T, typename Reader>
bool read(
hash_histogram< T > &h,
FILE *in,
Reader &reader)

Reads a hash_histogram h from in.

Parameters
reader

a scribe that is passed to read for core::hash_map.

template<typename T, typename Writer>
bool write(
const hash_histogram< T > &h,
FILE *out,
Writer &writer)

Writes the given hash_histogram h to out.

Parameters
writer

a scribe that is passed to write for core::hash_map.

template<typename T, typename... Printer>
void print(
const hash_histogram< T > &h,
FILE *out,
Printer &&...printer)

Prints the given hash_histogram h to out.

Parameters
printer

a scribe that is passed to print for core::hash_map.