#[cfg(any(test, cocycle_distance_bench))]
use super::bytes;
use super::{Diagnostics, NONE, Pair, filled, push, reserve, size_overflow};
use crate::{Result, execution::WorkBudget};
struct Graph {
size: usize,
words: usize,
bits: Vec<u64>,
offsets: Vec<usize>,
neighbors: Vec<usize>,
}
#[derive(Clone, Copy)]
struct Cursor {
row: usize,
next: usize,
end: usize,
word: u64,
}
impl Graph {
fn new<const CONTROLLED: bool>(
pair: &Pair<'_, '_>,
radius: f64,
_stats: &mut Diagnostics,
budget: &mut WorkBudget<'_, CONTROLLED>,
) -> Result<Self> {
budget.check()?;
let size = pair.size;
let words = if size < 128 { size.div_ceil(64) } else { 0 };
let mut result = Self {
size,
words,
bits: filled(size.checked_mul(words).ok_or_else(size_overflow)?, 0)?,
offsets: Vec::new(),
neighbors: Vec::new(),
};
if words == 0 {
reserve(
&mut result.offsets,
size.checked_add(1).ok_or_else(size_overflow)?,
)?;
}
let n = pair.first.points.len();
let m = pair.second.points.len();
for left in 0..size {
budget.step()?;
if words == 0 {
result.offsets.push(result.neighbors.len());
}
if left < n {
if words == 0 {
let window = pair.second.window(pair.first.points[left][0], radius);
budget.step_by(window.len())?;
for position in window {
let right = pair.second.order[position];
record! { _stats.adjacency_checks += 1; }
if pair.cross(left, right) <= radius {
result.add(left, right)?;
}
}
} else {
budget.step_by(m)?;
for right in 0..m {
record! { _stats.adjacency_checks += 1; }
if pair.cross(left, right) <= radius {
result.add(left, right)?;
}
}
}
if pair.first.diagonals[left] <= radius {
result.add(left, m + left)?;
}
} else {
let point = left - n;
if pair.second.diagonals[point] <= radius {
result.add(left, point)?;
}
budget.step_by(size - m)?;
for right in m..size {
result.add(left, right)?;
}
}
}
if words == 0 {
result.offsets.push(result.neighbors.len());
}
Ok(result)
}
fn add(&mut self, left: usize, right: usize) -> Result<()> {
if self.words == 0 {
push(&mut self.neighbors, right)
} else {
self.bits[left * self.words + right / 64] |= 1_u64 << (right % 64);
Ok(())
}
}
fn cursor(&self, row: usize) -> Cursor {
if self.words == 0 {
Cursor {
row,
next: self.offsets[row],
end: self.offsets[row + 1],
word: 0,
}
} else {
Cursor {
row,
next: 0,
end: self.words,
word: self.bits[row * self.words],
}
}
}
fn next(&self, cursor: &mut Cursor) -> Option<usize> {
if self.words == 0 {
if cursor.next == cursor.end {
return None;
}
let result = self.neighbors[cursor.next];
cursor.next += 1;
return Some(result);
}
while cursor.next < cursor.end {
if cursor.word != 0 {
let bit = cursor.word.trailing_zeros() as usize;
cursor.word &= cursor.word - 1;
return Some(cursor.next * 64 + bit);
}
cursor.next += 1;
if cursor.next < cursor.end {
cursor.word = self.bits[cursor.row * self.words + cursor.next];
}
}
None
}
fn degree(&self, row: usize) -> usize {
if self.words == 0 {
self.offsets[row + 1] - self.offsets[row]
} else {
self.bits[row * self.words..(row + 1) * self.words]
.iter()
.map(|w| w.count_ones() as usize)
.sum()
}
}
#[cfg(any(test, cocycle_distance_bench))]
fn bytes(&self) -> usize {
bytes(&self.bits)
.saturating_add(bytes(&self.offsets))
.saturating_add(bytes(&self.neighbors))
}
}
struct Frame {
left: usize,
cursor: Cursor,
via: usize,
}
pub(super) struct Workspace {
left: Vec<usize>,
right: Vec<usize>,
order: Vec<usize>,
degrees: Vec<usize>,
seen: Vec<usize>,
stack: Vec<Frame>,
#[cfg(any(test, cocycle_distance_bench))]
used: bool,
}
impl Workspace {
pub(super) fn new(size: usize) -> Result<Self> {
let mut stack = Vec::new();
reserve(&mut stack, size)?;
Ok(Self {
left: filled(size, NONE)?,
right: filled(size, NONE)?,
order: filled(size, 0)?,
degrees: filled(size, 0)?,
seen: filled(size, 0)?,
stack,
#[cfg(any(test, cocycle_distance_bench))]
used: false,
})
}
pub(super) fn within<const CONTROLLED: bool>(
&mut self,
pair: &Pair<'_, '_>,
radius: f64,
_stats: &mut Diagnostics,
_outer_bytes: usize,
budget: &mut WorkBudget<'_, CONTROLLED>,
) -> Result<bool> {
let graph = Graph::new(pair, radius, _stats, budget)?;
record! { _stats.workspace(
_outer_bytes
.saturating_add(graph.bytes())
.saturating_add(self.bytes()),
); }
record! {
if self.used {
_stats.scratch_reuses += 1;
}
self.used = true;
}
budget.step_by(graph.size)?;
self.left.fill(NONE);
self.right.fill(NONE);
self.seen.fill(0);
for vertex in 0..graph.size {
if CONTROLLED && vertex % 256 == 0 {
budget.step_by((graph.size - vertex).min(256))?;
}
self.order[vertex] = vertex;
self.degrees[vertex] = graph.degree(vertex);
}
self.order
.sort_unstable_by_key(|&vertex| (self.degrees[vertex], vertex));
for &left in &self.order {
if CONTROLLED {
budget.step_by(self.degrees[left].max(1))?;
}
let mut cursor = graph.cursor(left);
while let Some(right) = graph.next(&mut cursor) {
if self.right[right] == NONE {
self.left[left] = right;
self.right[right] = left;
break;
}
}
}
for position in 0..graph.size {
budget.step()?;
let left = self.order[position];
if self.left[left] != NONE {
continue;
}
record! { _stats.augment_searches += 1; }
let generation = position + 1;
self.stack.clear();
self.stack.push(Frame {
left,
cursor: graph.cursor(left),
via: NONE,
});
let mut augmented = false;
while let Some(frame) = self.stack.last_mut() {
budget.step()?;
let Some(right) = graph.next(&mut frame.cursor) else {
self.stack.pop();
continue;
};
if self.seen[right] == generation {
continue;
}
self.seen[right] = generation;
let previous = self.right[right];
if previous == NONE {
let mut assign = right;
budget.step_by(self.stack.len())?;
for frame in self.stack.iter().rev() {
self.left[frame.left] = assign;
self.right[assign] = frame.left;
assign = frame.via;
}
augmented = true;
break;
}
self.stack.push(Frame {
left: previous,
cursor: graph.cursor(previous),
via: right,
});
}
if !augmented {
return Ok(false);
}
}
Ok(true)
}
#[cfg(any(test, cocycle_distance_bench))]
pub(super) fn bytes(&self) -> usize {
bytes(&self.left)
.saturating_add(bytes(&self.right))
.saturating_add(bytes(&self.order))
.saturating_add(bytes(&self.degrees))
.saturating_add(bytes(&self.seen))
.saturating_add(bytes(&self.stack))
}
}