use super::{DeqColumn, Timestamp};
use crate::error::{Error, Result};
#[derive(Clone, Debug, Default, PartialEq, Eq)]
pub struct TimeIndex {
times: DeqColumn<Timestamp>,
first: i64,
}
#[derive(Clone, Debug, PartialEq, Eq)]
pub enum SeriesMapping {
Aligned {
first: i64,
},
Mapped {
first: i64,
offsets: Vec<u32>,
},
}
impl SeriesMapping {
pub fn is_aligned(&self) -> bool {
matches!(self, Self::Aligned { .. })
}
pub fn logical_index(&self, i: usize) -> Option<i64> {
match self {
Self::Aligned { first } => first.checked_add(i64::try_from(i).ok()?),
Self::Mapped { first, offsets } => offsets.get(i).map(|&off| first + i64::from(off)),
}
}
}
impl TimeIndex {
pub const fn new() -> Self {
Self {
times: DeqColumn::new(),
first: 0,
}
}
pub fn from_times(times: Vec<Timestamp>) -> Result<Self> {
check_increasing(×, None)?;
Ok(Self {
times: DeqColumn::from_vec(times),
first: 0,
})
}
pub fn len(&self) -> usize {
self.times.len()
}
pub fn is_empty(&self) -> bool {
self.times.is_empty()
}
pub fn times(&self) -> &[Timestamp] {
&self.times
}
pub fn first_index(&self) -> i64 {
self.first
}
pub fn end_index(&self) -> i64 {
self.first + len_i64(self.times.len())
}
pub fn time_at(&self, index: i64) -> Option<Timestamp> {
let pos = usize::try_from(index.checked_sub(self.first)?).ok()?;
self.times.get(pos).copied()
}
pub fn index_of(&self, time: Timestamp) -> Option<i64> {
let pos = self.times.binary_search(&time).ok()?;
Some(self.first + len_i64(pos))
}
pub fn lower_bound(&self, time: Timestamp) -> i64 {
self.first + len_i64(self.times.partition_point(|&t| t < time))
}
pub fn append(&mut self, times: &[Timestamp]) -> Result<()> {
check_increasing(times, self.times.last().copied())?;
self.times.extend_back(times)
}
pub fn prepend(&mut self, times: &[Timestamp]) -> Result<()> {
check_increasing(times, None)?;
if let (Some(&last_new), Some(&first_old)) = (times.last(), self.times.first())
&& last_new >= first_old
{
return Err(Error::TimeNotIncreasing {
index: times.len() - 1,
});
}
let first = self
.first
.checked_sub(len_i64(times.len()))
.ok_or(Error::InvalidArgument("logical index overflows i64"))?;
self.times.extend_front(times)?;
self.first = first;
Ok(())
}
pub fn map_series(&self, times: &[Timestamp]) -> Result<Option<SeriesMapping>> {
let Some(&t0) = times.first() else {
return Ok(Some(SeriesMapping::Aligned {
first: self.end_index(),
}));
};
let Ok(start) = self.times.binary_search(&t0) else {
return Ok(None);
};
let first = self.first + len_i64(start);
if self.times.get(start..start + times.len()) == Some(times) {
return Ok(Some(SeriesMapping::Aligned { first }));
}
let mut offsets = Vec::new();
offsets
.try_reserve_exact(times.len())
.map_err(|_| Error::OutOfMemory)?;
let mut pos = start;
for &t in times {
let rest = &self.times[pos..];
let step = rest.partition_point(|&x| x < t);
if rest.get(step) != Some(&t) {
return Ok(None);
}
pos += step;
let offset = u32::try_from(pos - start).map_err(|_| {
Error::InvalidArgument("mapped series spans more than u32::MAX slots")
})?;
offsets.push(offset);
pos += 1;
}
Ok(Some(SeriesMapping::Mapped { first, offsets }))
}
pub fn merge(&mut self, times: &[Timestamp]) -> Result<usize> {
check_increasing(times, None)?;
let old = self.times.as_slice();
let before_first = old
.first()
.map_or(0, |&f| times.partition_point(|&t| t < f));
let mut merged = Vec::new();
merged
.try_reserve_exact(old.len() + times.len())
.map_err(|_| Error::OutOfMemory)?;
let (mut i, mut j) = (0, 0);
while i < old.len() && j < times.len() {
let (a, b) = (old[i], times[j]);
merged.push(a.min(b));
i += usize::from(a <= b);
j += usize::from(b <= a);
}
merged.extend_from_slice(&old[i..]);
merged.extend_from_slice(×[j..]);
let inserted = merged.len() - old.len();
if inserted == 0 {
return Ok(0);
}
let first = self
.first
.checked_sub(len_i64(before_first))
.ok_or(Error::InvalidArgument("logical index overflows i64"))?;
self.times = DeqColumn::from_vec(merged);
self.first = first;
Ok(inserted)
}
pub fn reserve_back(&mut self, additional: usize) -> Result<()> {
self.times.reserve_back(additional)
}
pub fn reserve_front(&mut self, additional: usize) -> Result<()> {
self.times.reserve_front(additional)
}
pub fn shrink_to_fit(&mut self) {
self.times.shrink_to_fit();
}
pub(crate) fn truncate_ends(&mut self, front: usize, back: usize) {
let front = front.min(self.times.len());
self.times.truncate_ends(front, back);
self.first += len_i64(front);
}
pub(crate) fn rebase(&mut self, first: i64) {
self.first = first;
}
}
fn check_increasing(times: &[Timestamp], prev: Option<Timestamp>) -> Result<()> {
if let (Some(p), Some(&t0)) = (prev, times.first())
&& t0 <= p
{
return Err(Error::TimeNotIncreasing { index: 0 });
}
match times.windows(2).position(|w| w[1] <= w[0]) {
Some(k) => Err(Error::TimeNotIncreasing { index: k + 1 }),
None => Ok(()),
}
}
fn len_i64(n: usize) -> i64 {
i64::try_from(n).unwrap_or(i64::MAX)
}
#[cfg(test)]
mod tests {
use super::*;
use proptest::prelude::*;
use std::collections::BTreeSet;
fn sorted(max_len: usize) -> impl Strategy<Value = Vec<i64>> {
prop::collection::btree_set(-1000i64..1000, 0..max_len)
.prop_map(|s| s.into_iter().collect())
}
#[test]
fn empty_index() {
let index = TimeIndex::new();
assert_eq!((index.first_index(), index.end_index()), (0, 0));
assert_eq!(index.time_at(0), None);
assert_eq!(index.index_of(0), None);
assert_eq!(index.lower_bound(0), 0);
}
#[test]
fn append_and_prepend_on_empty_index() {
let mut index = TimeIndex::new();
index.prepend(&[1, 2]).unwrap();
assert_eq!(index.first_index(), -2);
index.append(&[3]).unwrap();
assert_eq!(index.index_of(3), Some(0));
}
#[test]
fn errors_leave_index_unchanged() {
let mut index = TimeIndex::from_times(vec![10, 20, 30]).unwrap();
let before = index.clone();
assert_eq!(
index.append(&[40, 40]),
Err(Error::TimeNotIncreasing { index: 1 })
);
assert_eq!(
index.prepend(&[0, 10]),
Err(Error::TimeNotIncreasing { index: 1 })
);
assert_eq!(
index.prepend(&[5, 1]),
Err(Error::TimeNotIncreasing { index: 1 })
);
assert_eq!(
index.merge(&[1, 1]),
Err(Error::TimeNotIncreasing { index: 1 })
);
assert_eq!(index, before);
}
#[test]
fn prepend_overflow_is_an_error() {
let mut index = TimeIndex::from_times(vec![10]).unwrap();
index.first = i64::MIN + 1;
assert!(matches!(
index.prepend(&[1, 2]),
Err(Error::InvalidArgument(_))
));
assert_eq!(index.first_index(), i64::MIN + 1);
}
#[test]
fn map_series_rejects_duplicates() {
let index = TimeIndex::from_times(vec![10, 20, 30]).unwrap();
assert_eq!(index.map_series(&[10, 10]).unwrap(), None);
assert_eq!(index.map_series(&[10, 30, 30]).unwrap(), None);
}
#[test]
fn mapping_survives_prepend() {
let mut index = TimeIndex::from_times(vec![10, 20, 30, 40]).unwrap();
let mapping = index.map_series(&[20, 40]).unwrap().unwrap();
index.prepend(&[1, 2, 3]).unwrap();
index.append(&[50]).unwrap();
assert_eq!(index.time_at(mapping.logical_index(0).unwrap()), Some(20));
assert_eq!(index.time_at(mapping.logical_index(1).unwrap()), Some(40));
}
#[test]
fn merge_without_new_times_is_a_no_op() {
let mut index = TimeIndex::from_times(vec![10, 20]).unwrap();
index.prepend(&[5]).unwrap();
let before = index.clone();
assert_eq!(index.merge(&[5, 20]).unwrap(), 0);
assert_eq!(index, before);
}
proptest! {
#[test]
fn logical_indices_are_stable(base in sorted(50), older in sorted(50), newer in sorted(50)) {
let older: Vec<i64> = older.into_iter().map(|t| t - 3000).collect();
let newer: Vec<i64> = newer.into_iter().map(|t| t + 3000).collect();
let mut index = TimeIndex::from_times(base.clone()).unwrap();
let before: Vec<Option<i64>> = base.iter().map(|&t| index.index_of(t)).collect();
index.prepend(&older).unwrap();
index.append(&newer).unwrap();
for (&t, &idx) in base.iter().zip(&before) {
prop_assert_eq!(index.index_of(t), idx);
}
for k in index.first_index()..index.end_index() {
let t = index.time_at(k).unwrap();
prop_assert_eq!(index.index_of(t), Some(k));
}
}
#[test]
fn map_series_round_trips(all in sorted(200), picks in prop::collection::vec(any::<bool>(), 200)) {
let index = TimeIndex::from_times(all.clone()).unwrap();
let series: Vec<i64> = all.iter().zip(&picks).filter(|(_, p)| **p).map(|(t, _)| *t).collect();
let mapping = index.map_series(&series).unwrap().unwrap();
for (i, &t) in series.iter().enumerate() {
prop_assert_eq!(index.time_at(mapping.logical_index(i).unwrap()), Some(t));
}
let contiguous = series.is_empty() || {
let s = all.binary_search(&series[0]).unwrap();
all[s..].starts_with(&series)
};
prop_assert_eq!(mapping.is_aligned(), contiguous);
}
#[test]
fn map_series_detects_non_subsets(all in sorted(100), series in sorted(20)) {
let index = TimeIndex::from_times(all.clone()).unwrap();
let is_subset = series.iter().all(|t| all.binary_search(t).is_ok());
prop_assert_eq!(index.map_series(&series).unwrap().is_some(), is_subset);
}
#[test]
fn merge_is_sorted_union(base in sorted(100), extra in sorted(100)) {
let mut index = TimeIndex::from_times(base.clone()).unwrap();
let inserted = index.merge(&extra).unwrap();
let union: BTreeSet<i64> = base.iter().chain(&extra).copied().collect();
let union: Vec<i64> = union.into_iter().collect();
prop_assert_eq!(index.times(), &union[..]);
prop_assert_eq!(inserted, union.len() - base.len());
if let Some(&b0) = base.first() {
prop_assert_eq!(index.index_of(b0), Some(0));
}
}
}
}