| // Copyright 2022 The Go Authors. All rights reserved. |
| // Use of this source code is governed by a BSD-style |
| // license that can be found in the LICENSE file. |
| |
| //go:generate go run $GOROOT/src/sort/gen_sort_variants.go -exp |
| |
| package slices |
| |
| import ( |
| "math/bits" |
| |
| "golang.org/x/exp/constraints" |
| ) |
| |
| // Sort sorts a slice of any ordered type in ascending order. |
| // When sorting floating-point numbers, NaNs are ordered before other values. |
| func Sort[S ~[]E, E constraints.Ordered](x S) { |
| n := len(x) |
| pdqsortOrdered(x, 0, n, bits.Len(uint(n))) |
| } |
| |
| // SortFunc sorts the slice x in ascending order as determined by the cmp |
| // function. This sort is not guaranteed to be stable. |
| // cmp(a, b) should return a negative number when a < b, a positive number when |
| // a > b and zero when a == b or when a is not comparable to b in the sense |
| // of the formal definition of Strict Weak Ordering. |
| // |
| // SortFunc requires that cmp is a strict weak ordering. |
| // See https://en.wikipedia.org/wiki/Weak_ordering#Strict_weak_orderings. |
| // To indicate 'uncomparable', return 0 from the function. |
| func SortFunc[S ~[]E, E any](x S, cmp func(a, b E) int) { |
| n := len(x) |
| pdqsortCmpFunc(x, 0, n, bits.Len(uint(n)), cmp) |
| } |
| |
| // SortStableFunc sorts the slice x while keeping the original order of equal |
| // elements, using cmp to compare elements in the same way as [SortFunc]. |
| func SortStableFunc[S ~[]E, E any](x S, cmp func(a, b E) int) { |
| stableCmpFunc(x, len(x), cmp) |
| } |
| |
| // IsSorted reports whether x is sorted in ascending order. |
| func IsSorted[S ~[]E, E constraints.Ordered](x S) bool { |
| for i := len(x) - 1; i > 0; i-- { |
| if cmpLess(x[i], x[i-1]) { |
| return false |
| } |
| } |
| return true |
| } |
| |
| // IsSortedFunc reports whether x is sorted in ascending order, with cmp as the |
| // comparison function as defined by [SortFunc]. |
| func IsSortedFunc[S ~[]E, E any](x S, cmp func(a, b E) int) bool { |
| for i := len(x) - 1; i > 0; i-- { |
| if cmp(x[i], x[i-1]) < 0 { |
| return false |
| } |
| } |
| return true |
| } |
| |
| // Min returns the minimal value in x. It panics if x is empty. |
| // For floating-point numbers, Min propagates NaNs (any NaN value in x |
| // forces the output to be NaN). |
| func Min[S ~[]E, E constraints.Ordered](x S) E { |
| if len(x) < 1 { |
| panic("slices.Min: empty list") |
| } |
| m := x[0] |
| for i := 1; i < len(x); i++ { |
| m = min(m, x[i]) |
| } |
| return m |
| } |
| |
| // MinFunc returns the minimal value in x, using cmp to compare elements. |
| // It panics if x is empty. If there is more than one minimal element |
| // according to the cmp function, MinFunc returns the first one. |
| func MinFunc[S ~[]E, E any](x S, cmp func(a, b E) int) E { |
| if len(x) < 1 { |
| panic("slices.MinFunc: empty list") |
| } |
| m := x[0] |
| for i := 1; i < len(x); i++ { |
| if cmp(x[i], m) < 0 { |
| m = x[i] |
| } |
| } |
| return m |
| } |
| |
| // Max returns the maximal value in x. It panics if x is empty. |
| // For floating-point E, Max propagates NaNs (any NaN value in x |
| // forces the output to be NaN). |
| func Max[S ~[]E, E constraints.Ordered](x S) E { |
| if len(x) < 1 { |
| panic("slices.Max: empty list") |
| } |
| m := x[0] |
| for i := 1; i < len(x); i++ { |
| m = max(m, x[i]) |
| } |
| return m |
| } |
| |
| // MaxFunc returns the maximal value in x, using cmp to compare elements. |
| // It panics if x is empty. If there is more than one maximal element |
| // according to the cmp function, MaxFunc returns the first one. |
| func MaxFunc[S ~[]E, E any](x S, cmp func(a, b E) int) E { |
| if len(x) < 1 { |
| panic("slices.MaxFunc: empty list") |
| } |
| m := x[0] |
| for i := 1; i < len(x); i++ { |
| if cmp(x[i], m) > 0 { |
| m = x[i] |
| } |
| } |
| return m |
| } |
| |
| // BinarySearch searches for target in a sorted slice and returns the position |
| // where target is found, or the position where target would appear in the |
| // sort order; it also returns a bool saying whether the target is really found |
| // in the slice. The slice must be sorted in increasing order. |
| func BinarySearch[S ~[]E, E constraints.Ordered](x S, target E) (int, bool) { |
| // Inlining is faster than calling BinarySearchFunc with a lambda. |
| n := len(x) |
| // Define x[-1] < target and x[n] >= target. |
| // Invariant: x[i-1] < target, x[j] >= target. |
| i, j := 0, n |
| for i < j { |
| h := int(uint(i+j) >> 1) // avoid overflow when computing h |
| // i ≤ h < j |
| if cmpLess(x[h], target) { |
| i = h + 1 // preserves x[i-1] < target |
| } else { |
| j = h // preserves x[j] >= target |
| } |
| } |
| // i == j, x[i-1] < target, and x[j] (= x[i]) >= target => answer is i. |
| return i, i < n && (x[i] == target || (isNaN(x[i]) && isNaN(target))) |
| } |
| |
| // BinarySearchFunc works like [BinarySearch], but uses a custom comparison |
| // function. The slice must be sorted in increasing order, where "increasing" |
| // is defined by cmp. cmp should return 0 if the slice element matches |
| // the target, a negative number if the slice element precedes the target, |
| // or a positive number if the slice element follows the target. |
| // cmp must implement the same ordering as the slice, such that if |
| // cmp(a, t) < 0 and cmp(b, t) >= 0, then a must precede b in the slice. |
| func BinarySearchFunc[S ~[]E, E, T any](x S, target T, cmp func(E, T) int) (int, bool) { |
| n := len(x) |
| // Define cmp(x[-1], target) < 0 and cmp(x[n], target) >= 0 . |
| // Invariant: cmp(x[i - 1], target) < 0, cmp(x[j], target) >= 0. |
| i, j := 0, n |
| for i < j { |
| h := int(uint(i+j) >> 1) // avoid overflow when computing h |
| // i ≤ h < j |
| if cmp(x[h], target) < 0 { |
| i = h + 1 // preserves cmp(x[i - 1], target) < 0 |
| } else { |
| j = h // preserves cmp(x[j], target) >= 0 |
| } |
| } |
| // i == j, cmp(x[i-1], target) < 0, and cmp(x[j], target) (= cmp(x[i], target)) >= 0 => answer is i. |
| return i, i < n && cmp(x[i], target) == 0 |
| } |
| |
| type sortedHint int // hint for pdqsort when choosing the pivot |
| |
| const ( |
| unknownHint sortedHint = iota |
| increasingHint |
| decreasingHint |
| ) |
| |
| // xorshift paper: https://www.jstatsoft.org/article/view/v008i14/xorshift.pdf |
| type xorshift uint64 |
| |
| func (r *xorshift) Next() uint64 { |
| *r ^= *r << 13 |
| *r ^= *r >> 17 |
| *r ^= *r << 5 |
| return uint64(*r) |
| } |
| |
| func nextPowerOfTwo(length int) uint { |
| return 1 << bits.Len(uint(length)) |
| } |
| |
| // isNaN reports whether x is a NaN without requiring the math package. |
| // This will always return false if T is not floating-point. |
| func isNaN[T constraints.Ordered](x T) bool { |
| return x != x |
| } |