Documentation
¶
Overview ¶
Package slice implements some useful functions for slices.
Index ¶
- func At[T any, Slice ~[]T](ss Slice, i int) T
- func Batches[T any, Slice ~[]T](vs Slice, n int) iter.Seq[Slice]
- func Chunks[T any, Slice ~[]T](vs Slice, n int) iter.Seq[Slice]deprecated
- func Head[T any, Slice ~[]T](vs Slice, n int) Slice
- func LCS[T comparable, Slice ~[]T](as, bs Slice) Slice
- func LCSFunc[T any, Slice ~[]T](as, bs Slice, eq func(a, b T) bool) Slice
- func LIS[T cmp.Ordered, Slice ~[]T](vs Slice) Slice
- func LISFunc[T any, Slice ~[]T](vs Slice, cmp func(a, b T) int) Slice
- func LNDS[T cmp.Ordered, Slice ~[]T](vs Slice) Slice
- func LNDSFunc[T any, Slice ~[]T](vs Slice, cmp func(a, b T) int) Slice
- func Map[T, U any, Slice ~[]T](vs Slice, f func(T) U) []U
- func MapKeys[T comparable, U any](m map[T]U) []T
- func MatchingKeys[T comparable, U any](m map[T]U, f func(U) bool) iter.Seq[T]
- func Partition[T any](vs []T, keep func(T) bool) []T
- func PtrAt[T any, Slice ~[]T](ss Slice, i int) *T
- func Rotate[T any, Slice ~[]T](ss Slice, k int)
- func Select[T any, Slice ~[]T](vs Slice, f func(T) bool) iter.Seq[T]
- func Stripe[T any, Slice ~[]T](vs []Slice, i int) Slice
- func Tail[T any, Slice ~[]T](vs Slice, n int) Slice
- func Zero[T any, Slice ~[]T](vs Slice)deprecated
- type Edit
- type EditOp
Examples ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func At ¶ added in v0.3.1
At returns the element of ss at offset i. Negative offsets count backward from the end of the slice. If i is out of range, At will panic.
func Batches ¶ added in v0.6.2
Batches iterates a sequence of up to n contiguous subslices ("batches") of vs, each having nearly as possible to equal length and together covering the input. The slices returned share storage with the input. If n > len(vs), the number of batches is capped at len(vs); otherwise exactly n are constructed.
Batches will panic if n < 0. If n == 0 Batches yields no batches.
Example ¶
package main
import (
"fmt"
"strings"
"github.com/creachadair/mds/slice"
)
func main() {
vs := strings.Fields("the freckles in our eyes are mirror images that when we kiss are perfectly aligned")
for b := range slice.Batches(vs, 4) {
fmt.Println(b)
}
}
Output: [the freckles in our] [eyes are mirror images] [that when we kiss] [are perfectly aligned]
func Chunks
deprecated
added in
v0.6.2
Chunks iterates a sequence of contiguous subslices ("chunks") of vs, each having length at most n and together covering the input. All slices except the last will have length exactly n; the last may have fewer. The slices yielded share storage with the input.
Chunks will panic if n < 0. If n == 0, Chunks yields no chunks.
Deprecated: Use slices.Chunk instead.
Example ¶
package main
import (
"fmt"
"strings"
"github.com/creachadair/mds/slice"
)
func main() {
vs := strings.Fields("my heart is a fish hiding in the water grass")
for c := range slice.Chunks(vs, 3) {
fmt.Println(c)
}
}
Output: [my heart is] [a fish hiding] [in the water] [grass]
func Head ¶ added in v0.14.0
Head returns a subslice of up to n elements from the head (front) of vs. If vs has fewer than n elements, the whole slice is returned.
func LCS ¶ added in v0.10.0
func LCS[T comparable, Slice ~[]T](as, bs Slice) Slice
LCS computes a longest common subsequence of as and bs.
This implementation takes Θ(mn) time and O(P·min(m, n)) space for inputs of length m = len(as) and n = len(bs) and longest subsequence length P.
Example ¶
package main
import (
"fmt"
"github.com/creachadair/mds/slice"
)
func main() {
fmt.Println(slice.LCS(
[]int{1, 0, 3, 4, 2, 7, 9, 9},
[]int{1, 3, 5, 7, 9, 11},
))
}
Output: [1 3 7 9]
func LCSFunc ¶ added in v0.15.0
LCSFunc computes a longest common subsequence of as and bs, using eq to compare elements.
This implementation takes Θ(mn) time and O(P·min(m, n)) space for inputs of length m = len(as) and n = len(bs) and longest subsequence length P.
func LIS ¶ added in v0.15.1
LIS computes a longest strictly increasing subsequence of vs.
This implementation takes O(P·log(n)) time and O(n) space for inputs of length n = len(vs) and longest subsequence length P. If the longest subsequence is the entire input, it takes O(n) time and O(n) space.
func LISFunc ¶ added in v0.15.1
LISFunc computes a longest strictly increasing subsequence of vs, in the order determined by the cmp function. cmp must return a negative number when a < b, a positive number when a > b, and zero when a == b.
This implementation takes O(P·log(n)) time and O(n) space for inputs of length n = len(vs) and longest subsequence length P. If the longest subsequence is the entire input, it takes O(n) time and O(n) space.
func LNDS ¶ added in v0.15.0
LNDS computes a longest non-decreasing subsequence of vs.
This implementation takes O(P·log(n)) time and O(n) space for inputs of length n = len(vs) and longest subsequence length P. If the longest subsequence is the entire input, it takes O(n) time and O(n) space.
func LNDSFunc ¶ added in v0.15.0
LNDSFunc computes a longest non-decreasing subsequence of vs, in the order determined by the cmp function. cmp must return a negative number when a < b, a positive number when a > b, and zero when a == b.
This implementation takes O(P·log(n)) time and O(n) space for inputs of length n = len(vs) and longest subsequence length P. If the longest subsequence is the entire input, it takes O(n) time and O(n) space.
func Map ¶ added in v0.25.4
func Map[T, U any, Slice ~[]T](vs Slice, f func(T) U) []U
Map maps the elements of the input slice through f. If vs == nil, it returns nil; otherwise it returns a non-nil slice of the same length as vs, whose ith value is f(vs[i]).
Example ¶
package main
import (
"errors"
"fmt"
"github.com/creachadair/mds/slice"
)
func main() {
ss := []string{"apple", "pear", "plum", "cherry"}
errs := slice.Map(ss, func(s string) error {
if len(s) > 4 {
return errors.New("too long")
}
return nil
})
fmt.Println(errs)
}
Output: [too long <nil> <nil> too long]
func MapKeys ¶
func MapKeys[T comparable, U any](m map[T]U) []T
MapKeys extracts a slice of the keys from a map. The resulting slice is in arbitrary order.
func MatchingKeys ¶ added in v0.2.1
func MatchingKeys[T comparable, U any](m map[T]U, f func(U) bool) iter.Seq[T]
MatchingKeys returns an iterator over the keys k of m for which f(m[k]) is true. The results are delivered in arbitrary order.
Example ¶
package main
import (
"fmt"
"github.com/creachadair/mds/slice"
)
func isEven(v int) bool { return v%2 == 0 }
func main() {
vs := map[string]int{"red": 3, "yellow": 6, "blue": 4, "green": 5}
for key := range slice.MatchingKeys(vs, isEven) {
fmt.Println(key, vs[key])
}
}
Output: blue 4 yellow 6
func Partition ¶
Partition rearranges the elements of vs in-place so that all the elements v for which keep(v) is true precede all those for which it is false. It returns the prefix of vs that contains the kept elements. It takes time proportional to len(vs) and does not allocate storage outside the slice.
The input order of the kept elements is preserved, but the unkept elements are permuted arbitrarily. For example, given the input:
[6, 1, 3, 2, 8, 4, 5]
and
func keep(v int) bool { return v%2 == 0 }
after partition vs looks like:
[6, 2, 8, 4, ...]
where "..." contains the elements 1, 3, and 5 in unspecified order, and the returned slice is:
[6, 2, 8, 4]
The capacity of the slice returned is clipped to its length, so that appending to it will not modify the elements of vs after those kept.
Example ¶
package main
import (
"fmt"
"slices"
"github.com/creachadair/mds/slice"
)
func isOdd(v int) bool { return v%2 == 1 }
func main() {
vs := []int{3, 1, 8, 4, 2, 6, 9, 10, 5, 7}
// After partitioning, odd is a prefix of vs, which has been rearranged to
// contain only the odd elements in their original order.
odd := slice.Partition(vs, isOdd)
// Reslice the input after the length of the partition if you
// want to address the un-kept elements explicitly.
// Note that their order is unspecified, however, so we sort
// them for stable example output.
rest := vs[len(odd):]
slices.Sort(rest)
fmt.Println(odd)
fmt.Println(rest)
}
Output: [3 1 9 5 7] [2 4 6 8 10]
func PtrAt ¶ added in v0.13.1
PtrAt returns a pointer to the element of ss at offset i. Negative offsets count backward from the end of the slice. If i is out of range, PtrAt returns nil.
func Rotate ¶ added in v0.3.1
Rotate permutes the elements of ss in-place by k positions. If k > 0, elements are rotated rightward. If k < 0, elements are rotated leftward. If k is out of range, Rotate will panic.
For example, if
ss := []string{"a", "b", "c", "d"}
then slice.Rotate(ss, 1) produces
{"d", "a", "b", "c"}
while slice.Rotate(ss, -1) produces
{"b", "c", "d", "a"}
The rotation operation takes time proportional to len(ss) but does not allocate storage outside the input slice.
Example ¶
package main
import (
"fmt"
"github.com/creachadair/mds/slice"
)
func main() {
vs := []int{8, 6, 7, 5, 3, 0, 9}
slice.Rotate(vs, -3)
fmt.Println(vs)
}
Output: [5 3 0 9 8 6 7]
func Select ¶ added in v0.21.3
Select returns an iterator over the elements v of vs for which f(v) is true, in the same order they occur in the input.
func Stripe ¶ added in v0.14.7
Stripe returns a "stripe" of the ith elements of each slice in vs. Any slice that does not have an ith element is skipped. If none of the slices has an ith element, the result is empty.
Types ¶
type Edit ¶ added in v0.10.0
type Edit[T any] struct { Op EditOp // the diff operation to apply at the current offset // X specifies the elements of lhs affected by the edit. // For OpDrop and OpReplace it is the elements to be dropped. // For OpEmit its the elements to be emitted. // For OpCopy it is empty. X []T // Y specifies the elements of rhs affected by the edit. // For OpDrop and OpEmit it is empty. // For OpCopy and OpReplace it is the elements to be copied. Y []T }
Edit is an edit operation transforming specified as part of a diff. Each edit refers to a specific span of one of the inputs.
func EditScript ¶ added in v0.10.0
func EditScript[T comparable, Slice ~[]T](lhs, rhs Slice) []Edit[T]
EditScript computes a minimal-length sequence of Edit operations that will transform lhs into rhs. The result is empty if lhs == rhs. The slices stored in returned edit operations share storage with the inputs lhs and rhs.
This implementation takes Θ(mn) time and O(P·min(m, n)) space to compute a longest common subsequence, plus overhead of O(m+n) time and space to construct the edit sequence from the LCS.
An edit sequence is processed in order. Items are sent to the output according to the following rules.
For each element e of the edit script, if e.Op is:
OpDrop: No output; e.X records the items discarded.
OpEmit: Emit the elements in e.X from lhs.
OpCopy: Emit the elements in e.Y from rhs.
OpReplace: Emit the elements in e.Y from rhs. The items in e.X are the elements from lhs that were replaced. (== Drop + Copy)
If the edit script is empty, the output is equal to the input.
Example ¶
package main
import (
"fmt"
"strings"
"github.com/creachadair/mds/slice"
)
func main() {
lhs := strings.Fields("if you mix red with green you get blue")
rhs := strings.Fields("red mixed with green does not give blue at all")
fmt.Println("start", lhs)
var out []string
for _, e := range slice.EditScript(lhs, rhs) {
switch e.Op {
case slice.OpDrop:
fmt.Println("drop", e.X)
case slice.OpEmit:
fmt.Println("emit", e.X)
out = append(out, e.X...)
case slice.OpCopy:
fmt.Println("copy", e.Y)
out = append(out, e.Y...)
case slice.OpReplace:
fmt.Println("replace", e.X, "with", e.Y)
out = append(out, e.Y...)
default:
panic("invalid")
}
}
fmt.Println("end", out)
}
Output: start [if you mix red with green you get blue] drop [if you mix] emit [red] copy [mixed] emit [with green] replace [you get] with [does not give] emit [blue] copy [at all] end [red mixed with green does not give blue at all]
Source Files