diff options
Diffstat (limited to '')
-rw-r--r-- | dependencies/pkg/mod/golang.org/x/exp@v0.0.0-20220613132600-b0d781184e0d/slices/sort_test.go | 285 |
1 files changed, 285 insertions, 0 deletions
diff --git a/dependencies/pkg/mod/golang.org/x/exp@v0.0.0-20220613132600-b0d781184e0d/slices/sort_test.go b/dependencies/pkg/mod/golang.org/x/exp@v0.0.0-20220613132600-b0d781184e0d/slices/sort_test.go new file mode 100644 index 0000000..9a52992 --- /dev/null +++ b/dependencies/pkg/mod/golang.org/x/exp@v0.0.0-20220613132600-b0d781184e0d/slices/sort_test.go @@ -0,0 +1,285 @@ +// Copyright 2022 The Go Authors. All rights reserved. +// Use of this source code is governed by a BSD-style +// license that can be found in the LICENSE file. + +package slices + +import ( + "math" + "math/rand" + "sort" + "strconv" + "strings" + "testing" +) + +var ints = [...]int{74, 59, 238, -784, 9845, 959, 905, 0, 0, 42, 7586, -5467984, 7586} +var float64s = [...]float64{74.3, 59.0, math.Inf(1), 238.2, -784.0, 2.3, math.Inf(-1), 9845.768, -959.7485, 905, 7.8, 7.8, 74.3, 59.0, math.Inf(1), 238.2, -784.0, 2.3} +var float64sWithNaNs = [...]float64{74.3, 59.0, math.Inf(1), 238.2, -784.0, 2.3, math.NaN(), math.NaN(), math.Inf(-1), 9845.768, -959.7485, 905, 7.8, 7.8} +var strs = [...]string{"", "Hello", "foo", "bar", "foo", "f00", "%*&^*&^&", "***"} + +func TestSortIntSlice(t *testing.T) { + data := ints[:] + Sort(data) + if !IsSorted(data) { + t.Errorf("sorted %v", ints) + t.Errorf(" got %v", data) + } +} + +func TestSortFuncIntSlice(t *testing.T) { + data := ints[:] + SortFunc(data, func(a, b int) bool { return a < b }) + if !IsSorted(data) { + t.Errorf("sorted %v", ints) + t.Errorf(" got %v", data) + } +} + +func TestSortFloat64Slice(t *testing.T) { + data := float64s[:] + Sort(data) + if !IsSorted(data) { + t.Errorf("sorted %v", float64s) + t.Errorf(" got %v", data) + } +} + +func TestSortFloat64SliceWithNaNs(t *testing.T) { + data := float64sWithNaNs[:] + input := make([]float64, len(float64sWithNaNs)) + for i := range input { + input[i] = float64sWithNaNs[i] + } + // Make sure Sort doesn't panic when the slice contains NaNs. + Sort(data) + // Check whether the result is a permutation of the input. + sort.Float64s(data) + sort.Float64s(input) + for i, v := range input { + if data[i] != v && !(math.IsNaN(data[i]) && math.IsNaN(v)) { + t.Fatalf("the result is not a permutation of the input\ngot %v\nwant %v", data, input) + } + } +} + +func TestSortStringSlice(t *testing.T) { + data := strs[:] + Sort(data) + if !IsSorted(data) { + t.Errorf("sorted %v", strs) + t.Errorf(" got %v", data) + } +} + +func TestSortLarge_Random(t *testing.T) { + n := 1000000 + if testing.Short() { + n /= 100 + } + data := make([]int, n) + for i := 0; i < len(data); i++ { + data[i] = rand.Intn(100) + } + if IsSorted(data) { + t.Fatalf("terrible rand.rand") + } + Sort(data) + if !IsSorted(data) { + t.Errorf("sort didn't sort - 1M ints") + } +} + +type intPair struct { + a, b int +} + +type intPairs []intPair + +// Pairs compare on a only. +func intPairLess(x, y intPair) bool { + return x.a < y.a +} + +// Record initial order in B. +func (d intPairs) initB() { + for i := range d { + d[i].b = i + } +} + +// InOrder checks if a-equal elements were not reordered. +func (d intPairs) inOrder() bool { + lastA, lastB := -1, 0 + for i := 0; i < len(d); i++ { + if lastA != d[i].a { + lastA = d[i].a + lastB = d[i].b + continue + } + if d[i].b <= lastB { + return false + } + lastB = d[i].b + } + return true +} + +func TestStability(t *testing.T) { + n, m := 100000, 1000 + if testing.Short() { + n, m = 1000, 100 + } + data := make(intPairs, n) + + // random distribution + for i := 0; i < len(data); i++ { + data[i].a = rand.Intn(m) + } + if IsSortedFunc(data, intPairLess) { + t.Fatalf("terrible rand.rand") + } + data.initB() + SortStableFunc(data, intPairLess) + if !IsSortedFunc(data, intPairLess) { + t.Errorf("Stable didn't sort %d ints", n) + } + if !data.inOrder() { + t.Errorf("Stable wasn't stable on %d ints", n) + } + + // already sorted + data.initB() + SortStableFunc(data, intPairLess) + if !IsSortedFunc(data, intPairLess) { + t.Errorf("Stable shuffled sorted %d ints (order)", n) + } + if !data.inOrder() { + t.Errorf("Stable shuffled sorted %d ints (stability)", n) + } + + // sorted reversed + for i := 0; i < len(data); i++ { + data[i].a = len(data) - i + } + data.initB() + SortStableFunc(data, intPairLess) + if !IsSortedFunc(data, intPairLess) { + t.Errorf("Stable didn't sort %d ints", n) + } + if !data.inOrder() { + t.Errorf("Stable wasn't stable on %d ints", n) + } +} + +func TestBinarySearch(t *testing.T) { + str1 := []string{"foo"} + str2 := []string{"ab", "ca"} + str3 := []string{"mo", "qo", "vo"} + str4 := []string{"ab", "ad", "ca", "xy"} + + // slice with repeating elements + strRepeats := []string{"ba", "ca", "da", "da", "da", "ka", "ma", "ma", "ta"} + + // slice with all element equal + strSame := []string{"xx", "xx", "xx"} + + tests := []struct { + data []string + target string + wantPos int + wantFound bool + }{ + {[]string{}, "foo", 0, false}, + {[]string{}, "", 0, false}, + + {str1, "foo", 0, true}, + {str1, "bar", 0, false}, + {str1, "zx", 1, false}, + + {str2, "aa", 0, false}, + {str2, "ab", 0, true}, + {str2, "ad", 1, false}, + {str2, "ca", 1, true}, + {str2, "ra", 2, false}, + + {str3, "bb", 0, false}, + {str3, "mo", 0, true}, + {str3, "nb", 1, false}, + {str3, "qo", 1, true}, + {str3, "tr", 2, false}, + {str3, "vo", 2, true}, + {str3, "xr", 3, false}, + + {str4, "aa", 0, false}, + {str4, "ab", 0, true}, + {str4, "ac", 1, false}, + {str4, "ad", 1, true}, + {str4, "ax", 2, false}, + {str4, "ca", 2, true}, + {str4, "cc", 3, false}, + {str4, "dd", 3, false}, + {str4, "xy", 3, true}, + {str4, "zz", 4, false}, + + {strRepeats, "da", 2, true}, + {strRepeats, "db", 5, false}, + {strRepeats, "ma", 6, true}, + {strRepeats, "mb", 8, false}, + + {strSame, "xx", 0, true}, + {strSame, "ab", 0, false}, + {strSame, "zz", 3, false}, + } + for _, tt := range tests { + t.Run(tt.target, func(t *testing.T) { + { + pos, found := BinarySearch(tt.data, tt.target) + if pos != tt.wantPos || found != tt.wantFound { + t.Errorf("BinarySearch got (%v, %v), want (%v, %v)", pos, found, tt.wantPos, tt.wantFound) + } + } + + { + pos, found := BinarySearchFunc(tt.data, tt.target, strings.Compare) + if pos != tt.wantPos || found != tt.wantFound { + t.Errorf("BinarySearchFunc got (%v, %v), want (%v, %v)", pos, found, tt.wantPos, tt.wantFound) + } + } + }) + } +} + +func TestBinarySearchInts(t *testing.T) { + data := []int{20, 30, 40, 50, 60, 70, 80, 90} + tests := []struct { + target int + wantPos int + wantFound bool + }{ + {20, 0, true}, + {23, 1, false}, + {43, 3, false}, + {80, 6, true}, + } + for _, tt := range tests { + t.Run(strconv.Itoa(tt.target), func(t *testing.T) { + { + pos, found := BinarySearch(data, tt.target) + if pos != tt.wantPos || found != tt.wantFound { + t.Errorf("BinarySearch got (%v, %v), want (%v, %v)", pos, found, tt.wantPos, tt.wantFound) + } + } + + { + cmp := func(a, b int) int { + return a - b + } + pos, found := BinarySearchFunc(data, tt.target, cmp) + if pos != tt.wantPos || found != tt.wantFound { + t.Errorf("BinarySearchFunc got (%v, %v), want (%v, %v)", pos, found, tt.wantPos, tt.wantFound) + } + } + }) + } +} |