// Copyright 2023 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 -generic

package slices

import (
	
	
)

// Sort sorts a slice of any ordered type in ascending order.
// When sorting floating-point numbers, NaNs are ordered before other values.
func [ ~[],  cmp.Ordered]( ) {
	 := len()
	pdqsortOrdered(, 0, , bits.Len(uint()))
}

// 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 a and b are incomparable in the sense of
// a strict weak ordering.
//
// SortFunc requires that cmp is a strict weak ordering.
// See https://en.wikipedia.org/wiki/Weak_ordering#Strict_weak_orderings.
// The function should return 0 for incomparable items.
func [ ~[],  any]( ,  func(,  ) int) {
	 := len()
	pdqsortCmpFunc(, 0, , bits.Len(uint()), )
}

// 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 [ ~[],  any]( ,  func(,  ) int) {
	stableCmpFunc(, len(), )
}

// IsSorted reports whether x is sorted in ascending order.
func [ ~[],  cmp.Ordered]( ) bool {
	for  := len() - 1;  > 0; -- {
		if cmp.Less([], [-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 [ ~[],  any]( ,  func(,  ) int) bool {
	for  := len() - 1;  > 0; -- {
		if ([], [-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 [ ~[],  cmp.Ordered]( )  {
	if len() < 1 {
		panic("slices.Min: empty list")
	}
	 := [0]
	for  := 1;  < len(); ++ {
		 = min(, [])
	}
	return 
}

// 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 [ ~[],  any]( ,  func(,  ) int)  {
	if len() < 1 {
		panic("slices.MinFunc: empty list")
	}
	 := [0]
	for  := 1;  < len(); ++ {
		if ([], ) < 0 {
			 = []
		}
	}
	return 
}

// 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 [ ~[],  cmp.Ordered]( )  {
	if len() < 1 {
		panic("slices.Max: empty list")
	}
	 := [0]
	for  := 1;  < len(); ++ {
		 = max(, [])
	}
	return 
}

// 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 [ ~[],  any]( ,  func(,  ) int)  {
	if len() < 1 {
		panic("slices.MaxFunc: empty list")
	}
	 := [0]
	for  := 1;  < len(); ++ {
		if ([], ) > 0 {
			 = []
		}
	}
	return 
}

// BinarySearch searches for target in a sorted slice and returns the earliest
// 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 [ ~[],  cmp.Ordered]( ,  ) (int, bool) {
	// Inlining is faster than calling BinarySearchFunc with a lambda.
	 := len()
	// Define x[-1] < target and x[n] >= target.
	// Invariant: x[i-1] < target, x[j] >= target.
	,  := 0, 
	for  <  {
		 := int(uint(+) >> 1) // avoid overflow when computing h
		// i ≤ h < j
		if cmp.Less([], ) {
			 =  + 1 // preserves x[i-1] < target
		} else {
			 =  // preserves x[j] >= target
		}
	}
	// i == j, x[i-1] < target, and x[j] (= x[i]) >= target  =>  answer is i.
	return ,  <  && ([] ==  || (isNaN([]) && isNaN()))
}

// 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 [ ~[], ,  any]( ,  ,  func(, ) int) (int, bool) {
	 := len()
	// Define cmp(x[-1], target) < 0 and cmp(x[n], target) >= 0 .
	// Invariant: cmp(x[i - 1], target) < 0, cmp(x[j], target) >= 0.
	,  := 0, 
	for  <  {
		 := int(uint(+) >> 1) // avoid overflow when computing h
		// i ≤ h < j
		if ([], ) < 0 {
			 =  + 1 // preserves cmp(x[i - 1], target) < 0
		} else {
			 =  // 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 ,  <  && ([], ) == 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 ( *xorshift) () uint64 {
	* ^= * << 13
	* ^= * >> 7
	* ^= * << 17
	return uint64(*)
}

func nextPowerOfTwo( int) uint {
	return 1 << bits.Len(uint())
}

// 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[ cmp.Ordered]( ) bool {
	return  != 
}