blob: 8820c9ace435f2ba2690c30a450afbd6073294ba [file] [log] [blame]
// Package sets provides functions for operations on sets.
package sets
import "go.skia.org/infra/go/skerr"
// dup makes a copy of an int slice.
func dup(s []int) []int {
ret := make([]int, len(s))
copy(ret, s)
return ret
}
// allZeroes returns true if every int in a slice is zero.
func allZeroes(s []int) bool {
for _, n := range s {
if n != 0 {
return false
}
}
return true
}
// CartesianProduct returns a channel that lists all the combinations of
// elements from the given setSizes to produce the Cartesian Product of all the
// values in the sets.
//
// For example:
//
// CartesianProduct([]int{3, 2})
//
// Will produce the following int slices:
//
// {2, 1},
// {1, 1},
// {0, 1},
// {2, 0},
// {1, 0},
// {0, 0},
//
// Each setSize must be greater than one.
func CartesianProduct(setSizes []int) (<-chan []int, error) {
ret := make(chan []int)
if len(setSizes) == 0 {
close(ret)
return ret, nil
}
for _, n := range setSizes {
if n < 1 {
return nil, skerr.Fmt("set size must be >= 1, got %d", n)
}
}
// Convert the set sizes to indices by subtracting one.
setMaxIndex := dup(setSizes)
for i := range setMaxIndex {
setMaxIndex[i]--
}
// curent is the current set of indices we are going to emit on the channel.
current := dup(setMaxIndex)
go func() {
for {
ret <- dup(current)
if allZeroes(current) {
close(ret)
break
}
// Decrement current.
current[0]--
for i := 1; i < len(current); i++ {
if current[i-1] < 0 {
current[i-1] = setMaxIndex[i-1]
current[i]--
}
}
}
}()
return ret, nil
}