multiset.h

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

In the following example, both an array_multiset and a hash_multiset 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/multiset.h>
using namespace core;

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

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

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

Classes, functions, and variables in this file
structarray_multiset
boolinit (array_multiset< T > & s, unsigned int initial_capacity)
boolinit (array_multiset< T > & s, const array_multiset< T > & src)
booloperator == (const array_multiset< T > & first, const array_multiset< T > & second)
booloperator != (const array_multiset< T > & first, const array_multiset< T > & second)
boolread (array_multiset< T > & s, FILE * in, Reader &&... reader)
boolwrite (const array_multiset< T > & s, FILE * out, Writer &&... writer)
voidprint (const array_multiset< T > & s, FILE * out, Printer &&... printer)
structhash_multiset
boolinit (hash_multiset< T > & s, unsigned int initial_capacity)
boolread (hash_multiset< T > & s, FILE * in, Reader & reader)
boolwrite (const hash_multiset< T > & s, FILE * out, Writer & writer)
voidprint (const hash_multiset< T > & s, FILE * out, Printer &&... printer)

struct array_multiset

template<typename T>

A multiset 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_multiset 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_multiset (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_multiset< T > & items)
unsigned intsubtract (const T & item, unsigned int start_index = 0)
voidsubtract (const array_multiset< T > & items)
voidclear ()
voidremove_zeros (unsigned int start_index = 0)
boolis_sorted () const
static unsigned inthash (const array_multiset< T > & key)
static voidmove (const array_multiset< T > & src, array_multiset< T > & dst)
static voidswap (array_multiset< T > & first, array_multiset< T > & second)
static boolcopy (const array_multiset< T > & src, array_multiset< T > & dst)
static voidfree (array_multiset< T > & s)
array_map< T, unsigned int > array_multiset::counts

The underlying array_map.

unsigned int array_multiset::sum

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

array_multiset::array_multiset(
unsigned intinitial_capacity)

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

unsigned int array_multiset::total()

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

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

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

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

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

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

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

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

Adds the given multiset items to this multiset.

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

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

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

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

void array_multiset::clear()

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

void array_multiset::remove_zeros(
unsigned intstart_index = 0)

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

bool array_multiset::is_sorted()

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

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

Returns the hash function evaluated on the given array_multiset key.

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

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

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

Swaps the contents of the given array_multisets first and second.

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

Copies the contents of the array_multiset src into dst.

static void array_multiset::free(
array_multiset< T > &s)

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

template<typename T>
bool init(
array_multiset< T > &s,
unsigned intinitial_capacity)

Initializes an empty array_multiset s with the given initial_capacity for the underlying array_map array_multiset::counts.

template<typename T>
bool init(
array_multiset< T > &s,
const array_multiset< T > &src)

Initializes the given array_multiset s by copying the contents from the given array_multiset src.

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

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

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

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

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

Reads an array_multiset structure s from in.

Parameters
reader

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

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

Writes the given array_multiset structure s to out.

Parameters
writer

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

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

Prints the given array_multiset structure s to out.

Parameters
printer

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

struct hash_multiset

template<typename T>

A multiset 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_multiset 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_multiset (unsigned int initial_capacity)
unsigned inttotal () const
booladd (const T & item)
booladd (const array_multiset< T > & items)
voidsubtract (const T & item)
voidsubtract (const array_multiset< T > & items)
static voidmove (const hash_multiset< T > & src, hash_multiset< T > & dst)
static boolcopy (const hash_multiset< T > & src, hash_multiset< T > & dst)
static voidfree (hash_multiset< T > & s)
hash_map< T, unsigned int > hash_multiset::counts

The underlying hash_map.

unsigned int hash_multiset::sum

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

hash_multiset::hash_multiset(
unsigned intinitial_capacity)

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

unsigned int hash_multiset::total()

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

bool hash_multiset::add(
const T &item)

Adds the given item to the multiset.

bool hash_multiset::add(
const array_multiset< T > &items)

Adds the given multiset of items to this multiset.

void hash_multiset::subtract(
const T &item)

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

void hash_multiset::subtract(
const array_multiset< T > &items)

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

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

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

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

Copies the contents of the array_multiset src into dst.

static void hash_multiset::free(
hash_multiset< T > &s)

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

template<typename T>
bool init(
hash_multiset< T > &s,
unsigned intinitial_capacity)

Initializes an empty hash_multiset s with the given initial_capacity for the underlying hash_map hash_multiset::counts.

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

Reads a hash_multiset s from in.

Parameters
reader

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

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

Writes the given hash_multiset s to out.

Parameters
writer

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

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

Prints the given hash_multiset s to out.

Parameters
printer

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