1// Copyright 2015 The Golang Plus 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
5package sortp
6
7import (
8	"fmt"
9	"math/rand"
10	"sort"
11	"testing"
12
13	"github.com/golangplus/testing/assert"
14)
15
16// Make sure InterfaceStruct implements sort.Interface
17var _ sort.Interface = InterfaceStruct{}
18
19func TestSortF(t *testing.T) {
20	data := []int{5, 3, 1, 8, 0}
21
22	less := func(i, j int) bool {
23		return data[i] < data[j]
24	}
25	swap := func(i, j int) {
26		data[i], data[j] = data[j], data[i]
27	}
28	SortF(len(data), less, swap)
29
30	assert.True(t, "IsSortedF", IsSortedF(len(data), less))
31	assert.Equal(t, "data", data, []int{0, 1, 3, 5, 8})
32}
33
34func TestIndexSort(t *testing.T) {
35	data := []int{5, 3, 1, 8, 0}
36	indexes := IndexSort(sort.IntSlice(data))
37	assert.Equal(t, "indexes", indexes, []int{4, 2, 1, 0, 3})
38}
39
40func TestIndexSortF(t *testing.T) {
41	data := []int{5, 3, 1, 8, 0}
42	indexes := IndexSortF(len(data), func(i, j int) bool {
43		return data[i] < data[j]
44	})
45	assert.Equal(t, "indexes", indexes, []int{4, 2, 1, 0, 3})
46}
47
48func TestStableF(t *testing.T) {
49	data := []int{5, 1, 1, 8, 1}
50	sub := []int{1, 2, 3, 4, 5}
51	less := func(i, j int) bool {
52		return data[i] < data[j]
53	}
54	swap := func(i, j int) {
55		data[i], data[j] = data[j], data[i]
56		sub[i], sub[j] = sub[j], sub[i]
57	}
58	StableF(len(data), less, swap)
59	assert.True(t, "IsSortedF", IsSortedF(len(data), less))
60	assert.Equal(t, "data", data, []int{1, 1, 1, 5, 8})
61	assert.Equal(t, "sub", sub, []int{2, 3, 5, 1, 4})
62}
63
64func TestIndexStable(t *testing.T) {
65	data := []int{5, 1, 1, 8, 1}
66	indexes := IndexStable(sort.IntSlice(data))
67	assert.Equal(t, "indexes", indexes, []int{1, 2, 4, 0, 3})
68}
69
70func TestIndexStableF(t *testing.T) {
71	data := []int{5, 1, 1, 8, 1}
72	indexes := IndexStableF(len(data), func(i, j int) bool {
73		return data[i] < data[j]
74	})
75	assert.Equal(t, "indexes", indexes, []int{1, 2, 4, 0, 3})
76}
77
78func ExampleInterfaceStruct() {
79	data := []int{5, 3, 1, 8, 0}
80
81	sort.Sort(InterfaceStruct{
82		LenF: func() int {
83			return len(data)
84		}, LessF: func(i, j int) bool {
85			return data[i] < data[j]
86		}, SwapF: func(i, j int) {
87			data[i], data[j] = data[j], data[i]
88		},
89	})
90
91	fmt.Println(data)
92	// OUTPUT:
93	// [0 1 3 5 8]
94}
95
96func TestIsSortedF(t *testing.T) {
97	list := []int{1, 2, 3}
98	assert.True(t, "IsSortedF", IsSortedF(len(list), func(i, j int) bool {
99		return list[i] < list[j]
100	}))
101	list = []int{2, 1, 3}
102	assert.False(t, "IsSortedF", IsSortedF(len(list), func(i, j int) bool {
103		return list[i] < list[j]
104	}))
105}
106
107func TestReverseLess(t *testing.T) {
108	arr := []int{1, 1, 2}
109	less := func(i, j int) bool {
110		return arr[i] < arr[j]
111	}
112	assert.False(t, "less", less(0, 0))
113	assert.False(t, "less", less(0, 1))
114	assert.True(t, "less", less(0, 2))
115	assert.False(t, "less", less(1, 0))
116	assert.False(t, "less", less(1, 1))
117	assert.True(t, "less", less(1, 2))
118	assert.False(t, "less", less(2, 0))
119	assert.False(t, "less", less(2, 1))
120	assert.False(t, "less", less(2, 2))
121
122	less = ReverseLess(less)
123	assert.False(t, "less", less(0, 0))
124	assert.False(t, "less", less(0, 1))
125	assert.False(t, "less", less(0, 2))
126	assert.False(t, "less", less(1, 0))
127	assert.False(t, "less", less(1, 1))
128	assert.False(t, "less", less(1, 2))
129	assert.True(t, "less", less(2, 0))
130	assert.True(t, "less", less(2, 1))
131	assert.False(t, "less", less(2, 2))
132}
133
134func TestMerge(t *testing.T) {
135	left, right := make([]int, 100), make([]int, 200)
136	for i := range left {
137		left[i] = rand.Int()
138	}
139	for i := range right {
140		right[i] = rand.Int()
141	}
142
143	// Expected results can be obtained by sorting.
144	expMerged := append(append([]int{}, left...), right...)
145	sort.Ints(expMerged)
146
147	// Sort left and right
148	sort.Ints(left)
149	sort.Ints(right)
150
151	// Do merge
152	merged := make([]int, 0, len(left)+len(right))
153	Merge(len(left), len(right), func(l, r int) bool {
154		return left[l] < right[r]
155	}, func(l int) {
156		merged = append(merged, left[l])
157	}, func(r int) {
158		merged = append(merged, right[r])
159	})
160
161	assert.StringEqual(t, "merged", merged, expMerged)
162}
163
164func ExampleMerge() {
165	left := []int{1, 3, 5, 7}
166	right := []int{4, 6, 8, 10, 11}
167
168	var merged []int
169	Merge(len(left), len(right), func(l, r int) bool {
170		return left[l] < right[r]
171	}, func(l int) {
172		merged = append(merged, left[l])
173	}, func(r int) {
174		merged = append(merged, right[r])
175	})
176	fmt.Println(merged)
177
178	left, right = right, left
179	merged = nil
180	Merge(len(left), len(right), func(l, r int) bool {
181		return left[l] < right[r]
182	}, func(l int) {
183		merged = append(merged, left[l])
184	}, func(r int) {
185		merged = append(merged, right[r])
186	})
187	fmt.Println(merged)
188
189	// Output:
190	// [1 3 4 5 6 7 8 10 11]
191	// [1 3 4 5 6 7 8 10 11]
192}
193
194func ExampleDiffSortedList() {
195	from := []string{"a", "b", "d", "f"}
196	to := []string{"b", "c", "d", "g", "h"}
197
198	var extra, missing []string
199	DiffSortedList(len(from), len(to), func(f, t int) int {
200		if from[f] < to[t] {
201			return -1
202		}
203		if from[f] > to[t] {
204			return 1
205		}
206		return 0
207	}, func(f int) {
208		extra = append(extra, from[f])
209	}, func(t int) {
210		missing = append(missing, to[t])
211	})
212	fmt.Println("extra:", extra)
213	fmt.Println("missing:", missing)
214
215	from, to = to, from
216	extra, missing = nil, nil
217	DiffSortedList(len(from), len(to), func(f, t int) int {
218		if from[f] < to[t] {
219			return -1
220		}
221		if from[f] > to[t] {
222			return 1
223		}
224		return 0
225	}, func(f int) {
226		extra = append(extra, from[f])
227	}, func(t int) {
228		missing = append(missing, to[t])
229	})
230	fmt.Println("extra:", extra)
231	fmt.Println("missing:", missing)
232
233	to = from
234	extra, missing = nil, nil
235	DiffSortedList(len(from), len(to), func(f, t int) int {
236		if from[f] < to[t] {
237			return -1
238		}
239		if from[f] > to[t] {
240			return 1
241		}
242		return 0
243	}, func(f int) {
244		extra = append(extra, from[f])
245	}, func(t int) {
246		missing = append(missing, to[t])
247	})
248	fmt.Println("extra:", extra)
249	fmt.Println("missing:", missing)
250
251	// Output:
252	// extra: [a f]
253	// missing: [c g h]
254	// extra: [c g h]
255	// missing: [a f]
256	// extra: []
257	// missing: []
258}
259