algo_utils

package
v0.10.0 Latest Latest
Warning

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

Go to latest
Published: Apr 22, 2024 License: Apache-2.0 Imports: 1 Imported by: 9

Documentation

Index

Constants

This section is empty.

Variables

This section is empty.

Functions

func BinarySearch

func BinarySearch(slice []int, toFind int) int

BinarySearch looks for toFind in a sorted slice, and returns the index at which it either is or would be were it to be inserted.

func BinarySearchFunc

func BinarySearchFunc(eval func(int) int, end int, toFind int) int

BinarySearchFunc looks for toFind in an increasing function of domain 0 ... (end-1), and returns the index at which it either is or would be were it to be inserted.

func InvertPermutation

func InvertPermutation(permutation []int) []int

InvertPermutation input permutation must contain exactly 0, ..., len(permutation)-1

func Map

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

func MapAt

func MapAt[K comparable, V any](mp map[K]V) func(K) V

func MapRange

func MapRange[S any](begin, end int, f func(int) S) []S

func Permute

func Permute[T any](slice []T, permutation []int)

Permute operates in-place but is not thread-safe; it uses the permutation for scratching permutation[i] signifies which index slice[i] is going to

func SliceAt

func SliceAt[T any](slice []T) func(int) T

func SlicePtrAt

func SlicePtrAt[T any](slice []T) func(int) *T

func TopologicalSort

func TopologicalSort(inputs [][]int) (sorted []int, uniqueOutputs [][]int)

TopologicalSort takes a list of lists of dependencies and proposes a sorting of the lists in order of dependence. Such that for any wire, any one it depends on occurs before it. It tries to stick to the input order as much as possible. An already sorted list will remain unchanged. As a bonus, it returns for each list its "unique" outputs. That is, a list of its outputs with no duplicates. Worst-case inefficient O(n^2), but that probably won't matter since the circuits are small. Furthermore, it is efficient with already-close-to-sorted lists, which are the expected input. If performance was bad, consider using a heap for finding the value "leastReady". WARNING: Due to the current implementation of intSet, it is ALWAYS O(n^2).

Types

This section is empty.

Jump to

Keyboard shortcuts

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