Skip to main content

linkcell/
partition.rs

1//! Domain partition of the periodic cell grid.
2//!
3//! The mesh is the one [`pairs_within`](crate::pairs_within) builds for
4//! the same cutoff. A cell weight is the number of points in that bin.
5//! An edge weight is the number of cutoff pairs with one end in each
6//! bin. [`partition_graph`] cuts that graph. [`halo`] lists the ghost
7//! bins of one part.
8//!
9//! With `balance: None`, a part may exceed the ideal share by at most
10//! the heaviest cell. That is `1 + parts * w_max / total`. The same
11//! formula is used for every system. Serial Scotch is the `scotch`
12//! feature. Distributed Scotch is the `ptscotch` feature. Both are off
13//! unless compiled in.
14
15// The kernels take the grid, the geometry and the part bounds as separate
16// arguments, as the recursive splits pass them down.
17#![allow(clippy::too_many_arguments, clippy::type_complexity)]
18
19use std::cmp::Ordering;
20use std::collections::BTreeMap;
21use std::collections::BinaryHeap;
22use std::sync::atomic::{AtomicU64, Ordering as AtomicOrdering};
23use std::sync::OnceLock;
24use std::time::Instant;
25
26use crate::bins::{self, flat_cell};
27use crate::cell::Cell;
28use crate::pairs::{self, pairs_within};
29use crate::Error;
30
31/// Smallest advance `Instant` reported on this process.
32///
33/// The join classifier uses one tick of this clock. The value is the
34/// median of 32 observed steps, so it is the host timer, not a constant
35/// chosen per system.
36pub fn timer_resolution_ns() -> u64 {
37    static TICK: OnceLock<u64> = OnceLock::new();
38    *TICK.get_or_init(|| {
39        let mut samples = [1u64; 32];
40        for slot in &mut samples {
41            let start = Instant::now();
42            let mut next = Instant::now();
43            let mut spins = 0u32;
44            while next <= start && spins < 1_000_000 {
45                next = Instant::now();
46                spins += 1;
47            }
48            *slot = next.saturating_duration_since(start).as_nanos() as u64;
49            if *slot == 0 {
50                *slot = 1;
51            }
52        }
53        samples.sort_unstable();
54        samples[samples.len() / 2]
55    })
56}
57
58/// Balance allowed by one indivisible cell.
59///
60/// A weighted median gives the straddling cell to one part. That part
61/// may therefore exceed the ideal share `total / parts` by at most the
62/// heaviest cell `w_max`. The bound is `(total + parts * w_max) / total`,
63/// which is `1 + parts * w_max / total`. No cell-aligned cut can promise
64/// a tighter bound. `lc_partition` selects it when `balance <= 0`, which
65/// is the same per-frame rule the d-SEAMS domain driver derives.
66/// The same formula is used for every system. `balance: None` selects it.
67pub fn derived_balance(weight: &[u64], parts: u32) -> (u64, u64) {
68    let total: u64 = weight.iter().copied().sum();
69    if total == 0 || parts == 0 {
70        return (1, 1);
71    }
72    let w_max = weight.iter().copied().max().unwrap_or(0);
73    let extra = u64::from(parts).saturating_mul(w_max);
74    (total.saturating_add(extra), total)
75}
76
77/// The derived bound as a real ratio, for drivers that take a float.
78pub fn derived_balance_f64(weight: &[u64], parts: u32) -> f64 {
79    let (num, den) = derived_balance(weight, parts);
80    if den == 0 {
81        1.0
82    } else {
83        num as f64 / den as f64
84    }
85}
86
87/// How [`partition_graph`] cuts the cell graph.
88#[derive(Clone, Copy, Debug, Eq, PartialEq)]
89#[repr(u8)]
90pub enum Method {
91    /// Morton order, then a weighted prefix split.
92    Morton = 0,
93    /// Hilbert order, then a weighted prefix split.
94    Hilbert = 1,
95    /// Weighted recursive coordinate bisection.
96    Rcb = 2,
97    /// Hilbert prefix split, then Fiduccia-Mattheyses.
98    HilbertFm = 3,
99    /// Recursive coordinate bisection, then Fiduccia-Mattheyses.
100    RcbFm = 4,
101    /// Serial Scotch `SCOTCH_graphPart`, feature `scotch` only.
102    Scotch = 5,
103    /// Heavy-edge coarsening, coarse bisection, refinement on the way back.
104    Multi = 6,
105    /// PT-Scotch `SCOTCH_dgraphPart`, feature `ptscotch` only.
106    PtScotch = 7,
107}
108
109impl Method {
110    /// True when the initial cut is a curve prefix.
111    pub fn uses_curve(self) -> bool {
112        matches!(self, Method::Morton | Method::Hilbert | Method::HilbertFm)
113    }
114
115    /// True when a Fiduccia-Mattheyses pass follows the initial cut.
116    pub fn refines(self) -> bool {
117        matches!(self, Method::HilbertFm | Method::RcbFm)
118    }
119
120    /// True when the cut reads pair-count arcs.
121    ///
122    /// A plain recursive coordinate bisection and a curve prefix use the
123    /// link-cell point counts only. Refinement, coarsening, and Scotch
124    /// walk the arcs, so those methods still build them.
125    fn needs_edges(self) -> bool {
126        matches!(
127            self,
128            Method::HilbertFm | Method::RcbFm | Method::Scotch | Method::PtScotch | Method::Multi
129        )
130    }
131
132    fn from_code(code: u8) -> Result<Self, Error> {
133        match code {
134            0 => Ok(Method::Morton),
135            1 => Ok(Method::Hilbert),
136            2 => Ok(Method::Rcb),
137            3 => Ok(Method::HilbertFm),
138            4 => Ok(Method::RcbFm),
139            5 => Ok(Method::Scotch),
140            6 => Ok(Method::Multi),
141            7 => Ok(Method::PtScotch),
142            _ => Err(Error::BadPartition),
143        }
144    }
145}
146
147/// Default method.
148///
149/// The panel sums edge cuts over the five systems. The default is the
150/// native method with the smallest sum among those that stay within
151/// the balance bound on every system. A tie breaks toward the smaller
152/// sum of median wall times.
153pub const DEFAULT_METHOD: Method = Method::RcbFm;
154
155/// One call to [`partition`] or [`partition_graph`].
156#[derive(Clone, Copy, Debug, PartialEq)]
157pub struct PartRequest {
158    /// Number of domains. Must be at least 1.
159    pub parts: u32,
160    /// Cut to run.
161    pub method: Method,
162    /// `None` selects [`derived_balance`] for these cell weights.
163    pub balance: Option<f64>,
164    /// Run weights, curve keys, and the prefix split on the device.
165    pub device: bool,
166}
167
168impl PartRequest {
169    /// `parts` domains, [`DEFAULT_METHOD`], the default balance, on the host.
170    pub fn new(parts: u32) -> Self {
171        Self {
172            parts,
173            method: DEFAULT_METHOD,
174            balance: None,
175            device: false,
176        }
177    }
178}
179
180/// Fractional bins and the point count in each bin.
181#[derive(Clone, Debug, PartialEq)]
182pub struct CellGrid {
183    /// Bins along the first lattice axis.
184    pub nx: i32,
185    /// Bins along the second lattice axis.
186    pub ny: i32,
187    /// Bins along the third lattice axis.
188    pub nz: i32,
189    /// Perpendicular width of one bin on each axis.
190    pub bin_width: [f64; 3],
191    /// Point count of cell `((iz * ny) + iy) * nx + ix`.
192    pub weight: Vec<u64>,
193}
194
195impl CellGrid {
196    /// Number of bins.
197    pub fn ncell(&self) -> usize {
198        self.weight.len()
199    }
200}
201
202/// Place `copies` disjoint copies of `graph` side by side along x.
203///
204/// Cell count and arc count both equal the base counts times `copies`.
205/// Each copy keeps the base neighbourhood, so the work per copy stays
206/// the base cell count and the base arc count.
207pub fn replicate_graph(graph: &CellGraph, copies: usize) -> Result<CellGraph, Error> {
208    if copies == 0 {
209        return Err(Error::BadGraph);
210    }
211    if copies == 1 {
212        return Ok(graph.clone());
213    }
214    let nx = graph.grid.nx;
215    let ny = graph.grid.ny;
216    let nz = graph.grid.nz;
217    if nx <= 0 || ny <= 0 || nz <= 0 {
218        return Err(Error::BadGraph);
219    }
220    let n = graph.grid.ncell();
221    let expect = (nx as usize)
222        .checked_mul(ny as usize)
223        .and_then(|v| v.checked_mul(nz as usize))
224        .ok_or(Error::BadGraph)?;
225    if expect != n || graph.offsets.len() != n + 1 {
226        return Err(Error::BadGraph);
227    }
228    let copies_i = i32::try_from(copies).map_err(|_| Error::BadGraph)?;
229    let big_nx = nx.checked_mul(copies_i).ok_or(Error::BadGraph)?;
230    let big_n = n.checked_mul(copies).ok_or(Error::BadGraph)?;
231    let nx_u = nx as usize;
232    let ny_u = ny as usize;
233    let big_nx_u = big_nx as usize;
234    let mut weight = vec![0u64; big_n];
235    for copy in 0..copies {
236        for iz in 0..nz as usize {
237            for iy in 0..ny_u {
238                for ix in 0..nx_u {
239                    let src = ((iz * ny_u) + iy) * nx_u + ix;
240                    let dst = ((iz * ny_u) + iy) * big_nx_u + copy * nx_u + ix;
241                    weight[dst] = graph.grid.weight[src];
242                }
243            }
244        }
245    }
246    let mut neighbor = Vec::with_capacity(graph.neighbor.len().saturating_mul(copies));
247    let mut edge_weight = Vec::with_capacity(graph.edge_weight.len().saturating_mul(copies));
248    let mut offsets = vec![0u32; big_n + 1];
249    for dst in 0..big_n {
250        let plane = big_nx_u * ny_u;
251        let iz = dst / plane;
252        let rem = dst % plane;
253        let iy = rem / big_nx_u;
254        let ix_big = rem % big_nx_u;
255        let copy = ix_big / nx_u;
256        let ix = ix_big % nx_u;
257        let src = ((iz * ny_u) + iy) * nx_u + ix;
258        let lo = graph.offsets[src] as usize;
259        let hi = graph.offsets[src + 1] as usize;
260        for edge in lo..hi {
261            let nbr = graph.neighbor[edge] as usize;
262            if nbr >= n {
263                return Err(Error::BadGraph);
264            }
265            let nplane = nx_u * ny_u;
266            let niz = nbr / nplane;
267            let nrem = nbr % nplane;
268            let niy = nrem / nx_u;
269            let nix = nrem % nx_u;
270            let mapped = ((niz * ny_u) + niy) * big_nx_u + copy * nx_u + nix;
271            neighbor.push(mapped as u32);
272            edge_weight.push(graph.edge_weight[edge]);
273        }
274        offsets[dst + 1] = u32::try_from(neighbor.len()).map_err(|_| Error::BadGraph)?;
275    }
276    Ok(CellGraph {
277        grid: CellGrid {
278            nx: big_nx,
279            ny,
280            nz,
281            bin_width: graph.grid.bin_width,
282            weight,
283        },
284        offsets,
285        neighbor,
286        edge_weight,
287    })
288}
289
290/// Periodic cell adjacency with pair-count edge weights.
291///
292/// Each undirected pair is stored as two arcs of the same weight.
293/// A cut counts each undirected pair once.
294#[derive(Clone, Debug, PartialEq)]
295pub struct CellGraph {
296    /// Bin counts and point weights.
297    pub grid: CellGrid,
298    /// CSR offsets, length `ncell + 1`.
299    pub offsets: Vec<u32>,
300    /// Neighbour cell of each arc.
301    pub neighbor: Vec<u32>,
302    /// Pair count of each arc.
303    pub edge_weight: Vec<u64>,
304}
305
306/// Cut, imbalance, and halo fraction of one assignment.
307#[derive(Clone, Copy, Debug, PartialEq)]
308pub struct PartScore {
309    /// Sum of undirected edge weights whose ends lie in different parts.
310    pub cut: u64,
311    /// Heaviest part weight divided by the mean part weight.
312    /// Equal empty parts score `1`.
313    pub imbalance: f64,
314    /// Largest `ghost / owned` ratio over parts that own a cell.
315    /// A part that owns nothing is skipped. No owned cell scores `0`.
316    pub halo_fraction: f64,
317}
318
319/// Bin radii that cover a length of `cutoff * depth`.
320///
321/// Axis `i` gets the smallest integer `r` with `r * bin_width[i]` at
322/// least that length. `depth` is the number of cutoff shells the
323/// caller must cover. Zero cutoff or zero depth is a zero radius.
324pub fn halo_width(cutoff: f64, depth: u32, bin_width: [f64; 3]) -> Result<[u32; 3], Error> {
325    if !cutoff.is_finite() || cutoff < 0.0 {
326        return Err(Error::BadCutoff);
327    }
328    let length = cutoff * f64::from(depth);
329    if !length.is_finite() {
330        return Err(Error::BadCutoff);
331    }
332    let mut out = [0u32; 3];
333    for i in 0..3 {
334        out[i] = bins_needed(length, bin_width[i])?;
335    }
336    Ok(out)
337}
338
339/// Ghost cells of `domain`.
340///
341/// `width` is a bin radius on each axis, from [`halo_width`] or from
342/// the caller. The result is sorted and does not include cells whose
343/// assignment equals `domain`.
344pub fn halo(
345    grid: &CellGrid,
346    assign: &[u32],
347    domain: u32,
348    width: [u32; 3],
349) -> Result<Vec<u32>, Error> {
350    let n = check_assign(grid, assign)?;
351    let mut mark = vec![0u8; n];
352    let nx = grid.nx;
353    let ny = grid.ny;
354    let nz = grid.nz;
355    for (c, &owner) in assign.iter().enumerate().take(n) {
356        if owner != domain {
357            continue;
358        }
359        let (ix, iy, iz) = unravel(c, nx, ny);
360        paint(&mut mark, nx, ny, nz, ix, iy, iz, width);
361    }
362    let mut ghosts = Vec::new();
363    for c in 0..n {
364        if mark[c] != 0 && assign[c] != domain {
365            ghosts.push(c as u32);
366        }
367    }
368    Ok(ghosts)
369}
370
371/// Mark points owned by `domain` or within `reach` of one of its atoms.
372///
373/// The cell stencil from `hwidth` is only the candidate list. A point in
374/// a painted cell is kept when its minimum image to an owned atom is at
375/// most `reach`. Owned points are `2`. Reached ghosts are `1`.
376pub fn mark_reached(
377    xyz: &[[f64; 3]],
378    lengths: [f64; 3],
379    nxyz: [i32; 3],
380    assign: &[u32],
381    point_cell: &[u32],
382    hwidth: [u32; 3],
383    domain: u32,
384    reach: f64,
385) -> Result<Vec<u8>, Error> {
386    if xyz.len() != point_cell.len() || !(reach.is_finite() && reach >= 0.0) {
387        return Err(Error::BadGraph);
388    }
389    if nxyz[0] <= 0 || nxyz[1] <= 0 || nxyz[2] <= 0 {
390        return Err(Error::BadGraph);
391    }
392    let nx = nxyz[0] as usize;
393    let ny = nxyz[1] as usize;
394    let nz = nxyz[2] as usize;
395    let ncell = nx
396        .checked_mul(ny)
397        .and_then(|v| v.checked_mul(nz))
398        .ok_or(Error::BadGraph)?;
399    if assign.len() != ncell {
400        return Err(Error::BadGraph);
401    }
402    let mut start = vec![0usize; ncell + 1];
403    for &cell in point_cell {
404        let c = cell as usize;
405        if c < ncell {
406            start[c + 1] += 1;
407        }
408    }
409    for c in 0..ncell {
410        start[c + 1] += start[c];
411    }
412    let mut cursor = start.clone();
413    let mut atoms = vec![0usize; xyz.len()];
414    for (i, &cell) in point_cell.iter().enumerate() {
415        let c = cell as usize;
416        if c < ncell {
417            atoms[cursor[c]] = i;
418            cursor[c] += 1;
419        }
420    }
421    let reach2 = reach * reach;
422    let rad = [hwidth[0] as i32, hwidth[1] as i32, hwidth[2] as i32];
423    let mut hit = vec![0u8; xyz.len()];
424    for (i, &cell) in point_cell.iter().enumerate() {
425        let c = cell as usize;
426        if c >= ncell {
427            continue;
428        }
429        if assign[c] == domain {
430            hit[i] = 2;
431            continue;
432        }
433        let ix = (c % nx) as i32;
434        let iy = ((c / nx) % ny) as i32;
435        let iz = (c / (nx * ny)) as i32;
436        let mut found = false;
437        'search: for dz in -rad[2]..=rad[2] {
438            for dy in -rad[1]..=rad[1] {
439                for dx in -rad[0]..=rad[0] {
440                    let jx = (ix + dx).rem_euclid(nxyz[0]) as usize;
441                    let jy = (iy + dy).rem_euclid(nxyz[1]) as usize;
442                    let jz = (iz + dz).rem_euclid(nxyz[2]) as usize;
443                    let other = (jz * ny + jy) * nx + jx;
444                    if assign[other] != domain {
445                        continue;
446                    }
447                    for &j in &atoms[start[other]..start[other + 1]] {
448                        let mut sum = 0.0;
449                        for d in 0..3 {
450                            let mut delta = xyz[i][d] - xyz[j][d];
451                            delta -= lengths[d] * (delta / lengths[d] + 0.5).floor();
452                            sum += delta * delta;
453                        }
454                        if sum <= reach2 {
455                            found = true;
456                            break 'search;
457                        }
458                    }
459                }
460            }
461        }
462        if found {
463            hit[i] = 1;
464        }
465    }
466    Ok(hit)
467}
468
469/// Point counts on the mesh `pairs_within` would use.
470pub fn cell_grid(
471    xyz: &[[f64; 3]],
472    sim: &Cell,
473    cutoff: f64,
474    mask: Option<&[bool]>,
475    cell_hint: Option<f64>,
476) -> Result<CellGrid, Error> {
477    prepared(xyz, sim, cutoff, mask, cell_hint, false).map(|p| p.graph.grid)
478}
479
480/// Cell grid plus pair-count arcs from [`pairs_within`].
481pub fn cell_graph(
482    xyz: &[[f64; 3]],
483    sim: &Cell,
484    cutoff: f64,
485    mask: Option<&[bool]>,
486    cell_hint: Option<f64>,
487) -> Result<CellGraph, Error> {
488    prepared(xyz, sim, cutoff, mask, cell_hint, true).map(|p| p.graph)
489}
490
491/// Domain id of each cell. See [`PartRequest`].
492pub fn partition(
493    xyz: &[[f64; 3]],
494    sim: &Cell,
495    cutoff: f64,
496    mask: Option<&[bool]>,
497    cell_hint: Option<f64>,
498    request: PartRequest,
499) -> Result<Vec<u32>, Error> {
500    // The pair list is a full sort of every cutoff arc. A method that
501    // only reads cell counts must not build it: on the million-point
502    // frame that list is the whole call, and the bisection is the
503    // median of the link-cell bins.
504    let prep = prepared(
505        xyz,
506        sim,
507        cutoff,
508        mask,
509        cell_hint,
510        request.method.needs_edges(),
511    )?;
512    partition_prepared(&prep, request)
513}
514
515/// Partition an existing graph. `device` needs the point bins, so it
516/// returns [`Error::NoDevice`] here. Build the assignment from points
517/// with [`partition`] when the device path is required.
518pub fn partition_graph(graph: &CellGraph, request: PartRequest) -> Result<Vec<u32>, Error> {
519    if request.device {
520        return Err(Error::NoDevice);
521    }
522    let t_check = Instant::now();
523    check_graph(graph)?;
524    CHECK_NS.fetch_add(t_check.elapsed().as_nanos() as u64, AtomicOrdering::Relaxed);
525    let t_ratio = Instant::now();
526    let ratio = balance_ratio(request.balance, &graph.grid.weight, request.parts)?;
527    PACK_NS.fetch_add(t_ratio.elapsed().as_nanos() as u64, AtomicOrdering::Relaxed);
528    if request.parts == 0 {
529        return Err(Error::BadPartition);
530    }
531    dispatch(graph, request.method, request.parts, ratio, None)
532}
533
534/// Curve split on the device, including the copies both ways.
535///
536/// The result is the prefix assignment, with no refinement pass.
537/// [`Error::NoDevice`] means the driver is absent. A mismatch with the
538/// host histogram is [`Error::DeviceMismatch`].
539pub fn curve_split_device(
540    xyz: &[[f64; 3]],
541    sim: &Cell,
542    cutoff: f64,
543    mask: Option<&[bool]>,
544    cell_hint: Option<f64>,
545    parts: u32,
546    method: Method,
547) -> Result<Vec<u32>, Error> {
548    if !method.uses_curve() {
549        return Err(Error::NoDevice);
550    }
551    if parts == 0 {
552        return Err(Error::BadPartition);
553    }
554    let prep = prepared(xyz, sim, cutoff, mask, cell_hint, false)?;
555    device_curve(&prep, parts, method)
556}
557
558/// Cut, imbalance, and halo fraction.
559pub fn score(
560    graph: &CellGraph,
561    assign: &[u32],
562    parts: u32,
563    width: [u32; 3],
564) -> Result<PartScore, Error> {
565    check_graph(graph)?;
566    check_assign(&graph.grid, assign)?;
567    if parts == 0 {
568        return Err(Error::BadPartition);
569    }
570    for &d in assign {
571        if d >= parts {
572            return Err(Error::BadPartition);
573        }
574    }
575    Ok(PartScore {
576        cut: edge_cut(graph, assign),
577        imbalance: max_imbalance(&graph.grid.weight, assign, parts),
578        halo_fraction: halo_fraction(&graph.grid, assign, parts, width)?,
579    })
580}
581
582/// Undirected edge cut.
583pub fn edge_cut(graph: &CellGraph, assign: &[u32]) -> u64 {
584    let mut cut = 0u64;
585    let n = graph.grid.ncell();
586    for c in 0..n {
587        let a = assign[c];
588        let lo = graph.offsets[c] as usize;
589        let hi = graph.offsets[c + 1] as usize;
590        for e in lo..hi {
591            let nbr = graph.neighbor[e] as usize;
592            if nbr > c && assign[nbr] != a {
593                cut += graph.edge_weight[e];
594            }
595        }
596    }
597    cut
598}
599
600struct Prepared {
601    graph: CellGraph,
602    /// Flat bin of each active point, in point order with masked points omitted.
603    active_bins: Vec<u32>,
604    /// Bin of every point. A masked point keeps bin 0.
605    point_cell: Vec<u32>,
606}
607
608/// Threads the point binning splits over. A one-thread search on the
609/// caller bins there, as its walks do, and a build without `parallel`
610/// keeps the whole search serial.
611#[cfg(feature = "parallel")]
612fn bin_threads() -> usize {
613    if crate::on_caller() {
614        return 1;
615    }
616    std::thread::available_parallelism()
617        .map(|n| n.get())
618        .unwrap_or(1)
619}
620
621#[cfg(not(feature = "parallel"))]
622fn bin_threads() -> usize {
623    1
624}
625
626/// Point counts on the link-cell grid. Threads own disjoint point ranges
627/// and private histograms, then the histograms add. The active-bin list
628/// stays in point order. One range is binned on the calling thread.
629fn bin_points(
630    xyz: &[[f64; 3]],
631    sim: &Cell,
632    mask: Option<&[bool]>,
633    dims: [i32; 3],
634    ncell: usize,
635) -> (Vec<u64>, Vec<u32>, Vec<u32>) {
636    let n = xyz.len();
637    let threads = if n >= 8192 { bin_threads() } else { 1 };
638    let chunk = (n + threads - 1) / threads;
639    let mut bin_of = vec![0u32; n];
640    let mut weight = vec![0u64; ncell];
641    let bin_range = |t: usize, lo: usize, hi: usize| {
642        let mut local = vec![0u64; ncell];
643        let mut active = Vec::new();
644        for i in lo..hi {
645            if mask.is_some_and(|m| !m[i]) {
646                continue;
647            }
648            let (_, b) = bins::fold_point(sim, xyz[i], dims);
649            let c = flat_cell(b, dims) as u32;
650            local[c as usize] += 1;
651            active.push((i, c));
652        }
653        (t, active, local)
654    };
655    let mut hits: Vec<(usize, Vec<(usize, u32)>, Vec<u64>)> = if threads == 1 {
656        vec![bin_range(0, 0, n)]
657    } else {
658        std::thread::scope(|scope| {
659            let bin_range = &bin_range;
660            let mut joins = Vec::new();
661            for t in 0..threads {
662                let lo = t * chunk;
663                let hi = ((t + 1) * chunk).min(n);
664                if lo >= hi {
665                    continue;
666                }
667                joins.push(scope.spawn(move || bin_range(t, lo, hi)));
668            }
669            joins
670                .into_iter()
671                .map(|join| join.join().expect("bin"))
672                .collect()
673        })
674    };
675    hits.sort_by_key(|(t, _, _)| *t);
676    let mut active_bins = Vec::new();
677    for (_, active, local) in hits {
678        for (c, w) in local.into_iter().enumerate() {
679            weight[c] += w;
680        }
681        for (i, c) in active {
682            bin_of[i] = c;
683            active_bins.push(c);
684        }
685    }
686    (weight, active_bins, bin_of)
687}
688
689fn prepared(
690    xyz: &[[f64; 3]],
691    sim: &Cell,
692    cutoff: f64,
693    mask: Option<&[bool]>,
694    cell_hint: Option<f64>,
695    with_edges: bool,
696) -> Result<Prepared, Error> {
697    if !cutoff.is_finite() || cutoff <= 0.0 {
698        return Err(Error::BadCutoff);
699    }
700    if xyz.is_empty() {
701        return Err(Error::Empty);
702    }
703    if let Some(m) = mask {
704        if m.len() != xyz.len() {
705            return Err(Error::MaskLen);
706        }
707    }
708    let mut n_act = 0usize;
709    for (i, p) in xyz.iter().enumerate() {
710        if !p[0].is_finite() || !p[1].is_finite() || !p[2].is_finite() {
711            return Err(Error::NonFinite);
712        }
713        if mask.is_some_and(|m| !m[i]) {
714            continue;
715        }
716        n_act += 1;
717    }
718    let edge = bins::target_edge(sim, cell_hint, pairs::default_edge(sim, n_act, cutoff));
719    let dims = bins::grid_dims(sim, edge)?;
720    let ncell = (dims[0] as usize) * (dims[1] as usize) * (dims[2] as usize);
721    let box_w = sim.widths();
722    let bin_width = [
723        box_w[0] / f64::from(dims[0]),
724        box_w[1] / f64::from(dims[1]),
725        box_w[2] / f64::from(dims[2]),
726    ];
727    let (weight, active_bins, bin_of) = bin_points(xyz, sim, mask, dims, ncell);
728    let (offsets, neighbor, edge_weight) = if with_edges {
729        arcs_from_pairs(xyz, sim, cutoff, mask, cell_hint, &bin_of, ncell)?
730    } else {
731        (vec![0u32; ncell + 1], Vec::new(), Vec::new())
732    };
733    Ok(Prepared {
734        graph: CellGraph {
735            grid: CellGrid {
736                nx: dims[0],
737                ny: dims[1],
738                nz: dims[2],
739                bin_width,
740                weight,
741            },
742            offsets,
743            neighbor,
744            edge_weight,
745        },
746        active_bins,
747        point_cell: bin_of,
748    })
749}
750
751/// Assignment, the grid it was cut on, and the bin of every point.
752///
753/// One binning feeds the cut. A later frame that keeps this cut does not
754/// bin again.
755pub struct MeshCut {
756    /// Domain of each cell.
757    pub assign: Vec<u32>,
758    /// Bins and point weights.
759    pub grid: CellGrid,
760    /// Bin of each point, in point order.
761    pub point_cell: Vec<u32>,
762}
763
764/// Cut the mesh once and keep the point bins.
765pub fn mesh_cut(
766    xyz: &[[f64; 3]],
767    sim: &Cell,
768    cutoff: f64,
769    mask: Option<&[bool]>,
770    cell_hint: Option<f64>,
771    request: PartRequest,
772) -> Result<MeshCut, Error> {
773    let prep = prepared(
774        xyz,
775        sim,
776        cutoff,
777        mask,
778        cell_hint,
779        request.method.needs_edges(),
780    )?;
781    let assign = partition_prepared(&prep, request)?;
782    Ok(MeshCut {
783        assign,
784        grid: prep.graph.grid,
785        point_cell: prep.point_cell,
786    })
787}
788
789/// Point mask of one rank after its halo is painted.
790pub struct RankMask {
791    /// Points whose bin is owned or lies in the halo.
792    pub mask: Vec<bool>,
793    /// Points in cells this rank owns.
794    pub owned: usize,
795    /// Ghost cells, the painted bins this rank does not own.
796    pub ghosts: usize,
797}
798
799/// Paint each rank's halo while walking the cells that rank owns.
800///
801/// The owned lists come from one shared pass over the assignment. Each
802/// rank then paints its stencil from those cells and reads the point
803/// bins already stored on the cut. The ghost count matches [`halo`].
804pub fn fused_masks(
805    grid: &CellGrid,
806    assign: &[u32],
807    point_cell: &[u32],
808    parts: u32,
809    width: [u32; 3],
810) -> Result<Vec<RankMask>, Error> {
811    let n = check_assign(grid, assign)?;
812    if parts == 0 {
813        return Err(Error::BadPartition);
814    }
815    for &domain in assign {
816        if domain >= parts {
817            return Err(Error::BadPartition);
818        }
819    }
820    for &cell in point_cell {
821        if cell as usize >= n {
822            return Err(Error::BadPartition);
823        }
824    }
825    let owned = owned_cells(assign, parts);
826    let built = std::thread::scope(|scope| {
827        let mut joins = Vec::new();
828        for rank in 0..parts {
829            let cells = &owned[rank as usize];
830            joins
831                .push(scope.spawn(move || rank_mask(grid, assign, point_cell, cells, rank, width)));
832        }
833        joins
834            .into_iter()
835            .map(|join| join.join().expect("rank mask"))
836            .collect()
837    });
838    Ok(built)
839}
840
841/// Cells of each domain, in cell order.
842pub fn owned_cells(assign: &[u32], parts: u32) -> Vec<Vec<u32>> {
843    let n = assign.len();
844    let threads = std::thread::available_parallelism()
845        .map(|n| n.get())
846        .unwrap_or(1);
847    let threads = if n >= 8192 { threads.max(1) } else { 1 };
848    let chunk = (n + threads - 1) / threads;
849    let mut hits: Vec<(usize, Vec<Vec<u32>>)> = Vec::new();
850    std::thread::scope(|scope| {
851        let mut joins = Vec::new();
852        for t in 0..threads {
853            let lo = t * chunk;
854            let hi = ((t + 1) * chunk).min(n);
855            if lo >= hi {
856                continue;
857            }
858            joins.push(scope.spawn(move || {
859                let mut rows = vec![Vec::new(); parts as usize];
860                for cell in lo..hi {
861                    rows[assign[cell] as usize].push(cell as u32);
862                }
863                (t, rows)
864            }));
865        }
866        for join in joins {
867            hits.push(join.join().expect("owned"));
868        }
869    });
870    hits.sort_by_key(|(t, _)| *t);
871    let mut owned = vec![Vec::new(); parts as usize];
872    for (_, rows) in hits {
873        for (rank, cells) in rows.into_iter().enumerate() {
874            owned[rank].extend(cells);
875        }
876    }
877    owned
878}
879
880/// Halo and point mask for one rank, from that rank's own cells.
881///
882/// The stencil is painted in the same walk that visits those cells.
883pub fn rank_mask(
884    grid: &CellGrid,
885    assign: &[u32],
886    point_cell: &[u32],
887    cells: &[u32],
888    rank: u32,
889    width: [u32; 3],
890) -> RankMask {
891    let n = grid.ncell();
892    let mut mark = vec![0u8; n];
893    for &cell in cells {
894        let (ix, iy, iz) = unravel(cell as usize, grid.nx, grid.ny);
895        paint(&mut mark, grid.nx, grid.ny, grid.nz, ix, iy, iz, width);
896    }
897    let mut ghosts = 0usize;
898    for (cell, &flag) in mark.iter().enumerate() {
899        if flag != 0 && assign[cell] != rank {
900            ghosts += 1;
901        }
902    }
903    let mut mask = vec![false; point_cell.len()];
904    let mut owned_pts = 0usize;
905    for (i, &cell) in point_cell.iter().enumerate() {
906        let cell = cell as usize;
907        if assign[cell] == rank {
908            owned_pts += 1;
909        }
910        mask[i] = mark[cell] != 0;
911    }
912    RankMask {
913        mask,
914        owned: owned_pts,
915        ghosts,
916    }
917}
918
919fn arcs_from_pairs(
920    xyz: &[[f64; 3]],
921    sim: &Cell,
922    cutoff: f64,
923    mask: Option<&[bool]>,
924    cell_hint: Option<f64>,
925    bin_of: &[u32],
926    ncell: usize,
927) -> Result<(Vec<u32>, Vec<u32>, Vec<u64>), Error> {
928    let pairs = pairs_within(xyz, sim, cutoff, mask, cell_hint, true)?;
929    let mut ends: Vec<(u32, u32)> = Vec::new();
930    for pair in pairs {
931        let a = bin_of[pair.i];
932        let b = bin_of[pair.j];
933        if a == b {
934            continue;
935        }
936        if a < b {
937            ends.push((a, b));
938        } else {
939            ends.push((b, a));
940        }
941    }
942    ends.sort_unstable();
943    let mut undirected: Vec<(u32, u32, u64)> = Vec::new();
944    let mut cursor = 0;
945    while cursor < ends.len() {
946        let (a, b) = ends[cursor];
947        let mut count = 1u64;
948        cursor += 1;
949        while cursor < ends.len() && ends[cursor] == (a, b) {
950            count += 1;
951            cursor += 1;
952        }
953        undirected.push((a, b, count));
954    }
955    let mut arcs: Vec<(u32, u32, u64)> = Vec::with_capacity(undirected.len() * 2);
956    for (a, b, w) in undirected {
957        arcs.push((a, b, w));
958        arcs.push((b, a, w));
959    }
960    arcs.sort_unstable();
961    if arcs.len() > u32::MAX as usize {
962        return Err(Error::Overflow);
963    }
964    let mut offsets = vec![0u32; ncell + 1];
965    let mut neighbor = Vec::with_capacity(arcs.len());
966    let mut edge_weight = Vec::with_capacity(arcs.len());
967    for (src, dst, w) in arcs {
968        offsets[src as usize + 1] += 1;
969        neighbor.push(dst);
970        edge_weight.push(w);
971    }
972    for c in 0..ncell {
973        offsets[c + 1] += offsets[c];
974    }
975    Ok((offsets, neighbor, edge_weight))
976}
977
978fn partition_prepared(prep: &Prepared, request: PartRequest) -> Result<Vec<u32>, Error> {
979    if request.parts == 0 {
980        return Err(Error::BadPartition);
981    }
982    let ratio = balance_ratio(request.balance, &prep.graph.grid.weight, request.parts)?;
983    let device_assign = if request.device {
984        if !request.method.uses_curve() {
985            return Err(Error::NoDevice);
986        }
987        Some(device_curve(prep, request.parts, request.method)?)
988    } else {
989        None
990    };
991    dispatch(
992        &prep.graph,
993        request.method,
994        request.parts,
995        ratio,
996        device_assign,
997    )
998}
999
1000/// Largest weight one contracted vertex may have.
1001///
1002/// [`part_cap`] is the most weight `under_balance` allows one part to
1003/// hold. With the derived ratio that cap is the ideal share plus the
1004/// heaviest fine cell, so the stop is tied to the part count and
1005/// `w_max`. A coarse vertex above the cap cannot sit in any part, and
1006/// matching refuses a pair that would cross it.
1007fn cluster_cap(total: u64, parts: u32, w_max: u64, ratio: (u64, u64)) -> u64 {
1008    part_cap(total, parts, ratio).max(w_max).max(1)
1009}
1010
1011fn multi_assign(graph: &CellGraph, parts: u32, ratio: (u64, u64)) -> Vec<u32> {
1012    let n = graph.grid.ncell();
1013    let t_pack = Instant::now();
1014    let mut coords = Vec::with_capacity(n);
1015    for c in 0..n {
1016        let (ix, iy, iz) = unravel(c, graph.grid.nx, graph.grid.ny);
1017        coords.push((f64::from(ix), f64::from(iy), f64::from(iz)));
1018    }
1019    PACK_NS.fetch_add(t_pack.elapsed().as_nanos() as u64, AtomicOrdering::Relaxed);
1020    // Geometric bisection is the incumbent. A later cycle replaces it
1021    // only when the integer cut falls and every part stays inside the
1022    // balance bound. The cut cannot fall forever, so the loop ends when
1023    // a cycle brings no gain.
1024    let mut best = rcb_assign(graph, parts, true, ratio);
1025    let t_cut = Instant::now();
1026    let mut best_cut = edge_cut(graph, &best);
1027    COARSE_NS.fetch_add(t_cut.elapsed().as_nanos() as u64, AtomicOrdering::Relaxed);
1028    loop {
1029        let next = v_cycle(graph, &coords, &best, parts, ratio);
1030        let t_cut = Instant::now();
1031        let next_cut = edge_cut(graph, &next);
1032        let keep = next_cut < best_cut && holds_balance(&graph.grid.weight, &next, parts, ratio);
1033        COARSE_NS.fetch_add(t_cut.elapsed().as_nanos() as u64, AtomicOrdering::Relaxed);
1034        if keep {
1035            best = next;
1036            best_cut = next_cut;
1037        } else {
1038            break;
1039        }
1040    }
1041    best
1042}
1043
1044fn holds_balance(weight: &[u64], assign: &[u32], parts: u32, ratio: (u64, u64)) -> bool {
1045    if parts == 0 {
1046        return false;
1047    }
1048    let mut part_w = vec![0u64; parts as usize];
1049    let mut total = 0u64;
1050    for (c, &d) in assign.iter().enumerate() {
1051        if d >= parts {
1052            return false;
1053        }
1054        part_w[d as usize] += weight[c];
1055        total += weight[c];
1056    }
1057    part_w
1058        .iter()
1059        .all(|&w| under_balance(w, total, parts, ratio))
1060}
1061
1062/// One uncoarsening pass. Matching stays inside the current parts, so the
1063/// projected partition is the incumbent until refinement moves a cluster.
1064fn v_cycle(
1065    graph: &CellGraph,
1066    coords: &[(f64, f64, f64)],
1067    assign: &[u32],
1068    parts: u32,
1069    ratio: (u64, u64),
1070) -> Vec<u32> {
1071    let n = graph.grid.ncell();
1072    let t_prep = Instant::now();
1073    let total: u64 = graph.grid.weight.iter().copied().sum();
1074    let w_max = graph.grid.weight.iter().copied().max().unwrap_or(0);
1075    let cap = cluster_cap(total, parts, w_max, ratio);
1076    COARSE_NS.fetch_add(t_prep.elapsed().as_nanos() as u64, AtomicOrdering::Relaxed);
1077    // One vertex per part is already a legal assignment. A vertex above
1078    // the cap cannot be paired without producing an unsplittable part.
1079    if n <= parts as usize || graph.grid.weight.iter().any(|&w| w > cap) {
1080        let mut out = assign.to_vec();
1081        refine(&mut out, graph, parts, ratio);
1082        return out;
1083    }
1084    let t0 = Instant::now();
1085    let mate = heavy_match(graph, cap, Some(assign));
1086    let shrunk = mate.iter().enumerate().any(|(v, &m)| m != v as u32);
1087    if !shrunk {
1088        COARSE_NS.fetch_add(t0.elapsed().as_nanos() as u64, AtomicOrdering::Relaxed);
1089        let mut out = assign.to_vec();
1090        refine(&mut out, graph, parts, ratio);
1091        return out;
1092    }
1093    let (coarse, coarse_coords, owner) = contract(graph, coords, &mate);
1094    COARSE_NS.fetch_add(t0.elapsed().as_nanos() as u64, AtomicOrdering::Relaxed);
1095    let mut up = vec![0u32; coarse.grid.ncell()];
1096    for (fine, &cell) in owner.iter().enumerate() {
1097        up[cell as usize] = assign[fine];
1098    }
1099    let up = v_cycle(&coarse, &coarse_coords, &up, parts, ratio);
1100    let t_down = Instant::now();
1101    let mut out = vec![0u32; n];
1102    for (fine, &cell) in owner.iter().enumerate() {
1103        out[fine] = up[cell as usize];
1104    }
1105    COARSE_NS.fetch_add(t_down.elapsed().as_nanos() as u64, AtomicOrdering::Relaxed);
1106    refine(&mut out, graph, parts, ratio);
1107    out
1108}
1109
1110fn heavy_match(graph: &CellGraph, cap: u64, same: Option<&[u32]>) -> Vec<u32> {
1111    let n = graph.grid.ncell();
1112    let mut mate = vec![u32::MAX; n];
1113    for v in 0..n {
1114        if mate[v] != u32::MAX {
1115            continue;
1116        }
1117        let wv = graph.grid.weight[v];
1118        // Prefer a heavy edge between light vertices: compare edge/combined.
1119        let mut best: Option<(u64, u64, u32)> = None;
1120        let lo = graph.offsets[v] as usize;
1121        let hi = graph.offsets[v + 1] as usize;
1122        for e in lo..hi {
1123            let u = graph.neighbor[e];
1124            if u as usize == v || mate[u as usize] != u32::MAX {
1125                continue;
1126            }
1127            let wu = graph.grid.weight[u as usize];
1128            if wv.saturating_add(wu) > cap {
1129                continue;
1130            }
1131            if let Some(parts_of) = same {
1132                if parts_of[u as usize] != parts_of[v] {
1133                    continue;
1134                }
1135            }
1136            let w = graph.edge_weight[e];
1137            let denom = wv.max(1).saturating_add(wu.max(1));
1138            let take = match best {
1139                None => true,
1140                Some((bw, bden, bu)) => {
1141                    let left = u128::from(w) * u128::from(bden);
1142                    let right = u128::from(bw) * u128::from(denom);
1143                    left > right || (left == right && u < bu)
1144                }
1145            };
1146            if take {
1147                best = Some((w, denom, u));
1148            }
1149        }
1150        if let Some((_, _, u)) = best {
1151            mate[v] = u;
1152            mate[u as usize] = v as u32;
1153        } else {
1154            mate[v] = v as u32;
1155        }
1156    }
1157    mate
1158}
1159
1160fn contract(
1161    graph: &CellGraph,
1162    coords: &[(f64, f64, f64)],
1163    mate: &[u32],
1164) -> (CellGraph, Vec<(f64, f64, f64)>, Vec<u32>) {
1165    let n = graph.grid.ncell();
1166    let mut coarse_of = vec![u32::MAX; n];
1167    let mut members: Vec<Vec<u32>> = Vec::new();
1168    for v in 0..n {
1169        let lead = (v as u32).min(mate[v]) as usize;
1170        if coarse_of[lead] == u32::MAX {
1171            coarse_of[lead] = members.len() as u32;
1172            members.push(Vec::new());
1173        }
1174        let id = coarse_of[lead];
1175        coarse_of[v] = id;
1176        members[id as usize].push(v as u32);
1177    }
1178    let nc = members.len();
1179    let mut weight = vec![0u64; nc];
1180    let mut ccoords = vec![(0.0, 0.0, 0.0); nc];
1181    for (c, group) in members.iter().enumerate() {
1182        let mut mass = 0u64;
1183        let mut acc = (0.0, 0.0, 0.0);
1184        for &v in group {
1185            let w = graph.grid.weight[v as usize];
1186            mass += w;
1187            let p = coords[v as usize];
1188            acc.0 += p.0 * w as f64;
1189            acc.1 += p.1 * w as f64;
1190            acc.2 += p.2 * w as f64;
1191            weight[c] += w;
1192        }
1193        if mass == 0 {
1194            let p = coords[group[0] as usize];
1195            ccoords[c] = p;
1196        } else {
1197            let mass = mass as f64;
1198            ccoords[c] = (acc.0 / mass, acc.1 / mass, acc.2 / mass);
1199        }
1200    }
1201    let mut ends: Vec<(u32, u32, u64)> = Vec::new();
1202    for v in 0..n {
1203        let cv = coarse_of[v];
1204        let lo = graph.offsets[v] as usize;
1205        let hi = graph.offsets[v + 1] as usize;
1206        for e in lo..hi {
1207            let u = graph.neighbor[e] as usize;
1208            if u <= v {
1209                continue;
1210            }
1211            let cu = coarse_of[u];
1212            if cu == cv {
1213                continue;
1214            }
1215            let (a, b) = if cv < cu { (cv, cu) } else { (cu, cv) };
1216            ends.push((a, b, graph.edge_weight[e]));
1217        }
1218    }
1219    ends.sort_unstable_by(|p, q| p.0.cmp(&q.0).then(p.1.cmp(&q.1)));
1220    let mut arcs: Vec<(u32, u32, u64)> = Vec::new();
1221    let mut i = 0;
1222    while i < ends.len() {
1223        let (a, b, mut w) = ends[i];
1224        i += 1;
1225        while i < ends.len() && ends[i].0 == a && ends[i].1 == b {
1226            w += ends[i].2;
1227            i += 1;
1228        }
1229        // Each fine arc was stored once per direction, and the pair was
1230        // ordered, so the merged weight is the undirected total. Emit both.
1231        arcs.push((a, b, w));
1232        arcs.push((b, a, w));
1233    }
1234    arcs.sort_unstable_by(|p, q| p.0.cmp(&q.0).then(p.1.cmp(&q.1)));
1235    let mut offsets = vec![0u32; nc + 1];
1236    let mut neighbor = Vec::with_capacity(arcs.len());
1237    let mut edge_weight = Vec::with_capacity(arcs.len());
1238    for (src, dst, w) in arcs {
1239        offsets[src as usize + 1] += 1;
1240        neighbor.push(dst);
1241        edge_weight.push(w);
1242    }
1243    for c in 0..nc {
1244        offsets[c + 1] += offsets[c];
1245    }
1246    let coarse = CellGraph {
1247        grid: CellGrid {
1248            nx: nc as i32,
1249            ny: 1,
1250            nz: 1,
1251            bin_width: [1.0, 1.0, 1.0],
1252            weight,
1253        },
1254        offsets,
1255        neighbor,
1256        edge_weight,
1257    };
1258    (coarse, ccoords, coarse_of)
1259}
1260
1261fn ptscotch_assign(graph: &CellGraph, parts: u32, ratio: (u64, u64)) -> Result<Vec<u32>, Error> {
1262    #[cfg(not(feature = "ptscotch"))]
1263    {
1264        let _ = (graph, parts, ratio);
1265        Err(Error::ScotchDisabled)
1266    }
1267    #[cfg(feature = "ptscotch")]
1268    {
1269        ptscotch_linked(graph, parts, ratio)
1270    }
1271}
1272
1273#[cfg(feature = "ptscotch")]
1274fn ptscotch_linked(graph: &CellGraph, parts: u32, ratio: (u64, u64)) -> Result<Vec<u32>, Error> {
1275    let n = graph.grid.ncell();
1276    if n > i32::MAX as usize || parts > i32::MAX as u32 {
1277        return Err(Error::Overflow);
1278    }
1279    let mut offsets = Vec::with_capacity(n + 1);
1280    let mut edges = Vec::with_capacity(graph.neighbor.len());
1281    let mut vwgt = Vec::with_capacity(n);
1282    let mut ewgt = Vec::with_capacity(graph.edge_weight.len());
1283    for &v in &graph.offsets {
1284        if v > i32::MAX as u32 {
1285            return Err(Error::Overflow);
1286        }
1287        offsets.push(v as i32);
1288    }
1289    for &v in &graph.neighbor {
1290        if v > i32::MAX as u32 {
1291            return Err(Error::Overflow);
1292        }
1293        edges.push(v as i32);
1294    }
1295    for &v in &graph.grid.weight {
1296        if v > i32::MAX as u64 {
1297            return Err(Error::Overflow);
1298        }
1299        vwgt.push(v as i32);
1300    }
1301    for &v in &graph.edge_weight {
1302        if v > i32::MAX as u64 {
1303            return Err(Error::Overflow);
1304        }
1305        ewgt.push(v as i32);
1306    }
1307    let mut part = vec![0i32; n];
1308    let (num, den) = ratio;
1309    let imbalance = if den == 0 {
1310        0.0
1311    } else {
1312        (num as f64 / den as f64) - 1.0
1313    };
1314    let mut seconds = 0.0f64;
1315    let rc = unsafe {
1316        lc_ptscotch_part(
1317            n as i32,
1318            offsets.as_ptr(),
1319            edges.as_ptr(),
1320            vwgt.as_ptr(),
1321            ewgt.as_ptr(),
1322            parts as i32,
1323            imbalance,
1324            part.as_mut_ptr(),
1325            &mut seconds,
1326        )
1327    };
1328    if rc != 0 {
1329        return Err(Error::ScotchFailed);
1330    }
1331    let _ = seconds;
1332    let mut out = Vec::with_capacity(n);
1333    for v in part {
1334        if v < 0 || v as u32 >= parts {
1335            return Err(Error::ScotchFailed);
1336        }
1337        out.push(v as u32);
1338    }
1339    Ok(out)
1340}
1341
1342#[cfg(feature = "ptscotch")]
1343unsafe extern "C" {
1344    fn lc_ptscotch_part(
1345        n: i32,
1346        offsets: *const i32,
1347        edges: *const i32,
1348        vwgt: *const i32,
1349        ewgt: *const i32,
1350        parts: i32,
1351        imbalance: f64,
1352        part: *mut i32,
1353        seconds_max: *mut f64,
1354    ) -> i32;
1355}
1356
1357fn dispatch(
1358    graph: &CellGraph,
1359    method: Method,
1360    parts: u32,
1361    ratio: (u64, u64),
1362    device_assign: Option<Vec<u32>>,
1363) -> Result<Vec<u32>, Error> {
1364    let mut assign = match method {
1365        Method::Scotch => scotch_assign(graph, parts, ratio)?,
1366        Method::PtScotch => ptscotch_assign(graph, parts, ratio)?,
1367        Method::Multi => multi_assign(graph, parts, ratio),
1368        Method::Rcb | Method::RcbFm => rcb_assign(graph, parts, method == Method::RcbFm, ratio),
1369        Method::Morton | Method::Hilbert | Method::HilbertFm => match device_assign {
1370            Some(done) => done,
1371            None => curve_assign(graph, parts, method)?,
1372        },
1373    };
1374    if method.refines() {
1375        refine(&mut assign, graph, parts, ratio);
1376    }
1377    if matches!(method, Method::RcbFm | Method::HilbertFm | Method::Multi) {
1378        let t_repair = Instant::now();
1379        repair_balance(&mut assign, graph, parts, ratio);
1380        if matches!(method, Method::RcbFm | Method::Multi)
1381            && !holds_balance(&graph.grid.weight, &assign, parts, ratio)
1382        {
1383            REPAIR_NS.fetch_add(
1384                t_repair.elapsed().as_nanos() as u64,
1385                AtomicOrdering::Relaxed,
1386            );
1387            assign = rcb_assign(graph, parts, false, ratio);
1388        } else {
1389            REPAIR_NS.fetch_add(
1390                t_repair.elapsed().as_nanos() as u64,
1391                AtomicOrdering::Relaxed,
1392            );
1393        }
1394    }
1395    Ok(assign)
1396}
1397
1398fn part_cap(total: u64, parts: u32, ratio: (u64, u64)) -> u64 {
1399    let (num, den) = ratio;
1400    if parts == 0 || den == 0 {
1401        return total;
1402    }
1403    ((u128::from(total) * u128::from(num)) / (u128::from(parts) * u128::from(den))) as u64
1404}
1405
1406/// Move boundary weight off any part that finished above the cap.
1407fn repair_balance(assign: &mut [u32], graph: &CellGraph, parts: u32, ratio: (u64, u64)) {
1408    if parts <= 1 {
1409        return;
1410    }
1411    let n = assign.len();
1412    let weight = &graph.grid.weight;
1413    let total: u64 = weight.iter().copied().sum();
1414    let cap = part_cap(total, parts, ratio);
1415    let mut part_w = vec![0u64; parts as usize];
1416    for (c, &d) in assign.iter().enumerate() {
1417        if (d as usize) < part_w.len() {
1418            part_w[d as usize] += weight[c];
1419        }
1420    }
1421    for _ in 0..n {
1422        let Some(src) = part_w.iter().position(|&w| w > cap) else {
1423            return;
1424        };
1425        let mut best: Option<(i64, usize, u32)> = None;
1426        for cell in 0..n {
1427            if assign[cell] as usize != src {
1428                continue;
1429            }
1430            let w = weight[cell];
1431            if w == 0 || part_w[src] < w || !part_boundary(cell, assign, graph) {
1432                continue;
1433            }
1434            let lo = graph.offsets[cell] as usize;
1435            let hi = graph.offsets[cell + 1] as usize;
1436            let mut dests: Vec<u32> = Vec::new();
1437            let mut to_src = 0i64;
1438            let mut to_dest_w = vec![0i64; parts as usize];
1439            for e in lo..hi {
1440                let nbr = graph.neighbor[e] as usize;
1441                let dest = assign[nbr];
1442                let ww = graph.edge_weight[e] as i64;
1443                if dest as usize == src {
1444                    to_src += ww;
1445                } else if (dest as usize) < to_dest_w.len() {
1446                    to_dest_w[dest as usize] += ww;
1447                    if !dests.contains(&dest) {
1448                        dests.push(dest);
1449                    }
1450                }
1451            }
1452            for dest in dests {
1453                if part_w[dest as usize].saturating_add(w) > cap {
1454                    continue;
1455                }
1456                let gain = to_dest_w[dest as usize] - to_src;
1457                let take = match best {
1458                    None => true,
1459                    Some((bg, bcell, bdest)) => {
1460                        gain > bg
1461                            || (gain == bg && (cell < bcell || (cell == bcell && dest < bdest)))
1462                    }
1463                };
1464                if take {
1465                    best = Some((gain, cell, dest));
1466                }
1467            }
1468        }
1469        let Some((_, cell, dest)) = best else {
1470            return;
1471        };
1472        let w = weight[cell];
1473        part_w[src] -= w;
1474        part_w[dest as usize] += w;
1475        assign[cell] = dest;
1476    }
1477}
1478
1479fn curve_assign(graph: &CellGraph, parts: u32, method: Method) -> Result<Vec<u32>, Error> {
1480    let n = graph.grid.ncell();
1481    let mut order: Vec<u32> = (0..n as u32).collect();
1482    match method {
1483        Method::Morton => {
1484            order.sort_by(|&a, &b| morton_ord(a, b, &graph.grid).then(a.cmp(&b)));
1485        }
1486        Method::Hilbert | Method::HilbertFm => {
1487            let bits = hilbert_bits(graph.grid.nx, graph.grid.ny, graph.grid.nz);
1488            let mut keys = vec![0u64; n];
1489            for (c, key) in keys.iter_mut().enumerate() {
1490                let (x, y, z) = unravel(c, graph.grid.nx, graph.grid.ny);
1491                *key = hilbert_key(x as u32, y as u32, z as u32, bits);
1492            }
1493            order.sort_by(|&a, &b| keys[a as usize].cmp(&keys[b as usize]).then(a.cmp(&b)));
1494        }
1495        _ => return Err(Error::BadPartition),
1496    }
1497    Ok(prefix_assign(&order, &graph.grid.weight, parts))
1498}
1499
1500fn device_curve(prep: &Prepared, parts: u32, method: Method) -> Result<Vec<u32>, Error> {
1501    let n = prep.graph.grid.ncell();
1502    let coords = cell_coords(&prep.graph.grid);
1503    let mut assign = vec![0u32; n];
1504    let mut got_w = vec![0u64; n];
1505    let rc = unsafe {
1506        call_device_curve(
1507            prep.active_bins.as_ptr(),
1508            prep.active_bins.len(),
1509            coords.as_ptr(),
1510            n,
1511            parts,
1512            assign.as_mut_ptr(),
1513            got_w.as_mut_ptr(),
1514            method as u8,
1515        )
1516    };
1517    match rc {
1518        0 => {}
1519        2 => return Err(Error::NoDevice),
1520        _ => return Err(Error::NoDevice),
1521    }
1522    if got_w != prep.graph.grid.weight {
1523        return Err(Error::DeviceMismatch);
1524    }
1525    for &d in &assign {
1526        if d >= parts {
1527            return Err(Error::DeviceMismatch);
1528        }
1529    }
1530    Ok(assign)
1531}
1532
1533fn cell_coords(grid: &CellGrid) -> Vec<u32> {
1534    let mut coords = Vec::with_capacity(grid.ncell() * 3);
1535    for iz in 0..grid.nz {
1536        for iy in 0..grid.ny {
1537            for ix in 0..grid.nx {
1538                coords.push(ix as u32);
1539                coords.push(iy as u32);
1540                coords.push(iz as u32);
1541            }
1542        }
1543    }
1544    coords
1545}
1546
1547/// Weighted prefix of `order`. A zero total weight treats every cell as weight 1.
1548pub fn prefix_assign(order: &[u32], weight: &[u64], parts: u32) -> Vec<u32> {
1549    let n = weight.len();
1550    let mut assign = vec![0u32; n];
1551    if parts == 0 || n == 0 {
1552        return assign;
1553    }
1554    let total: u64 = weight.iter().copied().sum();
1555    let mut before = 0u64;
1556    for &cell in order {
1557        let w = if total == 0 { 1 } else { weight[cell as usize] };
1558        let tot = if total == 0 { n as u64 } else { total };
1559        assign[cell as usize] = owner_of(before, w, tot, parts);
1560        before += w;
1561    }
1562    assign
1563}
1564
1565fn owner_of(before: u64, weight: u64, total: u64, parts: u32) -> u32 {
1566    if total == 0 || parts == 0 {
1567        return 0;
1568    }
1569    let num = (2u128 * u128::from(before) + u128::from(weight)) * u128::from(parts);
1570    let den = 2u128 * u128::from(total);
1571    let mut owner = (num / den) as u32;
1572    if owner >= parts {
1573        owner = parts - 1;
1574    }
1575    owner
1576}
1577
1578static SELECT_NS: AtomicU64 = AtomicU64::new(0);
1579static FM_NS: AtomicU64 = AtomicU64::new(0);
1580static COARSE_NS: AtomicU64 = AtomicU64::new(0);
1581static PACK_NS: AtomicU64 = AtomicU64::new(0);
1582static REPAIR_NS: AtomicU64 = AtomicU64::new(0);
1583static CHECK_NS: AtomicU64 = AtomicU64::new(0);
1584static SCHEDULE_NS: AtomicU64 = AtomicU64::new(0);
1585
1586/// Zero the phase counters used by the next partition.
1587pub fn profile_reset() {
1588    SELECT_NS.store(0, AtomicOrdering::Relaxed);
1589    FM_NS.store(0, AtomicOrdering::Relaxed);
1590    COARSE_NS.store(0, AtomicOrdering::Relaxed);
1591    PACK_NS.store(0, AtomicOrdering::Relaxed);
1592    REPAIR_NS.store(0, AtomicOrdering::Relaxed);
1593    CHECK_NS.store(0, AtomicOrdering::Relaxed);
1594    SCHEDULE_NS.store(0, AtomicOrdering::Relaxed);
1595}
1596
1597/// Critical-path wall time, in nanoseconds.
1598///
1599/// The fields are the weighted median, boundary refinement, coarsening,
1600/// packing, the balance repair, the graph check, and join scheduling.
1601/// Packing fills coordinates, measures the span, and splits cell ids.
1602/// Scheduling is the join wall beyond the child that ran. Each value is
1603/// the sum over the calls since [`profile_reset`]. One thread adds the
1604/// children, because the join runs them in order.
1605pub fn profile_ns() -> (u64, u64, u64, u64, u64, u64, u64) {
1606    (
1607        SELECT_NS.load(AtomicOrdering::Relaxed),
1608        FM_NS.load(AtomicOrdering::Relaxed),
1609        COARSE_NS.load(AtomicOrdering::Relaxed),
1610        PACK_NS.load(AtomicOrdering::Relaxed),
1611        REPAIR_NS.load(AtomicOrdering::Relaxed),
1612        CHECK_NS.load(AtomicOrdering::Relaxed),
1613        SCHEDULE_NS.load(AtomicOrdering::Relaxed),
1614    )
1615}
1616
1617fn axis_coord(geom: &RcbGeom, axis: usize, id: u32) -> f64 {
1618    match axis {
1619        0 => geom.x[id as usize],
1620        1 => geom.y[id as usize],
1621        _ => geom.z[id as usize],
1622    }
1623}
1624
1625fn coord_before(geom: &RcbGeom, axis: usize, a: u32, b: u32) -> bool {
1626    let ca = axis_coord(geom, axis, a);
1627    let cb = axis_coord(geom, axis, b);
1628    ca < cb || (ca == cb && a < b)
1629}
1630
1631fn partition_at(ids: &mut [u32], geom: &RcbGeom, axis: usize, lo: usize, hi: usize) -> usize {
1632    let mid = lo + (hi - lo) / 2;
1633    let a = ids[lo];
1634    let b = ids[mid];
1635    let c = ids[hi - 1];
1636    let pivot = if coord_before(geom, axis, a, b) {
1637        if coord_before(geom, axis, b, c) {
1638            b
1639        } else if coord_before(geom, axis, a, c) {
1640            c
1641        } else {
1642            a
1643        }
1644    } else if coord_before(geom, axis, a, c) {
1645        a
1646    } else if coord_before(geom, axis, b, c) {
1647        c
1648    } else {
1649        b
1650    };
1651    let mut pivot_at = lo;
1652    if ids[mid] == pivot {
1653        pivot_at = mid;
1654    } else if ids[hi - 1] == pivot {
1655        pivot_at = hi - 1;
1656    }
1657    ids.swap(pivot_at, hi - 1);
1658    let pivot = ids[hi - 1];
1659    let mut store = lo;
1660    for i in lo..hi - 1 {
1661        if coord_before(geom, axis, ids[i], pivot) {
1662            ids.swap(store, i);
1663            store += 1;
1664        }
1665    }
1666    ids.swap(store, hi - 1);
1667    store
1668}
1669
1670fn clamp_cut(cut: usize, n: usize) -> usize {
1671    if n <= 1 {
1672        return 0;
1673    }
1674    cut.clamp(1, n - 1)
1675}
1676
1677fn subset_cut(ids: &[u32], cut: usize, graph: &CellGraph, side: &mut [u8]) -> u64 {
1678    side.fill(0);
1679    for &id in &ids[..cut] {
1680        side[id as usize] = 1;
1681    }
1682    for &id in &ids[cut..] {
1683        side[id as usize] = 2;
1684    }
1685    let side_ref: &[u8] = side;
1686    let left = &ids[..cut];
1687    #[cfg(feature = "parallel")]
1688    {
1689        if crate::pool_width() > 1 && left.len() > 1 {
1690            use rayon::prelude::*;
1691            let chunk = work_chunk(left.len());
1692            return left
1693                .par_chunks(chunk)
1694                .map(|group| crossing_weight(group, graph, side_ref))
1695                .sum();
1696        }
1697    }
1698    crossing_weight(left, graph, side_ref)
1699}
1700
1701fn crossing_weight(group: &[u32], graph: &CellGraph, side: &[u8]) -> u64 {
1702    let mut crossed = 0u64;
1703    for &id in group {
1704        let lo = graph.offsets[id as usize] as usize;
1705        let hi = graph.offsets[id as usize + 1] as usize;
1706        for e in lo..hi {
1707            let nbr = graph.neighbor[e] as usize;
1708            if side[nbr] == 2 {
1709                crossed += graph.edge_weight[e];
1710            }
1711        }
1712    }
1713    crossed
1714}
1715
1716#[cfg(feature = "parallel")]
1717fn work_chunk(n: usize) -> usize {
1718    let threads = {
1719        #[cfg(feature = "parallel")]
1720        {
1721            crate::pool_width().max(1)
1722        }
1723        #[cfg(not(feature = "parallel"))]
1724        {
1725            1
1726        }
1727    };
1728    (n / threads).max(1)
1729}
1730
1731/// Weighted median on each axis. Keeps the split with the smaller edge cut.
1732/// Ties keep `prefer`, which is the longest geometric axis.
1733fn lightest_axis(
1734    ids: &mut [u32],
1735    geom: &RcbGeom,
1736    graph: &CellGraph,
1737    total: u64,
1738    parts: u32,
1739    parts_l: u32,
1740    prefer: usize,
1741) -> usize {
1742    let saved = ids.to_vec();
1743    let mut side = vec![0u8; graph.grid.ncell()];
1744    let mut best_score = u64::MAX;
1745    let mut best_order = saved.clone();
1746    let mut best_at = 0usize;
1747    for axis_try in 0..3 {
1748        ids.copy_from_slice(&saved);
1749        let at = clamp_cut(
1750            if total == 0 {
1751                ids.len() * parts_l as usize / parts.max(1) as usize
1752            } else {
1753                weighted_cut(ids, geom, axis_try, total, parts, parts_l)
1754            },
1755            ids.len(),
1756        );
1757        let score = subset_cut(ids, at, graph, &mut side);
1758        let better = score < best_score || (score == best_score && axis_try == prefer);
1759        if better {
1760            best_score = score;
1761            best_order.copy_from_slice(ids);
1762            best_at = at;
1763        }
1764    }
1765    ids.copy_from_slice(&best_order);
1766    best_at
1767}
1768
1769/// Light side of a weighted median. Average linear in the slice length.
1770///
1771/// A slice already ordered by cell id uses one histogram per axis. The
1772/// bin count is the integer span of that coordinate, which is fixed by
1773/// the cells in the slice. Ties stay on cell id, so the light set matches
1774/// the serial quickselect.
1775fn weighted_cut(
1776    ids: &mut [u32],
1777    geom: &RcbGeom,
1778    axis: usize,
1779    total: u64,
1780    parts: u32,
1781    parts_l: u32,
1782) -> usize {
1783    if total > 0 && ids_increase(ids) {
1784        if let Some(cut) = weighted_cut_bins(ids, geom, axis, total, parts, parts_l) {
1785            return cut;
1786        }
1787    }
1788    weighted_cut_quick(ids, geom, axis, total, parts, parts_l)
1789}
1790
1791fn ids_increase(ids: &[u32]) -> bool {
1792    ids.windows(2).all(|pair| pair[0] < pair[1])
1793}
1794
1795fn coord_i64(geom: &RcbGeom, axis: usize, id: u32) -> Option<i64> {
1796    let value = axis_coord(geom, axis, id);
1797    if !value.is_finite() {
1798        return None;
1799    }
1800    let whole = value as i64;
1801    if whole as f64 != value {
1802        return None;
1803    }
1804    Some(whole)
1805}
1806
1807fn weighted_cut_bins(
1808    ids: &mut [u32],
1809    geom: &RcbGeom,
1810    axis: usize,
1811    total: u64,
1812    parts: u32,
1813    parts_l: u32,
1814) -> Option<usize> {
1815    let n = ids.len();
1816    if n < 2 {
1817        return Some(clamp_cut(0, n));
1818    }
1819    let mut min_c = i64::MAX;
1820    let mut max_c = i64::MIN;
1821    for &id in ids.iter() {
1822        let c = coord_i64(geom, axis, id)?;
1823        min_c = min_c.min(c);
1824        max_c = max_c.max(c);
1825    }
1826    let bins = (max_c - min_c + 1) as usize;
1827    if bins == 0 || bins > n {
1828        return None;
1829    }
1830    let (hist_w, hist_n) = bin_hist(ids, geom, axis, min_c, bins)?;
1831    let mut before_w = 0u64;
1832    let mut before_n = 0usize;
1833    let mut cut_bin = None;
1834    for b in 0..bins {
1835        let w = hist_w[b];
1836        let count = hist_n[b];
1837        if count == 0 {
1838            continue;
1839        }
1840        if owner_of(before_w.saturating_add(w), 0, total, parts) < parts_l {
1841            before_w = before_w.saturating_add(w);
1842            before_n += count;
1843            continue;
1844        }
1845        cut_bin = Some((b, before_w, before_n));
1846        break;
1847    }
1848    let (cut_b, before_w, before_n) = cut_bin.unwrap_or((bins, before_w, before_n));
1849    let cut_c = min_c + cut_b as i64;
1850    let take = if cut_b >= bins || owner_of(before_w, 0, total, parts) >= parts_l {
1851        0
1852    } else {
1853        bin_take(ids, geom, axis, cut_c, before_w, total, parts, parts_l)
1854    };
1855    let light_n = before_n + take;
1856    let cut = clamp_cut(light_n, n);
1857    arrange_cut(ids, geom, axis, cut_c, take, cut);
1858    Some(cut)
1859}
1860
1861fn bin_hist(
1862    ids: &[u32],
1863    geom: &RcbGeom,
1864    axis: usize,
1865    min_c: i64,
1866    bins: usize,
1867) -> Option<(Vec<u64>, Vec<usize>)> {
1868    let one = |group: &[u32]| -> Option<(Vec<u64>, Vec<usize>)> {
1869        let mut weight = vec![0u64; bins];
1870        let mut count = vec![0usize; bins];
1871        for &id in group {
1872            let c = coord_i64(geom, axis, id)?;
1873            let b = (c - min_c) as usize;
1874            if b >= bins {
1875                return None;
1876            }
1877            weight[b] = weight[b].saturating_add(geom.w[id as usize]);
1878            count[b] += 1;
1879        }
1880        Some((weight, count))
1881    };
1882    #[cfg(feature = "parallel")]
1883    {
1884        if crate::pool_width() > 1 && ids.len() > 1 {
1885            use rayon::prelude::*;
1886            let chunk = work_chunk(ids.len());
1887            let parts: Vec<Option<(Vec<u64>, Vec<usize>)>> =
1888                ids.par_chunks(chunk).map(one).collect();
1889            let mut weight = vec![0u64; bins];
1890            let mut count = vec![0usize; bins];
1891            for part in parts {
1892                let (w, c) = part?;
1893                for b in 0..bins {
1894                    weight[b] = weight[b].saturating_add(w[b]);
1895                    count[b] += c[b];
1896                }
1897            }
1898            return Some((weight, count));
1899        }
1900    }
1901    one(ids)
1902}
1903
1904fn bin_take(
1905    ids: &[u32],
1906    geom: &RcbGeom,
1907    axis: usize,
1908    cut_c: i64,
1909    mut before_w: u64,
1910    total: u64,
1911    parts: u32,
1912    parts_l: u32,
1913) -> usize {
1914    let mut take = 0usize;
1915    for &id in ids {
1916        let Some(c) = coord_i64(geom, axis, id) else {
1917            continue;
1918        };
1919        if c != cut_c {
1920            continue;
1921        }
1922        let w = geom.w[id as usize];
1923        if owner_of(before_w, w, total, parts) >= parts_l {
1924            break;
1925        }
1926        before_w = before_w.saturating_add(w);
1927        take += 1;
1928    }
1929    take
1930}
1931
1932fn arrange_cut(ids: &mut [u32], geom: &RcbGeom, axis: usize, cut_c: i64, take: usize, cut: usize) {
1933    #[cfg(feature = "parallel")]
1934    if crate::pool_width() > 1 && ids.len() >= 4096 {
1935        arrange_cut_parallel(ids, geom, axis, cut_c, take);
1936        return;
1937    }
1938    let _ = cut;
1939    arrange_cut_serial(ids, geom, axis, cut_c, take);
1940}
1941
1942/// Split the slice in encounter order. Cells below the cut bin, then the
1943/// first `take` cells of that bin, stay on the light side.
1944fn arrange_cut_serial(ids: &mut [u32], geom: &RcbGeom, axis: usize, cut_c: i64, take: usize) {
1945    let mut seen = 0usize;
1946    let mut light = Vec::with_capacity(ids.len());
1947    let mut heavy = Vec::with_capacity(ids.len());
1948    for &id in ids.iter() {
1949        let Some(c) = coord_i64(geom, axis, id) else {
1950            heavy.push(id);
1951            continue;
1952        };
1953        if c < cut_c || (c == cut_c && seen < take) {
1954            if c == cut_c {
1955                seen += 1;
1956            }
1957            light.push(id);
1958        } else {
1959            heavy.push(id);
1960        }
1961    }
1962    let n = light.len();
1963    ids[..n].copy_from_slice(&light);
1964    ids[n..].copy_from_slice(&heavy);
1965}
1966
1967/// Same light set and same order as [`arrange_cut_serial`], with one
1968/// chunk of the slice per thread.
1969#[cfg(feature = "parallel")]
1970fn arrange_cut_parallel(ids: &mut [u32], geom: &RcbGeom, axis: usize, cut_c: i64, take: usize) {
1971    use rayon::prelude::*;
1972    let chunk = work_chunk(ids.len());
1973    let groups: Vec<(Vec<u32>, Vec<u32>, Vec<u32>)> = ids
1974        .par_chunks(chunk)
1975        .map(|group| {
1976            let mut below = Vec::new();
1977            let mut equal = Vec::new();
1978            let mut above = Vec::new();
1979            for &id in group {
1980                match coord_i64(geom, axis, id) {
1981                    Some(c) if c < cut_c => below.push(id),
1982                    Some(c) if c == cut_c => equal.push(id),
1983                    _ => above.push(id),
1984                }
1985            }
1986            (below, equal, above)
1987        })
1988        .collect();
1989    let mut below = Vec::new();
1990    let mut equal = Vec::new();
1991    let mut above = Vec::new();
1992    for (lo, mid, hi) in groups {
1993        below.extend(lo);
1994        equal.extend(mid);
1995        above.extend(hi);
1996    }
1997    let take = take.min(equal.len());
1998    let light_n = below.len() + take;
1999    ids[..below.len()].copy_from_slice(&below);
2000    ids[below.len()..light_n].copy_from_slice(&equal[..take]);
2001    let rest = equal.len() - take;
2002    ids[light_n..light_n + rest].copy_from_slice(&equal[take..]);
2003    ids[light_n + rest..].copy_from_slice(&above);
2004}
2005
2006/// Span and weight of a slice. Threads own disjoint id ranges.
2007fn slice_span(ids: &[u32], geom: &RcbGeom) -> ([f64; 3], [f64; 3], u64) {
2008    let one = |group: &[u32]| {
2009        let mut min = [f64::MAX; 3];
2010        let mut max = [f64::MIN; 3];
2011        let mut total = 0u64;
2012        for &id in group {
2013            let c = [
2014                geom.x[id as usize],
2015                geom.y[id as usize],
2016                geom.z[id as usize],
2017            ];
2018            for axis in 0..3 {
2019                min[axis] = min[axis].min(c[axis]);
2020                max[axis] = max[axis].max(c[axis]);
2021            }
2022            total = total.saturating_add(geom.w[id as usize]);
2023        }
2024        (min, max, total)
2025    };
2026    #[cfg(feature = "parallel")]
2027    if crate::pool_width() > 1 && ids.len() >= 4096 {
2028        use rayon::prelude::*;
2029        let chunk = work_chunk(ids.len());
2030        let parts: Vec<_> = ids.par_chunks(chunk).map(one).collect();
2031        let mut min = [f64::MAX; 3];
2032        let mut max = [f64::MIN; 3];
2033        let mut total = 0u64;
2034        for (lo, hi, weight) in parts {
2035            for axis in 0..3 {
2036                min[axis] = min[axis].min(lo[axis]);
2037                max[axis] = max[axis].max(hi[axis]);
2038            }
2039            total = total.saturating_add(weight);
2040        }
2041        return (min, max, total);
2042    }
2043    one(ids)
2044}
2045
2046fn weighted_cut_quick(
2047    ids: &mut [u32],
2048    geom: &RcbGeom,
2049    axis: usize,
2050    total: u64,
2051    parts: u32,
2052    parts_l: u32,
2053) -> usize {
2054    fn walk(
2055        ids: &mut [u32],
2056        geom: &RcbGeom,
2057        axis: usize,
2058        lo: usize,
2059        hi: usize,
2060        before: u64,
2061        total: u64,
2062        parts: u32,
2063        parts_l: u32,
2064    ) -> usize {
2065        if hi <= lo {
2066            return lo;
2067        }
2068        if hi - lo == 1 {
2069            let w = geom.w[ids[lo] as usize];
2070            return if owner_of(before, w, total, parts) >= parts_l {
2071                lo
2072            } else {
2073                lo + 1
2074            };
2075        }
2076        let pivot = partition_at(ids, geom, axis, lo, hi);
2077        let mut left_w = before;
2078        for id in &ids[lo..pivot] {
2079            left_w += geom.w[*id as usize];
2080        }
2081        let pivot_w = geom.w[ids[pivot] as usize];
2082        if owner_of(left_w, pivot_w, total, parts) >= parts_l {
2083            walk(ids, geom, axis, lo, pivot, before, total, parts, parts_l)
2084        } else {
2085            walk(
2086                ids,
2087                geom,
2088                axis,
2089                pivot + 1,
2090                hi,
2091                left_w + pivot_w,
2092                total,
2093                parts,
2094                parts_l,
2095            )
2096        }
2097    }
2098    let cut = walk(ids, geom, axis, 0, ids.len(), 0, total, parts, parts_l);
2099    cut.clamp(1, ids.len().saturating_sub(1))
2100}
2101
2102fn rcb_assign(graph: &CellGraph, parts: u32, refine_cuts: bool, ratio: (u64, u64)) -> Vec<u32> {
2103    let n = graph.grid.ncell();
2104    let t_pack = Instant::now();
2105    let mut x = vec![0.0f64; n];
2106    let mut y = vec![0.0f64; n];
2107    let mut z = vec![0.0f64; n];
2108    for c in 0..n {
2109        let (ix, iy, iz) = unravel(c, graph.grid.nx, graph.grid.ny);
2110        x[c] = f64::from(ix);
2111        y[c] = f64::from(iy);
2112        z[c] = f64::from(iz);
2113    }
2114    let geom = RcbGeom {
2115        x,
2116        y,
2117        z,
2118        w: graph.grid.weight.clone(),
2119    };
2120    let mut ids: Vec<u32> = (0..n as u32).collect();
2121    let mut out = vec![0u32; n];
2122    PACK_NS.fetch_add(t_pack.elapsed().as_nanos() as u64, AtomicOrdering::Relaxed);
2123    let phase = rcb_slice(
2124        &mut ids,
2125        parts,
2126        0,
2127        &geom,
2128        SendPtr(out.as_mut_ptr()),
2129        graph,
2130        refine_cuts,
2131        ratio,
2132    );
2133    record_phase(phase);
2134    out
2135}
2136
2137#[derive(Clone, Copy)]
2138struct SendPtr(*mut u32);
2139unsafe impl Send for SendPtr {}
2140unsafe impl Sync for SendPtr {}
2141
2142/// Wall time of one bisection subtree.
2143///
2144/// `select`, `fm`, and `pack` are sequential on a single branch. A join
2145/// keeps the slower child when more than one thread is in the pool, and
2146/// adds the children when the join is serial.
2147#[derive(Clone, Copy, Default)]
2148struct Phase {
2149    select: u64,
2150    fm: u64,
2151    pack: u64,
2152    schedule: u64,
2153}
2154
2155#[cfg(feature = "parallel")]
2156fn phase_wall(phase: Phase) -> u64 {
2157    phase
2158        .select
2159        .saturating_add(phase.fm)
2160        .saturating_add(phase.pack)
2161        .saturating_add(phase.schedule)
2162}
2163
2164fn record_phase(phase: Phase) {
2165    SELECT_NS.fetch_add(phase.select, AtomicOrdering::Relaxed);
2166    FM_NS.fetch_add(phase.fm, AtomicOrdering::Relaxed);
2167    PACK_NS.fetch_add(phase.pack, AtomicOrdering::Relaxed);
2168    SCHEDULE_NS.fetch_add(phase.schedule, AtomicOrdering::Relaxed);
2169}
2170
2171#[cfg(feature = "parallel")]
2172fn join_measured(a: Phase, b: Phase, wall: u64) -> Phase {
2173    let sum_w = phase_wall(a).saturating_add(phase_wall(b));
2174    let max_w = phase_wall(a).max(phase_wall(b));
2175    // A sequential join lasts about as long as the two children.
2176    // An overlapped join finishes before that sum.
2177    // The slack is one tick of Instant, measured on this host.
2178    let overlapped = wall.saturating_add(timer_resolution_ns()) < sum_w;
2179    let mut child = if overlapped {
2180        if phase_wall(a) >= phase_wall(b) {
2181            a
2182        } else {
2183            b
2184        }
2185    } else {
2186        Phase {
2187            select: a.select.saturating_add(b.select),
2188            fm: a.fm.saturating_add(b.fm),
2189            pack: a.pack.saturating_add(b.pack),
2190            schedule: a.schedule.saturating_add(b.schedule),
2191        }
2192    };
2193    let base = if overlapped { max_w } else { sum_w };
2194    if wall > base {
2195        child.schedule = child.schedule.saturating_add(wall - base);
2196    }
2197    child
2198}
2199
2200fn phase_join(a: Phase, b: Phase) -> Phase {
2201    #[cfg(feature = "parallel")]
2202    {
2203        if crate::pool_width() > 1 {
2204            return if phase_wall(a) >= phase_wall(b) { a } else { b };
2205        }
2206    }
2207    Phase {
2208        select: a.select.saturating_add(b.select),
2209        fm: a.fm.saturating_add(b.fm),
2210        pack: a.pack.saturating_add(b.pack),
2211        schedule: a.schedule.saturating_add(b.schedule),
2212    }
2213}
2214
2215fn phase_after(select_here: u64, fm_here: u64, pack_here: u64, child: Phase) -> Phase {
2216    Phase {
2217        select: select_here.saturating_add(child.select),
2218        fm: fm_here.saturating_add(child.fm),
2219        pack: pack_here.saturating_add(child.pack),
2220        schedule: child.schedule,
2221    }
2222}
2223
2224struct RcbGeom {
2225    x: Vec<f64>,
2226    y: Vec<f64>,
2227    z: Vec<f64>,
2228    w: Vec<u64>,
2229}
2230
2231fn rcb_slice(
2232    ids: &mut [u32],
2233    parts: u32,
2234    part0: u32,
2235    geom: &RcbGeom,
2236    out: SendPtr,
2237    graph: &CellGraph,
2238    refine_cuts: bool,
2239    ratio: (u64, u64),
2240) -> Phase {
2241    if ids.is_empty() {
2242        return Phase::default();
2243    }
2244    if parts <= 1 || ids.len() == 1 {
2245        let t_pack = Instant::now();
2246        for &id in ids.iter() {
2247            // Each cell id is written by exactly one bisection branch.
2248            unsafe { out.0.add(id as usize).write(part0) };
2249        }
2250        return Phase {
2251            select: 0,
2252            fm: 0,
2253            pack: t_pack.elapsed().as_nanos() as u64,
2254            schedule: 0,
2255        };
2256    }
2257    let parts_l = parts / 2;
2258    let parts_r = parts - parts_l;
2259    let t_pack = Instant::now();
2260    let (min, max, total) = slice_span(ids, geom);
2261    let span = [max[0] - min[0], max[1] - min[1], max[2] - min[2]];
2262    let axis = if span[0] >= span[1] && span[0] >= span[2] {
2263        0
2264    } else if span[1] >= span[2] {
2265        1
2266    } else {
2267        2
2268    };
2269    let pack_span = t_pack.elapsed().as_nanos() as u64;
2270    let t_sel = Instant::now();
2271    let mut cut = if refine_cuts {
2272        // The longest axis is not the lightest cut when pair counts differ.
2273        lightest_axis(ids, geom, graph, total, parts, parts_l, axis)
2274    } else if total == 0 {
2275        ids.len() * parts_l as usize / parts as usize
2276    } else {
2277        weighted_cut(ids, geom, axis, total, parts, parts_l)
2278    };
2279    let select_here = t_sel.elapsed().as_nanos() as u64;
2280    if cut == 0 {
2281        cut = 1;
2282    }
2283    if cut >= ids.len() {
2284        cut = ids.len() - 1;
2285    }
2286    // The weighted cut already lays the light cells in the prefix. The two
2287    // sides descend from that prefix, with no second copy of the ids.
2288    if !refine_cuts {
2289        let (left_ids, right_ids) = ids.split_at_mut(cut);
2290        let child = descend(
2291            left_ids,
2292            parts_l,
2293            part0,
2294            right_ids,
2295            parts_r,
2296            part0 + parts_l,
2297            geom,
2298            out,
2299            graph,
2300            refine_cuts,
2301            ratio,
2302        );
2303        return phase_after(select_here, 0, pack_span, child);
2304    }
2305    let t_side = Instant::now();
2306    let mut side = vec![1u8; ids.len()];
2307    for s in side.iter_mut().take(cut) {
2308        *s = 0;
2309    }
2310    let pack_side = t_side.elapsed().as_nanos() as u64;
2311    let t_fm = Instant::now();
2312    bipartition_fm(ids, &mut side, geom, graph, parts_l, parts_r, ratio);
2313    let fm_here = t_fm.elapsed().as_nanos() as u64;
2314    let t_split = Instant::now();
2315    let mut left = Vec::new();
2316    let mut right = Vec::new();
2317    for (i, &id) in ids.iter().enumerate() {
2318        if side[i] == 0 {
2319            left.push(id);
2320        } else {
2321            right.push(id);
2322        }
2323    }
2324    let pack_here = pack_span
2325        .saturating_add(pack_side)
2326        .saturating_add(t_split.elapsed().as_nanos() as u64);
2327    let child = if left.is_empty() || right.is_empty() {
2328        let (left_ids, right_ids) = ids.split_at_mut(cut);
2329        descend(
2330            left_ids,
2331            parts_l,
2332            part0,
2333            right_ids,
2334            parts_r,
2335            part0 + parts_l,
2336            geom,
2337            out,
2338            graph,
2339            refine_cuts,
2340            ratio,
2341        )
2342    } else {
2343        descend(
2344            &mut left,
2345            parts_l,
2346            part0,
2347            &mut right,
2348            parts_r,
2349            part0 + parts_l,
2350            geom,
2351            out,
2352            graph,
2353            refine_cuts,
2354            ratio,
2355        )
2356    };
2357    let t_drop = Instant::now();
2358    drop(left);
2359    drop(right);
2360    drop(side);
2361    let pack_drop = t_drop.elapsed().as_nanos() as u64;
2362    phase_after(
2363        select_here,
2364        fm_here,
2365        pack_here.saturating_add(pack_drop),
2366        child,
2367    )
2368}
2369
2370fn descend(
2371    left: &mut [u32],
2372    parts_l: u32,
2373    part_l: u32,
2374    right: &mut [u32],
2375    parts_r: u32,
2376    part_r: u32,
2377    geom: &RcbGeom,
2378    out: SendPtr,
2379    graph: &CellGraph,
2380    refine_cuts: bool,
2381    ratio: (u64, u64),
2382) -> Phase {
2383    #[cfg(feature = "parallel")]
2384    if crate::pool_width() > 1 {
2385        let left_out = out;
2386        let right_out = out;
2387        let t_join = Instant::now();
2388        let (a, b) = rayon::join(
2389            move || {
2390                rcb_slice(
2391                    left,
2392                    parts_l,
2393                    part_l,
2394                    geom,
2395                    left_out,
2396                    graph,
2397                    refine_cuts,
2398                    ratio,
2399                )
2400            },
2401            move || {
2402                rcb_slice(
2403                    right,
2404                    parts_r,
2405                    part_r,
2406                    geom,
2407                    right_out,
2408                    graph,
2409                    refine_cuts,
2410                    ratio,
2411                )
2412            },
2413        );
2414        let wall = t_join.elapsed().as_nanos() as u64;
2415        return join_measured(a, b, wall);
2416    }
2417    {
2418        let a = rcb_slice(left, parts_l, part_l, geom, out, graph, refine_cuts, ratio);
2419        let b = rcb_slice(right, parts_r, part_r, geom, out, graph, refine_cuts, ratio);
2420        phase_join(a, b)
2421    }
2422}
2423
2424/// Fiduccia-Mattheyses across one bisection. `side` is 0 or 1.
2425fn bipartition_fm(
2426    ids: &[u32],
2427    side: &mut [u8],
2428    geom: &RcbGeom,
2429    graph: &CellGraph,
2430    parts_l: u32,
2431    parts_r: u32,
2432    ratio: (u64, u64),
2433) {
2434    let parts = parts_l + parts_r;
2435    if parts_l == 0 || parts_r == 0 {
2436        return;
2437    }
2438    let mut index = vec![usize::MAX; graph.grid.ncell()];
2439    let mut weight_l = 0u64;
2440    let mut weight_r = 0u64;
2441    for (i, &id) in ids.iter().enumerate() {
2442        index[id as usize] = i;
2443        if side[i] == 0 {
2444            weight_l += geom.w[id as usize];
2445        } else {
2446            weight_r += geom.w[id as usize];
2447        }
2448    }
2449    let total = weight_l + weight_r;
2450    loop {
2451        if !boundary_pass(
2452            ids,
2453            side,
2454            &index,
2455            geom,
2456            graph,
2457            parts_l,
2458            parts_r,
2459            parts,
2460            ratio,
2461            total,
2462            &mut weight_l,
2463            &mut weight_r,
2464        ) {
2465            break;
2466        }
2467    }
2468}
2469
2470fn side_limit(total: u64, side_parts: u32, parts: u32, ratio: (u64, u64)) -> u64 {
2471    if total == 0 || parts == 0 {
2472        return 0;
2473    }
2474    let (num, den) = ratio;
2475    let num = u128::from(total) * u128::from(side_parts) * u128::from(num);
2476    let den = u128::from(parts) * u128::from(den);
2477    (num / den) as u64
2478}
2479
2480fn cross_gain(slot: usize, ids: &[u32], side: &[u8], index: &[usize], graph: &CellGraph) -> i64 {
2481    let id = ids[slot] as usize;
2482    let src = side[slot];
2483    let mut to_src = 0i64;
2484    let mut to_dest = 0i64;
2485    let lo = graph.offsets[id] as usize;
2486    let hi = graph.offsets[id + 1] as usize;
2487    for e in lo..hi {
2488        let nbr = graph.neighbor[e] as usize;
2489        let other = index[nbr];
2490        if other == usize::MAX {
2491            continue;
2492        }
2493        let ww = graph.edge_weight[e] as i64;
2494        if side[other] == src {
2495            to_src += ww;
2496        } else {
2497            to_dest += ww;
2498        }
2499    }
2500    to_dest - to_src
2501}
2502
2503fn side_fits(
2504    slot: usize,
2505    ids: &[u32],
2506    side: &[u8],
2507    geom: &RcbGeom,
2508    weight_l: u64,
2509    weight_r: u64,
2510    limit_l: u64,
2511    limit_r: u64,
2512) -> bool {
2513    let w = geom.w[ids[slot] as usize];
2514    let (new_l, new_r) = if side[slot] == 0 {
2515        (weight_l - w, weight_r + w)
2516    } else {
2517        (weight_l + w, weight_r - w)
2518    };
2519    new_l <= limit_l && new_r <= limit_r
2520}
2521
2522#[allow(dead_code)]
2523fn bucket_drop(slot: usize, bins: &mut BTreeMap<i64, Vec<u32>>, loc: &mut [Option<(i64, usize)>]) {
2524    let Some((gain, at)) = loc[slot] else { return };
2525    let bin = bins.get_mut(&gain).unwrap();
2526    let last = bin.len() - 1;
2527    bin.swap(at, last);
2528    let moved = bin[at] as usize;
2529    if moved != slot {
2530        if let Some(entry) = loc[moved].as_mut() {
2531            entry.1 = at;
2532        }
2533    }
2534    bin.pop();
2535    if bin.is_empty() {
2536        bins.remove(&gain);
2537    }
2538    loc[slot] = None;
2539}
2540
2541#[allow(dead_code)]
2542fn bucket_add(
2543    slot: usize,
2544    bins: &mut BTreeMap<i64, Vec<u32>>,
2545    loc: &mut [Option<(i64, usize)>],
2546    ids: &[u32],
2547    side: &[u8],
2548    index: &[usize],
2549    graph: &CellGraph,
2550    geom: &RcbGeom,
2551    locked: &[bool],
2552    weight_l: u64,
2553    weight_r: u64,
2554    limit_l: u64,
2555    limit_r: u64,
2556) {
2557    if locked[slot] {
2558        return;
2559    }
2560    bucket_drop(slot, bins, loc);
2561    if !is_boundary(slot, ids, side, index, graph) {
2562        return;
2563    }
2564    if !side_fits(slot, ids, side, geom, weight_l, weight_r, limit_l, limit_r) {
2565        return;
2566    }
2567    let gain = cross_gain(slot, ids, side, index, graph);
2568    let bin = bins.entry(gain).or_default();
2569    loc[slot] = Some((gain, bin.len()));
2570    bin.push(slot as u32);
2571}
2572
2573#[allow(dead_code)]
2574fn boundary_pass(
2575    ids: &[u32],
2576    side: &mut [u8],
2577    index: &[usize],
2578    geom: &RcbGeom,
2579    graph: &CellGraph,
2580    parts_l: u32,
2581    parts_r: u32,
2582    parts: u32,
2583    ratio: (u64, u64),
2584    total: u64,
2585    weight_l: &mut u64,
2586    weight_r: &mut u64,
2587) -> bool {
2588    let t0 = Instant::now();
2589    let n = ids.len();
2590    let limit_l = side_limit(total, parts_l, parts, ratio);
2591    let limit_r = side_limit(total, parts_r, parts, ratio);
2592    let mut locked = vec![false; n];
2593    let mut loc: Vec<Option<(i64, usize)>> = vec![None; n];
2594    let mut bins: BTreeMap<i64, Vec<u32>> = BTreeMap::new();
2595    // Gains are a pure function of the current sides. The parallel scan
2596    // matches the serial scan, and slots enter each bucket in index order.
2597    let gains = bisect_gains(
2598        ids, side, index, graph, geom, *weight_l, *weight_r, limit_l, limit_r,
2599    );
2600    for slot in 0..n {
2601        let Some(gain) = gains[slot] else {
2602            continue;
2603        };
2604        let bin = bins.entry(gain).or_default();
2605        loc[slot] = Some((gain, bin.len()));
2606        bin.push(slot as u32);
2607    }
2608    let mut moves: Vec<(usize, u8)> = Vec::new();
2609    let mut cum: i128 = 0;
2610    let mut best: i128 = 0;
2611    let mut best_len = 0usize;
2612    // The balance bound lets a part absorb one extra heaviest cell.
2613    // The pass may try that many non-positive moves, then it stops.
2614    let heaviest = ids.iter().map(|&id| geom.w[id as usize]).max().unwrap_or(1);
2615    let mut neg_left = heaviest.max(1) as usize;
2616    while let Some((&gain, _)) = bins.iter().next_back() {
2617        if gain <= 0 {
2618            neg_left = neg_left.saturating_sub(1);
2619            if neg_left == 0 {
2620                break;
2621            }
2622        }
2623        let bin = bins.get_mut(&gain).unwrap();
2624        let slot = bin.pop().unwrap() as usize;
2625        if bin.is_empty() {
2626            bins.remove(&gain);
2627        }
2628        loc[slot] = None;
2629        if locked[slot] {
2630            continue;
2631        }
2632        if !side_fits(
2633            slot, ids, side, geom, *weight_l, *weight_r, limit_l, limit_r,
2634        ) {
2635            continue;
2636        }
2637        let fresh = cross_gain(slot, ids, side, index, graph);
2638        if fresh != gain {
2639            bucket_add(
2640                slot, &mut bins, &mut loc, ids, side, index, graph, geom, &locked, *weight_l,
2641                *weight_r, limit_l, limit_r,
2642            );
2643            continue;
2644        }
2645        let id = ids[slot] as usize;
2646        let w = geom.w[id];
2647        let src = side[slot];
2648        if src == 0 {
2649            *weight_l -= w;
2650            *weight_r += w;
2651            side[slot] = 1;
2652        } else {
2653            *weight_r -= w;
2654            *weight_l += w;
2655            side[slot] = 0;
2656        }
2657        locked[slot] = true;
2658        moves.push((slot, src));
2659        cum += i128::from(fresh);
2660        if cum > best {
2661            best = cum;
2662            best_len = moves.len();
2663        }
2664        let lo = graph.offsets[id] as usize;
2665        let hi = graph.offsets[id + 1] as usize;
2666        for e in lo..hi {
2667            let other = index[graph.neighbor[e] as usize];
2668            if other != usize::MAX && !locked[other] {
2669                bucket_add(
2670                    other, &mut bins, &mut loc, ids, side, index, graph, geom, &locked, *weight_l,
2671                    *weight_r, limit_l, limit_r,
2672                );
2673            }
2674        }
2675    }
2676    if best <= 0 {
2677        best_len = 0;
2678    }
2679    for &(slot, src) in moves
2680        .iter()
2681        .rev()
2682        .take(moves.len().saturating_sub(best_len))
2683    {
2684        let id = ids[slot] as usize;
2685        let w = geom.w[id];
2686        if side[slot] == 0 {
2687            *weight_l -= w;
2688            *weight_r += w;
2689        } else {
2690            *weight_r -= w;
2691            *weight_l += w;
2692        }
2693        side[slot] = src;
2694    }
2695    let _ = t0;
2696    best > 0
2697}
2698
2699fn is_boundary(slot: usize, ids: &[u32], side: &[u8], index: &[usize], graph: &CellGraph) -> bool {
2700    let id = ids[slot] as usize;
2701    let src = side[slot];
2702    let lo = graph.offsets[id] as usize;
2703    let hi = graph.offsets[id + 1] as usize;
2704    for e in lo..hi {
2705        let other = index[graph.neighbor[e] as usize];
2706        if other != usize::MAX && side[other] != src {
2707            return true;
2708        }
2709    }
2710    false
2711}
2712
2713fn bisect_gains(
2714    ids: &[u32],
2715    side: &[u8],
2716    index: &[usize],
2717    graph: &CellGraph,
2718    geom: &RcbGeom,
2719    weight_l: u64,
2720    weight_r: u64,
2721    limit_l: u64,
2722    limit_r: u64,
2723) -> Vec<Option<i64>> {
2724    let n = ids.len();
2725    let one = |slot: usize| -> Option<i64> {
2726        if !is_boundary(slot, ids, side, index, graph) {
2727            return None;
2728        }
2729        if !side_fits(slot, ids, side, geom, weight_l, weight_r, limit_l, limit_r) {
2730            return None;
2731        }
2732        Some(cross_gain(slot, ids, side, index, graph))
2733    };
2734    #[cfg(feature = "parallel")]
2735    {
2736        // The parallel map writes one slot per index, so it matches the
2737        // serial map at every length. One thread stays on the serial map.
2738        if crate::pool_width() > 1 {
2739            use rayon::prelude::*;
2740            return (0..n).into_par_iter().map(one).collect();
2741        }
2742    }
2743    (0..n).map(one).collect()
2744}
2745
2746fn refine(assign: &mut [u32], graph: &CellGraph, parts: u32, ratio: (u64, u64)) {
2747    if parts <= 1 {
2748        return;
2749    }
2750    let t0 = Instant::now();
2751    let weight = &graph.grid.weight;
2752    let mut part_w = vec![0u64; parts as usize];
2753    for (c, &d) in assign.iter().enumerate() {
2754        part_w[d as usize] += weight[c];
2755    }
2756    let total: u64 = part_w.iter().copied().sum();
2757    loop {
2758        if !fm_pass(assign, graph, parts, ratio, &mut part_w, total, weight) {
2759            break;
2760        }
2761    }
2762    FM_NS.fetch_add(t0.elapsed().as_nanos() as u64, AtomicOrdering::Relaxed);
2763}
2764
2765fn kway_proposal(
2766    assign: &[u32],
2767    graph: &CellGraph,
2768    parts: u32,
2769    ratio: (u64, u64),
2770    part_w: &[u64],
2771    total: u64,
2772    weight: &[u64],
2773) -> Vec<Option<(i64, u32)>> {
2774    let n = assign.len();
2775    let one = |cell: usize| -> Option<(i64, u32)> {
2776        if !part_boundary(cell, assign, graph) {
2777            return None;
2778        }
2779        let mut scratch = vec![0u64; parts as usize];
2780        best_move(
2781            cell as u32,
2782            assign,
2783            graph,
2784            parts,
2785            ratio,
2786            part_w,
2787            total,
2788            weight,
2789            &mut scratch,
2790        )
2791    };
2792    #[cfg(feature = "parallel")]
2793    {
2794        // Same rule as the bisection gain scan: every length, and only
2795        // when the pool has more than one thread.
2796        if crate::pool_width() > 1 {
2797            use rayon::prelude::*;
2798            return (0..n).into_par_iter().map(one).collect();
2799        }
2800    }
2801    (0..n).map(one).collect()
2802}
2803
2804#[allow(dead_code)]
2805#[derive(Clone, Copy, Eq, PartialEq)]
2806struct Cand {
2807    gain: i64,
2808    cell: u32,
2809    dest: u32,
2810    stamp: u32,
2811}
2812
2813impl Ord for Cand {
2814    fn cmp(&self, other: &Self) -> Ordering {
2815        self.gain
2816            .cmp(&other.gain)
2817            .then(other.cell.cmp(&self.cell))
2818            .then(other.dest.cmp(&self.dest))
2819    }
2820}
2821
2822impl PartialOrd for Cand {
2823    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
2824        Some(self.cmp(other))
2825    }
2826}
2827
2828#[allow(dead_code)]
2829fn fm_pass(
2830    assign: &mut [u32],
2831    graph: &CellGraph,
2832    parts: u32,
2833    ratio: (u64, u64),
2834    part_w: &mut [u64],
2835    total: u64,
2836    weight: &[u64],
2837) -> bool {
2838    let t0 = Instant::now();
2839    let n = assign.len();
2840    let mut locked = vec![false; n];
2841    let mut stamp = vec![0u32; n];
2842    let mut heap: BinaryHeap<Cand> = BinaryHeap::new();
2843    let mut scratch = vec![0u64; parts as usize];
2844    // The proposal is a pure function of the current assignment. Cells
2845    // are pushed in index order, so the heap matches a serial scan.
2846    let proposal = kway_proposal(assign, graph, parts, ratio, part_w, total, weight);
2847    for cell in 0..n {
2848        let Some((gain, dest)) = proposal[cell] else {
2849            continue;
2850        };
2851        stamp[cell] = stamp[cell].wrapping_add(1);
2852        heap.push(Cand {
2853            gain,
2854            cell: cell as u32,
2855            dest,
2856            stamp: stamp[cell],
2857        });
2858    }
2859    let mut moves: Vec<(u32, u32, u32)> = Vec::new();
2860    let mut cum: i128 = 0;
2861    let mut best: i128 = 0;
2862    let mut best_len = 0usize;
2863    let heaviest = weight.iter().copied().max().unwrap_or(1);
2864    let mut neg_left = heaviest.max(1) as usize;
2865    while let Some(cand) = heap.pop() {
2866        if cand.gain <= 0 {
2867            neg_left = neg_left.saturating_sub(1);
2868            if neg_left == 0 {
2869                break;
2870            }
2871        }
2872        let cell = cand.cell as usize;
2873        if locked[cell] || stamp[cell] != cand.stamp {
2874            continue;
2875        }
2876        let fresh = best_move(
2877            cand.cell,
2878            assign,
2879            graph,
2880            parts,
2881            ratio,
2882            part_w,
2883            total,
2884            weight,
2885            &mut scratch,
2886        );
2887        let Some((gain, dest)) = fresh else {
2888            continue;
2889        };
2890        if gain != cand.gain || dest != cand.dest {
2891            stamp[cell] = stamp[cell].wrapping_add(1);
2892            heap.push(Cand {
2893                gain,
2894                cell: cand.cell,
2895                dest,
2896                stamp: stamp[cell],
2897            });
2898            continue;
2899        }
2900        let src = assign[cell];
2901        let w = weight[cell];
2902        part_w[src as usize] -= w;
2903        part_w[dest as usize] += w;
2904        assign[cell] = dest;
2905        locked[cell] = true;
2906        moves.push((cand.cell, src, dest));
2907        cum += i128::from(gain);
2908        if cum > best {
2909            best = cum;
2910            best_len = moves.len();
2911        }
2912        let lo = graph.offsets[cell] as usize;
2913        let hi = graph.offsets[cell + 1] as usize;
2914        for e in lo..hi {
2915            let nbr = graph.neighbor[e] as usize;
2916            if !locked[nbr] {
2917                push_best(
2918                    nbr as u32,
2919                    assign,
2920                    graph,
2921                    parts,
2922                    ratio,
2923                    part_w,
2924                    total,
2925                    weight,
2926                    &locked,
2927                    &mut stamp,
2928                    &mut scratch,
2929                    &mut heap,
2930                );
2931            }
2932        }
2933    }
2934    if best <= 0 {
2935        best_len = 0;
2936    }
2937    for (cell, src, dest) in moves.iter().rev().take(moves.len() - best_len) {
2938        let w = weight[*cell as usize];
2939        part_w[*dest as usize] -= w;
2940        part_w[*src as usize] += w;
2941        assign[*cell as usize] = *src;
2942    }
2943    let _ = t0;
2944    best > 0
2945}
2946
2947fn part_boundary(cell: usize, assign: &[u32], graph: &CellGraph) -> bool {
2948    let src = assign[cell];
2949    let lo = graph.offsets[cell] as usize;
2950    let hi = graph.offsets[cell + 1] as usize;
2951    for e in lo..hi {
2952        if assign[graph.neighbor[e] as usize] != src {
2953            return true;
2954        }
2955    }
2956    false
2957}
2958
2959#[allow(dead_code)]
2960fn push_best(
2961    cell: u32,
2962    assign: &[u32],
2963    graph: &CellGraph,
2964    parts: u32,
2965    ratio: (u64, u64),
2966    part_w: &[u64],
2967    total: u64,
2968    weight: &[u64],
2969    locked: &[bool],
2970    stamp: &mut [u32],
2971    scratch: &mut [u64],
2972    heap: &mut BinaryHeap<Cand>,
2973) {
2974    if locked[cell as usize] || !part_boundary(cell as usize, assign, graph) {
2975        return;
2976    }
2977    let Some((gain, dest)) = best_move(
2978        cell, assign, graph, parts, ratio, part_w, total, weight, scratch,
2979    ) else {
2980        return;
2981    };
2982    stamp[cell as usize] = stamp[cell as usize].wrapping_add(1);
2983    heap.push(Cand {
2984        gain,
2985        cell,
2986        dest,
2987        stamp: stamp[cell as usize],
2988    });
2989}
2990
2991fn best_move(
2992    cell: u32,
2993    assign: &[u32],
2994    graph: &CellGraph,
2995    parts: u32,
2996    ratio: (u64, u64),
2997    part_w: &[u64],
2998    total: u64,
2999    weight: &[u64],
3000    scratch: &mut [u64],
3001) -> Option<(i64, u32)> {
3002    scratch.fill(0);
3003    let src = assign[cell as usize];
3004    let lo = graph.offsets[cell as usize] as usize;
3005    let hi = graph.offsets[cell as usize + 1] as usize;
3006    for e in lo..hi {
3007        let nbr = graph.neighbor[e] as usize;
3008        let part = assign[nbr] as usize;
3009        scratch[part] = scratch[part].saturating_add(graph.edge_weight[e]);
3010    }
3011    let w = weight[cell as usize];
3012    let mut best: Option<(i64, u32)> = None;
3013    for dest in 0..parts {
3014        if dest == src {
3015            continue;
3016        }
3017        let new_src = part_w[src as usize] - w;
3018        let new_dest = part_w[dest as usize] + w;
3019        if !under_balance(new_src, total, parts, ratio)
3020            || !under_balance(new_dest, total, parts, ratio)
3021        {
3022            continue;
3023        }
3024        let gain = scratch[dest as usize] as i64 - scratch[src as usize] as i64;
3025        let take = match best {
3026            None => true,
3027            Some((g, d)) => gain > g || (gain == g && dest < d),
3028        };
3029        if take {
3030            best = Some((gain, dest));
3031        }
3032    }
3033    best
3034}
3035
3036fn scotch_assign(graph: &CellGraph, parts: u32, ratio: (u64, u64)) -> Result<Vec<u32>, Error> {
3037    #[cfg(not(feature = "scotch"))]
3038    {
3039        let _ = (graph, parts, ratio);
3040        Err(Error::ScotchDisabled)
3041    }
3042    #[cfg(feature = "scotch")]
3043    {
3044        scotch_assign_linked(graph, parts, ratio)
3045    }
3046}
3047
3048#[cfg(feature = "scotch")]
3049fn scotch_assign_linked(
3050    graph: &CellGraph,
3051    parts: u32,
3052    ratio: (u64, u64),
3053) -> Result<Vec<u32>, Error> {
3054    let n = graph.grid.ncell();
3055    if n > i32::MAX as usize || parts > i32::MAX as u32 {
3056        return Err(Error::Overflow);
3057    }
3058    let mut offsets = Vec::with_capacity(n + 1);
3059    let mut edges = Vec::with_capacity(graph.neighbor.len());
3060    let mut vwgt = Vec::with_capacity(n);
3061    let mut ewgt = Vec::with_capacity(graph.edge_weight.len());
3062    for &v in &graph.offsets {
3063        if v > i32::MAX as u32 {
3064            return Err(Error::Overflow);
3065        }
3066        offsets.push(v as i32);
3067    }
3068    for &v in &graph.neighbor {
3069        if v > i32::MAX as u32 {
3070            return Err(Error::Overflow);
3071        }
3072        edges.push(v as i32);
3073    }
3074    for &v in &graph.grid.weight {
3075        if v > i32::MAX as u64 {
3076            return Err(Error::Overflow);
3077        }
3078        vwgt.push(v as i32);
3079    }
3080    for &v in &graph.edge_weight {
3081        if v > i32::MAX as u64 {
3082            return Err(Error::Overflow);
3083        }
3084        ewgt.push(v as i32);
3085    }
3086    let mut part = vec![0i32; n];
3087    let (num, den) = ratio;
3088    let imbalance = (num - den) as f64 / den as f64;
3089    let rc = unsafe {
3090        lc_scotch_part(
3091            n as i32,
3092            offsets.as_ptr(),
3093            edges.as_ptr(),
3094            vwgt.as_ptr(),
3095            ewgt.as_ptr(),
3096            parts as i32,
3097            imbalance,
3098            part.as_mut_ptr(),
3099        )
3100    };
3101    if rc != 0 {
3102        return Err(Error::ScotchFailed);
3103    }
3104    let mut out = Vec::with_capacity(n);
3105    for v in part {
3106        if v < 0 || v as u32 >= parts {
3107            return Err(Error::ScotchFailed);
3108        }
3109        out.push(v as u32);
3110    }
3111    Ok(out)
3112}
3113
3114#[cfg(feature = "scotch")]
3115unsafe extern "C" {
3116    fn lc_scotch_part(
3117        n: i32,
3118        offsets: *const i32,
3119        edges: *const i32,
3120        vwgt: *const i32,
3121        ewgt: *const i32,
3122        parts: i32,
3123        imbalance: f64,
3124        part: *mut i32,
3125    ) -> i32;
3126}
3127
3128fn max_imbalance(weight: &[u64], assign: &[u32], parts: u32) -> f64 {
3129    let mut part_w = vec![0u64; parts as usize];
3130    let mut total = 0u64;
3131    for (c, &d) in assign.iter().enumerate() {
3132        part_w[d as usize] += weight[c];
3133        total += weight[c];
3134    }
3135    if total == 0 {
3136        return 1.0;
3137    }
3138    let mean = total as f64 / parts as f64;
3139    let heavy = part_w.iter().copied().max().unwrap_or(0) as f64;
3140    heavy / mean
3141}
3142
3143fn halo_fraction(
3144    grid: &CellGrid,
3145    assign: &[u32],
3146    parts: u32,
3147    width: [u32; 3],
3148) -> Result<f64, Error> {
3149    let mut best = 0.0f64;
3150    for domain in 0..parts {
3151        let owned = assign.iter().filter(|&&d| d == domain).count();
3152        if owned == 0 {
3153            continue;
3154        }
3155        let ghosts = halo(grid, assign, domain, width)?.len();
3156        let ratio = ghosts as f64 / owned as f64;
3157        if ratio > best {
3158            best = ratio;
3159        }
3160    }
3161    Ok(best)
3162}
3163
3164fn balance_ratio(balance: Option<f64>, weight: &[u64], parts: u32) -> Result<(u64, u64), Error> {
3165    match balance {
3166        None => Ok(derived_balance(weight, parts)),
3167        Some(value) => {
3168            if !value.is_finite() || value < 1.0 {
3169                return Err(Error::BadPartition);
3170            }
3171            // Decimal resolution of a caller-supplied bound.
3172            let den = 1_000_000u64;
3173            let scaled = value * den as f64;
3174            if !scaled.is_finite() || scaled > u64::MAX as f64 {
3175                return Err(Error::BadPartition);
3176            }
3177            let num = scaled.round() as u64;
3178            if num < den {
3179                return Err(Error::BadPartition);
3180            }
3181            Ok((num, den))
3182        }
3183    }
3184}
3185
3186fn under_balance(weight: u64, total: u64, parts: u32, ratio: (u64, u64)) -> bool {
3187    if total == 0 {
3188        return true;
3189    }
3190    let (num, den) = ratio;
3191    u128::from(weight) * u128::from(parts) * u128::from(den) <= u128::from(total) * u128::from(num)
3192}
3193
3194fn bins_needed(length: f64, width: f64) -> Result<u32, Error> {
3195    // A NaN length or width fails `> 0.0` and needs no bins.
3196    if length.partial_cmp(&0.0) != Some(Ordering::Greater)
3197        || width.partial_cmp(&0.0) != Some(Ordering::Greater)
3198    {
3199        return Ok(0);
3200    }
3201    let q = length / width;
3202    if !q.is_finite() {
3203        return Err(Error::Overflow);
3204    }
3205    let ceil = q.ceil();
3206    if !ceil.is_finite() || ceil > u32::MAX as f64 {
3207        return Err(Error::Overflow);
3208    }
3209    let mut n = ceil as u32;
3210    while (n as f64) * width < length {
3211        n = n.saturating_add(1);
3212        if n == u32::MAX {
3213            break;
3214        }
3215    }
3216    Ok(n)
3217}
3218
3219fn check_graph(graph: &CellGraph) -> Result<usize, Error> {
3220    let n = graph.grid.ncell();
3221    if graph.grid.nx <= 0 || graph.grid.ny <= 0 || graph.grid.nz <= 0 {
3222        return Err(Error::BadGraph);
3223    }
3224    let expect = (graph.grid.nx as usize)
3225        .checked_mul(graph.grid.ny as usize)
3226        .and_then(|v| v.checked_mul(graph.grid.nz as usize))
3227        .ok_or(Error::BadGraph)?;
3228    if expect != n || graph.offsets.len() != n + 1 || graph.offsets[0] != 0 {
3229        return Err(Error::BadGraph);
3230    }
3231    if !offsets_increase(&graph.offsets) {
3232        return Err(Error::BadGraph);
3233    }
3234    let narc = graph.offsets[n] as usize;
3235    if graph.neighbor.len() != narc || graph.edge_weight.len() != narc {
3236        return Err(Error::BadGraph);
3237    }
3238    if !neighbors_in_range(&graph.neighbor, n) {
3239        return Err(Error::BadGraph);
3240    }
3241    Ok(n)
3242}
3243
3244fn offsets_increase(offsets: &[u32]) -> bool {
3245    let check = |start: usize, part: &[u32]| -> bool {
3246        let mut prev = if start == 0 { 0 } else { offsets[start - 1] };
3247        for &off in part {
3248            if off < prev {
3249                return false;
3250            }
3251            prev = off;
3252        }
3253        true
3254    };
3255    #[cfg(feature = "parallel")]
3256    {
3257        if crate::pool_width() > 1 && offsets.len() > 1 {
3258            use rayon::prelude::*;
3259            let chunk = work_chunk(offsets.len());
3260            return offsets
3261                .par_chunks(chunk)
3262                .enumerate()
3263                .all(|(index, part)| check(index * chunk, part));
3264        }
3265    }
3266    check(0, offsets)
3267}
3268
3269fn neighbors_in_range(neighbor: &[u32], n: usize) -> bool {
3270    let inside = |part: &[u32]| part.iter().all(|&nbr| (nbr as usize) < n);
3271    #[cfg(feature = "parallel")]
3272    {
3273        if crate::pool_width() > 1 && neighbor.len() > 1 {
3274            use rayon::prelude::*;
3275            let chunk = work_chunk(neighbor.len());
3276            return neighbor.par_chunks(chunk).all(inside);
3277        }
3278    }
3279    inside(neighbor)
3280}
3281
3282fn check_assign(grid: &CellGrid, assign: &[u32]) -> Result<usize, Error> {
3283    let n = grid.ncell();
3284    if assign.len() != n {
3285        return Err(Error::BadPartition);
3286    }
3287    let expect = (grid.nx as usize)
3288        .saturating_mul(grid.ny as usize)
3289        .saturating_mul(grid.nz as usize);
3290    if expect != n {
3291        return Err(Error::BadGraph);
3292    }
3293    Ok(n)
3294}
3295
3296fn unravel(c: usize, nx: i32, ny: i32) -> (i32, i32, i32) {
3297    let nx = nx as usize;
3298    let ny = ny as usize;
3299    let ix = (c % nx) as i32;
3300    let iy = ((c / nx) % ny) as i32;
3301    let iz = (c / (nx * ny)) as i32;
3302    (ix, iy, iz)
3303}
3304
3305fn paint(mark: &mut [u8], nx: i32, ny: i32, nz: i32, ix: i32, iy: i32, iz: i32, width: [u32; 3]) {
3306    let rx = width[0] as i32;
3307    let ry = width[1] as i32;
3308    let rz = width[2] as i32;
3309    for dz in -rz..=rz {
3310        for dy in -ry..=ry {
3311            for dx in -rx..=rx {
3312                let x = rem_euclid(ix + dx, nx);
3313                let y = rem_euclid(iy + dy, ny);
3314                let z = rem_euclid(iz + dz, nz);
3315                let c = ((z as usize * ny as usize) + y as usize) * nx as usize + x as usize;
3316                mark[c] = 1;
3317            }
3318        }
3319    }
3320}
3321
3322fn rem_euclid(v: i32, n: i32) -> i32 {
3323    let mut r = v % n;
3324    if r < 0 {
3325        r += n;
3326    }
3327    r
3328}
3329
3330fn morton_ord(a: u32, b: u32, grid: &CellGrid) -> Ordering {
3331    let (ax, ay, az) = unravel(a as usize, grid.nx, grid.ny);
3332    let (bx, by, bz) = unravel(b as usize, grid.nx, grid.ny);
3333    morton_cmp(
3334        [ax as u32, ay as u32, az as u32],
3335        [bx as u32, by as u32, bz as u32],
3336    )
3337}
3338
3339/// Morton order matching [`morton_key`]: at each bit, `z`, then `y`, then `x`.
3340///
3341/// `x` occupies the least significant bit of each triplet, so it varies
3342/// first along the curve.
3343pub fn morton_cmp(a: [u32; 3], b: [u32; 3]) -> Ordering {
3344    for bit in (0..32).rev() {
3345        let mask = 1u32 << bit;
3346        let az = a[2] & mask;
3347        let bz = b[2] & mask;
3348        if az != bz {
3349            return az.cmp(&bz);
3350        }
3351        let ay = a[1] & mask;
3352        let by = b[1] & mask;
3353        if ay != by {
3354            return ay.cmp(&by);
3355        }
3356        let ax = a[0] & mask;
3357        let bx = b[0] & mask;
3358        if ax != bx {
3359            return ax.cmp(&bx);
3360        }
3361    }
3362    Ordering::Equal
3363}
3364
3365/// Packed Morton key. Coordinates at or above `2^21` do not fit.
3366pub fn morton_key(x: u32, y: u32, z: u32) -> Option<u64> {
3367    if x >= (1 << 21) || y >= (1 << 21) || z >= (1 << 21) {
3368        return None;
3369    }
3370    Some(spread21(x) | (spread21(y) << 1) | (spread21(z) << 2))
3371}
3372
3373fn spread21(v: u32) -> u64 {
3374    let mut x = u64::from(v & 0x1f_ffff);
3375    x = (x | (x << 32)) & 0x001f_0000_0000_ffff;
3376    x = (x | (x << 16)) & 0x001f_0000_ff00_00ff;
3377    x = (x | (x << 8)) & 0x100f_00f0_0f00_f00f;
3378    x = (x | (x << 4)) & 0x10c3_0c30_c30c_30c3;
3379    x = (x | (x << 2)) & 0x1249_2492_4924_9249;
3380    x
3381}
3382
3383fn hilbert_bits(nx: i32, ny: i32, nz: i32) -> u32 {
3384    let n = (nx as u32).max(ny as u32).max(nz as u32);
3385    if n <= 1 {
3386        0
3387    } else {
3388        32 - (n - 1).leading_zeros()
3389    }
3390}
3391
3392/// Hilbert index on a cube of `2^bits` cells per axis (Skilling, 2004).
3393pub fn hilbert_key(x: u32, y: u32, z: u32, bits: u32) -> u64 {
3394    if bits == 0 {
3395        return 0;
3396    }
3397    let mut p = [x, y, z];
3398    let mut q = 1u32 << (bits - 1);
3399    while q > 1 {
3400        let mask = q - 1;
3401        for i in 0..3 {
3402            if p[i] & q != 0 {
3403                p[0] ^= mask;
3404            } else {
3405                let t = (p[0] ^ p[i]) & mask;
3406                p[0] ^= t;
3407                p[i] ^= t;
3408            }
3409        }
3410        q >>= 1;
3411    }
3412    p[1] ^= p[0];
3413    p[2] ^= p[1];
3414    let mut t = 0u32;
3415    q = 1u32 << (bits - 1);
3416    while q > 1 {
3417        if p[2] & q != 0 {
3418            t ^= q - 1;
3419        }
3420        q >>= 1;
3421    }
3422    for v in &mut p {
3423        *v ^= t;
3424    }
3425    let mut key = 0u64;
3426    for b in (0..bits).rev() {
3427        for v in &p {
3428            key = (key << 1) | u64::from((v >> b) & 1);
3429        }
3430    }
3431    key
3432}
3433
3434/// Histogram of flat bin ids.
3435pub fn histogram(bins_of: &[u32], ncell: usize) -> Vec<u64> {
3436    let mut weight = vec![0u64; ncell];
3437    for &b in bins_of {
3438        weight[b as usize] += 1;
3439    }
3440    weight
3441}
3442
3443/// Exclusive prefix. `out[i + 1] - out[i] = values[i]`, `out[0] = 0`.
3444pub fn exclusive_prefix(values: &[u64]) -> Vec<u64> {
3445    let mut out = vec![0u64; values.len() + 1];
3446    for (i, &v) in values.iter().enumerate() {
3447        out[i + 1] = out[i] + v;
3448    }
3449    out
3450}
3451
3452/// The device curve split that `src/gpu/partition.cpp` provides. The GPU
3453/// library registers it with `lc_set_gpu_curve_split` when it is loaded,
3454/// so this crate links without it and a search with no GPU library returns
3455/// [`Error::NoDevice`].
3456pub type DeviceCurveFn = unsafe extern "C" fn(
3457    atom_bin: *const u32,
3458    natom: usize,
3459    coords: *const u32,
3460    ncell: usize,
3461    parts: u32,
3462    assign: *mut u32,
3463    out_weight: *mut u64,
3464    method: u8,
3465) -> i32;
3466
3467static DEVICE_CURVE: std::sync::atomic::AtomicUsize = std::sync::atomic::AtomicUsize::new(0);
3468
3469/// Install the device curve split. `None` removes it.
3470pub fn register_device_curve(f: Option<DeviceCurveFn>) {
3471    DEVICE_CURVE.store(f.map_or(0, |f| f as usize), AtomicOrdering::Release);
3472}
3473
3474#[allow(clippy::too_many_arguments)]
3475unsafe fn call_device_curve(
3476    atom_bin: *const u32,
3477    natom: usize,
3478    coords: *const u32,
3479    ncell: usize,
3480    parts: u32,
3481    assign: *mut u32,
3482    out_weight: *mut u64,
3483    method: u8,
3484) -> i32 {
3485    let raw = DEVICE_CURVE.load(AtomicOrdering::Acquire);
3486    if raw == 0 {
3487        return 2;
3488    }
3489    // SAFETY: only register_device_curve stores a nonzero value, and it
3490    // stores a DeviceCurveFn.
3491    let f: DeviceCurveFn = unsafe { std::mem::transmute::<usize, DeviceCurveFn>(raw) };
3492    unsafe {
3493        f(
3494            atom_bin, natom, coords, ncell, parts, assign, out_weight, method,
3495        )
3496    }
3497}
3498
3499/// C ABI method code. Unknown codes are [`Error::BadPartition`].
3500pub fn method_from_c(code: u8) -> Result<Method, Error> {
3501    Method::from_code(code)
3502}
3503
3504#[cfg(test)]
3505mod tests {
3506    use super::*;
3507
3508    #[test]
3509    fn morton_matches_the_bit_order() {
3510        assert_eq!(morton_key(0, 0, 0), Some(0));
3511        assert_eq!(morton_key(1, 0, 0), Some(1));
3512        assert_eq!(morton_key(0, 1, 0), Some(2));
3513        assert_eq!(morton_key(0, 0, 1), Some(4));
3514        let mut coords = Vec::new();
3515        for z in 0..8u32 {
3516            for y in 0..8 {
3517                for x in 0..8 {
3518                    coords.push([x, y, z]);
3519                }
3520            }
3521        }
3522        let mut by_key = coords.clone();
3523        by_key.sort_by(|a, b| {
3524            morton_key(a[0], a[1], a[2])
3525                .unwrap()
3526                .cmp(&morton_key(b[0], b[1], b[2]).unwrap())
3527        });
3528        let mut by_cmp = coords.clone();
3529        by_cmp.sort_by(|a, b| morton_cmp(*a, *b));
3530        assert_eq!(by_key, by_cmp);
3531    }
3532
3533    #[test]
3534    fn histogram_median_matches_quickselect() {
3535        let mut weight = vec![1u64; 60];
3536        weight[3] = 5;
3537        weight[11] = 8;
3538        weight[40] = 2;
3539        let geom = RcbGeom {
3540            x: (0..60).map(|i| (i % 9) as f64).collect(),
3541            y: (0..60).map(|i| (i % 4) as f64).collect(),
3542            z: (0..60).map(|i| (i % 3) as f64).collect(),
3543            w: weight,
3544        };
3545        let total = geom.w.iter().sum();
3546        for axis in 0..3 {
3547            let mut hist = (0..60u32).collect::<Vec<_>>();
3548            let mut quick = hist.clone();
3549            let got = weighted_cut_bins(&mut hist, &geom, axis, total, 8, 4).unwrap();
3550            let expect = weighted_cut_quick(&mut quick, &geom, axis, total, 8, 4);
3551            assert_eq!(got, expect, "axis {axis}");
3552            let mut a = hist[..got].to_vec();
3553            let mut b = quick[..expect].to_vec();
3554            a.sort();
3555            b.sort();
3556            assert_eq!(a, b, "set axis {axis}");
3557        }
3558    }
3559
3560    #[test]
3561    fn histogram_and_prefix_are_exact() {
3562        let bins_of = [0u32, 1, 1, 2, 0];
3563        let weight = histogram(&bins_of, 4);
3564        assert_eq!(weight, vec![2, 2, 1, 0]);
3565        let prefix = exclusive_prefix(&weight);
3566        assert_eq!(prefix, vec![0, 2, 4, 5, 5]);
3567        assert_eq!(prefix.windows(2).map(|w| w[1] - w[0]).sum::<u64>(), 5);
3568    }
3569
3570    #[test]
3571    fn hilbert_keys_permute_a_cube() {
3572        for bits in 1u32..=4 {
3573            let side = 1u32 << bits;
3574            let mut seen = vec![false; (side * side * side) as usize];
3575            for z in 0..side {
3576                for y in 0..side {
3577                    for x in 0..side {
3578                        let key = hilbert_key(x, y, z, bits) as usize;
3579                        assert!(key < seen.len());
3580                        assert!(!seen[key]);
3581                        seen[key] = true;
3582                    }
3583                }
3584            }
3585            assert!(seen.iter().all(|&v| v));
3586        }
3587        assert_eq!(hilbert_key(0, 0, 0, 1), 0);
3588        assert_eq!(hilbert_key(1, 0, 0, 1), 7);
3589        assert_eq!(hilbert_key(0, 1, 0, 2), 1);
3590        assert_eq!(hilbert_key(1, 1, 1, 2), 5);
3591    }
3592
3593    #[test]
3594    fn replicated_copies_keep_cells_and_arcs() {
3595        let cell = Cell::ortho(8.0, 8.0, 8.0).unwrap();
3596        let xyz: Vec<[f64; 3]> = (0..4).map(|i| [1.0 + i as f64, 1.0, 1.0]).collect();
3597        let graph = cell_graph(&xyz, &cell, 2.0, None, None).unwrap();
3598        let copies = 4;
3599        let tiled = replicate_graph(&graph, copies).unwrap();
3600        assert_eq!(tiled.grid.ncell(), graph.grid.ncell() * copies);
3601        assert_eq!(tiled.neighbor.len(), graph.neighbor.len() * copies);
3602        assert_eq!(tiled.grid.ncell() / copies, graph.grid.ncell());
3603        assert_eq!(tiled.neighbor.len() / copies, graph.neighbor.len());
3604    }
3605
3606    #[test]
3607    fn prefix_puts_each_cell_in_one_part() {
3608        let weight = [1u64, 1, 1, 1];
3609        let order = [0u32, 1, 2, 3];
3610        let assign = prefix_assign(&order, &weight, 2);
3611        assert_eq!(assign.iter().filter(|&&d| d == 0).count(), 2);
3612        assert_eq!(assign.iter().filter(|&&d| d == 1).count(), 2);
3613        assert!(assign.iter().all(|&d| d < 2));
3614    }
3615}