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  

struct  array_histogram 
bool  init (array_histogram< T > & h, unsigned int initial_capacity) 
bool  init (array_histogram< T > & h, const array_histogram< T > & src) 
bool  operator == (const array_histogram< T > & first, const array_histogram< T > & second) 
bool  operator != (const array_histogram< T > & first, const array_histogram< T > & second) 
bool  read (array_histogram< T > & h, FILE * in, Reader &&... reader) 
bool  write (const array_histogram< T > & h, FILE * out, Writer &&... writer) 
void  print (const array_histogram< T > & h, FILE * out, Printer &&... printer) 
struct  hash_histogram 
bool  init (hash_histogram< T > & h, unsigned int initial_capacity) 
bool  read (hash_histogram< T > & h, FILE * in, Reader & reader) 
bool  write (const hash_histogram< T > & h, FILE * out, Writer & writer) 
void  print (const hash_histogram< T > & h, FILE * out, Printer &&... printer) 
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 int  sum 
array_histogram (unsigned int initial_capacity)  
unsigned int  total () const 
bool  add (const T & item, unsigned int count = 1, unsigned int start_index = 0) 
bool  add_unsorted (const T & item, unsigned int count = 1, unsigned int start_index = 0) 
bool  add (const array_histogram< T > & items) 
unsigned int  subtract (const T & item, unsigned int start_index = 0) 
void  subtract (const array_histogram< T > & items) 
void  clear () 
void  remove_zeros (unsigned int start_index = 0) 
bool  is_sorted () const 
static unsigned int  hash (const array_histogram< T > & key) 
static void  move (const array_histogram< T > & src, array_histogram< T > & dst) 
static void  swap (array_histogram< T > & first, array_histogram< T > & second) 
static bool  copy (const array_histogram< T > & src, array_histogram< T > & dst) 
static void  free (array_histogram< T > & h) 
The underlying array_map.
The sum of the values in array_histogram::counts (i.e. the total number of occurrences of all elements).
unsigned int  initial_capacity  ) 
Constructs an empty array_histogram with the given initial_capacity
for the underlying array_map array_histogram::counts.
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.
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 nonzero frequency, and the underlying index of item
in array_histogram::counts is not smaller than start_index
.
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).
Removes all elements from this histogram. This function also frees the keys in the underlying array_map by calling core::free on each element.
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.
Returns true if and only if the underlying array_map array_histogram::counts is sorted.
const array_histogram< T > &  key  ) 
Returns the hash function evaluated on the given array_histogram key
.
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.
array_histogram< T > &  first,  
array_histogram< T > &  second  ) 
Swaps the contents of the given array_histograms first
and second
.
const array_histogram< T > &  src,  
array_histogram< T > &  dst  ) 
Copies the contents of the array_histogram src
into dst
.
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.
Initializes an empty array_histogram h
with the given initial_capacity
for the underlying array_map array_histogram::counts.
Initializes the given array_histogram h
by copying the contents from the given array_histogram src
.
const array_histogram< T > &  first,  
const array_histogram< T > &  second  ) 
Returns true if and only if the array_histogram first
is equivalent to second
.
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  

reader 
a scribe that is passed to 
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 
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 
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.

Public members  

hash_map< T, unsigned int >  counts 
unsigned int  sum 
hash_histogram (unsigned int initial_capacity)  
unsigned int  total () const 
bool  add (const T & item) 
bool  add (const array_histogram< T > & items) 
void  subtract (const T & item) 
void  subtract (const array_histogram< T > & items) 
static void  move (const hash_histogram< T > & src, hash_histogram< T > & dst) 
static bool  copy (const hash_histogram< T > & src, hash_histogram< T > & dst) 
static void  free (hash_histogram< T > & h) 
The underlying hash_map.
The sum of the values in hash_histogram::counts (i.e. the total number of occurrences of all elements).
unsigned int  initial_capacity  ) 
Constructs an empty hash_histogram with the given initial_capacity
for the underlying hash_map hash_histogram::counts.
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.
const T &  item  ) 
Removes the given item from the histogram. This function assumes that item exists in the histogram with nonzero frequency.
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).
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.
const hash_histogram< T > &  src,  
hash_histogram< T > &  dst  ) 
Copies the contents of the array_histogram src
into dst
.
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.
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  

reader 
a scribe that is passed to 
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 
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 