minimize

Documentation

Index

• Variables
• func Slice[T any](config Config[T], slice []T) ([]T, error)
• func SliceWithFixed[T any](config Config[T], slice []T, fixed func(T) bool) ([]T, error)
• type Config

Variables

var ErrTooManyChunks = errors.New("the bisection process is following too many necessary chunks")

ErrTooManyChunks is returned if the number of necessary chunks surpassed MaxChunks.

Functions

func Slice

func Slice[T any](config Config[T], slice []T) ([]T, error)

Slice() finds a minimal subsequence of slice elements that still gives Pred() == true. The algorithm works by sequentially splitting the slice into smaller-size chunks and running Pred() witout those chunks. Slice() receives the original slice chunks. The expected number of Pred() runs is O(|result|*log2(|elements|)).

func SliceWithFixed

func SliceWithFixed[T any](config Config[T], slice []T, fixed func(T) bool) ([]T, error)

SliceWithFixed behaves like Slice, but also allows to designate the elements that must always remain (the "fixed" ones).

Types

type Config

type Config[T any] struct {
	// The original slice is minimized with respect to this predicate.
	// If Pred(X) returns true, X is assumed to contain all elements that must stay.
	Pred func([]T) (bool, error)
	// MaxSteps is a limit on the number of predicate calls during bisection.
	// If it's hit, the bisection continues as if Pred() begins to return false.
	// If it's set to 0 (by default), no limit is applied.
	MaxSteps int
	// MaxChunks sets a limit on the number of chunks pursued by the bisection algorithm.
	// If we hit the limit, bisection is stopped and Array() returns ErrTooManyChunks
	// anongside the intermediate bisection result (a valid, but not fully minimized slice).
	MaxChunks int
	// Logf is used for sharing debugging output.
	Logf func(string, ...interface{})
}