multiset

package module
v0.1.0 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Feb 3, 2023 License: MIT Imports: 3 Imported by: 0

README

GoDoc CI Codecov

An unordered multiset implementation.

A multiset, unlike a set, allows values to occur multiple times, and keep tracks of the number of duplicates a value holds.

License

MIT licensed. See the LICENSE file for details.

Documentation

Index

Examples

Constants

This section is empty.

Variables

This section is empty.

Functions

This section is empty.

Types

type Multiset 

type Multiset[T comparable] struct {
	// contains filtered or unexported fields
}

func New 

func New[T comparable]() *Multiset[T]

New contructs an empty multiset.

The multiset is created with an initial capacity of 0. The initial capacity does not bound its size, and it grows to accomodate the number of values stored in it.

Example 
package main

import (
	"github.com/aadamandersson/multiset"
)

func main() {
	_ = multiset.New[int]()
}

Output:

func WithCapacity 

func WithCapacity[T comparable](n int) *Multiset[T]

WithCapacity constructs an empty multiset with the specified capacity.

The multiset is created with an initial capacity of n. The initial capacity does not bound its size, and it grows to accomodate the number of values stored in it.

Example 
package main

import (
	"github.com/aadamandersson/multiset"
)

func main() {
	_ = multiset.WithCapacity[int](10)
}

Output:

func (*Multiset[T]) Cardinality 

func (m *Multiset[T]) Cardinality() int

Cardinality returns the number of items in multiset m.

Multiplicity of an item is not considered.

Example 
package main

import (
	"fmt"

	"github.com/aadamandersson/multiset"
)

func main() {
	ms := multiset.New[int]()
	ms.InsertMany(10, 1)
	ms.InsertMany(20, 2)
	ms.InsertMany(30, 3)
	fmt.Println(ms.Cardinality())
}

Output:

3

func (*Multiset[T]) Clone 

func (m *Multiset[T]) Clone() *Multiset[T]

Clone returns a new multiset which is a copy of multiset m.

Example 
package main

import (
	"fmt"

	"github.com/aadamandersson/multiset"
)

func main() {
	ms1 := multiset.New[int]()
	ms1.InsertMany(20, 2)
	ms1.InsertMany(30, 3)

	ms2 := ms1.Clone()
	fmt.Println(ms1.Equal(ms2))
	ms2.InsertMany(40, 4)
	fmt.Println(ms1.Equal(ms2))
}

Output:

true
false

func (*Multiset[T]) Contains 

func (m *Multiset[T]) Contains(v T) int

Contains returns the number of occurences of value v in multiset m.

Example 
package main

import (
	"fmt"

	"github.com/aadamandersson/multiset"
)

func main() {
	ms := multiset.New[int]()
	ms.Insert(10)
	ms.Insert(10)
	ms.Insert(20)
	fmt.Println(ms.Contains(10))
	fmt.Println(ms.Contains(20))
	fmt.Println(ms.Contains(40))
}

Output:

2
1
0

func (*Multiset[T]) Difference 

func (m *Multiset[T]) Difference(other *Multiset[T]) *Multiset[T]

Difference constructs a new multiset difference of multiset m and other.

The resulting multiset is a multiset whose multiplicities represents how many more of a given item are in m than other.

Example 
package main

import (
	"fmt"

	"github.com/aadamandersson/multiset"
)

func main() {
	ms1 := multiset.New[string]()
	ms1.InsertMany("a", 3)
	ms1.InsertMany("b", 2)
	ms1.InsertMany("c", 1)

	ms2 := multiset.New[string]()
	ms2.InsertMany("a", 2)
	ms2.InsertMany("b", 1)
	ms2.InsertMany("c", 1)
	ms2.InsertMany("d", 1)
	result := ms1.Difference(ms2)
	fmt.Println(result)
	fmt.Println(result.Len())
}

Output:

Multiset{a:1, b:1}
2

func (*Multiset[T]) Each 

func (m *Multiset[T]) Each(f func(T, int) bool)

Each iterates over all items and calls f for each item present in multiset m.

If f returns true, Each stops the iteration.

Example 
package main

import (
	"fmt"

	"github.com/aadamandersson/multiset"
)

func main() {
	ms1 := multiset.New[int]()
	ms1.Insert(10)
	ms1.Insert(20)
	ms1.InsertMany(30, 2)

	ms2 := multiset.New[int]()
	ms1.Each(func(value, multiplicity int) bool {
		ms2.InsertMany(value, multiplicity)
		return false
	})
	fmt.Println(ms1.Equal(ms2))
}

Output:

true

func (*Multiset[T]) Equal 

func (m *Multiset[T]) Equal(other *Multiset[T]) bool

Equal returns true if the length and items of multiset m and other are equal.

TODO: Update this when https://github.com/golang/go/issues/57436 lands.

func (*Multiset[T]) Get 

func (m *Multiset[T]) Get(v T) (T, int, bool)

Get returns a value from multiset m that equals value v, along with its number of occurences and a boolean that is true.

Get returns the zero value of type T, count 0 and false if value v does not exist in multiset m.

Example 
package main

import (
	"fmt"

	"github.com/aadamandersson/multiset"
)

func main() {
	ms := multiset.New[int]()
	ms.Insert(10)
	ms.Insert(20)
	ms.Insert(20)
	fmt.Println(ms.Get(10))
	fmt.Println(ms.Get(20))
	fmt.Println(ms.Get(30))
}

Output:

10 1 true
20 2 true
0 0 false

func (*Multiset[T]) Insert 

func (m *Multiset[T]) Insert(v T) int

Insert inserts a new value v to multiset m.

Insert returns the number of occurences of value v previously in multiset m.

Example 
package main

import (
	"fmt"

	"github.com/aadamandersson/multiset"
)

func main() {
	ms := multiset.New[int]()
	fmt.Println(ms.Insert(10))
	fmt.Println(ms.Insert(10))
	fmt.Println(ms.Insert(20))
}

Output:

0
1
0

func (*Multiset[T]) InsertMany 

func (m *Multiset[T]) InsertMany(v T, n int) int

InsertMany inserts value v to multiset m, with n number of occurences.

InsertMany returns the number of occurences of value v previously in multiset m.

Example 
package main

import (
	"fmt"

	"github.com/aadamandersson/multiset"
)

func main() {
	ms := multiset.New[int]()
	fmt.Println(ms.InsertMany(10, 2))
	fmt.Println(ms.InsertMany(10, 4))
	fmt.Println(ms.InsertMany(20, 6))
	fmt.Println(ms.InsertMany(20, 0))
}

Output:

0
2
0
6

func (*Multiset[T]) Intersection 

func (m *Multiset[T]) Intersection(other *Multiset[T]) *Multiset[T]

Intersection constructs a new multiset intersection of multiset m and other.

The resulting multiset is a multiset of the minimum multiplicity of items present in m and other.

Example 
package main

import (
	"fmt"

	"github.com/aadamandersson/multiset"
)

func main() {
	ms1 := multiset.New[string]()
	ms1.InsertMany("a", 3)
	ms1.InsertMany("b", 2)
	ms1.InsertMany("c", 3)
	ms1.InsertMany("d", 1)

	ms2 := multiset.New[string]()
	ms2.InsertMany("a", 2)
	ms2.InsertMany("b", 1)
	ms2.InsertMany("c", 1)
	fmt.Println(ms1.Intersection(ms2))
}

Output:

Multiset{a:2, b:1, c:1}

func (*Multiset[T]) IsEmpty 

func (m *Multiset[T]) IsEmpty() bool

IsEmpty returns true if there are no items in multiset m, otherwise false.

Example 
package main

import (
	"fmt"

	"github.com/aadamandersson/multiset"
)

func main() {
	ms := multiset.New[int]()
	fmt.Println(ms.IsEmpty())
	ms.Insert(10)
	fmt.Println(ms.IsEmpty())
}

Output:

true
false

func (*Multiset[T]) Len 

func (m *Multiset[T]) Len() int

Len returns the number of items of multiset m.

Duplicates are counted.

Example 
package main

import (
	"fmt"

	"github.com/aadamandersson/multiset"
)

func main() {
	ms := multiset.New[int]()
	ms.Insert(10)
	ms.Insert(10)
	ms.Insert(20)
	fmt.Println(ms.Len())
}

Output:

3

func (*Multiset[T]) Remove 

func (m *Multiset[T]) Remove(v T) int

Remove removes value v from multiset m.

Remove returns the number of occurences of value v previously in multiset m.

Example 
package main

import (
	"fmt"

	"github.com/aadamandersson/multiset"
)

func main() {
	ms := multiset.New[int]()
	ms.InsertMany(10, 2)
	fmt.Println(ms.Contains(10))
	ms.Remove(10)
	fmt.Println(ms.Contains(10))
	ms.Remove(10)
	fmt.Println(ms.Contains(10))
	fmt.Println(ms.Remove(10))
}

Output:

2
1
0
0

func (*Multiset[T]) Replace 

func (m *Multiset[T]) Replace(v T) int

Replace replaces all existing occurences of value v in multiset m, if any, with 1.

Replace returns the number of occurences of value v previously in multiset m.

Example 
package main

import (
	"fmt"

	"github.com/aadamandersson/multiset"
)

func main() {
	ms := multiset.New[int]()
	ms.InsertMany(10, 2)
	fmt.Println(ms.Get(10))
	fmt.Println(ms.Replace(10))
	fmt.Println(ms.Get(10))
}

Output:

10 2 true
2
10 1 true

func (*Multiset[T]) String 

func (m *Multiset[T]) String() string

String returns a formatted multiset with the following format:

Multiset{1: 2, 2: 3}

func (*Multiset[T]) Sum 

func (m *Multiset[T]) Sum(other *Multiset[T]) *Multiset[T]

Sum constructs a new multiset sum of multiset m and other.

The resulting multiset is a multiset whose multiplicities represents how many times a given item occur in both m and other.

Example 
package main

import (
	"fmt"

	"github.com/aadamandersson/multiset"
)

func main() {
	ms1 := multiset.New[string]()
	ms1.InsertMany("a", 2)
	ms1.InsertMany("b", 3)
	ms1.InsertMany("d", 1)

	ms2 := multiset.New[string]()
	ms2.InsertMany("a", 1)
	ms2.InsertMany("b", 3)
	ms2.InsertMany("c", 2)
	fmt.Println(ms1.Sum(ms2))
}

Output:

Multiset{a:3, b:6, c:2, d:1}

func (*Multiset[T]) Union 

func (m *Multiset[T]) Union(other *Multiset[T]) *Multiset[T]

Union constructs a new multiset union of multiset m and other.

The resulting multiset is a multiset of the maximum multiplicity of items present in m and other.

Example 
package main

import (
	"fmt"

	"github.com/aadamandersson/multiset"
)

func main() {
	ms1 := multiset.New[string]()
	ms1.InsertMany("a", 2)
	ms1.InsertMany("b", 3)
	ms1.InsertMany("c", 1)
	ms1.InsertMany("d", 2)

	ms2 := multiset.New[string]()
	ms2.InsertMany("b", 2)
	ms2.InsertMany("c", 3)
	ms2.InsertMany("d", 2)
	ms2.InsertMany("e", 1)
	fmt.Println(ms1.Union(ms2))
}

Output:

Multiset{a:2, b:3, c:3, d:2, e:1}

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.