1 // Copyright 2023 The Go 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 //go:generate go run $GOROOT/src/sort/gen_sort_variants.go -generic 6 7 package slices 8 9 import ( 10 "cmp" 11 "math/bits" 12 ) 13 14 // Sort sorts a slice of any ordered type in ascending order. 15 // When sorting floating-point numbers, NaNs are ordered before other values. 16 func Sort[S ~[]E, E cmp.Ordered](x S) { 17 n := len(x) 18 pdqsortOrdered(x, 0, n, bits.Len(uint(n))) 19 } 20 21 // SortFunc sorts the slice x in ascending order as determined by the cmp 22 // function. This sort is not guaranteed to be stable. 23 // cmp(a, b) should return a negative number when a < b, a positive number when 24 // a > b and zero when a == b or a and b are incomparable in the sense of 25 // a strict weak ordering. 26 // 27 // SortFunc requires that cmp is a strict weak ordering. 28 // See https://en.wikipedia.org/wiki/Weak_ordering#Strict_weak_orderings. 29 // The function should return 0 for incomparable items. 30 func SortFunc[S ~[]E, E any](x S, cmp func(a, b E) int) { 31 n := len(x) 32 pdqsortCmpFunc(x, 0, n, bits.Len(uint(n)), cmp) 33 } 34 35 // SortStableFunc sorts the slice x while keeping the original order of equal 36 // elements, using cmp to compare elements in the same way as [SortFunc]. 37 func SortStableFunc[S ~[]E, E any](x S, cmp func(a, b E) int) { 38 stableCmpFunc(x, len(x), cmp) 39 } 40 41 // IsSorted reports whether x is sorted in ascending order. 42 func IsSorted[S ~[]E, E cmp.Ordered](x S) bool { 43 for i := len(x) - 1; i > 0; i-- { 44 if cmp.Less(x[i], x[i-1]) { 45 return false 46 } 47 } 48 return true 49 } 50 51 // IsSortedFunc reports whether x is sorted in ascending order, with cmp as the 52 // comparison function as defined by [SortFunc]. 53 func IsSortedFunc[S ~[]E, E any](x S, cmp func(a, b E) int) bool { 54 for i := len(x) - 1; i > 0; i-- { 55 if cmp(x[i], x[i-1]) < 0 { 56 return false 57 } 58 } 59 return true 60 } 61 62 // Min returns the minimal value in x. It panics if x is empty. 63 // For floating-point numbers, Min propagates NaNs (any NaN value in x 64 // forces the output to be NaN). 65 func Min[S ~[]E, E cmp.Ordered](x S) E { 66 if len(x) < 1 { 67 panic("slices.Min: empty list") 68 } 69 m := x[0] 70 for i := 1; i < len(x); i++ { 71 m = min(m, x[i]) 72 } 73 return m 74 } 75 76 // MinFunc returns the minimal value in x, using cmp to compare elements. 77 // It panics if x is empty. If there is more than one minimal element 78 // according to the cmp function, MinFunc returns the first one. 79 func MinFunc[S ~[]E, E any](x S, cmp func(a, b E) int) E { 80 if len(x) < 1 { 81 panic("slices.MinFunc: empty list") 82 } 83 m := x[0] 84 for i := 1; i < len(x); i++ { 85 if cmp(x[i], m) < 0 { 86 m = x[i] 87 } 88 } 89 return m 90 } 91 92 // Max returns the maximal value in x. It panics if x is empty. 93 // For floating-point E, Max propagates NaNs (any NaN value in x 94 // forces the output to be NaN). 95 func Max[S ~[]E, E cmp.Ordered](x S) E { 96 if len(x) < 1 { 97 panic("slices.Max: empty list") 98 } 99 m := x[0] 100 for i := 1; i < len(x); i++ { 101 m = max(m, x[i]) 102 } 103 return m 104 } 105 106 // MaxFunc returns the maximal value in x, using cmp to compare elements. 107 // It panics if x is empty. If there is more than one maximal element 108 // according to the cmp function, MaxFunc returns the first one. 109 func MaxFunc[S ~[]E, E any](x S, cmp func(a, b E) int) E { 110 if len(x) < 1 { 111 panic("slices.MaxFunc: empty list") 112 } 113 m := x[0] 114 for i := 1; i < len(x); i++ { 115 if cmp(x[i], m) > 0 { 116 m = x[i] 117 } 118 } 119 return m 120 } 121 122 // BinarySearch searches for target in a sorted slice and returns the earliest 123 // position where target is found, or the position where target would appear 124 // in the sort order; it also returns a bool saying whether the target is 125 // really found in the slice. The slice must be sorted in increasing order. 126 func BinarySearch[S ~[]E, E cmp.Ordered](x S, target E) (int, bool) { 127 // Inlining is faster than calling BinarySearchFunc with a lambda. 128 n := len(x) 129 // Define x[-1] < target and x[n] >= target. 130 // Invariant: x[i-1] < target, x[j] >= target. 131 i, j := 0, n 132 for i < j { 133 h := int(uint(i+j) >> 1) // avoid overflow when computing h 134 // i ≤ h < j 135 if cmp.Less(x[h], target) { 136 i = h + 1 // preserves x[i-1] < target 137 } else { 138 j = h // preserves x[j] >= target 139 } 140 } 141 // i == j, x[i-1] < target, and x[j] (= x[i]) >= target => answer is i. 142 return i, i < n && (x[i] == target || (isNaN(x[i]) && isNaN(target))) 143 } 144 145 // BinarySearchFunc works like [BinarySearch], but uses a custom comparison 146 // function. The slice must be sorted in increasing order, where "increasing" 147 // is defined by cmp. cmp should return 0 if the slice element matches 148 // the target, a negative number if the slice element precedes the target, 149 // or a positive number if the slice element follows the target. 150 // cmp must implement the same ordering as the slice, such that if 151 // cmp(a, t) < 0 and cmp(b, t) >= 0, then a must precede b in the slice. 152 func BinarySearchFunc[S ~[]E, E, T any](x S, target T, cmp func(E, T) int) (int, bool) { 153 n := len(x) 154 // Define cmp(x[-1], target) < 0 and cmp(x[n], target) >= 0 . 155 // Invariant: cmp(x[i - 1], target) < 0, cmp(x[j], target) >= 0. 156 i, j := 0, n 157 for i < j { 158 h := int(uint(i+j) >> 1) // avoid overflow when computing h 159 // i ≤ h < j 160 if cmp(x[h], target) < 0 { 161 i = h + 1 // preserves cmp(x[i - 1], target) < 0 162 } else { 163 j = h // preserves cmp(x[j], target) >= 0 164 } 165 } 166 // i == j, cmp(x[i-1], target) < 0, and cmp(x[j], target) (= cmp(x[i], target)) >= 0 => answer is i. 167 return i, i < n && cmp(x[i], target) == 0 168 } 169 170 type sortedHint int // hint for pdqsort when choosing the pivot 171 172 const ( 173 unknownHint sortedHint = iota 174 increasingHint 175 decreasingHint 176 ) 177 178 // xorshift paper: https://www.jstatsoft.org/article/view/v008i14/xorshift.pdf 179 type xorshift uint64 180 181 func (r *xorshift) Next() uint64 { 182 *r ^= *r << 13 183 *r ^= *r >> 17 184 *r ^= *r << 5 185 return uint64(*r) 186 } 187 188 func nextPowerOfTwo(length int) uint { 189 return 1 << bits.Len(uint(length)) 190 } 191 192 // isNaN reports whether x is a NaN without requiring the math package. 193 // This will always return false if T is not floating-point. 194 func isNaN[T cmp.Ordered](x T) bool { 195 return x != x 196 } 197