tempoch_core/
interval.rs

1// SPDX-License-Identifier: AGPL-3.0-only
2// Copyright (C) 2026 Vallés Puig, Ramon
3
4//! Generic time intervals.
5//!
6//! [`Interval`] is a half-open range `[start, end)` over any totally-ordered
7//! instant type. It is parameterised on `T: Copy + PartialOrd` so that the
8//! same type works for `Time<A>` on any axis as well as for
9//! `chrono::DateTime<Utc>`.
10
11use core::fmt;
12
13use crate::Time;
14
15#[inline]
16fn partial_max<T: PartialOrd + Copy>(a: T, b: T) -> T {
17    if a >= b {
18        a
19    } else {
20        b
21    }
22}
23
24#[inline]
25fn partial_min<T: PartialOrd + Copy>(a: T, b: T) -> T {
26    if a <= b {
27        a
28    } else {
29        b
30    }
31}
32
33/// Error constructing an [`Interval`] with invalid bounds.
34#[derive(Debug, Clone, Copy, PartialEq, Eq)]
35pub enum InvalidIntervalError {
36    /// `!(start <= end)` (also triggers for NaN endpoints).
37    StartAfterEnd,
38}
39
40impl fmt::Display for InvalidIntervalError {
41    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
42        f.write_str("interval start must not be after end")
43    }
44}
45
46impl std::error::Error for InvalidIntervalError {}
47
48/// Invariants on a period list.
49#[derive(Debug, Clone, Copy, PartialEq, Eq)]
50pub enum PeriodListError {
51    /// Interval at `index` has `start > end`.
52    InvalidInterval { index: usize },
53    /// Interval at `index` is not sorted by start time.
54    Unsorted { index: usize },
55    /// Interval at `index` overlaps its predecessor.
56    Overlapping { index: usize },
57}
58
59impl fmt::Display for PeriodListError {
60    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
61        match self {
62            Self::InvalidInterval { index } => {
63                write!(f, "interval at index {index} has start > end")
64            }
65            Self::Unsorted { index } => {
66                write!(f, "interval at index {index} is not sorted by start time")
67            }
68            Self::Overlapping { index } => {
69                write!(f, "interval at index {index} overlaps its predecessor")
70            }
71        }
72    }
73}
74
75impl std::error::Error for PeriodListError {}
76
77/// Half-open time interval `[start, end)`.
78///
79/// Half-open intervals are convenient for period arithmetic because adjacent
80/// intervals such as `[a, b)` and `[b, c)` touch without overlapping.
81#[derive(Debug, Clone, Copy, PartialEq)]
82pub struct Interval<T: Copy + PartialOrd> {
83    /// Inclusive lower bound.
84    pub start: T,
85    /// Exclusive upper bound.
86    pub end: T,
87}
88
89impl<T> fmt::Display for Interval<T>
90where
91    T: Copy + PartialOrd + fmt::Display,
92{
93    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
94        write!(f, "[{}, {})", self.start, self.end)
95    }
96}
97
98/// Typed time period on a given scale.
99///
100/// This is an alias of [`Interval<Time<S>>`](Interval), so all interval
101/// operations are available directly on `Period`.
102pub type Period<S> = Interval<Time<S>>;
103
104/// Backward-compatible alias for period construction validation errors.
105pub type InvalidPeriodError = InvalidIntervalError;
106
107impl<T: Copy + PartialOrd> Interval<T> {
108    /// Construct without validation.
109    ///
110    /// This accepts any `start`/`end` pair, including reversed or NaN-like
111    /// endpoints. Prefer [`try_new`](Self::try_new) when the bounds come from
112    /// computation or external input.
113    #[inline]
114    pub fn new<S: Into<T>, E: Into<T>>(start: S, end: E) -> Self {
115        Self {
116            start: start.into(),
117            end: end.into(),
118        }
119    }
120
121    /// Validating constructor: rejects `start > end` and NaN endpoints.
122    ///
123    /// Zero-length intervals where `start == end` are allowed.
124    #[inline]
125    pub fn try_new<S: Into<T>, E: Into<T>>(start: S, end: E) -> Result<Self, InvalidIntervalError> {
126        let start = start.into();
127        let end = end.into();
128        if start <= end {
129            Ok(Self { start, end })
130        } else {
131            Err(InvalidIntervalError::StartAfterEnd)
132        }
133    }
134
135    // ── Pair operations ──────────────────────────────────────────────────────
136
137    /// Overlap as a half-open range. Returns `None` if the intervals touch
138    /// only at a point or do not overlap.
139    #[inline]
140    pub fn intersection(&self, other: &Self) -> Option<Self> {
141        let start = partial_max(self.start, other.start);
142        let end = partial_min(self.end, other.end);
143        if start < end {
144            Some(Self::new(start, end))
145        } else {
146            None
147        }
148    }
149
150    /// Smallest interval covering both `self` and `other`, together with any
151    /// gap between them.
152    ///
153    /// Returns one interval when they overlap or touch, two when they are
154    /// strictly disjoint (sorted by start time).
155    ///
156    /// This pairwise API preserves disjointness instead of forcing a merged
157    /// interval that would invent coverage through the gap.
158    #[inline]
159    pub fn union(&self, other: &Self) -> Vec<Self> {
160        if self.start <= other.end && other.start <= self.end {
161            vec![Self::new(
162                partial_min(self.start, other.start),
163                partial_max(self.end, other.end),
164            )]
165        } else if self.start <= other.start {
166            vec![*self, *other]
167        } else {
168            vec![*other, *self]
169        }
170    }
171
172    // ── Self-as-outer complement ─────────────────────────────────────────────
173
174    /// Gaps inside `self` that are not covered by any interval in `periods`.
175    ///
176    /// `periods` must be sorted and non-overlapping
177    /// (see [`Interval::validate`]). Intervals outside `self` are effectively
178    /// ignored except for how they advance the internal cursor.
179    #[inline]
180    pub fn complement(&self, periods: &[Self]) -> Vec<Self> {
181        let mut gaps = Vec::with_capacity(periods.len().saturating_add(1));
182        let mut cursor = self.start;
183        for p in periods {
184            if p.end <= cursor {
185                continue;
186            }
187            if p.start >= self.end {
188                break;
189            }
190            if p.start > cursor {
191                gaps.push(Self::new(cursor, p.start));
192            }
193            if p.end >= self.end {
194                return gaps;
195            }
196            cursor = p.end;
197        }
198        if cursor < self.end {
199            gaps.push(Self::new(cursor, self.end));
200        }
201        gaps
202    }
203
204    /// Checked variant of [`complement`](Self::complement).
205    ///
206    /// Validates that `self` is well ordered and that `periods` is sorted,
207    /// non-overlapping, and internally valid before computing the complement.
208    #[inline]
209    pub fn try_complement(&self, periods: &[Self]) -> Result<Vec<Self>, PeriodListError> {
210        if self
211            .start
212            .partial_cmp(&self.end)
213            .is_none_or(|ordering| ordering == core::cmp::Ordering::Greater)
214        {
215            return Err(PeriodListError::InvalidInterval { index: 0 });
216        }
217        Self::validate(periods)?;
218        Ok(self.complement(periods))
219    }
220
221    // ── List operations (associated functions) ───────────────────────────────
222
223    /// Check that a list is sorted, non-overlapping, and each `start <= end`.
224    ///
225    /// Touching intervals such as `[a, b)` followed by `[b, c)` are valid.
226    pub fn validate(periods: &[Self]) -> Result<(), PeriodListError> {
227        let mut prev: Option<Interval<T>> = None;
228        for (i, period) in periods.iter().copied().enumerate() {
229            if period
230                .start
231                .partial_cmp(&period.end)
232                .is_none_or(|ordering| ordering == core::cmp::Ordering::Greater)
233            {
234                return Err(PeriodListError::InvalidInterval { index: i });
235            }
236            if let Some(previous) = prev {
237                if previous
238                    .start
239                    .partial_cmp(&period.start)
240                    .is_none_or(|ordering| ordering == core::cmp::Ordering::Greater)
241                {
242                    return Err(PeriodListError::Unsorted { index: i });
243                }
244                if previous.end > period.start {
245                    return Err(PeriodListError::Overlapping { index: i });
246                }
247            }
248            prev = Some(period);
249        }
250        Ok(())
251    }
252
253    /// Intersection of two sorted, non-overlapping period lists. `O(n + m)`.
254    pub fn intersect_many(a: &[Self], b: &[Self]) -> Vec<Self> {
255        let mut result = Vec::with_capacity(a.len().min(b.len()));
256        let (mut i, mut j) = (0, 0);
257        while i < a.len() && j < b.len() {
258            let start = partial_max(a[i].start, b[j].start);
259            let end = partial_min(a[i].end, b[j].end);
260            if start < end {
261                result.push(Self::new(start, end));
262            }
263            if a[i].end <= b[j].end {
264                i += 1;
265            } else {
266                j += 1;
267            }
268        }
269        result
270    }
271
272    /// Checked variant of [`intersect_many`](Self::intersect_many).
273    ///
274    /// Validates both input lists before computing their intersection.
275    pub fn try_intersect_many(a: &[Self], b: &[Self]) -> Result<Vec<Self>, PeriodListError> {
276        Self::validate(a)?;
277        Self::validate(b)?;
278        Ok(Self::intersect_many(a, b))
279    }
280
281    /// Union of two sorted period lists.
282    ///
283    /// Overlapping and adjacent intervals are merged. The result is sorted and
284    /// non-overlapping.
285    pub fn union_many(a: &[Self], b: &[Self]) -> Vec<Self> {
286        let mut combined: Vec<Self> = a.iter().chain(b.iter()).copied().collect();
287        combined.sort_unstable_by(|x, y| {
288            x.start
289                .partial_cmp(&y.start)
290                .unwrap_or(core::cmp::Ordering::Equal)
291        });
292        Self::normalize(&combined)
293    }
294
295    /// Sort and merge overlapping or adjacent intervals.
296    ///
297    /// This is useful for normalizing hand-built or concatenated period lists
298    /// before later set operations.
299    pub fn normalize(periods: &[Self]) -> Vec<Self> {
300        if periods.is_empty() {
301            return Vec::new();
302        }
303        let mut sorted: Vec<_> = periods.to_vec();
304        sorted.sort_unstable_by(|a, b| {
305            a.start
306                .partial_cmp(&b.start)
307                .unwrap_or(core::cmp::Ordering::Equal)
308        });
309        let mut merged = Vec::with_capacity(sorted.len());
310        merged.push(sorted[0]);
311        for period in sorted.into_iter().skip(1) {
312            if let Some(last) = merged.last_mut() {
313                if period.start <= last.end {
314                    if period.end > last.end {
315                        last.end = period.end;
316                    }
317                } else {
318                    merged.push(period);
319                }
320            }
321        }
322        merged
323    }
324}
325
326#[cfg(test)]
327mod tests {
328    use super::*;
329    use crate::representation::{JulianDate, ModifiedJulianDate, MJD};
330    use crate::{Time, TT};
331    use qtty::Day;
332    #[cfg(feature = "serde")]
333    use serde::de::{value, IntoDeserializer};
334    #[cfg(feature = "serde")]
335    use serde::Deserialize;
336    #[cfg(feature = "serde")]
337    use serde_json::json;
338
339    #[test]
340    fn try_new_rejects_reversed() {
341        assert_eq!(
342            Interval::<f64>::try_new(2.0_f64, 1.0).unwrap_err(),
343            InvalidIntervalError::StartAfterEnd
344        );
345    }
346
347    #[test]
348    fn try_new_rejects_nan() {
349        assert!(Interval::<f64>::try_new(f64::NAN, 0.0).is_err());
350    }
351
352    #[test]
353    fn intersection_half_open() {
354        let a = Interval::<f64>::new(0.0_f64, 10.0);
355        let b = Interval::<f64>::new(10.0, 20.0);
356        assert!(a.intersection(&b).is_none());
357        let c = Interval::<f64>::new(5.0_f64, 15.0);
358        let x = a.intersection(&c).unwrap();
359        assert_eq!(x.start, 5.0);
360        assert_eq!(x.end, 10.0);
361    }
362
363    #[test]
364    fn complement_covers_gaps() {
365        let outer = Interval::<f64>::new(0.0_f64, 10.0);
366        let inside = vec![
367            Interval::<f64>::new(1.0_f64, 2.0),
368            Interval::<f64>::new(4.0, 6.0),
369        ];
370        let gaps = outer.complement(&inside);
371        assert_eq!(gaps.len(), 3);
372        assert_eq!(gaps[0], Interval::<f64>::new(0.0, 1.0));
373        assert_eq!(gaps[1], Interval::<f64>::new(2.0, 4.0));
374        assert_eq!(gaps[2], Interval::<f64>::new(6.0, 10.0));
375    }
376
377    #[test]
378    fn complement_ignores_periods_after_outer_interval() {
379        let outer = Interval::<f64>::new(10.0_f64, 20.0);
380        let inside = vec![Interval::<f64>::new(25.0_f64, 30.0)];
381
382        assert_eq!(
383            outer.complement(&inside),
384            vec![Interval::<f64>::new(10.0, 20.0)]
385        );
386    }
387
388    #[test]
389    fn complement_clips_periods_spanning_outer_end() {
390        let outer = Interval::<f64>::new(10.0_f64, 20.0);
391        let inside = vec![Interval::<f64>::new(12.0_f64, 30.0)];
392
393        assert_eq!(
394            outer.complement(&inside),
395            vec![Interval::<f64>::new(10.0, 12.0)]
396        );
397    }
398
399    #[test]
400    fn intersect_merge() {
401        let a = vec![
402            Interval::<f64>::new(0.0_f64, 5.0),
403            Interval::<f64>::new(10.0, 15.0),
404        ];
405        let b = vec![Interval::<f64>::new(3.0_f64, 12.0)];
406        let ix = Interval::intersect_many(&a, &b);
407        assert_eq!(ix.len(), 2);
408        assert_eq!(ix[0], Interval::<f64>::new(3.0, 5.0));
409        assert_eq!(ix[1], Interval::<f64>::new(10.0, 12.0));
410    }
411
412    #[test]
413    fn normalize_merges_overlap() {
414        let input = vec![
415            Interval::<f64>::new(5.0_f64, 8.0),
416            Interval::<f64>::new(0.0, 3.0),
417            Interval::<f64>::new(2.0, 6.0),
418        ];
419        let merged = Interval::normalize(&input);
420        assert_eq!(merged.len(), 1);
421        assert_eq!(merged[0], Interval::<f64>::new(0.0, 8.0));
422    }
423
424    #[test]
425    fn validate_detects_overlap() {
426        let periods = vec![
427            Interval::<f64>::new(0.0_f64, 5.0),
428            Interval::<f64>::new(3.0, 8.0),
429        ];
430        assert_eq!(
431            Interval::validate(&periods),
432            Err(PeriodListError::Overlapping { index: 1 })
433        );
434    }
435
436    #[test]
437    fn period_accepts_typed_times() {
438        let p = Period::<TT>::new(
439            ModifiedJulianDate::<TT>::try_new(Day::new(51_544.5))
440                .unwrap()
441                .to_time(),
442            ModifiedJulianDate::<TT>::try_new(Day::new(51_545.25))
443                .unwrap()
444                .to_time(),
445        );
446        assert_eq!(p.start.to::<MJD>().raw(), Day::new(51_544.5));
447        assert_eq!(p.end.to::<MJD>().raw(), Day::new(51_545.25));
448    }
449
450    #[test]
451    fn display_invalid_interval_error() {
452        let e = InvalidIntervalError::StartAfterEnd;
453        assert!(e.to_string().contains("start"));
454    }
455
456    #[test]
457    fn display_period_list_errors() {
458        assert!(PeriodListError::InvalidInterval { index: 2 }
459            .to_string()
460            .contains("2"));
461        assert!(PeriodListError::Unsorted { index: 3 }
462            .to_string()
463            .contains("3"));
464        assert!(PeriodListError::Overlapping { index: 4 }
465            .to_string()
466            .contains("4"));
467    }
468
469    #[test]
470    fn normalize_empty_returns_empty() {
471        let result = Interval::<f64>::normalize(&[]);
472        assert!(result.is_empty());
473    }
474
475    #[test]
476    fn validate_detects_invalid_interval() {
477        // Interval::new does not validate; create one with start > end directly
478        let periods = vec![Interval::<f64> {
479            start: 5.0,
480            end: 1.0,
481        }];
482        assert_eq!(
483            Interval::validate(&periods),
484            Err(PeriodListError::InvalidInterval { index: 0 })
485        );
486    }
487
488    #[test]
489    fn validate_detects_unsorted() {
490        let periods = vec![
491            Interval::<f64>::new(5.0_f64, 8.0),
492            Interval::<f64>::new(1.0_f64, 4.0),
493        ];
494        assert_eq!(
495            Interval::validate(&periods),
496            Err(PeriodListError::Unsorted { index: 1 })
497        );
498    }
499
500    #[test]
501    fn checked_complement_rejects_invalid_inputs() {
502        let outer = Interval::<f64>::new(0.0_f64, 10.0);
503        let periods = vec![
504            Interval::<f64>::new(5.0_f64, 8.0),
505            Interval::<f64>::new(1.0_f64, 4.0),
506        ];
507        assert_eq!(
508            outer.try_complement(&periods),
509            Err(PeriodListError::Unsorted { index: 1 })
510        );
511
512        let invalid_outer = Interval::<f64>::new(10.0_f64, 0.0);
513        assert_eq!(
514            invalid_outer.try_complement(&[]),
515            Err(PeriodListError::InvalidInterval { index: 0 })
516        );
517    }
518
519    #[test]
520    fn checked_intersection_matches_unchecked_for_valid_inputs() {
521        let a = vec![Interval::<f64>::new(0.0_f64, 5.0)];
522        let b = vec![Interval::<f64>::new(3.0_f64, 7.0)];
523        assert_eq!(
524            Interval::try_intersect_many(&a, &b).unwrap(),
525            Interval::intersect_many(&a, &b)
526        );
527    }
528
529    #[test]
530    fn union_pair_overlapping() {
531        let a = Interval::<f64>::new(0.0_f64, 5.0);
532        let b = Interval::<f64>::new(3.0_f64, 8.0);
533        let u = a.union(&b);
534        assert_eq!(u.len(), 1);
535        assert_eq!(u[0], Interval::<f64>::new(0.0, 8.0));
536    }
537
538    #[test]
539    fn union_pair_disjoint() {
540        let a = Interval::<f64>::new(0.0_f64, 3.0);
541        let b = Interval::<f64>::new(5.0_f64, 8.0);
542        let u = a.union(&b);
543        assert_eq!(u.len(), 2);
544        assert_eq!(u[0], Interval::<f64>::new(0.0, 3.0));
545        assert_eq!(u[1], Interval::<f64>::new(5.0, 8.0));
546    }
547
548    #[test]
549    fn union_many_merges_two_lists() {
550        let a = vec![
551            Interval::<f64>::new(0.0_f64, 3.0),
552            Interval::<f64>::new(7.0, 9.0),
553        ];
554        let b = vec![Interval::<f64>::new(2.0_f64, 5.0)];
555        let u = Interval::union_many(&a, &b);
556        assert_eq!(u.len(), 2);
557        assert_eq!(u[0], Interval::<f64>::new(0.0, 5.0));
558        assert_eq!(u[1], Interval::<f64>::new(7.0, 9.0));
559    }
560
561    #[test]
562    fn display_formats_periods_via_endpoint_display() {
563        let mjd = Period::<TT>::new(
564            ModifiedJulianDate::<TT>::try_new(Day::new(51_544.5))
565                .unwrap()
566                .to_time(),
567            ModifiedJulianDate::<TT>::try_new(Day::new(51_545.25))
568                .unwrap()
569                .to_time(),
570        );
571
572        assert!(mjd.to_string().contains("TT"));
573    }
574
575    #[cfg(feature = "serde")]
576    #[test]
577    fn serde_roundtrips_period_shapes() {
578        let mjd = Period::<TT>::new(
579            ModifiedJulianDate::<TT>::try_new(Day::new(51_544.5))
580                .unwrap()
581                .to_time(),
582            ModifiedJulianDate::<TT>::try_new(Day::new(51_545.25))
583                .unwrap()
584                .to_time(),
585        );
586        let jd = Period::<TT>::new(
587            JulianDate::<TT>::try_new(Day::new(2_451_545.0))
588                .unwrap()
589                .to_time(),
590            JulianDate::<TT>::try_new(Day::new(2_451_546.0))
591                .unwrap()
592                .to_time(),
593        );
594        let native = Period::<TT>::new(
595            Time::<TT>::from_raw_j2000_seconds(qtty::Second::new(100.0)).unwrap(),
596            Time::<TT>::from_raw_j2000_seconds(qtty::Second::new(200.0)).unwrap(),
597        );
598
599        assert_eq!(
600            serde_json::to_value(mjd).unwrap(),
601            json!({"start": {"hi": 0.0, "lo": 0.0}, "end": {"hi": 64800.0, "lo": 0.0}})
602        );
603        assert_eq!(
604            serde_json::to_value(native).unwrap(),
605            json!({"start": {"hi": 100.0, "lo": 0.0}, "end": {"hi": 200.0, "lo": 0.0}})
606        );
607
608        assert_eq!(
609            serde_json::from_value::<Period<TT>>(json!({
610                "start": {"hi": 0.0, "lo": 0.0},
611                "end": {"hi": 64800.0, "lo": 0.0}
612            }))
613            .unwrap(),
614            mjd
615        );
616        assert_eq!(
617            serde_json::from_value::<Period<TT>>(json!({
618                "start": {"hi": 0.0, "lo": 0.0},
619                "end": {"hi": 86400.0, "lo": 0.0}
620            }))
621            .unwrap(),
622            jd
623        );
624        assert_eq!(
625            serde_json::from_value::<Period<TT>>(json!({
626                "start": {"hi": 100.0, "lo": 0.0},
627                "end": {"hi": 200.0, "lo": 0.0}
628            }))
629            .unwrap(),
630            native
631        );
632    }
633
634    #[cfg(feature = "serde")]
635    #[test]
636    fn serde_rejects_reversed_periods() {
637        let err = serde_json::from_value::<Period<TT>>(json!({
638            "start": {"hi": 10.0, "lo": 0.0},
639            "end": {"hi": 9.0, "lo": 0.0}
640        }))
641        .unwrap_err();
642        assert!(err.to_string().contains("start"));
643    }
644
645    #[cfg(feature = "serde")]
646    #[test]
647    fn serde_rejects_nonfinite_nested_time_values() {
648        let start = value::MapDeserializer::<_, value::Error>::new(
649            vec![
650                ("hi".into_deserializer(), f64::NAN.into_deserializer()),
651                ("lo".into_deserializer(), 0.0_f64.into_deserializer()),
652            ]
653            .into_iter(),
654        );
655        let end = value::MapDeserializer::<_, value::Error>::new(
656            vec![
657                ("hi".into_deserializer(), 5.0_f64.into_deserializer()),
658                ("lo".into_deserializer(), 0.0_f64.into_deserializer()),
659            ]
660            .into_iter(),
661        );
662        let entries = vec![
663            ("start".into_deserializer(), start),
664            ("end".into_deserializer(), end),
665        ];
666        let deserializer = value::MapDeserializer::<_, value::Error>::new(entries.into_iter());
667        let err = Period::<TT>::deserialize(deserializer).unwrap_err();
668        assert!(err.to_string().contains("finite"));
669    }
670}
tempoch_core/interval.rs

tempoch_core/
interval.rs
