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

Download history 3/week @ 2024-08-25 2/week @ 2024-09-01 32/week @ 2024-09-22 189/week @ 2024-09-29

221 downloads per month
Used in orchidlang

MIT license

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));

No runtime deps