use crate::utils::haversine::haversine_km;
pub(crate) fn is_consistent_pair(
lats: &[f64],
lngs: &[f64],
times: &[f64],
i: usize,
j: usize,
max_speed_kmh: f64,
) -> bool {
let dt = times[j] - times[i];
if dt <= 0.0 {
return false;
}
let dist = haversine_km(lats[i], lngs[i], lats[j], lngs[j]);
dist / dt * 3600.0 <= max_speed_kmh
}
pub fn greedy_keep_mask(
lats: &[f64],
lngs: &[f64],
times: &[f64],
max_speed_kmh: f64,
) -> Vec<bool> {
let n = lats.len();
let mut keep = vec![false; n];
if n == 0 {
return keep;
}
keep[0] = true;
for (i, keep_i) in keep.iter_mut().enumerate().skip(1) {
*keep_i = is_consistent_pair(lats, lngs, times, i - 1, i, max_speed_kmh);
}
keep
}
pub fn smart_greedy_keep_mask(
lats: &[f64],
lngs: &[f64],
times: &[f64],
max_speed_kmh: f64,
) -> Vec<bool> {
let n = lats.len();
let mut keep = vec![false; n];
if n == 0 {
return keep;
}
let mut tails: Vec<usize> = Vec::new();
let mut tail_len: Vec<usize> = Vec::new();
let mut pred: Vec<Option<usize>> = vec![None; n];
for (i, pred_i) in pred.iter_mut().enumerate() {
let mut best_len_here = 1usize;
let mut best_pred: Option<usize> = None;
let mut matched = vec![false; tails.len()];
let mut any_matched = false;
for (k, &t) in tails.iter().enumerate() {
if is_consistent_pair(lats, lngs, times, t, i, max_speed_kmh) {
matched[k] = true;
any_matched = true;
let candidate_len = tail_len[k] + 1;
if candidate_len > best_len_here {
best_len_here = candidate_len;
best_pred = Some(t);
}
}
}
*pred_i = best_pred;
if any_matched {
let mut survivors_tails = Vec::with_capacity(tails.len());
let mut survivors_len = Vec::with_capacity(tail_len.len());
for (k, &t) in tails.iter().enumerate() {
if !matched[k] {
survivors_tails.push(t);
survivors_len.push(tail_len[k]);
}
}
tails = survivors_tails;
tail_len = survivors_len;
}
tails.push(i);
tail_len.push(best_len_here);
}
let best_k = (0..tails.len())
.max_by_key(|&k| tail_len[k])
.expect("n > 0, so at least one chain exists");
let mut cur = tails[best_k];
loop {
keep[cur] = true;
match pred[cur] {
Some(prev) => cur = prev,
None => break,
}
}
keep
}
#[cfg(test)]
mod tests {
use super::*;
fn times_seq(n: usize) -> Vec<f64> {
(0..n).map(|i| i as f64 * 3600.0).collect()
}
#[test]
fn greedy_keeps_first_point_and_rejects_a_single_teleport() {
let lats = vec![0.0, 0.001, 5.0, 0.003, 0.004];
let lngs = vec![0.0; 5];
let times = times_seq(5);
let keep = greedy_keep_mask(&lats, &lngs, ×, 10.0);
assert!(keep[0]);
assert!(
!keep[2],
"teleported point breaks the adjacent-pair speed test"
);
}
#[test]
fn greedy_empty_and_single_point_inputs() {
assert_eq!(greedy_keep_mask(&[], &[], &[], 10.0), Vec::<bool>::new());
assert_eq!(greedy_keep_mask(&[0.0], &[0.0], &[0.0], 10.0), vec![true]);
}
#[test]
fn smart_greedy_picks_the_longest_consistent_chain() {
let lats = vec![0.0, 0.001, 5.0, 0.003, 0.004];
let lngs = vec![0.0; 5];
let times = times_seq(5);
let keep = smart_greedy_keep_mask(&lats, &lngs, ×, 10.0);
assert_eq!(keep, vec![true, true, false, true, true]);
}
#[test]
fn smart_greedy_empty_and_single_point_inputs() {
assert_eq!(
smart_greedy_keep_mask(&[], &[], &[], 10.0),
Vec::<bool>::new()
);
assert_eq!(
smart_greedy_keep_mask(&[0.0], &[0.0], &[0.0], 10.0),
vec![true]
);
}
}