package slices
import (
+ "cmp"
"unsafe"
)
// 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 {
+func Equal[S ~[]E, E comparable](s1, s2 S) bool {
if len(s1) != len(s2) {
return false
}
return true
}
-// EqualFunc reports whether two slices are equal using a comparison
+// EqualFunc reports whether two slices are equal using an equality
// 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 {
+func EqualFunc[S1 ~[]E1, S2 ~[]E2, E1, E2 any](s1 S1, s2 S2, eq func(E1, E2) bool) bool {
if len(s1) != len(s2) {
return false
}
return true
}
+// Compare compares the elements of s1 and s2, using [cmp.Compare] on each pair
+// of elements. 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.
+func Compare[S ~[]E, E cmp.Ordered](s1, s2 S) int {
+ for i, v1 := range s1 {
+ if i >= len(s2) {
+ return +1
+ }
+ v2 := s2[i]
+ if c := cmp.Compare(v1, v2); c != 0 {
+ return c
+ }
+ }
+ if len(s1) < len(s2) {
+ return -1
+ }
+ return 0
+}
+
+// CompareFunc is like [Compare] but uses a custom comparison function on each
+// pair of elements.
+// 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[S1 ~[]E1, S2 ~[]E2, E1, E2 any](s1 S1, s2 S2, cmp func(E1, E2) int) int {
+ for i, v1 := range s1 {
+ if i >= len(s2) {
+ return +1
+ }
+ v2 := s2[i]
+ if c := cmp(v1, v2); c != 0 {
+ return c
+ }
+ }
+ if len(s1) < len(s2) {
+ 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 {
+func Index[S ~[]E, E comparable](s S, v E) int {
for i := range s {
if v == s[i] {
return i
// 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 {
+func IndexFunc[S ~[]E, E any](s S, f func(E) bool) int {
for i := range s {
if f(s[i]) {
return i
}
// Contains reports whether v is present in s.
-func Contains[E comparable](s []E, v E) bool {
+func Contains[S ~[]E, E comparable](s S, v E) bool {
return Index(s, v) >= 0
}
// ContainsFunc reports whether at least one
// element e of s satisfies f(e).
-func ContainsFunc[E any](s []E, f func(E) bool) bool {
+func ContainsFunc[S ~[]E, E any](s S, f func(E) bool) bool {
return IndexFunc(s, f) >= 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 {
+ n := len(s)
m := len(v)
if m == 0 {
+ // Panic if i is not in the range [0:n] inclusive.
+ // See issue 63913.
+ _ = s[:n:n][i:]
return s
}
- n := len(s)
if i == n {
return append(s, v...)
}
}
// 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 panics if j > len(s) or s[i:j] is not a valid slice of s.
// Delete is O(len(s)-j), 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.
// Delete might not modify the elements s[len(s)-(j-i):len(s)]. If those
// DeleteFunc removes any elements from s for which del returns true,
// returning the modified slice.
-// DeleteFunc modifies the contents of the slice s;
-// it does not create a new slice.
// When DeleteFunc removes m elements, it might not modify the elements
// s[len(s)-m:len(s)]. If those elements contain pointers you might consider
// zeroing those elements so that objects they reference can be garbage
// collected.
func DeleteFunc[S ~[]E, E any](s S, del func(E) bool) S {
+ i := IndexFunc(s, del)
+ if i == -1 {
+ return s
+ }
// Don't start copying elements until we find one to delete.
- for i, v := range s {
- if del(v) {
- j := i
- for i++; i < len(s); i++ {
- v = s[i]
- if !del(v) {
- s[j] = v
- j++
- }
- }
- return s[:j]
+ for j := i + 1; j < len(s); j++ {
+ if v := s[j]; !del(v) {
+ s[i] = v
+ i++
}
}
- return s
+ return s[:i]
}
// Replace replaces the elements s[i:j] by the given v, and returns the
-// modified slice. Replace panics if s[i:j] is not a valid slice of s.
+// modified slice.
+// Replace panics if j > len(s) or s[i:j] is not a valid slice of s.
func Replace[S ~[]E, E any](s S, i, j int, v ...E) S {
- _ = s[i:j] // verify that i:j is a valid subslice
+ _ = s[i:j] // bounds check
if i == j {
return Insert(s, i, v...)
if i+len(v) <= j {
// Easy, as v fits in the deleted portion.
copy(r[i:], v)
- if i+len(v) != j {
- copy(r[i+len(v):], s[j:])
- }
+ copy(r[i+len(v):], s[j:])
return r
}
// 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 {
- // Preserve nil in case it matters.
- if s == nil {
- return nil
- }
- return append(S([]E{}), s...)
+ // The s[:0:0] preserves nil in case it matters.
+ return append(s[:0:0], 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.
+// Compact modifies the contents of the slice s and returns the modified slice,
+// which may have a smaller length.
// When Compact discards m elements in total, it might not modify the elements
// s[len(s)-m:len(s)]. If those elements contain pointers you might consider
// zeroing those elements so that objects they reference can be garbage collected.
return s[:i]
}
-// CompactFunc is like Compact but uses a comparison function.
+// CompactFunc is like [Compact] but uses an equality function to compare elements.
+// For runs of elements that compare equal, CompactFunc keeps the first one.
func CompactFunc[S ~[]E, E any](s S, eq func(E, E) bool) S {
if len(s) < 2 {
return s
// rotateLeft rotates b left by n spaces.
// s_final[i] = s_orig[i+r], wrapping around.
-func rotateLeft[S ~[]E, E any](s S, r int) {
+func rotateLeft[E any](s []E, r int) {
for r != 0 && r != len(s) {
if r*2 <= len(s) {
swap(s[:r], s[len(s)-r:])
}
}
}
-func rotateRight[S ~[]E, E any](s S, r int) {
+func rotateRight[E any](s []E, r int) {
rotateLeft(s, len(s)-r)
}
// swap swaps the contents of x and y. x and y must be equal length and disjoint.
-func swap[S ~[]E, E any](x, y S) {
+func swap[E any](x, y []E) {
for i := 0; i < len(x); i++ {
x[i], y[i] = y[i], x[i]
}
}
// overlaps reports whether the memory ranges a[0:len(a)] and b[0:len(b)] overlap.
-func overlaps[S ~[]E, E any](a, b S) bool {
+func overlaps[E any](a, b []E) bool {
if len(a) == 0 || len(b) == 0 {
return false
}
// startIdx returns the index in haystack where the needle starts.
// prerequisite: the needle must be aliased entirely inside the haystack.
-func startIdx[S ~[]E, E any](haystack, needle S) int {
+func startIdx[E any](haystack, needle []E) int {
p := &needle[0]
for i := range haystack {
if p == &haystack[i] {
}
// Reverse reverses the elements of the slice in place.
-func Reverse[E any](s []E) {
+func Reverse[S ~[]E, E any](s S) {
for i, j := 0, len(s)-1; i < j; i, j = i+1, j-1 {
s[i], s[j] = s[j], s[i]
}
}
+
+// Concat returns a new slice concatenating the passed in slices.
+func Concat[S ~[]E, E any](slices ...S) S {
+ size := 0
+ for _, s := range slices {
+ size += len(s)
+ if size < 0 {
+ panic("len out of range")
+ }
+ }
+ newslice := Grow[S](nil, size)
+ for _, s := range slices {
+ newslice = append(newslice, s...)
+ }
+ return newslice
+}