iterset

package module
v0.5.0 Latest Latest
Warning

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

Go to latest
Published: Sep 19, 2025 License: Apache-2.0 Imports: 5 Imported by: 0

README

build codecov CodeQL go report go ref

iterset

A set library based on maps and iterators. A set type is not necessary to have set operations.

There are many mapset implementations available, but they restrict the values to struct{} or bool. Although it seems like the right abstract data type, in practice it limits the usability.

  • Maps must be copied even though they already support iteration and O(1) lookup.
  • Map values are lost.
  • Slices must be copied even if they would have only been iterated.
  • Slice ordering is lost.
  • Copying effectively means no early exits, e.g., in a subset check.

Since sets are not built-in, they realistically will always be a secondary type. Even in languages with built-in sets, it is common to call set operations on keys while still keeping data in a map, and common to want to retain ordering.

So iterset is built around generic maps with any value type. Inspired by Python sets, its methods support iterators. This integrates well with functions in maps and slices, and addresses the typical mapset issues.

  • Maps can be casted instead of copied.
  • Map values are kept without affecting set operations.
  • Slices can be iterated using slices.Values without copying.
  • Slice iterators retain ordering.
  • Iterators are lazily evaluated, inherently supporting early exits.

Usage

Constructors

There are constructors for all common use cases.

  • Cast a map
  • Unique{By} iterates keys in order
  • Compact{By} iterates consecutive grouped keys
  • Collect with default value
  • Set from variadic args
  • Index retains original position
  • Count stores key counts
  • IndexBy stores values by key function
  • Group{By} stores slices grouped by keys
  • Reduce combines values grouped by keys
  • Memoize caches function call
Methods

Methods support iterators, compatible with slices.Values and maps.Keys. Implementations are asymptotically optimal, and exit early where relevant.

  • Equal
  • IsSubset
  • IsSuperset
  • IsDisjoint
  • Union
  • Intersect
  • Difference
  • ReverseDifference
  • SymmetricDifference
Functions

Some operations are also functions, to avoid making unnecessary maps. Note there is a trade-off between early exits versus iteration overhead. If one sequence is expected to be smaller, it is often faster to collect it into a map anyway.

  • Equal{Counts}
  • IsSubset
  • IsDisjoint
  • Intersect
  • Difference
  • Sorted{Union,Intersect,Difference}

Includes general sequence utilities which complement the set operations. These are subject to change as iter patterns progress.

  • IsEmpty
  • Size
  • Keys
  • Sorted
  • Min
  • Max
  • GoIter

Iterators are only single-use if their input was.

Installation

No dependencies. Go >=1.23 required.

go get github.com/coady/iterset

Tests

100% code coverage.

go test -cover
go test -bench=.

Documentation

Overview

Package iterset is a set library based on maps and iterators.

Example (Difference)

Update a slice by removing common adapted keys.

values := []string{"A", "B", "C"}
keys := []string{"d", "c", "b"}
// With no sets.
m := map[string]bool{}
for _, value := range values {
	m[strings.ToLower(value)] = true
}
keys = slices.DeleteFunc(keys, func(key string) bool { return m[key] })
fmt.Println(keys)
// A typical `mapset` would have minimal impact on readability.
s := Set[string]()
for _, value := range values {
	s.Add(strings.ToLower(value))
}
keys = slices.DeleteFunc(keys, s.Contains)
fmt.Println(keys)
// Whereas `iterset` can in-line the set construction.
v := IndexBy(slices.Values(values), strings.ToLower)
keys = slices.DeleteFunc(keys, v.Contains)
fmt.Println(keys)
Output:

[d]
[d]
[d]
Example (Intersect)

Intersect a map with a slice of keys, retaining original order.

data := map[string]int{"a": 0, "b": 1, "c": 2}
keys := []string{"d", "c", "b"}
// With no sets.
for _, key := range keys {
	value, ok := data[key]
	if ok {
		fmt.Println(key, value)
	}
}
// A typical `mapset` would copy `data`, and have no impact on readability.
s := Set(slices.Collect(maps.Keys(data))...)
for _, key := range keys {
	if s.Contains(key) {
		fmt.Println(key, data[key])
	}
}
// Using an intersect method would also copy `keys`, and lose ordering.
// Whereas `iterset` methods have in-lined logic with zero copying and lazy iteration.
for key, value := range Cast(data).Intersect(slices.Values(keys)) {
	fmt.Println(key, value)
}
Output:

c 2
b 1
c 2
b 1
c 2
b 1
Example (Superset)

Is one slice a superset of another?

left, right := []string{"a", "b", "c"}, []string{"b", "c", "d"}
// With no sets.
m := map[string]bool{}
for _, c := range left {
	m[c] = true
}
isSuperset := true
for _, c := range right {
	if !m[c] {
		isSuperset = false
		break
	}
}
fmt.Println(isSuperset)
// Or in functional style.
fmt.Println(!slices.ContainsFunc(right, func(c string) bool { return !m[c] }))
// A typical `mapset` would copy both slices, which makes early exits irrelevant.
// Or it only solves half the problem.
s := Set(left...)
fmt.Println(!slices.ContainsFunc(right, func(c string) bool { return !s.Contains(c) }))
// Whereas `iterset` methods have in-lined logic with minimal copying and early exits.
fmt.Println(Set(left...).IsSuperset(slices.Values(right)))
Output:

false
false
false
false
Example (Unique)

Remove duplicates, retaining original order.

values := []string{"a", "b", "a"}
// With no sets.
m := map[string]bool{}
keys := []string{}
for _, c := range values {
	if !m[c] {
		keys = append(keys, c)
	}
	m[c] = true
}
fmt.Println(keys)
// A typical `mapset` would either have no impact on readability, or lose ordering.
// Whereas `iterset` has this built-in with lazy iteration.
for c := range Unique(slices.Values(values)) {
	fmt.Println(c)
}
// What if a `set` is still needed, in addition to ordering.
idx := Index(slices.Values(values))
fmt.Println(idx)
fmt.Println(Sorted(idx)) // keys sorted by value
Output:

[a b]
a
b
map[a:0 b:1]
[a b]

Index

Examples

Constants

This section is empty.

Variables

This section is empty.

Functions

func Compact added in v0.3.0

func Compact[K comparable](keys iter.Seq[K]) iter.Seq2[K, int]

Compact returns consecutive runs of deduplicated keys, with counts.

Related:

Example
k := slices.Values([]string{"b", "b", "a", "a", "b"})
for key, count := range Compact(k) {
	fmt.Println(key, count)
}
Output:

b 2
a 2
b 1

func CompactBy added in v0.3.0

func CompactBy[K comparable, V any](values iter.Seq[V], key func(V) K) iter.Seq2[K, []V]

CompactBy is like Compact but uses a key function and collects all values.

Related:

Example
v := slices.Values([]string{"B", "b", "A", "a", "b"})
for key, values := range CompactBy(v, strings.ToLower) {
	fmt.Println(key, values)
}
Output:

b [B b]
a [A a]
b [b]

func CompareValues added in v0.5.0

func CompareValues[K comparable, V cmp.Ordered](m map[K]V) func(K, K) int

CompareValues returns a function which compares by value.

Related:

Example
c := CompareValues(Index(slices.Values([]string{"c", "b", "a"})))
fmt.Println(slices.SortedFunc(slices.Values([]string{"a", "b"}), c))
Output:

[b a]

func Difference added in v0.2.0

func Difference[K comparable](keys iter.Seq[K], seqs ...iter.Seq[K]) iter.Seq[K]

Difference returns the ordered keys which are not present in the sequence(s).

Related:

Performance:

  • time: O(k)
  • space: O(k)
Example
s1 := slices.Values([]string{"a", "b"})
s2 := slices.Values([]string{"b", "c"})
fmt.Println(slices.Collect(Difference(s1, s2)))
Output:

[a]

func Equal added in v0.4.0

func Equal[K comparable](keys, seq iter.Seq[K]) bool

Equal returns whether the sets of keys are equal.

Related:

Performance:

  • time: O(k)
  • space: O(k)
Example
k := slices.Values([]string{"b", "a", "b"})
s := slices.Values([]string{"a"})
fmt.Println(Equal(k, slices.Values([]string{"a", "b"})), Equal(k, s), Equal(k, s))
Output:

true false false

func EqualCounts added in v0.4.0

func EqualCounts[K comparable](keys, seq iter.Seq[K]) bool

EqualCounts returns whether the multisets of keys are equal.

Related:

Performance:

  • time: O(k)
  • space: O(k)
Example
k := slices.Values([]string{"b", "a", "b"})
s := slices.Values([]string{"a", "b"})
fmt.Println(EqualCounts(k, k), EqualCounts(k, s), EqualCounts(s, k))
Output:

true false false

func GoIter added in v0.4.0

func GoIter[V any](seq iter.Seq[V], size int) iter.Seq[V]

GoIter iterates the sequence in a background goroutine and channel. An unbuffered channel (size 0) is sufficient for parallelism, but channels introduce overhead. As always, benchmark first.

Example
s := slices.Values([]string{"a", "b", "c"})
fmt.Println(slices.Collect(GoIter(s, 0)))
Output:

[a b c]

func Intersect added in v0.3.0

func Intersect[K comparable](keys iter.Seq[K], seqs ...iter.Seq[K]) iter.Seq[K]

Intersect returns the ordered keys which are present in the sequence(s).

Related:

Performance:

  • time: O(k)
  • space: O(k)
Example
s1 := slices.Values([]string{"a", "b"})
s2 := slices.Values([]string{"d", "c", "b"})
fmt.Println(slices.Collect(Intersect(s1, s2)))
Output:

[b]

func IsDisjoint added in v0.4.0

func IsDisjoint[K comparable](keys, seq iter.Seq[K]) bool

IsDisjoint returns whether no keys are present in the sequence.

Related:

Performance:

  • time: O(k)
  • space: O(k)
Example
k := slices.Values([]string{"a"})
s1 := slices.Values([]string{"b"})
s2 := slices.Values([]string{"b", "a"})
fmt.Println(IsDisjoint(k, s1), IsDisjoint(k, s2), IsDisjoint(s2, k))
Output:

true false false

func IsEmpty added in v0.4.0

func IsEmpty[V any](seq iter.Seq[V]) bool

IsEmpty returns where there are no values in a sequence.

Example
s := slices.Values([]int{})
fmt.Println(IsEmpty(s))
Output:

true

func IsSubset added in v0.2.0

func IsSubset[K comparable](keys, seq iter.Seq[K]) bool

IsSubset returns whether all keys are present in the sequence.

Related:

Performance:

  • time: O(k)
  • space: O(k)
Example
s1 := slices.Values([]string{"a"})
s2 := slices.Values([]string{"a", "b"})
fmt.Println(IsSubset(s1, s2), IsSubset(s2, s1))
Output:

true false

func Keys added in v0.4.0

func Keys[K, V any](seq iter.Seq2[K, V]) iter.Seq[K]

Keys returns the keys from a sequence of pairs.

Related:

Example
s := slices.All([]string{"a", "b", "c"})
fmt.Println(slices.Collect(Keys(s)))
Output:

[0 1 2]

func Max added in v0.3.0

func Max[K any, V cmp.Ordered](seq iter.Seq2[K, V]) []K

Max returns the key(s) with the maximum corresponding value. Will be empty only if the sequence is empty.

Related:

Example
s := Max(maps.All(map[string]int{"a": 2, "b": 2, "c": 1}))
slices.Sort(s)
fmt.Println(s)
Output:

[a b]

func Min added in v0.3.0

func Min[K any, V cmp.Ordered](seq iter.Seq2[K, V]) []K

Min returns the key(s) with the minimum corresponding value. Will be empty only if the sequence is empty.

Related:

Example
s := Min(maps.All(map[string]int{"a": 2, "b": 1, "c": 1}))
slices.Sort(s)
fmt.Println(s)
Output:

[b c]

func Size added in v0.4.0

func Size[V any](seq iter.Seq[V]) int

Size returns the number of values in a sequence.

Example
s := slices.Values([]int{0, 0, 0})
fmt.Println(Size(s))
Output:

3

func Sorted

func Sorted[K comparable, V cmp.Ordered](m map[K]V) []K

Sorted returns keys ordered by corresponding value.

Related:

Example
fmt.Println(Sorted(Index(slices.Values([]string{"b", "a", "b"}))))
Output:

[b a]

func SortedDifference added in v0.4.0

func SortedDifference[K cmp.Ordered](keys, seq iter.Seq[K]) iter.Seq[K]

SortedDifference returns the difference of sorted keys.

Performance:

  • time: O(k)
Example
s1, s2 := slices.Values([]string{"b", "c"}), slices.Values([]string{"a", "b", "d"})
fmt.Println(slices.Collect(SortedDifference(s1, s2)))
Output:

[c]

func SortedIntersect added in v0.4.0

func SortedIntersect[K cmp.Ordered](keys, seq iter.Seq[K]) iter.Seq[K]

SortedIntersect returns the intersection of sorted keys.

Performance:

  • time: O(k)
Example
s1, s2 := slices.Values([]string{"b", "c"}), slices.Values([]string{"a", "b", "d"})
fmt.Println(slices.Collect(SortedIntersect(s1, s2)))
Output:

[b]

func SortedUnion added in v0.4.0

func SortedUnion[K cmp.Ordered](keys, seq iter.Seq[K]) iter.Seq[K]

SortedUnion returns the union of sorted keys.

Related:

Performance:

  • time: O(k)
Example
s1, s2 := slices.Values([]string{"b", "c"}), slices.Values([]string{"a", "b", "d"})
fmt.Println(slices.Collect(SortedUnion(s1, s2)))
Output:

[a b b c d]

func Unique

func Unique[K comparable](keys iter.Seq[K]) iter.Seq[K]

Unique returns keys in order without duplicates.

Related:

  • Index to return a map
  • Compact if the keys are already grouped

Performance:

  • time: O(k)
  • space: O(k)
Example
k := slices.Values([]string{"b", "a", "b"})
fmt.Println(slices.Collect(Unique(k)))
Output:

[b a]

func UniqueBy added in v0.3.0

func UniqueBy[K comparable, V any](values iter.Seq[V], key func(V) K) iter.Seq2[K, V]

UniqueBy is like Unique but uses a key function to compare values. For values that compare equal, the first key-value pair is returned.

Related:

Performance:

  • time: O(k)
  • space: O(k)
Example
v := slices.Values([]string{"B", "a", "b"})
for key, value := range UniqueBy(v, strings.ToLower) {
	fmt.Println(key, value)
}
Output:

b B
a a

Types

type MapSet

type MapSet[K comparable, V any] map[K]V

MapSet is a `map` extended with set methods.

func Cast

func Cast[K comparable, V any](m map[K]V) MapSet[K, V]

Cast returns a zero-copy MapSet. Equivalent to `MapSet[K, V](m)` without having to specify concrete types.

An instantiated type alias would have the same functionality. Methods can also be called as unbound functions: `MapSet[K, V].Method(m, ...)`.

Example
m := map[string]bool{}
Cast(m).Add("a")
fmt.Println(m)
// equivalent to
type aSet = MapSet[string, bool]
aSet(m).Add("a")
aSet.Add(m, "a'")
Output:

map[a:false]

func Collect added in v0.2.0

func Collect[K comparable, V any](keys iter.Seq[K], value V) MapSet[K, V]

Collect returns unique keys with a default value. Equivalent to Set when value is `struct{}{}`.

Related:

Example
k := slices.Values([]string{"b", "a", "b"})
fmt.Println(Collect(k, true))
Output:

map[a:true b:true]

func Count

func Count[K comparable](keys iter.Seq[K]) MapSet[K, int]

Count returns unique keys with their counts.

Related:

  • Compact if the keys are already grouped
Example
fmt.Println(Count(slices.Values([]string{"b", "a", "b"})))
Output:

map[a:1 b:2]

func Group added in v0.5.0

func Group[K comparable, V any](seq iter.Seq2[K, V]) MapSet[K, []V]

Group returns values grouped by keys.

Related:

Example
seq := func(yield func(string, int) bool) {
	_ = yield("a", 1) && yield("b", 2) && yield("a", 3)
}
fmt.Println(Group(seq))
Output:

map[a:[1 3] b:[2]]

func GroupBy

func GroupBy[K comparable, V any](values iter.Seq[V], key func(V) K) MapSet[K, []V]

GroupBy returns values grouped by key function.

Related:

  • IndexBy to retain single value
  • CompactBy if the values are already grouped by key
Example
v := slices.Values([]string{"B", "a", "b"})
fmt.Println(GroupBy(v, strings.ToLower))
Output:

map[a:[a] b:[B b]]

func Index

func Index[K comparable](keys iter.Seq[K]) MapSet[K, int]

Index returns unique keys with their first index position.

Related:

  • Unique to return an ordered sequence
  • Sorted to restore original order
Example
fmt.Println(Index(slices.Values([]string{"b", "a", "b"})))
Output:

map[a:1 b:0]

func IndexBy

func IndexBy[K comparable, V any](values iter.Seq[V], key func(V) K) MapSet[K, V]

IndexBy returns values indexed by key function. If there are collisions, the last value remains.

Related:

Example
v := slices.Values([]string{"B", "a", "b"})
fmt.Println(IndexBy(v, strings.ToLower))
Output:

map[a:a b:b]

func Memoize added in v0.2.0

func Memoize[K comparable, V any](keys iter.Seq[K], f func(K) V) MapSet[K, V]

Memoize caches function call.

Example
fmt.Println(Memoize(slices.Values([]string{"b", "a", "b"}), strings.ToUpper))
Output:

map[a:A b:B]

func Reduce added in v0.5.0

func Reduce[K comparable, V any](seq iter.Seq2[K, V], f func(V, V) V) MapSet[K, V]

Reduce combines values grouped by keys with binary function.

Related:

  • Group to collect into a slice
Example
seq := func(yield func(string, int) bool) {
	_ = yield("a", 1) && yield("b", 2) && yield("a", 3)
}
fmt.Println(Reduce(seq, func(i, j int) int { return i + j }))
Output:

map[a:4 b:2]

func Set

func Set[K comparable](keys ...K) MapSet[K, struct{}]

Set returns unique keys with an empty struct value.

Related:

Example
fmt.Println(Set("b", "a", "b"))
Output:

map[a:{} b:{}]

func (MapSet[K, V]) Add

func (m MapSet[K, V]) Add(keys ...K)

Add key(s) with zero value.

Related:

Example
s := Set("a", "b")
s.Add("b", "c")
fmt.Println(len(s))
Output:

3

func (MapSet[K, V]) Contains

func (m MapSet[K, V]) Contains(key K) bool

Contains returns whether the key is present.

Related:

Example
s := Set("b", "a", "b")
fmt.Println(s.Contains("a"), s.Contains("c"))
Output:

true false

func (MapSet[K, V]) Delete

func (m MapSet[K, V]) Delete(keys ...K)

Delete key(s).

Related:

Example
s := Set("a", "b")
s.Delete("b", "c")
fmt.Println(len(s))
Output:

1

func (MapSet[K, V]) Difference

func (m MapSet[K, V]) Difference(keys iter.Seq[K]) iter.Seq2[K, V]

Difference returns the key-value pairs which are not present in the keys.

Related:

Performance:

  • time: O(m+k)
  • space: O(min(m,k))
Example
k := slices.Values([]string{"b", "c"})
fmt.Println(maps.Collect(Set("a", "b").Difference(k)))
Output:

map[a:{}]

func (MapSet[K, V]) Equal added in v0.2.0

func (m MapSet[K, V]) Equal(keys iter.Seq[K]) bool

Equal returns whether the key sets are equivalent.

Related:

Performance:

  • time: O(k)
  • space: O(min(m, k))
Example
k := slices.Values([]string{"b", "a", "b"})
fmt.Println(Set("a", "b").Equal(k), Set("a").Equal(k))
Output:

true false

func (MapSet[K, V]) Insert added in v0.2.0

func (m MapSet[K, V]) Insert(keys iter.Seq[K], value V)

Insert keys with default value.

Related:

Example
m := MapSet[string, bool]{}
m.Insert(slices.Values([]string{"b", "a", "b"}), true)
fmt.Println(m)
Output:

map[a:true b:true]

func (MapSet[K, V]) Intersect

func (m MapSet[K, V]) Intersect(keys iter.Seq[K]) iter.Seq2[K, V]

Intersect returns the ordered key-value pairs which are present in both.

Performance:

  • time: O(k)
Example
m := MapSet[string, int]{"a": 0, "b": 1}
s := slices.Values([]string{"b", "c"})
for key, value := range m.Intersect(s) {
	fmt.Println(key, value)
}
Output:

b 1

func (MapSet[K, V]) IsDisjoint

func (m MapSet[K, V]) IsDisjoint(keys iter.Seq[K]) bool

IsDisjoint returns whether no keys are present.

Performance:

  • time: O(k)
Example
k := slices.Values([]string{"b", "a", "b"})
fmt.Println(Set("c").IsDisjoint(k), Set("a").IsDisjoint(k))
Output:

true false

func (MapSet[K, V]) IsSubset added in v0.2.0

func (m MapSet[K, V]) IsSubset(keys iter.Seq[K]) bool

IsSubset returns whether every map key is present in keys.

Related:

Performance:

  • time: O(k)
  • space: O(min(m, k))
Example
k := slices.Values([]string{"b", "a", "b"})
fmt.Println(Set("a").IsSubset(k), Set("a", "c").IsSubset(k))
Output:

true false

func (MapSet[K, V]) IsSuperset

func (m MapSet[K, V]) IsSuperset(keys iter.Seq[K]) bool

IsSuperset returns whether all keys are present.

Performance:

  • time: O(k)
Example
k := slices.Values([]string{"b", "a", "b"})
fmt.Println(Set("a", "b").IsSuperset(k), Set("a").IsSuperset(k))
Output:

true false

func (MapSet[K, V]) Missing

func (m MapSet[K, V]) Missing(key K) bool

Missing returns whether the key is not present. Negation of MapSet.Contains; useful to pass as a bound method.

Related:

Example
s := Set("b", "a", "b")
fmt.Println(s.Missing("a"), s.Missing("c"))
Output:

false true

func (MapSet[K, V]) Overlap added in v0.5.0

func (m MapSet[K, V]) Overlap(keys iter.Seq[K]) (int, int, int)

Overlap returns the sizes of the intersection and differences: left only, both, right only.

Similarity measures:

  • overlap coefficient: both / (min(left, right) + both)
  • Jaccard index: both / (left + both + right)

Performance:

  • time: Θ(k)
  • space: Θ(k)
Example
s, k := Set("a", "b", "c"), []string{"b", "c", "d"}
fmt.Println(s.Overlap(slices.Values(k)))
Output:

1 2 1

func (MapSet[K, V]) Remove added in v0.3.0

func (m MapSet[K, V]) Remove(keys iter.Seq[K])

Remove keys.

Related:

Example
s := Set("a", "b")
s.Remove(slices.Values([]string{"b", "c"}))
fmt.Println(s)
Output:

map[a:{}]

func (MapSet[K, V]) ReverseDifference added in v0.2.0

func (m MapSet[K, V]) ReverseDifference(keys iter.Seq[K]) iter.Seq[K]

ReverseDifference returns the ordered keys which are not present in the map. Also known as the relative complement.

Performance:

  • time: O(k)
Example
k := slices.Values([]string{"b", "c"})
fmt.Println(slices.Collect(Set("a", "b").ReverseDifference(k)))
Output:

[c]

func (MapSet[K, V]) SymmetricDifference added in v0.2.0

func (m MapSet[K, V]) SymmetricDifference(keys iter.Seq[K]) iter.Seq[K]

SymmetricDifference returns keys which are not in both.

Related:

Performance:

  • time: O(m+k)
  • space: O(min(m, k))
Example
k := slices.Values([]string{"b", "c"})
fmt.Println(slices.Collect(Set("a", "b").SymmetricDifference(k)))
Output:

[c a]

func (MapSet[K, V]) Toggle added in v0.3.0

func (m MapSet[K, V]) Toggle(keys iter.Seq[K], value V)

Toggle removes present keys, and inserts missing keys.

Related:

Example
s := Set("a", "b")
s.Toggle(maps.Keys(Set("b", "c")), struct{}{})
fmt.Println(s)
Output:

map[a:{} c:{}]

func (MapSet[K, V]) Union added in v0.2.0

func (m MapSet[K, V]) Union(seqs ...iter.Seq2[K, V]) MapSet[K, V]

Union merges all keys with successive inserts.

Related:

Performance:

  • time: Θ(m+k)
  • space: Ω(max(m, k))..O(m+k)
Example
m := map[string]int{"a": 0, "b": 1}
n := map[string]int{"b": 2, "c": 3}
fmt.Println(Cast(m).Union(maps.All(n)))
Output:

map[a:0 b:2 c:3]

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL