bisect

README

Bisection algorithms module for Go

Inspired by CPython bisect

Installation

go get github.com/goimp/bisect

Docs can be found there

Documentation

Index

• func Bisect[T any](a []T, x T, lo int, hi int, compare Comparator[T]) int
• func BisectLeft[T any](a []T, x T, lo int, hi int, compare Comparator[T]) int
• func BisectRight[T any](a []T, x T, lo int, hi int, compare Comparator[T]) int
• func CompareBool(a, b bool) int
• func CompareByte(a, b byte) int
• func CompareFloat32(a, b float32) int
• func CompareFloat64(a, b float64) int
• func CompareInt(a, b int) int
• func CompareRune(a, b rune) int
• func CompareStrings(a, b string) int
• func CompareUint(a, b uint) int
• func Insort[T any](a *[]T, x T, lo, hi int, compare Comparator[T])
• func InsortLeft[T any](a *[]T, x T, lo, hi int, compare Comparator[T])
• func InsortRight[T any](a *[]T, x T, lo, hi int, compare Comparator[T])
• type Comparator

Functions

func Bisect

func Bisect[T any](a []T, x T, lo int, hi int, compare Comparator[T]) int

Global alias to BisectRight using wrapper functions

func BisectLeft

func BisectLeft[T any](a []T, x T, lo int, hi int, compare Comparator[T]) int

Return the index where to insert item x in list a, assuming a is sorted. The return value i is such that all e in a[:i] have e < x, and all e in a[i:] have e >= x. So if x already appears in the list, a.insert(i, x) will insert just before the leftmost x already there. Optional args lo (default 0) and hi (default len(a)) bound the slice of a to be searched. A comparator function should be supplied to customize the sort order.

func BisectRight

func BisectRight[T any](a []T, x T, lo int, hi int, compare Comparator[T]) int

Return the index where to insert item x in list a, assuming a is sorted. The return value i is such that all e in a[:i] have e <= x, and all e in a[i:] have e > x. So if x already appears in the list, a.insert(i, x) will insert just after the rightmost x already there. Optional args lo (default 0) and hi (default len(a)) bound the slice of a to be searched. A comparator function should be supplied to customize the sort order.

func CompareBool

func CompareBool(a, b bool) int

Comparator for boolean values (false < true)

func CompareByte

func CompareByte(a, b byte) int

Comparator for bytes (unsigned 8-bit integers)

func CompareFloat32

func CompareFloat32(a, b float32) int

Comparator for floating-point numbers

func CompareFloat64

func CompareFloat64(a, b float64) int

Comparator for floating-point numbers

func CompareInt

func CompareInt(a, b int) int

Comparator for integers

func CompareRune

func CompareRune(a, b rune) int

Comparator for runes (Unicode code points)

func CompareStrings

func CompareStrings(a, b string) int

Comparator for sorting strings lexicographically

func CompareUint

func CompareUint(a, b uint) int

Comparator for unsigned integers

func Insort

func Insort[T any](a *[]T, x T, lo, hi int, compare Comparator[T])

Global alias to InsortRight using wrapper functions

func InsortLeft

func InsortLeft[T any](a *[]T, x T, lo, hi int, compare Comparator[T])

Insert item x in list a, and keep it sorted assuming a is sorted. If x is already in a, insert it to the left of the leftmost x. Optional args lo (default 0) and hi (default len(a)) bound the slice of a to be searched. A comparator function should be supplied to customize the sort order.

func InsortRight

func InsortRight[T any](a *[]T, x T, lo, hi int, compare Comparator[T])

Insert item x in list a, and keep it sorted assuming a is sorted. If x is already in a, insert it to the right of the rightmost x. Optional args lo (default 0) and hi (default len(a)) bound the slice of a to be searched. A comparator function should be supplied to customize the sort order.

Types

type Comparator

type Comparator[T any] func(a, b T) int

Comparator defines a function type for comparing two elements. It should return a negative value if a < b, 0 if a == b, and a positive value if a > b.