sortutil

Documentation

Index

• func BinaryInsert[T any](l *[]T, cmp func(entry T) int) (entry *T, added bool)
• func FilterInPlace[V any](l []V, predicate func(V) bool) []V
• func Remove[T any](l *[]T, cmp func(entry T) int) bool
• func RemoveAt[T any](l *[]T, i int)
• func Search[T any](l []T, cmp func(entry T) int) (index int, found bool)

Functions

func BinaryInsert

func BinaryInsert[T any](l *[]T, cmp func(entry T) int) (entry *T, added bool)

BinaryInsert uses Search to find the smallest index i in [0, len(l)) at which cmp(l[i]) ≥ 0. If i ≥ len(l), an empty entry is appended. Otherwise an empty entry is inserted at i unless cmp == 0. BinaryInsert returns l, the address of l[i], and whether a new entry was added.

func FilterInPlace

func FilterInPlace[V any](l []V, predicate func(V) bool) []V

FilterInPlace removes elements of L that fail the predicate without allocating with O(N) runtime. FilterInPlace may reorder L.

This doesn't really fit in the sortutil package but 🤷 making a new package for just this function would be excessive.

func Remove

func Remove[T any](l *[]T, cmp func(entry T) int) bool

Remove removes the specified element.

func RemoveAt

func RemoveAt[T any](l *[]T, i int)

RemoveAt removes the specified element.

func Search

func Search[T any](l []T, cmp func(entry T) int) (index int, found bool)

Search uses a binary search to find and return the smallest index i in [0, len(l)) at which cmp(l[i]) ≥ 0, assuming that on the range [0, len(l)), cmp(l[i]) ≥ 0 implies cmp(l[i+1]) ≥ 0. That is, Search requires that cmp ≥ 0 for some (possibly empty) prefix of the input range [0, len(l)) and then < 0 for the (possibly empty) remainder; Search returns the first ≥ 0 index and whether cmp == 0 for that index. If there is no such index, Search returns len(l), false.