slices: new package
Update the go version in go.mod to go1.18 so that generics are permitted.
For golang/go#45955
Change-Id: Id5ab52d38c465313c27506008aece9356d34e3c9
Reviewed-on: https://go-review.googlesource.com/c/exp/+/363434
Trust: Ian Lance Taylor <iant@golang.org>
Run-TryBot: Ian Lance Taylor <iant@golang.org>
TryBot-Result: Go Bot <gobot@golang.org>
Reviewed-by: Robert Griesemer <gri@golang.org>
diff --git a/go.mod b/go.mod
index a3fce6a..4fa86a5 100644
--- a/go.mod
+++ b/go.mod
@@ -1,6 +1,6 @@
module golang.org/x/exp
-go 1.17
+go 1.18
require (
dmitri.shuralyov.com/gpu/mtl v0.0.0-20201218220906-28db891af037
diff --git a/slices/slices.go b/slices/slices.go
new file mode 100644
index 0000000..4e06568
--- /dev/null
+++ b/slices/slices.go
@@ -0,0 +1,209 @@
+// Copyright 2021 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+// Package slices defines various functions useful with slices of any type.
+// Unless otherwise specified, these functions all apply to the elements
+// of a slice at index 0 <= i < len(s).
+package slices
+
+import "constraints"
+
+// Equal reports whether two slices are equal: the same length and all
+// elements equal. If the lengths are different, Equal returns false.
+// Otherwise, the elements are compared in increasing index order, and the
+// comparison stops at the first unequal pair.
+// Floating point NaNs are not considered equal.
+func Equal[E comparable](s1, s2 []E) bool {
+ if len(s1) != len(s2) {
+ return false
+ }
+ for i, v1 := range s1 {
+ v2 := s2[i]
+ if v1 != v2 {
+ return false
+ }
+ }
+ return true
+}
+
+// EqualFunc reports whether two slices are equal using a comparison
+// function on each pair of elements. If the lengths are different,
+// EqualFunc returns false. Otherwise, the elements are compared in
+// increasing index order, and the comparison stops at the first index
+// for which eq returns false.
+func EqualFunc[E1, E2 any](s1 []E1, s2 []E2, eq func(E1, E2) bool) bool {
+ if len(s1) != len(s2) {
+ return false
+ }
+ for i, v1 := range s1 {
+ v2 := s2[i]
+ if !eq(v1, v2) {
+ return false
+ }
+ }
+ return true
+}
+
+// Compare compares the elements of s1 and s2.
+// The elements are compared sequentially, starting at index 0,
+// until one element is not equal to the other.
+// The result of comparing the first non-matching elements is returned.
+// If both slices are equal until one of them ends, the shorter slice is
+// considered less than the longer one.
+// The result is 0 if s1 == s2, -1 if s1 < s2, and +1 if s1 > s2.
+// Comparisons involving floating point NaNs are ignored.
+func Compare[E constraints.Ordered](s1, s2 []E) int {
+ s2len := len(s2)
+ for i, v1 := range s1 {
+ if i >= s2len {
+ return +1
+ }
+ v2 := s2[i]
+ switch {
+ case v1 < v2:
+ return -1
+ case v1 > v2:
+ return +1
+ }
+ }
+ if len(s1) < s2len {
+ return -1
+ }
+ return 0
+}
+
+// CompareFunc is like Compare but uses a comparison function
+// on each pair of elements. The elements are compared in increasing
+// index order, and the comparisons stop after the first time cmp
+// returns non-zero.
+// The result is the first non-zero result of cmp; if cmp always
+// returns 0 the result is 0 if len(s1) == len(s2), -1 if len(s1) < len(s2),
+// and +1 if len(s1) > len(s2).
+func CompareFunc[E1, E2 any](s1 []E1, s2 []E2, cmp func(E1, E2) int) int {
+ s2len := len(s2)
+ for i, v1 := range s1 {
+ if i >= s2len {
+ return +1
+ }
+ v2 := s2[i]
+ if c := cmp(v1, v2); c != 0 {
+ return c
+ }
+ }
+ if len(s1) < s2len {
+ return -1
+ }
+ return 0
+}
+
+// Index returns the index of the first occurrence of v in s,
+// or -1 if not present.
+func Index[E comparable](s []E, v E) int {
+ for i, vs := range s {
+ if v == vs {
+ return i
+ }
+ }
+ return -1
+}
+
+// IndexFunc returns the first index i satisfying f(s[i]),
+// or -1 if none do.
+func IndexFunc[E any](s []E, f func(E) bool) int {
+ for i, v := range s {
+ if f(v) {
+ return i
+ }
+ }
+ return -1
+}
+
+// Contains reports whether v is present in s.
+func Contains[E comparable](s []E, v E) bool {
+ return Index(s, v) >= 0
+}
+
+// Insert inserts the values v... into s at index i,
+// returning the modified slice.
+// In the returned slice r, r[i] == v[0].
+// Insert panics if i is out of range.
+// This function is O(len(s) + len(v)).
+func Insert[S ~[]E, E any](s S, i int, v ...E) S {
+ tot := len(s) + len(v)
+ if tot <= cap(s) {
+ s2 := s[:tot]
+ copy(s2[i+len(v):], s[i:])
+ copy(s2[i:], v)
+ return s2
+ }
+ s2 := make(S, tot)
+ copy(s2, s[:i])
+ copy(s2[i:], v)
+ copy(s2[i+len(v):], s[i:])
+ return s2
+}
+
+// Delete removes the elements s[i:j] from s, returning the modified slice.
+// Delete panics if s[i:j] is not a valid slice of s.
+// Delete modifies the contents of the slice s; it does not create a new slice.
+// Delete is O(len(s)-(j-i)), so if many items must be deleted, it is better to
+// make a single call deleting them all together than to delete one at a time.
+func Delete[S ~[]E, E any](s S, i, j int) S {
+ return append(s[:i], s[j:]...)
+}
+
+// Clone returns a copy of the slice.
+// The elements are copied using assignment, so this is a shallow clone.
+func Clone[S ~[]E, E any](s S) S {
+ return append(S(nil), s...)
+}
+
+// Compact replaces consecutive runs of equal elements with a single copy.
+// This is like the uniq command found on Unix.
+// Compact modifies the contents of the slice s; it does not create a new slice.
+func Compact[S ~[]E, E comparable](s S) S {
+ if len(s) == 0 {
+ return s
+ }
+ i := 1
+ last := s[0]
+ for _, v := range s[1:] {
+ if v != last {
+ s[i] = v
+ i++
+ last = v
+ }
+ }
+ return s[:i]
+}
+
+// CompactFunc is like Compact but uses a comparison function.
+func CompactFunc[S ~[]E, E any](s S, eq func(E, E) bool) S {
+ if len(s) == 0 {
+ return s
+ }
+ i := 1
+ last := s[0]
+ for _, v := range s[1:] {
+ if !eq(v, last) {
+ s[i] = v
+ i++
+ last = v
+ }
+ }
+ return s[:i]
+}
+
+// Grow increases the slice's capacity, if necessary, to guarantee space for
+// another n elements. After Grow(n), at least n elements can be appended
+// to the slice without another allocation. If n is negative or too large to
+// allocate the memory, Grow panics.
+func Grow[S ~[]E, E any](s S, n int) S {
+ return append(s, make(S, n)...)[:len(s)]
+}
+
+// Clip removes unused capacity from the slice, returning s[:len(s):len(s)].
+func Clip[S ~[]E, E any](s S) S {
+ return s[:len(s):len(s)]
+}
diff --git a/slices/slices_test.go b/slices/slices_test.go
new file mode 100644
index 0000000..948036d
--- /dev/null
+++ b/slices/slices_test.go
@@ -0,0 +1,545 @@
+// Copyright 2021 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package slices
+
+import (
+ "constraints"
+ "math"
+ "strings"
+ "testing"
+)
+
+var equalIntTests = []struct {
+ s1, s2 []int
+ want bool
+}{
+ {
+ []int{1},
+ nil,
+ false,
+ },
+ {
+ []int{},
+ nil,
+ true,
+ },
+ {
+ []int{1, 2, 3},
+ []int{1, 2, 3},
+ true,
+ },
+ {
+ []int{1, 2, 3},
+ []int{1, 2, 3, 4},
+ false,
+ },
+}
+
+var equalFloatTests = []struct {
+ s1, s2 []float64
+ wantEqual bool
+ wantEqualNaN bool
+}{
+ {
+ []float64{1, 2},
+ []float64{1, 2},
+ true,
+ true,
+ },
+ {
+ []float64{1, 2, math.NaN()},
+ []float64{1, 2, math.NaN()},
+ false,
+ true,
+ },
+}
+
+func TestEqual(t *testing.T) {
+ for _, test := range equalIntTests {
+ if got := Equal(test.s1, test.s2); got != test.want {
+ t.Errorf("Equal(%v, %v) = %t, want %t", test.s1, test.s2, got, test.want)
+ }
+ }
+ for _, test := range equalFloatTests {
+ if got := Equal(test.s1, test.s2); got != test.wantEqual {
+ t.Errorf("Equal(%v, %v) = %t, want %t", test.s1, test.s2, got, test.wantEqual)
+ }
+ }
+}
+
+// equal is simply ==.
+func equal[T comparable](v1, v2 T) bool {
+ return v1 == v2
+}
+
+// equalNaN is like == except that all NaNs are equal.
+func equalNaN[T comparable](v1, v2 T) bool {
+ isNaN := func(f T) bool { return f != f }
+ return v1 == v2 || (isNaN(v1) && isNaN(v2))
+}
+
+// offByOne returns true if integers v1 and v2 differ by 1.
+func offByOne[Elem constraints.Integer](v1, v2 Elem) bool {
+ return v1 == v2+1 || v1 == v2-1
+}
+
+func TestEqualFunc(t *testing.T) {
+ for _, test := range equalIntTests {
+ if got := EqualFunc(test.s1, test.s2, equal[int]); got != test.want {
+ t.Errorf("EqualFunc(%v, %v, equal[int]) = %t, want %t", test.s1, test.s2, got, test.want)
+ }
+ }
+ for _, test := range equalFloatTests {
+ if got := EqualFunc(test.s1, test.s2, equal[float64]); got != test.wantEqual {
+ t.Errorf("Equal(%v, %v, equal[float64]) = %t, want %t", test.s1, test.s2, got, test.wantEqual)
+ }
+ if got := EqualFunc(test.s1, test.s2, equalNaN[float64]); got != test.wantEqualNaN {
+ t.Errorf("Equal(%v, %v, equalNaN[float64]) = %t, want %t", test.s1, test.s2, got, test.wantEqualNaN)
+ }
+ }
+
+ s1 := []int{1, 2, 3}
+ s2 := []int{2, 3, 4}
+ if EqualFunc(s1, s1, offByOne[int]) {
+ t.Errorf("EqualFunc(%v, %v, offByOne) = true, want false", s1, s1)
+ }
+ if !EqualFunc(s1, s2, offByOne[int]) {
+ t.Errorf("EqualFunc(%v, %v, offByOne) = false, want true", s1, s2)
+ }
+
+ s3 := []string{"a", "b", "c"}
+ s4 := []string{"A", "B", "C"}
+ if !EqualFunc(s3, s4, strings.EqualFold) {
+ t.Errorf("EqualFunc(%v, %v, strings.EqualFold) = false, want true", s3, s4)
+ }
+
+ cmpIntString := func(v1 int, v2 string) bool {
+ return string(rune(v1)-1+'a') == v2
+ }
+ if !EqualFunc(s1, s3, cmpIntString) {
+ t.Errorf("EqualFunc(%v, %v, cmpIntString) = false, want true", s1, s3)
+ }
+}
+
+var compareIntTests = []struct {
+ s1, s2 []int
+ want int
+}{
+ {
+ []int{1, 2, 3},
+ []int{1, 2, 3, 4},
+ -1,
+ },
+ {
+ []int{1, 2, 3, 4},
+ []int{1, 2, 3},
+ +1,
+ },
+ {
+ []int{1, 2, 3},
+ []int{1, 4, 3},
+ -1,
+ },
+ {
+ []int{1, 4, 3},
+ []int{1, 2, 3},
+ +1,
+ },
+}
+
+var compareFloatTests = []struct {
+ s1, s2 []float64
+ want int
+}{
+ {
+ []float64{1, 2, math.NaN()},
+ []float64{1, 2, math.NaN()},
+ 0,
+ },
+ {
+ []float64{1, math.NaN(), 3},
+ []float64{1, math.NaN(), 4},
+ -1,
+ },
+ {
+ []float64{1, math.NaN(), 3},
+ []float64{1, 2, 4},
+ -1,
+ },
+ {
+ []float64{1, math.NaN(), 3},
+ []float64{1, 2, math.NaN()},
+ 0,
+ },
+ {
+ []float64{1, math.NaN(), 3, 4},
+ []float64{1, 2, math.NaN()},
+ +1,
+ },
+}
+
+func TestCompare(t *testing.T) {
+ intWant := func(want bool) string {
+ if want {
+ return "0"
+ }
+ return "!= 0"
+ }
+ for _, test := range equalIntTests {
+ if got := Compare(test.s1, test.s2); (got == 0) != test.want {
+ t.Errorf("Compare(%v, %v) = %d, want %s", test.s1, test.s2, got, intWant(test.want))
+ }
+ }
+ for _, test := range equalFloatTests {
+ if got := Compare(test.s1, test.s2); (got == 0) != test.wantEqualNaN {
+ t.Errorf("Compare(%v, %v) = %d, want %s", test.s1, test.s2, got, intWant(test.wantEqualNaN))
+ }
+ }
+
+ for _, test := range compareIntTests {
+ if got := Compare(test.s1, test.s2); got != test.want {
+ t.Errorf("Compare(%v, %v) = %d, want %d", test.s1, test.s2, got, test.want)
+ }
+ }
+ for _, test := range compareFloatTests {
+ if got := Compare(test.s1, test.s2); got != test.want {
+ t.Errorf("Compare(%v, %v) = %d, want %d", test.s1, test.s2, got, test.want)
+ }
+ }
+}
+
+func equalToCmp[T comparable](eq func(T, T) bool) func(T, T) int {
+ return func(v1, v2 T) int {
+ if eq(v1, v2) {
+ return 0
+ }
+ return 1
+ }
+}
+
+func cmp[T constraints.Ordered](v1, v2 T) int {
+ if v1 < v2 {
+ return -1
+ } else if v1 > v2 {
+ return 1
+ } else {
+ return 0
+ }
+}
+
+func TestCompareFunc(t *testing.T) {
+ intWant := func(want bool) string {
+ if want {
+ return "0"
+ }
+ return "!= 0"
+ }
+ for _, test := range equalIntTests {
+ if got := CompareFunc(test.s1, test.s2, equalToCmp(equal[int])); (got == 0) != test.want {
+ t.Errorf("CompareFunc(%v, %v, equalToCmp(equal[int])) = %d, want %s", test.s1, test.s2, got, intWant(test.want))
+ }
+ }
+ for _, test := range equalFloatTests {
+ if got := CompareFunc(test.s1, test.s2, equalToCmp(equal[float64])); (got == 0) != test.wantEqual {
+ t.Errorf("CompareFunc(%v, %v, equalToCmp(equal[float64])) = %d, want %s", test.s1, test.s2, got, intWant(test.wantEqual))
+ }
+ }
+
+ for _, test := range compareIntTests {
+ if got := CompareFunc(test.s1, test.s2, cmp[int]); got != test.want {
+ t.Errorf("CompareFunc(%v, %v, cmp[int]) = %d, want %d", test.s1, test.s2, got, test.want)
+ }
+ }
+ for _, test := range compareFloatTests {
+ if got := CompareFunc(test.s1, test.s2, cmp[float64]); got != test.want {
+ t.Errorf("CompareFunc(%v, %v, cmp[float64]) = %d, want %d", test.s1, test.s2, got, test.want)
+ }
+ }
+
+ s1 := []int{1, 2, 3}
+ s2 := []int{2, 3, 4}
+ if got := CompareFunc(s1, s2, equalToCmp(offByOne[int])); got != 0 {
+ t.Errorf("CompareFunc(%v, %v, offByOne) = %d, want 0", s1, s2, got)
+ }
+
+ s3 := []string{"a", "b", "c"}
+ s4 := []string{"A", "B", "C"}
+ if got := CompareFunc(s3, s4, strings.Compare); got != 1 {
+ t.Errorf("CompareFunc(%v, %v, strings.Compare) = %d, want 1", s3, s4, got)
+ }
+
+ compareLower := func(v1, v2 string) int {
+ return strings.Compare(strings.ToLower(v1), strings.ToLower(v2))
+ }
+ if got := CompareFunc(s3, s4, compareLower); got != 0 {
+ t.Errorf("CompareFunc(%v, %v, compareLower) = %d, want 0", s3, s4, got)
+ }
+
+ cmpIntString := func(v1 int, v2 string) int {
+ return strings.Compare(string(rune(v1)-1+'a'), v2)
+ }
+ if got := CompareFunc(s1, s3, cmpIntString); got != 0 {
+ t.Errorf("CompareFunc(%v, %v, cmpIntString) = %d, want 0", s1, s3, got)
+ }
+}
+
+var indexTests = []struct {
+ s []int
+ v int
+ want int
+}{
+ {
+ nil,
+ 0,
+ -1,
+ },
+ {
+ []int{},
+ 0,
+ -1,
+ },
+ {
+ []int{1, 2, 3},
+ 2,
+ 1,
+ },
+ {
+ []int{1, 2, 2, 3},
+ 2,
+ 1,
+ },
+ {
+ []int{1, 2, 3, 2},
+ 2,
+ 1,
+ },
+}
+
+func TestIndex(t *testing.T) {
+ for _, test := range indexTests {
+ if got := Index(test.s, test.v); got != test.want {
+ t.Errorf("Index(%v, %v) = %d, want %d", test.s, test.v, got, test.want)
+ }
+ }
+}
+
+func equalToIndex[T any](f func(T, T) bool, v1 T) func(T) bool {
+ return func(v2 T) bool {
+ return f(v1, v2)
+ }
+}
+
+func TestIndexFunc(t *testing.T) {
+ for _, test := range indexTests {
+ if got := IndexFunc(test.s, equalToIndex(equal[int], test.v)); got != test.want {
+ t.Errorf("IndexFunc(%v, equalToIndex(equal[int], %v)) = %d, want %d", test.s, test.v, got, test.want)
+ }
+ }
+
+ s1 := []string{"hi", "HI"}
+ if got := IndexFunc(s1, equalToIndex(equal[string], "HI")); got != 1 {
+ t.Errorf("IndexFunc(%v, equalToIndex(equal[string], %q)) = %d, want %d", s1, "HI", got, 1)
+ }
+ if got := IndexFunc(s1, equalToIndex(strings.EqualFold, "HI")); got != 0 {
+ t.Errorf("IndexFunc(%v, equalToIndex(strings.EqualFold, %q)) = %d, want %d", s1, "HI", got, 0)
+ }
+}
+
+func TestContains(t *testing.T) {
+ for _, test := range indexTests {
+ if got := Contains(test.s, test.v); got != (test.want != -1) {
+ t.Errorf("Contains(%v, %v) = %t, want %t", test.s, test.v, got, test.want != -1)
+ }
+ }
+}
+
+var insertTests = []struct {
+ s []int
+ i int
+ add []int
+ want []int
+}{
+ {
+ []int{1, 2, 3},
+ 0,
+ []int{4},
+ []int{4, 1, 2, 3},
+ },
+ {
+ []int{1, 2, 3},
+ 1,
+ []int{4},
+ []int{1, 4, 2, 3},
+ },
+ {
+ []int{1, 2, 3},
+ 3,
+ []int{4},
+ []int{1, 2, 3, 4},
+ },
+ {
+ []int{1, 2, 3},
+ 2,
+ []int{4, 5},
+ []int{1, 2, 4, 5, 3},
+ },
+}
+
+func TestInsert(t *testing.T) {
+ s := []int{1, 2, 3}
+ if got := Insert(s, 0); !Equal(got, s) {
+ t.Errorf("Insert(%v, 0) = %v, want %v", s, got, s)
+ }
+ for _, test := range insertTests {
+ copy := Clone(test.s)
+ if got := Insert(copy, test.i, test.add...); !Equal(got, test.want) {
+ t.Errorf("Insert(%v, %d, %v...) = %v, want %v", test.s, test.i, test.add, got, test.want)
+ }
+ }
+}
+
+var deleteTests = []struct {
+ s []int
+ i, j int
+ want []int
+}{
+ {
+ []int{1, 2, 3},
+ 0,
+ 0,
+ []int{1, 2, 3},
+ },
+ {
+ []int{1, 2, 3},
+ 0,
+ 1,
+ []int{2, 3},
+ },
+ {
+ []int{1, 2, 3},
+ 3,
+ 3,
+ []int{1, 2, 3},
+ },
+ {
+ []int{1, 2, 3},
+ 0,
+ 2,
+ []int{3},
+ },
+ {
+ []int{1, 2, 3},
+ 0,
+ 3,
+ []int{},
+ },
+}
+
+func TestDelete(t *testing.T) {
+ for _, test := range deleteTests {
+ copy := Clone(test.s)
+ if got := Delete(copy, test.i, test.j); !Equal(got, test.want) {
+ t.Errorf("Delete(%v, %d, %d) = %v, want %v", test.s, test.i, test.j, got, test.want)
+ }
+ }
+}
+
+func TestClone(t *testing.T) {
+ s1 := []int{1, 2, 3}
+ s2 := Clone(s1)
+ if !Equal(s1, s2) {
+ t.Errorf("Clone(%v) = %v, want %v", s1, s2, s1)
+ }
+ s1[0] = 4
+ want := []int{1, 2, 3}
+ if !Equal(s2, want) {
+ t.Errorf("Clone(%v) changed unexpectedly to %v", want, s2)
+ }
+}
+
+var compactTests = []struct {
+ s []int
+ want []int
+}{
+ {
+ nil,
+ nil,
+ },
+ {
+ []int{1},
+ []int{1},
+ },
+ {
+ []int{1, 2, 3},
+ []int{1, 2, 3},
+ },
+ {
+ []int{1, 1, 2},
+ []int{1, 2},
+ },
+ {
+ []int{1, 2, 1},
+ []int{1, 2, 1},
+ },
+ {
+ []int{1, 2, 2, 3, 3, 4},
+ []int{1, 2, 3, 4},
+ },
+}
+
+func TestCompact(t *testing.T) {
+ for _, test := range compactTests {
+ copy := Clone(test.s)
+ if got := Compact(copy); !Equal(got, test.want) {
+ t.Errorf("Compact(%v) = %v, want %v", test.s, got, test.want)
+ }
+ }
+}
+
+func TestCompactFunc(t *testing.T) {
+ for _, test := range compactTests {
+ copy := Clone(test.s)
+ if got := CompactFunc(copy, equal[int]); !Equal(got, test.want) {
+ t.Errorf("CompactFunc(%v, equal[int]) = %v, want %v", test.s, got, test.want)
+ }
+ }
+
+ s1 := []string{"a", "a", "A", "B", "b"}
+ copy := Clone(s1)
+ want := []string{"a", "B"}
+ if got := CompactFunc(copy, strings.EqualFold); !Equal(got, want) {
+ t.Errorf("CompactFunc(%v, strings.EqualFold) = %v, want %v", s1, got, want)
+ }
+}
+
+func TestGrow(t *testing.T) {
+ s1 := []int{1, 2, 3}
+ copy := Clone(s1)
+ s2 := Grow(copy, 1000)
+ if !Equal(s1, s2) {
+ t.Errorf("Grow(%v) = %v, want %v", s1, s2, s1)
+ }
+ if cap(s2) < 1000+len(s1) {
+ t.Errorf("after Grow(%v) cap = %d, want >= %d", s1, cap(s2), 1000+len(s1))
+ }
+}
+
+func TestClip(t *testing.T) {
+ s1 := []int{1, 2, 3, 4, 5, 6}[:3]
+ orig := Clone(s1)
+ if len(s1) != 3 {
+ t.Errorf("len(%v) = %d, want 3", s1, len(s1))
+ }
+ if cap(s1) < 6 {
+ t.Errorf("cap(%v[:3]) = %d, want >= 6", orig, cap(s1))
+ }
+ s2 := Clip(s1)
+ if !Equal(s1, s2) {
+ t.Errorf("Clip(%v) = %v, want %v", s1, s2, s1)
+ }
+ if cap(s2) != 3 {
+ t.Errorf("cap(Clip(%v)) = %d, want 3", orig, cap(s2))
+ }
+}
