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.
9package main
10
11import (
12	"fmt"
13	"math"
14	"strings"
15)
16
17type Ordered interface {
18	~int | ~int8 | ~int16 | ~int32 | ~int64 |
19		~uint | ~uint8 | ~uint16 | ~uint32 | ~uint64 | ~uintptr |
20		~float32 | ~float64 |
21		~string
22}
23
24type Integer interface {
25	~int | ~int8 | ~int16 | ~int32 | ~int64 |
26		~uint | ~uint8 | ~uint16 | ~uint32 | ~uint64 | ~uintptr
27}
28
29// Max returns the maximum of two values of some ordered type.
30func _Max[T Ordered](a, b T) T {
31	if a > b {
32		return a
33	}
34	return b
35}
36
37// Min returns the minimum of two values of some ordered type.
38func _Min[T Ordered](a, b T) T {
39	if a < b {
40		return a
41	}
42	return b
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.
47func _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
63// _EqualFn reports whether two slices are equal using a comparison
64// function on each element.
65func _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.
79func _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.
89func _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.
98func _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.
110func _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.
120func _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.
133func _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 {
139		news := make([]T, tot, tot+tot/2)
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.
150func _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
158func TestEqual() {
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	}
171
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	}
176
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	}
186}
187
188func offByOne[Elem Integer](a, b Elem) bool {
189	return a == b+1 || a == b-1
190}
191
192func 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
213func 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
232func TestReduce() {
233	s1 := []int{1, 2, 3}
234	r := _Reduce(s1, 0, func(f float64, i int) float64 { return float64(i)*2.5 + f })
235	if want := 15.0; r != want {
236		panic(fmt.Sprintf("_Reduce(%v, 0, ...) = %v, want %v", s1, r, want))
237	}
238
239	if got := _Reduce(nil, 0, func(i, j int) int { return i + j }); got != 0 {
240		panic(fmt.Sprintf("_Reduce(nil, 0, add) = %v, want 0", got))
241	}
242}
243
244func 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
256func 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
272func 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
288func 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
297func 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}
308func main() {
309	TestEqual()
310	TestEqualFn()
311	TestMap()
312	TestReduce()
313	TestFilter()
314	TestMax()
315	TestMin()
316	TestAppend()
317	TestCopy()
318}
319