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>
h.remove('r');
}

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

array_histogram<char> second(8);
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)
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)
boolwrite (const hash_histogram< T > & h, FILE * out, Writer & writer)
voidprint (const hash_histogram< T > & h, FILE * out, Printer &&... printer)

## struct array_histogram[view source]

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 int initial_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).

 const T & item, unsigned int count = 1, unsigned int start_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.

 const T & item, unsigned int count = 1, unsigned int start_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.

 const array_histogram< T > & items )

Adds the given histogram items to this histogram.

unsigned int array_histogram::subtract(
 const T & item, unsigned int start_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 int start_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 int initial_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.

 array_histogram< T > & h, FILE * in, Reader &&... reader )

Reads an array_histogram structure h from in.

Parameters

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[view source]

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. 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 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 int initial_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).

 const T & item )

Adds the given item to the histogram.

 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 int initial_capacity )

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

 hash_histogram< T > & h, FILE * in, Reader & reader )

Reads a hash_histogram h from in.

Parameters

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.