sort.go

     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
View as plain text