// Copyright 2009 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 (
"fmt"
"internal/testenv"
"math"
"math/rand"
. "sort"
"strconv"
stringspkg "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.NaN(), math.NaN(), math.Inf(-1), 9845.768, -959.7485, 905, 7.8, 7.8}
var strings = [...]string{"", "Hello", "foo", "bar", "foo", "f00", "%*&^*&^&", "***"}
func TestSortIntSlice(t *testing.T) {
data := ints
a := IntSlice(data[0:])
Sort(a)
if !IsSorted(a) {
t.Errorf("sorted %v", ints)
t.Errorf(" got %v", data)
}
}
func TestSortFloat64Slice(t *testing.T) {
data := float64s
a := Float64Slice(data[0:])
Sort(a)
if !IsSorted(a) {
t.Errorf("sorted %v", float64s)
t.Errorf(" got %v", data)
}
}
func TestSortStringSlice(t *testing.T) {
data := strings
a := StringSlice(data[0:])
Sort(a)
if !IsSorted(a) {
t.Errorf("sorted %v", strings)
t.Errorf(" got %v", data)
}
}
func TestInts(t *testing.T) {
data := ints
Ints(data[0:])
if !IntsAreSorted(data[0:]) {
t.Errorf("sorted %v", ints)
t.Errorf(" got %v", data)
}
}
func TestFloat64s(t *testing.T) {
data := float64s
Float64s(data[0:])
if !Float64sAreSorted(data[0:]) {
t.Errorf("sorted %v", float64s)
t.Errorf(" got %v", data)
}
}
func TestStrings(t *testing.T) {
data := strings
Strings(data[0:])
if !StringsAreSorted(data[0:]) {
t.Errorf("sorted %v", strings)
t.Errorf(" got %v", data)
}
}
func TestSlice(t *testing.T) {
data := strings
Slice(data[:], func(i, j int) bool {
return data[i] < data[j]
})
if !SliceIsSorted(data[:], func(i, j int) bool { return data[i] < data[j] }) {
t.Errorf("sorted %v", strings)
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 IntsAreSorted(data) {
t.Fatalf("terrible rand.rand")
}
Ints(data)
if !IntsAreSorted(data) {
t.Errorf("sort didn't sort - 1M ints")
}
}
func TestReverseSortIntSlice(t *testing.T) {
data := ints
data1 := ints
a := IntSlice(data[0:])
Sort(a)
r := IntSlice(data1[0:])
Sort(Reverse(r))
for i := 0; i < len(data); i++ {
if a[i] != r[len(data)-1-i] {
t.Errorf("reverse sort didn't sort")
}
if i > len(data)/2 {
break
}
}
}
type nonDeterministicTestingData struct {
r *rand.Rand
}
func (t *nonDeterministicTestingData) Len() int {
return 500
}
func (t *nonDeterministicTestingData) Less(i, j int) bool {
if i < 0 || j < 0 || i >= t.Len() || j >= t.Len() {
panic("nondeterministic comparison out of bounds")
}
return t.r.Float32() < 0.5
}
func (t *nonDeterministicTestingData) Swap(i, j int) {
if i < 0 || j < 0 || i >= t.Len() || j >= t.Len() {
panic("nondeterministic comparison out of bounds")
}
}
func TestNonDeterministicComparison(t *testing.T) {
// Ensure that sort.Sort does not panic when Less returns inconsistent results.
// See https://golang.org/issue/14377.
defer func() {
if r := recover(); r != nil {
t.Error(r)
}
}()
td := &nonDeterministicTestingData{
r: rand.New(rand.NewSource(0)),
}
for i := 0; i < 10; i++ {
Sort(td)
}
}
func BenchmarkSortString1K(b *testing.B) {
b.StopTimer()
unsorted := make([]string, 1<<10)
for i := range unsorted {
unsorted[i] = strconv.Itoa(i ^ 0x2cc)
}
data := make([]string, len(unsorted))
for i := 0; i < b.N; i++ {
copy(data, unsorted)
b.StartTimer()
Strings(data)
b.StopTimer()
}
}
func BenchmarkSortString1K_Slice(b *testing.B) {
b.StopTimer()
unsorted := make([]string, 1<<10)
for i := range unsorted {
unsorted[i] = strconv.Itoa(i ^ 0x2cc)
}
data := make([]string, len(unsorted))
for i := 0; i < b.N; i++ {
copy(data, unsorted)
b.StartTimer()
Slice(data, func(i, j int) bool { return data[i] < data[j] })
b.StopTimer()
}
}
func BenchmarkStableString1K(b *testing.B) {
b.StopTimer()
unsorted := make([]string, 1<<10)
for i := 0; i < len(data); i++ {
unsorted[i] = strconv.Itoa(i ^ 0x2cc)
}
data := make([]string, len(unsorted))
for i := 0; i < b.N; i++ {
copy(data, unsorted)
b.StartTimer()
Stable(StringSlice(data))
b.StopTimer()
}
}
func BenchmarkSortInt1K(b *testing.B) {
b.StopTimer()
for i := 0; i < b.N; i++ {
data := make([]int, 1<<10)
for i := 0; i < len(data); i++ {
data[i] = i ^ 0x2cc
}
b.StartTimer()
Ints(data)
b.StopTimer()
}
}
func BenchmarkStableInt1K(b *testing.B) {
b.StopTimer()
unsorted := make([]int, 1<<10)
for i := range unsorted {
unsorted[i] = i ^ 0x2cc
}
data := make([]int, len(unsorted))
for i := 0; i < b.N; i++ {
copy(data, unsorted)
b.StartTimer()
Stable(IntSlice(data))
b.StopTimer()
}
}
func BenchmarkStableInt1K_Slice(b *testing.B) {
b.StopTimer()
unsorted := make([]int, 1<<10)
for i := range unsorted {
unsorted[i] = i ^ 0x2cc
}
data := make([]int, len(unsorted))
for i := 0; i < b.N; i++ {
copy(data, unsorted)
b.StartTimer()
SliceStable(data, func(i, j int) bool { return data[i] < data[j] })
b.StopTimer()
}
}
func BenchmarkSortInt64K(b *testing.B) {
b.StopTimer()
for i := 0; i < b.N; i++ {
data := make([]int, 1<<16)
for i := 0; i < len(data); i++ {
data[i] = i ^ 0xcccc
}
b.StartTimer()
Ints(data)
b.StopTimer()
}
}
func BenchmarkSortInt64K_Slice(b *testing.B) {
b.StopTimer()
for i := 0; i < b.N; i++ {
data := make([]int, 1<<16)
for i := 0; i < len(data); i++ {
data[i] = i ^ 0xcccc
}
b.StartTimer()
Slice(data, func(i, j int) bool { return data[i] < data[j] })
b.StopTimer()
}
}
func BenchmarkStableInt64K(b *testing.B) {
b.StopTimer()
for i := 0; i < b.N; i++ {
data := make([]int, 1<<16)
for i := 0; i < len(data); i++ {
data[i] = i ^ 0xcccc
}
b.StartTimer()
Stable(IntSlice(data))
b.StopTimer()
}
}
const (
_Sawtooth = iota
_Rand
_Stagger
_Plateau
_Shuffle
_NDist
)
const (
_Copy = iota
_Reverse
_ReverseFirstHalf
_ReverseSecondHalf
_Sorted
_Dither
_NMode
)
type testingData struct {
desc string
t *testing.T
data []int
maxswap int // number of swaps allowed
ncmp, nswap int
}
func (d *testingData) Len() int { return len(d.data) }
func (d *testingData) Less(i, j int) bool {
d.ncmp++
return d.data[i] < d.data[j]
}
func (d *testingData) Swap(i, j int) {
if d.nswap >= d.maxswap {
d.t.Errorf("%s: used %d swaps sorting slice of %d", d.desc, d.nswap, len(d.data))
d.t.FailNow()
}
d.nswap++
d.data[i], d.data[j] = d.data[j], d.data[i]
}
func min(a, b int) int {
if a < b {
return a
}
return b
}
func lg(n int) int {
i := 0
for 1<