herring_automata/
dfa.rs

1use crate::{Dfa, Output, StateRef};
2use std::collections::{BTreeSet, HashMap};
3
4impl Dfa {
5    /// Hopcroft's algorithm
6    pub fn into_minimized(self) -> Self {
7        let mut accept_partitions = HashMap::<Output, Vec<StateRef>>::new();
8        for (state, output) in self.accepts.iter() {
9            if let Some(output) = output {
10                accept_partitions
11                    .entry(output.clone())
12                    .and_modify(|e| e.push(*state))
13                    .or_insert(vec![*state]);
14            }
15        }
16        let mut p = BTreeSet::new();
17        for (_, states) in accept_partitions {
18            p.insert(BTreeSet::from_iter(states));
19        }
20        let mut non_accept = BTreeSet::new();
21        for s in 0..self.states.len() {
22            if !self.accepts.contains_key(&StateRef(s)) {
23                non_accept.insert(StateRef(s));
24            }
25        }
26        if !non_accept.is_empty() {
27            p.insert(non_accept);
28        }
29        let mut w = p.clone();
30
31        while !w.is_empty() {
32            let a = w.pop_last().unwrap();
33            for b in u8::MIN..=u8::MAX {
34                let mut x = BTreeSet::new();
35                for (num, s) in self.states.iter().enumerate() {
36                    for t in s.transitions.iter() {
37                        let from = StateRef(num);
38                        if a.contains(&t.to) && t.when.contains(b) {
39                            x.insert(from);
40                        }
41                    }
42                }
43                if x.is_empty() {
44                    continue;
45                }
46                let mut replacements = Vec::with_capacity(p.len());
47                for y in p.iter() {
48                    let cut = x.intersection(y).copied().collect::<BTreeSet<_>>();
49                    let diff = y.difference(&x).copied().collect::<BTreeSet<_>>();
50                    if !cut.is_empty() && !diff.is_empty() {
51                        if w.contains(y) {
52                            w.remove(y);
53                            w.insert(cut.clone());
54                            w.insert(diff.clone());
55                        } else if cut.len() < diff.len() {
56                            w.insert(cut.clone());
57                        } else {
58                            w.insert(diff.clone());
59                        }
60                        replacements.push((y.clone(), (cut, diff)));
61                    }
62                }
63                for (y, (cut, diff)) in replacements.into_iter() {
64                    p.remove(&y);
65                    p.insert(cut);
66                    p.insert(diff);
67                }
68            }
69        }
70
71        let mut automaton = Dfa::new();
72        let mut new_states = HashMap::new();
73        for partition in p.iter() {
74            let state = if partition.contains(&self.start) {
75                automaton.start
76            } else {
77                automaton.add()
78            };
79            for s in partition {
80                new_states.insert(s, state);
81            }
82        }
83        for partition in p.iter() {
84            for s in partition {
85                let state = new_states[&s];
86                if let Some(tok) = self.accepts.get(s) {
87                    let _ = automaton.set_accept_output(state, tok.clone());
88                }
89                for t in self.states[s.0].transitions.iter() {
90                    let to = new_states[&t.to];
91                    automaton.add_transition(state, t.when.clone(), to);
92                }
93            }
94        }
95        automaton
96    }
97}
herring_automata/dfa.rs

herring_automata/
dfa.rs
