Skip to main content

parquet_geospatial/
interval.rs

1// SPDX-License-Identifier: Apache-2.0
2// SPDX-FileCopyrightText: See the NOTICE file distributed with this work for additional information regarding copyright ownership
3// SPDX-FileContributor: Licensed to the Apache Software Foundation (ASF) under one or more contributor license agreements
4
5use arrow_schema::ArrowError;
6
7/// Generic 1D intervals with wraparound support
8///
9/// This trait specifies common behaviour implemented by the [Interval] and
10/// [WraparoundInterval].
11///
12/// Briefly, "wraparound" support was included in the Parquet specification
13/// to ensure that geometries or geographies with components on both sides of
14/// antimeridian (180 degrees longitude) can be reasonably summarized. This
15/// concept was borrowed from the widely used GeoJSON and matches identical
16/// bounding box specifications for GeoParquet and STAC, among others.
17///
18/// Because the Parquet specification also states that longitude values
19/// are always stored as `x` values (i.e., the first coordinate component),
20/// this contingency is only available for the `xmin`/`xmax` component of the
21/// GeoStatistics. Thus, the `xmin`/`xmax` pair may either represent a regular
22/// interval (specified by xmin = 10 and xmax = 20):
23///
24/// ```text
25///           10         20
26///            |==========|
27/// ```
28///
29/// ...or a "wraparound" interval (specified by xmin = 20 and xmax = 10). This
30/// interval is the union of the two regular intervals (-Inf, 10] and (20, Inf).
31/// Infinity was chosen rather than any particular value to ensure that Parquet
32/// implementations did not have to consider the value of the coordinate
33/// reference system when comparing intervals.
34///
35/// ```text
36///           10         20
37/// <==========|          |============>
38/// ```
39///
40/// In general, one should use [Interval] unless specifically working with
41/// wraparound, as the contingency of wraparound incurs overhead (particularly
42/// in a loop). This trait is mostly used to simplify testing and unify
43/// documentation for the two concrete implementations.
44pub trait IntervalTrait: std::fmt::Debug + PartialEq {
45    /// Create an interval from lo and hi values
46    fn new(lo: f64, hi: f64) -> Self;
47
48    /// Create an empty interval that intersects nothing (except the full interval)
49    fn empty() -> Self;
50
51    /// Create the full interval (that intersects everything, including the empty interval)
52    fn full() -> Self;
53
54    /// Lower bound
55    ///
56    /// If `is_wraparound()` returns false, this is also the minimum value. When empty,
57    /// this value is Infinity; when full, this value is -Infinity.
58    fn lo(&self) -> f64;
59
60    /// Upper bound
61    ///
62    /// If `is_wraparound()` returns false, this is also the maximum value. When empty,
63    /// this value is -Infinity; when full, this value is Infinity.
64    fn hi(&self) -> f64;
65
66    /// Check for wraparound
67    ///
68    /// If `is_wraparound()` returns false, this interval represents the values that are
69    /// between lo and hi. If `is_wraparound()` returns true, this interval represents
70    /// the values that are *not* between lo and hi.
71    ///
72    /// It is recommended to work directly with an [Interval] where this is guaranteed to
73    /// return false unless wraparound support is specifically required.
74    fn is_wraparound(&self) -> bool;
75
76    /// Check for potential intersection with a value
77    ///
78    /// Note that intervals always contain their endpoints (for both the wraparound and
79    /// non-wraparound case).
80    fn intersects_value(&self, value: f64) -> bool;
81
82    /// Check for potential intersection with an interval
83    ///
84    /// Note that intervals always contain their endpoints (for both the wraparound and
85    /// non-wraparound case).
86    ///
87    /// This method accepts Self for performance reasons to prevent unnecessary checking of
88    /// `is_wraparound()` when not required for an implementation.
89    fn intersects_interval(&self, other: &Self) -> bool;
90
91    /// Check for potential containment of an interval
92    ///
93    /// Note that intervals always contain their endpoints (for both the wraparound and
94    /// non-wraparound case).
95    ///
96    /// This method accepts Self for performance reasons to prevent unnecessary checking of
97    /// `is_wraparound()` when not required for an implementation.
98    fn contains_interval(&self, other: &Self) -> bool;
99
100    /// The width of the interval
101    ///
102    /// For the non-wraparound case, this is the distance between lo and hi. For the wraparound
103    /// case, this is infinity.
104    fn width(&self) -> f64;
105
106    /// The midpoint of the interval
107    ///
108    /// For the non-wraparound case, this is the point exactly between lo and hi. For the wraparound
109    /// case, this is arbitrarily chosen as infinity (to preserve the property that intervals intersect
110    /// their midpoint).
111    fn mid(&self) -> f64;
112
113    /// True if this interval is empty (i.e. intersects no values)
114    fn is_empty(&self) -> bool;
115
116    /// Compute a new interval that is the union of both
117    ///
118    /// When accumulating intervals in a loop, use [Interval::update_interval].
119    fn merge_interval(&self, other: &Self) -> Self;
120
121    /// Compute a new interval that is the union of both
122    ///
123    /// When accumulating intervals in a loop, use [Interval::update_value].
124    fn merge_value(&self, other: f64) -> Self;
125
126    /// Expand this interval by a given distance
127    ///
128    /// Returns a new interval where both endpoints are moved outward by the given distance.
129    /// For regular intervals, this expands both lo and hi by the distance.
130    /// For wraparound intervals, this may result in the full interval if expansion is large enough.
131    fn expand_by(&self, distance: f64) -> Self;
132}
133
134/// 1D Interval that never wraps around
135///
136/// Represents a minimum and maximum value without wraparound logic (see [WraparoundInterval]
137/// for a wraparound implementation).
138#[derive(Debug, Clone, Copy, PartialEq)]
139pub struct Interval {
140    /// Lower bound
141    lo: f64,
142
143    /// Upper bound
144    hi: f64,
145}
146
147impl Interval {
148    /// Expand this interval to the union of self and other in place
149    ///
150    /// Note that NaN values are ignored when updating bounds.
151    pub fn update_interval(&mut self, other: &Self) {
152        self.lo = self.lo.min(other.lo);
153        self.hi = self.hi.max(other.hi);
154    }
155
156    /// Expand this interval to the union of self and other in place
157    ///
158    /// Note that NaN values are ignored when updating bounds.
159    pub fn update_value(&mut self, other: f64) {
160        self.lo = self.lo.min(other);
161        self.hi = self.hi.max(other);
162    }
163}
164
165impl From<(f64, f64)> for Interval {
166    fn from(value: (f64, f64)) -> Self {
167        Interval::new(value.0, value.1)
168    }
169}
170
171impl From<(i32, i32)> for Interval {
172    fn from(value: (i32, i32)) -> Self {
173        Interval::new(value.0 as f64, value.1 as f64)
174    }
175}
176
177impl TryFrom<WraparoundInterval> for Interval {
178    type Error = ArrowError;
179
180    fn try_from(value: WraparoundInterval) -> Result<Self, Self::Error> {
181        if value.is_wraparound() {
182            Err(ArrowError::InvalidArgumentError(format!(
183                "Can't convert wraparound interval {value:?} to Interval"
184            )))
185        } else {
186            Ok(Interval::new(value.lo(), value.hi()))
187        }
188    }
189}
190
191impl IntervalTrait for Interval {
192    fn new(lo: f64, hi: f64) -> Self {
193        Self { lo, hi }
194    }
195
196    fn empty() -> Self {
197        Self {
198            lo: f64::INFINITY,
199            hi: -f64::INFINITY,
200        }
201    }
202
203    fn full() -> Self {
204        Self {
205            lo: -f64::INFINITY,
206            hi: f64::INFINITY,
207        }
208    }
209
210    fn lo(&self) -> f64 {
211        self.lo
212    }
213
214    fn hi(&self) -> f64 {
215        self.hi
216    }
217
218    fn is_wraparound(&self) -> bool {
219        false
220    }
221
222    fn intersects_value(&self, value: f64) -> bool {
223        value >= self.lo && value <= self.hi
224    }
225
226    fn intersects_interval(&self, other: &Self) -> bool {
227        self.lo <= other.hi && other.lo <= self.hi
228    }
229
230    fn contains_interval(&self, other: &Self) -> bool {
231        self.lo <= other.lo && self.hi >= other.hi
232    }
233
234    fn width(&self) -> f64 {
235        self.hi - self.lo
236    }
237
238    fn mid(&self) -> f64 {
239        self.lo + self.width() / 2.0
240    }
241
242    fn is_empty(&self) -> bool {
243        self.width() == -f64::INFINITY
244    }
245
246    fn merge_interval(&self, other: &Self) -> Self {
247        let mut out = *self;
248        out.update_interval(other);
249        out
250    }
251
252    fn merge_value(&self, other: f64) -> Self {
253        let mut out = *self;
254        out.update_value(other);
255        out
256    }
257
258    fn expand_by(&self, distance: f64) -> Self {
259        if self.is_empty() || distance.is_nan() || distance < 0.0 {
260            return *self;
261        }
262
263        Self::new(self.lo - distance, self.hi + distance)
264    }
265}
266
267/// 1D Interval that may or may not wrap around
268///
269/// Concrete implementation that handles both the wraparound and regular
270/// interval case. This is separated from the [Interval] because the
271/// [Interval] is faster and most operations will use it directly (invoking
272/// this struct when it is specifically required).
273#[derive(Debug, Clone, Copy, PartialEq)]
274pub struct WraparoundInterval {
275    inner: Interval,
276}
277
278impl WraparoundInterval {
279    /// Splits this interval into exactly two non-wraparound intervals
280    ///
281    /// If this interval does not wrap around, one of these intervals will
282    /// be empty.
283    fn split(&self) -> (Interval, Interval) {
284        if self.is_wraparound() {
285            (
286                Interval {
287                    lo: -f64::INFINITY,
288                    hi: self.inner.hi,
289                },
290                Interval {
291                    lo: self.inner.lo,
292                    hi: f64::INFINITY,
293                },
294            )
295        } else {
296            (self.inner, Interval::empty())
297        }
298    }
299}
300
301impl From<(f64, f64)> for WraparoundInterval {
302    fn from(value: (f64, f64)) -> Self {
303        WraparoundInterval::new(value.0, value.1)
304    }
305}
306
307impl From<(i32, i32)> for WraparoundInterval {
308    fn from(value: (i32, i32)) -> Self {
309        WraparoundInterval::new(value.0 as f64, value.1 as f64)
310    }
311}
312
313impl From<Interval> for WraparoundInterval {
314    fn from(value: Interval) -> Self {
315        WraparoundInterval::new(value.lo(), value.hi())
316    }
317}
318
319impl IntervalTrait for WraparoundInterval {
320    fn new(lo: f64, hi: f64) -> Self {
321        Self {
322            inner: Interval::new(lo, hi),
323        }
324    }
325
326    fn empty() -> Self {
327        Self {
328            inner: Interval::empty(),
329        }
330    }
331
332    fn full() -> Self {
333        Self {
334            inner: Interval::full(),
335        }
336    }
337
338    fn lo(&self) -> f64 {
339        self.inner.lo
340    }
341
342    fn hi(&self) -> f64 {
343        self.inner.hi
344    }
345
346    fn is_wraparound(&self) -> bool {
347        !self.is_empty() && self.inner.width() < 0.0
348    }
349
350    fn intersects_value(&self, value: f64) -> bool {
351        let (left, right) = self.split();
352        left.intersects_value(value) || right.intersects_value(value)
353    }
354
355    fn intersects_interval(&self, other: &Self) -> bool {
356        let (left, right) = self.split();
357        let (other_left, other_right) = other.split();
358        left.intersects_interval(&other_left)
359            || left.intersects_interval(&other_right)
360            || right.intersects_interval(&other_left)
361            || right.intersects_interval(&other_right)
362    }
363
364    fn contains_interval(&self, other: &Self) -> bool {
365        let (left, right) = self.split();
366        let (other_left, other_right) = other.split();
367        left.contains_interval(&other_left) && right.contains_interval(&other_right)
368    }
369
370    fn width(&self) -> f64 {
371        if self.is_wraparound() {
372            f64::INFINITY
373        } else {
374            self.inner.width()
375        }
376    }
377
378    fn mid(&self) -> f64 {
379        if self.is_wraparound() {
380            f64::INFINITY
381        } else {
382            self.inner.mid()
383        }
384    }
385
386    fn is_empty(&self) -> bool {
387        self.inner.is_empty()
388    }
389
390    fn merge_interval(&self, other: &Self) -> Self {
391        if self.is_empty() {
392            return *other;
393        }
394
395        if other.is_empty() {
396            return *self;
397        }
398
399        let (wraparound, not_wraparound) = match (self.is_wraparound(), other.is_wraparound()) {
400            // Handle wraparound/not wraparound below
401            (true, false) => (self, other),
402            (false, true) => (other, self),
403            // Both are wraparound: Merge the two left intervals, then merge the two right intervals
404            // and check if we need the full interval
405            (true, true) => {
406                let (left, right) = self.split();
407                let (other_left, other_right) = other.split();
408
409                let new_left = left.merge_interval(&other_left);
410                let new_right = right.merge_interval(&other_right);
411
412                // If the left and right intervals intersect each other, we need the full interval
413                return if new_left.intersects_interval(&new_right) {
414                    WraparoundInterval::full()
415                } else {
416                    WraparoundInterval::new(new_right.lo(), new_left.hi())
417                };
418            }
419            // Neither are wraparound: just merge the inner intervals
420            (false, false) => {
421                return Self {
422                    inner: self.inner.merge_interval(&other.inner),
423                };
424            }
425        };
426
427        let (left, right) = wraparound.split();
428        let distance_not_wraparound_left = (not_wraparound.mid() - left.hi()).abs();
429        let distance_not_wraparound_right = (not_wraparound.mid() - right.lo()).abs();
430        let (new_left, new_right) = if distance_not_wraparound_left < distance_not_wraparound_right
431        {
432            (left.merge_interval(&not_wraparound.inner), right)
433        } else {
434            (left, right.merge_interval(&not_wraparound.inner))
435        };
436
437        // If the left and right intervals intersect each other, we need the full interval
438        if new_left.intersects_interval(&new_right) {
439            WraparoundInterval::full()
440        } else {
441            WraparoundInterval::new(new_right.lo(), new_left.hi())
442        }
443    }
444
445    fn merge_value(&self, value: f64) -> Self {
446        if self.intersects_value(value) || value.is_nan() {
447            return *self;
448        }
449
450        if !self.is_wraparound() {
451            return Self {
452                inner: self.inner.merge_value(value),
453            };
454        }
455
456        // Move only one of the endpoints
457        let distance_left = value - self.inner.hi;
458        let distance_right = self.inner.lo - value;
459        debug_assert!(distance_left > 0.0);
460        debug_assert!(distance_right > 0.0);
461        if distance_left < distance_right {
462            Self {
463                inner: Interval {
464                    lo: self.inner.lo,
465                    hi: value,
466                },
467            }
468        } else {
469            Self {
470                inner: Interval {
471                    lo: value,
472                    hi: self.inner.hi,
473                },
474            }
475        }
476    }
477
478    fn expand_by(&self, distance: f64) -> Self {
479        if self.is_empty() || distance.is_nan() || distance < 0.0 {
480            return *self;
481        }
482
483        if !self.is_wraparound() {
484            // For non-wraparound, just expand the inner interval
485            return Self {
486                inner: self.inner.expand_by(distance),
487            };
488        }
489
490        // For wraparound intervals, expanding means including more values
491        // Wraparound interval (a, b) where a > b excludes the region (b, a)
492        // To expand by distance d, we shrink the excluded region from (b, a) to (b+d, a-d)
493        // This means the new wraparound interval becomes (a-d, b+d)
494        let excluded_lo = self.inner.hi + distance; // b + d
495        let excluded_hi = self.inner.lo - distance; // a - d
496
497        // If the excluded region disappears (excluded_lo >= excluded_hi), we get the full interval
498        if excluded_lo >= excluded_hi {
499            return Self::full();
500        }
501
502        // The new wraparound interval excludes (excluded_lo, excluded_hi)
503        // So the interval itself is (excluded_hi, excluded_lo)
504        Self::new(excluded_hi, excluded_lo)
505    }
506}
507
508#[cfg(test)]
509mod test {
510    use super::*;
511
512    fn test_empty<T: IntervalTrait>(empty: T) {
513        // Equals itself
514        #[expect(clippy::eq_op)]
515        {
516            assert_eq!(empty, empty);
517        }
518
519        // Empty intersects no values
520        assert!(!empty.intersects_value(0.0));
521        assert!(!empty.intersects_value(f64::INFINITY));
522        assert!(!empty.intersects_value(-f64::INFINITY));
523        assert!(!empty.intersects_value(f64::NAN));
524
525        // Empty intersects no intervals
526        assert!(!empty.intersects_interval(&T::new(-10.0, 10.0)));
527        assert!(!empty.intersects_interval(&T::empty()));
528
529        // ...except the full interval
530        assert!(empty.intersects_interval(&T::full()));
531
532        // Empty contains no intervals
533        assert!(!empty.contains_interval(&T::new(-10.0, 10.0)));
534        assert!(!empty.contains_interval(&T::full()));
535
536        // ...except empty itself (empty set is subset of itself)
537        assert!(empty.contains_interval(&T::empty()));
538
539        // Merging NaN is still empty
540        assert_eq!(empty.merge_value(f64::NAN), empty);
541
542        // Merging an empty interval results in an empty interval
543        assert_eq!(empty.merge_interval(&empty), empty);
544
545        // Merging a value results in a interval with equal lo/hi
546        assert_eq!(empty.merge_value(12.0), T::new(12.0, 12.0));
547
548        // Merging a non-empty interval results in the other interval
549        assert_eq!(
550            empty.merge_interval(&T::new(10.0, 20.0)),
551            T::new(10.0, 20.0)
552        );
553
554        // Expanding empty interval keeps it empty
555        assert_eq!(empty.expand_by(5.0), empty);
556        assert_eq!(empty.expand_by(0.0), empty);
557        assert_eq!(empty.expand_by(-1.0), empty);
558        assert_eq!(empty.expand_by(f64::NAN), empty);
559    }
560
561    #[test]
562    fn interval_empty() {
563        let empty = Interval::empty();
564        test_empty(empty);
565    }
566
567    #[test]
568    fn wraparound_interval_empty() {
569        let empty = WraparoundInterval::empty();
570
571        // Should pass all the regular interval tests
572        test_empty(empty);
573
574        // Empty shouldn't be treated as wraparound
575        assert!(!empty.is_wraparound());
576
577        // When merging an interval where the other one is a
578        // wraparound, we should get the other interval
579        assert_eq!(
580            empty.merge_interval(&WraparoundInterval::new(20.0, 10.0)),
581            WraparoundInterval::new(20.0, 10.0)
582        );
583    }
584
585    fn test_finite<T: IntervalTrait>(finite: T) {
586        // Check accessors
587        assert_eq!(finite.lo(), 10.0);
588        assert_eq!(finite.hi(), 20.0);
589        assert_eq!(finite.mid(), 15.0);
590        assert_eq!(finite.width(), 10.0);
591        assert!(!finite.is_wraparound());
592        assert!(!finite.is_empty());
593
594        // Intersects endpoints and midpoint
595        assert!(finite.intersects_value(10.0));
596        assert!(finite.intersects_value(15.0));
597        assert!(finite.intersects_value(20.0));
598
599        // Doesn't intersect infinite values, NaN, or finite values outside
600        // the range
601        assert!(!finite.intersects_value(0.0));
602        assert!(!finite.intersects_value(f64::INFINITY));
603        assert!(!finite.intersects_value(-f64::INFINITY));
604        assert!(!finite.intersects_value(f64::NAN));
605
606        // Intervals that intersect
607        assert!(finite.intersects_interval(&T::new(14.0, 16.0)));
608        assert!(finite.intersects_interval(&T::new(5.0, 15.0)));
609        assert!(finite.intersects_interval(&T::new(15.0, 25.0)));
610        assert!(finite.intersects_interval(&T::new(5.0, 25.0)));
611        assert!(finite.intersects_interval(&T::full()));
612
613        // Barely touching ones count
614        assert!(finite.intersects_interval(&T::new(5.0, 10.0)));
615        assert!(finite.intersects_interval(&T::new(20.0, 25.0)));
616
617        // Intervals that don't intersect
618        assert!(!finite.intersects_interval(&T::new(0.0, 5.0)));
619        assert!(!finite.intersects_interval(&T::new(25.0, 30.0)));
620        assert!(!finite.intersects_interval(&T::empty()));
621
622        // Intervals that are contained
623        assert!(finite.contains_interval(&T::new(14.0, 16.0)));
624        assert!(finite.contains_interval(&T::new(10.0, 15.0)));
625        assert!(finite.contains_interval(&T::new(15.0, 20.0)));
626        assert!(finite.contains_interval(&T::new(10.0, 20.0))); // itself
627        assert!(finite.contains_interval(&T::empty()));
628
629        // Intervals that are not contained
630        assert!(!finite.contains_interval(&T::new(5.0, 15.0))); // extends below
631        assert!(!finite.contains_interval(&T::new(15.0, 25.0))); // extends above
632        assert!(!finite.contains_interval(&T::new(5.0, 25.0))); // extends both ways
633        assert!(!finite.contains_interval(&T::new(0.0, 5.0))); // completely below
634        assert!(!finite.contains_interval(&T::new(25.0, 30.0))); // completely above
635        assert!(!finite.contains_interval(&T::full())); // full interval is larger
636
637        // Merging NaN
638        assert_eq!(finite.merge_value(f64::NAN), finite);
639
640        // Merging Infinities
641        assert_eq!(
642            finite.merge_value(f64::INFINITY),
643            T::new(finite.lo(), f64::INFINITY)
644        );
645        assert_eq!(
646            finite.merge_value(-f64::INFINITY),
647            T::new(-f64::INFINITY, finite.hi())
648        );
649
650        // Merging a value within the interval
651        assert_eq!(finite.merge_value(15.0), finite);
652
653        // Merging a value above
654        assert_eq!(finite.merge_value(25.0), T::new(10.0, 25.0));
655
656        // Merging a value below
657        assert_eq!(finite.merge_value(5.0), T::new(5.0, 20.0));
658
659        // Merging an empty interval
660        assert_eq!(finite.merge_interval(&T::empty()), finite);
661
662        // Merging an interval with itself
663        assert_eq!(finite.merge_interval(&finite), finite);
664
665        // Merging an interval with the full interval
666        assert_eq!(finite.merge_interval(&T::full()), T::full());
667
668        // Merging an interval within the interval
669        assert_eq!(finite.merge_interval(&T::new(14.0, 16.0)), finite);
670
671        // Merging a partially overlapping interval below
672        assert_eq!(finite.merge_interval(&T::new(5.0, 15.0)), T::new(5.0, 20.0));
673
674        // Merging a partially overlapping interval above
675        assert_eq!(
676            finite.merge_interval(&T::new(15.0, 25.0)),
677            T::new(10.0, 25.0)
678        );
679
680        // Merging a disjoint interval below
681        assert_eq!(finite.merge_interval(&T::new(0.0, 5.0)), T::new(0.0, 20.0));
682
683        // Merging a disjoint interval above
684        assert_eq!(
685            finite.merge_interval(&T::new(25.0, 30.0)),
686            T::new(10.0, 30.0)
687        );
688
689        // Expanding by positive distance
690        assert_eq!(finite.expand_by(2.0), T::new(8.0, 22.0));
691        assert_eq!(finite.expand_by(5.0), T::new(5.0, 25.0));
692
693        // Expanding by zero does nothing
694        assert_eq!(finite.expand_by(0.0), finite);
695
696        // Expanding by negative distance does nothing
697        assert_eq!(finite.expand_by(-1.0), finite);
698
699        // Expanding by NaN does nothing
700        assert_eq!(finite.expand_by(f64::NAN), finite);
701    }
702
703    #[test]
704    fn interval_finite() {
705        let finite = Interval::new(10.0, 20.0);
706        test_finite(finite);
707    }
708
709    #[test]
710    fn wraparound_interval_finite() {
711        let finite = WraparoundInterval::new(10.0, 20.0);
712        test_finite(finite);
713
714        // Convert to an Interval
715        let interval: Interval = finite.try_into().unwrap();
716        assert_eq!(interval, Interval::new(10.0, 20.0));
717    }
718
719    #[test]
720    fn wraparound_interval_actually_wraparound_accessors() {
721        // Everything *except* the interval (10, 20)
722        let wraparound = WraparoundInterval::new(20.0, 10.0);
723        assert!(wraparound.is_wraparound());
724        assert!(!wraparound.is_empty());
725        assert_eq!(wraparound.mid(), f64::INFINITY);
726    }
727
728    #[test]
729    fn wraparound_interval_actually_wraparound_intersects_value() {
730        // Everything *except* the interval (10, 20)
731        let wraparound = WraparoundInterval::new(20.0, 10.0);
732
733        // Intersects endpoints but not a point between them
734        assert!(wraparound.intersects_value(10.0));
735        assert!(wraparound.intersects_value(20.0));
736        assert!(!wraparound.intersects_value(15.0));
737
738        // Intersects positive and negative infinity
739        assert!(wraparound.intersects_value(f64::INFINITY));
740        assert!(wraparound.intersects_value(-f64::INFINITY));
741
742        // ...but not NaN
743        assert!(!wraparound.intersects_value(f64::NAN));
744    }
745
746    #[test]
747    fn wraparound_interval_actually_wraparound_intersects_interval() {
748        // Everything *except* the interval (10, 20)
749        let wraparound = WraparoundInterval::new(20.0, 10.0);
750
751        // Intersects itself
752        assert!(wraparound.intersects_interval(&wraparound));
753
754        // Intersects the full interval
755        assert!(wraparound.intersects_interval(&WraparoundInterval::full()));
756
757        // Interval completely between endpoints doesn't intersect
758        assert!(!wraparound.intersects_interval(&WraparoundInterval::new(14.0, 16.0)));
759        // ...unless it's also wraparound
760        assert!(wraparound.intersects_interval(&WraparoundInterval::new(16.0, 14.0)));
761
762        // Intervals overlapping endpoints intersect whether the are or aren't wraparound
763        assert!(wraparound.intersects_interval(&WraparoundInterval::new(5.0, 15.0)));
764        assert!(wraparound.intersects_interval(&WraparoundInterval::new(15.0, 5.0)));
765        assert!(wraparound.intersects_interval(&WraparoundInterval::new(15.0, 25.0)));
766        assert!(wraparound.intersects_interval(&WraparoundInterval::new(25.0, 15.0)));
767
768        // Barely touching ones still intersect whether the are or aren't wraparound
769        assert!(wraparound.intersects_interval(&WraparoundInterval::new(5.0, 10.0)));
770        assert!(wraparound.intersects_interval(&WraparoundInterval::new(10.0, 5.0)));
771        assert!(wraparound.intersects_interval(&WraparoundInterval::new(20.0, 25.0)));
772        assert!(wraparound.intersects_interval(&WraparoundInterval::new(25.0, 20.0)));
773
774        // Intervals completely above and below endpoints do intersect whether they
775        // are or aren't wraparound
776        assert!(wraparound.intersects_interval(&WraparoundInterval::new(0.0, 5.0)));
777        assert!(wraparound.intersects_interval(&WraparoundInterval::new(5.0, 0.0)));
778        assert!(wraparound.intersects_interval(&WraparoundInterval::new(25.0, 30.0)));
779        assert!(wraparound.intersects_interval(&WraparoundInterval::new(30.0, 25.0)));
780    }
781
782    #[test]
783    fn wraparound_interval_actually_wraparound_contains_interval() {
784        // Everything *except* the interval (10, 20)
785        let wraparound = WraparoundInterval::new(20.0, 10.0);
786
787        // Contains itself
788        assert!(wraparound.contains_interval(&wraparound));
789
790        // Empty is contained by everything
791        assert!(wraparound.contains_interval(&WraparoundInterval::empty()));
792
793        // Does not contain the full interval
794        assert!(!wraparound.contains_interval(&WraparoundInterval::full()));
795
796        // Regular interval completely between endpoints is not contained
797        assert!(!wraparound.contains_interval(&WraparoundInterval::new(14.0, 16.0)));
798
799        // Wraparound intervals that exclude more (narrower included regions) are contained
800        assert!(wraparound.contains_interval(&WraparoundInterval::new(22.0, 8.0))); // excludes (8,22) which is larger than (10,20)
801        assert!(!wraparound.contains_interval(&WraparoundInterval::new(18.0, 12.0))); // excludes (12,18) which is smaller than (10,20)
802
803        // Regular intervals don't work the same way due to the split logic
804        // For a regular interval (a, b), split gives (left=(a,b), right=empty)
805        // For wraparound to contain it, we need both parts to be contained
806        // This means (-inf, 10] must contain (a,b) AND [20, inf) must contain empty
807        // The second is always true, but the first requires b <= 10
808        assert!(wraparound.contains_interval(&WraparoundInterval::new(0.0, 5.0))); // completely within left part
809        assert!(wraparound.contains_interval(&WraparoundInterval::new(-5.0, 10.0))); // fits in left part
810        assert!(!wraparound.contains_interval(&WraparoundInterval::new(25.0, 30.0))); // doesn't fit in left part
811        assert!(!wraparound.contains_interval(&WraparoundInterval::new(20.0, 25.0))); // doesn't fit in left part
812
813        // Regular intervals that overlap the excluded zone are not contained
814        assert!(!wraparound.contains_interval(&WraparoundInterval::new(5.0, 15.0))); // overlaps excluded zone
815        assert!(!wraparound.contains_interval(&WraparoundInterval::new(15.0, 25.0))); // overlaps excluded zone
816
817        // Wraparound intervals that exclude less (wider included regions) are not contained
818        assert!(!wraparound.contains_interval(&WraparoundInterval::new(15.0, 5.0))); // excludes (5,15) which is smaller
819        assert!(!wraparound.contains_interval(&WraparoundInterval::new(25.0, 15.0)));
820        // excludes (15,25) which is smaller
821    }
822
823    #[test]
824    fn wraparound_interval_actually_wraparound_merge_value() {
825        // Everything *except* the interval (10, 20)
826        let wraparound = WraparoundInterval::new(20.0, 10.0);
827
828        // Merging NaN
829        assert_eq!(wraparound.merge_value(f64::NAN), wraparound);
830
831        // Merging a value closer to the left endpoint should move
832        // that endpoint
833        assert_eq!(
834            wraparound.merge_value(12.0),
835            WraparoundInterval::new(20.0, 12.0)
836        );
837
838        // Merging a value closer to the right endpoint should move
839        // that endpoint
840        assert_eq!(
841            wraparound.merge_value(18.0),
842            WraparoundInterval::new(18.0, 10.0)
843        );
844
845        // Merging a value that is already intersecting shouldn't change the interval
846        assert_eq!(wraparound.merge_value(5.0), wraparound);
847        assert_eq!(wraparound.merge_value(10.0), wraparound);
848        assert_eq!(wraparound.merge_value(20.0), wraparound);
849        assert_eq!(wraparound.merge_value(25.0), wraparound);
850    }
851
852    #[test]
853    fn wraparound_interval_actually_wraparound_merge_interval() {
854        // Everything *except* the interval (10, 20)
855        let wraparound = WraparoundInterval::new(20.0, 10.0);
856
857        // Merging an empty interval
858        assert_eq!(
859            wraparound.merge_interval(&WraparoundInterval::empty()),
860            wraparound
861        );
862
863        // Merging an interval with itself
864        assert_eq!(wraparound.merge_interval(&wraparound), wraparound);
865
866        // Merging a wraparound interval with a "larger" wraparound interval
867        //           10         20
868        // <==========|          |============>
869        // <==============|  |================>
870        //               14  16
871        assert_eq!(
872            wraparound.merge_interval(&WraparoundInterval::new(16.0, 14.0)),
873            WraparoundInterval::new(16.0, 14.0)
874        );
875
876        // Merging a wraparound interval with a "smaller" wraparound interval
877        //           10         20
878        // <==========|          |============>
879        // <=====|                    |=======>
880        //       5                    25
881        // <==========|          |============>
882        assert_eq!(
883            wraparound.merge_interval(&WraparoundInterval::new(25.0, 5.0)),
884            wraparound
885        );
886
887        // Merge with partially intersecting wraparounds
888        //           10         20
889        // <==========|          |============>
890        // <=====|          |=================>
891        //       5          15
892        // <==========|     |=================>
893        assert_eq!(
894            wraparound.merge_interval(&WraparoundInterval::new(15.0, 5.0)),
895            WraparoundInterval::new(15.0, 10.0)
896        );
897
898        //           10         20
899        // <==========|          |============>
900        // <================|          |======>
901        //                  15         25
902        // <================|    |============>
903        assert_eq!(
904            wraparound.merge_interval(&WraparoundInterval::new(25.0, 15.0)),
905            WraparoundInterval::new(20.0, 15.0)
906        );
907
908        // Merge wraparound with wraparound whose union is the full interval
909        //           10         20
910        // <==========|          |=========================>
911        // <=============================|          |======>
912        //                               25         30
913        // <===============================================>
914        assert_eq!(
915            wraparound.merge_interval(&WraparoundInterval::new(30.0, 25.0)),
916            WraparoundInterval::full()
917        );
918
919        //                    10         20
920        // <===================|          |================>
921        // <==|          |=================================>
922        //    0          5
923        // <===============================================>
924        assert_eq!(
925            wraparound.merge_interval(&WraparoundInterval::new(5.0, 0.0)),
926            WraparoundInterval::full()
927        );
928
929        // Merge wraparound with a regular interval completely contained by the original
930        //                  10         20
931        // <=================|          |==================>
932        //                                   |=========|
933        //                                  25         30
934        // <=================|          |==================>
935        assert_eq!(
936            wraparound.merge_interval(&WraparoundInterval::new(25.0, 30.0)),
937            wraparound
938        );
939
940        //                  10         20
941        // <=================|          |==================>
942        //  |=========|
943        //  0         5
944        // <=================|          |==================>
945        assert_eq!(
946            wraparound.merge_interval(&WraparoundInterval::new(0.0, 5.0)),
947            wraparound
948        );
949
950        // Merge wraparound with a partially intersecting regular interval that
951        // should extend the left side
952        //                  10         20
953        // <=================|          |==================>
954        //              |=========|
955        //              5         15
956        // <======================|     |==================>
957        assert_eq!(
958            wraparound.merge_interval(&WraparoundInterval::new(5.0, 15.0)),
959            WraparoundInterval::new(20.0, 15.0)
960        );
961
962        // Merge wraparound with a partially intersecting regular interval that
963        // should extend the right side
964        //                  10         20
965        // <=================|          |==================>
966        //                         |=========|
967        //                         15        25
968        // <=================|     |==================>
969        assert_eq!(
970            wraparound.merge_interval(&WraparoundInterval::new(15.0, 25.0)),
971            WraparoundInterval::new(15.0, 10.0)
972        );
973
974        // Merge wraparound with a disjoint regular interval that should extend the left side
975        //                  10         20
976        // <=================|          |==================>
977        //                     |==|
978        //                    12  15
979        // <======================|     |==================>
980        assert_eq!(
981            wraparound.merge_interval(&WraparoundInterval::new(12.0, 15.0)),
982            WraparoundInterval::new(20.0, 15.0)
983        );
984
985        // Merge wraparound with a disjoint regular interval that should extend the right side
986        //                  10         20
987        // <=================|          |==================>
988        //                         |==|
989        //                        15  18
990        // <=================|     |==================>
991        assert_eq!(
992            wraparound.merge_interval(&WraparoundInterval::new(15.0, 18.0)),
993            WraparoundInterval::new(15.0, 10.0)
994        );
995    }
996
997    #[test]
998    fn wraparound_interval_actually_wraparound_expand_by() {
999        // Everything *except* the interval (10, 20)
1000        let wraparound = WraparoundInterval::new(20.0, 10.0);
1001
1002        // Expanding by a small amount shrinks the excluded region
1003        // Original excludes (10, 20), expanding by 2 should exclude (12, 18)
1004        // So the new interval should be (18, 12) = everything except (12, 18)
1005        assert_eq!(
1006            wraparound.expand_by(2.0),
1007            WraparoundInterval::new(18.0, 12.0)
1008        ); // now excludes (12, 18)
1009
1010        // Expanding by 4 should exclude (14, 16)
1011        assert_eq!(
1012            wraparound.expand_by(4.0),
1013            WraparoundInterval::new(16.0, 14.0)
1014        ); // now excludes (14, 16)
1015
1016        // Expanding by 5.0 should exactly eliminate the excluded region
1017        // excluded region (10, 20) shrinks to (15, 15) which is empty
1018        assert_eq!(wraparound.expand_by(5.0), WraparoundInterval::full()); // excluded region disappears
1019
1020        // Any expansion greater than 5.0 should also give full interval
1021        assert_eq!(wraparound.expand_by(6.0), WraparoundInterval::full());
1022
1023        assert_eq!(wraparound.expand_by(100.0), WraparoundInterval::full());
1024
1025        // Expanding by zero does nothing
1026        assert_eq!(wraparound.expand_by(0.0), wraparound);
1027
1028        // Expanding by negative distance does nothing
1029        assert_eq!(wraparound.expand_by(-1.0), wraparound);
1030
1031        // Expanding by NaN does nothing
1032        assert_eq!(wraparound.expand_by(f64::NAN), wraparound);
1033
1034        // Test a finite (non-wraparound) wraparound interval
1035        let non_wraparound = WraparoundInterval::new(10.0, 20.0);
1036        assert!(!non_wraparound.is_wraparound());
1037        assert_eq!(
1038            non_wraparound.expand_by(2.0),
1039            WraparoundInterval::new(8.0, 22.0)
1040        );
1041
1042        // Test another wraparound case - excludes (5, 15) with width 10
1043        let wraparound2 = WraparoundInterval::new(15.0, 5.0);
1044        // Expanding by 3 should shrink excluded region from (5, 15) to (8, 12)
1045        assert_eq!(
1046            wraparound2.expand_by(3.0),
1047            WraparoundInterval::new(12.0, 8.0)
1048        );
1049
1050        // Expanding by 5 should make excluded region disappear: (5+5, 15-5) = (10, 10)
1051        assert_eq!(wraparound2.expand_by(5.0), WraparoundInterval::full());
1052    }
1053
1054    #[test]
1055    fn wraparound_interval_actually_wraparound_convert() {
1056        // Everything *except* the interval (10, 20)
1057        let wraparound = WraparoundInterval::new(20.0, 10.0);
1058
1059        // Can't convert a wraparound interval that actually wraps around to an Interval
1060        let err = Interval::try_from(wraparound).unwrap_err();
1061        assert!(
1062            err.to_string()
1063                .contains("Can't convert wraparound interval")
1064        );
1065    }
1066}