rusty_alto/combinators/
determinized.rs

1use crate::{BottomUpTa, DetBottomUpTa, Symbol, combinators::product::product_step_sets};
2use std::collections::BTreeSet;
3
4/// Lazy subset construction for a nondeterministic automaton.
5///
6/// `Determinized(a)` has states that are sets of `a`'s states. A deterministic
7/// transition computes all possible underlying transitions and packages the
8/// result as one set.
9///
10/// This generic version uses [`std::collections::BTreeSet`], so it favors
11/// clarity and broad compatibility over raw speed. It is most useful for small
12/// examples, tests, and as a baseline for denser bitset-based variants.
13#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
14pub struct Determinized<A>(pub A);
15
16impl<A> BottomUpTa for Determinized<A>
17where
18    A: BottomUpTa,
19    A::State: Ord,
20{
21    type State = BTreeSet<A::State>;
22
23    fn step(&self, f: Symbol, children: &[Self::State], out: &mut dyn FnMut(Self::State)) {
24        let result = deterministic_result(&self.0, f, children);
25        if !result.is_empty() {
26            out(result);
27        }
28    }
29
30    fn is_accepting(&self, qs: &Self::State) -> bool {
31        qs.iter().any(|q| self.0.is_accepting(q))
32    }
33}
34
35impl<A> DetBottomUpTa for Determinized<A>
36where
37    A: BottomUpTa,
38    A::State: Ord,
39{
40    fn step_det(&self, f: Symbol, children: &[Self::State]) -> Option<Self::State> {
41        let result = deterministic_result(&self.0, f, children);
42        (!result.is_empty()).then_some(result)
43    }
44}
45
46fn deterministic_result<A>(
47    automaton: &A,
48    f: Symbol,
49    children: &[BTreeSet<A::State>],
50) -> BTreeSet<A::State>
51where
52    A: BottomUpTa,
53    A::State: Ord,
54{
55    let pools: Vec<Vec<A::State>> = children
56        .iter()
57        .map(|set| set.iter().cloned().collect())
58        .collect();
59    let mut result = BTreeSet::new();
60    product_step_sets(&pools, |tuple| {
61        automaton.step(f, tuple, &mut |q| {
62            result.insert(q);
63        });
64    });
65    result
66}
67
68#[cfg(test)]
69mod tests {
70    use super::*;
71    use crate::{ExplicitBuilder, Symbol};
72
73    #[test]
74    fn determinizes_nullary_nondeterminism() {
75        let mut b = ExplicitBuilder::new();
76        let q0 = b.new_state();
77        let q1 = b.new_state();
78        b.add_rule(Symbol(0), vec![], q0);
79        b.add_rule(Symbol(0), vec![], q1);
80        b.add_accepting(q1);
81        let det = Determinized(b.build());
82        let state = det.step_det(Symbol(0), &[]).unwrap();
83        assert_eq!(state.len(), 2);
84        assert!(det.is_accepting(&state));
85    }
86}
rusty_alto/combinators/determinized.rs

rusty_alto/combinators/
determinized.rs
