iterset

package module
v0.3.0 Latest Latest
Warning

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

 Go to latest Published: Jan 26, 2025 License: Apache-2.0 Imports: 4 Imported by: 0

README

build codecov go report

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

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
  • GroupBy stores slices grouped by key function
  • Memoize caches function call

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

Some operations are better expressed as functions, to avoid making unnecessary maps.

  • Sorted
  • IsSubset
  • Intersect
  • Difference

Installation

No dependencies. Go >=1.23 required.

go get github.com/coady/iterset

Tests

100% code coverage.

go test -cover

Documentation

Overview

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

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 
items := []item{{id: "b"}, {id: "b"}, {id: "a"}, {id: "a"}, {id: "b"}}
for key, values := range CompactBy(slices.Values(items), item.Id) {
	fmt.Println(key, values)
}

Output:

b [{b} {b}]
a [{a} {a}]
b [{b}]

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: Θ(k)
  • space: Θ(k)
Example 
s1 := slices.Values([]string{"a", "b"})
s2 := slices.Values([]string{"b", "c"})
fmt.Println(slices.Collect(Difference(s1, s2)))

Output:

[a]

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: Θ(k)
  • space: Θ(k)
Example 
s1 := slices.Values([]string{"a", "b"})
s2 := slices.Values([]string{"b", "c"})
fmt.Println(slices.Collect(Intersect(s1, s2)))

Output:

[b]

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: Θ(k)
  • space: Θ(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 Max added in v0.3.0 

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

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

Related:

  • Count to rank by frequency
Example 
s := Max(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 comparable, V cmp.Ordered](m map[K]V) []K

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

Related:

  • Count to rank by frequency
Example 
s := Min(map[string]int{"a": 2, "b": 1, "c": 1})
slices.Sort(s)
fmt.Println(s)

Output:

[b c]

func Sorted 

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

Sorted returns keys ordered by corresponding value.

Related:

  • Index to retain original order
  • Count to rank by frequency
Example 
fmt.Println(Sorted(Index(slices.Values([]string{"b", "a", "b"}))))

Output:

[b a]

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 
items := []item{{id: "b"}, {id: "a"}, {id: "b"}}
for key, value := range UniqueBy(slices.Values(items), item.Id) {
	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.

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.

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 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 
items := []item{{id: "b"}, {id: "a"}, {id: "b"}}
fmt.Println(GroupBy(slices.Values(items), item.Id))

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 
items := []item{{id: "b"}, {id: "a"}, {id: "b"}}
fmt.Println(IndexBy(slices.Values(items), item.Id))

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 Set 

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

Set returns unique keys with an empty struct value.

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(keys ...K) bool

Contains returns whether the key(s) is present.

Related:

Example 
s := Set("b", "a", "b")
fmt.Println(s.Contains("a"), s.Contains("b", "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:

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)

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]) 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.

  • time: O(k)

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(seq iter.Seq2[K, V])

Toggle removes present keys, and inserts missing keys.

Related:

Example 
s := Set("a", "b")
s.Toggle(maps.All(Set("b", "c")))
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]

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.
JackTT - Gopher 🇻🇳