Crate algorithms_lib

Expand description

Algorithms Library for Rust

A comprehensive, zero-dependency collection of common algorithms across sorting, searching, graphs, dynamic programming, strings, greedy, and divide-and-conquer.

§Conventions

Fallible operations return Result<T, Error>; lookups that miss return Err(Error::NotFound) rather than a sentinel index.
*_search functions on strings report byte offsets, not char indices.
Most sorts take &[T] and return Vec<T>; *_in_place variants sort &mut [T] without returning an allocation.

§Example

use algorithms_lib::{quick_sort, binary_search};

let sorted = quick_sort(&[3, 1, 4, 1, 5]);
assert_eq!(sorted, vec![1, 1, 3, 4, 5]);
assert_eq!(binary_search(&sorted, &4), Ok(3));

Structs§

Edge: Weighted edge for graph algorithms.
MSTEdge: An undirected, weighted edge for minimum spanning tree algorithms.
PriorityQueue: A min-priority queue.
UnionFind: Disjoint-set union–find with union by rank and path compression.

Enums§

EditOp: One step in an edit-distance script.
Error: Errors that can be returned by algorithms in this crate.

Functions§

a_star: A* shortest path.
activity_selection: Maximum compatible activity indices.
bellman_ford: Bellman-Ford shortest paths with negative cycle detection.
bfs: Breadth-first search.
binary_search: Binary search.
binary_search_on_answer: Binary search on answer for monotone predicates.
boyer_moore_search: Boyer-Moore pattern matching with the bad-character and good-suffix rules.
count_inversions: Inversion count.
dfs: Depth-first search.
dijkstra: Dijkstra’s shortest paths.
edit_distance: Levenshtein distance.
edit_distance_reconstruction: Levenshtein distance and one optimal edit script.
fast_power: Exponentiation by squaring. Returns Err(Error::InvalidInput) when base is zero and exponent is negative. By convention, 0^0 returns 1.0.
floyd_warshall: Floyd–Warshall all-pairs shortest paths.
fractional_knapsack: Fractional knapsack maximum value.
gcd: Greatest common divisor.
has_cycle: Returns whether the directed graph contains a cycle.
heap_sort: Binary max-heap sort.
heap_sort_in_place: Sorts items in place using a binary max-heap. True in-place sort: no auxiliary buffer proportional to items is allocated.
huffman_coding: Huffman coding.
huffman_decode: Decode a Huffman bit string using a code table.
huffman_encode: Encode a sequence of symbols using a Huffman code table.
interpolation_search: Interpolation search for numeric data.
jump_search: Jump search.
kmp_search: Knuth-Morris-Pratt pattern matching.
knapsack_01: 0/1 knapsack.
lcm: Least common multiple.
longest_common_subsequence: Longest common subsequence length.
longest_common_subsequence_reconstruction: Longest common subsequence length and one actual subsequence.
max_subarray: Maximum subarray sum.
merge_sort: Stable merge sort.
merge_sort_in_place: Sorts items in place using stable merge sort.
minimum_spanning_tree: Kruskal’s minimum spanning tree (or forest) algorithm.
modular_fast_power: Modular exponentiation by squaring: (base^exponent) % mod.
native_sort: Standard-library sort wrapper.
native_sort_in_place: Sorts items in place using the standard library sort (slice::sort).
quick_select: Returns the k-th smallest element (0-indexed) of items.
quick_sort: Quick sort. Returns a new sorted Vec; see quick_sort_in_place to sort a mutable slice without allocating the result.
quick_sort_in_place: Sorts items in place using quick sort’s partitioning result.
rabin_karp_search: Rolling-hash pattern matching.
radix_sort: LSD radix sort for non-negative integers.
sieve_of_eratosthenes: Sieve of Eratosthenes. Returns all prime numbers <= n.
strongly_connected_components: Kosaraju’s strongly connected components algorithm.
topological_sort: Topological sort using Kahn’s algorithm.

Crate algorithms_lib

Crate algorithms_lib Copy item path

§Conventions

§Example

Structs§

Enums§

Functions§

Crate algorithms_lib