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, vs := range s {
  47                 if v == vs {
  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, v := range s {
  58                 if f(v) {
  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         s2 := make(S, tot)
  92         copy(s2, s[:i])
  93         copy(s2[i:], v)
  94         copy(s2[i+len(v):], s[i:])
  95         return s2
  96 }
  97
  98 // Delete removes the elements s[i:j] from s, returning the modified slice.
  99 // Delete panics if s[i:j] is not a valid slice of s.
 100 // Delete modifies the contents of the slice s; it does not create a new slice.
 101 // Delete is O(len(s)-j), so if many items must be deleted, it is better to
 102 // make a single call deleting them all together than to delete one at a time.
 103 // Delete might not modify the elements s[len(s)-(j-i):len(s)]. If those
 104 // elements contain pointers you might consider zeroing those elements so that
 105 // objects they reference can be garbage collected.
 106 func Delete[S ~[]E, E any](s S, i, j int) S {
 107         _ = s[i:j] // bounds check
 108
 109         return append(s[:i], s[j:]...)
 110 }
 111
 112 // DeleteFunc removes any elements from s for which del returns true,
 113 // returning the modified slice.
 114 // DeleteFunc modifies the contents of the slice s;
 115 // it does not create a new slice.
 116 // When DeleteFunc removes m elements, it might not modify the elements
 117 // s[len(s)-m:len(s)]. If those elements contain pointers you might consider
 118 // zeroing those elements so that objects they reference can be garbage
 119 // collected.
 120 func DeleteFunc[S ~[]E, E any](s S, del func(E) bool) S {
 121         // Don't start copying elements until we find one to delete.
 122         for i, v := range s {
 123                 if del(v) {
 124                         j := i
 125                         for i++; i < len(s); i++ {
 126                                 v = s[i]
 127                                 if !del(v) {
 128                                         s[j] = v
 129                                         j++
 130                                 }
 131                         }
 132                         return s[:j]
 133                 }
 134         }
 135         return s
 136 }
 137
 138 // Replace replaces the elements s[i:j] by the given v, and returns the
 139 // modified slice. Replace panics if s[i:j] is not a valid slice of s.
 140 func Replace[S ~[]E, E any](s S, i, j int, v ...E) S {
 141         _ = s[i:j] // verify that i:j is a valid subslice
 142         tot := len(s[:i]) + len(v) + len(s[j:])
 143         if tot <= cap(s) {
 144                 s2 := s[:tot]
 145                 copy(s2[i+len(v):], s[j:])
 146                 copy(s2[i:], v)
 147                 return s2
 148         }
 149         s2 := make(S, tot)
 150         copy(s2, s[:i])
 151         copy(s2[i:], v)
 152         copy(s2[i+len(v):], s[j:])
 153         return s2
 154 }
 155
 156 // Clone returns a copy of the slice.
 157 // The elements are copied using assignment, so this is a shallow clone.
 158 func Clone[S ~[]E, E any](s S) S {
 159         // Preserve nil in case it matters.
 160         if s == nil {
 161                 return nil
 162         }
 163         return append(S([]E{}), s...)
 164 }
 165
 166 // Compact replaces consecutive runs of equal elements with a single copy.
 167 // This is like the uniq command found on Unix.
 168 // Compact modifies the contents of the slice s; it does not create a new slice.
 169 // When Compact discards m elements in total, it might not modify the elements
 170 // s[len(s)-m:len(s)]. If those elements contain pointers you might consider
 171 // zeroing those elements so that objects they reference can be garbage collected.
 172 func Compact[S ~[]E, E comparable](s S) S {
 173         if len(s) < 2 {
 174                 return s
 175         }
 176         i := 1
 177         last := s[0]
 178         for _, v := range s[1:] {
 179                 if v != last {
 180                         s[i] = v
 181                         i++
 182                         last = v
 183                 }
 184         }
 185         return s[:i]
 186 }
 187
 188 // CompactFunc is like Compact but uses a comparison function.
 189 func CompactFunc[S ~[]E, E any](s S, eq func(E, E) bool) S {
 190         if len(s) < 2 {
 191                 return s
 192         }
 193         i := 1
 194         last := s[0]
 195         for _, v := range s[1:] {
 196                 if !eq(v, last) {
 197                         s[i] = v
 198                         i++
 199                         last = v
 200                 }
 201         }
 202         return s[:i]
 203 }
 204
 205 // Grow increases the slice's capacity, if necessary, to guarantee space for
 206 // another n elements. After Grow(n), at least n elements can be appended
 207 // to the slice without another allocation. If n is negative or too large to
 208 // allocate the memory, Grow panics.
 209 func Grow[S ~[]E, E any](s S, n int) S {
 210         if n < 0 {
 211                 panic("cannot be negative")
 212         }
 213         if n -= cap(s) - len(s); n > 0 {
 214                 s = append(s[:cap(s)], make([]E, n)...)[:len(s)]
 215         }
 216         return s
 217 }
 218
 219 // Clip removes unused capacity from the slice, returning s[:len(s):len(s)].
 220 func Clip[S ~[]E, E any](s S) S {
 221         return s[:len(s):len(s)]
 222 }