dandy 0.1.10

Implementation of DFAs, NFAs and regular expressions together with a file format
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109

use crate::nfa::{Nfa, NfaState};
use std::collections::{HashMap, HashSet};
use std::iter;
use std::rc::Rc;

#[derive(Clone, Debug)]
pub struct NfaEvaluator<'a> {
    nfa: &'a Nfa,
    rev_map: Rc<HashMap<&'a str, usize>>,
    current_states: HashSet<usize>,
    unknown_elem_seen: bool,
}

impl<'a> NfaEvaluator<'a> {
    pub fn is_accepting(&self) -> bool {
        if self.unknown_elem_seen {
            false
        } else {
            self.current_states().iter().any(|s| s.accepting)
        }
    }

    pub fn current_states(&self) -> Vec<&NfaState> {
        self.current_states
            .iter()
            .map(|&s| &self.nfa.states[s])
            .collect()
    }

    pub fn current_states_idx(&self) -> &HashSet<usize> {
        &self.current_states
    }

    pub fn step_all(&self) -> Vec<NfaEvaluator<'a>> {
        iter::repeat(self.clone())
            .zip(self.nfa.alphabet())
            .map(|(mut eval, elem)| {
                eval.step(elem);
                eval
            })
            .collect()
    }

    pub fn step(&mut self, elem: &str) -> Option<()> {
        match self.rev_map.get(elem) {
            None => {
                self.unknown_elem_seen = true;
                None
            }
            Some(&idx) => {
                self.current_states = self
                    .current_states
                    .iter()
                    .flat_map(|&state| &self.nfa.states[state].transitions[idx])
                    .copied()
                    .collect();
                self.include_closure();
                Some(())
            }
        }
    }

    pub fn step_multiple(&mut self, elems: &[&str]) -> Option<()> {
        match elems.iter().try_for_each(|e| self.step(e)) {
            None => {
                self.unknown_elem_seen = true;
                None
            }
            Some(_) => Some(())
        }
    }

    fn include_closure(&mut self) {
        let mut updated = true;
        let mut to_push = HashSet::new();
        while updated {
            updated = false;
            for state in self.current_states.iter() {
                for epsilon_state in self.nfa.states[*state].epsilon_transitions.iter() {
                    if !self.current_states.contains(epsilon_state) {
                        updated = true;
                        to_push.insert(epsilon_state);
                    }
                }
            }
            self.current_states.extend(to_push.drain());
        }
    }
}

impl<'a> From<&'a Nfa> for NfaEvaluator<'a> {
    fn from(value: &'a Nfa) -> Self {
        let map = value
            .alphabet
            .iter()
            .enumerate()
            .map(|(idx, c)| (c as &str, idx))
            .collect();
        let mut evaluator = Self {
            nfa: value,
            rev_map: Rc::new(map),
            current_states: HashSet::new(),
            unknown_elem_seen: false,
        };
        evaluator.current_states.insert(value.initial_state);
        evaluator.include_closure();
        evaluator
    }
}