diff options
author | Daniel Baumann <daniel.baumann@progress-linux.org> | 2024-04-16 19:23:18 +0000 |
---|---|---|
committer | Daniel Baumann <daniel.baumann@progress-linux.org> | 2024-04-16 19:23:18 +0000 |
commit | 43a123c1ae6613b3efeed291fa552ecd909d3acf (patch) | |
tree | fd92518b7024bc74031f78a1cf9e454b65e73665 /src/sort/search_test.go | |
parent | Initial commit. (diff) | |
download | golang-1.20-43a123c1ae6613b3efeed291fa552ecd909d3acf.tar.xz golang-1.20-43a123c1ae6613b3efeed291fa552ecd909d3acf.zip |
Adding upstream version 1.20.14.upstream/1.20.14upstream
Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>
Diffstat (limited to 'src/sort/search_test.go')
-rw-r--r-- | src/sort/search_test.go | 266 |
1 files changed, 266 insertions, 0 deletions
diff --git a/src/sort/search_test.go b/src/sort/search_test.go new file mode 100644 index 0000000..49813ea --- /dev/null +++ b/src/sort/search_test.go @@ -0,0 +1,266 @@ +// Copyright 2010 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 sort_test + +import ( + "runtime" + . "sort" + stringspkg "strings" + "testing" +) + +func f(a []int, x int) func(int) bool { + return func(i int) bool { + return a[i] >= x + } +} + +var data = []int{0: -10, 1: -5, 2: 0, 3: 1, 4: 2, 5: 3, 6: 5, 7: 7, 8: 11, 9: 100, 10: 100, 11: 100, 12: 1000, 13: 10000} + +var tests = []struct { + name string + n int + f func(int) bool + i int +}{ + {"empty", 0, nil, 0}, + {"1 1", 1, func(i int) bool { return i >= 1 }, 1}, + {"1 true", 1, func(i int) bool { return true }, 0}, + {"1 false", 1, func(i int) bool { return false }, 1}, + {"1e9 991", 1e9, func(i int) bool { return i >= 991 }, 991}, + {"1e9 true", 1e9, func(i int) bool { return true }, 0}, + {"1e9 false", 1e9, func(i int) bool { return false }, 1e9}, + {"data -20", len(data), f(data, -20), 0}, + {"data -10", len(data), f(data, -10), 0}, + {"data -9", len(data), f(data, -9), 1}, + {"data -6", len(data), f(data, -6), 1}, + {"data -5", len(data), f(data, -5), 1}, + {"data 3", len(data), f(data, 3), 5}, + {"data 11", len(data), f(data, 11), 8}, + {"data 99", len(data), f(data, 99), 9}, + {"data 100", len(data), f(data, 100), 9}, + {"data 101", len(data), f(data, 101), 12}, + {"data 10000", len(data), f(data, 10000), 13}, + {"data 10001", len(data), f(data, 10001), 14}, + {"descending a", 7, func(i int) bool { return []int{99, 99, 59, 42, 7, 0, -1, -1}[i] <= 7 }, 4}, + {"descending 7", 1e9, func(i int) bool { return 1e9-i <= 7 }, 1e9 - 7}, + {"overflow", 2e9, func(i int) bool { return false }, 2e9}, +} + +func TestSearch(t *testing.T) { + for _, e := range tests { + i := Search(e.n, e.f) + if i != e.i { + t.Errorf("%s: expected index %d; got %d", e.name, e.i, i) + } + } +} + +func TestFind(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) { + cmp := func(i int) int { + return stringspkg.Compare(tt.target, tt.data[i]) + } + + pos, found := Find(len(tt.data), cmp) + if pos != tt.wantPos || found != tt.wantFound { + t.Errorf("Find got (%v, %v), want (%v, %v)", pos, found, tt.wantPos, tt.wantFound) + } + }) + } +} + +// log2 computes the binary logarithm of x, rounded up to the next integer. +// (log2(0) == 0, log2(1) == 0, log2(2) == 1, log2(3) == 2, etc.) +func log2(x int) int { + n := 0 + for p := 1; p < x; p += p { + // p == 2**n + n++ + } + // p/2 < x <= p == 2**n + return n +} + +func TestSearchEfficiency(t *testing.T) { + n := 100 + step := 1 + for exp := 2; exp < 10; exp++ { + // n == 10**exp + // step == 10**(exp-2) + max := log2(n) + for x := 0; x < n; x += step { + count := 0 + i := Search(n, func(i int) bool { count++; return i >= x }) + if i != x { + t.Errorf("n = %d: expected index %d; got %d", n, x, i) + } + if count > max { + t.Errorf("n = %d, x = %d: expected <= %d calls; got %d", n, x, max, count) + } + } + n *= 10 + step *= 10 + } +} + +// Smoke tests for convenience wrappers - not comprehensive. + +var fdata = []float64{0: -3.14, 1: 0, 2: 1, 3: 2, 4: 1000.7} +var sdata = []string{0: "f", 1: "foo", 2: "foobar", 3: "x"} + +var wrappertests = []struct { + name string + result int + i int +}{ + {"SearchInts", SearchInts(data, 11), 8}, + {"SearchFloat64s", SearchFloat64s(fdata, 2.1), 4}, + {"SearchStrings", SearchStrings(sdata, ""), 0}, + {"IntSlice.Search", IntSlice(data).Search(0), 2}, + {"Float64Slice.Search", Float64Slice(fdata).Search(2.0), 3}, + {"StringSlice.Search", StringSlice(sdata).Search("x"), 3}, +} + +func TestSearchWrappers(t *testing.T) { + for _, e := range wrappertests { + if e.result != e.i { + t.Errorf("%s: expected index %d; got %d", e.name, e.i, e.result) + } + } +} + +func runSearchWrappers() { + SearchInts(data, 11) + SearchFloat64s(fdata, 2.1) + SearchStrings(sdata, "") + IntSlice(data).Search(0) + Float64Slice(fdata).Search(2.0) + StringSlice(sdata).Search("x") +} + +func TestSearchWrappersDontAlloc(t *testing.T) { + if testing.Short() { + t.Skip("skipping malloc count in short mode") + } + if runtime.GOMAXPROCS(0) > 1 { + t.Skip("skipping; GOMAXPROCS>1") + } + allocs := testing.AllocsPerRun(100, runSearchWrappers) + if allocs != 0 { + t.Errorf("expected no allocs for runSearchWrappers, got %v", allocs) + } +} + +func BenchmarkSearchWrappers(b *testing.B) { + for i := 0; i < b.N; i++ { + runSearchWrappers() + } +} + +// Abstract exhaustive test: all sizes up to 100, +// all possible return values. If there are any small +// corner cases, this test exercises them. +func TestSearchExhaustive(t *testing.T) { + for size := 0; size <= 100; size++ { + for targ := 0; targ <= size; targ++ { + i := Search(size, func(i int) bool { return i >= targ }) + if i != targ { + t.Errorf("Search(%d, %d) = %d", size, targ, i) + } + } + } +} + +// Abstract exhaustive test for Find. +func TestFindExhaustive(t *testing.T) { + // Test Find for different sequence sizes and search targets. + // For each size, we have a (unmaterialized) sequence of integers: + // 2,4...size*2 + // And we're looking for every possible integer between 1 and size*2 + 1. + for size := 0; size <= 100; size++ { + for x := 1; x <= size*2+1; x++ { + var wantFound bool + var wantPos int + + cmp := func(i int) int { + // Encodes the unmaterialized sequence with elem[i] == (i+1)*2 + return x - (i+1)*2 + } + pos, found := Find(size, cmp) + + if x%2 == 0 { + wantPos = x/2 - 1 + wantFound = true + } else { + wantPos = x / 2 + wantFound = false + } + if found != wantFound || pos != wantPos { + t.Errorf("Find(%d, %d): got (%v, %v), want (%v, %v)", size, x, pos, found, wantPos, wantFound) + } + } + } +} |