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