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(¬_wraparound.inner), right)
433 } else {
434 (left, right.merge_interval(¬_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}