use super::aag::AagFunction;
use super::surface::RibbonGraph;
#[derive(Clone, Debug, PartialEq, Eq, Hash, PartialOrd, Ord)]
pub struct GentleDerivedInvariant {
aag: AagFunction,
genus: usize,
class: WindingClass,
}
#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash, PartialOrd, Ord)]
pub enum WindingClass {
Planar,
Gcd(u64),
Odd,
Even,
Arf(u8),
}
impl GentleDerivedInvariant {
pub(super) fn new(
aag: AagFunction,
genus: usize,
graph: &RibbonGraph,
) -> GentleDerivedInvariant {
let cycles = graph.fundamental_cycles();
let windings: Vec<i64> = cycles.iter().map(|cycle| graph.winding(cycle)).collect();
let pairing = graph.pairing(&cycles);
let boundary: Vec<i64> = aag
.pairs()
.iter()
.map(|&(n, m)| n as i64 - m as i64)
.collect();
let reduction = Reduction::new(&pairing, &windings);
assert_eq!(
reduction.pairs,
genus,
"the intersection pairing has rank {} mod 2, not twice the genus {genus}; library bug",
2 * reduction.pairs
);
let class = match genus {
0 => WindingClass::Planar,
1 => WindingClass::Gcd(torus_gcd(&boundary, &windings, &pairing)),
_ => higher_class(&boundary, &windings, &reduction),
};
GentleDerivedInvariant { aag, genus, class }
}
accessor_methods! {
pub aag_function() -> &AagFunction = |this| &this.aag;
pub genus() -> usize = |this| this.genus;
pub winding_class() -> WindingClass = |this| this.class;
}
}
impl std::fmt::Display for GentleDerivedInvariant {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
write!(f, "{}, genus {}, {}", self.aag, self.genus, self.class)
}
}
impl std::fmt::Display for WindingClass {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
match self {
WindingClass::Planar => f.write_str("planar"),
WindingClass::Gcd(value) => write!(f, "gcd {value}"),
WindingClass::Odd => f.write_str("odd"),
WindingClass::Even => f.write_str("even"),
WindingClass::Arf(value) => write!(f, "arf {value}"),
}
}
}
fn torus_gcd(boundary: &[i64], windings: &[i64], pairing: &[Vec<i64>]) -> u64 {
let shifted = boundary.iter().fold(0, |acc, &w| gcd(acc, w + 2));
let mut total = shifted;
for (winding, row) in windings.iter().zip(pairing) {
if row.iter().any(|&entry| entry != 0) {
total = gcd(total, *winding);
} else {
assert!(
divides(shifted, winding - 2) || divides(shifted, winding + 2),
"a separating curve has winding number {winding} modulo {shifted}; library bug"
);
}
}
total
}
fn higher_class(boundary: &[i64], windings: &[i64], reduction: &Reduction) -> WindingClass {
if windings.iter().any(|w| w % 2 != 0) {
return WindingClass::Odd;
}
assert!(
boundary.iter().all(|w| w % 2 == 0),
"even interior winding numbers with an odd boundary one; library bug"
);
if boundary.iter().any(|w| w % 4 == 0) {
return WindingClass::Even;
}
assert!(
reduction.radical_is_isotropic,
"the Arf form does not vanish on the radical; library bug"
);
WindingClass::Arf(u8::from(reduction.arf))
}
struct Reduction {
pairs: usize,
arf: bool,
radical_is_isotropic: bool,
}
#[derive(Clone)]
struct Vector {
coords: Vec<bool>,
image: Vec<bool>,
}
impl Vector {
fn add(&mut self, other: &Vector) {
xor_into(&mut self.coords, &other.coords);
xor_into(&mut self.image, &other.image);
}
fn pair(&self, other: &Vector) -> bool {
dot(&self.image, &other.coords)
}
}
impl Reduction {
fn new(pairing: &[Vec<i64>], windings: &[i64]) -> Reduction {
let gram: Vec<Vec<bool>> = pairing
.iter()
.map(|row| row.iter().map(|&entry| entry % 2 != 0).collect())
.collect();
let values: Vec<bool> = windings
.iter()
.map(|w| (w.div_euclid(2) + 1) % 2 != 0)
.collect();
let quadratic = |x: &Vector| quadratic(&gram, &values, &x.coords);
let mut pool: Vec<Vector> = (0..gram.len())
.map(|index| Vector {
coords: (0..gram.len()).map(|j| j == index).collect(),
image: gram[index].clone(),
})
.collect();
let (mut pairs, mut arf, mut radical_is_isotropic) = (0, false, true);
while let Some(first) = pool.pop() {
let Some(index) = pool.iter().position(|other| first.pair(other)) else {
radical_is_isotropic &= !quadratic(&first);
continue;
};
let second = pool.swap_remove(index);
arf ^= quadratic(&first) && quadratic(&second);
project(&mut pool, &first, &second);
pairs += 1;
}
Reduction {
pairs,
arf,
radical_is_isotropic,
}
}
}
fn project(pool: &mut [Vector], first: &Vector, second: &Vector) {
for vector in pool {
let (with_first, with_second) = (vector.pair(first), vector.pair(second));
if with_second {
vector.add(first);
}
if with_first {
vector.add(second);
}
}
}
fn quadratic(gram: &[Vec<bool>], values: &[bool], coords: &[bool]) -> bool {
let mut total = false;
for (i, _) in coords.iter().enumerate().filter(|(_, x)| **x) {
total ^= values[i];
for j in (i + 1..coords.len()).filter(|&j| coords[j]) {
total ^= gram[i][j];
}
}
total
}
fn dot(left: &[bool], right: &[bool]) -> bool {
left.iter().zip(right).filter(|(a, b)| **a && **b).count() % 2 == 1
}
fn xor_into(target: &mut [bool], other: &[bool]) {
for (bit, &flip) in target.iter_mut().zip(other) {
*bit ^= flip;
}
}
fn gcd(a: u64, b: i64) -> u64 {
let (mut a, mut b) = (a, b.unsigned_abs());
while b != 0 {
(a, b) = (b, a % b);
}
a
}
fn divides(divisor: u64, value: i64) -> bool {
match divisor {
0 => value == 0,
_ => value.unsigned_abs().is_multiple_of(divisor),
}
}