use rayon::prelude::*;
use rustc_hash::{FxHashMap as HashMap, FxHashSet as HashSet};
pub type ExpandTrajectoryBatchResult = (Vec<usize>, Vec<i64>, Vec<usize>);
const FIVE_MIN_MS: i64 = 5 * 60 * 1000;
const NULL_TIMESTAMP_SENTINEL_MS: i64 = i64::MIN;
fn ceil_5min_ms(t: i64) -> i64 {
let rem = t.rem_euclid(FIVE_MIN_MS);
if rem == 0 { t } else { t + (FIVE_MIN_MS - rem) }
}
fn floor_5min_ms(t: i64) -> i64 {
t - t.rem_euclid(FIVE_MIN_MS)
}
struct ExpandedRow {
timestamp_ms: i64,
source_row_idx: usize,
}
fn expand_5min_for_user(
start_ms: &[i64],
end_ms: &[i64],
user_indices: &[usize],
) -> Vec<ExpandedRow> {
let mut rows: Vec<ExpandedRow> = Vec::new();
let mut seen: HashSet<i64> = HashSet::default();
for &idx in user_indices {
let start = start_ms[idx];
let end = end_ms[idx];
if start == NULL_TIMESTAMP_SENTINEL_MS || end == NULL_TIMESTAMP_SENTINEL_MS {
continue;
}
let mut t = ceil_5min_ms(start);
let last = floor_5min_ms(end);
while t <= last {
if seen.insert(t) {
rows.push(ExpandedRow {
timestamp_ms: t,
source_row_idx: idx,
});
}
t += FIVE_MIN_MS;
}
}
rows
}
pub fn expand_5min_trajectory_batch_indexed_impl(
start_ms: &[i64],
end_ms: &[i64],
sorted_indices: &[usize],
ends: &[usize],
) -> ExpandTrajectoryBatchResult {
let per_user_rows: Vec<Vec<ExpandedRow>> = (0..ends.len())
.into_par_iter()
.map(|i| {
let start = if i == 0 { 0 } else { ends[i - 1] };
let end = ends[i];
expand_5min_for_user(start_ms, end_ms, &sorted_indices[start..end])
})
.collect();
let n: usize = per_user_rows.iter().map(|rows| rows.len()).sum();
let mut user_range_idx = Vec::with_capacity(n);
let mut timestamps_ms = Vec::with_capacity(n);
let mut source_row_idx = Vec::with_capacity(n);
for (range_idx, rows) in per_user_rows.into_iter().enumerate() {
for row in rows {
user_range_idx.push(range_idx);
timestamps_ms.push(row.timestamp_ms);
source_row_idx.push(row.source_row_idx);
}
}
(user_range_idx, timestamps_ms, source_row_idx)
}
pub type ExpandTrajectoryWithImputationBatchResult = (Vec<usize>, Vec<i64>, Vec<u32>, Vec<u32>);
const HOUR_MS: i64 = 60 * 60 * 1000;
fn hour_of_day(timestamp_ms: i64) -> u32 {
timestamp_ms.div_euclid(HOUR_MS).rem_euclid(24) as u32
}
#[derive(Clone, Copy, PartialEq, Eq, Hash)]
enum AnchorWindow {
Home,
WorkA,
WorkB,
}
fn anchor_window_for_hour(hour: u32) -> Option<AnchorWindow> {
match hour {
2..=5 => Some(AnchorWindow::Home),
10 => Some(AnchorWindow::WorkA),
14..=16 => Some(AnchorWindow::WorkB),
_ => None,
}
}
#[derive(Default)]
struct AnchorTally {
counts: HashMap<u32, (u64, usize)>,
next_position: usize,
}
impl AnchorTally {
fn record(&mut self, location_code: u32) {
let next_position = self.next_position;
let entry = self
.counts
.entry(location_code)
.or_insert((0, next_position));
entry.0 += 1;
self.next_position += 1;
}
fn winner(&self) -> Option<u32> {
self.counts
.iter()
.max_by(|(_, (count_a, pos_a)), (_, (count_b, pos_b))| {
count_a.cmp(count_b).then(pos_b.cmp(pos_a))
})
.map(|(&location_code, _)| location_code)
}
}
fn expand_5min_with_imputation_for_user(
start_ms: &[i64],
end_ms: &[i64],
location_codes: &[u32],
user_indices: &[usize],
) -> Vec<(i64, u32, u32)> {
let observed_rows = expand_5min_for_user(start_ms, end_ms, user_indices);
if observed_rows.is_empty() {
return Vec::new();
}
let mut observed: Vec<(i64, u32)> = observed_rows
.into_iter()
.map(|row| (row.timestamp_ms, location_codes[row.source_row_idx]))
.collect();
observed.sort_unstable_by_key(|&(timestamp_ms, _)| timestamp_ms);
let mut tallies: HashMap<AnchorWindow, AnchorTally> = HashMap::default();
for &(timestamp_ms, location_code) in &observed {
if let Some(window) = anchor_window_for_hour(hour_of_day(timestamp_ms)) {
tallies.entry(window).or_default().record(location_code);
}
}
let anchor_for = |window: AnchorWindow| -> Option<u32> {
tallies.get(&window).and_then(AnchorTally::winner)
};
let home_anchor = anchor_for(AnchorWindow::Home);
let work_a_anchor = anchor_for(AnchorWindow::WorkA);
let work_b_anchor = anchor_for(AnchorWindow::WorkB);
let observed_by_timestamp: HashMap<i64, u32> = observed.iter().copied().collect();
let first_timestamp = observed.first().unwrap().0;
let last_timestamp = observed.last().unwrap().0;
let mut seen: HashSet<u32> = HashSet::default();
let mut result: Vec<(i64, u32, u32)> = Vec::new();
let mut current_run: Option<(i64, u32, u32, bool)> = None;
let mut t = first_timestamp;
while t <= last_timestamp {
let location = observed_by_timestamp.get(&t).copied().or_else(|| {
match anchor_window_for_hour(hour_of_day(t)) {
Some(AnchorWindow::Home) => home_anchor,
Some(AnchorWindow::WorkA) => work_a_anchor,
Some(AnchorWindow::WorkB) => work_b_anchor,
None => None,
}
});
if let Some(location) = location {
let is_known = !seen.insert(location); match &mut current_run {
Some((_, run_location, run_length, run_is_known))
if *run_location == location && *run_is_known == is_known =>
{
*run_length += 1;
}
_ => {
if let Some(run) = current_run.take() {
result.push((run.0, run.1, run.2));
}
current_run = Some((t, location, 1, is_known));
}
}
}
t += FIVE_MIN_MS;
}
if let Some(run) = current_run.take() {
result.push((run.0, run.1, run.2));
}
result
}
pub fn expand_5min_trajectory_with_imputation_batch_indexed_impl(
start_ms: &[i64],
end_ms: &[i64],
location_codes: &[u32],
sorted_indices: &[usize],
ends: &[usize],
) -> ExpandTrajectoryWithImputationBatchResult {
let per_user_runs: Vec<Vec<(i64, u32, u32)>> = (0..ends.len())
.into_par_iter()
.map(|i| {
let start = if i == 0 { 0 } else { ends[i - 1] };
let end = ends[i];
expand_5min_with_imputation_for_user(
start_ms,
end_ms,
location_codes,
&sorted_indices[start..end],
)
})
.collect();
let n: usize = per_user_runs.iter().map(|runs| runs.len()).sum();
let mut user_range_idx = Vec::with_capacity(n);
let mut timestamps_ms = Vec::with_capacity(n);
let mut location_out = Vec::with_capacity(n);
let mut run_length_out = Vec::with_capacity(n);
for (range_idx, runs) in per_user_runs.into_iter().enumerate() {
for (run_start_ms, location_code, run_length) in runs {
user_range_idx.push(range_idx);
timestamps_ms.push(run_start_ms);
location_out.push(location_code);
run_length_out.push(run_length);
}
}
(user_range_idx, timestamps_ms, location_out, run_length_out)
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn aligned_stay_yields_inclusive_5min_slices() {
let base = 1_600_000_000_000i64; let base = base - base.rem_euclid(FIVE_MIN_MS);
let start = vec![base];
let end = vec![base + 10 * 60 * 1000];
let sorted_indices = vec![0usize];
let ends = vec![1usize];
let (user_idx, ts, src) =
expand_5min_trajectory_batch_indexed_impl(&start, &end, &sorted_indices, &ends);
assert_eq!(user_idx, vec![0, 0, 0]);
assert_eq!(ts, vec![base, base + 5 * 60 * 1000, base + 10 * 60 * 1000]);
assert_eq!(src, vec![0, 0, 0]);
}
#[test]
fn non_aligned_stay_yields_inner_slices_only() {
let base = 1_600_000_000_000i64;
let base = base - base.rem_euclid(FIVE_MIN_MS);
let start = vec![base + 2 * 60 * 1000]; let end = vec![base + 13 * 60 * 1000]; let sorted_indices = vec![0usize];
let ends = vec![1usize];
let (_user_idx, ts, _src) =
expand_5min_trajectory_batch_indexed_impl(&start, &end, &sorted_indices, &ends);
assert_eq!(ts, vec![base + 5 * 60 * 1000, base + 10 * 60 * 1000]);
}
#[test]
fn duplicate_timestamp_across_rows_keeps_first_occurrence() {
let base = 1_600_000_000_000i64;
let base = base - base.rem_euclid(FIVE_MIN_MS);
let start = vec![base, base];
let end = vec![base, base];
let sorted_indices = vec![0usize, 1usize];
let ends = vec![2usize];
let (_user_idx, ts, src) =
expand_5min_trajectory_batch_indexed_impl(&start, &end, &sorted_indices, &ends);
assert_eq!(ts, vec![base]);
assert_eq!(src, vec![0]);
}
#[test]
fn null_sentinel_rows_are_skipped() {
let start = vec![NULL_TIMESTAMP_SENTINEL_MS, 0];
let end = vec![NULL_TIMESTAMP_SENTINEL_MS, 0];
let sorted_indices = vec![0usize, 1usize];
let ends = vec![2usize];
let (_user_idx, ts, src) =
expand_5min_trajectory_batch_indexed_impl(&start, &end, &sorted_indices, &ends);
assert_eq!(ts, vec![0]);
assert_eq!(src, vec![1]);
}
const HOME: u32 = 0;
const SHOP: u32 = 1;
fn ms(hour: i64, minute: i64) -> i64 {
hour * HOUR_MS + minute * 60_000
}
#[test]
fn imputation_fills_nighttime_gap_with_home_anchor() {
let start = vec![ms(2, 0), ms(2, 15)];
let end = vec![ms(2, 5), ms(2, 15)];
let location_codes = vec![HOME, SHOP];
let sorted_indices = vec![0usize, 1usize];
let ends = vec![2usize];
let (_user_idx, ts, loc, run_len) =
expand_5min_trajectory_with_imputation_batch_indexed_impl(
&start,
&end,
&location_codes,
&sorted_indices,
&ends,
);
assert_eq!(ts, vec![ms(2, 0), ms(2, 5), ms(2, 15)]);
assert_eq!(loc, vec![HOME, HOME, SHOP]);
assert_eq!(run_len, vec![1, 2, 1]);
}
#[test]
fn imputation_leaves_gap_absent_outside_anchor_windows() {
let start = vec![ms(8, 0), ms(8, 15)];
let end = vec![ms(8, 5), ms(8, 15)];
let location_codes = vec![HOME, SHOP];
let sorted_indices = vec![0usize, 1usize];
let ends = vec![2usize];
let (_user_idx, ts, loc, run_len) =
expand_5min_trajectory_with_imputation_batch_indexed_impl(
&start,
&end,
&location_codes,
&sorted_indices,
&ends,
);
assert_eq!(ts, vec![ms(8, 0), ms(8, 5), ms(8, 15)]);
assert_eq!(loc, vec![HOME, HOME, SHOP]);
assert_eq!(run_len, vec![1, 1, 1]);
}
#[test]
fn long_run_across_a_gap_compresses_to_a_single_return_record() {
let three_days_ms = 3 * 24 * HOUR_MS;
let start = vec![ms(2, 0), three_days_ms + ms(2, 0)];
let end = vec![ms(2, 0), three_days_ms + ms(2, 0)];
let location_codes = vec![HOME, HOME];
let sorted_indices = vec![0usize, 1usize];
let ends = vec![2usize];
let (_user_idx, ts, loc, run_len) =
expand_5min_trajectory_with_imputation_batch_indexed_impl(
&start,
&end,
&location_codes,
&sorted_indices,
&ends,
);
assert_eq!(ts, vec![ms(2, 0), ms(2, 5)]);
assert_eq!(loc, vec![HOME, HOME]);
assert_eq!(run_len[0], 1, "first slice is home's first-ever occurrence");
assert!(
run_len[1] > 100,
"expected a long compressed return run, got {}",
run_len[1]
);
}
}