slice

package
v0.22.0 Latest Latest
Warning

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

 Go to latest Published: Nov 22, 2024 License: BSD-3-Clause Imports: 4 Imported by: 7

Documentation

Overview

Package slice implements some useful functions for slices.

Index

Examples

Constants

This section is empty.

Variables

This section is empty.

Functions

func At added in v0.3.1 

func At[T any, Slice ~[]T](ss Slice, i int) T

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 

func Batches[T any, Slice ~[]T](vs Slice, n int) []Slice

Batches returns a slice 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 returns nil.

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 added in v0.6.2 

func Chunks[T any, Slice ~[]T](vs Slice, n int) []Slice

Chunks returns a slice 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 returned share storage with the input.

Chunks will panic if n < 0. If n == 0, Chunks returns a single chunk containing the entire input.

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 Dedup deprecated 

func Dedup[T comparable](vs []T) []T

Dedup rearranges the elements of vs in-place to deduplicate consecutive runs of identical elements. It returns a prefix of vs that contains the first element of each run found.

Deprecated: Use the equivalent slices.Compact instead. 

func Head[T any, Slice ~[]T](vs Slice, n int) Slice

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 

func LCSFunc[T any, Slice ~[]T](as, bs Slice, eq func(a, b T) bool) Slice

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 

func LIS[T cmp.Ordered, Slice ~[]T](vs Slice) Slice

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 

func LISFunc[T any, Slice ~[]T](vs Slice, cmp func(a, b T) int) Slice

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 

func LNDS[T cmp.Ordered, Slice ~[]T](vs Slice) Slice

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 

func LNDSFunc[T any, Slice ~[]T](vs Slice, cmp func(a, b T) int) Slice

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 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 

func Partition[T any](vs []T, keep func(T) bool) []T

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]
Example 
package main

import (
	"fmt"

	"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}
	odd := slice.Partition(vs, isOdd)
	fmt.Println(odd)
}

Output:

[3 1 9 5 7]

func PtrAt added in v0.13.1 

func PtrAt[T any, Slice ~[]T](ss Slice, i int) *T

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 Reverse deprecated 

func Reverse[T any, Slice ~[]T](vs Slice)

Reverse reverses the contents of vs in-place.

Deprecated: Use the equivalent slices.Reverse instead.

func Rotate added in v0.3.1 

func Rotate[T any, Slice ~[]T](ss Slice, k int)

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 

func Select[T any, Slice ~[]T](vs Slice, f func(T) bool) iter.Seq[T]

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 

func Stripe[T any, Slice ~[]T](vs []Slice, i int) Slice

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.

func Tail added in v0.14.0 

func Tail[T any, Slice ~[]T](vs Slice, n int) Slice

Tail returns a subslice of up to n elements from the tail (end) of vs. If vs has fewer than n elements, the whole slice is returned.

func Zero added in v0.8.3 

func Zero[T any, Slice ~[]T](vs Slice)

Zero sets all the elements of vs to their zero value.

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]

func (Edit[T]) String added in v0.10.0 

func (e Edit[T]) String() string

type EditOp added in v0.10.0 

type EditOp byte

EditOp is the opcode of an edit sequence instruction. 

const (
	OpDrop    EditOp = '-' // Drop items from lhs
	OpEmit    EditOp = '=' // Emit elements from lhs
	OpCopy    EditOp = '+' // Copy items from rhs
	OpReplace EditOp = '!' // Replace with items from rhs (== Drop+Copy)
)

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.