triblespace_paths/
automaton.rs1use std::collections::BTreeSet;
2use std::error::Error;
3use std::fmt;
4
5use triblespace_core::id::RawId;
6
7pub type StateId = u32;
9
10#[derive(Clone, Debug, Eq, PartialEq, Ord, PartialOrd)]
15pub enum Step {
16 Forward(RawId),
18 Reverse(RawId),
20 ForwardExcept(Vec<RawId>),
22 ReverseExcept(Vec<RawId>),
24}
25
26impl Step {
27 pub fn forward_any() -> Self {
29 Self::ForwardExcept(Vec::new())
30 }
31
32 pub fn reverse_any() -> Self {
34 Self::ReverseExcept(Vec::new())
35 }
36
37 fn canonicalize(&mut self) {
38 let excluded = match self {
39 Self::ForwardExcept(excluded) | Self::ReverseExcept(excluded) => excluded,
40 Self::Forward(_) | Self::Reverse(_) => return,
41 };
42 excluded.sort_unstable();
43 excluded.dedup();
44 }
45
46 pub(crate) fn matches(&self, attribute: &RawId) -> bool {
47 match self {
48 Self::Forward(expected) | Self::Reverse(expected) => expected == attribute,
49 Self::ForwardExcept(excluded) | Self::ReverseExcept(excluded) => {
50 excluded.binary_search(attribute).is_err()
51 }
52 }
53 }
54
55 pub(crate) fn is_reverse(&self) -> bool {
56 matches!(self, Self::Reverse(_) | Self::ReverseExcept(_))
57 }
58}
59
60#[derive(Clone, Debug, Eq, PartialEq, Ord, PartialOrd)]
62pub struct Transition {
63 pub from: StateId,
65 pub to: StateId,
67 pub step: Step,
69}
70
71impl Transition {
72 pub fn new(from: StateId, to: StateId, step: Step) -> Self {
74 Self { from, to, step }
75 }
76}
77
78#[derive(Clone, Debug, Eq, PartialEq)]
83pub struct Automaton {
84 state_count: StateId,
85 initial: BTreeSet<StateId>,
86 accepting: BTreeSet<StateId>,
87 transitions: Vec<Transition>,
88}
89
90#[derive(Clone, Debug, Eq, PartialEq)]
92pub enum AutomatonError {
93 NoStates,
95 NoInitialState,
97 StateOutOfRange {
99 state: StateId,
101 state_count: StateId,
103 },
104}
105
106impl fmt::Display for AutomatonError {
107 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
108 match self {
109 Self::NoStates => write!(f, "an automaton needs at least one state"),
110 Self::NoInitialState => write!(f, "an automaton needs an initial state"),
111 Self::StateOutOfRange { state, state_count } => {
112 write!(f, "automaton state {state} is outside 0..{state_count}")
113 }
114 }
115 }
116}
117
118impl Error for AutomatonError {}
119
120impl Automaton {
121 pub fn new(
123 state_count: StateId,
124 initial: impl IntoIterator<Item = StateId>,
125 accepting: impl IntoIterator<Item = StateId>,
126 transitions: impl IntoIterator<Item = Transition>,
127 ) -> Result<Self, AutomatonError> {
128 if state_count == 0 {
129 return Err(AutomatonError::NoStates);
130 }
131
132 let initial = initial.into_iter().collect::<BTreeSet<_>>();
133 if initial.is_empty() {
134 return Err(AutomatonError::NoInitialState);
135 }
136 let accepting = accepting.into_iter().collect::<BTreeSet<_>>();
137 let mut transitions = transitions.into_iter().collect::<Vec<_>>();
138
139 for state in initial.iter().chain(&accepting).copied().chain(
140 transitions
141 .iter()
142 .flat_map(|transition| [transition.from, transition.to]),
143 ) {
144 if state >= state_count {
145 return Err(AutomatonError::StateOutOfRange { state, state_count });
146 }
147 }
148
149 for transition in &mut transitions {
150 transition.step.canonicalize();
151 }
152 transitions.sort_unstable();
153 transitions.dedup();
154
155 Ok(Self {
156 state_count,
157 initial,
158 accepting,
159 transitions,
160 })
161 }
162
163 pub fn state_count(&self) -> StateId {
165 self.state_count
166 }
167
168 pub fn initial_states(&self) -> impl Iterator<Item = StateId> + '_ {
170 self.initial.iter().copied()
171 }
172
173 pub fn accepting_states(&self) -> impl Iterator<Item = StateId> + '_ {
175 self.accepting.iter().copied()
176 }
177
178 pub fn accepts_empty(&self) -> bool {
183 self.initial
184 .iter()
185 .any(|state| self.accepting.contains(state))
186 }
187
188 pub fn is_accepting(&self, state: StateId) -> bool {
190 self.accepting.contains(&state)
191 }
192
193 pub fn transitions(&self) -> &[Transition] {
195 &self.transitions
196 }
197}