use std::collections::BTreeSet;
use std::error::Error;
use std::fmt;
use triblespace_core::id::RawId;
pub type StateId = u32;
#[derive(Clone, Debug, Eq, PartialEq, Ord, PartialOrd)]
pub enum Step {
Forward(RawId),
Reverse(RawId),
ForwardExcept(Vec<RawId>),
ReverseExcept(Vec<RawId>),
}
impl Step {
pub fn forward_any() -> Self {
Self::ForwardExcept(Vec::new())
}
pub fn reverse_any() -> Self {
Self::ReverseExcept(Vec::new())
}
fn canonicalize(&mut self) {
let excluded = match self {
Self::ForwardExcept(excluded) | Self::ReverseExcept(excluded) => excluded,
Self::Forward(_) | Self::Reverse(_) => return,
};
excluded.sort_unstable();
excluded.dedup();
}
pub(crate) fn matches(&self, attribute: &RawId) -> bool {
match self {
Self::Forward(expected) | Self::Reverse(expected) => expected == attribute,
Self::ForwardExcept(excluded) | Self::ReverseExcept(excluded) => {
excluded.binary_search(attribute).is_err()
}
}
}
pub(crate) fn is_reverse(&self) -> bool {
matches!(self, Self::Reverse(_) | Self::ReverseExcept(_))
}
}
#[derive(Clone, Debug, Eq, PartialEq, Ord, PartialOrd)]
pub struct Transition {
pub from: StateId,
pub to: StateId,
pub step: Step,
}
impl Transition {
pub fn new(from: StateId, to: StateId, step: Step) -> Self {
Self { from, to, step }
}
}
#[derive(Clone, Debug, Eq, PartialEq)]
pub struct Automaton {
state_count: StateId,
initial: BTreeSet<StateId>,
accepting: BTreeSet<StateId>,
transitions: Vec<Transition>,
}
#[derive(Clone, Debug, Eq, PartialEq)]
pub enum AutomatonError {
NoStates,
NoInitialState,
StateOutOfRange {
state: StateId,
state_count: StateId,
},
}
impl fmt::Display for AutomatonError {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
match self {
Self::NoStates => write!(f, "an automaton needs at least one state"),
Self::NoInitialState => write!(f, "an automaton needs an initial state"),
Self::StateOutOfRange { state, state_count } => {
write!(f, "automaton state {state} is outside 0..{state_count}")
}
}
}
}
impl Error for AutomatonError {}
impl Automaton {
pub fn new(
state_count: StateId,
initial: impl IntoIterator<Item = StateId>,
accepting: impl IntoIterator<Item = StateId>,
transitions: impl IntoIterator<Item = Transition>,
) -> Result<Self, AutomatonError> {
if state_count == 0 {
return Err(AutomatonError::NoStates);
}
let initial = initial.into_iter().collect::<BTreeSet<_>>();
if initial.is_empty() {
return Err(AutomatonError::NoInitialState);
}
let accepting = accepting.into_iter().collect::<BTreeSet<_>>();
let mut transitions = transitions.into_iter().collect::<Vec<_>>();
for state in initial.iter().chain(&accepting).copied().chain(
transitions
.iter()
.flat_map(|transition| [transition.from, transition.to]),
) {
if state >= state_count {
return Err(AutomatonError::StateOutOfRange { state, state_count });
}
}
for transition in &mut transitions {
transition.step.canonicalize();
}
transitions.sort_unstable();
transitions.dedup();
Ok(Self {
state_count,
initial,
accepting,
transitions,
})
}
pub fn state_count(&self) -> StateId {
self.state_count
}
pub fn initial_states(&self) -> impl Iterator<Item = StateId> + '_ {
self.initial.iter().copied()
}
pub fn accepting_states(&self) -> impl Iterator<Item = StateId> + '_ {
self.accepting.iter().copied()
}
pub fn accepts_empty(&self) -> bool {
self.initial
.iter()
.any(|state| self.accepting.contains(state))
}
pub fn is_accepting(&self, state: StateId) -> bool {
self.accepting.contains(&state)
}
pub fn transitions(&self) -> &[Transition] {
&self.transitions
}
}