codekingpro/portable-devtools

1// Copyright 2010 The Go Authors. All rights reserved.2// Use of this source code is governed by a BSD-style3// license that can be found in the LICENSE file.4 5package sort_test6 7import (8	"math/bits"9	"runtime"10	. "sort"11	stringspkg "strings"12	"testing"13)14 15func f(a []int, x int) func(int) bool {16	return func(i int) bool {17		return a[i] >= x18	}19}20 21var 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}22 23var tests = []struct {24	name string25	n    int26	f    func(int) bool27	i    int28}{29	{"empty", 0, nil, 0},30	{"1 1", 1, func(i int) bool { return i >= 1 }, 1},31	{"1 true", 1, func(i int) bool { return true }, 0},32	{"1 false", 1, func(i int) bool { return false }, 1},33	{"1e9 991", 1e9, func(i int) bool { return i >= 991 }, 991},34	{"1e9 true", 1e9, func(i int) bool { return true }, 0},35	{"1e9 false", 1e9, func(i int) bool { return false }, 1e9},36	{"data -20", len(data), f(data, -20), 0},37	{"data -10", len(data), f(data, -10), 0},38	{"data -9", len(data), f(data, -9), 1},39	{"data -6", len(data), f(data, -6), 1},40	{"data -5", len(data), f(data, -5), 1},41	{"data 3", len(data), f(data, 3), 5},42	{"data 11", len(data), f(data, 11), 8},43	{"data 99", len(data), f(data, 99), 9},44	{"data 100", len(data), f(data, 100), 9},45	{"data 101", len(data), f(data, 101), 12},46	{"data 10000", len(data), f(data, 10000), 13},47	{"data 10001", len(data), f(data, 10001), 14},48	{"descending a", 7, func(i int) bool { return []int{99, 99, 59, 42, 7, 0, -1, -1}[i] <= 7 }, 4},49	{"descending 7", 1e9, func(i int) bool { return 1e9-i <= 7 }, 1e9 - 7},50	{"overflow", 2e9, func(i int) bool { return false }, 2e9},51}52 53func TestSearch(t *testing.T) {54	for _, e := range tests {55		i := Search(e.n, e.f)56		if i != e.i {57			t.Errorf("%s: expected index %d; got %d", e.name, e.i, i)58		}59	}60}61 62func TestFind(t *testing.T) {63	str1 := []string{"foo"}64	str2 := []string{"ab", "ca"}65	str3 := []string{"mo", "qo", "vo"}66	str4 := []string{"ab", "ad", "ca", "xy"}67 68	// slice with repeating elements69	strRepeats := []string{"ba", "ca", "da", "da", "da", "ka", "ma", "ma", "ta"}70 71	// slice with all element equal72	strSame := []string{"xx", "xx", "xx"}73 74	tests := []struct {75		data      []string76		target    string77		wantPos   int78		wantFound bool79	}{80		{[]string{}, "foo", 0, false},81		{[]string{}, "", 0, false},82 83		{str1, "foo", 0, true},84		{str1, "bar", 0, false},85		{str1, "zx", 1, false},86 87		{str2, "aa", 0, false},88		{str2, "ab", 0, true},89		{str2, "ad", 1, false},90		{str2, "ca", 1, true},91		{str2, "ra", 2, false},92 93		{str3, "bb", 0, false},94		{str3, "mo", 0, true},95		{str3, "nb", 1, false},96		{str3, "qo", 1, true},97		{str3, "tr", 2, false},98		{str3, "vo", 2, true},99		{str3, "xr", 3, false},100 101		{str4, "aa", 0, false},102		{str4, "ab", 0, true},103		{str4, "ac", 1, false},104		{str4, "ad", 1, true},105		{str4, "ax", 2, false},106		{str4, "ca", 2, true},107		{str4, "cc", 3, false},108		{str4, "dd", 3, false},109		{str4, "xy", 3, true},110		{str4, "zz", 4, false},111 112		{strRepeats, "da", 2, true},113		{strRepeats, "db", 5, false},114		{strRepeats, "ma", 6, true},115		{strRepeats, "mb", 8, false},116 117		{strSame, "xx", 0, true},118		{strSame, "ab", 0, false},119		{strSame, "zz", 3, false},120	}121 122	for _, tt := range tests {123		t.Run(tt.target, func(t *testing.T) {124			cmp := func(i int) int {125				return stringspkg.Compare(tt.target, tt.data[i])126			}127 128			pos, found := Find(len(tt.data), cmp)129			if pos != tt.wantPos || found != tt.wantFound {130				t.Errorf("Find got (%v, %v), want (%v, %v)", pos, found, tt.wantPos, tt.wantFound)131			}132		})133	}134}135 136// log2 computes the binary logarithm of x, rounded up to the next integer.137// (log2(0) == 0, log2(1) == 0, log2(2) == 1, log2(3) == 2, etc.)138func log2(x int) int {139	if x < 1 {140		return 0141	}142	return bits.Len(uint(x - 1))143}144 145func TestSearchEfficiency(t *testing.T) {146	n := 100147	step := 1148	for exp := 2; exp < 10; exp++ {149		// n == 10**exp150		// step == 10**(exp-2)151		max := log2(n)152		for x := 0; x < n; x += step {153			count := 0154			i := Search(n, func(i int) bool { count++; return i >= x })155			if i != x {156				t.Errorf("n = %d: expected index %d; got %d", n, x, i)157			}158			if count > max {159				t.Errorf("n = %d, x = %d: expected <= %d calls; got %d", n, x, max, count)160			}161		}162		n *= 10163		step *= 10164	}165}166 167// Smoke tests for convenience wrappers - not comprehensive.168 169var fdata = []float64{0: -3.14, 1: 0, 2: 1, 3: 2, 4: 1000.7}170var sdata = []string{0: "f", 1: "foo", 2: "foobar", 3: "x"}171 172var wrappertests = []struct {173	name   string174	result int175	i      int176}{177	{"SearchInts", SearchInts(data, 11), 8},178	{"SearchFloat64s", SearchFloat64s(fdata, 2.1), 4},179	{"SearchStrings", SearchStrings(sdata, ""), 0},180	{"IntSlice.Search", IntSlice(data).Search(0), 2},181	{"Float64Slice.Search", Float64Slice(fdata).Search(2.0), 3},182	{"StringSlice.Search", StringSlice(sdata).Search("x"), 3},183}184 185func TestSearchWrappers(t *testing.T) {186	for _, e := range wrappertests {187		if e.result != e.i {188			t.Errorf("%s: expected index %d; got %d", e.name, e.i, e.result)189		}190	}191}192 193func runSearchWrappers() {194	SearchInts(data, 11)195	SearchFloat64s(fdata, 2.1)196	SearchStrings(sdata, "")197	IntSlice(data).Search(0)198	Float64Slice(fdata).Search(2.0)199	StringSlice(sdata).Search("x")200}201 202func TestSearchWrappersDontAlloc(t *testing.T) {203	if testing.Short() {204		t.Skip("skipping malloc count in short mode")205	}206	if runtime.GOMAXPROCS(0) > 1 {207		t.Skip("skipping; GOMAXPROCS>1")208	}209	allocs := testing.AllocsPerRun(100, runSearchWrappers)210	if allocs != 0 {211		t.Errorf("expected no allocs for runSearchWrappers, got %v", allocs)212	}213}214 215func BenchmarkSearchWrappers(b *testing.B) {216	for i := 0; i < b.N; i++ {217		runSearchWrappers()218	}219}220 221// Abstract exhaustive test: all sizes up to 100,222// all possible return values. If there are any small223// corner cases, this test exercises them.224func TestSearchExhaustive(t *testing.T) {225	for size := 0; size <= 100; size++ {226		for targ := 0; targ <= size; targ++ {227			i := Search(size, func(i int) bool { return i >= targ })228			if i != targ {229				t.Errorf("Search(%d, %d) = %d", size, targ, i)230			}231		}232	}233}234 235// Abstract exhaustive test for Find.236func TestFindExhaustive(t *testing.T) {237	// Test Find for different sequence sizes and search targets.238	// For each size, we have a (unmaterialized) sequence of integers:239	//   2,4...size*2240	// And we're looking for every possible integer between 1 and size*2 + 1.241	for size := 0; size <= 100; size++ {242		for x := 1; x <= size*2+1; x++ {243			var wantFound bool244			var wantPos int245 246			cmp := func(i int) int {247				// Encodes the unmaterialized sequence with elem[i] == (i+1)*2248				return x - (i+1)*2249			}250			pos, found := Find(size, cmp)251 252			if x%2 == 0 {253				wantPos = x/2 - 1254				wantFound = true255			} else {256				wantPos = x / 2257				wantFound = false258			}259			if found != wantFound || pos != wantPos {260				t.Errorf("Find(%d, %d): got (%v, %v), want (%v, %v)", size, x, pos, found, wantPos, wantFound)261			}262		}263	}264}265