use rustc_hash::FxHashSet;
use crate::monomial::MonomialIdeal;
use crate::quiver::{ArrowId, Quiver};
#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash, PartialOrd, Ord)]
pub enum Sign {
Plus,
Minus,
}
impl Sign {
const BOTH: [Sign; 2] = [Sign::Plus, Sign::Minus];
pub fn negated(self) -> Sign {
match self {
Sign::Plus => Sign::Minus,
Sign::Minus => Sign::Plus,
}
}
fn index(self) -> usize {
self as usize
}
}
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub(crate) enum Kind {
Permitted,
Forbidden,
}
impl Kind {
pub(crate) fn partner(self, sign: Sign) -> Sign {
match self {
Kind::Permitted => sign.negated(),
Kind::Forbidden => sign,
}
}
}
#[derive(Clone, Debug)]
pub(crate) struct Shape {
arrows: Vec<(u32, u32)>,
sigma: Vec<Sign>,
epsilon: Vec<Sign>,
outgoing: Vec<[Option<ArrowId>; 2]>,
incoming: Vec<[Option<ArrowId>; 2]>,
}
impl Shape {
pub(crate) fn empty(vertices: u32) -> Shape {
Shape {
arrows: Vec::new(),
sigma: Vec::new(),
epsilon: Vec::new(),
outgoing: vec![[None; 2]; vertices as usize],
incoming: vec![[None; 2]; vertices as usize],
}
}
pub(crate) fn solve(quiver: &Quiver, forbidden: &FxHashSet<(ArrowId, ArrowId)>) -> Shape {
let arrows = quiver.num_arrows();
let mut sigma = vec![Sign::Plus; arrows];
let mut epsilon = vec![Sign::Plus; arrows];
for vertex in 0..quiver.num_vertices() {
let outgoing = quiver.arrows_from(vertex);
for (&arrow, sign) in outgoing.iter().zip(Sign::BOTH) {
sigma[arrow.index()] = sign;
}
let incoming = quiver.arrows_to(vertex);
for (position, &arrow) in incoming.iter().enumerate() {
epsilon[arrow.index()] = match outgoing.first() {
Some(&next) if forbidden.contains(&(arrow, next)) => sigma[next.index()],
Some(&next) => sigma[next.index()].negated(),
None => Sign::BOTH[position],
};
}
}
let mut shape = Shape::empty(quiver.num_vertices());
for (index, &(source, target)) in quiver.arrows().iter().enumerate() {
shape.push(source, sigma[index], target, epsilon[index]);
}
shape
}
pub(crate) fn push(&mut self, source: u32, sigma: Sign, target: u32, epsilon: Sign) {
let arrow = ArrowId(self.arrows.len() as u32);
let out = &mut self.outgoing[source as usize][sigma.index()];
assert!(
out.is_none(),
"two arrows share an outgoing slot; library bug"
);
*out = Some(arrow);
let into = &mut self.incoming[target as usize][epsilon.index()];
assert!(
into.is_none(),
"two arrows share an incoming slot; library bug"
);
*into = Some(arrow);
self.arrows.push((source, target));
self.sigma.push(sigma);
self.epsilon.push(epsilon);
}
pub(crate) fn push_vertex(&mut self) -> u32 {
self.outgoing.push([None; 2]);
self.incoming.push([None; 2]);
self.outgoing.len() as u32 - 1
}
accessor_methods! {
pub(crate) vertices() -> u32 = |this| this.outgoing.len() as u32;
pub(crate) arrows() -> &[(u32, u32)] = |this| &this.arrows;
pub(crate) sigma(arrow: ArrowId) -> Sign = |this| this.sigma[arrow.index()];
pub(crate) epsilon(arrow: ArrowId) -> Sign = |this| this.epsilon[arrow.index()];
pub(crate) outgoing(vertex: u32, sign: Sign) -> Option<ArrowId> = |this| this.outgoing[vertex as usize][sign.index()];
pub(crate) incoming(vertex: u32, sign: Sign) -> Option<ArrowId> = |this| this.incoming[vertex as usize][sign.index()];
pub(crate) source(arrow: ArrowId) -> u32 = |this| this.arrows[arrow.index()].0;
pub(crate) target(arrow: ArrowId) -> u32 = |this| this.arrows[arrow.index()].1;
}
pub(crate) fn successor(&self, kind: Kind, arrow: ArrowId) -> Option<ArrowId> {
self.outgoing(self.target(arrow), kind.partner(self.epsilon(arrow)))
}
pub(crate) fn predecessor(&self, kind: Kind, arrow: ArrowId) -> Option<ArrowId> {
self.incoming(self.source(arrow), kind.partner(self.sigma(arrow)))
}
pub(crate) fn outgoing_sibling(&self, arrow: ArrowId) -> Option<ArrowId> {
self.outgoing(self.source(arrow), self.sigma(arrow).negated())
}
pub(crate) fn incoming_sibling(&self, arrow: ArrowId) -> Option<ArrowId> {
self.incoming(self.target(arrow), self.epsilon(arrow).negated())
}
pub(crate) fn relations(&self) -> Vec<(ArrowId, ArrowId)> {
(0..self.arrows.len() as u32)
.map(ArrowId)
.filter_map(|arrow| {
self.successor(Kind::Forbidden, arrow)
.map(|next| (arrow, next))
})
.collect()
}
pub(crate) fn monomial_ideal(&self) -> MonomialIdeal {
monomial_ideal(self.vertices(), &self.arrows, &self.relations())
}
}
pub(crate) fn monomial_ideal(
vertices: u32,
arrows: &[(u32, u32)],
relations: &[(ArrowId, ArrowId)],
) -> MonomialIdeal {
let quiver = Quiver::new(vertices, arrows).expect("slot endpoints are vertices");
let words = relations.iter().map(|&(b, c)| vec![b, c]).collect();
MonomialIdeal::new(quiver, words).expect("a relation joins an arrow to one at its target")
}