use crate::connectivity_graph::ConnectivityGraph;
use crate::dijkstra::{checked_int_distance_bound, IntQueue};
use crate::neighborhood::{neighborhood_masks, neighborhood_offsets, DIRECTIONS_26};
use crate::queue::binary_heap::BinaryHeapQueue;
use crate::queue::bucket::BucketQueue;
use crate::voxel::{ToU64Fast, VolumeShape};
use crate::{Connectivity, Dijkstra3dError, Result};
#[derive(Debug, Clone, Copy, Default, PartialEq, Eq)]
pub struct WorkStats {
pub relaxations_attempted: u64,
pub relaxations_succeeded: u64,
pub pops: u64,
pub settled: u64,
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum WorkOp {
Dijkstra {
source: u64,
target: u64,
},
ParentalField {
source: u64,
},
DistanceField {
sources: Vec<u64>,
},
}
pub fn work_stats_int<T: ToU64Fast>(
field: &[T],
shape: VolumeShape,
op: &WorkOp,
connectivity: Connectivity,
graph: Option<ConnectivityGraph<'_>>,
) -> Result<WorkStats> {
let total = shape.total();
if field.len() as u64 != total {
return Err(Dijkstra3dError::InvalidInput(format!(
"work_stats_int: slice length {} != shape.total() {}",
field.len(),
total
)));
}
if total > u32::MAX as u64 {
return Err(Dijkstra3dError::InvalidInput(format!(
"work_stats_int: volume {total} exceeds u32::MAX voxels"
)));
}
let (sources, target): (Vec<u64>, Option<u64>) = match op {
WorkOp::Dijkstra { source, target } => {
check_bounds(*source, total)?;
check_bounds(*target, total)?;
(vec![*source], Some(*target))
}
WorkOp::ParentalField { source } => {
check_bounds(*source, total)?;
(vec![*source], None)
}
WorkOp::DistanceField { sources } => {
if sources.is_empty() {
return Err(Dijkstra3dError::InvalidInput(
"sources cannot be empty".into(),
));
}
for &s in sources {
check_bounds(s, total)?;
}
(sources.clone(), None)
}
};
let max_weight = field.iter().map(|&v| v.to_u64_fast()).max().unwrap_or(0);
checked_int_distance_bound(shape, max_weight)?;
let use_bucket = max_weight < 65_536;
let stats = if use_bucket {
run_instrumented(
field,
shape,
&sources,
target,
connectivity,
graph,
BucketQueue::with_capacity(max_weight as u32),
)
} else {
run_instrumented(
field,
shape,
&sources,
target,
connectivity,
graph,
BinaryHeapQueue::<u64, u32>::new(),
)
};
Ok(stats)
}
#[inline]
fn check_bounds(idx: u64, total: u64) -> Result<()> {
if idx >= total {
return Err(Dijkstra3dError::OutOfBounds {
idx,
volume_size: total,
});
}
Ok(())
}
fn run_instrumented<T: ToU64Fast, Q: IntQueue>(
field: &[T],
shape: VolumeShape,
sources: &[u64],
target: Option<u64>,
connectivity: Connectivity,
graph: Option<ConnectivityGraph<'_>>,
mut queue: Q,
) -> WorkStats {
let total = shape.total() as usize;
let mut distances = vec![u64::MAX; total];
for &s in sources {
distances[s as usize] = 0;
queue.push_i(0, s as u32);
}
let sx_i = shape.sx as i64;
let sxy_i = (shape.sx * shape.sy) as i64;
let offsets = neighborhood_offsets(sx_i, sxy_i);
let masks = neighborhood_masks();
let neighbor_count = connectivity.count();
let sx_u = shape.sx as i64;
let sy_u = shape.sy as i64;
let sz_u = shape.sz as i64;
let mut stats = WorkStats::default();
while let Some((dist, loc)) = queue.pop_i() {
stats.pops += 1;
let loc_us = loc as usize;
if dist > distances[loc_us] {
continue;
}
stats.settled += 1;
if let Some(t) = target {
if loc as u64 == t {
break;
}
}
let (lx, ly, lz) = shape.coords(loc as u64);
let current_dist = distances[loc_us];
for i in 0..neighbor_count {
let (dx, dy, dz) = DIRECTIONS_26[i];
let nx = lx as i64 + dx as i64;
let ny = ly as i64 + dy as i64;
let nz = lz as i64 + dz as i64;
if nx < 0 || nx >= sx_u || ny < 0 || ny >= sy_u || nz < 0 || nz >= sz_u {
continue;
}
let neighbor = (loc as i64 + offsets[i]) as u64;
if let Some(ref g) = graph {
if !g.allows(loc as u64, masks[i]) {
continue;
}
}
stats.relaxations_attempted += 1;
let neighbor_cost = field[neighbor as usize].to_u64_fast();
let new_dist = current_dist.saturating_add(neighbor_cost);
if new_dist < distances[neighbor as usize] {
distances[neighbor as usize] = new_dist;
stats.relaxations_succeeded += 1;
queue.push_i(new_dist, neighbor as u32);
}
}
}
stats
}
#[cfg(test)]
mod tests {
use super::*;
fn uniform(sx: u64, sy: u64, sz: u64, val: u8) -> (Vec<u8>, VolumeShape) {
let shape = VolumeShape::new(sx, sy, sz);
(vec![val; shape.total() as usize], shape)
}
#[test]
fn settled_equals_reachable_for_full_traversal() {
let (field, shape) = uniform(8, 8, 8, 1);
let stats = work_stats_int(
&field,
shape,
&WorkOp::ParentalField { source: 0 },
Connectivity::TwentySix,
None,
)
.unwrap();
assert_eq!(stats.settled, shape.total());
assert!(stats.pops >= stats.settled);
assert!(stats.relaxations_succeeded >= shape.total() - 1);
assert!(stats.relaxations_attempted >= stats.relaxations_succeeded);
}
#[test]
fn distance_field_multisource_settles_all() {
let (field, shape) = uniform(6, 6, 6, 2);
let stats = work_stats_int(
&field,
shape,
&WorkOp::DistanceField {
sources: vec![0, (shape.total() - 1)],
},
Connectivity::Six,
None,
)
.unwrap();
assert_eq!(stats.settled, shape.total());
}
#[test]
fn dijkstra_early_terminates_before_full_settle() {
let (field, shape) = uniform(16, 16, 16, 1);
let target = shape.linear(2, 0, 0);
let stats = work_stats_int(
&field,
shape,
&WorkOp::Dijkstra { source: 0, target },
Connectivity::Six,
None,
)
.unwrap();
assert!(stats.settled >= 1);
assert!(stats.settled < shape.total());
assert!(stats.pops >= stats.settled);
}
#[test]
fn out_of_bounds_source_errors() {
let (field, shape) = uniform(4, 4, 4, 1);
let bad = shape.total() + 10;
let err = work_stats_int(
&field,
shape,
&WorkOp::ParentalField { source: bad },
Connectivity::Six,
None,
);
assert!(err.is_err());
}
#[test]
fn work_stats_rejects_unrepresentable_distance_bound() {
let shape = VolumeShape::new(2, 2, 2);
let field = vec![u64::MAX; shape.total() as usize];
let result = work_stats_int(
&field,
shape,
&WorkOp::Dijkstra {
source: 0,
target: shape.total() - 1,
},
Connectivity::Six,
None,
);
assert!(matches!(result, Err(Dijkstra3dError::InvalidInput(_))));
}
}