4 stable releases
new 1.1.1 | Oct 1, 2024 |
---|---|
1.1.0 | Nov 15, 2023 |
1.0.1 | Oct 31, 2023 |
#6 in #iterable
221 downloads per month
Used in orchidlang
10KB
167 lines
A linked list on the stack to avoid heap allocations in recursive algorithms
use substack::Substack;
/// Walk a disjoint set and find the representative of an element, or return None if the
/// set contains a loop
fn find_value(alias_map: &[usize], idx: usize, prev: Substack<usize>) -> Option<usize> {
match () {
() if alias_map[idx] == idx => Some(idx),
() if prev.iter().any(|i| *i == idx) => None,
() => find_value(alias_map, alias_map[idx], prev.push(idx)),
}
}
const map: &[usize] = &[2, 4, 1, 5, 1, 5];
assert_eq!(find_value(map, 0, Substack::Bottom), None);
assert_eq!(find_value(map, 3, Substack::Bottom), Some(5));