| // 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 "golang.org/x/exp/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 := range s1 { |
| if s1[i] != s2[i] { |
| 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 { |
| // Preserve nil in case it matters. |
| if s == nil { |
| return nil |
| } |
| return append(S([]E{}), 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. Grow may modify elements of the |
| // slice between the length and the capacity. 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)] |
| } |