use std::fmt;
use crate::error::{Error, Result};
use crate::p21::{Exchange, Instance};
pub struct Graph<'a> {
exchange: Exchange<'a>,
forward: Adjacency,
backward: Adjacency,
unresolved: Vec<(usize, u64)>,
}
struct Adjacency {
offsets: Vec<usize>,
targets: Vec<usize>,
}
impl<'a> Graph<'a> {
pub fn new(exchange: Exchange<'a>) -> Result<Self> {
let graph = Self::build(exchange);
match graph.unresolved.first() {
Some(&(node, to)) => Err(Error::UnresolvedReference {
from: graph.instance(node).id,
to,
}),
None => Ok(graph),
}
}
pub fn build(exchange: Exchange<'a>) -> Self {
let instances = exchange.instances();
let mut offsets = Vec::with_capacity(instances.len() + 1);
offsets.push(0);
let mut targets = Vec::new();
let mut unresolved = Vec::new();
let mut neighbours = Vec::new();
for (node, instance) in instances.iter().enumerate() {
neighbours.clear();
for id in exchange.references(instance) {
match exchange.position(id) {
Some(target) => neighbours.push(target),
None if exchange.is_external(id) => {}
None => unresolved.push((node, id)),
}
}
neighbours.sort_unstable();
neighbours.dedup();
targets.extend_from_slice(&neighbours);
offsets.push(targets.len());
}
let forward = Adjacency { offsets, targets };
let backward = forward.reversed();
Self {
exchange,
forward,
backward,
unresolved,
}
}
pub fn exchange(&self) -> &Exchange<'a> {
&self.exchange
}
pub fn len(&self) -> usize {
self.exchange.instances().len()
}
pub fn is_empty(&self) -> bool {
self.len() == 0
}
pub fn node(&self, id: u64) -> Option<usize> {
self.exchange.position(id)
}
pub fn instance(&self, node: usize) -> &Instance {
&self.exchange.instances()[node]
}
pub fn references(&self, node: usize) -> &[usize] {
self.forward.neighbours(node)
}
pub fn referenced_by(&self, node: usize) -> &[usize] {
self.backward.neighbours(node)
}
pub fn unresolved(&self) -> &[(usize, u64)] {
&self.unresolved
}
}
impl fmt::Debug for Graph<'_> {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
f.debug_struct("Graph")
.field("nodes", &self.len())
.field("edges", &self.forward.targets.len())
.field("unresolved", &self.unresolved.len())
.finish_non_exhaustive()
}
}
impl Adjacency {
fn neighbours(&self, node: usize) -> &[usize] {
&self.targets[self.offsets[node]..self.offsets[node + 1]]
}
fn reversed(&self) -> Self {
let nodes = self.offsets.len() - 1;
let mut offsets = vec![0; nodes + 1];
for &target in &self.targets {
offsets[target + 1] += 1;
}
let mut total = 0;
for offset in &mut offsets {
total += *offset;
*offset = total;
}
let mut next = offsets.clone();
let mut targets = vec![0; self.targets.len()];
for source in 0..nodes {
for &target in self.neighbours(source) {
targets[next[target]] = source;
next[target] += 1;
}
}
Self { offsets, targets }
}
}
#[cfg(test)]
mod tests {
use super::*;
use crate::p21::parse;
fn file_with(data: &str) -> String {
format!("ISO-10303-21;HEADER;FILE_SCHEMA(('X'));ENDSEC;DATA;{data}ENDSEC;END-ISO-10303-21;")
}
#[test]
fn forward_and_back_indices() {
let src = file_with("#1=A(#2,#3,#2);#2=B(#3);#3=C('see #1');#4=D((#3,#1));");
let graph = Graph::new(parse(src.as_bytes()).unwrap()).unwrap();
assert_eq!(graph.len(), 4);
assert_eq!(graph.references(0), [1, 2]);
assert_eq!(graph.references(1), [2]);
assert!(
graph.references(2).is_empty(),
"'#1' in a string is not a reference"
);
assert_eq!(graph.references(3), [0, 2]);
assert_eq!(graph.referenced_by(0), [3]);
assert_eq!(graph.referenced_by(2), [0, 1, 3]);
assert!(
graph.referenced_by(3).is_empty(),
"{:?}",
graph.referenced_by(3)
);
assert!(graph.unresolved().is_empty(), "{:?}", graph.unresolved());
}
#[test]
fn nodes_follow_file_order_not_ids() {
let src = file_with("#10=A(#5);#5=B();");
let graph = Graph::new(parse(src.as_bytes()).unwrap()).unwrap();
assert_eq!(graph.node(10), Some(0));
assert_eq!(graph.node(5), Some(1));
assert_eq!(graph.instance(1).id, 5);
assert_eq!(graph.references(0), [1]);
assert_eq!(graph.node(7), None);
}
#[test]
fn dangling_references() {
let src = file_with("#1=A(#2,#8);#2=B((#9));");
let err = Graph::new(parse(src.as_bytes()).unwrap()).unwrap_err();
assert!(matches!(err, Error::UnresolvedReference { from: 1, to: 8 }));
let graph = Graph::build(parse(src.as_bytes()).unwrap());
assert_eq!(graph.unresolved(), [(0, 8), (1, 9)]);
assert_eq!(graph.references(0), [1]);
assert!(graph.references(1).is_empty(), "{:?}", graph.references(1));
}
#[test]
fn empty_data_section() {
let src = file_with("");
let graph = Graph::new(parse(src.as_bytes()).unwrap()).unwrap();
assert!(graph.is_empty());
}
}