1// Copyright 2024 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
5package slices_test
6
7import (
8	"iter"
9	"math/rand/v2"
10	. "slices"
11	"testing"
12)
13
14func TestAll(t *testing.T) {
15	for size := 0; size < 10; size++ {
16		var s []int
17		for i := range size {
18			s = append(s, i)
19		}
20		ei, ev := 0, 0
21		cnt := 0
22		for i, v := range All(s) {
23			if i != ei || v != ev {
24				t.Errorf("at iteration %d got %d, %d want %d, %d", cnt, i, v, ei, ev)
25			}
26			ei++
27			ev++
28			cnt++
29		}
30		if cnt != size {
31			t.Errorf("read %d values expected %d", cnt, size)
32		}
33	}
34}
35
36func TestBackward(t *testing.T) {
37	for size := 0; size < 10; size++ {
38		var s []int
39		for i := range size {
40			s = append(s, i)
41		}
42		ei, ev := size-1, size-1
43		cnt := 0
44		for i, v := range Backward(s) {
45			if i != ei || v != ev {
46				t.Errorf("at iteration %d got %d, %d want %d, %d", cnt, i, v, ei, ev)
47			}
48			ei--
49			ev--
50			cnt++
51		}
52		if cnt != size {
53			t.Errorf("read %d values expected %d", cnt, size)
54		}
55	}
56}
57
58func TestValues(t *testing.T) {
59	for size := 0; size < 10; size++ {
60		var s []int
61		for i := range size {
62			s = append(s, i)
63		}
64		ev := 0
65		cnt := 0
66		for v := range Values(s) {
67			if v != ev {
68				t.Errorf("at iteration %d got %d want %d", cnt, v, ev)
69			}
70			ev++
71			cnt++
72		}
73		if cnt != size {
74			t.Errorf("read %d values expected %d", cnt, size)
75		}
76	}
77}
78
79func testSeq(yield func(int) bool) {
80	for i := 0; i < 10; i += 2 {
81		if !yield(i) {
82			return
83		}
84	}
85}
86
87var testSeqResult = []int{0, 2, 4, 6, 8}
88
89func TestAppendSeq(t *testing.T) {
90	s := AppendSeq([]int{1, 2}, testSeq)
91	want := append([]int{1, 2}, testSeqResult...)
92	if !Equal(s, want) {
93		t.Errorf("got %v, want %v", s, want)
94	}
95}
96
97func TestCollect(t *testing.T) {
98	s := Collect(testSeq)
99	want := testSeqResult
100	if !Equal(s, want) {
101		t.Errorf("got %v, want %v", s, want)
102	}
103}
104
105var iterTests = [][]string{
106	nil,
107	{"a"},
108	{"a", "b"},
109	{"b", "a"},
110	strs[:],
111}
112
113func TestValuesAppendSeq(t *testing.T) {
114	for _, prefix := range iterTests {
115		for _, s := range iterTests {
116			got := AppendSeq(prefix, Values(s))
117			want := append(prefix, s...)
118			if !Equal(got, want) {
119				t.Errorf("AppendSeq(%v, Values(%v)) == %v, want %v", prefix, s, got, want)
120			}
121		}
122	}
123}
124
125func TestValuesCollect(t *testing.T) {
126	for _, s := range iterTests {
127		got := Collect(Values(s))
128		if !Equal(got, s) {
129			t.Errorf("Collect(Values(%v)) == %v, want %v", s, got, s)
130		}
131	}
132}
133
134func TestSorted(t *testing.T) {
135	s := Sorted(Values(ints[:]))
136	if !IsSorted(s) {
137		t.Errorf("sorted %v", ints)
138		t.Errorf("   got %v", s)
139	}
140}
141
142func TestSortedFunc(t *testing.T) {
143	s := SortedFunc(Values(ints[:]), func(a, b int) int { return a - b })
144	if !IsSorted(s) {
145		t.Errorf("sorted %v", ints)
146		t.Errorf("   got %v", s)
147	}
148}
149
150func TestSortedStableFunc(t *testing.T) {
151	n, m := 1000, 100
152	data := make(intPairs, n)
153	for i := range data {
154		data[i].a = rand.IntN(m)
155	}
156	data.initB()
157
158	s := intPairs(SortedStableFunc(Values(data), intPairCmp))
159	if !IsSortedFunc(s, intPairCmp) {
160		t.Errorf("SortedStableFunc didn't sort %d ints", n)
161	}
162	if !s.inOrder(false) {
163		t.Errorf("SortedStableFunc wasn't stable on %d ints", n)
164	}
165
166	// iterVal converts a Seq2 to a Seq.
167	iterVal := func(seq iter.Seq2[int, intPair]) iter.Seq[intPair] {
168		return func(yield func(intPair) bool) {
169			for _, v := range seq {
170				if !yield(v) {
171					return
172				}
173			}
174		}
175	}
176
177	s = intPairs(SortedStableFunc(iterVal(Backward(data)), intPairCmp))
178	if !IsSortedFunc(s, intPairCmp) {
179		t.Errorf("SortedStableFunc didn't sort %d reverse ints", n)
180	}
181	if !s.inOrder(true) {
182		t.Errorf("SortedStableFunc wasn't stable on %d reverse ints", n)
183	}
184}
185
186func TestChunk(t *testing.T) {
187	cases := []struct {
188		name   string
189		s      []int
190		n      int
191		chunks [][]int
192	}{
193		{
194			name:   "nil",
195			s:      nil,
196			n:      1,
197			chunks: nil,
198		},
199		{
200			name:   "empty",
201			s:      []int{},
202			n:      1,
203			chunks: nil,
204		},
205		{
206			name:   "short",
207			s:      []int{1, 2},
208			n:      3,
209			chunks: [][]int{{1, 2}},
210		},
211		{
212			name:   "one",
213			s:      []int{1, 2},
214			n:      2,
215			chunks: [][]int{{1, 2}},
216		},
217		{
218			name:   "even",
219			s:      []int{1, 2, 3, 4},
220			n:      2,
221			chunks: [][]int{{1, 2}, {3, 4}},
222		},
223		{
224			name:   "odd",
225			s:      []int{1, 2, 3, 4, 5},
226			n:      2,
227			chunks: [][]int{{1, 2}, {3, 4}, {5}},
228		},
229	}
230
231	for _, tc := range cases {
232		t.Run(tc.name, func(t *testing.T) {
233			var chunks [][]int
234			for c := range Chunk(tc.s, tc.n) {
235				chunks = append(chunks, c)
236			}
237
238			if !chunkEqual(chunks, tc.chunks) {
239				t.Errorf("Chunk(%v, %d) = %v, want %v", tc.s, tc.n, chunks, tc.chunks)
240			}
241
242			if len(chunks) == 0 {
243				return
244			}
245
246			// Verify that appending to the end of the first chunk does not
247			// clobber the beginning of the next chunk.
248			s := Clone(tc.s)
249			chunks[0] = append(chunks[0], -1)
250			if !Equal(s, tc.s) {
251				t.Errorf("slice was clobbered: %v, want %v", s, tc.s)
252			}
253		})
254	}
255}
256
257func TestChunkPanics(t *testing.T) {
258	for _, test := range []struct {
259		name string
260		x    []struct{}
261		n    int
262	}{
263		{
264			name: "cannot be less than 1",
265			x:    make([]struct{}, 0),
266			n:    0,
267		},
268	} {
269		if !panics(func() { _ = Chunk(test.x, test.n) }) {
270			t.Errorf("Chunk %s: got no panic, want panic", test.name)
271		}
272	}
273}
274
275func TestChunkRange(t *testing.T) {
276	// Verify Chunk iteration can be stopped.
277	var got [][]int
278	for c := range Chunk([]int{1, 2, 3, 4, -100}, 2) {
279		if len(got) == 2 {
280			// Found enough values, break early.
281			break
282		}
283
284		got = append(got, c)
285	}
286
287	if want := [][]int{{1, 2}, {3, 4}}; !chunkEqual(got, want) {
288		t.Errorf("Chunk iteration did not stop, got %v, want %v", got, want)
289	}
290}
291
292func chunkEqual[Slice ~[]E, E comparable](s1, s2 []Slice) bool {
293	return EqualFunc(s1, s2, Equal[Slice])
294}
295