Skip to main content

linkcell/
open_cell.rs

1//! Cutoff pairs on open axes.
2//!
3//! [`crate::pairs_within`](crate::pairs_within) is a periodic list. An
4//! open axis has no images. Padding that axis out to a periodic box
5//! makes the partner stencil depend on the bounding span, so moving one
6//! atom rebuilds it. This walk bins the occupied Cartesian cells. With
7//! every axis open the stencil is the reach in x of each row of bin
8//! offsets, which depends on the bin edge and the cutoff alone, so
9//! frames that occupy other bins reuse it. A periodic axis keeps the
10//! stencil until the bounding bins change.
11
12use std::sync::atomic::{AtomicU64, Ordering};
13use std::sync::{Arc, Mutex};
14
15use crate::bins::certify;
16use crate::pairs::{keep_half, Pair};
17use crate::{Cell, Error};
18
19const MAX_CELLS: i64 = 16_777_216;
20const MAX_IMAGES: i64 = 1 << 24;
21
22static STENCIL_BUILDS: AtomicU64 = AtomicU64::new(0);
23static CACHE: Mutex<Option<Arc<Stencil>>> = Mutex::new(None);
24
25/// How many partner stencils have been built since the process started.
26///
27/// A reused stencil does not increment the count. The periodic list and
28/// the open-cell list share the counter.
29pub fn stencil_builds() -> u64 {
30    STENCIL_BUILDS.load(Ordering::Relaxed)
31}
32
33pub(crate) fn note_stencil_build() {
34    STENCIL_BUILDS.fetch_add(1, Ordering::Relaxed);
35}
36
37/// Options for [`pairs_within_pbc`].
38pub struct PbcQuery<'a> {
39    /// `periodic[k]` is false when lattice axis `k` is open.
40    pub periodic: [bool; 3],
41    /// Pairs with squared distance below `cutoff` squared are kept.
42    /// [`Self::closed`] also keeps the boundary.
43    pub cutoff: f64,
44    /// `None` keeps every point. A `false` entry drops that point as
45    /// both source and candidate.
46    pub mask: Option<&'a [bool]>,
47    /// Bin edge. `None` uses the cutoff, which does not move when the
48    /// bounding span jitters inside a bin.
49    pub cell_hint: Option<f64>,
50    /// Keep one side of `(i, j, S)`.
51    pub half: bool,
52    /// Also keep `dist2 == cutoff²` on an open or mixed cell.
53    pub closed: bool,
54    /// Drop rows with `i == j`, including a periodic image of the source.
55    pub exclude_self_images: bool,
56}
57
58impl<'a> PbcQuery<'a> {
59    /// Fully periodic search. The other flags start unset.
60    pub fn periodic(cutoff: f64) -> Self {
61        Self::new([true, true, true], cutoff)
62    }
63
64    /// Every axis open.
65    pub fn open(cutoff: f64) -> Self {
66        Self::new([false, false, false], cutoff)
67    }
68
69    /// `periodic` selects the axes that take images.
70    pub fn new(periodic: [bool; 3], cutoff: f64) -> Self {
71        Self {
72            periodic,
73            cutoff,
74            mask: None,
75            cell_hint: None,
76            half: false,
77            closed: false,
78            exclude_self_images: false,
79        }
80    }
81
82    /// Set the point mask.
83    pub fn mask(mut self, mask: Option<&'a [bool]>) -> Self {
84        self.mask = mask;
85        self
86    }
87
88    /// Set the bin edge.
89    pub fn cell_hint(mut self, cell_hint: Option<f64>) -> Self {
90        self.cell_hint = cell_hint;
91        self
92    }
93
94    /// Keep one side of each pair.
95    pub fn half(mut self, half: bool) -> Self {
96        self.half = half;
97        self
98    }
99
100    /// Keep the cutoff boundary.
101    pub fn closed(mut self, closed: bool) -> Self {
102        self.closed = closed;
103        self
104    }
105
106    /// Drop `i == j`.
107    pub fn exclude_self_images(mut self, exclude: bool) -> Self {
108        self.exclude_self_images = exclude;
109        self
110    }
111}
112
113/// Cartesian half pair list of an open cluster.
114///
115/// Every axis is open. Row `(i, j, [0, 0, 0], dist2)` has `i < j` and
116/// `dist2 < cutoff²`. The atoms are binned on the occupied Cartesian
117/// cells. One partner stencil serves every call with the same cutoff and
118/// bin edge, so [`stencil_builds`] does not move when later frames occupy
119/// other bins. A reach past 16 bins can widen it when a frame spans more
120/// bins on y or z than it covers.
121///
122/// ```
123/// use linkcell::pairs_open;
124///
125/// let xyz = [[0.0, 0.0, 0.0], [1.0, 0.0, 0.0], [3.0, 0.0, 0.0]];
126/// let rows = pairs_open(&xyz, 1.5, None).unwrap();
127/// assert_eq!(rows.len(), 1);
128/// assert_eq!((rows[0].i, rows[0].j, rows[0].shift), (0, 1, [0, 0, 0]));
129/// ```
130pub fn pairs_open(
131    xyz: &[[f64; 3]],
132    cutoff: f64,
133    cell_hint: Option<f64>,
134) -> Result<Vec<Pair>, Error> {
135    let cell = Cell::ortho(1.0, 1.0, 1.0).map_err(|_| Error::BadBox)?;
136    let query = PbcQuery::open(cutoff).half(true).cell_hint(cell_hint);
137    pairs_within_pbc(xyz, &cell, &query)
138}
139
140/// Cutoff pairs with a periodicity mask.
141///
142/// `query.periodic[k]` false keeps axis `k` out of the image sum. A
143/// fully periodic mask is [`crate::pairs_within`](crate::pairs_within).
144/// Any open axis uses occupied Cartesian bins and no periodic padding.
145/// `cell` supplies the periodic lattice. It is not read when every axis
146/// is open.
147pub fn pairs_within_pbc(
148    xyz: &[[f64; 3]],
149    cell: &Cell,
150    query: &PbcQuery<'_>,
151) -> Result<Vec<Pair>, Error> {
152    if !query.cutoff.is_finite() || query.cutoff <= 0.0 {
153        return Err(Error::BadCutoff);
154    }
155    if xyz.is_empty() {
156        return Err(Error::Empty);
157    }
158    if let Some(mask) = query.mask {
159        if mask.len() != xyz.len() {
160            return Err(Error::MaskLen);
161        }
162    }
163    for point in xyz {
164        if !point[0].is_finite() || !point[1].is_finite() || !point[2].is_finite() {
165            return Err(Error::NonFinite);
166        }
167    }
168    if query.periodic == [true, true, true] {
169        let mut rows = crate::pairs::pairs_within(
170            xyz,
171            cell,
172            query.cutoff,
173            query.mask,
174            query.cell_hint,
175            query.half,
176        )?;
177        if query.exclude_self_images {
178            rows.retain(|pair| pair.i != pair.j);
179        }
180        return Ok(rows);
181    }
182    let frame = place(xyz, cell, query)?;
183    if frame.n_active == 0 {
184        return Ok(Vec::new());
185    }
186    let stencil = stencil_for(&frame, cell, query)?;
187    walk(&frame, cell, &stencil, query)
188}
189
190/// Lattice for `periodic`. A zero row on an open axis is replaced by a
191/// unit axis so the periodic rows still define a cell. A fully open
192/// mask does not read `rows`.
193pub fn cell_for_pbc(
194    mut rows: [[f64; 3]; 3],
195    origin: [f64; 3],
196    periodic: [bool; 3],
197) -> Result<Cell, Error> {
198    if periodic == [false, false, false] {
199        return Cell::ortho(1.0, 1.0, 1.0).map_err(|_| Error::BadBox);
200    }
201    for axis in 0..3 {
202        if periodic[axis] {
203            continue;
204        }
205        let len2 = rows[axis][0] * rows[axis][0]
206            + rows[axis][1] * rows[axis][1]
207            + rows[axis][2] * rows[axis][2];
208        if !len2.is_finite() || len2 <= 1.0e-24 {
209            rows[axis] = [0.0, 0.0, 0.0];
210            rows[axis][axis] = 1.0;
211        }
212    }
213    Cell::from_vectors(rows[0], rows[1], rows[2], origin).map_err(|_| Error::BadBox)
214}
215
216struct Frame {
217    pos: Vec<[f64; 3]>,
218    image: Vec<[i32; 3]>,
219    off: Vec<u32>,
220    occ: Vec<u32>,
221    origin: [i32; 3],
222    dims: [i32; 3],
223    edge: f64,
224    n_active: usize,
225    any_image: bool,
226}
227
228struct Link {
229    dst: u32,
230    shift: [i32; 3],
231}
232
233struct Stencil {
234    key: Key,
235    off: Vec<u32>,
236    links: Vec<Link>,
237    /// The partner rows of a fully open frame. `None` when `links` holds
238    /// the stencil.
239    open: Option<OpenRows>,
240}
241
242/// Partner bins of a fully open frame, one row of `dx` per `(dy, dz)`.
243///
244/// `width[(dz + ext[1]) * (2 * ext[0] + 1) + dy + ext[0]]` is the largest
245/// `|dx|` within reach on that row, or -1 when no bin of the row is. Rows
246/// past `ext` are not stored. A frame that spans more bins on y or z
247/// needs a wider table, unless `ext` already covers `reach` on that axis.
248struct OpenRows {
249    reach: i32,
250    ext: [i32; 2],
251    width: Vec<i32>,
252}
253
254/// Rows stored on y and z before a frame asks for more.
255const OPEN_EXTENT: i32 = 16;
256
257#[derive(Clone, Copy, PartialEq, Eq)]
258struct Key {
259    edge: u64,
260    cut: u64,
261    periodic: [u8; 3],
262    origin: [i32; 3],
263    dims: [i32; 3],
264    repeats: [i32; 3],
265    box_bits: [u64; 12],
266}
267
268fn bin_edge(hint: Option<f64>, cutoff: f64) -> f64 {
269    match hint {
270        Some(edge) if edge.is_finite() && edge > 0.0 => edge,
271        _ => cutoff,
272    }
273}
274
275fn floor_i32(value: f64) -> Result<i32, Error> {
276    if !value.is_finite() {
277        return Err(Error::NonFinite);
278    }
279    let floored = value.floor();
280    if floored < i32::MIN as f64 || floored > i32::MAX as f64 {
281        return Err(Error::Overflow);
282    }
283    Ok(floored as i32)
284}
285
286fn mul_columns(h: [[f64; 3]; 3], v: [f64; 3]) -> [f64; 3] {
287    [
288        h[0][0] * v[0] + h[1][0] * v[1] + h[2][0] * v[2],
289        h[0][1] * v[0] + h[1][1] * v[1] + h[2][1] * v[2],
290        h[0][2] * v[0] + h[1][2] * v[1] + h[2][2] * v[2],
291    ]
292}
293
294fn unwrapped_frac(cell: &Cell, point: [f64; 3]) -> [f64; 3] {
295    let origin = cell.origin();
296    if cell.is_ortho() {
297        let widths = cell.widths();
298        return [
299            (point[0] - origin[0]) / widths[0],
300            (point[1] - origin[1]) / widths[1],
301            (point[2] - origin[2]) / widths[2],
302        ];
303    }
304    let delta = [
305        point[0] - origin[0],
306        point[1] - origin[1],
307        point[2] - origin[2],
308    ];
309    mul_columns(cell.hinv(), delta)
310}
311
312fn repeats_of(cell: &Cell, periodic: [bool; 3], cutoff: f64) -> Result<[i32; 3], Error> {
313    let widths = cell.widths();
314    let mut repeats = [0i32; 3];
315    let mut images = 1i64;
316    for axis in 0..3 {
317        if !periodic[axis] {
318            continue;
319        }
320        if !widths[axis].is_finite() || widths[axis] <= 0.0 {
321            return Err(Error::BadBox);
322        }
323        let count = (cutoff / widths[axis]).ceil();
324        if !count.is_finite() || count > i32::MAX as f64 {
325            return Err(Error::TooManyImages);
326        }
327        repeats[axis] = count as i32;
328        let factor = 2 * i64::from(repeats[axis]) + 1;
329        if images > MAX_IMAGES / factor {
330            return Err(Error::TooManyImages);
331        }
332        images *= factor;
333    }
334    Ok(repeats)
335}
336
337fn place(xyz: &[[f64; 3]], cell: &Cell, query: &PbcQuery<'_>) -> Result<Frame, Error> {
338    let edge = bin_edge(query.cell_hint, query.cutoff);
339    let periodic = query.periodic;
340    let open = periodic == [false, false, false];
341    let n = xyz.len();
342    let mut pos = vec![[0.0; 3]; n];
343    let mut image = vec![[0i32; 3]; n];
344    let mut bins = vec![[0i32; 3]; n];
345    let mut active = Vec::with_capacity(n);
346    let mut any_image = false;
347    let mut lo = [i32::MAX; 3];
348    let mut hi = [i32::MIN; 3];
349    for (index, point) in xyz.iter().enumerate() {
350        if query.mask.is_some_and(|mask| !mask[index]) {
351            continue;
352        }
353        let located = if open {
354            *point
355        } else {
356            let frac = unwrapped_frac(cell, *point);
357            let mut folded = frac;
358            for axis in 0..3 {
359                if !periodic[axis] {
360                    continue;
361                }
362                let whole = floor_i32(frac[axis])?;
363                image[index][axis] = whole;
364                if whole != 0 {
365                    any_image = true;
366                }
367                folded[axis] = frac[axis] - f64::from(whole);
368            }
369            cell.cartesian(folded)
370        };
371        if !located[0].is_finite() || !located[1].is_finite() || !located[2].is_finite() {
372            return Err(Error::NonFinite);
373        }
374        pos[index] = *point;
375        for axis in 0..3 {
376            let bin = floor_i32(located[axis] / edge)?;
377            bins[index][axis] = bin;
378            lo[axis] = lo[axis].min(bin);
379            hi[axis] = hi[axis].max(bin);
380        }
381        active.push(index);
382    }
383    if active.is_empty() {
384        return Ok(Frame {
385            pos,
386            image,
387            off: vec![0],
388            occ: Vec::new(),
389            origin: [0; 3],
390            dims: [1, 1, 1],
391            edge,
392            n_active: 0,
393            any_image: false,
394        });
395    }
396    let mut dims = [0i32; 3];
397    let mut ncell: i64 = 1;
398    for axis in 0..3 {
399        let span = i64::from(hi[axis]) - i64::from(lo[axis]) + 1;
400        if span <= 0 || span > i32::MAX as i64 {
401            return Err(Error::TooManyCells);
402        }
403        dims[axis] = span as i32;
404        ncell = ncell.saturating_mul(span);
405        if ncell > MAX_CELLS {
406            return Err(Error::TooManyCells);
407        }
408    }
409    let ncell = ncell as usize;
410    let mut count = vec![0u32; ncell];
411    let mut which = vec![0u32; active.len()];
412    for (slot, &index) in active.iter().enumerate() {
413        let local = [
414            bins[index][0] - lo[0],
415            bins[index][1] - lo[1],
416            bins[index][2] - lo[2],
417        ];
418        let flat = ((local[2] as usize * dims[1] as usize) + local[1] as usize) * dims[0] as usize
419            + local[0] as usize;
420        which[slot] = flat as u32;
421        count[flat] += 1;
422    }
423    let mut off = vec![0u32; ncell + 1];
424    for cell_index in 0..ncell {
425        off[cell_index + 1] = off[cell_index] + count[cell_index];
426    }
427    let mut cursor = off.clone();
428    let mut occ = vec![0u32; active.len()];
429    for (slot, &index) in active.iter().enumerate() {
430        let at = cursor[which[slot] as usize];
431        occ[at as usize] = index as u32;
432        cursor[which[slot] as usize] = at + 1;
433    }
434    Ok(Frame {
435        pos,
436        image,
437        off,
438        occ,
439        origin: lo,
440        dims,
441        edge,
442        n_active: active.len(),
443        any_image,
444    })
445}
446
447fn box_bits(cell: &Cell, periodic: [bool; 3]) -> [u64; 12] {
448    if periodic == [false, false, false] {
449        return [0; 12];
450    }
451    let h = cell.h();
452    let origin = cell.origin();
453    let mut bits = [0u64; 12];
454    for axis in 0..3 {
455        if !periodic[axis] {
456            continue;
457        }
458        for component in 0..3 {
459            bits[3 * axis + component] = h[axis][component].to_bits();
460        }
461        bits[9 + axis] = origin[axis].to_bits();
462    }
463    bits
464}
465
466fn axis_gap(a0: f64, a1: f64, b0: f64, b1: f64) -> f64 {
467    if a1 <= b0 {
468        b0 - a1
469    } else if b1 <= a0 {
470        a0 - b1
471    } else {
472        0.0
473    }
474}
475
476fn cells_too_far(
477    src: [i32; 3],
478    dst: [i32; 3],
479    origin: [i32; 3],
480    edge: f64,
481    delta: [f64; 3],
482    cutoff: f64,
483) -> bool {
484    let mut gap2 = 0.0;
485    for axis in 0..3 {
486        let s0 = f64::from(origin[axis] + src[axis]) * edge;
487        let d0 = f64::from(origin[axis] + dst[axis]) * edge + delta[axis];
488        let gap = axis_gap(s0, s0 + edge, d0, d0 + edge);
489        gap2 += gap * gap;
490    }
491    let gap = certify(gap2.sqrt());
492    gap > cutoff
493}
494
495fn local_of(flat: usize, dims: [i32; 3]) -> [i32; 3] {
496    let nx = dims[0] as usize;
497    let ny = dims[1] as usize;
498    let x = (flat % nx) as i32;
499    let y = ((flat / nx) % ny) as i32;
500    let z = (flat / (nx * ny)) as i32;
501    [x, y, z]
502}
503
504fn flat_of(local: [i32; 3], dims: [i32; 3]) -> Option<usize> {
505    if local[0] < 0 || local[1] < 0 || local[2] < 0 {
506        return None;
507    }
508    if local[0] >= dims[0] || local[1] >= dims[1] || local[2] >= dims[2] {
509        return None;
510    }
511    Some(
512        ((local[2] as usize * dims[1] as usize) + local[1] as usize) * dims[0] as usize
513            + local[0] as usize,
514    )
515}
516
517fn build_stencil(
518    frame: &Frame,
519    cell: &Cell,
520    query: &PbcQuery<'_>,
521    key: Key,
522) -> Result<Stencil, Error> {
523    let repeats = key.repeats;
524    let ncell = frame.off.len() - 1;
525    let edge = frame.edge;
526    let reach = stencil_reach(query.cutoff, edge)?;
527    let mut shifts = Vec::new();
528    for sa in -repeats[0]..=repeats[0] {
529        for sb in -repeats[1]..=repeats[1] {
530            for sc in -repeats[2]..=repeats[2] {
531                let shift = [sa, sb, sc];
532                let delta = if shift == [0, 0, 0] {
533                    [0.0; 3]
534                } else {
535                    cell.lattice_shift(sa, sb, sc)
536                };
537                shifts.push((shift, delta));
538            }
539        }
540    }
541    let scan_all = (ncell as u64).saturating_mul(shifts.len() as u64) <= 250_000;
542    let mut off = vec![0u32; ncell + 1];
543    let mut links = Vec::new();
544    for src in 0..ncell {
545        let src_local = local_of(src, frame.dims);
546        for &(shift, delta) in &shifts {
547            if scan_all {
548                for dst in 0..ncell {
549                    let dst_local = local_of(dst, frame.dims);
550                    if cells_too_far(
551                        src_local,
552                        dst_local,
553                        frame.origin,
554                        edge,
555                        delta,
556                        query.cutoff,
557                    ) {
558                        continue;
559                    }
560                    links.push(Link {
561                        dst: dst as u32,
562                        shift,
563                    });
564                }
565            } else {
566                let center = [
567                    src_local[0] - (delta[0] / edge).round() as i32,
568                    src_local[1] - (delta[1] / edge).round() as i32,
569                    src_local[2] - (delta[2] / edge).round() as i32,
570                ];
571                for dz in -reach..=reach {
572                    for dy in -reach..=reach {
573                        for dx in -reach..=reach {
574                            let dst_local = [center[0] + dx, center[1] + dy, center[2] + dz];
575                            let Some(dst) = flat_of(dst_local, frame.dims) else {
576                                continue;
577                            };
578                            if cells_too_far(
579                                src_local,
580                                dst_local,
581                                frame.origin,
582                                edge,
583                                delta,
584                                query.cutoff,
585                            ) {
586                                continue;
587                            }
588                            links.push(Link {
589                                dst: dst as u32,
590                                shift,
591                            });
592                        }
593                    }
594                }
595            }
596        }
597        off[src + 1] = links.len() as u32;
598    }
599    Ok(Stencil {
600        key,
601        off,
602        links,
603        open: None,
604    })
605}
606
607fn stencil_reach(cutoff: f64, edge: f64) -> Result<i32, Error> {
608    let reach = (cutoff / edge).ceil();
609    // `reach as i32 + 2` is the stencil pad. A value past `i32::MAX - 2`
610    // overflows that add in debug and wraps the image window in release.
611    if !reach.is_finite() || reach > (i32::MAX - 2) as f64 {
612        return Err(Error::TooManyImages);
613    }
614    Ok(reach as i32 + 2)
615}
616
617/// Bin offsets a fully open frame can pair across. The gap between two
618/// bins depends on their offset and not on where they sit, so one table
619/// serves every frame with this bin edge and cutoff that spans at most
620/// `need[0] + 1` bins on y and `need[1] + 1` on z.
621fn build_open_stencil(edge: f64, cutoff: f64, key: Key, need: [i32; 2]) -> Result<Stencil, Error> {
622    let reach = stencil_reach(cutoff, edge)?;
623    let ext = [
624        need[0].max(OPEN_EXTENT).min(reach),
625        need[1].max(OPEN_EXTENT).min(reach),
626    ];
627    let mut width = Vec::with_capacity((2 * ext[0] + 1) as usize * (2 * ext[1] + 1) as usize);
628    for dz in -ext[1]..=ext[1] {
629        for dy in -ext[0]..=ext[0] {
630            width.push(row_width(dy, dz, reach, edge, cutoff));
631        }
632    }
633    Ok(Stencil {
634        key,
635        off: Vec::new(),
636        links: Vec::new(),
637        open: Some(OpenRows { reach, ext, width }),
638    })
639}
640
641/// Largest `|dx|` up to `reach` whose bin is within reach of the origin
642/// bin on row `(dy, dz)`, or -1. The true gap grows with `|dx|`, so once
643/// the certified gap passes the cutoff no farther bin on the row holds a
644/// pair.
645fn row_width(dy: i32, dz: i32, reach: i32, edge: f64, cutoff: f64) -> i32 {
646    let near = |dx: i32| !cells_too_far([0; 3], [dx, dy, dz], [0; 3], edge, [0.0; 3], cutoff);
647    if !near(0) {
648        return -1;
649    }
650    let (mut lo, mut hi) = (0, reach);
651    while lo < hi {
652        let mid = lo + (hi - lo + 1) / 2;
653        if near(mid) {
654            lo = mid;
655        } else {
656            hi = mid - 1;
657        }
658    }
659    lo
660}
661
662impl Stencil {
663    fn covers(&self, frame: &Frame) -> bool {
664        let Some(open) = &self.open else {
665            return true;
666        };
667        (0..2)
668            .all(|axis| frame.dims[axis + 1] - 1 <= open.ext[axis] || open.ext[axis] == open.reach)
669    }
670}
671
672fn stencil_for(frame: &Frame, cell: &Cell, query: &PbcQuery<'_>) -> Result<Arc<Stencil>, Error> {
673    let open = query.periodic == [false, false, false];
674    let repeats = if open {
675        [0; 3]
676    } else {
677        repeats_of(cell, query.periodic, query.cutoff)?
678    };
679    let key = Key {
680        edge: frame.edge.to_bits(),
681        cut: query.cutoff.to_bits(),
682        periodic: [
683            u8::from(query.periodic[0]),
684            u8::from(query.periodic[1]),
685            u8::from(query.periodic[2]),
686        ],
687        origin: if open { [0; 3] } else { frame.origin },
688        dims: if open { [0; 3] } else { frame.dims },
689        repeats,
690        box_bits: box_bits(cell, query.periodic),
691    };
692    let mut need = [frame.dims[1] - 1, frame.dims[2] - 1];
693    {
694        let guard = CACHE.lock().unwrap_or_else(|err| err.into_inner());
695        if let Some(stencil) = guard.as_ref() {
696            if stencil.key == key {
697                if stencil.covers(frame) {
698                    return Ok(Arc::clone(stencil));
699                }
700                if let Some(open) = &stencil.open {
701                    for (want, &ext) in need.iter_mut().zip(open.ext.iter()) {
702                        *want = if *want > ext {
703                            (*want).max(ext.saturating_mul(2))
704                        } else {
705                            ext
706                        };
707                    }
708                }
709            }
710        }
711    }
712    let built = Arc::new(if open {
713        build_open_stencil(frame.edge, query.cutoff, key, need)?
714    } else {
715        build_stencil(frame, cell, query, key)?
716    });
717    note_stencil_build();
718    let mut guard = CACHE.lock().unwrap_or_else(|err| err.into_inner());
719    *guard = Some(Arc::clone(&built));
720    Ok(built)
721}
722
723fn reported_shift(frame: &Frame, i: usize, j: usize, shift: [i32; 3]) -> Result<[i32; 3], Error> {
724    if !frame.any_image {
725        return Ok(shift);
726    }
727    let mut out = [0i32; 3];
728    for axis in 0..3 {
729        let value = i64::from(shift[axis]) + i64::from(frame.image[i][axis])
730            - i64::from(frame.image[j][axis]);
731        if value < i64::from(i32::MIN) || value > i64::from(i32::MAX) {
732            return Err(Error::Overflow);
733        }
734        out[axis] = value as i32;
735    }
736    Ok(out)
737}
738
739fn neg_shift(shift: [i32; 3]) -> Option<[i32; 3]> {
740    Some([
741        shift[0].checked_neg()?,
742        shift[1].checked_neg()?,
743        shift[2].checked_neg()?,
744    ])
745}
746
747fn accept(dist2: f64, cut2: f64, closed: bool) -> bool {
748    if closed {
749        dist2 <= cut2
750    } else {
751        dist2 < cut2
752    }
753}
754
755fn walk(
756    frame: &Frame,
757    cell: &Cell,
758    stencil: &Stencil,
759    query: &PbcQuery<'_>,
760) -> Result<Vec<Pair>, Error> {
761    let cut2 = query.cutoff * query.cutoff;
762    let mut rows = Vec::new();
763    if let Some(open) = &stencil.open {
764        walk_open(frame, open, query, cut2, &mut rows);
765        return Ok(rows);
766    }
767    let ncell = frame.off.len() - 1;
768    for src in 0..ncell {
769        let src_atoms = &frame.occ[frame.off[src] as usize..frame.off[src + 1] as usize];
770        if src_atoms.is_empty() {
771            continue;
772        }
773        for link in &stencil.links[stencil.off[src] as usize..stencil.off[src + 1] as usize] {
774            pair_bins(
775                frame,
776                cell,
777                query,
778                cut2,
779                src_atoms,
780                link.dst as usize,
781                link.shift,
782                &mut rows,
783            )?;
784        }
785    }
786    Ok(rows)
787}
788
789/// Each source bin visits its partner rows clipped to the frame, in
790/// ascending flat order, which is the order of a per-bin link list.
791fn walk_open(
792    frame: &Frame,
793    open: &OpenRows,
794    query: &PbcQuery<'_>,
795    cut2: f64,
796    rows: &mut Vec<Pair>,
797) {
798    let dims = frame.dims;
799    let [ey, ez] = open.ext;
800    let stride = (2 * ey + 1) as usize;
801    let mut src = 0usize;
802    for z in 0..dims[2] {
803        let dz_lo = (-z).max(-ez);
804        let dz_hi = (dims[2] - 1 - z).min(ez);
805        for y in 0..dims[1] {
806            let dy_lo = (-y).max(-ey);
807            let dy_hi = (dims[1] - 1 - y).min(ey);
808            for x in 0..dims[0] {
809                let src_atoms = &frame.occ[frame.off[src] as usize..frame.off[src + 1] as usize];
810                src += 1;
811                if src_atoms.is_empty() {
812                    continue;
813                }
814                for dz in dz_lo..=dz_hi {
815                    let plane = (dz + ez) as usize * stride;
816                    let row_z = (z + dz) as usize * dims[1] as usize;
817                    for dy in dy_lo..=dy_hi {
818                        let width = open.width[plane + (dy + ey) as usize];
819                        if width < 0 {
820                            continue;
821                        }
822                        let row = (row_z + (y + dy) as usize) * dims[0] as usize;
823                        let first = row + (x - width.min(x)) as usize;
824                        let last = row + (x + width.min(dims[0] - 1 - x)) as usize;
825                        for dst in first..=last {
826                            let dst_atoms =
827                                &frame.occ[frame.off[dst] as usize..frame.off[dst + 1] as usize];
828                            pair_open_bins(frame, query, cut2, src_atoms, dst_atoms, rows);
829                        }
830                    }
831                }
832            }
833        }
834    }
835}
836
837/// [`pair_bins`] with no shift and no images. A bin lists its atoms in
838/// ascending index, so the partners `j > i` are a suffix of `dst_atoms`.
839#[inline(always)]
840fn pair_open_bins(
841    frame: &Frame,
842    query: &PbcQuery<'_>,
843    cut2: f64,
844    src_atoms: &[u32],
845    dst_atoms: &[u32],
846    rows: &mut Vec<Pair>,
847) {
848    for &ia in src_atoms {
849        let i = ia as usize;
850        let start = match (dst_atoms.first(), dst_atoms.last()) {
851            (Some(&first), _) if first > ia => 0,
852            (_, Some(&last)) if last > ia => dst_atoms.partition_point(|&ja| ja <= ia),
853            _ => continue,
854        };
855        let pi = frame.pos[i];
856        for &ja in &dst_atoms[start..] {
857            let j = ja as usize;
858            let pj = frame.pos[j];
859            // The zero shift [`pair_bins`] adds can only flip the sign of
860            // a zero difference, which squares to the same `dist2` bits.
861            let dx = pj[0] - pi[0];
862            let dy = pj[1] - pi[1];
863            let dz = pj[2] - pi[2];
864            let dist2 = dx * dx + dy * dy + dz * dz;
865            if !accept(dist2, cut2, query.closed) {
866                continue;
867            }
868            rows.push(Pair {
869                i,
870                j,
871                shift: [0; 3],
872                dist2,
873            });
874            if !query.half {
875                rows.push(Pair {
876                    i: j,
877                    j: i,
878                    shift: [0; 3],
879                    dist2,
880                });
881            }
882        }
883    }
884}
885
886#[allow(clippy::too_many_arguments)]
887#[inline(always)]
888fn pair_bins(
889    frame: &Frame,
890    cell: &Cell,
891    query: &PbcQuery<'_>,
892    cut2: f64,
893    src_atoms: &[u32],
894    dst: usize,
895    shift: [i32; 3],
896    rows: &mut Vec<Pair>,
897) -> Result<(), Error> {
898    let dst_atoms = &frame.occ[frame.off[dst] as usize..frame.off[dst + 1] as usize];
899    if dst_atoms.is_empty() {
900        return Ok(());
901    }
902    for &ia in src_atoms {
903        let i = ia as usize;
904        let pi = frame.pos[i];
905        for &ja in dst_atoms {
906            let j = ja as usize;
907            if i == j && shift == [0, 0, 0] {
908                continue;
909            }
910            let reported = reported_shift(frame, i, j, shift)?;
911            if i > j {
912                continue;
913            }
914            if i == j && !keep_half(i, j, reported) {
915                continue;
916            }
917            if query.exclude_self_images && i == j {
918                continue;
919            }
920            let pj = frame.pos[j];
921            let delta = if reported == [0, 0, 0] {
922                [0.0; 3]
923            } else {
924                cell.lattice_shift(reported[0], reported[1], reported[2])
925            };
926            let dx = pj[0] + delta[0] - pi[0];
927            let dy = pj[1] + delta[1] - pi[1];
928            let dz = pj[2] + delta[2] - pi[2];
929            let dist2 = dx * dx + dy * dy + dz * dz;
930            if !accept(dist2, cut2, query.closed) {
931                continue;
932            }
933            rows.push(Pair {
934                i,
935                j,
936                shift: reported,
937                dist2,
938            });
939            if !query.half {
940                let flipped = neg_shift(reported).ok_or(Error::Overflow)?;
941                if i == j {
942                    rows.push(Pair {
943                        i,
944                        j,
945                        shift: flipped,
946                        dist2,
947                    });
948                } else {
949                    rows.push(Pair {
950                        i: j,
951                        j: i,
952                        shift: flipped,
953                        dist2,
954                    });
955                }
956            }
957        }
958    }
959    Ok(())
960}