Home | History | Annotate | Download | only in sort 
      1 // Copyright 2010 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 
      5 package sort_test
      6 
      7 import (
      8 	"runtime"
      9 	. "sort"
     10 	"testing"
     11 )
     12 
     13 func f(a []int, x int) func(int) bool {
     14 	return func(i int) bool {
     15 		return a[i] >= x
     16 	}
     17 }
     18 
     19 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}
     20 
     21 var tests = []struct {
     22 	name string
     23 	n    int
     24 	f    func(int) bool
     25 	i    int
     26 }{
     27 	{"empty", 0, nil, 0},
     28 	{"1 1", 1, func(i int) bool { return i >= 1 }, 1},
     29 	{"1 true", 1, func(i int) bool { return true }, 0},
     30 	{"1 false", 1, func(i int) bool { return false }, 1},
     31 	{"1e9 991", 1e9, func(i int) bool { return i >= 991 }, 991},
     32 	{"1e9 true", 1e9, func(i int) bool { return true }, 0},
     33 	{"1e9 false", 1e9, func(i int) bool { return false }, 1e9},
     34 	{"data -20", len(data), f(data, -20), 0},
     35 	{"data -10", len(data), f(data, -10), 0},
     36 	{"data -9", len(data), f(data, -9), 1},
     37 	{"data -6", len(data), f(data, -6), 1},
     38 	{"data -5", len(data), f(data, -5), 1},
     39 	{"data 3", len(data), f(data, 3), 5},
     40 	{"data 11", len(data), f(data, 11), 8},
     41 	{"data 99", len(data), f(data, 99), 9},
     42 	{"data 100", len(data), f(data, 100), 9},
     43 	{"data 101", len(data), f(data, 101), 12},
     44 	{"data 10000", len(data), f(data, 10000), 13},
     45 	{"data 10001", len(data), f(data, 10001), 14},
     46 	{"descending a", 7, func(i int) bool { return []int{99, 99, 59, 42, 7, 0, -1, -1}[i] <= 7 }, 4},
     47 	{"descending 7", 1e9, func(i int) bool { return 1e9-i <= 7 }, 1e9 - 7},
     48 	{"overflow", 2e9, func(i int) bool { return false }, 2e9},
     49 }
     50 
     51 func TestSearch(t *testing.T) {
     52 	for _, e := range tests {
     53 		i := Search(e.n, e.f)
     54 		if i != e.i {
     55 			t.Errorf("%s: expected index %d; got %d", e.name, e.i, i)
     56 		}
     57 	}
     58 }
     59 
     60 // log2 computes the binary logarithm of x, rounded up to the next integer.
     61 // (log2(0) == 0, log2(1) == 0, log2(2) == 1, log2(3) == 2, etc.)
     62 //
     63 func log2(x int) int {
     64 	n := 0
     65 	for p := 1; p < x; p += p {
     66 		// p == 2**n
     67 		n++
     68 	}
     69 	// p/2 < x <= p == 2**n
     70 	return n
     71 }
     72 
     73 func TestSearchEfficiency(t *testing.T) {
     74 	n := 100
     75 	step := 1
     76 	for exp := 2; exp < 10; exp++ {
     77 		// n == 10**exp
     78 		// step == 10**(exp-2)
     79 		max := log2(n)
     80 		for x := 0; x < n; x += step {
     81 			count := 0
     82 			i := Search(n, func(i int) bool { count++; return i >= x })
     83 			if i != x {
     84 				t.Errorf("n = %d: expected index %d; got %d", n, x, i)
     85 			}
     86 			if count > max {
     87 				t.Errorf("n = %d, x = %d: expected <= %d calls; got %d", n, x, max, count)
     88 			}
     89 		}
     90 		n *= 10
     91 		step *= 10
     92 	}
     93 }
     94 
     95 // Smoke tests for convenience wrappers - not comprehensive.
     96 
     97 var fdata = []float64{0: -3.14, 1: 0, 2: 1, 3: 2, 4: 1000.7}
     98 var sdata = []string{0: "f", 1: "foo", 2: "foobar", 3: "x"}
     99 
    100 var wrappertests = []struct {
    101 	name   string
    102 	result int
    103 	i      int
    104 }{
    105 	{"SearchInts", SearchInts(data, 11), 8},
    106 	{"SearchFloat64s", SearchFloat64s(fdata, 2.1), 4},
    107 	{"SearchStrings", SearchStrings(sdata, ""), 0},
    108 	{"IntSlice.Search", IntSlice(data).Search(0), 2},
    109 	{"Float64Slice.Search", Float64Slice(fdata).Search(2.0), 3},
    110 	{"StringSlice.Search", StringSlice(sdata).Search("x"), 3},
    111 }
    112 
    113 func TestSearchWrappers(t *testing.T) {
    114 	for _, e := range wrappertests {
    115 		if e.result != e.i {
    116 			t.Errorf("%s: expected index %d; got %d", e.name, e.i, e.result)
    117 		}
    118 	}
    119 }
    120 
    121 func runSearchWrappers() {
    122 	SearchInts(data, 11)
    123 	SearchFloat64s(fdata, 2.1)
    124 	SearchStrings(sdata, "")
    125 	IntSlice(data).Search(0)
    126 	Float64Slice(fdata).Search(2.0)
    127 	StringSlice(sdata).Search("x")
    128 }
    129 
    130 func TestSearchWrappersDontAlloc(t *testing.T) {
    131 	if testing.Short() {
    132 		t.Skip("skipping malloc count in short mode")
    133 	}
    134 	if runtime.GOMAXPROCS(0) > 1 {
    135 		t.Skip("skipping; GOMAXPROCS>1")
    136 	}
    137 	allocs := testing.AllocsPerRun(100, runSearchWrappers)
    138 	if allocs != 0 {
    139 		t.Errorf("expected no allocs for runSearchWrappers, got %v", allocs)
    140 	}
    141 }
    142 
    143 func BenchmarkSearchWrappers(b *testing.B) {
    144 	for i := 0; i < b.N; i++ {
    145 		runSearchWrappers()
    146 	}
    147 }
    148 
    149 // Abstract exhaustive test: all sizes up to 100,
    150 // all possible return values.  If there are any small
    151 // corner cases, this test exercises them.
    152 func TestSearchExhaustive(t *testing.T) {
    153 	for size := 0; size <= 100; size++ {
    154 		for targ := 0; targ <= size; targ++ {
    155 			i := Search(size, func(i int) bool { return i >= targ })
    156 			if i != targ {
    157 				t.Errorf("Search(%d, %d) = %d", size, targ, i)
    158 			}
    159 		}
    160 	}
    161 }
    162