Functions — github.com/EbTech/rust-algorithms

hub / github.com/EbTech/rust-algorithms / functions

Functions212 in github.com/EbTech/rust-algorithms

⨍ Functions 212◇ Types & classes 33

↓ 43 callersMethodpush

(&mut self, (p, s): ArqView)

src/range_query/dynamic_arq.rs:99

↓ 32 callersMethodadd_edge

Adds a directed edge from u to v.

src/graph/mod.rs:77

↓ 27 callersMethodupdate

Applies the endomorphism f to all entries from l to r, inclusive. If l == r, the updates are eager. Otherwise, they are lazy. # Panics Panics if r >

src/range_query/static_arq.rs:83

↓ 16 callersMethodadd_edge

Adds an edge with specified directional capacities and cost per unit of flow. If only forward flow is allowed, rcap should be zero.

src/graph/flow.rs:29

↓ 11 callersMethodadj_list

Gets vertex u's adjacency list.

src/graph/mod.rs:100

↓ 11 callersMethodnum_v

Returns the number of vertices.

src/graph/mod.rs:67

↓ 10 callersMethodadd_undirected_edge

An undirected edge is two directed edges. If edges are added only via this funcion, the reverse of any edge e can be found at e^1.

src/graph/mod.rs:85

↓ 9 callersMethodclone

(&self)

src/range_query/dynamic_arq.rs:13

↓ 8 callersMethodrecip

(self)

src/math/num.rs:36

↓ 6 callersMethodnum_e

Returns the number of edges, double-counting undirected edges.

src/graph/mod.rs:72

↓ 5 callersMethodcall

Performs a lookup into the HashMap to see if the value has already been calculated. If it has, returns the value. If it has not, calls the function, s

src/caching.rs:58

↓ 5 callersMethodinsert

Inserts a word into the trie, and returns the index of its node.

src/string_proc.rs:21

↓ 4 callersMethodabs

(self)

src/math/num.rs:30

↓ 4 callersMethodadd_two_sat_clause

If we think of each even-numbered vertex as a variable, and its odd-numbered successor as its negation, then we can build the implication graph corres

src/graph/mod.rs:94

↓ 4 callersMethodapply

(&mut self, p: usize, f: &T::F, s: i64)

src/range_query/static_arq.rs:40

↓ 4 callersMethodbuild_from_slice

Builds a tree whose leaves are set to a given non-empty slice.

src/range_query/dynamic_arq.rs:69

↓ 4 callersFunctionconvolution

Given two polynomials (vectors) sum_i a[i] x^i and sum_i b[i] x^i, computes their product (convolution) c[k] = sum_(i+j=k) a[i]*b[j]. Uses complex FFT

src/math/fft.rs:168

↓ 4 callersFunctiondft_from_reals

From a slice of reals (f64 or i64), computes DFT of size at least desired_len

src/math/fft.rs:140

↓ 4 callersFunctionfirst_negative

An example of binary search to find the first position whose element is negative. In this case, we use RMQ to locate the leftmost negative element. To

src/range_query/static_arq.rs:143

↓ 4 callersFunctionmod_mul

(a: i64, b: i64, m: i64)

src/math/mod.rs:36

↓ 4 callersMethodpush_to

(&mut self, p: usize)

src/range_query/static_arq.rs:63

↓ 4 callersMethodrows

(&self)

src/math/num.rs:284

↓ 3 callersMethodapply

(&mut self, f: &T::F, size: i64)

src/range_query/dynamic_arq.rs:33

Finds a word in the trie, and returns the index of its node.

src/string_proc.rs:39

↓ 3 callersFunctionidft_to_reals

The inverse of dft_from_reals()

src/math/fft.rs:154

↓ 3 callersMethodlower

(&mut self, u: usize, val: usize)

src/graph/connectivity.rs:32

↓ 3 callersMethodnext

(&mut self)

src/math/fft.rs:19

↓ 3 callersFunctionpos_mod

TODO: deduplicate modular arithmetic code with num::Field

src/math/mod.rs:33

↓ 3 callersFunctionsolve

(scan: &mut Scanner<R>, out: &mut W)

src/scanner.rs:86

↓ 2 callersFunctionasserting_cmp

Ordering algorithms. A comparator on partially ordered elements, that panics if they are incomparable # Example ``` use contest_algorithms::order::a

src/order.rs:13

↓ 2 callersMethodbuild_from_identity

Lazily builds a tree initialized to the identity.

src/range_query/dynamic_arq.rs:63

↓ 2 callersMethodclone_node

(&mut self, p_orig: usize)

src/range_query/dynamic_arq.rs:121

↓ 2 callersMethoddinic

Dinic's algorithm to find the maximum flow from s to t where s != t. Generalizes the Hopcroft-Karp maximum bipartite matching algorithm. V^2E in gener

src/graph/flow.rs:45

↓ 2 callersFunctionextended_gcd

Finds (d, coef_a, coef_b) such that d = gcd(a, b) = a * coef_a + b * coef_b.

src/math/mod.rs:6

↓ 2 callersFunctionfast_gcd

Fast iterative version of Euclid's GCD algorithm

src/math/num.rs:8

↓ 2 callersMethodfind

Finds the set's representative. Do path compression along the way to make future queries faster.

src/graph/mod.rs:26

↓ 2 callersMethodinsert_left

(&mut self, pos: usize)

src/range_query/sqrt_decomp.rs:88

↓ 2 callersFunctionmerge_sorted

Stably merges two sorted and totally ordered collections into one

src/order.rs:34

↓ 2 callersMethodnext

Returns next edge and vertex in the depth-first traversal Refs: https://www.geeksforgeeks.org/iterative-depth-first-traversal/ https://en.wikipedia.or

src/graph/util.rs:91

↓ 2 callersMethodpow

Computes self^n in O(log n) time

src/math/num.rs:178

↓ 2 callersMethodpull

(&mut self, p: usize)

src/range_query/static_arq.rs:59

↓ 2 callersMethodpull

(&mut self, p: usize)

src/range_query/dynamic_arq.rs:114

↓ 2 callersMethodpull_from

(&mut self, mut p: usize)

src/range_query/static_arq.rs:70

↓ 2 callersMethodpush

(&mut self, p: usize)

src/range_query/static_arq.rs:51

↓ 2 callersMethodremove_left

(&mut self, pos: usize)

src/range_query/sqrt_decomp.rs:95

↓ 2 callersMethodtranspose

(&self)

src/math/num.rs:287

↓ 2 callersMethodvisit

(&mut self, u: usize)

src/graph/connectivity.rs:25

↓ 1 callersMethodabs_square

(self)

src/math/num.rs:115

↓ 1 callersMethodac_match

Aho-Corasick algorithm, sets @return[i] = node corresponding to longest prefix of some pattern matching a suffix of text[0..=i].

src/string_proc.rs:176

↓ 1 callersMethodbcc

(&mut self, data: &mut ConnectivityData, u: usize, par: usize)

src/graph/connectivity.rs:134

↓ 1 callersMethodcall_and_replace

Calls the function without performing a lookup and replaces the old return value with the new one, and returns it. Potentially useful if the function

src/caching.rs:68

↓ 1 callersMethodcmp

(&self, other: &Self)

src/math/num.rs:92

↓ 1 callersFunctiondfs

( graph: &Graph, u: usize, l: &mut [usize], r: &mut [usize], p: &mut [usize], time: &m

tests/codeforces343d.rs:42

↓ 1 callersMethoddijkstra

Single-source shortest paths on a directed graph with non-negative weights

src/graph/util.rs:43

↓ 1 callersMethoddinic_augment

Pushes a blocking flow that increases the residual's s-t distance.

src/graph/flow.rs:80

↓ 1 callersMethoddinic_search

Compute BFS distances to restrict attention to shortest path edges.

src/graph/flow.rs:63

↓ 1 callersMethodeval_unoptimized

Evaluates the function at x

src/order.rs:124

↓ 1 callersMethodevaluate

Evaluates the function at x with good amortized runtime

src/order.rs:135

↓ 1 callersMethodevaluate

Finds the maximum mx+b among all lines in the structure. O(log N) complexity.

src/li_chao.rs:78

↓ 1 callersMethodevaluate_impl

Because of the invariant established by add_line, we know that the best line for a given point is stored in one of the ancestors of its node. So we ac

src/li_chao.rs:61

↓ 1 callersMethodget_end_pos_and_pat_id

For each non-empty match, returns where in the text it ends, and the index of the corresponding pattern.

src/string_proc.rs:188

↓ 1 callersMethodinsert_right

(&mut self, pos: usize)

src/range_query/sqrt_decomp.rs:16

↓ 1 callersMethodis_cut_edge

In an undirected graph, determines whether e is a bridge

src/graph/connectivity.rs:186

↓ 1 callersMethodis_cut_vertex

In an undirected graph, determines whether u is an articulation vertex.

src/graph/connectivity.rs:175

↓ 1 callersFunctionis_prime

Assuming x >= 0, returns whether x is prime

src/math/mod.rs:68

↓ 1 callersFunctionis_strong_probable_prime

(n: i64, exp: u64, r: i64, a: i64)

src/math/mod.rs:53

↓ 1 callersMethodkmp_match

KMP algorithm, sets @return[i] = length of longest prefix of pattern matching a suffix of text[0..=i].

src/string_proc.rs:97

↓ 1 callersMethodmax_with

Replaces the represented function with the maximum of itself and a provided line

src/order.rs:102

↓ 1 callersMethodmax_with

Adds the line with slope m and intercept b. O(log N) complexity.

src/li_chao.rs:54

↓ 1 callersMethodmax_with_impl

Every node in the tree has the property that the line that maximizes its midpoint is found either in the node or one of its ancestors. When we visit

src/li_chao.rs:35

↓ 1 callersMethodmax_with_sorted

Similar to max_with but requires that (new_m, new_b) be the largest pair so far

src/order.rs:107

↓ 1 callersMethodmcf

Among all s-t maximum flows, finds one with minimum cost, assuming s != t and no negative-cost cycles. # Panics Panics if the flow or cost overflow

src/graph/flow.rs:128

↓ 1 callersMethodmcf_augment

Pushes flow along an augmenting path of minimum cost.

src/graph/flow.rs:181

↓ 1 callersMethodmcf_search

Maintains Johnson's potentials to prevent negative-cost residual edges. This allows running Dijkstra instead of the slower Bellman-Ford.

src/graph/flow.rs:158

↓ 1 callersMethodmerge

Merges the sets containing u and v into a single set containing their union. Returns true if u and v were previously in different sets.

src/graph/mod.rs:36

↓ 1 callersMethodmerge_equal_sized

Merges two balanced subtrees into a single tree with a 0-indexed view.

src/range_query/dynamic_arq.rs:87

↓ 1 callersMethodmin_spanning_tree

Kruskal's minimum spanning tree algorithm on an undirected graph.

src/graph/util.rs:30

↓ 1 callersFunctionmod_exp

(mut base: i64, mut exp: u64, m: i64)

src/math/mod.rs:39

↓ 1 callersMethodnext

Produces an outgoing edge and vertex.

src/graph/mod.rs:118

↓ 1 callersMethodnext_u64

(&mut self)

src/rng.rs:45

↓ 1 callersFunctionpalindromes

Manacher's algorithm for computing palindrome substrings in linear time. pal[2*i] = odd length of palindrome centred at text[i]. pal[2*i+1] = even len

src/string_proc.rs:294

↓ 1 callersMethodpartial_cmp

(&self, other: &Self)

src/math/num.rs:97

↓ 1 callersFunctionpollard_rho

(n: i64)

src/math/mod.rs:85

↓ 1 callersMethodprocess

After initializing self to a state corresponding to an empty interval, call this function to answer all your queries.

src/range_query/sqrt_decomp.rs:24

↓ 1 callersMethodquery

(&self, _: &Self::Q)

src/range_query/sqrt_decomp.rs:85

↓ 1 callersMethodquery

Returns the aggregate range query on all entries from l to r, inclusive. # Panics Panics if r >= size. Note that l > r is valid, meaning an empty ra

src/range_query/static_arq.rs:115

↓ 1 callersMethodremove_right

(&mut self, pos: usize)

src/range_query/sqrt_decomp.rs:19

↓ 1 callersFunctionscanner_from_file

(filename: &str)

src/scanner.rs:72

↓ 1 callersMethodscc

(&mut self, data: &mut ConnectivityData, u: usize)

src/graph/connectivity.rs:89

↓ 1 callersFunctionslice_lower_bound

Assuming slice is sorted and totally ordered, returns the minimum i for which slice[i] >= key, or slice.len() if no such i exists

src/order.rs:19

↓ 1 callersFunctionsolve

(scan: &mut Scanner<R>, out: &mut W)

tests/codeforces343d.rs:63

↓ 1 callersFunctionunsafe_solve

(scan: &mut UnsafeScanner<R>, out: &mut W)

src/scanner.rs:92

↓ 1 callersFunctionwriter_to_file

(&f: &Self::F, _: &Self::S, _: i64)

src/range_query/specs.rs:58

Assuming a != 0, finds smallest coef_b >= 0 such that a * coef_a + b * coef_b = c. # Panics Panics if a == 0.

src/math/mod.rs:20

Methodcompose

(&f: &Self::F, _: &Self::F)

src/range_query/specs.rs:55

Methodcompress

Returns Ok(i) if the coordinate q appears at index i Returns Err(i) if q appears between indices i-1 and i

src/order.rs:73

next →1–100 of 212, ranked by callers