tempoch_core/period/
mod.rs

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

tempoch_core/period/
mod.rs
