1
2
3
4
5 package slices
6
7 import (
8 "math"
9 "strings"
10 "testing"
11 )
12
13 var raceEnabled bool
14
15 var equalIntTests = []struct {
16 s1, s2 []int
17 want bool
18 }{
19 {
20 []int{1},
21 nil,
22 false,
23 },
24 {
25 []int{},
26 nil,
27 true,
28 },
29 {
30 []int{1, 2, 3},
31 []int{1, 2, 3},
32 true,
33 },
34 {
35 []int{1, 2, 3},
36 []int{1, 2, 3, 4},
37 false,
38 },
39 }
40
41 var equalFloatTests = []struct {
42 s1, s2 []float64
43 wantEqual bool
44 wantEqualNaN bool
45 }{
46 {
47 []float64{1, 2},
48 []float64{1, 2},
49 true,
50 true,
51 },
52 {
53 []float64{1, 2, math.NaN()},
54 []float64{1, 2, math.NaN()},
55 false,
56 true,
57 },
58 }
59
60 func TestEqual(t *testing.T) {
61 for _, test := range equalIntTests {
62 if got := Equal(test.s1, test.s2); got != test.want {
63 t.Errorf("Equal(%v, %v) = %t, want %t", test.s1, test.s2, got, test.want)
64 }
65 }
66 for _, test := range equalFloatTests {
67 if got := Equal(test.s1, test.s2); got != test.wantEqual {
68 t.Errorf("Equal(%v, %v) = %t, want %t", test.s1, test.s2, got, test.wantEqual)
69 }
70 }
71 }
72
73
74 func equal[T comparable](v1, v2 T) bool {
75 return v1 == v2
76 }
77
78
79 func equalNaN[T comparable](v1, v2 T) bool {
80 isNaN := func(f T) bool { return f != f }
81 return v1 == v2 || (isNaN(v1) && isNaN(v2))
82 }
83
84
85 func offByOne(v1, v2 int) bool {
86 return v1 == v2+1 || v1 == v2-1
87 }
88
89 func TestEqualFunc(t *testing.T) {
90 for _, test := range equalIntTests {
91 if got := EqualFunc(test.s1, test.s2, equal[int]); got != test.want {
92 t.Errorf("EqualFunc(%v, %v, equal[int]) = %t, want %t", test.s1, test.s2, got, test.want)
93 }
94 }
95 for _, test := range equalFloatTests {
96 if got := EqualFunc(test.s1, test.s2, equal[float64]); got != test.wantEqual {
97 t.Errorf("Equal(%v, %v, equal[float64]) = %t, want %t", test.s1, test.s2, got, test.wantEqual)
98 }
99 if got := EqualFunc(test.s1, test.s2, equalNaN[float64]); got != test.wantEqualNaN {
100 t.Errorf("Equal(%v, %v, equalNaN[float64]) = %t, want %t", test.s1, test.s2, got, test.wantEqualNaN)
101 }
102 }
103
104 s1 := []int{1, 2, 3}
105 s2 := []int{2, 3, 4}
106 if EqualFunc(s1, s1, offByOne) {
107 t.Errorf("EqualFunc(%v, %v, offByOne) = true, want false", s1, s1)
108 }
109 if !EqualFunc(s1, s2, offByOne) {
110 t.Errorf("EqualFunc(%v, %v, offByOne) = false, want true", s1, s2)
111 }
112
113 s3 := []string{"a", "b", "c"}
114 s4 := []string{"A", "B", "C"}
115 if !EqualFunc(s3, s4, strings.EqualFold) {
116 t.Errorf("EqualFunc(%v, %v, strings.EqualFold) = false, want true", s3, s4)
117 }
118
119 cmpIntString := func(v1 int, v2 string) bool {
120 return string(rune(v1)-1+'a') == v2
121 }
122 if !EqualFunc(s1, s3, cmpIntString) {
123 t.Errorf("EqualFunc(%v, %v, cmpIntString) = false, want true", s1, s3)
124 }
125 }
126
127 func BenchmarkEqualFunc_Large(b *testing.B) {
128 type Large [4 * 1024]byte
129
130 xs := make([]Large, 1024)
131 ys := make([]Large, 1024)
132 for i := 0; i < b.N; i++ {
133 _ = EqualFunc(xs, ys, func(x, y Large) bool { return x == y })
134 }
135 }
136
137 var compareIntTests = []struct {
138 s1, s2 []int
139 want int
140 }{
141 {
142 []int{1},
143 []int{1},
144 0,
145 },
146 {
147 []int{1},
148 []int{},
149 1,
150 },
151 {
152 []int{},
153 []int{1},
154 -1,
155 },
156 {
157 []int{},
158 []int{},
159 0,
160 },
161 {
162 []int{1, 2, 3},
163 []int{1, 2, 3},
164 0,
165 },
166 {
167 []int{1, 2, 3},
168 []int{1, 2, 3, 4},
169 -1,
170 },
171 {
172 []int{1, 2, 3, 4},
173 []int{1, 2, 3},
174 +1,
175 },
176 {
177 []int{1, 2, 3},
178 []int{1, 4, 3},
179 -1,
180 },
181 {
182 []int{1, 4, 3},
183 []int{1, 2, 3},
184 +1,
185 },
186 {
187 []int{1, 4, 3},
188 []int{1, 2, 3, 8, 9},
189 +1,
190 },
191 }
192
193 var compareFloatTests = []struct {
194 s1, s2 []float64
195 want int
196 }{
197 {
198 []float64{},
199 []float64{},
200 0,
201 },
202 {
203 []float64{1},
204 []float64{1},
205 0,
206 },
207 {
208 []float64{math.NaN()},
209 []float64{math.NaN()},
210 0,
211 },
212 {
213 []float64{1, 2, math.NaN()},
214 []float64{1, 2, math.NaN()},
215 0,
216 },
217 {
218 []float64{1, math.NaN(), 3},
219 []float64{1, math.NaN(), 4},
220 -1,
221 },
222 {
223 []float64{1, math.NaN(), 3},
224 []float64{1, 2, 4},
225 -1,
226 },
227 {
228 []float64{1, math.NaN(), 3},
229 []float64{1, 2, math.NaN()},
230 -1,
231 },
232 {
233 []float64{1, 2, 3},
234 []float64{1, 2, math.NaN()},
235 +1,
236 },
237 {
238 []float64{1, 2, 3},
239 []float64{1, math.NaN(), 3},
240 +1,
241 },
242 {
243 []float64{1, math.NaN(), 3, 4},
244 []float64{1, 2, math.NaN()},
245 -1,
246 },
247 }
248
249 func TestCompare(t *testing.T) {
250 intWant := func(want bool) string {
251 if want {
252 return "0"
253 }
254 return "!= 0"
255 }
256 for _, test := range equalIntTests {
257 if got := Compare(test.s1, test.s2); (got == 0) != test.want {
258 t.Errorf("Compare(%v, %v) = %d, want %s", test.s1, test.s2, got, intWant(test.want))
259 }
260 }
261 for _, test := range equalFloatTests {
262 if got := Compare(test.s1, test.s2); (got == 0) != test.wantEqualNaN {
263 t.Errorf("Compare(%v, %v) = %d, want %s", test.s1, test.s2, got, intWant(test.wantEqualNaN))
264 }
265 }
266
267 for _, test := range compareIntTests {
268 if got := Compare(test.s1, test.s2); got != test.want {
269 t.Errorf("Compare(%v, %v) = %d, want %d", test.s1, test.s2, got, test.want)
270 }
271 }
272 for _, test := range compareFloatTests {
273 if got := Compare(test.s1, test.s2); got != test.want {
274 t.Errorf("Compare(%v, %v) = %d, want %d", test.s1, test.s2, got, test.want)
275 }
276 }
277 }
278
279 func equalToCmp[T comparable](eq func(T, T) bool) func(T, T) int {
280 return func(v1, v2 T) int {
281 if eq(v1, v2) {
282 return 0
283 }
284 return 1
285 }
286 }
287
288 func TestCompareFunc(t *testing.T) {
289 intWant := func(want bool) string {
290 if want {
291 return "0"
292 }
293 return "!= 0"
294 }
295 for _, test := range equalIntTests {
296 if got := CompareFunc(test.s1, test.s2, equalToCmp(equal[int])); (got == 0) != test.want {
297 t.Errorf("CompareFunc(%v, %v, equalToCmp(equal[int])) = %d, want %s", test.s1, test.s2, got, intWant(test.want))
298 }
299 }
300 for _, test := range equalFloatTests {
301 if got := CompareFunc(test.s1, test.s2, equalToCmp(equal[float64])); (got == 0) != test.wantEqual {
302 t.Errorf("CompareFunc(%v, %v, equalToCmp(equal[float64])) = %d, want %s", test.s1, test.s2, got, intWant(test.wantEqual))
303 }
304 }
305
306 for _, test := range compareIntTests {
307 if got := CompareFunc(test.s1, test.s2, cmpCompare[int]); got != test.want {
308 t.Errorf("CompareFunc(%v, %v, cmp[int]) = %d, want %d", test.s1, test.s2, got, test.want)
309 }
310 }
311 for _, test := range compareFloatTests {
312 if got := CompareFunc(test.s1, test.s2, cmpCompare[float64]); got != test.want {
313 t.Errorf("CompareFunc(%v, %v, cmp[float64]) = %d, want %d", test.s1, test.s2, got, test.want)
314 }
315 }
316
317 s1 := []int{1, 2, 3}
318 s2 := []int{2, 3, 4}
319 if got := CompareFunc(s1, s2, equalToCmp(offByOne)); got != 0 {
320 t.Errorf("CompareFunc(%v, %v, offByOne) = %d, want 0", s1, s2, got)
321 }
322
323 s3 := []string{"a", "b", "c"}
324 s4 := []string{"A", "B", "C"}
325 if got := CompareFunc(s3, s4, strings.Compare); got != 1 {
326 t.Errorf("CompareFunc(%v, %v, strings.Compare) = %d, want 1", s3, s4, got)
327 }
328
329 compareLower := func(v1, v2 string) int {
330 return strings.Compare(strings.ToLower(v1), strings.ToLower(v2))
331 }
332 if got := CompareFunc(s3, s4, compareLower); got != 0 {
333 t.Errorf("CompareFunc(%v, %v, compareLower) = %d, want 0", s3, s4, got)
334 }
335
336 cmpIntString := func(v1 int, v2 string) int {
337 return strings.Compare(string(rune(v1)-1+'a'), v2)
338 }
339 if got := CompareFunc(s1, s3, cmpIntString); got != 0 {
340 t.Errorf("CompareFunc(%v, %v, cmpIntString) = %d, want 0", s1, s3, got)
341 }
342 }
343
344 var indexTests = []struct {
345 s []int
346 v int
347 want int
348 }{
349 {
350 nil,
351 0,
352 -1,
353 },
354 {
355 []int{},
356 0,
357 -1,
358 },
359 {
360 []int{1, 2, 3},
361 2,
362 1,
363 },
364 {
365 []int{1, 2, 2, 3},
366 2,
367 1,
368 },
369 {
370 []int{1, 2, 3, 2},
371 2,
372 1,
373 },
374 }
375
376 func TestIndex(t *testing.T) {
377 for _, test := range indexTests {
378 if got := Index(test.s, test.v); got != test.want {
379 t.Errorf("Index(%v, %v) = %d, want %d", test.s, test.v, got, test.want)
380 }
381 }
382 }
383
384 func equalToIndex[T any](f func(T, T) bool, v1 T) func(T) bool {
385 return func(v2 T) bool {
386 return f(v1, v2)
387 }
388 }
389
390 func BenchmarkIndex_Large(b *testing.B) {
391 type Large [4 * 1024]byte
392
393 ss := make([]Large, 1024)
394 for i := 0; i < b.N; i++ {
395 _ = Index(ss, Large{1})
396 }
397 }
398
399 func TestIndexFunc(t *testing.T) {
400 for _, test := range indexTests {
401 if got := IndexFunc(test.s, equalToIndex(equal[int], test.v)); got != test.want {
402 t.Errorf("IndexFunc(%v, equalToIndex(equal[int], %v)) = %d, want %d", test.s, test.v, got, test.want)
403 }
404 }
405
406 s1 := []string{"hi", "HI"}
407 if got := IndexFunc(s1, equalToIndex(equal[string], "HI")); got != 1 {
408 t.Errorf("IndexFunc(%v, equalToIndex(equal[string], %q)) = %d, want %d", s1, "HI", got, 1)
409 }
410 if got := IndexFunc(s1, equalToIndex(strings.EqualFold, "HI")); got != 0 {
411 t.Errorf("IndexFunc(%v, equalToIndex(strings.EqualFold, %q)) = %d, want %d", s1, "HI", got, 0)
412 }
413 }
414
415 func BenchmarkIndexFunc_Large(b *testing.B) {
416 type Large [4 * 1024]byte
417
418 ss := make([]Large, 1024)
419 for i := 0; i < b.N; i++ {
420 _ = IndexFunc(ss, func(e Large) bool {
421 return e == Large{1}
422 })
423 }
424 }
425
426 func TestContains(t *testing.T) {
427 for _, test := range indexTests {
428 if got := Contains(test.s, test.v); got != (test.want != -1) {
429 t.Errorf("Contains(%v, %v) = %t, want %t", test.s, test.v, got, test.want != -1)
430 }
431 }
432 }
433
434 func TestContainsFunc(t *testing.T) {
435 for _, test := range indexTests {
436 if got := ContainsFunc(test.s, equalToIndex(equal[int], test.v)); got != (test.want != -1) {
437 t.Errorf("ContainsFunc(%v, equalToIndex(equal[int], %v)) = %t, want %t", test.s, test.v, got, test.want != -1)
438 }
439 }
440
441 s1 := []string{"hi", "HI"}
442 if got := ContainsFunc(s1, equalToIndex(equal[string], "HI")); got != true {
443 t.Errorf("ContainsFunc(%v, equalToContains(equal[string], %q)) = %t, want %t", s1, "HI", got, true)
444 }
445 if got := ContainsFunc(s1, equalToIndex(equal[string], "hI")); got != false {
446 t.Errorf("ContainsFunc(%v, equalToContains(strings.EqualFold, %q)) = %t, want %t", s1, "hI", got, false)
447 }
448 if got := ContainsFunc(s1, equalToIndex(strings.EqualFold, "hI")); got != true {
449 t.Errorf("ContainsFunc(%v, equalToContains(strings.EqualFold, %q)) = %t, want %t", s1, "hI", got, true)
450 }
451 }
452
453 var insertTests = []struct {
454 s []int
455 i int
456 add []int
457 want []int
458 }{
459 {
460 []int{1, 2, 3},
461 0,
462 []int{4},
463 []int{4, 1, 2, 3},
464 },
465 {
466 []int{1, 2, 3},
467 1,
468 []int{4},
469 []int{1, 4, 2, 3},
470 },
471 {
472 []int{1, 2, 3},
473 3,
474 []int{4},
475 []int{1, 2, 3, 4},
476 },
477 {
478 []int{1, 2, 3},
479 2,
480 []int{4, 5},
481 []int{1, 2, 4, 5, 3},
482 },
483 }
484
485 func TestInsert(t *testing.T) {
486 s := []int{1, 2, 3}
487 if got := Insert(s, 0); !Equal(got, s) {
488 t.Errorf("Insert(%v, 0) = %v, want %v", s, got, s)
489 }
490 for _, test := range insertTests {
491 copy := Clone(test.s)
492 if got := Insert(copy, test.i, test.add...); !Equal(got, test.want) {
493 t.Errorf("Insert(%v, %d, %v...) = %v, want %v", test.s, test.i, test.add, got, test.want)
494 }
495 }
496
497 if !raceEnabled {
498
499 const count = 50
500 n := testing.AllocsPerRun(10, func() {
501 s := []int{1, 2, 3}
502 for i := 0; i < count; i++ {
503 s = Insert(s, 0, 1)
504 }
505 })
506 if n > count/2 {
507 t.Errorf("too many allocations inserting %d elements: got %v, want less than %d", count, n, count/2)
508 }
509 }
510 }
511
512 func TestInsertOverlap(t *testing.T) {
513 const N = 10
514 a := make([]int, N)
515 want := make([]int, 2*N)
516 for n := 0; n <= N; n++ {
517 for i := 0; i <= n; i++ {
518 for x := 0; x <= N; x++ {
519 for y := x; y <= N; y++ {
520 for k := 0; k < N; k++ {
521 a[k] = k
522 }
523 want = want[:0]
524 want = append(want, a[:i]...)
525 want = append(want, a[x:y]...)
526 want = append(want, a[i:n]...)
527 got := Insert(a[:n], i, a[x:y]...)
528 if !Equal(got, want) {
529 t.Errorf("Insert with overlap failed n=%d i=%d x=%d y=%d, got %v want %v", n, i, x, y, got, want)
530 }
531 }
532 }
533 }
534 }
535 }
536
537 var deleteTests = []struct {
538 s []int
539 i, j int
540 want []int
541 }{
542 {
543 []int{1, 2, 3},
544 0,
545 0,
546 []int{1, 2, 3},
547 },
548 {
549 []int{1, 2, 3},
550 0,
551 1,
552 []int{2, 3},
553 },
554 {
555 []int{1, 2, 3},
556 3,
557 3,
558 []int{1, 2, 3},
559 },
560 {
561 []int{1, 2, 3},
562 0,
563 2,
564 []int{3},
565 },
566 {
567 []int{1, 2, 3},
568 0,
569 3,
570 []int{},
571 },
572 }
573
574 func TestDelete(t *testing.T) {
575 for _, test := range deleteTests {
576 copy := Clone(test.s)
577 if got := Delete(copy, test.i, test.j); !Equal(got, test.want) {
578 t.Errorf("Delete(%v, %d, %d) = %v, want %v", test.s, test.i, test.j, got, test.want)
579 }
580 }
581 }
582
583 var deleteFuncTests = []struct {
584 s []int
585 fn func(int) bool
586 want []int
587 }{
588 {
589 nil,
590 func(int) bool { return true },
591 nil,
592 },
593 {
594 []int{1, 2, 3},
595 func(int) bool { return true },
596 nil,
597 },
598 {
599 []int{1, 2, 3},
600 func(int) bool { return false },
601 []int{1, 2, 3},
602 },
603 {
604 []int{1, 2, 3},
605 func(i int) bool { return i > 2 },
606 []int{1, 2},
607 },
608 {
609 []int{1, 2, 3},
610 func(i int) bool { return i < 2 },
611 []int{2, 3},
612 },
613 {
614 []int{10, 2, 30},
615 func(i int) bool { return i >= 10 },
616 []int{2},
617 },
618 }
619
620 func TestDeleteFunc(t *testing.T) {
621 for i, test := range deleteFuncTests {
622 copy := Clone(test.s)
623 if got := DeleteFunc(copy, test.fn); !Equal(got, test.want) {
624 t.Errorf("DeleteFunc case %d: got %v, want %v", i, got, test.want)
625 }
626 }
627 }
628
629 func panics(f func()) (b bool) {
630 defer func() {
631 if x := recover(); x != nil {
632 b = true
633 }
634 }()
635 f()
636 return false
637 }
638
639 func TestDeletePanics(t *testing.T) {
640 for _, test := range []struct {
641 name string
642 s []int
643 i, j int
644 }{
645 {"with negative first index", []int{42}, -2, 1},
646 {"with negative second index", []int{42}, 1, -1},
647 {"with out-of-bounds first index", []int{42}, 2, 3},
648 {"with out-of-bounds second index", []int{42}, 0, 2},
649 {"with invalid i>j", []int{42}, 1, 0},
650 } {
651 if !panics(func() { Delete(test.s, test.i, test.j) }) {
652 t.Errorf("Delete %s: got no panic, want panic", test.name)
653 }
654 }
655 }
656
657 func TestDeleteClearTail(t *testing.T) {
658 mem := []*int{new(int), new(int), new(int), new(int), new(int), new(int)}
659 s := mem[0:5]
660
661 s = Delete(s, 2, 4)
662
663 if mem[3] != nil || mem[4] != nil {
664
665 t.Errorf("Delete: want nil discarded elements, got %v, %v", mem[3], mem[4])
666 }
667 if mem[5] == nil {
668 t.Errorf("Delete: want unchanged elements beyond original len, got nil")
669 }
670 }
671
672 func TestDeleteFuncClearTail(t *testing.T) {
673 mem := []*int{new(int), new(int), new(int), new(int), new(int), new(int)}
674 *mem[2], *mem[3] = 42, 42
675 s := mem[0:5]
676
677 s = DeleteFunc(s, func(i *int) bool {
678 return i != nil && *i == 42
679 })
680
681 if mem[3] != nil || mem[4] != nil {
682
683 t.Errorf("DeleteFunc: want nil discarded elements, got %v, %v", mem[3], mem[4])
684 }
685 if mem[5] == nil {
686 t.Errorf("DeleteFunc: want unchanged elements beyond original len, got nil")
687 }
688 }
689
690 func TestClone(t *testing.T) {
691 s1 := []int{1, 2, 3}
692 s2 := Clone(s1)
693 if !Equal(s1, s2) {
694 t.Errorf("Clone(%v) = %v, want %v", s1, s2, s1)
695 }
696 s1[0] = 4
697 want := []int{1, 2, 3}
698 if !Equal(s2, want) {
699 t.Errorf("Clone(%v) changed unexpectedly to %v", want, s2)
700 }
701 if got := Clone([]int(nil)); got != nil {
702 t.Errorf("Clone(nil) = %#v, want nil", got)
703 }
704 if got := Clone(s1[:0]); got == nil || len(got) != 0 {
705 t.Errorf("Clone(%v) = %#v, want %#v", s1[:0], got, s1[:0])
706 }
707 }
708
709 var compactTests = []struct {
710 name string
711 s []int
712 want []int
713 }{
714 {
715 "nil",
716 nil,
717 nil,
718 },
719 {
720 "one",
721 []int{1},
722 []int{1},
723 },
724 {
725 "sorted",
726 []int{1, 2, 3},
727 []int{1, 2, 3},
728 },
729 {
730 "1 item",
731 []int{1, 1, 2},
732 []int{1, 2},
733 },
734 {
735 "unsorted",
736 []int{1, 2, 1},
737 []int{1, 2, 1},
738 },
739 {
740 "many",
741 []int{1, 2, 2, 3, 3, 4},
742 []int{1, 2, 3, 4},
743 },
744 }
745
746 func TestCompact(t *testing.T) {
747 for _, test := range compactTests {
748 copy := Clone(test.s)
749 if got := Compact(copy); !Equal(got, test.want) {
750 t.Errorf("Compact(%v) = %v, want %v", test.s, got, test.want)
751 }
752 }
753 }
754
755 func BenchmarkCompact(b *testing.B) {
756 for _, c := range compactTests {
757 b.Run(c.name, func(b *testing.B) {
758 ss := make([]int, 0, 64)
759 for k := 0; k < b.N; k++ {
760 ss = ss[:0]
761 ss = append(ss, c.s...)
762 _ = Compact(ss)
763 }
764 })
765 }
766 }
767
768 func BenchmarkCompact_Large(b *testing.B) {
769 type Large [4 * 1024]byte
770
771 ss := make([]Large, 1024)
772 for i := 0; i < b.N; i++ {
773 _ = Compact(ss)
774 }
775 }
776
777 func TestCompactFunc(t *testing.T) {
778 for _, test := range compactTests {
779 copy := Clone(test.s)
780 if got := CompactFunc(copy, equal[int]); !Equal(got, test.want) {
781 t.Errorf("CompactFunc(%v, equal[int]) = %v, want %v", test.s, got, test.want)
782 }
783 }
784
785 s1 := []string{"a", "a", "A", "B", "b"}
786 copy := Clone(s1)
787 want := []string{"a", "B"}
788 if got := CompactFunc(copy, strings.EqualFold); !Equal(got, want) {
789 t.Errorf("CompactFunc(%v, strings.EqualFold) = %v, want %v", s1, got, want)
790 }
791 }
792
793 func TestCompactClearTail(t *testing.T) {
794 one, two, three, four := 1, 2, 3, 4
795 mem := []*int{&one, &one, &two, &two, &three, &four}
796 s := mem[0:5]
797 copy := Clone(s)
798
799 s = Compact(s)
800
801 if want := []*int{&one, &two, &three}; !Equal(s, want) {
802 t.Errorf("Compact(%v) = %v, want %v", copy, s, want)
803 }
804
805 if mem[3] != nil || mem[4] != nil {
806
807 t.Errorf("Compact: want nil discarded elements, got %v, %v", mem[3], mem[4])
808 }
809 if mem[5] != &four {
810 t.Errorf("Compact: want unchanged element beyond original len, got %v", mem[5])
811 }
812 }
813
814 func TestCompactFuncClearTail(t *testing.T) {
815 a, b, c, d, e, f := 1, 1, 2, 2, 3, 4
816 mem := []*int{&a, &b, &c, &d, &e, &f}
817 s := mem[0:5]
818 copy := Clone(s)
819
820 s = CompactFunc(s, func(x, y *int) bool {
821 if x == nil || y == nil {
822 return x == y
823 }
824 return *x == *y
825 })
826
827 if want := []*int{&a, &c, &e}; !Equal(s, want) {
828 t.Errorf("CompactFunc(%v) = %v, want %v", copy, s, want)
829 }
830
831 if mem[3] != nil || mem[4] != nil {
832
833 t.Errorf("CompactFunc: want nil discarded elements, got %v, %v", mem[3], mem[4])
834 }
835 if mem[5] != &f {
836 t.Errorf("CompactFunc: want unchanged elements beyond original len, got %v", mem[5])
837 }
838 }
839
840 func BenchmarkCompactFunc_Large(b *testing.B) {
841 type Large [4 * 1024]byte
842
843 ss := make([]Large, 1024)
844 for i := 0; i < b.N; i++ {
845 _ = CompactFunc(ss, func(a, b Large) bool { return a == b })
846 }
847 }
848
849 func TestGrow(t *testing.T) {
850 s1 := []int{1, 2, 3}
851
852 copy := Clone(s1)
853 s2 := Grow(copy, 1000)
854 if !Equal(s1, s2) {
855 t.Errorf("Grow(%v) = %v, want %v", s1, s2, s1)
856 }
857 if cap(s2) < 1000+len(s1) {
858 t.Errorf("after Grow(%v) cap = %d, want >= %d", s1, cap(s2), 1000+len(s1))
859 }
860
861
862 copy = Clone(s1)
863 s3 := Grow(copy[:1], 2)[:3]
864 if !Equal(s1, s3) {
865 t.Errorf("Grow should not mutate elements between length and capacity")
866 }
867 s3 = Grow(copy[:1], 1000)[:3]
868 if !Equal(s1, s3) {
869 t.Errorf("Grow should not mutate elements between length and capacity")
870 }
871
872
873 if n := testing.AllocsPerRun(100, func() { Grow(s2, cap(s2)-len(s2)) }); n != 0 {
874 t.Errorf("Grow should not allocate when given sufficient capacity; allocated %v times", n)
875 }
876 if n := testing.AllocsPerRun(100, func() { Grow(s2, cap(s2)-len(s2)+1) }); n != 1 {
877 errorf := t.Errorf
878 if raceEnabled {
879 errorf = t.Logf
880 }
881 errorf("Grow should allocate once when given insufficient capacity; allocated %v times", n)
882 }
883
884
885 var gotPanic bool
886 func() {
887 defer func() { gotPanic = recover() != nil }()
888 Grow(s1, -1)
889 }()
890 if !gotPanic {
891 t.Errorf("Grow(-1) did not panic; expected a panic")
892 }
893 }
894
895 func TestClip(t *testing.T) {
896 s1 := []int{1, 2, 3, 4, 5, 6}[:3]
897 orig := Clone(s1)
898 if len(s1) != 3 {
899 t.Errorf("len(%v) = %d, want 3", s1, len(s1))
900 }
901 if cap(s1) < 6 {
902 t.Errorf("cap(%v[:3]) = %d, want >= 6", orig, cap(s1))
903 }
904 s2 := Clip(s1)
905 if !Equal(s1, s2) {
906 t.Errorf("Clip(%v) = %v, want %v", s1, s2, s1)
907 }
908 if cap(s2) != 3 {
909 t.Errorf("cap(Clip(%v)) = %d, want 3", orig, cap(s2))
910 }
911 }
912
913 func TestReverse(t *testing.T) {
914 even := []int{3, 1, 4, 1, 5, 9}
915 Reverse(even)
916 if want := []int{9, 5, 1, 4, 1, 3}; !Equal(even, want) {
917 t.Errorf("Reverse(even) = %v, want %v", even, want)
918 }
919
920 odd := []int{3, 1, 4, 1, 5, 9, 2}
921 Reverse(odd)
922 if want := []int{2, 9, 5, 1, 4, 1, 3}; !Equal(odd, want) {
923 t.Errorf("Reverse(odd) = %v, want %v", odd, want)
924 }
925
926 words := strings.Fields("one two three")
927 Reverse(words)
928 if want := strings.Fields("three two one"); !Equal(words, want) {
929 t.Errorf("Reverse(words) = %v, want %v", words, want)
930 }
931
932 singleton := []string{"one"}
933 Reverse(singleton)
934 if want := []string{"one"}; !Equal(singleton, want) {
935 t.Errorf("Reverse(singeleton) = %v, want %v", singleton, want)
936 }
937
938 Reverse[[]string](nil)
939 }
940
941
942 func naiveReplace[S ~[]E, E any](s S, i, j int, v ...E) S {
943 s = Delete(s, i, j)
944 s = Insert(s, i, v...)
945 return s
946 }
947
948 func TestReplace(t *testing.T) {
949 for _, test := range []struct {
950 s, v []int
951 i, j int
952 }{
953 {},
954 {
955 s: []int{1, 2, 3, 4},
956 v: []int{5},
957 i: 1,
958 j: 2,
959 },
960 {
961 s: []int{1, 2, 3, 4},
962 v: []int{5, 6, 7, 8},
963 i: 1,
964 j: 2,
965 },
966 {
967 s: func() []int {
968 s := make([]int, 3, 20)
969 s[0] = 0
970 s[1] = 1
971 s[2] = 2
972 return s
973 }(),
974 v: []int{3, 4, 5, 6, 7},
975 i: 0,
976 j: 1,
977 },
978 } {
979 ss, vv := Clone(test.s), Clone(test.v)
980 want := naiveReplace(ss, test.i, test.j, vv...)
981 got := Replace(test.s, test.i, test.j, test.v...)
982 if !Equal(got, want) {
983 t.Errorf("Replace(%v, %v, %v, %v) = %v, want %v", test.s, test.i, test.j, test.v, got, want)
984 }
985 }
986 }
987
988 func TestReplacePanics(t *testing.T) {
989 for _, test := range []struct {
990 name string
991 s, v []int
992 i, j int
993 }{
994 {"indexes out of order", []int{1, 2}, []int{3}, 2, 1},
995 {"large index", []int{1, 2}, []int{3}, 1, 10},
996 {"negative index", []int{1, 2}, []int{3}, -1, 2},
997 } {
998 ss, vv := Clone(test.s), Clone(test.v)
999 if !panics(func() { Replace(ss, test.i, test.j, vv...) }) {
1000 t.Errorf("Replace %s: should have panicked", test.name)
1001 }
1002 }
1003 }
1004
1005 func TestReplaceGrow(t *testing.T) {
1006
1007
1008 a, b, c, d, e, f := 1, 2, 3, 4, 5, 6
1009 mem := []*int{&a, &b, &c, &d, &e, &f}
1010 memcopy := Clone(mem)
1011 s := mem[0:5]
1012 copy := Clone(s)
1013 original := s
1014
1015
1016 z := 99
1017 s = Replace(s, 1, 3, &z, &z, &z, &z)
1018
1019 if want := []*int{&a, &z, &z, &z, &z, &d, &e}; !Equal(s, want) {
1020 t.Errorf("Replace(%v, 1, 3, %v, %v, %v, %v) = %v, want %v", copy, &z, &z, &z, &z, s, want)
1021 }
1022
1023 if !Equal(original, copy) {
1024 t.Errorf("original slice has changed, got %v, want %v", original, copy)
1025 }
1026
1027 if !Equal(mem, memcopy) {
1028
1029 t.Errorf("original backing memory has changed, got %v, want %v", mem, memcopy)
1030 }
1031 }
1032
1033 func TestReplaceClearTail(t *testing.T) {
1034 a, b, c, d, e, f := 1, 2, 3, 4, 5, 6
1035 mem := []*int{&a, &b, &c, &d, &e, &f}
1036 s := mem[0:5]
1037 copy := Clone(s)
1038
1039 y, z := 8, 9
1040 s = Replace(s, 1, 4, &y, &z)
1041
1042 if want := []*int{&a, &y, &z, &e}; !Equal(s, want) {
1043 t.Errorf("Replace(%v) = %v, want %v", copy, s, want)
1044 }
1045
1046 if mem[4] != nil {
1047
1048 t.Errorf("Replace: want nil discarded element, got %v", mem[4])
1049 }
1050 if mem[5] != &f {
1051 t.Errorf("Replace: want unchanged elements beyond original len, got %v", mem[5])
1052 }
1053 }
1054
1055 func TestReplaceOverlap(t *testing.T) {
1056 const N = 10
1057 a := make([]int, N)
1058 want := make([]int, 2*N)
1059 for n := 0; n <= N; n++ {
1060 for i := 0; i <= n; i++ {
1061 for j := i; j <= n; j++ {
1062 for x := 0; x <= N; x++ {
1063 for y := x; y <= N; y++ {
1064 for k := 0; k < N; k++ {
1065 a[k] = k
1066 }
1067 want = want[:0]
1068 want = append(want, a[:i]...)
1069 want = append(want, a[x:y]...)
1070 want = append(want, a[j:n]...)
1071 got := Replace(a[:n], i, j, a[x:y]...)
1072 if !Equal(got, want) {
1073 t.Errorf("Insert with overlap failed n=%d i=%d j=%d x=%d y=%d, got %v want %v", n, i, j, x, y, got, want)
1074 }
1075 }
1076 }
1077 }
1078 }
1079 }
1080 }
1081
1082 func BenchmarkReplace(b *testing.B) {
1083 cases := []struct {
1084 name string
1085 s, v func() []int
1086 i, j int
1087 }{
1088 {
1089 name: "fast",
1090 s: func() []int {
1091 return make([]int, 100)
1092 },
1093 v: func() []int {
1094 return make([]int, 20)
1095 },
1096 i: 10,
1097 j: 40,
1098 },
1099 {
1100 name: "slow",
1101 s: func() []int {
1102 return make([]int, 100)
1103 },
1104 v: func() []int {
1105 return make([]int, 20)
1106 },
1107 i: 0,
1108 j: 2,
1109 },
1110 }
1111
1112 for _, c := range cases {
1113 b.Run("naive-"+c.name, func(b *testing.B) {
1114 for k := 0; k < b.N; k++ {
1115 s := c.s()
1116 v := c.v()
1117 _ = naiveReplace(s, c.i, c.j, v...)
1118 }
1119 })
1120 b.Run("optimized-"+c.name, func(b *testing.B) {
1121 for k := 0; k < b.N; k++ {
1122 s := c.s()
1123 v := c.v()
1124 _ = Replace(s, c.i, c.j, v...)
1125 }
1126 })
1127 }
1128
1129 }
1130
1131 func TestRotate(t *testing.T) {
1132 const N = 10
1133 s := make([]int, 0, N)
1134 for n := 0; n < N; n++ {
1135 for r := 0; r < n; r++ {
1136 s = s[:0]
1137 for i := 0; i < n; i++ {
1138 s = append(s, i)
1139 }
1140 rotateLeft(s, r)
1141 for i := 0; i < n; i++ {
1142 if s[i] != (i+r)%n {
1143 t.Errorf("expected n=%d r=%d i:%d want:%d got:%d", n, r, i, (i+r)%n, s[i])
1144 }
1145 }
1146 }
1147 }
1148 }
1149
1150 func TestInsertGrowthRate(t *testing.T) {
1151 b := make([]byte, 1)
1152 maxCap := cap(b)
1153 nGrow := 0
1154 const N = 1e6
1155 for i := 0; i < N; i++ {
1156 b = Insert(b, len(b)-1, 0)
1157 if cap(b) > maxCap {
1158 maxCap = cap(b)
1159 nGrow++
1160 }
1161 }
1162 want := int(math.Log(N) / math.Log(1.25))
1163 if nGrow > want {
1164 t.Errorf("too many grows. got:%d want:%d", nGrow, want)
1165 }
1166 }
1167
1168 func TestReplaceGrowthRate(t *testing.T) {
1169 b := make([]byte, 2)
1170 maxCap := cap(b)
1171 nGrow := 0
1172 const N = 1e6
1173 for i := 0; i < N; i++ {
1174 b = Replace(b, len(b)-2, len(b)-1, 0, 0)
1175 if cap(b) > maxCap {
1176 maxCap = cap(b)
1177 nGrow++
1178 }
1179 }
1180 want := int(math.Log(N) / math.Log(1.25))
1181 if nGrow > want {
1182 t.Errorf("too many grows. got:%d want:%d", nGrow, want)
1183 }
1184 }
1185
View as plain text