Skip to main content

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(&times, 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(&times[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}