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 >> 7
184 *r ^= *r << 17
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