src/slices/slices.go

   1 // Copyright 2021 The Go Authors. All rights reserved.
   2 // Use of this source code is governed by a BSD-style
   3 // license that can be found in the LICENSE file.
   4
   5 // Package slices defines various functions useful with slices of any type.
   6 package slices
   7
   8 // Equal reports whether two slices are equal: the same length and all
   9 // elements equal. If the lengths are different, Equal returns false.
  10 // Otherwise, the elements are compared in increasing index order, and the
  11 // comparison stops at the first unequal pair.
  12 // Floating point NaNs are not considered equal.
  13 func Equal[E comparable](s1, s2 []E) bool {
  14         if len(s1) != len(s2) {
  15                 return false
  16         }
  17         for i := range s1 {
  18                 if s1[i] != s2[i] {
  19                         return false
  20                 }
  21         }
  22         return true
  23 }
  24
  25 // EqualFunc reports whether two slices are equal using a comparison
  26 // function on each pair of elements. If the lengths are different,
  27 // EqualFunc returns false. Otherwise, the elements are compared in
  28 // increasing index order, and the comparison stops at the first index
  29 // for which eq returns false.
  30 func EqualFunc[E1, E2 any](s1 []E1, s2 []E2, eq func(E1, E2) bool) bool {
  31         if len(s1) != len(s2) {
  32                 return false
  33         }
  34         for i, v1 := range s1 {
  35                 v2 := s2[i]
  36                 if !eq(v1, v2) {
  37                         return false
  38                 }
  39         }
  40         return true
  41 }
  42
  43 // Index returns the index of the first occurrence of v in s,
  44 // or -1 if not present.
  45 func Index[E comparable](s []E, v E) int {
  46         for i := range s {
  47                 if v == s[i] {
  48                         return i
  49                 }
  50         }
  51         return -1
  52 }
  53
  54 // IndexFunc returns the first index i satisfying f(s[i]),
  55 // or -1 if none do.
  56 func IndexFunc[E any](s []E, f func(E) bool) int {
  57         for i := range s {
  58                 if f(s[i]) {
  59                         return i
  60                 }
  61         }
  62         return -1
  63 }
  64
  65 // Contains reports whether v is present in s.
  66 func Contains[E comparable](s []E, v E) bool {
  67         return Index(s, v) >= 0
  68 }
  69
  70 // ContainsFunc reports whether at least one
  71 // element e of s satisfies f(e).
  72 func ContainsFunc[E any](s []E, f func(E) bool) bool {
  73         return IndexFunc(s, f) >= 0
  74 }
  75
  76 // Insert inserts the values v... into s at index i,
  77 // returning the modified slice.
  78 // The elements at s[i:] are shifted up to make room.
  79 // In the returned slice r, r[i] == v[0],
  80 // and r[i+len(v)] == value originally at r[i].
  81 // Insert panics if i is out of range.
  82 // This function is O(len(s) + len(v)).
  83 func Insert[S ~[]E, E any](s S, i int, v ...E) S {
  84         tot := len(s) + len(v)
  85         if tot <= cap(s) {
  86                 s2 := s[:tot]
  87                 copy(s2[i+len(v):], s[i:])
  88                 copy(s2[i:], v)
  89                 return s2
  90         }
  91         // Use append rather than make so that we bump the size of
  92         // the slice up to the next storage class.
  93         // This is what Grow does but we don't call Grow because
  94         // that might copy the values twice.
  95         s2 := append(S(nil), make(S, tot)...)
  96         copy(s2, s[:i])
  97         copy(s2[i:], v)
  98         copy(s2[i+len(v):], s[i:])
  99         return s2
 100 }
 101
 102 // Delete removes the elements s[i:j] from s, returning the modified slice.
 103 // Delete panics if s[i:j] is not a valid slice of s.
 104 // Delete modifies the contents of the slice s; it does not create a new slice.
 105 // Delete is O(len(s)-j), so if many items must be deleted, it is better to
 106 // make a single call deleting them all together than to delete one at a time.
 107 // Delete might not modify the elements s[len(s)-(j-i):len(s)]. If those
 108 // elements contain pointers you might consider zeroing those elements so that
 109 // objects they reference can be garbage collected.
 110 func Delete[S ~[]E, E any](s S, i, j int) S {
 111         _ = s[i:j] // bounds check
 112
 113         return append(s[:i], s[j:]...)
 114 }
 115
 116 // DeleteFunc removes any elements from s for which del returns true,
 117 // returning the modified slice.
 118 // DeleteFunc modifies the contents of the slice s;
 119 // it does not create a new slice.
 120 // When DeleteFunc removes m elements, it might not modify the elements
 121 // s[len(s)-m:len(s)]. If those elements contain pointers you might consider
 122 // zeroing those elements so that objects they reference can be garbage
 123 // collected.
 124 func DeleteFunc[S ~[]E, E any](s S, del func(E) bool) S {
 125         // Don't start copying elements until we find one to delete.
 126         for i, v := range s {
 127                 if del(v) {
 128                         j := i
 129                         for i++; i < len(s); i++ {
 130                                 v = s[i]
 131                                 if !del(v) {
 132                                         s[j] = v
 133                                         j++
 134                                 }
 135                         }
 136                         return s[:j]
 137                 }
 138         }
 139         return s
 140 }
 141
 142 // Replace replaces the elements s[i:j] by the given v, and returns the
 143 // modified slice. Replace panics if s[i:j] is not a valid slice of s.
 144 func Replace[S ~[]E, E any](s S, i, j int, v ...E) S {
 145         _ = s[i:j] // verify that i:j is a valid subslice
 146         tot := len(s[:i]) + len(v) + len(s[j:])
 147         if tot <= cap(s) {
 148                 s2 := s[:tot]
 149                 copy(s2[i+len(v):], s[j:])
 150                 copy(s2[i:], v)
 151                 return s2
 152         }
 153         s2 := make(S, tot)
 154         copy(s2, s[:i])
 155         copy(s2[i:], v)
 156         copy(s2[i+len(v):], s[j:])
 157         return s2
 158 }
 159
 160 // Clone returns a copy of the slice.
 161 // The elements are copied using assignment, so this is a shallow clone.
 162 func Clone[S ~[]E, E any](s S) S {
 163         // Preserve nil in case it matters.
 164         if s == nil {
 165                 return nil
 166         }
 167         return append(S([]E{}), s...)
 168 }
 169
 170 // Compact replaces consecutive runs of equal elements with a single copy.
 171 // This is like the uniq command found on Unix.
 172 // Compact modifies the contents of the slice s; it does not create a new slice.
 173 // When Compact discards m elements in total, it might not modify the elements
 174 // s[len(s)-m:len(s)]. If those elements contain pointers you might consider
 175 // zeroing those elements so that objects they reference can be garbage collected.
 176 func Compact[S ~[]E, E comparable](s S) S {
 177         if len(s) < 2 {
 178                 return s
 179         }
 180         i := 1
 181         for k := 1; k < len(s); k++ {
 182                 if s[k] != s[k-1] {
 183                         if i != k {
 184                                 s[i] = s[k]
 185                         }
 186                         i++
 187                 }
 188         }
 189         return s[:i]
 190 }
 191
 192 // CompactFunc is like Compact but uses a comparison function.
 193 func CompactFunc[S ~[]E, E any](s S, eq func(E, E) bool) S {
 194         if len(s) < 2 {
 195                 return s
 196         }
 197         i := 1
 198         for k := 1; k < len(s); k++ {
 199                 if !eq(s[k], s[k-1]) {
 200                         if i != k {
 201                                 s[i] = s[k]
 202                         }
 203                         i++
 204                 }
 205         }
 206         return s[:i]
 207 }
 208
 209 // Grow increases the slice's capacity, if necessary, to guarantee space for
 210 // another n elements. After Grow(n), at least n elements can be appended
 211 // to the slice without another allocation. If n is negative or too large to
 212 // allocate the memory, Grow panics.
 213 func Grow[S ~[]E, E any](s S, n int) S {
 214         if n < 0 {
 215                 panic("cannot be negative")
 216         }
 217         if n -= cap(s) - len(s); n > 0 {
 218                 s = append(s[:cap(s)], make([]E, n)...)[:len(s)]
 219         }
 220         return s
 221 }
 222
 223 // Clip removes unused capacity from the slice, returning s[:len(s):len(s)].
 224 func Clip[S ~[]E, E any](s S) S {
 225         return s[:len(s):len(s)]
 226 }