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 5/* 6Package sortp is a plus to the standard "sort" package. 7*/ 8package sortp 9 10import ( 11 "sort" 12) 13 14// InterfaceStruct is a struct implementing sort.Interface given closures 15type InterfaceStruct struct { 16 // Len is the number of elements in the collection. 17 LenF func() int 18 // Less reports whether the element with 19 // index i should sort before the element with index j. 20 LessF func(i, j int) bool 21 // Swap swaps the elements with indexes i and j. 22 SwapF func(i, j int) 23} 24 25// sort.Interface.Len 26func (is InterfaceStruct) Len() int { 27 return is.LenF() 28} 29 30// sort.Interface.Less 31func (is InterfaceStruct) Less(i, j int) bool { 32 return is.LessF(i, j) 33} 34 35// sort.Interface.Swap 36func (is InterfaceStruct) Swap(i, j int) { 37 is.SwapF(i, j) 38} 39 40// SortF calls sort.Sort by closures. Since Interface.Len always returns a constant, 41// it is an int parameter rather than a closure here. 42func SortF(Len int, Less func(i, j int) bool, Swap func(i, j int)) { 43 sort.Sort(InterfaceStruct{ 44 LenF: func() int { 45 return Len 46 }, 47 LessF: Less, 48 SwapF: Swap, 49 }) 50} 51 52// IndexSort returns a slice of indexes l, so that data[l[i]], i = 0...N-1, are sorted. 53func IndexSort(data sort.Interface) []int { 54 indexes := make([]int, data.Len()) 55 for i := range indexes { 56 indexes[i] = i 57 } 58 sort.Sort(InterfaceStruct{ 59 LenF: data.Len, 60 LessF: func(i, j int) bool { 61 return data.Less(indexes[i], indexes[j]) 62 }, 63 SwapF: func(i, j int) { 64 indexes[i], indexes[j] = indexes[j], indexes[i] 65 }, 66 }) 67 return indexes 68} 69 70// IndexSortF is similar to IndexSort but with funcs as the input. 71func IndexSortF(Len int, Less func(i, j int) bool) []int { 72 indexes := make([]int, Len) 73 for i := range indexes { 74 indexes[i] = i 75 } 76 sort.Sort(InterfaceStruct{ 77 LenF: func() int { 78 return Len 79 }, 80 LessF: func(i, j int) bool { 81 return Less(indexes[i], indexes[j]) 82 }, 83 SwapF: func(i, j int) { 84 indexes[i], indexes[j] = indexes[j], indexes[i] 85 }, 86 }) 87 return indexes 88} 89 90// StableF calls sort.Stable by closures. Since Interface.Len always returns a constant, 91// it is an int parameter rather than a closure here. 92func StableF(Len int, Less func(i, j int) bool, Swap func(i, j int)) { 93 sort.Stable(InterfaceStruct{ 94 LenF: func() int { 95 return Len 96 }, 97 LessF: Less, 98 SwapF: Swap, 99 }) 100} 101 102// IndexSort returns a slice of indexes l, so that data[l[i]], i = 0...N-1, are sorted. 103func IndexStable(data sort.Interface) []int { 104 indexes := make([]int, data.Len()) 105 for i := range indexes { 106 indexes[i] = i 107 } 108 sort.Stable(InterfaceStruct{ 109 LenF: data.Len, 110 LessF: func(i, j int) bool { 111 return data.Less(indexes[i], indexes[j]) 112 }, 113 SwapF: func(i, j int) { 114 indexes[i], indexes[j] = indexes[j], indexes[i] 115 }, 116 }) 117 return indexes 118} 119 120// IndexStableF is similar to IndexStable but with funcs as the input. 121func IndexStableF(Len int, Less func(i, j int) bool) []int { 122 indexes := make([]int, Len) 123 for i := range indexes { 124 indexes[i] = i 125 } 126 sort.Stable(InterfaceStruct{ 127 LenF: func() int { 128 return Len 129 }, 130 LessF: func(i, j int) bool { 131 return Less(indexes[i], indexes[j]) 132 }, 133 SwapF: func(i, j int) { 134 indexes[i], indexes[j] = indexes[j], indexes[i] 135 }, 136 }) 137 return indexes 138} 139 140// IsSortedF is similar to sort.IsSorted but with closure as arguments. 141func IsSortedF(Len int, Less func(i, j int) bool) bool { 142 for i := 1; i < Len; i++ { 143 if Less(i, i-1) { 144 return false 145 } 146 } 147 return true 148} 149 150// ReverseLess returns a func which can be used to sort data in a reverse order. 151func ReverseLess(Less func(i, j int) bool) func(i, j int) bool { 152 return func(i, j int) bool { 153 return Less(j, i) 154 } 155} 156 157// Merge merges two sorted list. 158// 159// @param LeftLen is the length of the left list. 160// @param RightLen is the length of the right list. 161// @param Less compares the l-th element of left list and the r-th element of the right list. 162// @param AppendLeft appends the l-th element of the left list to the result list. 163// @param AppendRight appends the r-th element of the right list to the result list. 164func Merge(LeftLen, RightLen int, Less func(l, r int) bool, AppendLeft func(l int), AppendRight func(r int)) { 165 l, r := 0, 0 166 if l < LeftLen && r < RightLen { 167 for { 168 if Less(l, r) { 169 AppendLeft(l) 170 l++ 171 if l == LeftLen { 172 break 173 } 174 } else { 175 AppendRight(r) 176 r++ 177 if r == RightLen { 178 break 179 } 180 } 181 } 182 } 183 // Append rest elements 184 for ; l < LeftLen; l++ { 185 AppendLeft(l) 186 } 187 for ; r < RightLen; r++ { 188 AppendRight(r) 189 } 190} 191 192// DiffSortedList compares the difference of two sorted list. 193// LeftLen and RightLen are lengths of the left/right lists, respectively. 194// Compare returns -1/1/0 if l-th element of left list is less/greater/equal to the 195// r-th element of the right list, both are zero-based. 196// OutputLeft is called with the index of the element existing in the left list but not in the right list. 197// OutputLeft will be called with ascending indexes. 198// OutputRight is similar. 199// Please make no assumption of the calling order of OutputLeft/OutputRight. 200func DiffSortedList(LeftLen, RightLen int, Compare func(l, r int) int, OutputLeft, OutputRight func(index int)) { 201 l, r := 0, 0 202 if LeftLen > 0 && RightLen > 0 { 203 forloop: 204 for { 205 switch Compare(l, r) { 206 case -1: 207 OutputLeft(l) 208 l++ 209 if l == LeftLen { 210 break forloop 211 } 212 case 1: 213 OutputRight(r) 214 r++ 215 if r == RightLen { 216 break forloop 217 } 218 default: 219 l++ 220 r++ 221 if l == LeftLen || r == RightLen { 222 break forloop 223 } 224 } 225 } 226 } 227 for l < LeftLen { 228 OutputLeft(l) 229 l++ 230 } 231 for r < RightLen { 232 OutputRight(r) 233 r++ 234 } 235} 236