1use crate::consts::{iangle180, CTXS, TABLE_OVERFLOW_LIMIT, TK, TXS};
13use crate::intra::CompRow;
14
15pub(crate) type ColpRow = [i32; 5];
17
18pub(crate) fn bz_match(probe: &[CompRow], gallery: &[CompRow]) -> Vec<ColpRow> {
25 let probe_len = probe.len();
26 let gallery_len = gallery.len();
27 let mut rot: Vec<ColpRow> = Vec::new();
28 let mut st: usize = 1;
29
30 'k: for k in 1..probe_len {
31 let ss = &probe[k - 1];
32 let mut j = st;
33 while j <= gallery_len {
34 let ff = &gallery[j - 1];
35
36 let dz = (ff[0] - ss[0]) as f32;
38 let fi = (2.0_f32 * TK) * ((ff[0] + ss[0]) as f32);
39 if dz * dz > fi * fi {
40 if dz < 0.0 {
41 st = j + 1;
43 j += 1;
44 continue;
45 }
46 break;
48 }
49
50 let mut incompatible = false;
52 for i in 1..3usize {
53 let d = ss[i] - ff[i];
54 let d2 = i64::from(d) * i64::from(d);
57 if d2 > i64::from(TXS) && d2 < i64::from(CTXS) {
58 incompatible = true;
59 break;
60 }
61 }
62 if incompatible {
63 j += 1;
64 continue;
65 }
66
67 let (mut p1, n) = if ss[5] >= 220 {
69 (ss[5] - 580, 1)
70 } else {
71 (ss[5], 0)
72 };
73 let (p2, b) = if ff[5] >= 220 {
74 (ff[5] - 580, 1)
75 } else {
76 (ff[5], 0)
77 };
78 p1 -= p2;
79 p1 = iangle180(p1);
80
81 let row: ColpRow = if n != b {
83 [p1, ss[3], ss[4], ff[4], ff[3]]
84 } else {
85 [p1, ss[3], ss[4], ff[3], ff[4]]
86 };
87 rot.push(row);
88 if rot.len() == TABLE_OVERFLOW_LIMIT {
89 break 'k;
90 }
91 j += 1;
92 }
93 }
94
95 rot.sort_by(|a, b| (a[1], a[3], a[2]).cmp(&(b[1], b[3], b[2])));
98 rot
99}
100
101#[cfg(test)]
102mod tests {
103 use super::*;
104
105 fn row(distance: i32, betas: (i32, i32), ids: (i32, i32), theta_kj: i32) -> CompRow {
107 [distance, betas.0, betas.1, ids.0, ids.1, theta_kj]
108 }
109
110 fn plain(distance: i32, ids: (i32, i32)) -> CompRow {
112 row(distance, (0, 0), ids, 0)
113 }
114
115 #[test]
116 fn bz_match_empty_and_single_row_webs() {
117 assert!(bz_match(&[], &[]).is_empty());
119 assert!(bz_match(&[], &[plain(100, (1, 2))]).is_empty());
120 assert!(bz_match(&[plain(100, (1, 2))], &[]).is_empty());
121 assert!(bz_match(&[plain(100, (1, 2))], &[plain(100, (3, 4))]).is_empty());
122 }
123
124 #[test]
125 fn bz_match_advances_st_across_probe_rows() {
126 let gallery = [plain(100, (11, 12)), plain(1000, (13, 14))];
130
131 let descending = [plain(1000, (1, 2)), plain(100, (3, 4)), plain(100, (5, 6))];
134 let rows = bz_match(&descending, &gallery);
135 assert_eq!(rows.len(), 1, "only the long/long pair survives");
136 assert_eq!(rows[0][1], 1, "and it is probe row 1");
137 assert!(
138 !rows.iter().any(|r| r[1] == 3),
139 "probe row 3 must find nothing: st has already passed the gallery row it matches"
140 );
141
142 let short_first = [plain(100, (3, 4)), plain(100, (5, 6))];
145 let rows = bz_match(&short_first, &gallery);
146 assert_eq!(rows.len(), 1);
147 assert_eq!(
148 (rows[0][1], rows[0][3]),
149 (3, 11),
150 "probe row 3 pairs with gallery row 11 when st has not passed it"
151 );
152 }
153
154 #[test]
155 fn bz_match_breaks_when_gallery_edge_longer() {
156 let probe = [plain(100, (1, 2)), plain(100, (3, 4))];
159 let gallery = [plain(10_000, (11, 12)), plain(100, (13, 14))];
160 assert!(
161 bz_match(&probe, &gallery).is_empty(),
162 "the break must skip gallery row 13, despite its matching distance"
163 );
164 }
165
166 #[test]
167 fn bz_match_angle_band_boundaries() {
168 for (delta, compatible) in [(11, true), (12, false), (348, false), (349, true)] {
170 let probe = [row(100, (delta, 0), (1, 2), 0), plain(100, (3, 4))];
171 let gallery = [plain(100, (11, 12))];
172 let rows = bz_match(&probe, &gallery);
173 assert_eq!(
174 !rows.is_empty(),
175 compatible,
176 "beta delta {delta} (d*d = {}) should be {}",
177 delta * delta,
178 if compatible { "kept" } else { "rejected" }
179 );
180 }
181 }
182
183 #[test]
184 fn bz_match_decodes_swap_flag_at_220() {
185 let gallery = [plain(100, (11, 12))];
186 let paired = |theta_kj| {
187 let probe = [row(100, (0, 0), (1, 2), theta_kj), plain(100, (3, 4))];
188 bz_match(&probe, &gallery)[0]
189 };
190
191 let unswapped = paired(219);
193 assert_eq!(unswapped[0], iangle180(219), "219 is not a swap flag");
194 assert_eq!((unswapped[3], unswapped[4]), (11, 12));
195
196 let swapped = paired(220);
198 assert_eq!(swapped[0], iangle180(220 - 580), "220 is a swap flag");
199 assert_eq!(
200 (swapped[3], swapped[4]),
201 (12, 11),
202 "one side swapped, so the gallery endpoints flip"
203 );
204 }
205
206 #[test]
207 fn bz_match_keeps_the_gallery_pair_when_both_sides_are_swapped() {
208 let probe = [row(100, (0, 0), (1, 2), 400), plain(100, (3, 4))];
210 let gallery = [row(100, (0, 0), (11, 12), 400)];
211 let rows = bz_match(&probe, &gallery);
212 assert_eq!(rows.len(), 1);
213 assert_eq!((rows[0][3], rows[0][4]), (11, 12));
214 }
215
216 #[test]
217 fn bz_match_sorts_by_probe_k_then_gallery_a_then_probe_j() {
218 let probe = [plain(100, (1, 9)), plain(100, (1, 5)), plain(100, (7, 7))];
221 let gallery = [plain(100, (30, 31)), plain(100, (20, 21))];
222 let rows = bz_match(&probe, &gallery);
223 assert!(rows.len() > 2, "need several rows to observe an order");
224 let keys: Vec<_> = rows.iter().map(|r| (r[1], r[3], r[2])).collect();
225 let mut want = keys.clone();
226 want.sort();
227 assert_eq!(
228 keys, want,
229 "rows must ascend by (probe_k, gallery_a, probe_j)"
230 );
231 }
232
233 #[test]
234 fn bz_match_stops_at_table_overflow_limit() {
235 let probe: Vec<CompRow> = (0..201).map(|i| plain(100, (i, i))).collect();
238 let gallery: Vec<CompRow> = (0..101).map(|i| plain(100, (i, i))).collect();
239 assert_eq!(bz_match(&probe, &gallery).len(), TABLE_OVERFLOW_LIMIT);
240 }
241}