Documentation
¶
Overview ¶
Multiset is a map with uint-values that represents a set of elements with their respective number of elements. Functions `Increment` and `Decrement` will increase or decrease the count of elements of that key, and if the count reaches zero, it will delete the element from the map (multiset). This allows testing the map with `len(multiset)` to test current size.
The multiset uses `uint`-based counts such that the multiset adapts to the capacity of the architecture on which it is executed.
These multiset functions are just functions that operate on a map. Therefore there is no caching or any other kind of optimization possible/available.
INVARIANT: all elements have a count strictly larger than 0. (I.e. elements that reach 0 are --must be-- deleted from the multiset.) FIXME try to set an upper-limit guard for `C` to ensure that multiset does not wrap around undetected.
Index ¶
- func Contains[K comparable, C types.UnsignedInteger](multiset map[K]C, e K) bool
- func Count[K comparable, C types.UnsignedInteger](multiset map[K]C) C
- func Create[K comparable, C types.UnsignedInteger](count C, elements ...K) map[K]C
- func Difference[K comparable, C types.UnsignedInteger](a, b map[K]C) map[K]C
- func Elements[K comparable, C types.UnsignedInteger](multiset map[K]C) []K
- func ElementsOrdered[K comparable, C types.UnsignedInteger](multiset map[K]C, lessFunc func(key1, key2 K) bool) []K
- func Equal[K comparable, C types.UnsignedInteger](a, b map[K]C) bool
- func Insert[K comparable, C types.UnsignedInteger](multiset map[K]C, e K)
- func InsertMany[K comparable, C types.UnsignedInteger](multiset map[K]C, elements []K)
- func InsertN[K comparable, C types.UnsignedInteger](multiset map[K]C, e K, n C)
- func InsertSet[K comparable, C types.UnsignedInteger](multiset map[K]C, set map[K]struct{})
- func InsertSetN[K comparable, C types.UnsignedInteger](multiset map[K]C, set map[K]struct{}, n C)
- func Intersection[K comparable, C types.UnsignedInteger](a, b map[K]C) map[K]C
- func Remove[K comparable, C types.UnsignedInteger](multiset map[K]C, e K)
- func RemoveMany[K comparable, C types.UnsignedInteger](multiset map[K]C, elements []K)
- func RemoveN[K comparable, C types.UnsignedInteger](multiset map[K]C, e K, n C)
- func RemoveSet[K comparable, C types.UnsignedInteger](multiset map[K]C, set map[K]struct{})
- func Set[K comparable, C types.UnsignedInteger](multiset map[K]C) map[K]struct{}
- func Sum[K comparable, C types.UnsignedInteger](a, b map[K]C) map[K]C
- func Union[K comparable, C types.UnsignedInteger](a, b map[K]C) map[K]C
- func Update[K comparable, C types.UnsignedInteger](multiset map[K]C, update func(K, C) C)
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func Contains ¶
func Contains[K comparable, C types.UnsignedInteger](multiset map[K]C, e K) bool
Contains tests for presence of an element in a multiset-like map.
func Count ¶
func Count[K comparable, C types.UnsignedInteger](multiset map[K]C) C
Sum the numbers of each element in the multiset into a total count. (The number of unique elements can be acquired using `len(multiset)`.)
func Create ¶
func Create[K comparable, C types.UnsignedInteger](count C, elements ...K) map[K]C
Create creates and initializes a new map[K]C for use as multiset. All provided elements will immediately be included in the multiset, with initial value as specified in param `count`. Initialization assumes that elements are unique; immediately allocates room for `len(elements)` elements in the map.
func Difference ¶
func Difference[K comparable, C types.UnsignedInteger](a, b map[K]C) map[K]C
func Elements ¶
func Elements[K comparable, C types.UnsignedInteger](multiset map[K]C) []K
Elements generates a slice (`[]K`) with all elements of the multiset.
func ElementsOrdered ¶
func ElementsOrdered[K comparable, C types.UnsignedInteger](multiset map[K]C, lessFunc func(key1, key2 K) bool) []K
ElementsOrdered generates a slice (`[]K`) with all elements of the multiset, ordered according to the provided `lessFunc`.
func Equal ¶
func Equal[K comparable, C types.UnsignedInteger](a, b map[K]C) bool
Equal compares to multisets for equality, i.e. same elements with same counts.
func Insert ¶
func Insert[K comparable, C types.UnsignedInteger](multiset map[K]C, e K)
Insert increments the count of an element, inserting the element if necessary.
func InsertMany ¶
func InsertMany[K comparable, C types.UnsignedInteger](multiset map[K]C, elements []K)
InsertMany increments the count of an element for each element provided in `elements`.
func InsertN ¶
func InsertN[K comparable, C types.UnsignedInteger](multiset map[K]C, e K, n C)
InsertN increments the count of an element with n, inserting the element if necessary.
func InsertSet ¶
func InsertSet[K comparable, C types.UnsignedInteger](multiset map[K]C, set map[K]struct{})
InsertSet increments count of each element of `set` (by 1) in `multiset`.
func InsertSetN ¶
func InsertSetN[K comparable, C types.UnsignedInteger](multiset map[K]C, set map[K]struct{}, n C)
InsertSetN increments count of each element of `set` by `n` in `multiset`.
func Intersection ¶
func Intersection[K comparable, C types.UnsignedInteger](a, b map[K]C) map[K]C
func Remove ¶
func Remove[K comparable, C types.UnsignedInteger](multiset map[K]C, e K)
Remove decrements the count of an element, deleting the element from the map (multiset) if the count reaches 0. By deleting the element, `len(...)` may be used to accurately measure how many different elements are currently present. Go's property of assuming zero-value default allows transparently querying non-existing element and receiving an accurate count of 0.
func RemoveMany ¶
func RemoveMany[K comparable, C types.UnsignedInteger](multiset map[K]C, elements []K)
RemoveMany removes all values in `elements` from `multiset`.
func RemoveN ¶
func RemoveN[K comparable, C types.UnsignedInteger](multiset map[K]C, e K, n C)
RemoveN decrements the count of an element by `n`. The element count must be at least `n`, otherwise the function panics.
func RemoveSet ¶
func RemoveSet[K comparable, C types.UnsignedInteger](multiset map[K]C, set map[K]struct{})
RemoveSet removes all elements in `set` from `multiset`.
func Set ¶
func Set[K comparable, C types.UnsignedInteger](multiset map[K]C) map[K]struct{}
Set generates a set (`map[K]struct{}`) with all elements of the multiset.
func Sum ¶
func Sum[K comparable, C types.UnsignedInteger](a, b map[K]C) map[K]C
func Union ¶
func Union[K comparable, C types.UnsignedInteger](a, b map[K]C) map[K]C
func Update ¶
func Update[K comparable, C types.UnsignedInteger](multiset map[K]C, update func(K, C) C)
Update updates the counts for each key. `update` is the update-function, the returned value is used as new count-value for this key. A value of 0 will result in the key being deleted.
Types ¶
This section is empty.
Source Files