use crate::quiver::ArrowId;
use super::shape::{Kind, Shape, Sign};
#[derive(Clone, Debug, PartialEq, Eq, Hash)]
pub struct GentleThread {
start: u32,
end: u32,
arrows: Vec<ArrowId>,
sigma: Sign,
epsilon: Sign,
}
impl GentleThread {
accessor_methods! {
pub start() -> u32 = |this| this.start;
pub end() -> u32 = |this| this.end;
pub arrows() -> &[ArrowId] = |this| &this.arrows;
pub length() -> usize = |this| this.arrows.len();
pub is_trivial() -> bool = |this| this.arrows.is_empty();
pub sigma() -> Sign = |this| this.sigma;
pub epsilon() -> Sign = |this| this.epsilon;
}
}
#[derive(Clone, Debug)]
pub(crate) struct Threads {
pub(crate) permitted: Vec<GentleThread>,
pub(crate) forbidden: Vec<GentleThread>,
pub(crate) cycles: Vec<Vec<ArrowId>>,
}
impl Threads {
pub(crate) fn new(shape: &Shape) -> Threads {
let forbidden = threads_of(shape, Kind::Forbidden);
let cycles = full_relation_cycles(shape, &forbidden);
Threads {
permitted: threads_of(shape, Kind::Permitted),
forbidden,
cycles,
}
}
}
fn threads_of(shape: &Shape, kind: Kind) -> Vec<GentleThread> {
let mut threads = Vec::new();
for vertex in 0..shape.vertices() {
for sign in [Sign::Plus, Sign::Minus] {
let partner = kind.partner(sign);
if shape.incoming(vertex, partner).is_some() {
continue;
}
threads.push(match shape.outgoing(vertex, sign) {
Some(first) => follow(shape, kind, first),
None => GentleThread {
start: vertex,
end: vertex,
arrows: Vec::new(),
sigma: sign,
epsilon: partner,
},
});
}
}
threads
}
fn follow(shape: &Shape, kind: Kind, first: ArrowId) -> GentleThread {
let mut arrows = vec![first];
let mut last = first;
while let Some(next) = shape.successor(kind, last) {
assert!(
arrows.len() < shape.arrows().len(),
"a {kind:?} thread repeats an arrow; library bug"
);
arrows.push(next);
last = next;
}
GentleThread {
start: shape.source(first),
end: shape.target(last),
arrows,
sigma: shape.sigma(first),
epsilon: shape.epsilon(last),
}
}
fn full_relation_cycles(shape: &Shape, forbidden: &[GentleThread]) -> Vec<Vec<ArrowId>> {
let mut used = vec![false; shape.arrows().len()];
for arrow in forbidden.iter().flat_map(GentleThread::arrows) {
used[arrow.index()] = true;
}
let mut cycles = Vec::new();
for first in 0..used.len() {
if used[first] {
continue;
}
let mut cycle = Vec::new();
let mut arrow = ArrowId(first as u32);
while !used[arrow.index()] {
used[arrow.index()] = true;
cycle.push(arrow);
arrow = shape
.successor(Kind::Forbidden, arrow)
.expect("an arrow outside every open forbidden thread lies on a cycle");
}
cycles.push(cycle);
}
cycles
}