use crate::connectivity_graph::ConnectivityGraph;
use crate::neighborhood::{neighborhood_masks, neighborhood_offsets};
use crate::perf_pool::resolve_batch_pool;
use crate::queue::binary_heap::BinaryHeapQueue;
use crate::queue::bucket::BucketQueue;
use crate::queue::PriorityQueue;
use crate::voxel::{Anisotropy, ToF32Fast, ToU64Fast, VolumeShape, VoxelSource};
use crate::{Connectivity, Dijkstra3dError, Result};
use num_traits::ToPrimitive;
use rayon::prelude::*;
fn run_batch_on_pool<R: Send>(threads: Option<usize>, f: impl FnOnce() -> R + Send) -> R {
match resolve_batch_pool(threads) {
Some(pool) => pool.install(f),
None => f(),
}
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum Mode {
Unidirectional,
Bidirectional,
Compass,
}
#[derive(Debug, Clone, Copy)]
pub struct DijkstraConfig {
pub connectivity: Connectivity,
pub anisotropy: Anisotropy,
pub mode: Mode,
}
impl Default for DijkstraConfig {
fn default() -> Self {
Self {
connectivity: Connectivity::TwentySix,
anisotropy: Anisotropy::default(),
mode: Mode::Unidirectional,
}
}
}
pub fn dijkstra<V>(
field: &V,
source: u64,
target: u64,
cfg: DijkstraConfig,
graph: Option<ConnectivityGraph<'_>>,
) -> Result<Vec<u64>>
where
V: VoxelSource,
V::Item: ToPrimitive,
{
let shape = field.shape();
let total = shape.total();
if source >= total {
return Err(Dijkstra3dError::OutOfBounds {
idx: source,
volume_size: total,
});
}
if target >= total {
return Err(Dijkstra3dError::OutOfBounds {
idx: target,
volume_size: total,
});
}
if source == target {
return Ok(vec![source]);
}
match cfg.mode {
Mode::Unidirectional => dijkstra_unidirectional(field, source, target, cfg, graph),
Mode::Bidirectional => dijkstra_bidirectional(field, source, target, cfg, graph),
Mode::Compass => dijkstra_compass(field, source, target, cfg, graph),
}
}
fn dijkstra_unidirectional<V>(
field: &V,
source: u64,
target: u64,
cfg: DijkstraConfig,
graph: Option<ConnectivityGraph<'_>>,
) -> Result<Vec<u64>>
where
V: VoxelSource,
V::Item: ToPrimitive,
{
let shape = field.shape();
let total = shape.total();
let mut distances = vec![f32::INFINITY; total as usize];
let mut parents = vec![0u64; total as usize];
distances[source as usize] = 0.0;
let mut queue = BinaryHeapQueue::<f32, u64>::new();
queue.push(0.0, source);
let sx = shape.sx as i64;
let sxy = (shape.sx * shape.sy) as i64;
let offsets = neighborhood_offsets(sx, sxy);
let masks = neighborhood_masks();
let neighbor_count = cfg.connectivity.count();
let sx_u = shape.sx;
let sy_u = shape.sy;
let sz_u = shape.sz;
while let Some((dist, loc)) = queue.pop() {
if dist > distances[loc as usize] {
continue;
}
if loc == target {
return Ok(reconstruct_path(&parents, source, target));
}
let (lx, ly, lz) = shape.coords(loc);
for i in 0..neighbor_count {
let (dx, dy, dz) = crate::neighborhood::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 as i64
|| ny < 0
|| ny >= sy_u as i64
|| nz < 0
|| nz >= sz_u as i64
{
continue;
}
let neighbor = (loc as i64 + offsets[i]) as u64;
if let Some(ref g) = graph {
if !g.allows(loc, masks[i]) {
continue;
}
}
let neighbor_cost = field.get(neighbor)?;
let neighbor_cost_f32 = neighbor_cost.to_f32().ok_or(Dijkstra3dError::OutOfBounds {
idx: neighbor,
volume_size: total,
})?;
let new_dist = distances[loc as usize] + neighbor_cost_f32;
if new_dist < distances[neighbor as usize] {
distances[neighbor as usize] = new_dist;
parents[neighbor as usize] = loc + 1; queue.push(new_dist, neighbor);
}
}
}
Err(Dijkstra3dError::Unreachable)
}
fn reconstruct_path(parents: &[u64], source: u64, target: u64) -> Vec<u64> {
let mut path = vec![target];
let mut current = target;
while current != source {
let parent = parents[current as usize];
if parent == 0 {
break;
}
current = parent - 1;
path.push(current);
}
path.reverse();
path
}
fn dijkstra_bidirectional<V>(
field: &V,
source: u64,
target: u64,
cfg: DijkstraConfig,
graph: Option<ConnectivityGraph<'_>>,
) -> Result<Vec<u64>>
where
V: VoxelSource,
V::Item: ToPrimitive,
{
let shape = field.shape();
let total = shape.total();
let field_tgt_f32 = field
.get(target)?
.to_f32()
.ok_or(Dijkstra3dError::OutOfBounds {
idx: target,
volume_size: total,
})?;
let mut dist_fwd = vec![f32::INFINITY; total as usize];
let mut parents_fwd = vec![0u64; total as usize];
dist_fwd[source as usize] = 0.0;
let mut queue_fwd = BinaryHeapQueue::<f32, u64>::new();
queue_fwd.push(0.0, source);
let mut dist_bwd = vec![f32::INFINITY; total as usize];
let mut parents_bwd = vec![0u64; total as usize];
dist_bwd[target as usize] = 0.0;
let mut queue_bwd = BinaryHeapQueue::<f32, u64>::new();
queue_bwd.push(0.0, target);
let mut best_cost = f32::INFINITY;
let mut final_loc: Option<u64> = None;
let sx = shape.sx as i64;
let sxy = (shape.sx * shape.sy) as i64;
let offsets = neighborhood_offsets(sx, sxy);
let masks = neighborhood_masks();
let neighbor_count = cfg.connectivity.count();
let sx_u = shape.sx;
let sy_u = shape.sy;
let sz_u = shape.sz;
let mut forward = false;
loop {
let kf = match queue_fwd.peek() {
Some((k, _)) => k,
None => break,
};
let kb = match queue_bwd.peek() {
Some((k, _)) => k,
None => break,
};
if kf + kb >= best_cost {
break;
}
forward = !forward;
let (dist, loc) = if forward {
queue_fwd.pop().unwrap()
} else {
queue_bwd.pop().unwrap()
};
let loc_us = loc as usize;
if forward {
if dist > dist_fwd[loc_us] {
continue;
}
} else if dist > dist_bwd[loc_us] {
continue;
}
if (forward && dist_bwd[loc_us].is_finite()) || (!forward && dist_fwd[loc_us].is_finite()) {
let field_loc_f32 = field
.get(loc)?
.to_f32()
.ok_or(Dijkstra3dError::OutOfBounds {
idx: loc,
volume_size: total,
})?;
let cost = dist_fwd[loc_us] + dist_bwd[loc_us] + field_tgt_f32 - field_loc_f32;
if cost < best_cost {
best_cost = cost;
final_loc = Some(loc);
}
}
let (lx, ly, lz) = shape.coords(loc);
for i in 0..neighbor_count {
let (dx, dy, dz) = crate::neighborhood::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 as i64
|| ny < 0
|| ny >= sy_u as i64
|| nz < 0
|| nz >= sz_u as i64
{
continue;
}
let neighbor = (loc as i64 + offsets[i]) as u64;
if let Some(ref g) = graph {
if !g.allows(loc, masks[i]) {
continue;
}
}
let neighbor_cost = field.get(neighbor)?;
let neighbor_cost_f32 = neighbor_cost.to_f32().ok_or(Dijkstra3dError::OutOfBounds {
idx: neighbor,
volume_size: total,
})?;
if forward {
let new_dist = dist_fwd[loc_us] + neighbor_cost_f32;
if new_dist < dist_fwd[neighbor as usize] {
dist_fwd[neighbor as usize] = new_dist;
parents_fwd[neighbor as usize] = loc + 1;
queue_fwd.push(new_dist, neighbor);
if dist_bwd[neighbor as usize].is_finite() {
let cost = new_dist + dist_bwd[neighbor as usize] + field_tgt_f32
- neighbor_cost_f32;
if cost < best_cost {
best_cost = cost;
final_loc = Some(neighbor);
}
}
}
} else {
let new_dist = dist_bwd[loc_us] + neighbor_cost_f32;
if new_dist < dist_bwd[neighbor as usize] {
dist_bwd[neighbor as usize] = new_dist;
parents_bwd[neighbor as usize] = loc + 1;
queue_bwd.push(new_dist, neighbor);
if dist_fwd[neighbor as usize].is_finite() {
let cost = dist_fwd[neighbor as usize] + new_dist + field_tgt_f32
- neighbor_cost_f32;
if cost < best_cost {
best_cost = cost;
final_loc = Some(neighbor);
}
}
}
}
}
}
if let Some(meet) = final_loc {
let fwd = reconstruct_path(&parents_fwd, source, meet);
let bwd = reconstruct_path(&parents_bwd, target, meet);
let mut path = fwd;
path.extend(bwd.iter().rev().skip(1).copied());
Ok(path)
} else {
Err(Dijkstra3dError::Unreachable)
}
}
fn dijkstra_compass<V>(
field: &V,
source: u64,
target: u64,
cfg: DijkstraConfig,
graph: Option<ConnectivityGraph<'_>>,
) -> Result<Vec<u64>>
where
V: VoxelSource,
V::Item: ToPrimitive,
{
let shape = field.shape();
let total = shape.total();
let mut distances = vec![f32::INFINITY; total as usize];
let mut parents = vec![0u64; total as usize];
distances[source as usize] = 0.0;
let mut queue = BinaryHeapQueue::<f32, u64>::new();
let (tx, ty, tz) = shape.coords(target);
let (sx_coord, sy_coord, sz_coord) = shape.coords(source);
let h_source = euclidean_heuristic(sx_coord, sy_coord, sz_coord, tx, ty, tz, cfg.anisotropy);
queue.push(h_source, source);
let sx = shape.sx as i64;
let sxy = (shape.sx * shape.sy) as i64;
let offsets = neighborhood_offsets(sx, sxy);
let masks = neighborhood_masks();
let neighbor_count = cfg.connectivity.count();
let sx_u = shape.sx;
let sy_u = shape.sy;
let sz_u = shape.sz;
while let Some((_, loc)) = queue.pop() {
let current_g = distances[loc as usize];
if loc == target {
return Ok(reconstruct_path(&parents, source, target));
}
let (lx, ly, lz) = shape.coords(loc);
for i in 0..neighbor_count {
let (dx, dy, dz) = crate::neighborhood::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 as i64
|| ny < 0
|| ny >= sy_u as i64
|| nz < 0
|| nz >= sz_u as i64
{
continue;
}
let neighbor = (loc as i64 + offsets[i]) as u64;
if let Some(ref g) = graph {
if !g.allows(loc, masks[i]) {
continue;
}
}
let neighbor_cost = field.get(neighbor)?;
let neighbor_cost_f32 = neighbor_cost.to_f32().ok_or(Dijkstra3dError::OutOfBounds {
idx: neighbor,
volume_size: total,
})?;
let new_g = current_g + neighbor_cost_f32;
if new_g < distances[neighbor as usize] {
distances[neighbor as usize] = new_g;
parents[neighbor as usize] = loc + 1;
let (nx_u, ny_u, nz_u) = shape.coords(neighbor);
let h = euclidean_heuristic(nx_u, ny_u, nz_u, tx, ty, tz, cfg.anisotropy);
let f = new_g + h;
queue.push(f, neighbor);
}
}
}
Err(Dijkstra3dError::Unreachable)
}
fn euclidean_heuristic(
x: u64,
y: u64,
z: u64,
tx: u64,
ty: u64,
tz: u64,
aniso: Anisotropy,
) -> f32 {
let (wx, wy, wz) = (aniso.wx, aniso.wy, aniso.wz);
let dx = (x as f32 - tx as f32) * wx;
let dy = (y as f32 - ty as f32) * wy;
let dz = (z as f32 - tz as f32) * wz;
(dx * dx + dy * dy + dz * dz).sqrt()
}
pub const COMPASS_INFORMATIVE_RATIO: f32 = 0.30;
pub fn compass_heuristic_is_informative<T: ToF32Fast>(
field: &[T],
shape: VolumeShape,
source: u64,
target: u64,
anisotropy: Anisotropy,
) -> bool {
let (sx, sy, sz) = shape.coords(source);
let (tx, ty, tz) = shape.coords(target);
let dx = (sx as i64 - tx as i64).unsigned_abs();
let dy = (sy as i64 - ty as i64).unsigned_abs();
let dz = (sz as i64 - tz as i64).unsigned_abs();
let cheb = dx.max(dy).max(dz);
if cheb == 0 {
return true;
}
let mut samples: Vec<f32> = Vec::with_capacity(cheb as usize + 1);
let (fsx, fsy, fsz) = (sx as f64, sy as f64, sz as f64);
let (seg_x, seg_y, seg_z) = (
tx as f64 - sx as f64,
ty as f64 - sy as f64,
tz as f64 - sz as f64,
);
for k in 0..=cheb {
let t = k as f64 / cheb as f64;
let px = (fsx + seg_x * t).round() as u64;
let py = (fsy + seg_y * t).round() as u64;
let pz = (fsz + seg_z * t).round() as u64;
let idx = shape.linear(px, py, pz) as usize;
samples.push(field[idx].to_f32_fast());
}
samples.sort_by(|a, b| a.partial_cmp(b).unwrap_or(std::cmp::Ordering::Equal));
let line_cost = samples[samples.len() / 2];
let h = euclidean_heuristic(sx, sy, sz, tx, ty, tz, anisotropy);
h >= COMPASS_INFORMATIVE_RATIO * line_cost * cheb as f32
}
pub fn dijkstra_unidirectional_slice<T>(
field: &[T],
shape: VolumeShape,
source: u64,
target: u64,
connectivity: Connectivity,
graph: Option<ConnectivityGraph<'_>>,
) -> Result<Vec<u64>>
where
T: ToF32Fast,
{
let total = shape.total();
if field.len() as u64 != total {
return Err(Dijkstra3dError::InvalidInput(format!(
"dijkstra_unidirectional_slice: slice length {} != shape.total() {}",
field.len(),
total
)));
}
if source >= total {
return Err(Dijkstra3dError::OutOfBounds {
idx: source,
volume_size: total,
});
}
if target >= total {
return Err(Dijkstra3dError::OutOfBounds {
idx: target,
volume_size: total,
});
}
if source == target {
return Ok(vec![source]);
}
let mut distances = vec![f32::INFINITY; total as usize];
let mut parents = vec![0u64; total as usize];
distances[source as usize] = 0.0;
let mut queue = BinaryHeapQueue::<f32, u64>::new();
queue.push(0.0, source);
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;
let sy_u = shape.sy;
let sz_u = shape.sz;
while let Some((dist, loc)) = queue.pop() {
if dist > distances[loc as usize] {
continue;
}
if loc == target {
return Ok(reconstruct_path(&parents, source, target));
}
let (lx, ly, lz) = shape.coords(loc);
let current_dist = distances[loc as usize];
for i in 0..neighbor_count {
let (dx, dy, dz) = crate::neighborhood::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 as i64
|| ny < 0
|| ny >= sy_u as i64
|| nz < 0
|| nz >= sz_u as i64
{
continue;
}
let neighbor = (loc as i64 + offsets[i]) as u64;
if let Some(ref g) = graph {
if !g.allows(loc, masks[i]) {
continue;
}
}
let neighbor_cost_f32 = field[neighbor as usize].to_f32_fast();
let new_dist = current_dist + neighbor_cost_f32;
if new_dist < distances[neighbor as usize] {
distances[neighbor as usize] = new_dist;
parents[neighbor as usize] = loc + 1;
queue.push(new_dist, neighbor);
}
}
}
Err(Dijkstra3dError::Unreachable)
}
fn reconstruct_path_u32(parents: &[u32], source: u64, target: u64) -> Vec<u64> {
let mut path = vec![target];
let mut current = target;
while current != source {
let parent = parents[current as usize];
if parent == 0 {
break;
}
current = (parent - 1) as u64;
path.push(current);
}
path.reverse();
path
}
pub(crate) trait IntQueue {
fn push_i(&mut self, priority: u64, payload: u32);
fn pop_i(&mut self) -> Option<(u64, u32)>;
fn peek_key_i(&mut self) -> Option<u64>;
}
impl IntQueue for BucketQueue {
#[inline]
fn push_i(&mut self, priority: u64, payload: u32) {
self.push(priority, payload);
}
#[inline]
fn pop_i(&mut self) -> Option<(u64, u32)> {
self.pop()
}
#[inline]
fn peek_key_i(&mut self) -> Option<u64> {
self.peek_key()
}
}
impl IntQueue for BinaryHeapQueue<u64, u32> {
#[inline]
fn push_i(&mut self, priority: u64, payload: u32) {
self.push(priority, payload);
}
#[inline]
fn pop_i(&mut self) -> Option<(u64, u32)> {
self.pop()
}
#[inline]
fn peek_key_i(&mut self) -> Option<u64> {
<Self as PriorityQueue<u64, u32>>::peek(self).map(|(p, _)| p)
}
}
pub(crate) trait Dist: Copy + Ord {
const MAX: Self;
const ZERO: Self;
fn add_cost(self, w: u64) -> Self;
fn to_priority(self) -> u64;
}
impl Dist for u16 {
const MAX: Self = u16::MAX;
const ZERO: Self = 0;
#[inline]
fn add_cost(self, w: u64) -> Self {
self + w as u16
}
#[inline]
fn to_priority(self) -> u64 {
self as u64
}
}
impl Dist for u32 {
const MAX: Self = u32::MAX;
const ZERO: Self = 0;
#[inline]
fn add_cost(self, w: u64) -> Self {
self + w as u32
}
#[inline]
fn to_priority(self) -> u64 {
self as u64
}
}
impl Dist for u64 {
const MAX: Self = u64::MAX;
const ZERO: Self = 0;
#[inline]
fn add_cost(self, w: u64) -> Self {
self + w
}
#[inline]
fn to_priority(self) -> u64 {
self
}
}
#[derive(Clone, Copy, PartialEq, Eq, Debug)]
pub(crate) enum DistWidth {
U16,
U32,
U64,
}
#[doc(hidden)]
#[derive(Clone, Copy, PartialEq, Eq, Debug)]
pub enum AblationQueue {
Dial,
BinaryHeap,
}
#[doc(hidden)]
#[derive(Clone, Copy, PartialEq, Eq, Debug)]
pub enum AblationDistanceWidth {
U16,
U32,
U64,
}
#[inline]
pub(crate) fn select_dist_width(dist_bound: u64) -> DistWidth {
if dist_bound <= u16::MAX as u64 {
DistWidth::U16
} else if dist_bound <= u32::MAX as u64 {
DistWidth::U32
} else {
DistWidth::U64
}
}
pub(crate) fn checked_int_distance_bound(shape: VolumeShape, max_weight: u64) -> Result<u64> {
let max_steps = shape
.sx
.checked_add(shape.sy)
.and_then(|sum| sum.checked_add(shape.sz))
.and_then(|sum| sum.checked_add(1))
.ok_or_else(|| {
Dijkstra3dError::InvalidInput(format!(
"volume dimensions ({}, {}, {}) overflow integer distance bounds",
shape.sx, shape.sy, shape.sz
))
})?;
let bound = max_steps.checked_mul(max_weight).ok_or_else(|| {
Dijkstra3dError::InvalidInput(format!(
"integer costs with maximum weight {max_weight} are too large for shape ({}, {}, {})",
shape.sx, shape.sy, shape.sz
))
})?;
if bound == u64::MAX {
return Err(Dijkstra3dError::InvalidInput(format!(
"integer costs with maximum weight {max_weight} collide with the u64::MAX distance sentinel"
)));
}
Ok(bound)
}
pub fn dijkstra_unidirectional_slice_int<T: ToU64Fast>(
field: &[T],
shape: VolumeShape,
source: u64,
target: u64,
connectivity: Connectivity,
graph: Option<ConnectivityGraph<'_>>,
) -> Result<Vec<u64>> {
let total = shape.total();
if field.len() as u64 != total {
return Err(Dijkstra3dError::InvalidInput(format!(
"dijkstra_unidirectional_slice_int: slice length {} != shape.total() {}",
field.len(),
total
)));
}
if total > u32::MAX as u64 {
return Err(Dijkstra3dError::InvalidInput(format!(
"dijkstra_unidirectional_slice_int: volume {total} exceeds u32::MAX voxels; \
use the u64 fast path"
)));
}
if source >= total {
return Err(Dijkstra3dError::OutOfBounds {
idx: source,
volume_size: total,
});
}
if target >= total {
return Err(Dijkstra3dError::OutOfBounds {
idx: target,
volume_size: total,
});
}
if source == target {
return Ok(vec![source]);
}
let max_weight = field.iter().map(|&v| v.to_u64_fast()).max().unwrap_or(0);
let dist_bound = checked_int_distance_bound(shape, max_weight)?;
let width = select_dist_width(dist_bound);
let use_bucket = max_weight < 65_536;
match (use_bucket, width) {
(true, DistWidth::U16) => slice_int_search::<_, _, u16>(
field,
shape,
source,
target,
connectivity,
graph,
BucketQueue::with_capacity(max_weight as u32),
),
(true, DistWidth::U32) => slice_int_search::<_, _, u32>(
field,
shape,
source,
target,
connectivity,
graph,
BucketQueue::with_capacity(max_weight as u32),
),
(true, DistWidth::U64) => slice_int_search::<_, _, u64>(
field,
shape,
source,
target,
connectivity,
graph,
BucketQueue::with_capacity(max_weight as u32),
),
(false, DistWidth::U16) => slice_int_search::<_, _, u16>(
field,
shape,
source,
target,
connectivity,
graph,
BinaryHeapQueue::<u64, u32>::new(),
),
(false, DistWidth::U32) => slice_int_search::<_, _, u32>(
field,
shape,
source,
target,
connectivity,
graph,
BinaryHeapQueue::<u64, u32>::new(),
),
(false, DistWidth::U64) => slice_int_search::<_, _, u64>(
field,
shape,
source,
target,
connectivity,
graph,
BinaryHeapQueue::<u64, u32>::new(),
),
}
}
#[doc(hidden)]
#[allow(clippy::too_many_arguments)]
pub fn dijkstra_unidirectional_slice_int_ablation<T: ToU64Fast>(
field: &[T],
shape: VolumeShape,
source: u64,
target: u64,
connectivity: Connectivity,
graph: Option<ConnectivityGraph<'_>>,
queue: AblationQueue,
width: AblationDistanceWidth,
) -> Result<Vec<u64>> {
let total = shape.total();
if field.len() as u64 != total || total > u32::MAX as u64 {
return Err(Dijkstra3dError::InvalidInput(
"integer ablation field/shape is invalid".into(),
));
}
if source >= total {
return Err(Dijkstra3dError::OutOfBounds {
idx: source,
volume_size: total,
});
}
if target >= total {
return Err(Dijkstra3dError::OutOfBounds {
idx: target,
volume_size: total,
});
}
if source == target {
return Ok(vec![source]);
}
let max_weight = field
.iter()
.map(|&value| value.to_u64_fast())
.max()
.unwrap_or(0);
let dist_bound = checked_int_distance_bound(shape, max_weight)?;
if queue == AblationQueue::Dial && max_weight >= 65_536 {
return Err(Dijkstra3dError::InvalidInput(format!(
"Dial ablation requires max_weight < 65536; got {max_weight}"
)));
}
let width_limit = match width {
AblationDistanceWidth::U16 => u16::MAX as u64,
AblationDistanceWidth::U32 => u32::MAX as u64,
AblationDistanceWidth::U64 => u64::MAX,
};
if dist_bound > width_limit {
return Err(Dijkstra3dError::InvalidInput(format!(
"forced {width:?} distance cannot represent bound {dist_bound}"
)));
}
macro_rules! run {
($dist:ty, $queue:expr) => {
slice_int_search::<_, _, $dist>(
field,
shape,
source,
target,
connectivity,
graph,
$queue,
)
};
}
match (queue, width) {
(AblationQueue::Dial, AblationDistanceWidth::U16) => {
run!(u16, BucketQueue::with_capacity(max_weight as u32))
}
(AblationQueue::Dial, AblationDistanceWidth::U32) => {
run!(u32, BucketQueue::with_capacity(max_weight as u32))
}
(AblationQueue::Dial, AblationDistanceWidth::U64) => {
run!(u64, BucketQueue::with_capacity(max_weight as u32))
}
(AblationQueue::BinaryHeap, AblationDistanceWidth::U16) => {
run!(u16, BinaryHeapQueue::<u64, u32>::new())
}
(AblationQueue::BinaryHeap, AblationDistanceWidth::U32) => {
run!(u32, BinaryHeapQueue::<u64, u32>::new())
}
(AblationQueue::BinaryHeap, AblationDistanceWidth::U64) => {
run!(u64, BinaryHeapQueue::<u64, u32>::new())
}
}
}
fn slice_int_search<T: ToU64Fast, Q: IntQueue, D: Dist>(
field: &[T],
shape: VolumeShape,
source: u64,
target: u64,
connectivity: Connectivity,
graph: Option<ConnectivityGraph<'_>>,
mut queue: Q,
) -> Result<Vec<u64>> {
let total = shape.total() as usize;
let mut distances = vec![D::MAX; total];
let mut parents = vec![0u32; total];
distances[source as usize] = D::ZERO;
queue.push_i(0, source 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;
while let Some((dist, loc)) = queue.pop_i() {
let loc_us = loc as usize;
if dist > distances[loc_us].to_priority() {
continue;
}
if loc as u64 == target {
return Ok(reconstruct_path_u32(&parents, source, target));
}
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) = crate::neighborhood::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;
}
}
let neighbor_cost = field[neighbor as usize].to_u64_fast();
let new_dist = current_dist.add_cost(neighbor_cost);
if new_dist < distances[neighbor as usize] {
distances[neighbor as usize] = new_dist;
parents[neighbor as usize] = loc + 1; queue.push_i(new_dist.to_priority(), neighbor as u32);
}
}
}
Err(Dijkstra3dError::Unreachable)
}
pub fn dijkstra_bidirectional_slice<T: ToF32Fast>(
field: &[T],
shape: VolumeShape,
source: u64,
target: u64,
connectivity: Connectivity,
graph: Option<ConnectivityGraph<'_>>,
) -> Result<Vec<u64>> {
let total = shape.total();
if field.len() as u64 != total {
return Err(Dijkstra3dError::InvalidInput(format!(
"dijkstra_bidirectional_slice: slice length {} != shape.total() {}",
field.len(),
total
)));
}
if source >= total {
return Err(Dijkstra3dError::OutOfBounds {
idx: source,
volume_size: total,
});
}
if target >= total {
return Err(Dijkstra3dError::OutOfBounds {
idx: target,
volume_size: total,
});
}
if source == target {
return Ok(vec![source]);
}
let field_tgt_f32 = field[target as usize].to_f32_fast();
let mut dist_fwd = vec![f32::INFINITY; total as usize];
let mut parents_fwd = vec![0u64; total as usize];
dist_fwd[source as usize] = 0.0;
let mut queue_fwd = BinaryHeapQueue::<f32, u64>::new();
queue_fwd.push(0.0, source);
let mut dist_bwd = vec![f32::INFINITY; total as usize];
let mut parents_bwd = vec![0u64; total as usize];
dist_bwd[target as usize] = 0.0;
let mut queue_bwd = BinaryHeapQueue::<f32, u64>::new();
queue_bwd.push(0.0, target);
let mut best_cost = f32::INFINITY;
let mut final_loc: Option<u64> = None;
let sx = shape.sx as i64;
let sxy = (shape.sx * shape.sy) as i64;
let offsets = neighborhood_offsets(sx, sxy);
let masks = neighborhood_masks();
let neighbor_count = connectivity.count();
let sx_u = shape.sx;
let sy_u = shape.sy;
let sz_u = shape.sz;
let mut forward = false;
loop {
let kf = match queue_fwd.peek() {
Some((k, _)) => k,
None => break,
};
let kb = match queue_bwd.peek() {
Some((k, _)) => k,
None => break,
};
if kf + kb >= best_cost {
break;
}
forward = !forward;
let (dist, loc) = if forward {
queue_fwd.pop().unwrap()
} else {
queue_bwd.pop().unwrap()
};
let loc_us = loc as usize;
if forward {
if dist > dist_fwd[loc_us] {
continue;
}
} else if dist > dist_bwd[loc_us] {
continue;
}
if forward {
if dist_bwd[loc_us].is_finite() {
let cost = dist_fwd[loc_us] + dist_bwd[loc_us] + field_tgt_f32
- field[loc_us].to_f32_fast();
if cost < best_cost {
best_cost = cost;
final_loc = Some(loc);
}
}
} else if dist_fwd[loc_us].is_finite() {
let cost =
dist_fwd[loc_us] + dist_bwd[loc_us] + field_tgt_f32 - field[loc_us].to_f32_fast();
if cost < best_cost {
best_cost = cost;
final_loc = Some(loc);
}
}
let (lx, ly, lz) = shape.coords(loc);
for i in 0..neighbor_count {
let (dx, dy, dz) = crate::neighborhood::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 as i64
|| ny < 0
|| ny >= sy_u as i64
|| nz < 0
|| nz >= sz_u as i64
{
continue;
}
let neighbor = (loc as i64 + offsets[i]) as u64;
if let Some(ref g) = graph {
if !g.allows(loc, masks[i]) {
continue;
}
}
let neighbor_cost_f32 = field[neighbor as usize].to_f32_fast();
if forward {
let new_dist = dist_fwd[loc_us] + neighbor_cost_f32;
if new_dist < dist_fwd[neighbor as usize] {
dist_fwd[neighbor as usize] = new_dist;
parents_fwd[neighbor as usize] = loc + 1;
queue_fwd.push(new_dist, neighbor);
if dist_bwd[neighbor as usize].is_finite() {
let cost = new_dist + dist_bwd[neighbor as usize] + field_tgt_f32
- neighbor_cost_f32;
if cost < best_cost {
best_cost = cost;
final_loc = Some(neighbor);
}
}
}
} else {
let new_dist = dist_bwd[loc_us] + neighbor_cost_f32;
if new_dist < dist_bwd[neighbor as usize] {
dist_bwd[neighbor as usize] = new_dist;
parents_bwd[neighbor as usize] = loc + 1;
queue_bwd.push(new_dist, neighbor);
if dist_fwd[neighbor as usize].is_finite() {
let cost = dist_fwd[neighbor as usize] + new_dist + field_tgt_f32
- neighbor_cost_f32;
if cost < best_cost {
best_cost = cost;
final_loc = Some(neighbor);
}
}
}
}
}
}
if let Some(meet) = final_loc {
let fwd = reconstruct_path(&parents_fwd, source, meet);
let bwd = reconstruct_path(&parents_bwd, target, meet);
let mut path = fwd;
path.extend(bwd.iter().rev().skip(1).copied());
Ok(path)
} else {
Err(Dijkstra3dError::Unreachable)
}
}
pub fn dijkstra_bidirectional_slice_int<T: ToU64Fast>(
field: &[T],
shape: VolumeShape,
source: u64,
target: u64,
connectivity: Connectivity,
graph: Option<ConnectivityGraph<'_>>,
) -> Result<Vec<u64>> {
let total = shape.total();
if field.len() as u64 != total {
return Err(Dijkstra3dError::InvalidInput(format!(
"dijkstra_bidirectional_slice_int: slice length {} != shape.total() {}",
field.len(),
total
)));
}
if total > u32::MAX as u64 {
return Err(Dijkstra3dError::InvalidInput(format!(
"dijkstra_bidirectional_slice_int: volume {total} exceeds u32::MAX voxels; \
use the u64/f32 path"
)));
}
if source >= total {
return Err(Dijkstra3dError::OutOfBounds {
idx: source,
volume_size: total,
});
}
if target >= total {
return Err(Dijkstra3dError::OutOfBounds {
idx: target,
volume_size: total,
});
}
if source == target {
return Ok(vec![source]);
}
let max_weight = field.iter().map(|&v| v.to_u64_fast()).max().unwrap_or(0);
let dist_bound = checked_int_distance_bound(shape, max_weight)?;
let use_u32 = dist_bound <= u32::MAX as u64;
let use_bucket = max_weight < 65_536;
match (use_bucket, use_u32) {
(true, true) => bidir_int_search::<_, _, u32>(
field,
shape,
source,
target,
connectivity,
graph,
BucketQueue::with_capacity(max_weight as u32),
BucketQueue::with_capacity(max_weight as u32),
),
(true, false) => bidir_int_search::<_, _, u64>(
field,
shape,
source,
target,
connectivity,
graph,
BucketQueue::with_capacity(max_weight as u32),
BucketQueue::with_capacity(max_weight as u32),
),
(false, true) => bidir_int_search::<_, _, u32>(
field,
shape,
source,
target,
connectivity,
graph,
BinaryHeapQueue::<u64, u32>::new(),
BinaryHeapQueue::<u64, u32>::new(),
),
(false, false) => bidir_int_search::<_, _, u64>(
field,
shape,
source,
target,
connectivity,
graph,
BinaryHeapQueue::<u64, u32>::new(),
BinaryHeapQueue::<u64, u32>::new(),
),
}
}
#[allow(clippy::too_many_arguments)]
fn bidir_int_search<T: ToU64Fast, Q: IntQueue, D: Dist>(
field: &[T],
shape: VolumeShape,
source: u64,
target: u64,
connectivity: Connectivity,
graph: Option<ConnectivityGraph<'_>>,
mut queue_fwd: Q,
mut queue_bwd: Q,
) -> Result<Vec<u64>> {
let total = shape.total() as usize;
let field_tgt = field[target as usize].to_u64_fast();
let mut dist_fwd = vec![D::MAX; total];
let mut parents_fwd = vec![0u32; total];
dist_fwd[source as usize] = D::ZERO;
queue_fwd.push_i(0, source as u32);
let mut dist_bwd = vec![D::MAX; total];
let mut parents_bwd = vec![0u32; total];
dist_bwd[target as usize] = D::ZERO;
queue_bwd.push_i(0, target as u32);
let mut best_cost: u64 = u64::MAX;
let mut final_loc: Option<u32> = None;
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;
loop {
let kf = match queue_fwd.peek_key_i() {
Some(k) => k,
None => break,
};
let kb = match queue_bwd.peek_key_i() {
Some(k) => k,
None => break,
};
if kf.saturating_add(kb) >= best_cost {
break;
}
let forward = kf <= kb;
let (dist, loc) = if forward {
queue_fwd.pop_i().unwrap()
} else {
queue_bwd.pop_i().unwrap()
};
let loc_us = loc as usize;
if forward {
if dist > dist_fwd[loc_us].to_priority() {
continue;
}
} else if dist > dist_bwd[loc_us].to_priority() {
continue;
}
let opp_reached = if forward {
dist_bwd[loc_us] != D::MAX
} else {
dist_fwd[loc_us] != D::MAX
};
if opp_reached {
let field_loc = field[loc_us].to_u64_fast();
let s = dist_fwd[loc_us]
.to_priority()
.saturating_add(dist_bwd[loc_us].to_priority())
.saturating_add(field_tgt);
let cost = s - field_loc;
if cost < best_cost {
best_cost = cost;
final_loc = Some(loc);
}
}
let (lx, ly, lz) = shape.coords(loc as u64);
for i in 0..neighbor_count {
let (dx, dy, dz) = crate::neighborhood::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;
let neighbor_us = neighbor as usize;
if let Some(ref g) = graph {
if !g.allows(loc as u64, masks[i]) {
continue;
}
}
let neighbor_cost = field[neighbor_us].to_u64_fast();
if forward {
let new_dist = dist_fwd[loc_us].add_cost(neighbor_cost);
if new_dist < dist_fwd[neighbor_us] {
dist_fwd[neighbor_us] = new_dist;
parents_fwd[neighbor_us] = loc + 1;
queue_fwd.push_i(new_dist.to_priority(), neighbor as u32);
if dist_bwd[neighbor_us] != D::MAX {
let s = new_dist
.to_priority()
.saturating_add(dist_bwd[neighbor_us].to_priority())
.saturating_add(field_tgt);
let cost = s - neighbor_cost;
if cost < best_cost {
best_cost = cost;
final_loc = Some(neighbor as u32);
}
}
}
} else {
let new_dist = dist_bwd[loc_us].add_cost(neighbor_cost);
if new_dist < dist_bwd[neighbor_us] {
dist_bwd[neighbor_us] = new_dist;
parents_bwd[neighbor_us] = loc + 1;
queue_bwd.push_i(new_dist.to_priority(), neighbor as u32);
if dist_fwd[neighbor_us] != D::MAX {
let s = dist_fwd[neighbor_us]
.to_priority()
.saturating_add(new_dist.to_priority())
.saturating_add(field_tgt);
let cost = s - neighbor_cost;
if cost < best_cost {
best_cost = cost;
final_loc = Some(neighbor as u32);
}
}
}
}
}
}
if let Some(meet) = final_loc {
let meet = meet as u64;
let fwd = reconstruct_path_u32(&parents_fwd, source, meet);
let bwd = reconstruct_path_u32(&parents_bwd, target, meet);
let mut path = fwd;
path.extend(bwd.iter().rev().skip(1).copied());
Ok(path)
} else {
Err(Dijkstra3dError::Unreachable)
}
}
pub fn dijkstra_compass_slice<T: ToF32Fast>(
field: &[T],
shape: VolumeShape,
source: u64,
target: u64,
connectivity: Connectivity,
anisotropy: Anisotropy,
graph: Option<ConnectivityGraph<'_>>,
) -> Result<Vec<u64>> {
let total = shape.total();
if field.len() as u64 != total {
return Err(Dijkstra3dError::InvalidInput(format!(
"dijkstra_compass_slice: slice length {} != shape.total() {}",
field.len(),
total
)));
}
if source >= total {
return Err(Dijkstra3dError::OutOfBounds {
idx: source,
volume_size: total,
});
}
if target >= total {
return Err(Dijkstra3dError::OutOfBounds {
idx: target,
volume_size: total,
});
}
if source == target {
return Ok(vec![source]);
}
let mut distances = vec![f32::INFINITY; total as usize];
let mut parents = vec![0u64; total as usize];
distances[source as usize] = 0.0;
let mut queue = BinaryHeapQueue::<f32, u64>::new();
let (tx, ty, tz) = shape.coords(target);
let (sx_coord, sy_coord, sz_coord) = shape.coords(source);
let h_source = euclidean_heuristic(sx_coord, sy_coord, sz_coord, tx, ty, tz, anisotropy);
queue.push(h_source, source);
let sx = shape.sx as i64;
let sxy = (shape.sx * shape.sy) as i64;
let offsets = neighborhood_offsets(sx, sxy);
let masks = neighborhood_masks();
let neighbor_count = connectivity.count();
let sx_u = shape.sx;
let sy_u = shape.sy;
let sz_u = shape.sz;
while let Some((_, loc)) = queue.pop() {
let current_g = distances[loc as usize];
if loc == target {
return Ok(reconstruct_path(&parents, source, target));
}
let (lx, ly, lz) = shape.coords(loc);
for i in 0..neighbor_count {
let (dx, dy, dz) = crate::neighborhood::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 as i64
|| ny < 0
|| ny >= sy_u as i64
|| nz < 0
|| nz >= sz_u as i64
{
continue;
}
let neighbor = (loc as i64 + offsets[i]) as u64;
if let Some(ref g) = graph {
if !g.allows(loc, masks[i]) {
continue;
}
}
let neighbor_cost_f32 = field[neighbor as usize].to_f32_fast();
let new_g = current_g + neighbor_cost_f32;
if new_g < distances[neighbor as usize] {
distances[neighbor as usize] = new_g;
parents[neighbor as usize] = loc + 1;
let h =
euclidean_heuristic(nx as u64, ny as u64, nz as u64, tx, ty, tz, anisotropy);
let f = new_g + h;
queue.push(f, neighbor);
}
}
}
Err(Dijkstra3dError::Unreachable)
}
struct BatchScratchInt<D: Dist> {
distances: Vec<D>,
parents: Vec<u32>,
}
impl<D: Dist> BatchScratchInt<D> {
fn new(total: usize) -> Self {
Self {
distances: vec![D::MAX; total],
parents: vec![0u32; total],
}
}
#[inline]
fn reset(&mut self) {
self.distances.iter_mut().for_each(|d| *d = D::MAX);
self.parents.iter_mut().for_each(|p| *p = 0);
}
}
fn slice_int_search_reuse<T: ToU64Fast, Q: IntQueue, D: Dist>(
field: &[T],
shape: VolumeShape,
source: u64,
target: u64,
connectivity: Connectivity,
scratch: &mut BatchScratchInt<D>,
mut queue: Q,
) -> Result<Vec<u64>> {
let out = {
let distances = &mut scratch.distances;
let parents = &mut scratch.parents;
distances[source as usize] = D::ZERO;
queue.push_i(0, source 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 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 result: Result<Vec<u64>> = Err(Dijkstra3dError::Unreachable);
while let Some((dist, loc)) = queue.pop_i() {
let loc_us = loc as usize;
if dist > distances[loc_us].to_priority() {
continue;
}
if loc as u64 == target {
result = Ok(reconstruct_path_u32(parents, source, target));
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) = crate::neighborhood::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;
let neighbor_us = neighbor as usize;
let neighbor_cost = field[neighbor_us].to_u64_fast();
let new_dist = current_dist.add_cost(neighbor_cost);
if new_dist < distances[neighbor_us] {
distances[neighbor_us] = new_dist;
parents[neighbor_us] = loc + 1; queue.push_i(new_dist.to_priority(), neighbor as u32);
}
}
}
result
};
scratch.reset();
out
}
pub fn dijkstra_batch_slice_int<T: ToU64Fast + Sync>(
field: &[T],
shape: VolumeShape,
pairs: &[(u64, u64)],
connectivity: Connectivity,
threads: Option<usize>,
) -> Vec<Result<Vec<u64>>> {
let total = shape.total();
let global_err = if field.len() as u64 != total {
Some(Dijkstra3dError::InvalidInput(format!(
"dijkstra_batch_slice_int: slice length {} != shape.total() {}",
field.len(),
total
)))
} else if total > u32::MAX as u64 {
Some(Dijkstra3dError::InvalidInput(format!(
"dijkstra_batch_slice_int: volume {total} exceeds u32::MAX voxels; \
use the u64/f32 path"
)))
} else {
None
};
if let Some(err) = global_err {
return pairs.iter().map(|_| Err(err.clone())).collect();
}
let max_weight = field.iter().map(|&v| v.to_u64_fast()).max().unwrap_or(0);
let dist_bound = match checked_int_distance_bound(shape, max_weight) {
Ok(bound) => bound,
Err(error) => return pairs.iter().map(|_| Err(error.clone())).collect(),
};
let use_u32 = dist_bound <= u32::MAX as u64;
let use_bucket = max_weight < 65_536;
run_batch_on_pool(threads, || match (use_bucket, use_u32) {
(true, true) => batch_int_run::<T, u32, _, _>(field, shape, pairs, connectivity, || {
BucketQueue::with_capacity(max_weight as u32)
}),
(true, false) => batch_int_run::<T, u64, _, _>(field, shape, pairs, connectivity, || {
BucketQueue::with_capacity(max_weight as u32)
}),
(false, true) => batch_int_run::<T, u32, _, _>(field, shape, pairs, connectivity, || {
BinaryHeapQueue::<u64, u32>::new()
}),
(false, false) => batch_int_run::<T, u64, _, _>(field, shape, pairs, connectivity, || {
BinaryHeapQueue::<u64, u32>::new()
}),
})
}
fn batch_int_run<T, D, Q, Mk>(
field: &[T],
shape: VolumeShape,
pairs: &[(u64, u64)],
connectivity: Connectivity,
make_queue: Mk,
) -> Vec<Result<Vec<u64>>>
where
T: ToU64Fast + Sync,
D: Dist,
Q: IntQueue,
Mk: Fn() -> Q + Sync + Send,
{
let total = shape.total();
pairs
.par_iter()
.map_init(
|| BatchScratchInt::<D>::new(total as usize),
|scratch, &(source, target)| {
if source >= total {
return Err(Dijkstra3dError::OutOfBounds {
idx: source,
volume_size: total,
});
}
if target >= total {
return Err(Dijkstra3dError::OutOfBounds {
idx: target,
volume_size: total,
});
}
if source == target {
return Ok(vec![source]);
}
slice_int_search_reuse::<T, Q, D>(
field,
shape,
source,
target,
connectivity,
scratch,
make_queue(),
)
},
)
.collect()
}
pub fn dijkstra_batch_slice<T: ToF32Fast + Sync>(
field: &[T],
shape: VolumeShape,
pairs: &[(u64, u64)],
connectivity: Connectivity,
threads: Option<usize>,
) -> Vec<Result<Vec<u64>>> {
run_batch_on_pool(threads, || {
pairs
.par_iter()
.map(|&(source, target)| {
dijkstra_unidirectional_slice(field, shape, source, target, connectivity, None)
})
.collect()
})
}
#[cfg(test)]
mod tests {
use super::*;
use crate::voxel::{ArrayView3Source, VolumeShape};
use ndarray::Array3;
fn ones_field(n: usize) -> Array3<u32> {
Array3::from_elem((n, n, n), 1u32)
}
fn run_ones(n: usize, conn: Connectivity) -> Vec<u64> {
let arr = ones_field(n);
let src = ArrayView3Source::new(arr.view());
let shape = VolumeShape::new(n as u64, n as u64, n as u64);
let s = shape.linear(0, 0, 0);
let t = shape.linear((n - 1) as u64, (n - 1) as u64, (n - 1) as u64);
let cfg = DijkstraConfig {
connectivity: conn,
anisotropy: Anisotropy::default(),
mode: Mode::Unidirectional,
};
dijkstra(&src, s, t, cfg, None).unwrap()
}
#[test]
fn ones_3x3x3_path_length_by_connectivity() {
assert_eq!(run_ones(3, Connectivity::Six).len(), 7);
assert_eq!(run_ones(3, Connectivity::Eighteen).len(), 4);
assert_eq!(run_ones(3, Connectivity::TwentySix).len(), 3);
}
#[test]
fn source_equals_target_returns_singleton() {
let arr = ones_field(5);
let src = ArrayView3Source::new(arr.view());
let shape = VolumeShape::new(5, 5, 5);
let s = shape.linear(2, 2, 2);
let path = dijkstra(&src, s, s, DijkstraConfig::default(), None).unwrap();
assert_eq!(path, vec![s]);
}
fn path_cost_u64<T: ToU64Fast>(field: &[T], path: &[u64]) -> u64 {
path.iter()
.skip(1)
.map(|&v| field[v as usize].to_u64_fast())
.sum()
}
fn path_cost_f32<T: ToF32Fast>(field: &[T], path: &[u64]) -> f64 {
path.iter()
.skip(1)
.map(|&v| field[v as usize].to_f32_fast() as f64)
.sum()
}
#[test]
fn int_slice_matches_float_slice_cost() {
use rand::rngs::StdRng;
use rand::{Rng, SeedableRng};
let n = 20usize;
let n_u = n as u64;
let shape = VolumeShape::new(n_u, n_u, n_u);
let src = shape.linear(0, 0, 0);
let tgt = shape.linear(n_u - 1, n_u - 1, n_u - 1);
let conns = [
Connectivity::Six,
Connectivity::Eighteen,
Connectivity::TwentySix,
];
macro_rules! check_dtype {
($t:ty, $lo:expr, $hi:expr, $seed_base:expr) => {{
for seed in 0..4u64 {
let mut rng = StdRng::seed_from_u64($seed_base + seed);
let field: Vec<$t> = (0..shape.total())
.map(|_| rng.random_range($lo..=$hi) as $t)
.collect();
for &conn in &conns {
let float_path =
dijkstra_unidirectional_slice(&field, shape, src, tgt, conn, None)
.unwrap();
let int_path =
dijkstra_unidirectional_slice_int(&field, shape, src, tgt, conn, None)
.unwrap();
assert_eq!(int_path.first(), Some(&src));
assert_eq!(int_path.last(), Some(&tgt));
let c_int = path_cost_u64(&field, &int_path);
let c_float_i = path_cost_u64(&field, &float_path);
assert_eq!(
c_int,
c_float_i,
"cost mismatch dtype={} seed={} conn={:?}: int={} float={}",
stringify!($t),
seed,
conn,
c_int,
c_float_i
);
let c_float_f = path_cost_f32(&field, &float_path);
assert!((c_float_f - c_int as f64).abs() < 1.0);
}
}
}};
}
check_dtype!(u8, 1u32, 255u32, 100);
check_dtype!(u16, 1u32, 60_000u32, 200);
check_dtype!(u32, 1u32, 1_000_000u32, 300);
}
#[test]
fn int_slice_ones_path_length_by_connectivity() {
let n = 3u64;
let shape = VolumeShape::new(n, n, n);
let field = vec![1u32; shape.total() as usize];
let src = shape.linear(0, 0, 0);
let tgt = shape.linear(2, 2, 2);
assert_eq!(
dijkstra_unidirectional_slice_int(&field, shape, src, tgt, Connectivity::Six, None)
.unwrap()
.len(),
7
);
assert_eq!(
dijkstra_unidirectional_slice_int(
&field,
shape,
src,
tgt,
Connectivity::Eighteen,
None
)
.unwrap()
.len(),
4
);
assert_eq!(
dijkstra_unidirectional_slice_int(
&field,
shape,
src,
tgt,
Connectivity::TwentySix,
None
)
.unwrap()
.len(),
3
);
}
#[test]
fn int_slice_heap_fallback_large_range() {
let n = 8u64;
let shape = VolumeShape::new(n, n, n);
let mut field = vec![1u32; shape.total() as usize];
field[10] = 1_000_000;
let src = shape.linear(0, 0, 0);
let tgt = shape.linear(7, 7, 7);
let int_path = dijkstra_unidirectional_slice_int(
&field,
shape,
src,
tgt,
Connectivity::TwentySix,
None,
)
.unwrap();
let float_path =
dijkstra_unidirectional_slice(&field, shape, src, tgt, Connectivity::TwentySix, None)
.unwrap();
assert_eq!(
path_cost_u64(&field, &int_path),
path_cost_u64(&field, &float_path)
);
}
#[test]
fn int_slice_rejects_unrepresentable_distance_bound() {
let shape = VolumeShape::new(2, 2, 2);
let field = vec![u64::MAX; shape.total() as usize];
let error = dijkstra_unidirectional_slice_int(
&field,
shape,
0,
shape.total() - 1,
Connectivity::TwentySix,
None,
)
.unwrap_err();
assert!(matches!(error, Dijkstra3dError::InvalidInput(_)));
}
#[test]
fn int_slice_source_equals_target() {
let shape = VolumeShape::new(4, 4, 4);
let field = vec![3u32; shape.total() as usize];
let s = shape.linear(1, 1, 1);
let path = dijkstra_unidirectional_slice_int(&field, shape, s, s, Connectivity::Six, None)
.unwrap();
assert_eq!(path, vec![s]);
}
#[test]
fn int_engine_distance_width_branches_exact_cost() {
let n = 8u64;
let shape = VolumeShape::new(n, n, n);
let src = shape.linear(0, 0, 0);
let tgt = shape.linear(n - 1, n - 1, n - 1);
let steps = n - 1;
let wa: u64 = 1_000_000_000;
let fa = vec![wa; (n * n * n) as usize];
let pa =
dijkstra_unidirectional_slice_int(&fa, shape, src, tgt, Connectivity::TwentySix, None)
.unwrap();
assert_eq!(path_cost_u64(&fa, &pa), steps * wa);
let wb: u32 = 150_000_000;
let fb = vec![wb; (n * n * n) as usize];
let pb =
dijkstra_unidirectional_slice_int(&fb, shape, src, tgt, Connectivity::TwentySix, None)
.unwrap();
assert_eq!(path_cost_u64(&fb, &pb), steps * wb as u64);
}
#[test]
fn dist_width_selector_boundaries() {
assert_eq!(select_dist_width(0), DistWidth::U16);
assert_eq!(select_dist_width(u16::MAX as u64), DistWidth::U16);
assert_eq!(select_dist_width(u16::MAX as u64 + 1), DistWidth::U32);
assert_eq!(select_dist_width(u32::MAX as u64), DistWidth::U32);
assert_eq!(select_dist_width(u32::MAX as u64 + 1), DistWidth::U64);
assert_eq!(select_dist_width(u64::MAX), DistWidth::U64);
}
#[test]
fn dist_width_u16_matches_u32_and_u64_paths() {
use rand::rngs::StdRng;
use rand::{Rng, SeedableRng};
let n = 16u64;
let shape = VolumeShape::new(n, n, n);
let src = shape.linear(0, 0, 0);
let tgt = shape.linear(n - 1, n - 1, n - 1);
let conns = [
Connectivity::Six,
Connectivity::Eighteen,
Connectivity::TwentySix,
];
for seed in 0..24u64 {
let mut rng = StdRng::seed_from_u64(0xD157_0000 + seed);
let field: Vec<u32> = (0..shape.total())
.map(|_| rng.random_range(1..=8u32))
.collect();
let max_w = field.iter().copied().max().unwrap() as u64;
let dist_bound = (shape.sx + shape.sy + shape.sz + 1) * max_w;
assert_eq!(
select_dist_width(dist_bound),
DistWidth::U16,
"seed {seed}: small-weight field should route to u16"
);
let cap = max_w as u32;
for &conn in &conns {
let p16 = slice_int_search::<_, _, u16>(
&field,
shape,
src,
tgt,
conn,
None,
BucketQueue::with_capacity(cap),
)
.unwrap();
let p32 = slice_int_search::<_, _, u32>(
&field,
shape,
src,
tgt,
conn,
None,
BucketQueue::with_capacity(cap),
)
.unwrap();
let p64 = slice_int_search::<_, _, u64>(
&field,
shape,
src,
tgt,
conn,
None,
BucketQueue::with_capacity(cap),
)
.unwrap();
assert_eq!(p16, p32, "u16 vs u32 differ seed={seed} conn={conn:?}");
assert_eq!(p16, p64, "u16 vs u64 differ seed={seed} conn={conn:?}");
let pub_path =
dijkstra_unidirectional_slice_int(&field, shape, src, tgt, conn, None).unwrap();
assert_eq!(
pub_path, p16,
"public path != forced-u16 seed={seed} conn={conn:?}"
);
}
}
}
#[test]
fn ablation_queue_width_factorial_preserves_path_cost() {
let shape = VolumeShape::new(12, 11, 10);
let field: Vec<u16> = (0..shape.total())
.map(|index| 1 + ((index * 17 + 3) % 8) as u16)
.collect();
let source = shape.linear(0, 0, 0);
let target = shape.linear(11, 10, 9);
let reference = dijkstra_unidirectional_slice_int(
&field,
shape,
source,
target,
Connectivity::Six,
None,
)
.unwrap();
let reference_cost = path_cost_u64(&field, &reference);
for queue in [AblationQueue::Dial, AblationQueue::BinaryHeap] {
for width in [
AblationDistanceWidth::U16,
AblationDistanceWidth::U32,
AblationDistanceWidth::U64,
] {
let path = dijkstra_unidirectional_slice_int_ablation(
&field,
shape,
source,
target,
Connectivity::Six,
None,
queue,
width,
)
.unwrap();
assert_eq!(path_cost_u64(&field, &path), reference_cost);
}
}
}
#[test]
fn ablation_rejects_unsafe_forced_distance_width() {
let shape = VolumeShape::new(64, 64, 64);
let field = vec![1_000u16; shape.total() as usize];
let error = dijkstra_unidirectional_slice_int_ablation(
&field,
shape,
0,
shape.total() - 1,
Connectivity::Six,
None,
AblationQueue::Dial,
AblationDistanceWidth::U16,
)
.unwrap_err();
assert!(matches!(error, Dijkstra3dError::InvalidInput(_)));
}
#[test]
fn int_engine_u16_width_exact_cost() {
let n = 32u64;
let shape = VolumeShape::new(n, n, n);
let src = shape.linear(0, 0, 0);
let tgt = shape.linear(n - 1, n - 1, n - 1);
let w: u32 = 20;
let dist_bound = (shape.sx + shape.sy + shape.sz + 1) * w as u64;
assert_eq!(select_dist_width(dist_bound), DistWidth::U16);
let field = vec![w; (n * n * n) as usize];
let p = dijkstra_unidirectional_slice_int(
&field,
shape,
src,
tgt,
Connectivity::TwentySix,
None,
)
.unwrap();
assert_eq!(path_cost_u64(&field, &p), (n - 1) * w as u64);
}
fn assert_contiguous(shape: VolumeShape, path: &[u64], conn: Connectivity) {
for w in path.windows(2) {
let (ax, ay, az) = shape.coords(w[0]);
let (bx, by, bz) = shape.coords(w[1]);
let dx = (ax as i64 - bx as i64).abs();
let dy = (ay as i64 - by as i64).abs();
let dz = (az as i64 - bz as i64).abs();
assert!(
dx <= 1 && dy <= 1 && dz <= 1,
"non-adjacent step {:?}->{:?}",
w[0],
w[1]
);
let l1 = dx + dy + dz;
assert!(l1 >= 1, "duplicate consecutive voxel {}", w[0]);
let ok = match conn {
Connectivity::Six => l1 == 1,
Connectivity::Eighteen => l1 <= 2,
Connectivity::TwentySix => true,
};
assert!(ok, "step violates connectivity {:?}: l1={}", conn, l1);
}
}
#[test]
fn bidirectional_int_is_optimal_2000() {
use rand::rngs::StdRng;
use rand::{Rng, SeedableRng};
let conns = [
Connectivity::Six,
Connectivity::Eighteen,
Connectivity::TwentySix,
];
let mut trials = 0usize;
let mut rng = StdRng::seed_from_u64(0xB1D14EC7);
for iter in 0..3000u64 {
let a = rng.random_range(2u64..=16);
let b = rng.random_range(2u64..=16);
let c = rng.random_range(2u64..=16);
let shape = VolumeShape::new(a, b, c);
let total = shape.total();
let src = rng.random_range(0..total);
let mut tgt = rng.random_range(0..total);
while tgt == src {
tgt = rng.random_range(0..total);
}
let conn = conns[(iter % 3) as usize];
macro_rules! run {
($t:ty, $hi:expr) => {{
let field: Vec<$t> = (0..total)
.map(|_| rng.random_range(1..=$hi) as $t)
.collect();
let bi = dijkstra_bidirectional_slice_int(&field, shape, src, tgt, conn, None)
.unwrap();
let uni =
dijkstra_unidirectional_slice_int(&field, shape, src, tgt, conn, None)
.unwrap();
let bif =
dijkstra_bidirectional_slice(&field, shape, src, tgt, conn, None).unwrap();
assert_eq!(bi.first(), Some(&src), "bad src endpoint");
assert_eq!(bi.last(), Some(&tgt), "bad tgt endpoint");
assert_contiguous(shape, &bi, conn);
let c_bi = path_cost_u64(&field, &bi);
let c_uni = path_cost_u64(&field, &uni);
let c_bif = path_cost_u64(&field, &bif);
assert_eq!(
c_bi, c_uni,
"SUBOPTIMAL int bidir: dims=({},{},{}) src={} tgt={} conn={:?} \
bidir={} optimum={}",
a, b, c, src, tgt, conn, c_bi, c_uni
);
assert_eq!(
c_bif, c_uni,
"SUBOPTIMAL f32 bidir: dims=({},{},{}) src={} tgt={} conn={:?} \
bidir={} optimum={}",
a, b, c, src, tgt, conn, c_bif, c_uni
);
trials += 1;
}};
}
match iter % 3 {
0 => run!(u8, 8u32),
1 => run!(u8, 255u32),
_ => run!(u16, 1000u32),
}
}
assert!(trials >= 2000, "only ran {} trials", trials);
}
#[test]
fn bidirectional_matches_unidirectional_on_tied_field() {
let shape = VolumeShape::new(3, 3, 3);
let field: Vec<u8> = vec![
1, 3, 1, 4, 3, 4, 3, 2, 4, 1, 3, 1, 2, 3, 2, 3, 3, 2, 1, 4, 4, 3, 4, 1, 3, 3, 3,
];
let src = shape.linear(0, 0, 0);
let tgt = shape.linear(2, 2, 2);
let conn = Connectivity::TwentySix;
let bi = dijkstra_bidirectional_slice_int(&field, shape, src, tgt, conn, None).unwrap();
let bif = dijkstra_bidirectional_slice(&field, shape, src, tgt, conn, None).unwrap();
let uni = dijkstra_unidirectional_slice_int(&field, shape, src, tgt, conn, None).unwrap();
assert_eq!(path_cost_u64(&field, &bi), 6);
assert_eq!(path_cost_u64(&field, &bif), 6);
assert_eq!(path_cost_u64(&field, &uni), 6);
}
#[test]
fn bidirectional_int_rejects_unrepresentable_distance_bound() {
let shape = VolumeShape::new(2, 2, 2);
let field = vec![u64::MAX; shape.total() as usize];
let error = dijkstra_bidirectional_slice_int(
&field,
shape,
0,
shape.total() - 1,
Connectivity::Six,
None,
)
.unwrap_err();
assert!(matches!(error, Dijkstra3dError::InvalidInput(_)));
}
use proptest::prelude::*;
proptest! {
#![proptest_config(ProptestConfig::with_cases(400))]
#[test]
fn prop_int_engine_cost_matches_float(
a in 2u64..=5, b in 2u64..=5, c in 2u64..=5,
weights in prop::collection::vec(1u16..=2000, 125),
conn_idx in 0usize..3,
) {
let total = (a * b * c) as usize;
let field: Vec<u16> = weights[..total].to_vec();
let shape = VolumeShape::new(a, b, c);
let src = shape.linear(0, 0, 0);
let tgt = shape.linear(a - 1, b - 1, c - 1);
let conn = [
Connectivity::Six,
Connectivity::Eighteen,
Connectivity::TwentySix,
][conn_idx];
let ip =
dijkstra_unidirectional_slice_int(&field, shape, src, tgt, conn, None).unwrap();
let fp =
dijkstra_unidirectional_slice(&field, shape, src, tgt, conn, None).unwrap();
prop_assert_eq!(path_cost_u64(&field, &ip), path_cost_u64(&field, &fp));
}
}
#[test]
fn batch_int_matches_single_call_paths() {
use rand::rngs::StdRng;
use rand::{Rng, SeedableRng};
let n = 24usize;
let n_u = n as u64;
let shape = VolumeShape::new(n_u, n_u, n_u);
let total = shape.total();
let conns = [
Connectivity::Six,
Connectivity::Eighteen,
Connectivity::TwentySix,
];
macro_rules! check_dtype {
($t:ty, $hi:expr, $seed:expr) => {{
let mut rng = StdRng::seed_from_u64($seed);
let field: Vec<$t> =
(0..total).map(|_| rng.random_range(1..=$hi) as $t).collect();
let mut pairs: Vec<(u64, u64)> = (0..40)
.map(|_| {
let s = rng.random_range(0..total);
let t = rng.random_range(0..total);
(s, t)
})
.collect();
pairs.push((7, 7)); pairs.push((total, 0));
for &conn in &conns {
let batch = dijkstra_batch_slice_int(&field, shape, &pairs, conn, None);
assert_eq!(batch.len(), pairs.len());
for (i, &(s, t)) in pairs.iter().enumerate() {
let single =
dijkstra_unidirectional_slice_int(&field, shape, s, t, conn, None);
match (&batch[i], &single) {
(Ok(bp), Ok(sp)) => assert_eq!(
bp, sp,
"path mismatch dtype={} conn={:?} pair=({},{})",
stringify!($t), conn, s, t
),
(Err(be), Err(se)) => assert_eq!(be, se),
_ => panic!(
"ok/err mismatch dtype={} conn={:?} pair=({},{}): batch={:?} single={:?}",
stringify!($t), conn, s, t, batch[i], single
),
}
}
}
}};
}
check_dtype!(u8, 8u32, 1); check_dtype!(u8, 255u32, 2);
check_dtype!(u16, 60_000u32, 3); check_dtype!(u32, 1_000_000u32, 4); }
#[test]
fn batch_float_matches_single_call_paths() {
use rand::rngs::StdRng;
use rand::{Rng, SeedableRng};
let n = 16usize;
let n_u = n as u64;
let shape = VolumeShape::new(n_u, n_u, n_u);
let total = shape.total();
let mut rng = StdRng::seed_from_u64(0xF10A7);
let field: Vec<f32> = (0..total)
.map(|_| rng.random_range(1.0f32..=100.0f32))
.collect();
let pairs: Vec<(u64, u64)> = (0..24)
.map(|_| (rng.random_range(0..total), rng.random_range(0..total)))
.collect();
for &conn in &[Connectivity::Six, Connectivity::TwentySix] {
let batch = dijkstra_batch_slice(&field, shape, &pairs, conn, None);
for (i, &(s, t)) in pairs.iter().enumerate() {
let single = dijkstra_unidirectional_slice(&field, shape, s, t, conn, None);
match (&batch[i], &single) {
(Ok(bp), Ok(sp)) => assert_eq!(bp, sp),
(Err(_), Err(_)) => {}
_ => panic!("ok/err mismatch pair=({},{})", s, t),
}
}
}
}
#[test]
fn batch_int_global_error_is_per_pair() {
let shape = VolumeShape::new(4, 4, 4);
let field = vec![1u32; 10]; let pairs = vec![(0u64, 5u64), (1, 2), (3, 4)];
let out = dijkstra_batch_slice_int(&field, shape, &pairs, Connectivity::TwentySix, Some(0));
assert_eq!(out.len(), pairs.len());
for r in &out {
assert!(matches!(r, Err(Dijkstra3dError::InvalidInput(_))));
}
}
#[test]
fn batch_int_distance_bound_error_is_per_pair() {
let shape = VolumeShape::new(2, 2, 2);
let field = vec![u64::MAX; shape.total() as usize];
let pairs = [(0, shape.total() - 1), (1, 2)];
let output = dijkstra_batch_slice_int(&field, shape, &pairs, Connectivity::Six, None);
assert_eq!(output.len(), pairs.len());
assert!(output
.iter()
.all(|result| matches!(result, Err(Dijkstra3dError::InvalidInput(_)))));
}
#[test]
fn batch_int_mixed_pairs_independent() {
let shape = VolumeShape::new(5, 5, 5);
let field = vec![2u32; shape.total() as usize];
let s = shape.linear(0, 0, 0);
let t = shape.linear(4, 4, 4);
let pairs = vec![(s, t), (s, s), (t, s)];
let out = dijkstra_batch_slice_int(&field, shape, &pairs, Connectivity::TwentySix, None);
assert_eq!(out.len(), 3);
assert_eq!(out[0].as_ref().unwrap().first(), Some(&s));
assert_eq!(out[0].as_ref().unwrap().last(), Some(&t));
assert_eq!(out[1].as_ref().unwrap(), &vec![s]); assert_eq!(out[2].as_ref().unwrap().first(), Some(&t));
assert_eq!(out[2].as_ref().unwrap().last(), Some(&s));
}
#[test]
fn compass_gate_classifies_workloads() {
use rand::rngs::StdRng;
use rand::{Rng, SeedableRng};
let n = 48u64;
let shape = VolumeShape::new(n, n, n);
let src = shape.linear(0, 0, 0);
let tgt = shape.linear(n - 1, n - 1, n - 1);
let aniso = Anisotropy::default();
let total = shape.total() as usize;
let mut rng = StdRng::seed_from_u64(0xC0FFEE);
let f_uniform: Vec<u8> = (0..total)
.map(|_| rng.random_range(1..=255u32) as u8)
.collect();
assert!(
!compass_heuristic_is_informative(&f_uniform, shape, src, tgt, aniso),
"random_uniform should route to unidirectional"
);
let f_small: Vec<u8> = (0..total)
.map(|_| rng.random_range(1..=8u32) as u8)
.collect();
assert!(
compass_heuristic_is_informative(&f_small, shape, src, tgt, aniso),
"smallweight should keep compass"
);
let mut f_bimodal: Vec<u32> = (0..total).map(|_| rng.random_range(1..=8u32)).collect();
for v in f_bimodal.iter_mut() {
if rng.random::<f32>() < 0.02 {
*v = 200_000;
}
}
assert!(
compass_heuristic_is_informative(&f_bimodal, shape, src, tgt, aniso),
"bimodal should keep compass despite a high mean"
);
let mut f_maze: Vec<u8> = vec![255u8; total];
for y in (0..n).step_by(2) {
for z in 0..n {
for x in 0..n {
f_maze[shape.linear(x, y, z) as usize] = 1;
}
}
}
assert!(
!compass_heuristic_is_informative(&f_maze, shape, src, tgt, aniso),
"maze should route to unidirectional (walls block the straight line)"
);
let f_plateau: Vec<u32> = vec![7u32; total];
assert!(
!compass_heuristic_is_informative(&f_plateau, shape, src, tgt, aniso),
"plateau should route to unidirectional"
);
}
#[test]
fn compass_gate_source_equals_target_is_safe() {
let shape = VolumeShape::new(4, 4, 4);
let field = vec![3u8; shape.total() as usize];
let s = shape.linear(1, 1, 1);
assert!(compass_heuristic_is_informative(
&field,
shape,
s,
s,
Anisotropy::default()
));
}
#[test]
fn batch_int_output_pool_independent() {
use rand::rngs::StdRng;
use rand::{Rng, SeedableRng};
let shape = VolumeShape::new(20, 18, 16);
let total = shape.total();
let mut rng = StdRng::seed_from_u64(0xBA7C_4001);
let field: Vec<u16> = (0..total).map(|_| rng.random_range(1..=200u16)).collect();
let pairs: Vec<(u64, u64)> = (0..40)
.map(|_| (rng.random_range(0..total), rng.random_range(0..total)))
.collect();
let conn = Connectivity::TwentySix;
let auto = dijkstra_batch_slice_int(&field, shape, &pairs, conn, None);
let global = dijkstra_batch_slice_int(&field, shape, &pairs, conn, Some(0));
let pinned = dijkstra_batch_slice_int(&field, shape, &pairs, conn, Some(2));
assert_eq!(auto, global, "auto vs global pool output differs");
assert_eq!(auto, pinned, "auto vs pinned pool output differs");
}
}