finite_automata/
lib.rs

1use std::collections::BTreeSet as Set;
2
3#[macro_use]
4mod util;
5mod dfa;
6mod nfa;
7mod enfa;
8
9/// An index for a state in a finite automaton.
10#[derive(Clone, Copy, Debug, Eq, Ord, PartialEq, PartialOrd)]
11pub struct StateIndex {
12    inner: u128,
13}
14
15impl From<u128> for StateIndex {
16    /// Create a state index from the unsigned integer.
17    fn from(inner: u128) -> StateIndex {
18        StateIndex { inner }
19    }
20}
21
22/// An index for a transition in a finite automaton.
23#[derive(Clone, Copy, Debug, Eq, Ord, PartialEq, PartialOrd)]
24pub struct TransitionIndex {
25    inner: u128,
26}
27
28impl From<u128> for TransitionIndex {
29    /// Create a transition index from the unsigned integer.
30    fn from(inner: u128) -> TransitionIndex {
31        TransitionIndex { inner }
32    }
33}
34
35pub trait Subsume<F> {
36    /// Insert all the states and transitions of the finite automaton.
37    fn subsume(&mut self, fa: &F);
38}
39
40pub trait StatesContains<S> {
41    /// Return the state index of the state, if it exists.
42    fn states_contains(&self, state: &S) -> Option<StateIndex>;
43}
44
45pub trait StatesIndex<S> {
46    /// Get the state at the state index.
47    fn states_index(&self, state_index: StateIndex) -> &S;
48}
49
50pub trait StatesSlice<S> {
51    /// Convert the state indices to states.
52    fn states_slice<'a>(&'a self, state_indices: impl IntoIterator<Item = StateIndex> + 'a) -> Box<dyn Iterator<Item = &S> + 'a>;
53}
54
55/// Convert state index from `from` into a state index in the container, if the state exists.
56pub fn states_contains_from<S>(container: &impl StatesContains<S>, from: &impl StatesIndex<S>, state_index: StateIndex) -> Option<StateIndex> {
57    container.states_contains(from.states_index(state_index))
58}
59
60/// Convert state indices from `from` into a set of states and returns the state indices in the container, if all states exist.
61pub fn states_contains_all_from<'a, S>(container: &impl StatesContains<S>, from: &impl StatesSlice<S>, state_indices: impl IntoIterator<Item = StateIndex> + 'a) -> Option<Box<dyn Iterator<Item = StateIndex> + 'a>> {
62    from.states_slice(state_indices).map(|state| container.states_contains(state)).collect::<Option<Set<_>>>().map(|state_indices| Box::new(state_indices.into_iter()) as Box<dyn Iterator<Item = StateIndex>>)
63}
64
65/// Convert state indices from `from` into a set of states and returns the state index in the container, if the set of states exist.
66pub fn states_contains_closure_from<'a, S: Clone + Ord>(container: &impl StatesContains<Set<S>>, from: &impl StatesSlice<S>, state_indices: impl IntoIterator<Item = StateIndex> + 'a) -> Option<StateIndex> {
67    container.states_contains(&from.states_slice(state_indices).cloned().collect())
68}
69
70pub use crate::enfa::Enfa;
71pub use crate::nfa::Nfa;
72pub use crate::dfa::Dfa;
73
finite_automata/lib.rs

finite_automata/
lib.rs
