Lib.rs

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