slice

Documentation

Overview

Package slice provides generic slice utilities such as binary search and sorting.

Index

• func Bsearch[T any](slice []T, compare func(target T) CompareType) int
• func IsSorted[T any](slice []T, compare func(a, b T) bool) bool
• func ParallelSort[T any](slice []T, compare func(a, b T) bool, level int)
• func Sort[T any](slice []T, compare func(a, b T) bool)
• type CompareType

Functions

func Bsearch

func Bsearch[T any](slice []T, compare func(target T) CompareType) int

Bsearch performs a binary search on a sorted slice. The compare function should return one of TARGET_SMALL, EQUAL, or TARGET_BIG for the probed element. It returns the index i such that compare(slice[i]) == EQUAL, or -1 if no such element exists.

func IsSorted

func IsSorted[T any](slice []T, compare func(a, b T) bool) bool

IsSorted verifies that slice is sorted. It returns true if for all adjacent elements a, b in slice, compare(a, b) is true.

func ParallelSort

func ParallelSort[T any](slice []T, compare func(a, b T) bool, level int)

ParallelSort performs a parallel merge sort on slice using compare. level is the maximum recursion depth to parallelize.

func Sort

func Sort[T any](slice []T, compare func(a, b T) bool)

Sort performs a merge sort on slice using compare. The compare function should return true if a should come before b.

Types

type CompareType

type CompareType int

CompareType indicates the relation of the probed element to the target.

const (
	// TARGET_SMALL indicates the target is larger than the probed element; search right.
	TARGET_SMALL CompareType = -1
	// EQUAL indicates the target matches the probed element.
	EQUAL CompareType = 0
	// TARGET_BIG indicates the target is smaller than the probed element; search left.
	TARGET_BIG CompareType = 1
)