use std::sync::atomic::{AtomicUsize, Ordering};
use crate::partition::Partition;
const ITEMS_PER_WORKER: usize = 32;
#[allow(clippy::too_many_arguments)]
pub(crate) fn walk(
j: usize,
stop: usize,
left: u32,
prev: u32,
mu: &[u32],
strips: usize,
cand: &mut Vec<u32>,
leaf: &mut impl FnMut(&[u32], u32),
) {
if j == stop {
leaf(&cand[..stop], left);
return;
}
let at = |i: usize| mu.get(i).copied().unwrap_or(0);
let lo = at(j);
let hi = if j < strips {
prev.min(left + lo)
} else {
at(j - strips).min(prev).min(left + lo)
};
if hi < lo {
return;
}
for v in lo..=hi {
cand[j] = v;
walk(j + 1, stop, left - (v - lo), v, mu, strips, cand, leaf);
}
cand[j] = 0;
}
pub(crate) fn count_all<F>(
mu: &[u32],
strips: usize,
total: u32,
threads: usize,
make_counter: impl Fn() -> F + Sync,
) -> Vec<(Partition, u128)>
where
F: FnMut(&[u32]) -> u128,
{
let rows = mu.len() + strips;
let split = rows.min(2);
let mut items: Vec<([u32; 2], u32)> = Vec::new();
{
let mut cand = vec![0u32; rows];
walk(
0,
split,
total,
u32::MAX,
mu,
strips,
&mut cand,
&mut |c, left| {
items.push(([c[0], c.get(1).copied().unwrap_or(0)], left));
},
);
}
let threads = threads.min(items.len() / ITEMS_PER_WORKER).max(1);
let run = |counter: &mut F,
cand: &mut Vec<u32>,
out: &mut Vec<(Partition, u128)>,
item: ([u32; 2], u32)| {
let ([v0, v1], left) = item;
cand[..split].copy_from_slice(&[v0, v1][..split]);
let prev = if split == 0 {
u32::MAX
} else {
cand[split - 1]
};
walk(split, rows, left, prev, mu, strips, cand, &mut |c, left| {
if left != 0 {
return;
}
let end = c.iter().rposition(|&x| x > 0).map_or(0, |i| i + 1);
let k = counter(&c[..end]);
if k > 0 {
out.push((Partition::new(c[..end].iter().copied()), k));
}
});
cand[..split].fill(0);
};
let mut out = if threads <= 1 {
let mut counter = make_counter();
let mut cand = vec![0u32; rows];
let mut out = Vec::new();
for &item in &items {
run(&mut counter, &mut cand, &mut out, item);
}
out
} else {
let cursor = AtomicUsize::new(0);
let parts: Vec<Vec<(Partition, u128)>> = std::thread::scope(|s| {
let handles: Vec<_> = (0..threads)
.map(|_| {
let (cursor, items, run, make_counter) = (&cursor, &items, &run, &make_counter);
s.spawn(move || {
let mut counter = make_counter();
let mut cand = vec![0u32; rows];
let mut out = Vec::new();
loop {
let i = cursor.fetch_add(1, Ordering::Relaxed);
if i >= items.len() {
break;
}
run(&mut counter, &mut cand, &mut out, items[i]);
}
out
})
})
.collect();
handles
.into_iter()
.map(|h| h.join().unwrap_or_else(|e| std::panic::resume_unwind(e)))
.collect()
});
parts.into_iter().flatten().collect()
};
out.sort_by(|x, y| x.0.cmp(&y.0));
out
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn walk_visits_each_admissible_candidate_once_in_order() {
use crate::partition::partitions_of;
for (mu, strips, total) in [
(vec![3u32, 1], 2usize, 4u32),
(vec![4, 2, 1], 3, 5),
(vec![2, 2], 2, 6),
(vec![], 3, 4),
(vec![5], 2, 1),
] {
let rows = mu.len() + strips;
let mut seen = Vec::new();
let mut cand = vec![0u32; rows];
walk(
0,
rows,
total,
u32::MAX,
&mu,
strips,
&mut cand,
&mut |c, left| {
if left == 0 {
let end = c.iter().rposition(|&x| x > 0).map_or(0, |i| i + 1);
seen.push(c[..end].to_vec());
}
},
);
assert!(cand.iter().all(|&x| x == 0), "walk left cand dirty");
let n = mu.iter().sum::<u32>() + total;
let at = |v: &[u32], i: usize| v.get(i).copied().unwrap_or(0);
let mut want: Vec<Vec<u32>> = partitions_of(n)
.into_iter()
.map(|p| p.parts().to_vec())
.filter(|lam| {
lam.len() <= rows
&& (0..rows).all(|j| {
at(lam, j) >= at(&mu, j)
&& (j < strips || at(lam, j) <= at(&mu, j - strips))
})
})
.collect();
want.sort();
assert_eq!(seen, want, "μ = {mu:?}, {strips} strips, {total} cells");
}
}
#[test]
fn count_all_does_not_depend_on_the_thread_count() {
let make = || {
|lam: &[u32]| {
u128::from(if lam[0].is_multiple_of(2) {
1
} else {
lam.len() as u32
})
}
};
let mu = vec![20u32, 16, 12];
let one = count_all(&mu, 3, 48, 1, make);
let many = count_all(&mu, 3, 48, 4, make);
assert_eq!(one, many);
assert!(one.len() > 1000, "expected a real sweep, got {}", one.len());
assert!(
one.windows(2).all(|w| w[0].0 < w[1].0),
"terms must be sorted and distinct"
);
}
#[test]
fn a_worker_panic_is_re_raised_with_its_payload() {
let make = || {
|lam: &[u32]| -> u128 {
if lam[0] == 30 {
panic!("counter refused λ₁ = 30");
}
1
}
};
let mu = vec![20u32, 16, 12];
let err = std::panic::catch_unwind(|| count_all(&mu, 3, 48, 4, make)).unwrap_err();
let msg = err
.downcast_ref::<&str>()
.map(|s| (*s).to_string())
.or_else(|| err.downcast_ref::<String>().cloned())
.unwrap_or_default();
assert_eq!(msg, "counter refused λ₁ = 30");
}
}