1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
//! Periodic linked-cell k-nearest neighbour search.
//!
//! vesin builds cutoff pair lists. nanoflann builds Euclidean KD-trees
//! without a minimum-image convention. This crate is the missing piece:
//! Allen and Tildesley's linked cells, a k-heap per source, and an
//! index box that grows one axis at a time until the k-th neighbour
//! cannot lie past an unvisited face. The pair itself is Rapaport's
//! cell shift, not a per-pair nearest integer. [`pairs_within`] is the
//! cutoff pair list with integer cell shifts (vesin/tonari `ijS`);
//! [`knearest`] unique-indexes.
//!
//! # Algorithm
//!
//! 1. **Fold** every position into the primary cell
//! ([`Cell::fractional`], then [`Cell::cartesian`]).
//! 2. **Bin** the folded points on a fractional mesh. The bin count
//! along each axis uses the perpendicular face width, so a sheared
//! dump is not treated as orthogonal.
//! 3. **Grow an index box** of linked cells. The first visit is the
//! 3×3×3 around the home bin. After that, only an axis whose
//! unvisited plane is still inside the k-th neighbour grows.
//! Occupants are stored in cell order. A neighbour cell whose slab
//! cannot beat the worst heap entry is skipped. The cap is the
//! space diagonal over the minimum cell height, so a shift outside
//! `{-1,0,1}` is still visited when it is the Euclidean image.
//!
//! The walk basis depends on the cell. An orthorhombic box, including
//! a rectangular film, is used as stored. A restricted triclinic box
//! (LAMMPS dump bounds, a CON angle, a hexagonal prism) is
//! tilt-reduced in place and the shift is triangular. A general
//! orientation is Minkowski-reduced. [`pairs_within`] keeps the
//! caller's basis, because the reported shift is an integer
//! combination of that H.
//!
//! Pair distances in the walk are not a per-pair minimum-image wrap.
//! After the fold, a neighbour stencil `(jx, jy, jz)` contributes
//! [`Cell::lattice_shift`] and [`Cell::dist2_shifted`]: a Cartesian
//! subtract plus one lattice vector (the vesin / LAMMPS ghost trick).
//! Orthorhombic boxes set the [`Cell::is_ortho`] flag and skip the two
//! 3x3 matvecs: three independent wraps, and the shift is a scaled
//! diagonal. The Highway batch ([`dist2_ortho_diffs`]) is that wrap
//! for a raw difference. [`knearest_brute`] uses it on an orthorhombic
//! box. [`pairs_within`] keeps the stencil image and does not wrap
//! the shifted difference again.
//!
//! # Why a unique-cell stamp is wrong
//!
//! A stamp that visits each linked cell once, with a **single** shift
//! for every occupant, is not a minimum-image convention. Occupants of
//! one cell can need **different** images of the same source (a wide
//! bin, or a source near a face). The walk keys on the integer stencil
//! `(jx, jy, jz)`, including wraps: the same `rem_euclid` bin may
//! appear with more than one [`Cell::lattice_shift`].
//!
//! # Output
//!
//! [`knearest`] returns one [`Neighbors`] row per input point, nearest
//! first. [`knearest_into`] writes a packed `n * k` index buffer
//! (`-1` in unused slots), the same layout as `lc_knearest`.
//!
//! # Features
//!
//! `parallel` (rayon over sources) is on by default for wall-clock.
//! `--no-default-features` drops rayon and serializes the walk (re-enable
//! `capi` if the C ABI is still required). The per-source k-heap
//! (`KHeap`) stays on the stack for `k <= 16`; larger `k` spills to the
//! heap.
//!
//! # Examples
//!
//! Periodic image, not the raw Cartesian vector:
//!
//! ```
//! use linkcell::{knearest, Cell};
//!
//! # fn main() -> Result<(), linkcell::Error> {
//! let sim = Cell::ortho(10.0, 10.0, 10.0)?;
//! let xyz = [[0.2, 0.0, 0.0], [9.4, 0.0, 0.0]];
//! let rows = knearest(&xyz, &sim, 1, None, None)?;
//! assert_eq!(rows[0].indices, vec![1]);
//! assert!((rows[0].dist2[0] - 0.64).abs() < 1e-12);
//! # Ok(())
//! # }
//! ```
//!
//! Two occupants of one linked cell (the whole box is a single bin)
//! need different images of the source. A unique-cell stamp with one
//! shift cannot serve both.
//!
//! ```
//! use linkcell::{knearest, Cell};
//!
//! # fn main() -> Result<(), linkcell::Error> {
//! let sim = Cell::ortho(10.0, 10.0, 10.0)?;
//! let xyz = [[0.1, 0.0, 0.0], [1.0, 0.0, 0.0], [9.8, 0.0, 0.0]];
//! let rows = knearest(&xyz, &sim, 2, None, Some(10.0))?;
//! assert_eq!(rows[0].indices, vec![2, 1]);
//! assert!((rows[0].dist2[0] - 0.09).abs() < 1e-12);
//! assert!((rows[0].dist2[1] - 0.81).abs() < 1e-12);
//! # Ok(())
//! # }
//! ```
//!
//! Packed `n * k` indices, unused slots `-1`:
//!
//! ```
//! use linkcell::{knearest_into, Cell};
//!
//! # fn main() -> Result<(), linkcell::Error> {
//! let sim = Cell::ortho(10.0, 10.0, 10.0)?;
//! let xyz = [[0.0, 0.0, 0.0], [1.0, 0.0, 0.0]];
//! let mut out = [0; 4];
//! knearest_into(&xyz, &sim, 2, None, None, &mut out)?;
//! assert_eq!(out, [1, -1, 0, -1]);
//! # Ok(())
//! # }
//! ```
//!
//! The C ABI (`lc_*`) is the hourglass waist: packed `n * k` indices,
//! matching squared distances, and `lc_pairs_within` for a cutoff
//! list with the caller's shift. C++ lives in `include/linkcell.hpp`
//! as a RAII header over that ABI.
pub use ;
pub use Error;
pub use ;
pub use ;
pub use ;
pub use *;