use std::collections::BTreeSet;
use std::error::Error;
use std::fmt;
use triblespace_core::id::RawId;
use triblespace_core::inline::encodings::UnknownInline;
use triblespace_core::inline::RawInline;
use triblespace_core::trible::Trible;
use crate::{Automaton, StateId};
#[derive(Clone, Copy, Debug, Eq, PartialEq, Ord, PartialOrd)]
pub struct GraphEdge {
pub source: RawInline,
pub attribute: RawId,
pub target: RawInline,
}
impl From<&Trible> for GraphEdge {
fn from(trible: &Trible) -> Self {
Self {
source: RawInline::from(*trible.e()),
attribute: RawId::from(*trible.a()),
target: trible.v::<UnknownInline>().raw,
}
}
}
impl From<Trible> for GraphEdge {
fn from(trible: Trible) -> Self {
Self::from(&trible)
}
}
#[derive(Clone, Copy, Debug, Eq, PartialEq, Ord, PartialOrd)]
struct ProductNode {
vertex: RawInline,
state: StateId,
}
#[derive(Clone, Copy, Debug, Eq, PartialEq, Ord, PartialOrd)]
struct ProductArc {
source: ProductNode,
target: ProductNode,
}
#[derive(Clone, Debug, Eq, PartialEq)]
pub struct PathSummary {
pub(crate) automaton: Automaton,
pub(crate) vertices: Vec<RawInline>,
arcs: Vec<ProductArc>,
}
#[derive(Clone, Debug, Eq, PartialEq)]
pub enum PathError {
EmptyInput,
DifferentAutomata,
TooManyVertices {
count: usize,
},
ProductCarrierTooLarge {
vertices: usize,
states: StateId,
},
CapacityOverflow,
}
impl fmt::Display for PathError {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
match self {
Self::EmptyInput => write!(f, "cannot combine an empty path-summary list"),
Self::DifferentAutomata => write!(f, "path summaries use different automata"),
Self::TooManyVertices { count } => {
write!(f, "{count} path vertices do not fit in u32 ordinals")
}
Self::ProductCarrierTooLarge { vertices, states } => write!(
f,
"the {vertices} by {states} product carrier does not fit in u32 ordinals"
),
Self::CapacityOverflow => write!(f, "path-index allocation dimensions overflow usize"),
}
}
}
impl Error for PathError {}
impl PathSummary {
pub(crate) fn from_canonical_ordinals(
automaton: Automaton,
vertices: Vec<RawInline>,
arcs: Vec<(u32, u32)>,
) -> Result<Self, PathError> {
let state_count = automaton.state_count();
let product_count = vertices
.len()
.checked_mul(state_count as usize)
.ok_or(PathError::CapacityOverflow)?;
let mut product_arcs = Vec::with_capacity(arcs.len());
for (source, target) in arcs {
if source as usize >= product_count || target as usize >= product_count {
return Err(PathError::ProductCarrierTooLarge {
vertices: vertices.len(),
states: state_count,
});
}
product_arcs.push(ProductArc {
source: ProductNode {
vertex: vertices[source as usize / state_count as usize],
state: source % state_count,
},
target: ProductNode {
vertex: vertices[target as usize / state_count as usize],
state: target % state_count,
},
});
}
Ok(Self {
automaton,
vertices,
arcs: product_arcs,
})
}
pub fn from_edges(automaton: Automaton, edges: impl IntoIterator<Item = GraphEdge>) -> Self {
let edges = edges.into_iter().collect::<BTreeSet<_>>();
let mut vertices = if automaton.accepts_empty() {
edges
.iter()
.flat_map(|edge| [edge.source, edge.target])
.collect::<BTreeSet<_>>()
} else {
BTreeSet::new()
};
let mut arcs = BTreeSet::new();
for edge in edges {
for transition in automaton.transitions() {
if !transition.step.matches(&edge.attribute) {
continue;
}
let (source, target) = if transition.step.is_reverse() {
(edge.target, edge.source)
} else {
(edge.source, edge.target)
};
vertices.insert(source);
vertices.insert(target);
arcs.insert(ProductArc {
source: ProductNode {
vertex: source,
state: transition.from,
},
target: ProductNode {
vertex: target,
state: transition.to,
},
});
}
}
Self {
automaton,
vertices: vertices.into_iter().collect(),
arcs: arcs.into_iter().collect(),
}
}
pub fn from_tribles<'a>(
automaton: Automaton,
tribles: impl IntoIterator<Item = &'a Trible>,
) -> Self {
Self::from_edges(automaton, tribles.into_iter().map(GraphEdge::from))
}
pub fn automaton(&self) -> &Automaton {
&self.automaton
}
pub fn vertices(&self) -> &[RawInline] {
&self.vertices
}
pub fn direct_arc_count(&self) -> usize {
self.arcs.len()
}
pub fn merge(&self, other: &Self) -> Result<Self, PathError> {
Self::merge_all([self, other])
}
pub fn merge_all<'a>(summaries: impl IntoIterator<Item = &'a Self>) -> Result<Self, PathError> {
let summaries = summaries.into_iter().collect::<Vec<_>>();
let Some(first) = summaries.first() else {
return Err(PathError::EmptyInput);
};
if summaries
.iter()
.any(|summary| summary.automaton != first.automaton)
{
return Err(PathError::DifferentAutomata);
}
let vertices = summaries
.iter()
.flat_map(|summary| summary.vertices.iter().copied())
.collect::<BTreeSet<_>>()
.into_iter()
.collect();
let arcs = summaries
.iter()
.flat_map(|summary| summary.arcs.iter().copied())
.collect::<BTreeSet<_>>()
.into_iter()
.collect();
Ok(Self {
automaton: first.automaton.clone(),
vertices,
arcs,
})
}
pub(crate) fn ordinal_arcs(&self) -> impl Iterator<Item = (u32, u32)> + '_ {
self.ordinal_arcs_in(&self.vertices)
}
pub(crate) fn active_vertices(&self) -> Vec<RawInline> {
self.arcs
.iter()
.flat_map(|arc| [arc.source.vertex, arc.target.vertex])
.collect::<BTreeSet<_>>()
.into_iter()
.collect()
}
pub(crate) fn has_canonical_domain(&self) -> bool {
self.automaton.accepts_empty() || self.vertices == self.active_vertices()
}
pub(crate) fn ordinal_arcs_in<'a>(
&'a self,
vertices: &'a [RawInline],
) -> impl Iterator<Item = (u32, u32)> + 'a {
let states = self.automaton.state_count();
self.arcs.iter().map(move |arc| {
let source_vertex = vertices
.binary_search(&arc.source.vertex)
.expect("summary arc source belongs to the requested product carrier")
as u32;
let target_vertex = vertices
.binary_search(&arc.target.vertex)
.expect("summary arc target belongs to the requested product carrier")
as u32;
(
source_vertex * states + arc.source.state,
target_vertex * states + arc.target.state,
)
})
}
}