1package slice
2
3import (
4	"math/rand"
5	"reflect"
6	"sort"
7	"testing"
8	"unsafe"
9)
10
11const nItem = 50000
12
13type S struct {
14	s string
15	i int64
16	p *int
17	b byte
18}
19
20type lessCall struct {
21	i, j int
22	res  bool
23}
24
25type lessLogger struct {
26	sort.Interface
27	dst *[]lessCall
28}
29
30func (l lessLogger) Less(i, j int) bool {
31	got := l.Interface.Less(i, j)
32	*l.dst = append(*l.dst, lessCall{i, j, got})
33	return got
34}
35
36func TestSwapMem(t *testing.T) {
37	buf := []byte{
38		1, 2, 3, 4,
39		5, 6, 7, 8,
40		0, 0, 0, 0,
41	}
42	const size = 4
43	ms := newMemSwap(size, unsafe.Pointer(&buf[0]), unsafe.Pointer(&buf[8]))
44	ms.Swap(0, 1)
45	want := []byte{
46		5, 6, 7, 8,
47		1, 2, 3, 4,
48		1, 2, 3, 4,
49	}
50	if !reflect.DeepEqual(buf, want) {
51		t.Errorf("buf = %v; want %v", buf, want)
52	}
53}
54
55func TestSort3(t *testing.T) {
56	x := []int{3, 2, 1}
57	var sawOutside, sawInside []lessCall
58	si := SortInterface(x, func(i, j int) bool {
59		ret := x[i] < x[j]
60		sawInside = append(sawInside, lessCall{i, j, ret})
61		return ret
62	})
63	sort.Sort(lessLogger{si, &sawOutside})
64	want := []int{1, 2, 3}
65	if !reflect.DeepEqual(x, want) {
66		t.Errorf("bad Sort = %v; want %v", x, want)
67	}
68	if !reflect.DeepEqual(sawOutside, sawInside) {
69		t.Errorf("assembly goo wrong. Inner func & outer interface saw different results:\nInner: %v\nOuter: %v\n", sawInside, sawOutside)
70	}
71}
72
73func TestSort(t *testing.T) {
74	rand.Seed(1)
75	x := make([]int64, nItem)
76	for i := range x {
77		x[i] = int64(rand.Intn(nItem * 10))
78	}
79	x2 := append([]int64(nil), x...)
80
81	Sort(x, func(i, j int) bool {
82		return x[i] < x[j]
83	})
84	sort.Sort(Int64Slice(x2))
85	if !reflect.DeepEqual(x, x2) {
86		t.Errorf("sorting failed")
87	}
88}
89
90func TestSortStruct(t *testing.T) {
91	rand.Seed(1)
92	x := make([]S, nItem)
93	for i := range x {
94		x[i] = S{i: int64(rand.Intn(nItem * 10))}
95	}
96	x2 := append([]S(nil), x...)
97
98	Sort(x, func(i, j int) bool {
99		return x[i].i < x[j].i
100	})
101	sort.Sort(SSlice(x2))
102	if !reflect.DeepEqual(x, x2) {
103		t.Errorf("sorting failed")
104	}
105}
106
107func BenchmarkSortInt64New(b *testing.B) {
108	rand.Seed(1)
109	x := make([]int64, nItem)
110	for i := 0; i < b.N; i++ {
111		for j := range x {
112			x[j] = int64(rand.Intn(nItem * 10))
113		}
114		Sort(x, func(i, j int) bool {
115			return x[i] < x[j]
116		})
117	}
118}
119
120func BenchmarkSortInt64Old(b *testing.B) {
121	rand.Seed(1)
122	x := make([]int64, nItem)
123	for i := 0; i < b.N; i++ {
124		for j := range x {
125			x[j] = int64(rand.Intn(nItem * 10))
126		}
127		sort.Sort(Int64Slice(x))
128	}
129}
130
131func BenchmarkSortInt32New(b *testing.B) {
132	rand.Seed(1)
133	x := make([]int32, nItem)
134	for i := 0; i < b.N; i++ {
135		for j := range x {
136			x[j] = int32(rand.Intn(nItem * 10))
137		}
138		Sort(x, func(i, j int) bool {
139			return x[i] < x[j]
140		})
141	}
142}
143
144func BenchmarkSortInt32Old(b *testing.B) {
145	rand.Seed(1)
146	x := make([]int32, nItem)
147	for i := 0; i < b.N; i++ {
148		for j := range x {
149			x[j] = int32(rand.Intn(nItem * 10))
150		}
151		sort.Sort(Int32Slice(x))
152	}
153}
154
155func BenchmarkSortStructOld(b *testing.B) {
156	rand.Seed(1)
157	x := make([]S, nItem)
158	for i := 0; i < b.N; i++ {
159		for j := range x {
160			x[j] = S{i: int64(rand.Intn(nItem * 10))}
161		}
162		sort.Sort(SSlice(x))
163	}
164}
165
166func BenchmarkSortStructNew(b *testing.B) {
167	rand.Seed(1)
168	x := make([]S, nItem)
169	for i := 0; i < b.N; i++ {
170		for j := range x {
171			x[j] = S{i: int64(rand.Intn(nItem * 10))}
172		}
173		Sort(x, func(i, j int) bool {
174			return x[i].i < x[j].i
175		})
176	}
177}
178
179// Int64Slice attaches the methods of sort.Interface to []int64, sorting in increasing order.
180type Int64Slice []int64
181
182func (s Int64Slice) Len() int           { return len(s) }
183func (s Int64Slice) Less(i, j int) bool { return s[i] < s[j] }
184func (s Int64Slice) Swap(i, j int)      { s[i], s[j] = s[j], s[i] }
185
186// Int32Slice attaches the methods of sort.Interface to []int32, sorting in increasing order.
187type Int32Slice []int32
188
189func (s Int32Slice) Len() int           { return len(s) }
190func (s Int32Slice) Less(i, j int) bool { return s[i] < s[j] }
191func (s Int32Slice) Swap(i, j int)      { s[i], s[j] = s[j], s[i] }
192
193type SSlice []S
194
195func (s SSlice) Len() int           { return len(s) }
196func (s SSlice) Less(i, j int) bool { return s[i].i < s[j].i }
197func (s SSlice) Swap(i, j int)      { s[i], s[j] = s[j], s[i] }
198