lib

package
v0.0.0-...-6c6fb3e Latest Latest
Warning

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

 Go to latest Published: Jan 1, 2024 License: MIT Imports: 15 Imported by: 0

Documentation

Index

Constants

View Source 
const EPSILON = 1e-12

Variables

View Source 
var AocFunMap map[int][]func()

Functions

func Abs 

func Abs[T SignedNum](a T) T

func Add2 

func Add2[T Num](p, q [2]T) [2]T

func Add3 

func Add3[T Num](p, q [3]T) [3]T

func Append 

func Append[T any](xs *[]T, el ...T)

func AssertEqual 

func AssertEqual[E comparable](t *testing.T, got, want E)

func AssertSlicesEqual 

func AssertSlicesEqual[E comparable](t *testing.T, got, want []E)

func CaptureStdout 

func CaptureStdout(f func()) []byte

func Colinear 

func Colinear(a, b, c [2]float64) bool

func Det22 

func Det22[T Num, E ~[2]T](a, b E) T

func Det22Rat 

func Det22Rat(a, b [2]*big.Rat) *big.Rat

func Det32 

func Det32[T Num, E ~[2]T](a, b, c E) T

func Dist2 

func Dist2[T SignedNum](a, b [2]T) T

func DistL1Rat 

func DistL1Rat(a, b [2]*big.Rat) *big.Rat

func EdgesOf 

func EdgesOf[T comparable](g map[T]map[T]int) map[[2]T]int

func Filter 

func Filter[E any](xs []E, pred func(E) bool) []E

func FloydWarshallUnitEdges 

func FloydWarshallUnitEdges(g [][]int) (dist [][]int)

func Freq 

func Freq[E comparable](xs []E) map[E]int

func Gcd 

func Gcd(a, b int) int

func GlobalMinCut 

func GlobalMinCut(mat [][]int) (int, []int)

func Greater 

func Greater[T Ordered](p, q T) bool

func Greater2 

func Greater2[T Ordered](p, q [2]T) bool

func Greater3 

func Greater3[T Ordered](a, b [3]T) bool

func IntersectCuboids 

func IntersectCuboids[T Ordered](xs, ys [][2]T) [][2]T

func IntersectItvs 

func IntersectItvs[T Ordered](x, y [2]T) [2]T

Intersection of two (closed) intervals

func IsBetween 

func IsBetween(a, b, c [2]*big.Rat) bool

IsBetween checks whether point b is between a and c It assumes all three points are on one line

func IsDigit 

func IsDigit[T rune | byte](ch T) bool

func IsEmptyItv 

func IsEmptyItv[T Ordered](a [2]T) bool

IsEmpty returns true if the interval is empty

func Last 

func Last[E any](xs []E) E

func Lcm 

func Lcm(xs ...int) int

func Less2 

func Less2[T Ordered](a, b [2]T) bool

func Less3 

func Less3[T Ordered](a, b [3]T) bool

func LessOrEqual2 

func LessOrEqual2[T Ordered](a, b [2]T) bool

func Map 

func Map[T, S any](f func(T) S, xs []T) []S

func MatrixOfAdjList 

func MatrixOfAdjList(g AdjList) [][]int

func MaxIdx 

func MaxIdx[T Ordered](xs []T) int

func MergeItvs 

func MergeItvs[T Ordered](itvs [][2]T) [][2]T

func MkNumsUpto 

func MkNumsUpto[E Num](n int) []E

func MkSlice2 

func MkSlice2[E any](rows, cols int) [][]E

func MkSlice2Filled 

func MkSlice2Filled[E any](rows, cols int, t E) [][]E

func MkSlice3 

func MkSlice3[E any](rows, cols, height int) [][][]E

func MkSlice3Filled 

func MkSlice3Filled[E any](rows, cols, height int, e E) [][][]E

func MkSliceFilled 

func MkSliceFilled[E any](rows int, t E) []E

func Mod 

func Mod(a, b int) int

func PolygonArea 

func PolygonArea(pts [][2]int) int

func PopBack 

func PopBack[E any](x *[]E) E

func PopFront 

func PopFront[E any](x *[]E) E

func PrefixSums 

func PrefixSums[T Num](xs []T) []T

func PrefixSumsFunc 

func PrefixSumsFunc[T Num](f func(int) T, n int) []T

func PrintlnVect2s 

func PrintlnVect2s(vs []Vect2)

func Prod 

func Prod[T Num](xs []T) T

func PushBack 

func PushBack[E any](x *[]E, e E)

func PushFront 

func PushFront[E any](x *[]E, e E)

func QuadraticSolve 

func QuadraticSolve(a, b, c float64) (float64, float64, bool)

func ReadByteSlices 

func ReadByteSlices() [][]byte

func ReadByteSlicesFromScanner 

func ReadByteSlicesFromScanner(sc *bufio.Scanner) [][]byte

func ReadLines 

func ReadLines() []string

func ReadLinesFromFile 

func ReadLinesFromFile(fileName string) []string

func ReadStringsFromScanner 

func ReadStringsFromScanner(sc *bufio.Scanner) []string

func ReadTextFromScanner 

func ReadTextFromScanner(sc *bufio.Scanner) string

func Reverse 

func Reverse[E any](x []E)

func ScanFloat 

func ScanFloat(sc *bufio.Scanner) float64

func ScanInt 

func ScanInt(sc *bufio.Scanner) int

func ScanText 

func ScanText(sc *bufio.Scanner) string

func SecantSearch 

func SecantSearch(f func(float64) float64, a, b, precision float64) float64

func SetMax 

func SetMax[T Ordered](a *T, b T)

func SetMin 

func SetMin[T Ordered](a *T, b T)

func SetStdin 

func SetStdin(fName string) *os.File

func Shuffle 

func Shuffle[T any](xs []T)

func Sign 

func Sign[T SignedNum](a T) int

func SlicesEqual 

func SlicesEqual[E comparable](s1, s2 []E) bool

func SortLess2 

func SortLess2[T Ordered](s [][2]int)

func SortSliceDecr 

func SortSliceDecr[T Ordered](xs []T)

func SortSliceFunc 

func SortSliceFunc[E any, T Ordered](xs []E, f func(E) T)

func SortSliceLessFunc 

func SortSliceLessFunc[E any](xs []E, less func(a, b E) bool)

func StringOfList 

func StringOfList(l *list.List) string

func StringOfPointerSlice 

func StringOfPointerSlice[T any](l []*T) string

func Sum 

func Sum[T Num](xs []T) T

func SumOverMap 

func SumOverMap[T comparable, E Num](m map[T]E) E

func SurfaceOfCuboid3 

func SurfaceOfCuboid3(width, height, depth int) int

func Swap 

func Swap[T any](a [2]T) [2]T

func TernarySearch 

func TernarySearch(f func(float64) float64, a, b, precision float64) float64

func TransposeStrings 

func TransposeStrings(xs []string) []string

Types

type AdjList 

type AdjList [][]int

AdjList

func (AdjList) Add 

func (g AdjList) Add(v, w int)

func (AdjList) AddBoth 

func (g AdjList) AddBoth(v, w int)

type AdjMap 

type AdjMap []map[int]bool

AdjMap

func MkAdjMap 

func MkAdjMap(n int) AdjMap

func (AdjMap) Add 

func (g AdjMap) Add(v, w int)

func (AdjMap) AddBoth 

func (g AdjMap) AddBoth(v, w int)

type Bits 

type Bits uint64

func (Bits) Clear 

func (b Bits) Clear(pos int) Bits

func (Bits) ClearFlag 

func (b Bits) ClearFlag(flag Bits) Bits

func (Bits) Has 

func (b Bits) Has(pos int) bool

func (Bits) HasFlag 

func (b Bits) HasFlag(flag Bits) bool

func (Bits) Set 

func (b Bits) Set(pos int) Bits

func (Bits) SetFlag 

func (b Bits) SetFlag(flag Bits) Bits

func (Bits) Toggle 

func (b Bits) Toggle(pos int) Bits

func (Bits) ToggleFlag 

func (b Bits) ToggleFlag(flag Bits) Bits

type Heap 

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

func NewCostFunHeap 

func NewCostFunHeap[T any, V Ordered](cost func(T) V, data ...T) *Heap[T]

func NewHeap 

func NewHeap[T any](less func(a, b T) bool, data ...T) *Heap[T]

func NewIntCostHeap 

func NewIntCostHeap[T Ordered](cost []T, data ...int) *Heap[int]

func NewMaxHeap 

func NewMaxHeap[T Ordered](data ...T) *Heap[T]

func NewMinHeap 

func NewMinHeap[T Ordered](data ...T) *Heap[T]

func (*Heap[T]) Clear 

func (h *Heap[T]) Clear()

func (*Heap[T]) Data 

func (h *Heap[T]) Data() []T

func (*Heap[T]) Fix 

func (h *Heap[T]) Fix(i int)

Fix re-establishes the heap ordering after the element at index i has changed its value. Changing the value of the element at index i and then calling Fix is equivalent to, but less expensive than, calling h.Remove(i) followed by a Push of the new value. The complexity is O(log n) where n = h.Len().

func (*Heap[T]) Init 

func (h *Heap[T]) Init()

Init establishes the heap invariants required by the other routines in this package. Init is idempotent with respect to the heap invariants and may be called whenever the heap invariants may have been invalidated. The complexity is O(n) where n = h.Len().

func (*Heap[T]) Len 

func (h *Heap[T]) Len() int

func (*Heap[T]) Peek 

func (h *Heap[T]) Peek() T

func (*Heap[T]) Pop 

func (h *Heap[T]) Pop() T

Pop removes and returns the minimum element (according to lessFun) from the heap. The complexity is O(log n) where n = h.Len(). Pop is equivalent to h.Remove(0).

func (*Heap[T]) Push 

func (h *Heap[T]) Push(x T)

Push pushes the element x onto the heap. The complexity is O(log n) where n = h.Len().

func (*Heap[T]) Remove 

func (h *Heap[T]) Remove(i int) T

Remove removes and returns the element at index i from the heap. The complexity is O(log n) where n = h.Len()

func (*Heap[T]) String 

func (h *Heap[T]) String() string

type Integer 

type Integer interface {
	constraints.Integer
}

type MapGraph 

type MapGraph[T Num] []map[int]T

func MkMapGraph 

func MkMapGraph[T Num](n int) MapGraph[T]

func (MapGraph[T]) Add 

func (g MapGraph[T]) Add(u, v int, weight T)

Add inserts a directed edge from v to w with weight c. It overwrites the previous weight if this edge already exists.

func (MapGraph[T]) AddBoth 

func (g MapGraph[T]) AddBoth(u, v int, weight T)

AddBoth inserts edges with weigth c between v and w. It overwrites the previous weights if these edges already exist.

func (MapGraph[T]) AddBothNoChecks 

func (g MapGraph[T]) AddBothNoChecks(u, v int, weight T)

func (MapGraph[T]) AddNoChecks 

func (g MapGraph[T]) AddNoChecks(u, v int, weight T)

func (MapGraph[T]) Delete 

func (g MapGraph[T]) Delete(u, v int)

Delete removes an edge from v to w.

func (MapGraph[T]) DeleteBoth 

func (g MapGraph[T]) DeleteBoth(u, v int)

DeleteBoth removes all edges between v and w.

func (MapGraph[T]) HasEdge 

func (g MapGraph[T]) HasEdge(u, v int) bool

func (MapGraph[T]) HasEdgeNoChecks 

func (g MapGraph[T]) HasEdgeNoChecks(u, v int) bool

func (MapGraph[T]) LongestPathsAcyclicNP 

func (g MapGraph[T]) LongestPathsAcyclicNP(src int, MAX T) []T

func (MapGraph[T]) ShortestPathNP 

func (g MapGraph[T]) ShortestPathNP(src, tgt int, MAX T) T

func (MapGraph[T]) TopoSort 

func (g MapGraph[T]) TopoSort() []int

TopoSort assumes that the graph is acyclic

func (MapGraph[T]) Weight 

func (g MapGraph[T]) Weight(u, v int) T

type Num 

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

type Ordered 

type Ordered interface {
	constraints.Integer | constraints.Float | ~string
}

Ordered represents the set of types for which the '<' operator work.

type PQInt 

type PQInt[T Integer] struct {
	Heap[T]
	// contains filtered or unexported fields
}

func NewMaxPrioQ 

func NewMaxPrioQ[T Ordered](prio []T, num ...int) *PQInt[int]

func NewMaxPrioQG 

func NewMaxPrioQG[T Ordered, U Integer](prio []T, num ...int) *PQInt[U]

func NewMinCostQ 

func NewMinCostQ[T Ordered](cost []T, num ...int) *PQInt[int]

func NewMinCostQG 

func NewMinCostQG[T Ordered, U Integer](cost []T, num ...int) *PQInt[U]

func NewPQInt 

func NewPQInt[T Integer](less func(a, b T) bool, num ...int) *PQInt[T]

func (*PQInt[T]) Contains 

func (q *PQInt[T]) Contains(v int) bool

Contains tells whether v is in the queue.

func (*PQInt[T]) Fix 

func (q *PQInt[T]) Fix(v T)

func (*PQInt[T]) IndexLen 

func (q *PQInt[T]) IndexLen() int

func (*PQInt[T]) Pop 

func (q *PQInt[T]) Pop() T

func (*PQInt[T]) Push 

func (q *PQInt[T]) Push(v T)

func (*PQInt[T]) Remove 

func (q *PQInt[T]) Remove(v int)

Remove element v

func (*PQInt[T]) Resize 

func (q *PQInt[T]) Resize(n int)

Resize the index so that the queue can hold larger elements

func (*PQInt[T]) String 

func (h *PQInt[T]) String() string

type PQItem 

type PQItem[T any] struct {
	Value T
	Index int
}

type PQueue 

type PQueue[T any] struct {
	Heap[*PQItem[T]]
}

func NewPQueue 

func NewPQueue[T any](less func(a, b T) bool) *PQueue[T]

func (*PQueue[T]) Peek 

func (q *PQueue[T]) Peek() T

func (*PQueue[T]) Pop 

func (q *PQueue[T]) Pop() T

func (*PQueue[T]) Push 

func (q *PQueue[T]) Push(x *PQItem[T])

func (*PQueue[T]) Remove 

func (q *PQueue[T]) Remove(i int) T

func (*PQueue[T]) String 

func (q *PQueue[T]) String() string

type Pair 

type Pair[U any, V any] struct {
	Fst U
	Snd V
}

func MkPair 

func MkPair[U any, V any](u U, v V) Pair[U, V]

func (Pair[U, V]) Extract 

func (p Pair[U, V]) Extract() (U, V)

type RLine 

type RLine [2][2]*big.Rat

func (RLine) Intersect 

func (l RLine) Intersect(s RLine) ([2]*big.Rat, bool)

type SignedNum 

type SignedNum interface {
	constraints.Signed | constraints.Float
}

type UnionFind 

type UnionFind struct {
	// Union-find data structure with size for balancing
	Parent []int
	Size   []int
}

https://www.cs.princeton.edu/~rs/AlgsDS07/01UnionFind.pdf Could also define a Union-Find by "rank"="depth" Also called "Disjoint Set"

func NewUnionFind 

func NewUnionFind(n int) *UnionFind

func (*UnionFind) Copy 

func (uf *UnionFind) Copy() *UnionFind

func (*UnionFind) Extend 

func (uf *UnionFind) Extend()

func (*UnionFind) Find 

func (uf *UnionFind) Find(i int) int

func (*UnionFind) Merge 

func (uf *UnionFind) Merge(p, q int)

func (*UnionFind) SameRoot 

func (union *UnionFind) SameRoot(p, q int) bool

type Vect2 

type Vect2 [2]float64

func ScanVect2 

func ScanVect2(sc *bufio.Scanner) Vect2

func ScanVect2s 

func ScanVect2s(sc *bufio.Scanner, n int) []Vect2

func Vect2DOfPolar 

func Vect2DOfPolar(d, θ float64) Vect2

func (Vect2) Add 

func (v Vect2) Add(w [2]float64) Vect2

func (Vect2) Angle 

func (v Vect2) Angle() float64

Angle between vector and x-axis. result range is -π to π

func (Vect2) AngleAt 

func (p Vect2) AngleAt(q, r [2]float64) float64

AngleAt is angle between lines p.To(q) and p.To(r)

func (Vect2) AngleBetween 

func (v Vect2) AngleBetween(w [2]float64) float64

AngleBetween returns angle between vectors v and w at origin

func (Vect2) Dist 

func (v Vect2) Dist(w [2]float64) float64

func (Vect2) DistSquared 

func (v Vect2) DistSquared(q [2]float64) float64

func (Vect2) Dot 

func (v Vect2) Dot(w [2]float64) float64

Dot product (= "inner product")

func (Vect2) Mag 

func (v Vect2) Mag() float64

func (Vect2) MagSquared 

func (v Vect2) MagSquared() float64

func (Vect2) Normal 

func (v Vect2) Normal() Vect2

func (Vect2) Normalize 

func (v Vect2) Normalize() Vect2

func (Vect2) Orientation 

func (a Vect2) Orientation(b, c [2]float64) int

func (Vect2) Rotate 

func (v Vect2) Rotate(θ float64) Vect2

Rotate vector v around the origin by θ

func (Vect2) RotateAround 

func (p Vect2) RotateAround(q [2]float64, θ float64) Vect2

RotateAround rotates point q around point p by θ

func (Vect2) Scale 

func (v Vect2) Scale(λ float64) Vect2

func (Vect2) String 

func (v Vect2) String() string

func (Vect2) Subtract 

func (v Vect2) Subtract(w [2]float64) Vect2

func (Vect2) To 

func (p Vect2) To(q Vect2) Vect2

To(p,q) is vector from p to q

func (Vect2) X 

func (v Vect2) X() float64

func (Vect2) Y 

func (v Vect2) Y() float64

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.