Dan Willemsen | cc753b7 | 2021-08-31 13:25:42 -0700 | [diff] [blame] | 1 | // run -gcflags=-G=3 |
| 2 | |
| 3 | // Copyright 2021 The Go Authors. All rights reserved. |
| 4 | // Use of this source code is governed by a BSD-style |
| 5 | // license that can be found in the LICENSE file. |
| 6 | |
| 7 | // Package slices provides functions for basic operations on |
| 8 | // slices of any element type. |
| 9 | package main |
| 10 | |
| 11 | import ( |
| 12 | "fmt" |
| 13 | "math" |
| 14 | "strings" |
| 15 | ) |
| 16 | |
| 17 | type Ordered interface { |
Dan Willemsen | bc60c3c | 2021-12-15 01:09:00 -0800 | [diff] [blame] | 18 | ~int | ~int8 | ~int16 | ~int32 | ~int64 | |
| 19 | ~uint | ~uint8 | ~uint16 | ~uint32 | ~uint64 | ~uintptr | |
| 20 | ~float32 | ~float64 | |
| 21 | ~string |
Dan Willemsen | cc753b7 | 2021-08-31 13:25:42 -0700 | [diff] [blame] | 22 | } |
| 23 | |
| 24 | type Integer interface { |
Dan Willemsen | bc60c3c | 2021-12-15 01:09:00 -0800 | [diff] [blame] | 25 | ~int | ~int8 | ~int16 | ~int32 | ~int64 | |
| 26 | ~uint | ~uint8 | ~uint16 | ~uint32 | ~uint64 | ~uintptr |
Dan Willemsen | cc753b7 | 2021-08-31 13:25:42 -0700 | [diff] [blame] | 27 | } |
| 28 | |
| 29 | // Max returns the maximum of two values of some ordered type. |
| 30 | func _Max[T Ordered](a, b T) T { |
Dan Willemsen | bc60c3c | 2021-12-15 01:09:00 -0800 | [diff] [blame] | 31 | if a > b { |
| 32 | return a |
| 33 | } |
| 34 | return b |
Dan Willemsen | cc753b7 | 2021-08-31 13:25:42 -0700 | [diff] [blame] | 35 | } |
| 36 | |
| 37 | // Min returns the minimum of two values of some ordered type. |
| 38 | func _Min[T Ordered](a, b T) T { |
Dan Willemsen | bc60c3c | 2021-12-15 01:09:00 -0800 | [diff] [blame] | 39 | if a < b { |
| 40 | return a |
| 41 | } |
| 42 | return b |
Dan Willemsen | cc753b7 | 2021-08-31 13:25:42 -0700 | [diff] [blame] | 43 | } |
| 44 | |
| 45 | // _Equal reports whether two slices are equal: the same length and all |
| 46 | // elements equal. All floating point NaNs are considered equal. |
| 47 | func _Equal[Elem comparable](s1, s2 []Elem) bool { |
| 48 | if len(s1) != len(s2) { |
| 49 | return false |
| 50 | } |
| 51 | for i, v1 := range s1 { |
| 52 | v2 := s2[i] |
| 53 | if v1 != v2 { |
| 54 | isNaN := func(f Elem) bool { return f != f } |
| 55 | if !isNaN(v1) || !isNaN(v2) { |
| 56 | return false |
| 57 | } |
| 58 | } |
| 59 | } |
| 60 | return true |
| 61 | } |
| 62 | |
Dan Willemsen | bc60c3c | 2021-12-15 01:09:00 -0800 | [diff] [blame] | 63 | // _EqualFn reports whether two slices are equal using a comparison |
Dan Willemsen | cc753b7 | 2021-08-31 13:25:42 -0700 | [diff] [blame] | 64 | // function on each element. |
| 65 | func _EqualFn[Elem any](s1, s2 []Elem, eq func(Elem, Elem) bool) bool { |
| 66 | if len(s1) != len(s2) { |
| 67 | return false |
| 68 | } |
| 69 | for i, v1 := range s1 { |
| 70 | v2 := s2[i] |
| 71 | if !eq(v1, v2) { |
| 72 | return false |
| 73 | } |
| 74 | } |
| 75 | return true |
| 76 | } |
| 77 | |
| 78 | // _Map turns a []Elem1 to a []Elem2 using a mapping function. |
| 79 | func _Map[Elem1, Elem2 any](s []Elem1, f func(Elem1) Elem2) []Elem2 { |
| 80 | r := make([]Elem2, len(s)) |
| 81 | for i, v := range s { |
| 82 | r[i] = f(v) |
| 83 | } |
| 84 | return r |
| 85 | } |
| 86 | |
| 87 | // _Reduce reduces a []Elem1 to a single value of type Elem2 using |
| 88 | // a reduction function. |
| 89 | func _Reduce[Elem1, Elem2 any](s []Elem1, initializer Elem2, f func(Elem2, Elem1) Elem2) Elem2 { |
| 90 | r := initializer |
| 91 | for _, v := range s { |
| 92 | r = f(r, v) |
| 93 | } |
| 94 | return r |
| 95 | } |
| 96 | |
| 97 | // _Filter filters values from a slice using a filter function. |
| 98 | func _Filter[Elem any](s []Elem, f func(Elem) bool) []Elem { |
| 99 | var r []Elem |
| 100 | for _, v := range s { |
| 101 | if f(v) { |
| 102 | r = append(r, v) |
| 103 | } |
| 104 | } |
| 105 | return r |
| 106 | } |
| 107 | |
| 108 | // _Max returns the maximum element in a slice of some ordered type. |
| 109 | // If the slice is empty it returns the zero value of the element type. |
| 110 | func _SliceMax[Elem Ordered](s []Elem) Elem { |
| 111 | if len(s) == 0 { |
| 112 | var zero Elem |
| 113 | return zero |
| 114 | } |
| 115 | return _Reduce(s[1:], s[0], _Max[Elem]) |
| 116 | } |
| 117 | |
| 118 | // _Min returns the minimum element in a slice of some ordered type. |
| 119 | // If the slice is empty it returns the zero value of the element type. |
| 120 | func _SliceMin[Elem Ordered](s []Elem) Elem { |
| 121 | if len(s) == 0 { |
| 122 | var zero Elem |
| 123 | return zero |
| 124 | } |
| 125 | return _Reduce(s[1:], s[0], _Min[Elem]) |
| 126 | } |
| 127 | |
| 128 | // _Append adds values to the end of a slice, returning a new slice. |
| 129 | // This is like the predeclared append function; it's an example |
| 130 | // of how to write it using generics. We used to write code like |
| 131 | // this before append was added to the language, but we had to write |
| 132 | // a separate copy for each type. |
| 133 | func _Append[T any](s []T, t ...T) []T { |
| 134 | lens := len(s) |
| 135 | tot := lens + len(t) |
| 136 | if tot <= cap(s) { |
| 137 | s = s[:tot] |
| 138 | } else { |
Dan Willemsen | bc60c3c | 2021-12-15 01:09:00 -0800 | [diff] [blame] | 139 | news := make([]T, tot, tot+tot/2) |
Dan Willemsen | cc753b7 | 2021-08-31 13:25:42 -0700 | [diff] [blame] | 140 | _Copy(news, s) |
| 141 | s = news |
| 142 | } |
| 143 | _Copy(s[lens:tot], t) |
| 144 | return s |
| 145 | } |
| 146 | |
| 147 | // _Copy copies values from t to s, stopping when either slice is full, |
| 148 | // returning the number of values copied. This is like the predeclared |
| 149 | // copy function; it's an example of how to write it using generics. |
| 150 | func _Copy[T any](s, t []T) int { |
| 151 | i := 0 |
| 152 | for ; i < len(s) && i < len(t); i++ { |
| 153 | s[i] = t[i] |
| 154 | } |
| 155 | return i |
| 156 | } |
| 157 | |
| 158 | func TestEqual() { |
Dan Willemsen | bc60c3c | 2021-12-15 01:09:00 -0800 | [diff] [blame] | 159 | s1 := []int{1, 2, 3} |
| 160 | if !_Equal(s1, s1) { |
| 161 | panic(fmt.Sprintf("_Equal(%v, %v) = false, want true", s1, s1)) |
| 162 | } |
| 163 | s2 := []int{1, 2, 3} |
| 164 | if !_Equal(s1, s2) { |
| 165 | panic(fmt.Sprintf("_Equal(%v, %v) = false, want true", s1, s2)) |
| 166 | } |
| 167 | s2 = append(s2, 4) |
| 168 | if _Equal(s1, s2) { |
| 169 | panic(fmt.Sprintf("_Equal(%v, %v) = true, want false", s1, s2)) |
| 170 | } |
Dan Willemsen | cc753b7 | 2021-08-31 13:25:42 -0700 | [diff] [blame] | 171 | |
Dan Willemsen | bc60c3c | 2021-12-15 01:09:00 -0800 | [diff] [blame] | 172 | s3 := []float64{1, 2, math.NaN()} |
| 173 | if !_Equal(s3, s3) { |
| 174 | panic(fmt.Sprintf("_Equal(%v, %v) = false, want true", s3, s3)) |
| 175 | } |
Dan Willemsen | cc753b7 | 2021-08-31 13:25:42 -0700 | [diff] [blame] | 176 | |
Dan Willemsen | bc60c3c | 2021-12-15 01:09:00 -0800 | [diff] [blame] | 177 | if _Equal(s1, nil) { |
| 178 | panic(fmt.Sprintf("_Equal(%v, nil) = true, want false", s1)) |
| 179 | } |
| 180 | if _Equal(nil, s1) { |
| 181 | panic(fmt.Sprintf("_Equal(nil, %v) = true, want false", s1)) |
| 182 | } |
| 183 | if !_Equal(s1[:0], nil) { |
| 184 | panic(fmt.Sprintf("_Equal(%v, nil = false, want true", s1[:0])) |
| 185 | } |
Dan Willemsen | cc753b7 | 2021-08-31 13:25:42 -0700 | [diff] [blame] | 186 | } |
| 187 | |
| 188 | func offByOne[Elem Integer](a, b Elem) bool { |
Dan Willemsen | bc60c3c | 2021-12-15 01:09:00 -0800 | [diff] [blame] | 189 | return a == b+1 || a == b-1 |
Dan Willemsen | cc753b7 | 2021-08-31 13:25:42 -0700 | [diff] [blame] | 190 | } |
| 191 | |
| 192 | func TestEqualFn() { |
| 193 | s1 := []int{1, 2, 3} |
| 194 | s2 := []int{2, 3, 4} |
| 195 | if _EqualFn(s1, s1, offByOne[int]) { |
| 196 | panic(fmt.Sprintf("_EqualFn(%v, %v, offByOne) = true, want false", s1, s1)) |
| 197 | } |
| 198 | if !_EqualFn(s1, s2, offByOne[int]) { |
| 199 | panic(fmt.Sprintf("_EqualFn(%v, %v, offByOne) = false, want true", s1, s2)) |
| 200 | } |
| 201 | |
| 202 | if !_EqualFn(s1[:0], nil, offByOne[int]) { |
| 203 | panic(fmt.Sprintf("_EqualFn(%v, nil, offByOne) = false, want true", s1[:0])) |
| 204 | } |
| 205 | |
| 206 | s3 := []string{"a", "b", "c"} |
| 207 | s4 := []string{"A", "B", "C"} |
| 208 | if !_EqualFn(s3, s4, strings.EqualFold) { |
| 209 | panic(fmt.Sprintf("_EqualFn(%v, %v, strings.EqualFold) = false, want true", s3, s4)) |
| 210 | } |
| 211 | } |
| 212 | |
| 213 | func TestMap() { |
| 214 | s1 := []int{1, 2, 3} |
| 215 | s2 := _Map(s1, func(i int) float64 { return float64(i) * 2.5 }) |
| 216 | if want := []float64{2.5, 5, 7.5}; !_Equal(s2, want) { |
| 217 | panic(fmt.Sprintf("_Map(%v, ...) = %v, want %v", s1, s2, want)) |
| 218 | } |
| 219 | |
| 220 | s3 := []string{"Hello", "World"} |
| 221 | s4 := _Map(s3, strings.ToLower) |
| 222 | if want := []string{"hello", "world"}; !_Equal(s4, want) { |
| 223 | panic(fmt.Sprintf("_Map(%v, strings.ToLower) = %v, want %v", s3, s4, want)) |
| 224 | } |
| 225 | |
| 226 | s5 := _Map(nil, func(i int) int { return i }) |
| 227 | if len(s5) != 0 { |
| 228 | panic(fmt.Sprintf("_Map(nil, identity) = %v, want empty slice", s5)) |
| 229 | } |
| 230 | } |
| 231 | |
| 232 | func TestReduce() { |
| 233 | s1 := []int{1, 2, 3} |
Dan Willemsen | bc60c3c | 2021-12-15 01:09:00 -0800 | [diff] [blame] | 234 | r := _Reduce(s1, 0, func(f float64, i int) float64 { return float64(i)*2.5 + f }) |
Dan Willemsen | cc753b7 | 2021-08-31 13:25:42 -0700 | [diff] [blame] | 235 | if want := 15.0; r != want { |
| 236 | panic(fmt.Sprintf("_Reduce(%v, 0, ...) = %v, want %v", s1, r, want)) |
| 237 | } |
| 238 | |
Dan Willemsen | bc60c3c | 2021-12-15 01:09:00 -0800 | [diff] [blame] | 239 | if got := _Reduce(nil, 0, func(i, j int) int { return i + j }); got != 0 { |
Dan Willemsen | cc753b7 | 2021-08-31 13:25:42 -0700 | [diff] [blame] | 240 | panic(fmt.Sprintf("_Reduce(nil, 0, add) = %v, want 0", got)) |
| 241 | } |
| 242 | } |
| 243 | |
| 244 | func TestFilter() { |
| 245 | s1 := []int{1, 2, 3} |
| 246 | s2 := _Filter(s1, func(i int) bool { return i%2 == 0 }) |
| 247 | if want := []int{2}; !_Equal(s2, want) { |
| 248 | panic(fmt.Sprintf("_Filter(%v, even) = %v, want %v", s1, s2, want)) |
| 249 | } |
| 250 | |
| 251 | if s3 := _Filter(s1[:0], func(i int) bool { return true }); len(s3) > 0 { |
| 252 | panic(fmt.Sprintf("_Filter(%v, identity) = %v, want empty slice", s1[:0], s3)) |
| 253 | } |
| 254 | } |
| 255 | |
| 256 | func TestMax() { |
| 257 | s1 := []int{1, 2, 3, -5} |
| 258 | if got, want := _SliceMax(s1), 3; got != want { |
| 259 | panic(fmt.Sprintf("_Max(%v) = %d, want %d", s1, got, want)) |
| 260 | } |
| 261 | |
| 262 | s2 := []string{"aaa", "a", "aa", "aaaa"} |
| 263 | if got, want := _SliceMax(s2), "aaaa"; got != want { |
| 264 | panic(fmt.Sprintf("_Max(%v) = %q, want %q", s2, got, want)) |
| 265 | } |
| 266 | |
| 267 | if got, want := _SliceMax(s2[:0]), ""; got != want { |
| 268 | panic(fmt.Sprintf("_Max(%v) = %q, want %q", s2[:0], got, want)) |
| 269 | } |
| 270 | } |
| 271 | |
| 272 | func TestMin() { |
| 273 | s1 := []int{1, 2, 3, -5} |
| 274 | if got, want := _SliceMin(s1), -5; got != want { |
| 275 | panic(fmt.Sprintf("_Min(%v) = %d, want %d", s1, got, want)) |
| 276 | } |
| 277 | |
| 278 | s2 := []string{"aaa", "a", "aa", "aaaa"} |
| 279 | if got, want := _SliceMin(s2), "a"; got != want { |
| 280 | panic(fmt.Sprintf("_Min(%v) = %q, want %q", s2, got, want)) |
| 281 | } |
| 282 | |
| 283 | if got, want := _SliceMin(s2[:0]), ""; got != want { |
| 284 | panic(fmt.Sprintf("_Min(%v) = %q, want %q", s2[:0], got, want)) |
| 285 | } |
| 286 | } |
| 287 | |
| 288 | func TestAppend() { |
| 289 | s := []int{1, 2, 3} |
| 290 | s = _Append(s, 4, 5, 6) |
| 291 | want := []int{1, 2, 3, 4, 5, 6} |
| 292 | if !_Equal(s, want) { |
| 293 | panic(fmt.Sprintf("after _Append got %v, want %v", s, want)) |
| 294 | } |
| 295 | } |
| 296 | |
| 297 | func TestCopy() { |
| 298 | s1 := []int{1, 2, 3} |
| 299 | s2 := []int{4, 5} |
| 300 | if got := _Copy(s1, s2); got != 2 { |
| 301 | panic(fmt.Sprintf("_Copy returned %d, want 2", got)) |
| 302 | } |
| 303 | want := []int{4, 5, 3} |
| 304 | if !_Equal(s1, want) { |
| 305 | panic(fmt.Sprintf("after _Copy got %v, want %v", s1, want)) |
| 306 | } |
| 307 | } |
| 308 | func main() { |
| 309 | TestEqual() |
| 310 | TestEqualFn() |
| 311 | TestMap() |
| 312 | TestReduce() |
| 313 | TestFilter() |
| 314 | TestMax() |
| 315 | TestMin() |
| 316 | TestAppend() |
| 317 | TestCopy() |
| 318 | } |