ferrochart_core/data/time_index.rs
1//! The global, index-based time axis shared by all series of a chart.
2//!
3//! Every distinct timestamp occupies one equal-width slot, so market closures,
4//! weekends and gaps are skipped naturally. Series refer to slots by **logical
5//! index**. Logical indices of existing timestamps never change on `append` or
6//! `prepend`; only [`TimeIndex::merge`] (a series that is not a subset of the
7//! time between existing slots) can shift them, and that requires a full rebuild.
8//!
9
10use super::{DeqColumn, Timestamp};
11use crate::error::{Error, Result};
12
13/// Sorted union of the timestamps of all series, with stable logical indices.
14///
15/// The slot of `times()[k]` has logical index `first_index() + k`. A new index
16/// starts at logical index 0; `prepend` moves `first_index()` down so that the
17/// existing timestamps keep their indices.
18///
19/// # Examples
20///
21/// ```
22/// use ferrochart_core::data::TimeIndex;
23///
24/// let mut index = TimeIndex::from_times(vec![100, 200, 300])?;
25/// index.append(&[400])?;
26/// index.prepend(&[0, 50])?;
27///
28/// // Existing timestamps keep their logical index; history gets negative ones.
29/// assert_eq!(index.index_of(100), Some(0));
30/// assert_eq!(index.index_of(0), Some(-2));
31/// assert_eq!(index.time_at(3), Some(400));
32/// assert_eq!((index.first_index(), index.end_index()), (-2, 4));
33/// # Ok::<(), ferrochart_core::Error>(())
34/// ```
35#[derive(Clone, Debug, Default, PartialEq, Eq)]
36pub struct TimeIndex {
37 times: DeqColumn<Timestamp>,
38 /// Logical index of `times[0]`. Decreases on `prepend`.
39 first: i64,
40}
41
42/// How the points of one series map to logical indices of the [`TimeIndex`].
43///
44///
45/// # Examples
46///
47/// ```
48/// use ferrochart_core::data::{SeriesMapping, TimeIndex};
49///
50/// let index = TimeIndex::from_times(vec![10, 20, 30, 40])?;
51///
52/// // A contiguous run of the index (e.g. an indicator computed from the main series).
53/// let aligned = index.map_series(&[20, 30, 40])?;
54/// assert_eq!(aligned, Some(SeriesMapping::Aligned { first: 1 }));
55///
56/// // A sparse subset needs a lookup table.
57/// let mapped = index.map_series(&[10, 40])?.unwrap();
58/// assert!(!mapped.is_aligned());
59/// assert_eq!(mapped.logical_index(1), Some(3));
60///
61/// // Not a subset: the caller has to merge.
62/// assert_eq!(index.map_series(&[15])?, None);
63/// # Ok::<(), ferrochart_core::Error>(())
64/// ```
65#[derive(Clone, Debug, PartialEq, Eq)]
66pub enum SeriesMapping {
67 /// Fast path: point `i` of the series is at logical index `first + i`. No
68 /// per-point memory.
69 Aligned {
70 /// Logical index of the series' first point.
71 first: i64,
72 },
73 /// General path: point `i` is at logical index `first + offsets[i]`.
74 /// `offsets` is strictly increasing and starts at 0. 4 bytes per point.
75 Mapped {
76 /// Logical index of the series' first point.
77 first: i64,
78 /// Offset of each point from `first`.
79 offsets: Vec<u32>,
80 },
81}
82
83impl SeriesMapping {
84 /// Whether this is the [`Aligned`](Self::Aligned) fast path.
85 ///
86 /// # Examples
87 ///
88 /// ```
89 /// use ferrochart_core::data::SeriesMapping;
90 ///
91 /// assert!(SeriesMapping::Aligned { first: 0 }.is_aligned());
92 /// ```
93 pub fn is_aligned(&self) -> bool {
94 matches!(self, Self::Aligned { .. })
95 }
96
97 /// Logical index of point `i` of the series. For `Mapped`, `None` if `i` is
98 /// out of range; for `Aligned`, `None` only if the index overflows `i64`.
99 ///
100 /// # Examples
101 ///
102 /// ```
103 /// use ferrochart_core::data::SeriesMapping;
104 ///
105 /// let m = SeriesMapping::Mapped { first: -5, offsets: vec![0, 2, 7] };
106 /// assert_eq!(m.logical_index(1), Some(-3));
107 /// assert_eq!(m.logical_index(3), None);
108 /// ```
109 pub fn logical_index(&self, i: usize) -> Option<i64> {
110 match self {
111 Self::Aligned { first } => first.checked_add(i64::try_from(i).ok()?),
112 Self::Mapped { first, offsets } => offsets.get(i).map(|&off| first + i64::from(off)),
113 }
114 }
115}
116
117impl TimeIndex {
118 /// Creates an empty index. Its first slot will get logical index 0.
119 ///
120 /// # Examples
121 ///
122 /// ```
123 /// use ferrochart_core::data::TimeIndex;
124 ///
125 /// assert!(TimeIndex::new().is_empty());
126 /// ```
127 pub const fn new() -> Self {
128 Self {
129 times: DeqColumn::new(),
130 first: 0,
131 }
132 }
133
134 /// Builds an index from timestamps without copying them.
135 /// Logical indices start at 0.
136 ///
137 /// # Errors
138 ///
139 /// [`Error::TimeNotIncreasing`] if `times` is not strictly increasing.
140 ///
141 /// # Examples
142 ///
143 /// ```
144 /// use ferrochart_core::{Error, data::TimeIndex};
145 ///
146 /// assert_eq!(TimeIndex::from_times(vec![1, 2, 2]), Err(Error::TimeNotIncreasing { index: 2 }));
147 /// assert_eq!(TimeIndex::from_times(vec![1, 2, 3])?.len(), 3);
148 /// # Ok::<(), ferrochart_core::Error>(())
149 /// ```
150 pub fn from_times(times: Vec<Timestamp>) -> Result<Self> {
151 check_increasing(×, None)?;
152 Ok(Self {
153 times: DeqColumn::from_vec(times),
154 first: 0,
155 })
156 }
157
158 /// Number of slots.
159 ///
160 /// # Examples
161 ///
162 /// ```
163 /// use ferrochart_core::data::TimeIndex;
164 ///
165 /// assert_eq!(TimeIndex::from_times(vec![5, 6])?.len(), 2);
166 /// # Ok::<(), ferrochart_core::Error>(())
167 /// ```
168 pub fn len(&self) -> usize {
169 self.times.len()
170 }
171
172 /// Whether there are no slots.
173 ///
174 /// # Examples
175 ///
176 /// ```
177 /// use ferrochart_core::data::TimeIndex;
178 ///
179 /// assert!(TimeIndex::default().is_empty());
180 /// ```
181 pub fn is_empty(&self) -> bool {
182 self.times.is_empty()
183 }
184
185 /// All timestamps, sorted, as one slice. `times()[k]` has logical index
186 /// `first_index() + k`.
187 ///
188 /// # Examples
189 ///
190 /// ```
191 /// use ferrochart_core::data::TimeIndex;
192 ///
193 /// let index = TimeIndex::from_times(vec![5, 6])?;
194 /// assert_eq!(index.times(), &[5, 6]);
195 /// # Ok::<(), ferrochart_core::Error>(())
196 /// ```
197 pub fn times(&self) -> &[Timestamp] {
198 &self.times
199 }
200
201 /// Logical index of the first slot.
202 ///
203 /// # Examples
204 ///
205 /// ```
206 /// use ferrochart_core::data::TimeIndex;
207 ///
208 /// let mut index = TimeIndex::from_times(vec![5, 6])?;
209 /// index.prepend(&[1, 2, 3])?;
210 /// assert_eq!(index.first_index(), -3);
211 /// # Ok::<(), ferrochart_core::Error>(())
212 /// ```
213 pub fn first_index(&self) -> i64 {
214 self.first
215 }
216
217 /// Logical index one past the last slot (`first_index() + len()`).
218 ///
219 /// # Examples
220 ///
221 /// ```
222 /// use ferrochart_core::data::TimeIndex;
223 ///
224 /// assert_eq!(TimeIndex::from_times(vec![5, 6])?.end_index(), 2);
225 /// # Ok::<(), ferrochart_core::Error>(())
226 /// ```
227 pub fn end_index(&self) -> i64 {
228 self.first + len_i64(self.times.len())
229 }
230
231 /// Timestamp of the slot with logical index `index`, or `None` outside the data.
232 ///
233 /// # Examples
234 ///
235 /// ```
236 /// use ferrochart_core::data::TimeIndex;
237 ///
238 /// let index = TimeIndex::from_times(vec![5, 6])?;
239 /// assert_eq!(index.time_at(1), Some(6));
240 /// assert_eq!(index.time_at(2), None);
241 /// assert_eq!(index.time_at(-1), None);
242 /// # Ok::<(), ferrochart_core::Error>(())
243 /// ```
244 pub fn time_at(&self, index: i64) -> Option<Timestamp> {
245 let pos = usize::try_from(index.checked_sub(self.first)?).ok()?;
246 self.times.get(pos).copied()
247 }
248
249 /// Logical index of `time` if it is in the index. O(log n).
250 ///
251 /// # Examples
252 ///
253 /// ```
254 /// use ferrochart_core::data::TimeIndex;
255 ///
256 /// let index = TimeIndex::from_times(vec![5, 6])?;
257 /// assert_eq!(index.index_of(6), Some(1));
258 /// assert_eq!(index.index_of(7), None);
259 /// # Ok::<(), ferrochart_core::Error>(())
260 /// ```
261 pub fn index_of(&self, time: Timestamp) -> Option<i64> {
262 let pos = self.times.binary_search(&time).ok()?;
263 Some(self.first + len_i64(pos))
264 }
265
266 /// Logical index of the first slot whose time is `>= time`; `end_index()` if
267 /// there is none. O(log n).
268 ///
269 /// # Examples
270 ///
271 /// ```
272 /// use ferrochart_core::data::TimeIndex;
273 ///
274 /// let index = TimeIndex::from_times(vec![10, 20, 30])?;
275 /// assert_eq!(index.lower_bound(20), 1);
276 /// assert_eq!(index.lower_bound(21), 2);
277 /// assert_eq!(index.lower_bound(99), 3);
278 /// # Ok::<(), ferrochart_core::Error>(())
279 /// ```
280 pub fn lower_bound(&self, time: Timestamp) -> i64 {
281 self.first + len_i64(self.times.partition_point(|&t| t < time))
282 }
283
284 /// Appends new slots after the last one. Existing logical indices are unchanged.
285 ///
286 /// # Errors
287 ///
288 /// - [`Error::TimeNotIncreasing`] if `times` is not strictly increasing or its
289 /// first element is not after the current last timestamp (`index` refers to
290 /// `times`);
291 /// - [`Error::OutOfMemory`] if the allocation fails.
292 ///
293 /// The index is unchanged on error.
294 ///
295 /// # Examples
296 ///
297 /// ```
298 /// use ferrochart_core::{Error, data::TimeIndex};
299 ///
300 /// let mut index = TimeIndex::from_times(vec![10, 20])?;
301 /// assert_eq!(index.append(&[20]), Err(Error::TimeNotIncreasing { index: 0 }));
302 /// index.append(&[30, 40])?;
303 /// assert_eq!(index.times(), &[10, 20, 30, 40]);
304 /// # Ok::<(), ferrochart_core::Error>(())
305 /// ```
306 pub fn append(&mut self, times: &[Timestamp]) -> Result<()> {
307 check_increasing(times, self.times.last().copied())?;
308 self.times.extend_back(times)
309 }
310
311 /// Inserts older slots before the first one (loading history). Existing
312 /// timestamps keep their logical indices; the new ones get the indices just
313 /// below `first_index()`.
314 ///
315 /// # Errors
316 ///
317 /// - [`Error::TimeNotIncreasing`] if `times` is not strictly increasing or its
318 /// last element is not before the current first timestamp (`index` refers
319 /// to `times`);
320 /// - [`Error::InvalidArgument`] if the logical index would overflow `i64`;
321 /// - [`Error::OutOfMemory`] if the allocation fails.
322 ///
323 /// The index is unchanged on error.
324 ///
325 /// # Examples
326 ///
327 /// ```
328 /// use ferrochart_core::data::TimeIndex;
329 ///
330 /// let mut index = TimeIndex::from_times(vec![30, 40])?;
331 /// index.prepend(&[10, 20])?;
332 /// assert_eq!(index.times(), &[10, 20, 30, 40]);
333 /// assert_eq!(index.index_of(30), Some(0));
334 /// assert_eq!(index.index_of(10), Some(-2));
335 /// # Ok::<(), ferrochart_core::Error>(())
336 /// ```
337 pub fn prepend(&mut self, times: &[Timestamp]) -> Result<()> {
338 check_increasing(times, None)?;
339 if let (Some(&last_new), Some(&first_old)) = (times.last(), self.times.first())
340 && last_new >= first_old
341 {
342 return Err(Error::TimeNotIncreasing {
343 index: times.len() - 1,
344 });
345 }
346 let first = self
347 .first
348 .checked_sub(len_i64(times.len()))
349 .ok_or(Error::InvalidArgument("logical index overflows i64"))?;
350 self.times.extend_front(times)?;
351 self.first = first;
352 Ok(())
353 }
354
355 /// Maps a series' timestamps onto the index.
356 ///
357 /// Returns `Some(Aligned)` if `times` equals a contiguous run of the index,
358 /// `Some(Mapped)` if it is a sparse subset, and `None` if it contains a
359 /// timestamp that is not in the index or is not strictly increasing (the
360 /// caller then has to [`merge`](Self::merge)). An empty
361 /// series maps to `Aligned { first: end_index() }`.
362 ///
363 /// Cost: O(m) when aligned, O(m log n) otherwise (m = `times.len()`).
364 ///
365 /// # Errors
366 ///
367 /// - [`Error::InvalidArgument`] if a mapped series spans more than `u32::MAX`
368 /// slots;
369 /// - [`Error::OutOfMemory`] if the offset table cannot be allocated.
370 ///
371 /// # Examples
372 ///
373 /// ```
374 /// use ferrochart_core::data::{SeriesMapping, TimeIndex};
375 ///
376 /// let index = TimeIndex::from_times(vec![10, 20, 30])?;
377 /// assert_eq!(index.map_series(&[10, 20, 30])?, Some(SeriesMapping::Aligned { first: 0 }));
378 /// assert_eq!(
379 /// index.map_series(&[10, 30])?,
380 /// Some(SeriesMapping::Mapped { first: 0, offsets: vec![0, 2] }),
381 /// );
382 /// assert_eq!(index.map_series(&[30, 10])?, None); // not increasing
383 /// # Ok::<(), ferrochart_core::Error>(())
384 /// ```
385 pub fn map_series(&self, times: &[Timestamp]) -> Result<Option<SeriesMapping>> {
386 let Some(&t0) = times.first() else {
387 return Ok(Some(SeriesMapping::Aligned {
388 first: self.end_index(),
389 }));
390 };
391 let Ok(start) = self.times.binary_search(&t0) else {
392 return Ok(None);
393 };
394 let first = self.first + len_i64(start);
395
396 // Fast path: a contiguous run (one memcmp).
397 if self.times.get(start..start + times.len()) == Some(times) {
398 return Ok(Some(SeriesMapping::Aligned { first }));
399 }
400
401 // General path: each next timestamp must be found strictly after the
402 // previous match, which also rejects unsorted or duplicate input.
403 let mut offsets = Vec::new();
404 offsets
405 .try_reserve_exact(times.len())
406 .map_err(|_| Error::OutOfMemory)?;
407 let mut pos = start;
408 for &t in times {
409 let rest = &self.times[pos..];
410 let step = rest.partition_point(|&x| x < t);
411 if rest.get(step) != Some(&t) {
412 return Ok(None);
413 }
414 pos += step;
415 let offset = u32::try_from(pos - start).map_err(|_| {
416 Error::InvalidArgument("mapped series spans more than u32::MAX slots")
417 })?;
418 offsets.push(offset);
419 pos += 1;
420 }
421 Ok(Some(SeriesMapping::Mapped { first, offsets }))
422 }
423
424 /// Merges timestamps that are not yet in the index, keeping it sorted, and
425 /// returns how many slots were inserted.
426 ///
427 /// Timestamps before the current first one get logical indices below
428 /// `first_index()`, so those slots behave like a prepend. Any timestamp
429 /// inserted **between** existing ones shifts the logical index of every later
430 /// slot: the caller must then rebuild everything that stores logical indices
431 /// (series mappings, LOD, GPU buffers) and report a warning. O(n + m).
432 ///
433 /// # Errors
434 ///
435 /// - [`Error::TimeNotIncreasing`] if `times` is not strictly increasing;
436 /// - [`Error::InvalidArgument`] if the logical index would overflow `i64`;
437 /// - [`Error::OutOfMemory`] if the allocation fails.
438 ///
439 /// The index is unchanged on error.
440 ///
441 /// # Examples
442 ///
443 /// ```
444 /// use ferrochart_core::data::TimeIndex;
445 ///
446 /// let mut index = TimeIndex::from_times(vec![10, 20, 30])?;
447 /// assert_eq!(index.merge(&[5, 20, 25])?, 2);
448 /// assert_eq!(index.times(), &[5, 10, 20, 25, 30]);
449 /// assert_eq!(index.index_of(10), Some(0)); // before the first insertion: unchanged
450 /// assert_eq!(index.index_of(30), Some(3)); // after an inner insertion: shifted
451 /// # Ok::<(), ferrochart_core::Error>(())
452 /// ```
453 pub fn merge(&mut self, times: &[Timestamp]) -> Result<usize> {
454 check_increasing(times, None)?;
455 let old = self.times.as_slice();
456 let before_first = old
457 .first()
458 .map_or(0, |&f| times.partition_point(|&t| t < f));
459
460 let mut merged = Vec::new();
461 merged
462 .try_reserve_exact(old.len() + times.len())
463 .map_err(|_| Error::OutOfMemory)?;
464 let (mut i, mut j) = (0, 0);
465 while i < old.len() && j < times.len() {
466 let (a, b) = (old[i], times[j]);
467 merged.push(a.min(b));
468 i += usize::from(a <= b);
469 j += usize::from(b <= a);
470 }
471 merged.extend_from_slice(&old[i..]);
472 merged.extend_from_slice(×[j..]);
473
474 let inserted = merged.len() - old.len();
475 if inserted == 0 {
476 return Ok(0);
477 }
478 let first = self
479 .first
480 .checked_sub(len_i64(before_first))
481 .ok_or(Error::InvalidArgument("logical index overflows i64"))?;
482 self.times = DeqColumn::from_vec(merged);
483 self.first = first;
484 Ok(inserted)
485 }
486
487 /// Reserves room for `additional` slots after the last one, so that a later
488 /// [`append`](Self::append) of that many cannot fail with `OutOfMemory`.
489 ///
490 /// # Errors
491 ///
492 /// [`Error::OutOfMemory`] if the allocation fails.
493 ///
494 /// # Examples
495 ///
496 /// ```
497 /// use ferrochart_core::data::TimeIndex;
498 ///
499 /// let mut index = TimeIndex::new();
500 /// index.reserve_back(10)?;
501 /// # Ok::<(), ferrochart_core::Error>(())
502 /// ```
503 pub fn reserve_back(&mut self, additional: usize) -> Result<()> {
504 self.times.reserve_back(additional)
505 }
506
507 /// Reserves room for `additional` slots before the first one, so that a later
508 /// [`prepend`](Self::prepend) of that many cannot fail with `OutOfMemory`.
509 ///
510 /// # Errors
511 ///
512 /// [`Error::OutOfMemory`] if the allocation fails.
513 ///
514 /// # Examples
515 ///
516 /// ```
517 /// use ferrochart_core::data::TimeIndex;
518 ///
519 /// let mut index = TimeIndex::new();
520 /// index.reserve_front(10)?;
521 /// # Ok::<(), ferrochart_core::Error>(())
522 /// ```
523 pub fn reserve_front(&mut self, additional: usize) -> Result<()> {
524 self.times.reserve_front(additional)
525 }
526
527 /// Releases growth slack (called after `set_data`).
528 ///
529 /// # Examples
530 ///
531 /// ```
532 /// use ferrochart_core::data::TimeIndex;
533 ///
534 /// let mut index = TimeIndex::new();
535 /// index.append(&[1, 2, 3])?;
536 /// index.shrink_to_fit();
537 /// assert_eq!(index.len(), 3);
538 /// # Ok::<(), ferrochart_core::Error>(())
539 /// ```
540 pub fn shrink_to_fit(&mut self) {
541 self.times.shrink_to_fit();
542 }
543
544 /// Removes `front` slots at the front and `back` at the back (undoes a
545 /// `prepend`/`append` whose series operation then failed).
546 pub(crate) fn truncate_ends(&mut self, front: usize, back: usize) {
547 let front = front.min(self.times.len());
548 self.times.truncate_ends(front, back);
549 self.first += len_i64(front);
550 }
551
552 /// Moves the logical indices so that the first slot gets index `first`.
553 pub(crate) fn rebase(&mut self, first: i64) {
554 self.first = first;
555 }
556}
557
558/// Checks that `times` is strictly increasing and, if given, starts after `prev`.
559fn check_increasing(times: &[Timestamp], prev: Option<Timestamp>) -> Result<()> {
560 if let (Some(p), Some(&t0)) = (prev, times.first())
561 && t0 <= p
562 {
563 return Err(Error::TimeNotIncreasing { index: 0 });
564 }
565 match times.windows(2).position(|w| w[1] <= w[0]) {
566 Some(k) => Err(Error::TimeNotIncreasing { index: k + 1 }),
567 None => Ok(()),
568 }
569}
570
571/// Lengths and positions fit in `i64`: a `Vec` never exceeds `isize::MAX` elements.
572fn len_i64(n: usize) -> i64 {
573 i64::try_from(n).unwrap_or(i64::MAX)
574}
575
576#[cfg(test)]
577mod tests {
578 use super::*;
579 use proptest::prelude::*;
580 use std::collections::BTreeSet;
581
582 fn sorted(max_len: usize) -> impl Strategy<Value = Vec<i64>> {
583 prop::collection::btree_set(-1000i64..1000, 0..max_len)
584 .prop_map(|s| s.into_iter().collect())
585 }
586
587 #[test]
588 fn empty_index() {
589 let index = TimeIndex::new();
590 assert_eq!((index.first_index(), index.end_index()), (0, 0));
591 assert_eq!(index.time_at(0), None);
592 assert_eq!(index.index_of(0), None);
593 assert_eq!(index.lower_bound(0), 0);
594 }
595
596 #[test]
597 fn append_and_prepend_on_empty_index() {
598 let mut index = TimeIndex::new();
599 index.prepend(&[1, 2]).unwrap();
600 assert_eq!(index.first_index(), -2);
601 index.append(&[3]).unwrap();
602 assert_eq!(index.index_of(3), Some(0));
603 }
604
605 #[test]
606 fn errors_leave_index_unchanged() {
607 let mut index = TimeIndex::from_times(vec![10, 20, 30]).unwrap();
608 let before = index.clone();
609 assert_eq!(
610 index.append(&[40, 40]),
611 Err(Error::TimeNotIncreasing { index: 1 })
612 );
613 assert_eq!(
614 index.prepend(&[0, 10]),
615 Err(Error::TimeNotIncreasing { index: 1 })
616 );
617 assert_eq!(
618 index.prepend(&[5, 1]),
619 Err(Error::TimeNotIncreasing { index: 1 })
620 );
621 assert_eq!(
622 index.merge(&[1, 1]),
623 Err(Error::TimeNotIncreasing { index: 1 })
624 );
625 assert_eq!(index, before);
626 }
627
628 #[test]
629 fn prepend_overflow_is_an_error() {
630 let mut index = TimeIndex::from_times(vec![10]).unwrap();
631 index.first = i64::MIN + 1;
632 assert!(matches!(
633 index.prepend(&[1, 2]),
634 Err(Error::InvalidArgument(_))
635 ));
636 assert_eq!(index.first_index(), i64::MIN + 1);
637 }
638
639 #[test]
640 fn map_series_rejects_duplicates() {
641 let index = TimeIndex::from_times(vec![10, 20, 30]).unwrap();
642 assert_eq!(index.map_series(&[10, 10]).unwrap(), None);
643 assert_eq!(index.map_series(&[10, 30, 30]).unwrap(), None);
644 }
645
646 #[test]
647 fn mapping_survives_prepend() {
648 let mut index = TimeIndex::from_times(vec![10, 20, 30, 40]).unwrap();
649 let mapping = index.map_series(&[20, 40]).unwrap().unwrap();
650 index.prepend(&[1, 2, 3]).unwrap();
651 index.append(&[50]).unwrap();
652 assert_eq!(index.time_at(mapping.logical_index(0).unwrap()), Some(20));
653 assert_eq!(index.time_at(mapping.logical_index(1).unwrap()), Some(40));
654 }
655
656 #[test]
657 fn merge_without_new_times_is_a_no_op() {
658 let mut index = TimeIndex::from_times(vec![10, 20]).unwrap();
659 index.prepend(&[5]).unwrap();
660 let before = index.clone();
661 assert_eq!(index.merge(&[5, 20]).unwrap(), 0);
662 assert_eq!(index, before);
663 }
664
665 proptest! {
666 /// Appends and prepends never change the logical index of existing times.
667 #[test]
668 fn logical_indices_are_stable(base in sorted(50), older in sorted(50), newer in sorted(50)) {
669 let older: Vec<i64> = older.into_iter().map(|t| t - 3000).collect();
670 let newer: Vec<i64> = newer.into_iter().map(|t| t + 3000).collect();
671 let mut index = TimeIndex::from_times(base.clone()).unwrap();
672 let before: Vec<Option<i64>> = base.iter().map(|&t| index.index_of(t)).collect();
673 index.prepend(&older).unwrap();
674 index.append(&newer).unwrap();
675 for (&t, &idx) in base.iter().zip(&before) {
676 prop_assert_eq!(index.index_of(t), idx);
677 }
678 for k in index.first_index()..index.end_index() {
679 let t = index.time_at(k).unwrap();
680 prop_assert_eq!(index.index_of(t), Some(k));
681 }
682 }
683
684 /// A mapping always points back at the series' own timestamps, and it is
685 /// `Aligned` exactly when the series is a contiguous run of the index.
686 #[test]
687 fn map_series_round_trips(all in sorted(200), picks in prop::collection::vec(any::<bool>(), 200)) {
688 let index = TimeIndex::from_times(all.clone()).unwrap();
689 let series: Vec<i64> = all.iter().zip(&picks).filter(|(_, p)| **p).map(|(t, _)| *t).collect();
690 let mapping = index.map_series(&series).unwrap().unwrap();
691 for (i, &t) in series.iter().enumerate() {
692 prop_assert_eq!(index.time_at(mapping.logical_index(i).unwrap()), Some(t));
693 }
694 let contiguous = series.is_empty() || {
695 let s = all.binary_search(&series[0]).unwrap();
696 all[s..].starts_with(&series)
697 };
698 prop_assert_eq!(mapping.is_aligned(), contiguous);
699 }
700
701 /// `map_series` returns `None` exactly when some timestamp is not in the index.
702 #[test]
703 fn map_series_detects_non_subsets(all in sorted(100), series in sorted(20)) {
704 let index = TimeIndex::from_times(all.clone()).unwrap();
705 let is_subset = series.iter().all(|t| all.binary_search(t).is_ok());
706 prop_assert_eq!(index.map_series(&series).unwrap().is_some(), is_subset);
707 }
708
709 /// `merge` produces the sorted union and keeps indices of timestamps before
710 /// the first inner insertion.
711 #[test]
712 fn merge_is_sorted_union(base in sorted(100), extra in sorted(100)) {
713 let mut index = TimeIndex::from_times(base.clone()).unwrap();
714 let inserted = index.merge(&extra).unwrap();
715 let union: BTreeSet<i64> = base.iter().chain(&extra).copied().collect();
716 let union: Vec<i64> = union.into_iter().collect();
717 prop_assert_eq!(index.times(), &union[..]);
718 prop_assert_eq!(inserted, union.len() - base.len());
719 if let Some(&b0) = base.first() {
720 prop_assert_eq!(index.index_of(b0), Some(0));
721 }
722 }
723 }
724}