use super::shape::Sign;
use super::threads::{GentleThread, Threads};
#[derive(Clone, Debug, PartialEq, Eq, Hash, PartialOrd, Ord)]
pub struct AagFunction {
pairs: Vec<(usize, usize)>,
}
impl AagFunction {
pub(crate) fn new(threads: &Threads, vertices: u32) -> AagFunction {
let permitted = SlotIndex::new(vertices, &threads.permitted, |h| (h.start(), h.sigma()));
let forbidden = SlotIndex::new(vertices, &threads.forbidden, |p| (p.end(), p.epsilon()));
let mut visited = vec![false; threads.permitted.len()];
let mut pairs = Vec::new();
for first in 0..threads.permitted.len() {
let mut current = first;
let (mut n, mut m) = (0, 0);
while !visited[current] {
visited[current] = true;
let thread = &threads.permitted[current];
let closing = &threads.forbidden[forbidden.at(thread.end(), thread.epsilon())];
current = permitted.at(closing.start(), closing.sigma());
n += 1;
m += closing.length();
}
assert_eq!(
current, first,
"the thread map is not a bijection; library bug"
);
if n > 0 {
pairs.push((n, m));
}
}
pairs.extend(threads.cycles.iter().map(|cycle| (0, cycle.len())));
pairs.sort_unstable();
AagFunction { pairs }
}
accessor_methods! {
pub pairs() -> &[(usize, usize)] = |this| &this.pairs;
pub len() -> usize = |this| this.pairs.len();
pub is_empty() -> bool = |this| this.pairs.is_empty();
}
}
impl std::fmt::Display for AagFunction {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
f.write_str("[")?;
for (position, (n, m)) in self.pairs.iter().enumerate() {
let separator = if position == 0 { "" } else { ", " };
write!(f, "{separator}({n}, {m})")?;
}
f.write_str("]")
}
}
struct SlotIndex(Vec<Option<usize>>);
impl SlotIndex {
fn new(
vertices: u32,
threads: &[GentleThread],
key: impl Fn(&GentleThread) -> (u32, Sign),
) -> SlotIndex {
let mut slots = vec![None; 2 * vertices as usize];
for (position, thread) in threads.iter().enumerate() {
let (vertex, sign) = key(thread);
let slot = &mut slots[slot(vertex, sign)];
assert!(slot.is_none(), "two threads share a slot; library bug");
*slot = Some(position);
}
SlotIndex(slots)
}
fn at(&self, vertex: u32, sign: Sign) -> usize {
self.0[slot(vertex, sign.negated())].expect("every thread end meets a thread; library bug")
}
}
fn slot(vertex: u32, sign: Sign) -> usize {
2 * vertex as usize + usize::from(sign == Sign::Minus)
}