Documentation
¶
Overview ¶
Package multiset uses the primitives in mapset to implement a simple multiset.
Index ¶
- Variables
- type Of
- func (m Of[K]) Add(o Of[K]) Of[K]
- func (m Of[K]) Cardinality() uint64
- func (m Of[K]) Clone() Of[K]
- func (m Of[K]) Contains(k K) bool
- func (m Of[K]) Dec(k K, x uint64) uint64
- func (m Of[K]) Equal(o Of[K]) bool
- func (m Of[K]) Inc(k K, x uint64) uint64
- func (m Of[K]) IncDec(k K, n int) uint64
- func (m Of[K]) Included(o Of[K]) bool
- func (m Of[K]) Intersect(o Of[K]) Of[K]
- func (m Of[K]) Keys() []K
- func (m Of[K]) ProperIncluded(o Of[K]) bool
- func (m Of[K]) Purge()
- func (m Of[K]) Sub(o Of[K]) Of[K]
- func (m Of[K]) Union(o Of[K]) Of[K]
Examples ¶
Constants ¶
This section is empty.
Variables ¶
var ErrOverflow = errors.New("overflow")
ErrOverflow is used whenever addition of two uint64 would overflow. This is an unlikely thing that few will ever need to consider so it is always reported via
panic(ErrOverflow)
Functions ¶
This section is empty.
Types ¶
type Of ¶
type Of[K comparable] map[K]uint64
multiset.Of[K] is a set of K where keys can be stored more than once. The number of times a key is stored, m[k], is called the multiplicity of the key.
A multiplicity of 0 is the same as not being in the set.
func (Of[K]) Add ¶
Add chooses the sum of multiplicities of both multisets. It panics if any sum overflows.
r[k] = m[k] + o[k]
Example ¶
package main
import (
"fmt"
"github.com/jimmyfrasche/mapset/multiset"
)
func main() {
x := multiset.Of[string]{"a": 1, "b": 0, "c": 5}
y := multiset.Of[string]{"c": 3, "d": 4}
fmt.Println(x.Add(y))
}
Output: map[a:1 c:8 d:4]
func (Of[K]) Cardinality ¶
Cardinality is the sum of the multiplicities of all items. It panics if the sum overflows.
Example ¶
package main
import (
"fmt"
"github.com/jimmyfrasche/mapset/multiset"
)
func main() {
x := multiset.Of[string]{"a": 1, "b": 0, "c": 5}
fmt.Println(x.Cardinality())
}
Output: 6
func (Of[K]) Equal ¶
true if, for all k:
m[k] == o[k]
Example ¶
package main
import (
"fmt"
"github.com/jimmyfrasche/mapset/multiset"
)
func main() {
x := multiset.Of[string]{"a": 1, "b": 2, "c": 3}
y := multiset.Of[string]{"a": 1, "b": 3, "c": 4}
z := multiset.Of[string]{"a": 1, "b": 2, "c": 3, "d": 1}
fmt.Println("x = y?", x.Equal(y))
fmt.Println("y = x?", y.Equal(x))
fmt.Println("x = z?", x.Equal(z))
fmt.Println("x = x?", x.Equal(x))
}
Output: x = y? false y = x? false x = z? false x = x? true
func (Of[K]) Included ¶
m Included in o if the multiplicity of each item in m is <= the corresponding multiplicity in o.
true if, for all k:
m[k] <= o[k]
Example ¶
package main
import (
"fmt"
"github.com/jimmyfrasche/mapset/multiset"
)
func main() {
x := multiset.Of[string]{"a": 1, "b": 2, "c": 3}
y := multiset.Of[string]{"a": 1, "b": 3, "c": 4}
z := multiset.Of[string]{"d": 0, "e": 9, "f": 2}
fmt.Println("x ≤ y?", x.Included(y))
fmt.Println("x ≥ y?", y.Included(x))
fmt.Println("x ≤ z?", x.Included(z))
}
Output: x ≤ y? true x ≥ y? false x ≤ z? false
func (Of[K]) Intersect ¶
Intersect chooses the minimum of multiplicities of both multisets.
r[k] = min(m[k], o[k])
Example ¶
package main
import (
"fmt"
"github.com/jimmyfrasche/mapset/multiset"
)
func main() {
x := multiset.Of[string]{"a": 1, "b": 0, "c": 5, "e": 1}
y := multiset.Of[string]{"c": 3, "d": 4, "e": 9}
fmt.Println(x.Intersect(y))
}
Output: map[a:1 c:3 d:4 e:1]
func (Of[K]) ProperIncluded ¶
m is ProperIncluded in o if the multiplicity of each item in m is < the corresponding multiplicity in o.
true if, for all k:
m[k] < o[k]
Example ¶
package main
import (
"fmt"
"github.com/jimmyfrasche/mapset/multiset"
)
func main() {
x := multiset.Of[string]{"a": 1, "b": 2, "c": 3}
y := multiset.Of[string]{"a": 5, "b": 3, "c": 4}
z := multiset.Of[string]{"d": 0, "e": 9, "f": 2}
fmt.Println("x < y?", x.ProperIncluded(y))
fmt.Println("x > y?", y.ProperIncluded(x))
fmt.Println("x < z?", x.ProperIncluded(z))
}
Output: x < y? true x > y? false x < z? false
func (Of[K]) Sub ¶
Sub chooses the proper subtraction of both multisets.
r[k] = max(m[k] - o[k], 0)
Example ¶
package main
import (
"fmt"
"github.com/jimmyfrasche/mapset/multiset"
)
func main() {
x := multiset.Of[string]{"a": 1, "b": 0, "c": 5}
y := multiset.Of[string]{"c": 3, "d": 4}
fmt.Println(x.Sub(y))
fmt.Println(y.Sub(x))
}
Output: map[a:1 c:2 d:4] map[a:1 d:4]
func (Of[K]) Union ¶
Union chooses the maximum of multiplicities of both multisets.
r[k] = max(m[k], o[k])
Example ¶
package main
import (
"fmt"
"github.com/jimmyfrasche/mapset/multiset"
)
func main() {
x := multiset.Of[string]{"a": 1, "b": 0, "c": 5, "e": 1}
y := multiset.Of[string]{"c": 3, "d": 4, "e": 9}
fmt.Println(x.Union(y))
}
Output: map[a:1 c:5 d:4 e:9]
Source Files