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

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

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

## struct array_multiset[view source]

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

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

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

 const array_multiset< T > & items )

Adds the given multiset items to this multiset.

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

 array_multiset< T > & s, FILE * in, Reader &&... reader )

Reads an array_multiset structure s from in.

Parameters

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

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

 const T & item )

Adds the given item to the multiset.

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

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

 hash_multiset< T > & s, FILE * in, Reader & reader )

Reads a hash_multiset s from in.

Parameters

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.