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); }
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.
| T | satisfies LessThanComparable and CopyAssignable. |
| AutomaticallyFree | whether the keys of the underlying core::hash_map are freed when this object is freed. |
The underlying array_map.
The sum of the values in array_multiset::counts (i.e. the total number of occurrences of all elements).
Constructs an empty array_multiset with the given initial_capacity for the underlying array_map array_multiset::counts.
Returns the total number of occurrences of all elements (array_multiset::sum).
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.
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, OtherAutomaticallyFree > & | items | ) |
Adds the given multiset items to this multiset.
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.
| const array_multiset< T, OtherAutomaticallyFree > & | 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).
Removes all elements from this multiset. If AutomaticallyFree == true, this function also frees the keys in the underlying array_map by calling core::free on each element.
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.
Returns true if and only if the underlying array_map array_multiset::counts is sorted.
Returns the hash function evaluated on the given array_multiset key.
| const array_multiset< T, AutomaticallyFree > & | src, | |
| array_multiset< T, OtherAutomaticallyFree > & | dst | ) |
Moves the array_multiset src into dst. Note that this function merely copies pointers, and not contents.
| array_multiset< T, AutomaticallyFree > & | first, | |
| array_multiset< T, OtherAutomaticallyFree > & | second | ) |
Swaps the contents of the given array_multisets first and second.
| const array_multiset< T, AutomaticallyFree > & | src, | |
| array_multiset< T, OtherAutomaticallyFree > & | dst | ) |
Copies the contents of the array_multiset src into dst.
Frees the given array_multiset s. If AutomaticallyFree == true, this function also frees the keys in the underlying array_map by calling core::free on each element.
| array_multiset< T, AutomaticallyFree > & | s, | |
| unsigned int | initial_capacity | ) |
Initializes an empty array_multiset s with the given initial_capacity for the underlying array_map array_multiset::counts.
| array_multiset< T, AutomaticallyFree > & | s, | |
| const array_multiset< T, OtherAutomaticallyFree > & | src | ) |
Initializes the given array_multiset s by copying the contents from the given array_multiset src.
| const array_multiset< T, AutomaticallyFree > & | first, | |
| const array_multiset< T, OtherAutomaticallyFree > & | second | ) |
Returns true if and only if the array_multiset first is equivalent to second.
| const array_multiset< T, AutomaticallyFree > & | first, | |
| const array_multiset< T, OtherAutomaticallyFree > & | second | ) |
Returns false if and only if the array_multiset first is equivalent to second.
| array_multiset< T, AutomaticallyFree > & | s, | |
| FILE * | in, | |
| Reader &&... | reader | ) |
s from in.| reader | a scribe that is passed to |
| const array_multiset< T, AutomaticallyFree > & | s, | |
| FILE * | out, | |
| Writer &&... | writer | ) |
s to out.| writer | a scribe that is passed to |
| const array_multiset< T, AutomaticallyFree > & | s, | |
| FILE * | out, | |
| Printer &&... | printer | ) |
s to out.| printer | a scribe that is passed to |
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.
| T | the generic type of the elements. T must satisfy either:
|
| AutomaticallyFree | whether the keys of the underlying core::hash_map are freed when this object is freed. |
| Public members | |
|---|---|
| hash_map< T, unsigned int > | counts |
| unsigned int | sum |
| hash_multiset (unsigned int initial_capacity) | |
| unsigned int | total () const |
| bool | add (const T & item) |
| bool | add (const array_multiset< T, OtherAutomaticallyFree > & items) |
| void | subtract (const T & item) |
| void | subtract (const array_multiset< T, OtherAutomaticallyFree > & items) |
| static void | move (const hash_multiset< T, AutomaticallyFree > & src, hash_multiset< T, OtherAutomaticallyFree > & dst) |
| static bool | copy (const hash_multiset< T, AutomaticallyFree > & src, hash_multiset< T, OtherAutomaticallyFree > & dst) |
| static void | free (hash_multiset< T, AutomaticallyFree > & s) |
The underlying hash_map.
The sum of the values in hash_multiset::counts (i.e. the total number of occurrences of all elements).
Constructs an empty hash_multiset with the given initial_capacity for the underlying hash_map hash_multiset::counts.
Returns the total number of occurrences of all elements (hash_multiset::sum).
Adds the given item to the multiset.
| const array_multiset< T, OtherAutomaticallyFree > & | items | ) |
Adds the given multiset of items to this multiset.
Removes the given item from the multiset. This function assumes that item exists in the multiset with non-zero frequency.
| const array_multiset< T, OtherAutomaticallyFree > & | 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).
| const hash_multiset< T, AutomaticallyFree > & | src, | |
| hash_multiset< T, OtherAutomaticallyFree > & | dst | ) |
Moves the hash_multiset src into dst. Note that this function merely copies pointers, and not contents.
| const hash_multiset< T, AutomaticallyFree > & | src, | |
| hash_multiset< T, OtherAutomaticallyFree > & | dst | ) |
Copies the contents of the array_multiset src into dst.
Frees the given hash_multiset s. If AutomaticallyFree == true, this function also frees the keys in the underlying hash_map by calling core::free on each element.
| hash_multiset< T, AutomaticallyFree > & | 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, AutomaticallyFree > & | s, | |
| FILE * | in, | |
| Reader &&... | reader | ) |
| const hash_multiset< T, AutomaticallyFree > & | s, | |
| FILE * | out, | |
| Writer &&... | writer | ) |
| const hash_multiset< T, AutomaticallyFree > & | s, | |
| FILE * | out, | |
| Printer &&... | printer | ) |