array.go

// Package arrayx provides generic algorithms that operate on slices.
//
// All functions are O(n) time unless documented otherwise, and they never
// allocate beyond what is required by the operation.
package arrayx

// Number is a constraint for any built-in numeric type.
type Number interface {
	~int | ~int8 | ~int16 | ~int32 | ~int64 |
		~uint | ~uint8 | ~uint16 | ~uint32 | ~uint64 | ~uintptr |
		~float32 | ~float64
}

// Ordered is a constraint for any built-in ordered (comparable with <) type.
type Ordered interface {
	Number | ~string
}

// Sum returns the arithmetic sum of all values in s. For an empty slice it
// returns the zero value of T.
func Sum[T Number](s []T) T {
	var total T
	for _, v := range s {
		total += v
	}
	return total
}

// Max returns the largest element of s along with true. If s is empty it
// returns the zero value of T and false.
func Max[T Ordered](s []T) (T, bool) {
	var zero T
	if len(s) == 0 {
		return zero, false
	}
	m := s[0]
	for _, v := range s[1:] {
		if v > m {
			m = v
		}
	}
	return m, true
}

// Min returns the smallest element of s along with true.
func Min[T Ordered](s []T) (T, bool) {
	var zero T
	if len(s) == 0 {
		return zero, false
	}
	m := s[0]
	for _, v := range s[1:] {
		if v < m {
			m = v
		}
	}
	return m, true
}

// Reverse reverses s in place.
func Reverse[T any](s []T) {
	for i, j := 0, len(s)-1; i < j; i, j = i+1, j-1 {
		s[i], s[j] = s[j], s[i]
	}
}

// Reversed returns a new slice containing the elements of s in reverse order.
func Reversed[T any](s []T) []T {
	out := make([]T, len(s))
	for i, v := range s {
		out[len(s)-1-i] = v
	}
	return out
}

// IndexOf returns the index of the first element equal to x, or -1 if absent.
func IndexOf[T comparable](s []T, x T) int {
	for i, v := range s {
		if v == x {
			return i
		}
	}
	return -1
}

// Contains reports whether x appears in s.
func Contains[T comparable](s []T, x T) bool {
	return IndexOf(s, x) >= 0
}

// Insert returns a new slice with v inserted at index i. It panics if i is
// out of range [0, len(s)].
func Insert[T any](s []T, i int, v T) []T {
	if i < 0 || i > len(s) {
		panic("arrayx.Insert: index out of range")
	}
	out := make([]T, 0, len(s)+1)
	out = append(out, s[:i]...)
	out = append(out, v)
	out = append(out, s[i:]...)
	return out
}

// Remove returns a new slice with the element at index i removed, preserving
// order. It panics if i is out of range [0, len(s)).
func Remove[T any](s []T, i int) []T {
	if i < 0 || i >= len(s) {
		panic("arrayx.Remove: index out of range")
	}
	out := make([]T, 0, len(s)-1)
	out = append(out, s[:i]...)
	out = append(out, s[i+1:]...)
	return out
}

// RemoveUnordered removes the element at index i in O(1) by swapping with the
// last element and shrinking. It mutates and returns s.
func RemoveUnordered[T any](s []T, i int) []T {
	if i < 0 || i >= len(s) {
		panic("arrayx.RemoveUnordered: index out of range")
	}
	last := len(s) - 1
	s[i] = s[last]
	var zero T
	s[last] = zero // help GC if T is pointer-like
	return s[:last]
}

// BinarySearch returns the index of x in the sorted slice s along with true.
// If x is absent it returns the index where x could be inserted along with
// false. Runs in O(log n).
func BinarySearch[T Ordered](s []T, x T) (int, bool) {
	lo, hi := 0, len(s)
	for lo < hi {
		mid := int(uint(lo+hi) >> 1) // avoid overflow
		switch {
		case s[mid] < x:
			lo = mid + 1
		case s[mid] > x:
			hi = mid
		default:
			return mid, true
		}
	}
	return lo, false
}

// TwoSumSorted finds two indices i < j in the sorted slice s such that
// s[i]+s[j] == target, in O(n) time using the two-pointer technique. The
// boolean is false if no such pair exists.
func TwoSumSorted[T Number](s []T, target T) (int, int, bool) {
	lo, hi := 0, len(s)-1
	for lo < hi {
		sum := s[lo] + s[hi]
		switch {
		case sum == target:
			return lo, hi, true
		case sum < target:
			lo++
		default:
			hi--
		}
	}
	return 0, 0, false
}

// RotateLeft rotates s to the left by k positions in place, in O(n) time and
// O(1) extra space using the three-reverse trick.
func RotateLeft[T any](s []T, k int) {
	n := len(s)
	if n == 0 {
		return
	}
	k %= n
	if k < 0 {
		k += n
	}
	Reverse(s[:k])
	Reverse(s[k:])
	Reverse(s)
}