README
¶
set 
Package set provides type-safe, polymorphic mathematical set operations that operate on any sort.Interface implementation.
Documentation: http://godoc.org/github.com/xtgo/set
Talk: https://go-talks.appspot.com/github.com/xtblog/gotalks/sets.slide
Documentation
¶
Overview ¶
Package set implements type-safe, non-allocating algorithms that operate on ordered sets.
Most functions take a data parameter of type sort.Interface and a pivot parameter of type int; data represents two sets covering the ranges [0:pivot] and [pivot:Len], each of which is expected to be sorted and free of duplicates. sort.Sort may be used for sorting, and Uniq may be used to filter away duplicates.
All mutating functions swap elements as necessary from the two input sets to form a single output set, returning its size: the output set will be in the range [0:size], and will be in sorted order and free of duplicates. Elements which were moved into the range [size:Len] will have undefined order and may contain duplicates.
All pivots must be in the range [0:Len]. A panic may occur when invalid pivots are passed into any of the functions.
Convenience functions exist for slices of int, float64, and string element types, and also serve as examples for implementing utility functions for other types.
Elements will be considered equal if `!Less(i,j) && !Less(j,i)`. An implication of this is that NaN values are equal to each other.
Example ¶
package main
import (
"fmt"
"github.com/xtgo/set"
)
func main() {
s := set.Strings([]string{"alpha", "gamma", "alpha"})
fmt.Println("set:", s)
s = set.StringsDo(set.Union, s, "beta")
fmt.Println("set + beta:", s)
fmt.Println(s, "contains any [alpha delta]:",
set.StringsChk(set.IsInter, s, "alpha", "delta"))
fmt.Println(s, "contains all [alpha delta]:",
set.StringsChk(set.IsSuper, s, "alpha", "delta"))
}
Output: set: [alpha gamma] set + beta: [alpha beta gamma] [alpha beta gamma] contains any [alpha delta]: true [alpha beta gamma] contains all [alpha delta]: false
Index ¶
- func Apply(op Op, data sort.Interface, pivots []int) (size int)
- func Diff(data sort.Interface, pivot int) (size int)
- func Float64s(data []float64) []float64
- func Float64sChk(cmp Cmp, s []float64, t ...float64) bool
- func Float64sDo(op Op, s []float64, t ...float64) []float64
- func Inter(data sort.Interface, pivot int) (size int)
- func Ints(data []int) []int
- func IntsChk(cmp Cmp, s []int, t ...int) bool
- func IntsDo(op Op, s []int, t ...int) []int
- func IsEqual(data sort.Interface, pivot int) bool
- func IsInter(data sort.Interface, pivot int) bool
- func IsSub(data sort.Interface, pivot int) bool
- func IsSuper(data sort.Interface, pivot int) bool
- func Pivots(sizes ...int) []int
- func Strings(data []string) []string
- func StringsChk(cmp Cmp, s []string, t ...string) bool
- func StringsDo(op Op, s []string, t ...string) []string
- func SymDiff(data sort.Interface, pivot int) (size int)
- func Union(data sort.Interface, pivot int) (size int)
- func Uniq(data sort.Interface) (size int)
- type Cmp
- type Op
- Bugs
Examples ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func Apply ¶
Apply concurrently applies op to all the sets terminated by pivots. pivots must contain one higher than the final index in each set, with the final element of pivots being equal to data.Len(); this deviates from the pivot semantics of other functions (which treat pivot as a delimiter) in order to make initializing the pivots slice simpler.
data.Swap and data.Less are assumed to be concurrent-safe. Only associative operations should be used (Diff is not associative); see the Apply (Diff) example for a workaround. The result of applying SymDiff will contain elements that exist in an odd number of sets.
The implementation runs op concurrently on pairs of neighbor sets in-place; when any pair has been merged, the resulting set is re-paired with one of its neighbor sets and the process repeats until only one set remains. The process is adaptive (large sets will not prevent small pairs from being processed), and strives for data-locality (only adjacent neighbors are paired and data shifts toward the zero index).
Example ¶
package main
import (
"fmt"
"sort"
"github.com/xtgo/set"
)
func main() {
sets := []sort.IntSlice{
{1, 3, 5, 7, 9}, // odds from 1
{3, 5, 7, 9, 11}, // odds from 3
{5, 10, 15, 20}, // 5-multiples
{2, 3, 5, 7, 11}, // primes
}
pivots := make([]int, len(sets))
var orig, data sort.IntSlice
// concatenate the sets together for use with the set package
for i, set := range sets {
pivots[i] = len(set)
orig = append(orig, set...)
}
// transform set sizes into pivots
pivots = set.Pivots(pivots...)
tasks := []struct {
name string
op set.Op
}{
{"union", set.Union},
{"inter", set.Inter},
{"sdiff", set.SymDiff},
}
for _, task := range tasks {
// make a copy of the original data (Apply rearranges the input)
data = append(data[:0], orig...)
size := set.Apply(task.op, data, pivots)
data = data[:size]
fmt.Printf("%s: %v\n", task.name, data)
}
}
Output: union: [1 2 3 5 7 9 10 11 15 20] inter: [5] sdiff: [1 2 3 7 10 15 20]
Example (Diff) ¶
package main
import (
"fmt"
"sort"
"github.com/xtgo/set"
)
func main() {
// a - b - c - d cannot be used with Apply (Diff is non-associative)
// a - (b + c + d) equivalent, using Apply (Union is associative)
sets := []sort.IntSlice{
{0, 2, 4, 6, 8, 10}, // positive evens
{0, 1, 2, 3, 5, 8}, // set of fibonacci numbers
{5, 10, 15}, // positive 5-multiples
{2, 3, 5, 7, 11, 13}, // primes
}
var data sort.IntSlice
// for use with (b + c + d)
exprsets := sets[1:]
pivots := make([]int, len(exprsets))
// concatenate the sets together for use with the set package
for i, set := range exprsets {
pivots[i] = len(set)
data = append(data, set...)
}
// transform set sizes into pivots
pivots = set.Pivots(pivots...)
// calculate x = (b + c + d)
size := set.Apply(set.Union, data, pivots)
// concatenate the result to the end of a
data = append(sets[0], data[:size]...)
// calculate a - x
size = set.Diff(data, len(sets[0]))
data = data[:size]
fmt.Println("diff:", data)
}
Output: diff: [4 6]
func Diff ¶
Diff performs an in-place difference on the two sets [0:pivot] and [pivot:Len]; the resulting set will occupy [0:size]. Diff is neither associative nor commutative.
func Float64s ¶
Float64s sorts and deduplicates a slice of float64s in place, returning the resulting set.
func Float64sChk ¶
Float64sChk compares s and t according to cmp.
func Float64sDo ¶
Float64sDo applies op to the float64 sets, s and t, returning the result. s and t must already be individually sorted and free of duplicates.
func Inter ¶
Inter performs an in-place intersection on the two sets [0:pivot] and [pivot:Len]; the resulting set will occupy [0:size]. Inter is both associative and commutative.
Example ¶
package main
import (
"fmt"
"sort"
"github.com/xtgo/set"
)
func main() {
data := sort.IntSlice{3, 5, 7} // create a set (it must be sorted)
pivot := len(data) // store the length of our first set
data = append(data, 1, 3, 5) // append a second set (which also must be sorted)
size := set.Inter(data, pivot) // perform set intersection
// trim data to contain just the result set
data = data[:size]
fmt.Println("inter:", data)
}
Output: inter: [3 5]
func IntsDo ¶
IntsDo applies op to the int sets, s and t, returning the result. s and t must already be individually sorted and free of duplicates.
func IsInter ¶
IsInter returns true if any element in the range [0:pivot] is also present in the range [pivot:Len]. IsInter is especially useful for partial membership testing.
Example ¶
package main
import (
"fmt"
"sort"
"github.com/xtgo/set"
)
func main() {
data := sort.StringSlice{"b", "c", "d"} // create a set (it must be sorted)
pivot := len(data) // store the length of our first set
data = append(data, "d", "z") // append a second set (which also must be sorted)
contained := set.IsInter(data, pivot) // check the first set is a superset of the second
fmt.Printf("%v intersects %v = %t\n", data[:pivot], data[pivot:], contained)
data = data[:pivot] // trim off the second set
data = append(data, "s") // append a new singleton set to compare against
contained = set.IsInter(data, pivot) // check for membership
fmt.Printf("%v intersects %v = %t\n", data[:pivot], data[pivot:], contained)
}
Output: [b c d] intersects [d z] = true [b c d] intersects [s] = false
func IsSub ¶
IsSub returns true only if all elements in the range [0:pivot] are also present in the range [pivot:Len].
func IsSuper ¶
IsSuper returns true only if all elements in the range [pivot:Len] are also present in the range [0:pivot]. IsSuper is especially useful for full membership testing.
Example ¶
package main
import (
"fmt"
"sort"
"github.com/xtgo/set"
)
func main() {
data := sort.StringSlice{"b", "c", "d"} // create a set (it must be sorted)
pivot := len(data) // store the length of our first set
data = append(data, "c", "d") // append a second set (which also must be sorted)
contained := set.IsSuper(data, pivot) // check the first set is a superset of the second
fmt.Printf("%v superset of %v = %t\n", data[:pivot], data[pivot:], contained)
data = data[:pivot] // trim off the second set
data = append(data, "s") // append a new singleton set to compare against
contained = set.IsSuper(data, pivot) // check for membership
fmt.Printf("%v superset of %v = %t\n", data[:pivot], data[pivot:], contained)
}
Output: [b c d] superset of [c d] = true [b c d] superset of [s] = false
func Pivots ¶
Pivots transforms set-relative sizes into data-absolute pivots. Pivots is mostly only useful in conjunction with Apply. The sizes slice sizes may be modified by the call.
func Strings ¶
Strings sorts and deduplicates a slice of strings in place, returning the resulting set.
func StringsChk ¶
StringsChk compares s and t according to cmp.
func StringsDo ¶
StringsDo applies op to the string sets, s and t, returning the result. s and t must already be individually sorted and free of duplicates.
func SymDiff ¶
SymDiff performs an in-place symmetric difference on the two sets [0:pivot] and [pivot:Len]; the resulting set will occupy [0:size]. SymDiff is both associative and commutative.
func Union ¶
Union performs an in-place union on the two sets [0:pivot] and [pivot:Len]; the resulting set will occupy [0:size]. Union is both associative and commutative.
func Uniq ¶
Uniq swaps away duplicate elements in data, returning the size of the unique set. data is expected to be pre-sorted, and the resulting set in the range [0:size] will remain in sorted order. Uniq, following a sort.Sort call, can be used to prepare arbitrary inputs for use as sets.
Example ¶
package main
import (
"fmt"
"sort"
"github.com/xtgo/set"
)
func main() {
data := sort.IntSlice{5, 7, 3, 3, 5}
sort.Sort(data) // sort the data first
n := set.Uniq(data) // Uniq returns the size of the set
data = data[:n] // trim the duplicate elements
fmt.Println(data)
}
Output: [3 5 7]
Types ¶
Notes ¶
Bugs ¶
All ops should use binary search when runs are detected
Union currently uses a multi-pass implementation
SymDiff currently uses a multi-pass implementation
Source Files
¶
Directories
¶
| Path | Synopsis |
|---|---|
|
internal
|
|
|
mapset
Package mapset provides a reasonable map-based set implementation for use in comparative benchmarks, and to check arbitrary fuzz outputs.
|
Package mapset provides a reasonable map-based set implementation for use in comparative benchmarks, and to check arbitrary fuzz outputs. |
|
sliceset
Package sliceset provides a convenient []int set wrapper to aid in testing and benchmarks, and to serve as an example for those in need of a (concrete) abstraction for simplifying code.
|
Package sliceset provides a convenient []int set wrapper to aid in testing and benchmarks, and to serve as an example for those in need of a (concrete) abstraction for simplifying code. |