README
¶
Sets
A dead-simple library to handle quick and dirty sets.
Install
go get github.com/mcvoid/sets
What's up with sets?
We've all improvised set types in Go. Using a map like map[MyObj]struct{}, it works okay.
But if we want some set operations like union, you have to roll your own. And it doesn't
preserve order. You need a slice for that, but then you have to roll your own deduplication.
I did that all for you. And it'll work on all your custom improvised set types. Now that that's over with, you can get on with the task at hand.
Ordered vs Unordered
There's basically two sets of set functions in this library: ordered set functions, and unordered set functions.
Unordered sets are maps, like given above. Any map can be made to act like a set, and these functions act on these. Any function that has "Unordered" in its name works on all maps. If you created your own type that uses a map as underlying storage, that works too. These are:
UnorderedUnionUnorderedComplementUnorderedIntersectIsUnorderedSubsetOf
Ordered sets are slices. Any slice of a comparable type (if it can be used as a map key, it's comparable), these functions can acts on those as well. You just use the functions with "Ordered" in their name. These are:
OrderedUnionOrderedComplementOrderedIntersectIsOrderedSubsetOf
How to use
These functions work with plain slices and maps:
a := sets.OrderedUnion([]string{"a", "b"}, []string{"b", "c"})
fmt.Println(a) // prints ["a", "b", "c"]
s1 := map[string]struct{}{"a": {}, "b": {}}
s2 := map[string]struct{}{"c": {}, "b": {}}
b := sets.UnorderedIntersect(s1, s2)
fmt.Println(b) // prints {"b":{}}
They can also be used for user-defined types based on slices and maps:
type MySet []string
type MyUSet map[int]any
...
s1 := MySet{"foo", "bar", "baz"}
s2 := MySet{"baz"}
c := sets.OrderedComplement(s1, s2) // is type MySet
fmt.Println(c) // prints ["foo", "bar"]
s3 := MyUSet{1: nil, 2: nil, 3: nil, 4: nil}
s4 := MyUSet{2: nil, 3: nil, 4: nil}
d := sets.IsUnorderedSubsetOf(s3, s4)
fmt.Println(d) // prints true
Tips and Tricks
You can easily do a surprising amount of things with just those functions...
// append an item to a set
s1 = sets.OrderedUnion(s1, []string{"item to add"})
// prepend an item to a set
s1 = sets.OrderedUnion([]string{"item to add"}, s1)
// remove an item from a set
s1 = sets.OrderedComplement(s1, []string{"item to remove"})
// check if a set contains an item
containsItem := sets.IsOrderedSubsetOf(s1, []string{"item to find"})
// clone a set
s2 := sets.OrderedUnion(nil, s1)
// deduplicate a slice
s1 = sets.OrderedUnion(s1)
// splice in elems at point i
s1 = sets.OrderedUnion(s1[:i], []string{"a", "b", "c"}, s1[i:])
...but if you don't want to remember those, I put added helper functions for all of those and more. Check out the docs for a complete function list.
License
Released under the MIT license.
Documentation
¶
Overview ¶
A simple library for managing slices and maps as sets.
All OrderedX functions (eg: OrderedUnion) work with slices or any type based on a slice as long as the slice elements are comparable. These slices are treated as ordered sets.
For slices, all operations here automatically remove duplicates and preserve the order of the elements in the original slice. Whenever possible, they also seek to avoid allocations. So they preserve nilness, they don't make a new set out of a slice which already adheres to the set property, etc. All operations are variadic and applied left-to-right (index 0 and up).
It's "naive" in that it has no tricks to speed up performance. It will deliberately sacrifice cycles to favor avoiding an allocation, for example.
All UnorderedX functions (eg: UnorderedUnion) work with maps and any type based on a map. Since all map keys are already comparable, there is no restriction to their use. These maps are treated as unordered sets.
For maps, no order is preserved and the operations are faster. Allocations are still avoided. Map keys are treated as the set elements, not their values. As such, values found in duplicate keys will be clobbered. This mimics the conventional use of maps as ad-hoc sets, so they should work in the same way. Whenever possible, the values for the first given set will be in the output.
As "nil" is common nomenclature for the empty set ({}, or 0), nil is accepted as input to mean an empty slice or empty map, and empty set results such as the intersection of disjoint sets are similarly returned as nil.
All sets are treated as if immutable - no modifications will occur on any of these operations, and instead copies will be returned.
Index ¶
- func Append[S ~[]E, E comparable](s S, e ...E) S
- func CloneOrderedSet[S ~[]E, E comparable](s S) S
- func CloneUnorderedSet[S ~map[K]V, K comparable, V any](s S) S
- func Deduplicate[S ~[]E, E comparable](s S) S
- func Insert[S ~map[K]V, K comparable, V any](s S, e S) S
- func IsOrderedSubsetOf[S ~[]E, E comparable](super, sub S) bool
- func IsUnorderedSubsetOf[S ~map[K]V, K comparable, V any](super, sub S) bool
- func OrderedComplement[S ~[]E, E comparable](sets ...S) S
- func OrderedIntersect[S ~[]E, E comparable](sets ...S) S
- func OrderedRemove[S ~[]E, E comparable](s S, e ...E) S
- func OrderedUnion[S ~[]E, E comparable](sets ...S) S
- func Prepend[S ~[]E, E comparable](s S, e ...E) S
- func RemoveFirstN[S ~[]E, E comparable](s S, n int) S
- func RemoveLastN[S ~[]E, E comparable](s S, n int) S
- func Splice[S ~[]E, E comparable](s S, i int, e ...E) S
- func UnorderedComplement[S ~map[K]V, K comparable, V any](sets ...S) S
- func UnorderedIntersect[S ~map[K]V, K comparable, V any](sets ...S) S
- func UnorderedRemove[S ~map[K]V, K comparable, V any](s S, k K) S
- func UnorderedUnion[S ~map[K]V, K comparable, V any](sets ...S) S
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func Append ¶ added in v1.1.0
func Append[S ~[]E, E comparable](s S, e ...E) S
Helper function. Equivalent to OrderedUnion(s, e)
func CloneOrderedSet ¶ added in v1.1.0
func CloneOrderedSet[S ~[]E, E comparable](s S) S
Helper function. Equivalent to OrderedUnion(nil, s)
func CloneUnorderedSet ¶ added in v1.1.0
func CloneUnorderedSet[S ~map[K]V, K comparable, V any](s S) S
Helper function. Equivalent to UnorderedUnion(nil, s)
func Deduplicate ¶ added in v1.1.0
func Deduplicate[S ~[]E, E comparable](s S) S
Helper function. Equivalent to OrderedUnion(s)
func Insert ¶ added in v1.1.0
func Insert[S ~map[K]V, K comparable, V any](s S, e S) S
Helper function. Equivalent to UnorderedUnion(e, s)
func IsOrderedSubsetOf ¶
func IsOrderedSubsetOf[S ~[]E, E comparable](super, sub S) bool
Returns whether sub is a subset of super. It is a subset if and only if every element in sub is also in super.
This version is meant to be for slices.
func IsUnorderedSubsetOf ¶
func IsUnorderedSubsetOf[S ~map[K]V, K comparable, V any](super, sub S) bool
Returns whether sub is a subset of super. It is a subset if and only if every key in sub is also in super.
This version is meant to be for maps.
func OrderedComplement ¶
func OrderedComplement[S ~[]E, E comparable](sets ...S) S
Produces the relative complements of slices as sets. The output will be all elements of the first argument which do not appear in any the the rest of the input slices, without suplicates. Preserves order.
Each argument is getting complemented to the relative complement of the previous two arguments. Applies in left-to-right order, so OrderedComplement(a, b, c) is the set of all elements in a not in b, and also not in c.
func OrderedIntersect ¶
func OrderedIntersect[S ~[]E, E comparable](sets ...S) S
Produces the intersection of slices as sets. The output will be a new slice containing the elements in all input slices, without duplicates. Preserves order.
Each argument is getting intersected with the intersection of the previous two arguments.
func OrderedRemove ¶ added in v1.1.0
func OrderedRemove[S ~[]E, E comparable](s S, e ...E) S
Helper function. Equivalent to OrderedComplement(s, e)
func OrderedUnion ¶
func OrderedUnion[S ~[]E, E comparable](sets ...S) S
Produces the union of slices as sets. The output will be a new slice containing the elements of all input slices, without duplicates. Preserves order.
func Prepend ¶ added in v1.1.0
func Prepend[S ~[]E, E comparable](s S, e ...E) S
Helper function. Equivalent to OrderedUnion(S{e}, s)
func RemoveFirstN ¶ added in v1.1.0
func RemoveFirstN[S ~[]E, E comparable](s S, n int) S
Helper function. Equivalent to OrderedComplement(s, S{s[n-1]})
func RemoveLastN ¶ added in v1.1.0
func RemoveLastN[S ~[]E, E comparable](s S, n int) S
Helper function. Equivalent to OrderedComplement(s, S{s[len(s)-n]})
func Splice ¶ added in v1.1.0
func Splice[S ~[]E, E comparable](s S, i int, e ...E) S
Helper function. Equivalent to OrderedUnion(s[:i], e, s[i:])
func UnorderedComplement ¶
func UnorderedComplement[S ~map[K]V, K comparable, V any](sets ...S) S
Produces the relative complement of maps as sets, where the maps' keys are the set's members. The output will be a new map with the keys of the first argument which do not appear in the rest of the input maps.
func UnorderedIntersect ¶
func UnorderedIntersect[S ~map[K]V, K comparable, V any](sets ...S) S
Produces the intersection of maps as sets, where the maps' keys are the set's members. The output will be a new map where the keys are the ones of the first given set which also appear in every other given set.
The values are those of the first set for they keys still remaining after intersection.
func UnorderedRemove ¶ added in v1.1.0
func UnorderedRemove[S ~map[K]V, K comparable, V any](s S, k K) S
Helper function. Equivalent to UnorderedComplement(s, S{k: v})
func UnorderedUnion ¶
func UnorderedUnion[S ~map[K]V, K comparable, V any](sets ...S) S
Produces the union of maps as sets, where the maps' keys are the set's members. The output will be a new map containing the keys of all the sets. Union is applied in argument order, with the values of repeated keys clobbering each other, so the last value applied for a key us what's in the set.
Types ¶
This section is empty.
Source Files