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