algo

package
Version: v0.0.0-...-618c4c6 Latest Latest
Warning

This package is not in the latest version of its module.

Go to latest
Published: Jan 18, 2023 License: Apache-2.0 Imports: 8 Imported by: 0

Documentation

Overview

Package algo implements a few generic algorithms.

Index

Constants

This section is empty.

Variables

View Source
var (
	// Neigh4 is a slice containing a step up, right, down, and left
	// (N, E, S, W).
	Neigh4 = []image.Point{{0, -1}, {1, 0}, {0, 1}, {-1, 0}}

	// Neigh8 is a slice containing a step to all 8 neighbouring cells in order
	// from top-left to bottom-right.
	Neigh8 = []image.Point{
		{-1, -1}, {0, -1}, {1, -1},
		{-1, 0}, {1, 0},
		{-1, 1}, {0, 1}, {1, 1},
	}

	// ULDR maps U, L, D, and R to a single step in that direction.
	ULDR = map[rune]image.Point{
		'U': {0, -1},
		'R': {1, 0},
		'D': {0, 1},
		'L': {-1, 0},
	}

	// NESW maps N, E, S, and W to a single step in that direction.
	NESW = map[rune]image.Point{
		'N': {0, -1},
		'E': {1, 0},
		'S': {0, 1},
		'W': {-1, 0},
	}

	// CGVL maps ^, >, v, and < to a single step in that direction.
	CGVL = map[rune]image.Point{
		'^': {0, -1},
		'>': {1, 0},
		'v': {0, 1},
		'<': {-1, 0},
	}
)

Functions

func AStar

func AStar[T comparable, D constraints.Ordered](start T, h func(T) D, visit func(T, D) (map[T]D, error)) (map[T]T, error)

AStar implements A* search, a variant of Dijkstra's algorithm which takes an additional heuristic h into account. h(x) should return an estimate of d(x, end). If h(x) <= d(x, end) (that is, h underestimates) then AStar will find the shortest path. It returns a map of each node to the previous node in the shortest path to that node. This predecessor map is only complete for visited nodes.

The algorithm starts with a given start node and assumes the zero value for D is the starting distance for that node. It then repeatedly calls visit, passing each node and the length of the shortest path to that node. visit should either return a new collection of items and weights (the neighbours of the node it was given, and the weight of the edge connecting it) or an error. If visit returns a non-nil error, the algorithm halts and passes both the error and the partial map of predecessors, back to the caller. The algorithm takes care of tracking nodes that have already been visited - since visit does not need to track already-visited nodes, it can safely return all known neighbours of a node.

func Abs

func Abs[T Real](x T) T

Abs returns the absolute value of x (with no regard for negative overflow).

The math/cmplx package provides a version of Abs for complex types.

func Count

func Count[S ~[]E, E comparable](s S, e E) int

Count counts the number of occurrences of e in the slice s, in O(len(s)) time. This is faster than Freq when counting only one or a few values.

func Dijkstra

func Dijkstra[T comparable, D constraints.Ordered](start T, visit func(T, D) (map[T]D, error)) (map[T]T, error)

Dijkstra is an implementation of Dijkstra's algorithm for single-source shortest paths on a directed, non-negatively weighted graph. It is equivalent to AStar with a heuristic that always returns zero. It returns a map of each node to the previous node in the shortest path to that node. This predecessor map is only complete for visited nodes.

The algorithm starts with a given start node and assumes the zero value for D is the starting distance for that node. It then repeatedly calls visit, passing each node and the length of the shortest path to that node. visit should either return a new collection of items and weights (the neighbours of the node it was given, and the weight of the edge connecting it) or an error. If visit returns a non-nil error, the algorithm halts and passes both the error and the partial map of predecessors, back to the caller. The algorithm takes care of tracking nodes that have already been visited - since visit does not need to track already-visited nodes, it can safely return all known neighbours of a node.

func ExpandRect

func ExpandRect(r *image.Rectangle, p image.Point)

ExpandRect expands the Rectangle r to include p.

func FloodFill

func FloodFill[T comparable](start T, visit func(T, int) ([]T, error)) (map[T]T, error)

FloodFill is an algorithm for finding single-source shortest paths in an unweighted directed graph. It follows the same conventions as the Dijkstra function. It assumes the weight of each edge is always 1, tallying distances as ints. This flood-fill is generic and makes minimal assumptions about each node. A more specific implementation than this one is more appropriate in some cases, e.g. flood-filling a 2D grid.

func Foldl

func Foldl[S ~[]E, E any](in S, f func(E, E) E) E

Foldl implements a functional "reduce" operation over slices. Loosely: Foldl(in, f) = f(f(f(...f(in[0], in[1]), in[2]),...), in[len(in)-1]). For example, if in is []int, Foldl(in, func(x, y int) int { return x + y }) computes the sum. (The Sum function achieves the same thing in less code.) If len(in) == 0, the zero value for E is returned.

func Foldr

func Foldr[S ~[]E, E any](in S, f func(E, E) E) E

Foldr is the same as Foldl, but considers elements in the reverse.

func Freq

func Freq[S ~[]E, E comparable](s S) map[E]int

Freq counts the frequency of each item in a slice.

func GCD

func GCD[T constraints.Integer](a, b T) T

GCD returns the greatest common divisor of a and b.

func L1

func L1(p image.Point) int

L1 returns the Manhattan norm of p.

func Linfty

func Linfty(p image.Point) int

Linfty returns the L∞ norm of p.

func Map

func Map[S ~[]X, X, Y any](in S, f func(X) Y) []Y

Map calls f with each element of in, to build the output slice.

func MapCount

func MapCount[M ~map[K]V, K, V comparable](m M, v V) int

MapCount counts the number of occurrences of v in the map m, in O(len(m)) time. This is faster than MapFreq when counting only one or a few values.

func MapFreq

func MapFreq[M ~map[K]V, K, V comparable](m M) map[V]int

MapFreq counts the frequency of each value in a map.

func MapFromSlice

func MapFromSlice[S ~[]E, E any](s S) map[int]E

MapFromSlice creates a map[int]E from a slice of E. There's usually no reason for this.

func MapKeyRange

func MapKeyRange[M ~map[K]V, K constraints.Ordered, V any](m M) (min, max K)

MapKeyRange reports the minimum and maximum keys in the map m. If m is empty, the zero value for K is returned.

func MapMap

func MapMap[M ~map[K1]V1, K1, K2 comparable, V1, V2 any](m M, f func(K1, V1) (K2, V2)) map[K2]V2

MapMap is like Map, but for maps. This seems thoroughly pointless.

func MapMax

func MapMax[M ~map[K]V, K comparable, V constraints.Ordered](m M) (K, V)

MapMax finds the greatest value in the map m and returns the corresponding key and the value itself. If len(m) == 0, the zero values for K and V are returned. If there is a tie, the first key encountered is returned (which could be random).

func MapMin

func MapMin[M ~map[K]V, K comparable, V constraints.Ordered](m M) (K, V)

MapMin finds the least value in the map m and returns the corresponding key and the value itself. If len(m) == 0, the zero values for K and V are returned. If there is a tie, the first key encountered is returned (which could be random).

func MapOrErr

func MapOrErr[S ~[]X, X, Y any](in S, f func(X) (Y, error)) ([]Y, error)

MapOrErr calls f with each element of in, to build the output slice. It stops and returns the first error returned by f.

func MapRange

func MapRange[M ~map[K]V, K comparable, V constraints.Ordered](m M) (mink, maxk K, minv, maxv V)

MapRange reports the minimum and maximum values in the map m, and their corresponding keys. It does the work of MapMin and MapMax in one loop. If m is empty, the zero values for K and V are returned.

func Max

func Max[T constraints.Ordered](x ...T) T

Max returns the greatest argument (using `>`). If no arguments are provided, Max returns the zero value for T.

func Min

func Min[T constraints.Ordered](x ...T) T

Min returns the least argument (using `<`). If no arguments are provided, Min returns the zero value for T.

func MustMap

func MustMap[S ~[]X, X, Y any](in S, f func(X) (Y, error)) []Y

MustMap calls f with each element of in, to build the output slice. It panics with the first error returned by f.

func MustMapMap

func MustMapMap[M ~map[K1]V1, K1, K2 comparable, V1, V2 any](m M, f func(K1, V1) (K2, V2, error)) map[K2]V2

MustMapMap is like MustMap, but for maps. This seems extra pointless.

func NextPermutation

func NextPermutation[S ~[]E, E constraints.Ordered](s S) bool

NextPermutation reorders s into the next permutation (in the lexicographic order), reporting if it was able to do so. Based on Knuth.

func Pow

func Pow[T any](base T, pow uint, op func(T, T) T) T

Pow raises base to the power pow, where multiplication is given by op. The only requirements are that:

  • op must be power associative for base (i.e. `op(op(base,base),base) == op(base,op(base,base))`), and
  • pow must be strictly positive (pow >= 1). If pow <= 0, Pow will panic.

op is called O(log(pow) + bits.OnesCount(pow)) times.

If you are working with big numbers, use math/big.

Note that op need *not* have an identity element, or even be generally associative. *Power associativity* is the minimum condition needed to make "the nth power of a value" unambiguous. If you like, you can dispense with power associativity, but then Pow is not guaranteed to give you any particular power (for pow > 2).

(In the current implementation, Pow(base, 7, ...) = base * base^2 * (base^2 * base^2).)

For Pow to be able to handle pow == 0 would require either an additional parameter, or more convention-setting. But you can easily test for pow == 0 yourself before calling.

func Prod

func Prod[S ~[]E, E Numeric](in S) E

Prod computes the product of elements in any slice where the element type is numeric. If len(in) == 0, 1 is returned.

func Reverse

func Reverse[S ~[]E, E any](s S)

Reverse reverses a slice.

func SliceFromMap

func SliceFromMap[M ~map[K]V, K constraints.Integer, V any](m M) ([]V, K)

SliceFromMap creates a slice of V from a map[K]V, plus an offset value such that s[k] == m[k+offset] for all k in m. The slice will be exactly large enough to contain all keys (offsetted). The result will be extremely memory wasteful if the keys in m are few and far between. Entries in the slice with no corresponding entry in the map will have the zero value.

func SortAsc

func SortAsc[S ~[]E, E constraints.Ordered](s S)

SortAsc sorts the slice in ascending order.

func SortByFuncAsc

func SortByFuncAsc[S ~[]E, E any, V constraints.Ordered](s S, f func(E) V)

SortByFuncAsc stably sorts the slice using the function to provide values to compare.

func SortByFuncDesc

func SortByFuncDesc[S ~[]E, E any, V constraints.Ordered](s S, f func(E) V)

SortByFuncDesc stably sorts the slice using the function to provide values to compare.

func SortByMapAsc

func SortByMapAsc[S ~[]K, M ~map[K]V, K comparable, V constraints.Ordered](s S, m M)

SortByMapAsc stably sorts the slice using the map to provide values to compare.

func SortByMapDesc

func SortByMapDesc[S ~[]K, M ~map[K]V, K comparable, V constraints.Ordered](s S, m M)

SortByMapDesc stably sorts the slice using the map to provide values to compare.

func SortDesc

func SortDesc[S ~[]E, E constraints.Ordered](s S)

SortDesc sort the slice in descending order.

func Sum

func Sum[S ~[]E, E Addable](in S) E

Sum sums any slice where the elements support the + operator. If len(in) == 0, the zero value for E is returned.

func XGCD

func XGCD[T constraints.Integer](a, b T) (d, x, y T)

XGCD returns the greatest common divisor of a and b, as well as the Bézout coefficients (x and y such that ax + by = GCD(a, b)). For arithmetic on large integers, use math/big.

Types

type AABB3

type AABB3[E Real] struct {
	Min, Max Vec3[E]
}

AABB3 is a three-dimensional axis-aligned bounding box.

func (AABB3[E]) Empty

func (r AABB3[E]) Empty() bool

Empty reports if the box is empty.

func (*AABB3[E]) Expand

func (r *AABB3[E]) Expand(p Vec3[E])

Expand increases the box to include the given point.

type AABB4

type AABB4[E Real] struct {
	Min, Max Vec4[E]
}

AABB4 is a four-dimensional axis-aligned bounding box.

func (AABB4[E]) Empty

func (r AABB4[E]) Empty() bool

Empty reports if the box is empty.

func (*AABB4[E]) Expand

func (r *AABB4[E]) Expand(p Vec4[E])

Expand increases the box to include the given point.

type Addable

type Addable interface {
	Numeric | ~string
}

Addable types have any of the built-in types that support the + operator as the underlying type.

type DisjointSets

type DisjointSets[T comparable] map[T]T

DisjointSets implements union-find algorithms for disjoint sets.

func (DisjointSets[T]) Find

func (d DisjointSets[T]) Find(x T) T

Find returns the representative element of the set containing x. It freely modifies d. If x is not contained in d, Find inserts x as a new disjoint singleton set within d and returns x.

func (DisjointSets[T]) Reps

func (d DisjointSets[T]) Reps() Set[T]

Reps returns a set containing each representative element.

func (DisjointSets[T]) Sets

func (d DisjointSets[T]) Sets() map[T][]T

Sets returns all the sets in d, in a map from the representative element to a slice containing all members of that set.

func (DisjointSets[T]) Union

func (d DisjointSets[T]) Union(x, y T)

Union merges the set containing x with the set containing y. If both of the elements are not contained in d, a new set is created.

type ListNode

type ListNode[E any] struct {
	Prev, Next *ListNode[E]
	Value      E
}

ListNode implements a node in a doubly-linked list.

func ListFromSlice

func ListFromSlice[E any, S ~[]E](s S) []*ListNode[E]

ListFromSlice creates a circular list from a slice, and returns a slice containing all the nodes in order. (Why? Often the original order is important for some reason.)

func (*ListNode[E]) InsertAfter

func (n *ListNode[E]) InsertAfter(p *ListNode[E])

InsertAfter inserts n after p.

func (*ListNode[E]) InsertBefore

func (n *ListNode[E]) InsertBefore(p *ListNode[E])

InsertBefore inserts n before p.

func (*ListNode[E]) Remove

func (n *ListNode[E]) Remove()

Remove removes the node from the list (its neighbors point to one another). The node's Prev and Next remain unaltered.

func (*ListNode[E]) Succ

func (n *ListNode[E]) Succ(m int) *ListNode[E]

Succ returns the mth item from n. For example, n.Succ(1) == n.Next. m can be negative (n.Succ(-1) == n.Prev). Runs in time O(|m|).

func (*ListNode[E]) ToSlice

func (n *ListNode[E]) ToSlice() []E

ToSlice returns a new slice containing the items in list order.

type Numeric

type Numeric interface {
	Real | constraints.Complex
}

Numeric types have any of the built-in numeric types as the underlying type.

type PriQueue

type PriQueue[T any, D constraints.Ordered] minHeap[T, D]

PriQueue implements a priority queue of items of type T each having a priority of type D. It uses container/heap under the hood.

func (*PriQueue[T, D]) Len

func (pq *PriQueue[T, D]) Len() int

Len returns the size of the queue.

func (*PriQueue[T, D]) Pop

func (pq *PriQueue[T, D]) Pop() (T, D)

Pop removes the item with the least priority value, and returns both it and its priority.

func (*PriQueue[T, D]) Push

func (pq *PriQueue[T, D]) Push(item T, priority D)

Push adds an item to the queue with a priority.

type Range

type Range[T constraints.Ordered] struct {
	Min, Max T
}

Range represents an inclusive range of values.

func (Range[T]) Clamp

func (r Range[T]) Clamp(x T) T

Clamp returns x if x is within the range, r.Min if x is less than the range, or r.Max if x is greather than the range.

func (Range[T]) Contains

func (r Range[T]) Contains(x T) bool

Contains reports if r contains x.

func (Range[T]) ContainsRange

func (r Range[T]) ContainsRange(s Range[T]) bool

ContainsRange reports if r contains the entirety of s.

func (Range[T]) Intersection

func (r Range[T]) Intersection(s Range[T]) Range[T]

Intersection returns the intersection of the two ranges. (It could be empty.)

func (Range[T]) IsEmpty

func (r Range[T]) IsEmpty() bool

IsEmpty reports if the range is empty.

func (Range[T]) Union

func (r Range[T]) Union(s Range[T]) Range[T]

Union returns a range covering both ranges. (It could include subranges that don't overlap either r or s).

type Real

type Real interface {
	constraints.Integer | constraints.Float
}

Real types have any of the built-in integer or float types (but not complex) as the underlying type.

type Set

type Set[T comparable] map[T]struct{}

Set is a generic set type based on map. There's a million of these now; what harm is another?

Set aims to work in a slice-like fashion with nil-valued sets, i.e.:

var s Set[int]
s = s.Insert(420, 69)   // s now contains 420 and 69

However, Insert (and Add) do not make new sets if the set is non-nil, e.g.:

s := make(Set[int])
s.Insert(420, 69)   // as above

func ByteSet

func ByteSet(s string) Set[byte]

ByteSet saves keystrokes (it returns SetFromSlice([]byte(s)))

func Intersection

func Intersection[T comparable](sets ...Set[T]) Set[T]

Intersection returns the intersection of multiple sets as a new set.

func MakeSet

func MakeSet[T comparable](items ...T) Set[T]

MakeSet makes a set out of a list of items.

func RuneSet

func RuneSet(s string) Set[rune]

RuneSet saves keystrokes (it returns SetFromSlice([]rune(s)))

func SetFromSlice

func SetFromSlice[E comparable, S ~[]E](sl S) Set[E]

SetFromSlice saves keystrokes (it returns make(Set[E]).Insert(sl...))

func Union

func Union[T comparable](sets ...Set[T]) Set[T]

Union returns the union of multiple sets as a new set.

func (Set[T]) Add

func (s Set[T]) Add(t Set[T]) Set[T]

Add adds the elements from t into s, and returns s. If s == nil, Add returns a new set which is a copy of t.

func (Set[T]) Contains

func (s Set[T]) Contains(x T) bool

Contains reports whether s contains x.

func (Set[T]) Copy

func (s Set[T]) Copy() Set[T]

Copy returns a copy of the set.

func (Set[T]) Difference

func (s Set[T]) Difference(t Set[T]) Set[T]

Difference returns a new set with elements from s that are not in t.

func (Set[T]) Disjoint

func (s Set[T]) Disjoint(t Set[T]) bool

Disjoint reports whether s and t have an empty intersection.

func (Set[T]) Equal

func (s Set[T]) Equal(t Set[T]) bool

Equal reports whether two sets are equal.

func (Set[T]) Insert

func (s Set[T]) Insert(x ...T) Set[T]

Insert inserts x into the set. If s == nil, Insert returns a new set containing x. This allows patterns like `m[k] = m[k].Insert(x)` (for a map m with set values).

func (Set[T]) Intersection

func (s Set[T]) Intersection(t Set[T]) Set[T]

Intersection returns a new set with elements common to both sets.

func (Set[T]) Keep

func (s Set[T]) Keep(t Set[T]) Set[T]

Keep removes all elements *not* in t from s, and returns s. (s = s.Intersection(t), but Keep modifies s in-place.)

func (Set[T]) String

func (s Set[T]) String() string

func (Set[T]) SubsetOf

func (s Set[T]) SubsetOf(t Set[T]) bool

SubsetOf reports whether s is a subset or equal to t.

func (Set[T]) Subtract

func (s Set[T]) Subtract(t Set[T]) Set[T]

Subtract removes all elements in t from s, and returns s.

func (Set[T]) SymmetricDifference

func (s Set[T]) SymmetricDifference(t Set[T]) Set[T]

SymmetricDifference returns a new set with elements that are either in s, or in t, but not in both.

func (Set[T]) ToSlice

func (s Set[T]) ToSlice() []T

ToSlice returns a new slice with all the elements of the set in random order.

func (Set[T]) Union

func (s Set[T]) Union(t Set[T]) Set[T]

Union returns a new set containing elements from both sets.

type Topic

type Topic[T any] struct {
	// contains filtered or unexported fields
}

Topic is a pub-sub topic.

func (*Topic[T]) Close

func (q *Topic[T]) Close()

Close closes the topic.

func (*Topic[T]) Pub

func (q *Topic[T]) Pub(v T)

Pub publishes the value v onto the topic.

func (*Topic[T]) Sub

func (q *Topic[T]) Sub() <-chan T

Sub subscribes to subsequent messages on the topic.

type Vec3

type Vec3[E Real] [3]E

Vec3 is a three-dimensional vector type over E.

func (Vec3[E]) Add

func (x Vec3[E]) Add(y Vec3[E]) Vec3[E]

Add returns x+y.

func (Vec3[E]) Div

func (x Vec3[E]) Div(k E) Vec3[E]

Div returns the scalar product with (1/k).

func (Vec3[E]) Dot

func (x Vec3[E]) Dot(y Vec3[E]) E

Dot returns the dot product of x and y.

func (Vec3[E]) In

func (x Vec3[E]) In(r AABB3[E]) bool

In reports if the vector is inside the bounding box.

func (Vec3[E]) L1

func (x Vec3[E]) L1() E

L1 returns the Manhattan norm.

func (Vec3[E]) L2

func (x Vec3[E]) L2() float64

L2 returns the Euclidean norm.

func (Vec3[E]) Linfty

func (x Vec3[E]) Linfty() E

Linfty returns the L∞ norm.

func (Vec3[E]) Mul

func (x Vec3[E]) Mul(k E) Vec3[E]

Mul returns the scalar product.

func (Vec3[E]) Sub

func (x Vec3[E]) Sub(y Vec3[E]) Vec3[E]

Sub returns x-y.

type Vec4

type Vec4[E Real] [4]E

Vec4 is a four-dimensional vector type over E.

func (Vec4[E]) Add

func (x Vec4[E]) Add(y Vec4[E]) Vec4[E]

Add returns x+y.

func (Vec4[E]) Div

func (x Vec4[E]) Div(k E) Vec4[E]

Div returns the scalar product with (1/k).

func (Vec4[E]) Dot

func (x Vec4[E]) Dot(y Vec4[E]) E

Dot returns the dot product of x and y.

func (Vec4[E]) In

func (x Vec4[E]) In(r AABB4[E]) bool

In reports if the vector is inside the bounding box.

func (Vec4[E]) L1

func (x Vec4[E]) L1() E

L1 returns the Manhattan norm.

func (Vec4[E]) L2

func (x Vec4[E]) L2() float64

L2 returns the Euclidean norm.

func (Vec4[E]) Linfty

func (x Vec4[E]) Linfty() E

Linfty returns the L∞ norm.

func (Vec4[E]) Mul

func (x Vec4[E]) Mul(k E) Vec4[E]

Mul returns the scalar product.

func (Vec4[E]) Sub

func (x Vec4[E]) Sub(y Vec4[E]) Vec4[E]

Sub returns x-y.

type WeightedItem

type WeightedItem[T any, D constraints.Ordered] struct {
	Item   T
	Weight D
}

WeightedItem is an item together with a weight value.

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL