inari/overlap.rs
1use crate::interval::*;
2
3/// The overlapping state between intervals, returned by [`Interval::overlap`].
4///
5/// # Quick Reference
6///
7/// `self` relative to `rhs`:
8///
9/// ```text
10/// rhs
11/// c d
12/// •———————•
13/// ┌─ a b : :
14/// │ B •———• : :
15/// │ M •———• : rhs
16/// │ O •———• : c=d
17/// │ S •———• : •
18/// │ S • : ┌─ a b :
19/// │ Cb : •———• : │ B •———• :
20/// │ : •———• F │ • E
21/// self │ : • F self │ •———• Fb
22/// │ •———————• E │ •———• C
23/// │ •—————————• Fb │ •———• Sb
24/// │ •———————————• C │ : •———• A
25/// │ •—————————• Sb └─ : a b
26/// │ : •———• Ob •
27/// │ : •———• Mb c=d
28/// │ : : •———• A
29/// └─ : : a b
30/// •———————•
31/// c d
32/// ```
33///
34/// `rhs` relative to `self`:
35///
36/// ```text
37/// self
38/// a b
39/// •———————•
40/// ┌─ : : c d
41/// │ : : •———• B
42/// │ : •———• M self
43/// │ : •———• O a=b
44/// │ •—————————• S •
45/// │ •———————————• Cb ┌─ : c d
46/// │ •—————————• F │ : •———• B
47/// │ •———————• E │ •———• S
48/// rhs │ : •———• Fb rhs │ •———• Cb
49/// │ : • Fb │ •———• F
50/// │ C : •———• : │ • E
51/// │ Sb •———• : │ A •———• :
52/// │ Sb • : └─ c d :
53/// │ Ob •———• : •
54/// │ Mb •———• : a=b
55/// │ A •———• : :
56/// └─ c d : :
57/// •———————•
58/// a b
59/// ```
60#[derive(Clone, Copy, Debug, Eq, Hash, PartialEq)]
61pub enum Overlap {
62 /// Both `self` and `rhs` are empty.
63 ///
64 /// Equivalently, $\self = \rhs = ∅$.
65 BothEmpty,
66
67 /// `self` is empty while `rhs` is not.
68 ///
69 /// Equivalently, $\self = ∅ ∧ \rhs ≠ ∅$.
70 FirstEmpty,
71
72 /// `rhs` is empty while `self` is not.
73 ///
74 /// Equivalently, $\self ≠ ∅ ∧ \rhs = ∅$.
75 SecondEmpty,
76
77 /// Both $\self = \[a, b\]$ and $rhs = \[c, d\]$ are nonempty and $b < c$.
78 ///
79 /// Equivalently,
80 ///
81 /// $$
82 /// \self ≠ ∅ ∧ \rhs ≠ ∅ ∧ ∀x ∈ \self, ∀y ∈ \rhs : x < y.
83 /// $$
84 ///
85 /// ```text
86 /// a b
87 /// self: •——————•
88 /// rhs: •——————•
89 /// c d
90 /// ```
91 ///
92 /// Inverse: [`Overlap::After`].
93 Before,
94
95 /// Both $\self = \[a, b\]$ and $rhs = \[c, d\]$ are nonempty and $a < b ∧ b = c ∧ c < d$.
96 ///
97 /// Equivalently,
98 ///
99 ///
100 /// $$
101 /// \begin{align*}
102 /// \self ≠ ∅ ∧ \rhs ≠ ∅
103 /// &∧ ∀x ∈ \self, ∀y ∈ \rhs : x ≤ y \\\\
104 /// &∧ ∃x ∈ \self, ∀y ∈ \rhs : x < y \\\\
105 /// &∧ ∃x ∈ \self, ∃y ∈ \rhs : x = y.
106 /// \end{align*}
107 /// $$
108 ///
109 /// ```text
110 /// a b
111 /// self: •——————•
112 /// rhs: •——————•
113 /// c d
114 /// ```
115 ///
116 /// Inverse: [`Overlap::MetBy`].
117 Meets,
118
119 /// Both $\self = \[a, b\]$ and $rhs = \[c, d\]$ are nonempty and $a < c ∧ c < b ∧ b < d$.
120 ///
121 /// Equivalently,
122 ///
123 /// $$
124 /// \begin{align*}
125 /// \self ≠ ∅ ∧ \rhs ≠ ∅
126 /// &∧ ∃x ∈ \self, ∀y ∈ \rhs : x < y \\\\
127 /// &∧ ∃y ∈ \rhs, ∀x ∈ \self : x < y \\\\
128 /// &∧ ∃x ∈ \self, ∃y ∈ \rhs : y < x.
129 /// \end{align*}
130 /// $$
131 ///
132 /// ```text
133 /// a b
134 /// self: •——————•
135 /// rhs: •——————•
136 /// c d
137 /// ```
138 ///
139 /// Inverse: [`Overlap::OverlappedBy`].
140 Overlaps,
141
142 /// Both $\self = \[a, b\]$ and $rhs = \[c, d\]$ are nonempty and $a = c ∧ b < d$.
143 ///
144 /// Equivalently,
145 ///
146 /// $$
147 /// \begin{align*}
148 /// \self ≠ ∅ ∧ \rhs ≠ ∅
149 /// &∧ ∀y ∈ \rhs, ∃x ∈ \self : x ≤ y \\\\
150 /// &∧ ∀x ∈ \self, ∃y ∈ \rhs : y ≤ x \\\\
151 /// &∧ ∃y ∈ \rhs, ∀x ∈ \self : x < y.
152 /// \end{align*}
153 /// $$
154 ///
155 /// ```text
156 /// a b : a=b
157 /// self: •————• : self: •
158 /// rhs: •————————• : rhs: •——————•
159 /// c d : c d
160 /// ```
161 ///
162 /// Inverse: [`Overlap::StartedBy`].
163 Starts,
164
165 /// Both $\self = \[a, b\]$ and $rhs = \[c, d\]$ are nonempty and $c < a ∧ b < d$.
166 ///
167 /// Equivalently,
168 ///
169 /// $$
170 /// \begin{align*}
171 /// \self ≠ ∅ ∧ \rhs ≠ ∅
172 /// &∧ ∃y ∈ \rhs, ∀x ∈ \self : y < x \\\\
173 /// &∧ ∃y ∈ \rhs, ∀x ∈ \self : x < y.
174 /// \end{align*}
175 /// $$
176 ///
177 /// ```text
178 /// a b
179 /// self: •————•
180 /// rhs: •————————•
181 /// c d
182 /// ```
183 ///
184 /// Inverse: [`Overlap::Contains`].
185 ContainedBy,
186
187 /// Both $\self = \[a, b\]$ and $rhs = \[c, d\]$ are nonempty and $c < a ∧ b = d$.
188 ///
189 /// Equivalently,
190 ///
191 /// $$
192 /// \begin{align*}
193 /// \self ≠ ∅ ∧ \rhs ≠ ∅
194 /// &∧ ∃y ∈ \rhs, ∀x ∈ \self : y < x \\\\
195 /// &∧ ∀y ∈ \rhs, ∃x ∈ \self : y ≤ x \\\\
196 /// &∧ ∀x ∈ \self, ∃y ∈ \rhs : x ≤ y.
197 /// \end{align*}
198 /// $$
199 ///
200 /// ```text
201 /// a b : a=b
202 /// self: •————• : self: •
203 /// rhs: •————————• : rhs: •——————•
204 /// c d : c d
205 /// ```
206 ///
207 /// Inverse: [`Overlap::FinishedBy`].
208 Finishes,
209
210 /// Both $\self = \[a, b\]$ and $rhs = \[c, d\]$ are nonempty and $a = c ∧ b = d$.
211 ///
212 /// Equivalently,
213 ///
214 /// $$
215 /// \begin{align*}
216 /// \self ≠ ∅ ∧ \rhs ≠ ∅
217 /// &∧ ∀x ∈ \self, ∃y ∈ \rhs : x = y \\\\
218 /// &∧ ∀y ∈ \rhs, ∃x ∈ \self : y = x.
219 /// \end{align*}
220 /// $$
221 ///
222 /// ```text
223 /// a b : a=b
224 /// self: •——————• : self: •
225 /// rhs: •——————• : rhs: •
226 /// c d : c=d
227 /// ```
228 Equals,
229
230 /// Both $\self = \[a, b\]$ and $rhs = \[c, d\]$ are nonempty and $a < c ∧ b = d$.
231 ///
232 /// Equivalently,
233 ///
234 /// $$
235 /// \begin{align*}
236 /// \self ≠ ∅ ∧ \rhs ≠ ∅
237 /// &∧ ∃x ∈ \self, ∀y ∈ \rhs : x < y \\\\
238 /// &∧ ∀x ∈ \self, ∃y ∈ \rhs : x ≤ y \\\\
239 /// &∧ ∀y ∈ \rhs, ∃x ∈ \self : y ≤ x.
240 /// \end{align*}
241 /// $$
242 ///
243 /// ```text
244 /// a b : a b
245 /// self: •————————• : self: •——————•
246 /// rhs: •————• : rhs: •
247 /// c d : c=d
248 /// ```
249 ///
250 /// Inverse: [`Overlap::Finishes`].
251 FinishedBy,
252
253 /// Both $\self = \[a, b\]$ and $rhs = \[c, d\]$ are nonempty and $a < c ∧ d < b$.
254 ///
255 /// Equivalently,
256 ///
257 /// $$
258 /// \begin{align*}
259 /// \self ≠ ∅ ∧ \rhs ≠ ∅
260 /// &∧ ∃x ∈ \self, ∀y ∈ \rhs : x < y \\\\
261 /// &∧ ∃x ∈ \self, ∀y ∈ \rhs : y < x.
262 /// \end{align*}
263 /// $$
264 ///
265 /// ```text
266 /// a b
267 /// self: •————————•
268 /// rhs: •————•
269 /// c d
270 /// ```
271 ///
272 /// Inverse: [`Overlap::ContainedBy`].
273 Contains,
274
275 /// Both $\self = \[a, b\]$ and $rhs = \[c, d\]$ are nonempty and $a = c ∧ d < b$.
276 ///
277 /// Equivalently,
278 ///
279 /// $$
280 /// \begin{align*}
281 /// \self ≠ ∅ ∧ \rhs ≠ ∅
282 /// &∧ ∀x ∈ \self, ∃y ∈ \rhs : y ≤ x \\\\
283 /// &∧ ∀y ∈ \rhs, ∃x ∈ \self : x ≤ y \\\\
284 /// &∧ ∃x ∈ \self, ∀y ∈ \rhs : y < x.
285 /// \end{align*}
286 /// $$
287 ///
288 /// ```text
289 /// a b : a b
290 /// self: •————————• : self: •——————•
291 /// rhs: •————• : rhs: •
292 /// c d : c=d
293 /// ```
294 ///
295 /// Inverse: [`Overlap::Starts`].
296 StartedBy,
297
298 /// Both $\self = \[a, b\]$ and $rhs = \[c, d\]$ are nonempty and $c < a ∧ a < d ∧ d < b$.
299 ///
300 /// Equivalently,
301 ///
302 /// $$
303 /// \begin{align*}
304 /// \self ≠ ∅ ∧ \rhs ≠ ∅
305 /// &∧ ∃y ∈ \rhs, ∀x ∈ \self : y < x \\\\
306 /// &∧ ∃x ∈ \self, ∀y ∈ \rhs : y < x \\\\
307 /// &∧ ∃y ∈ \rhs, ∃x ∈ \self : x < y.
308 /// \end{align*}
309 /// $$
310 ///
311 /// ```text
312 /// a b
313 /// self: •——————•
314 /// rhs: •——————•
315 /// c d
316 /// ```
317 ///
318 /// Inverse: [`Overlap::Overlaps`].
319 OverlappedBy,
320
321 /// Both $\self = \[a, b\]$ and $rhs = \[c, d\]$ are nonempty and $c < d ∧ a = d ∧ a < b$.
322 ///
323 /// Equivalently,
324 ///
325 /// $$
326 /// \begin{align*}
327 /// \self ≠ ∅ ∧ \rhs ≠ ∅
328 /// &∧ ∀y ∈ \rhs, ∀x ∈ \self : y ≤ x \\\\
329 /// &∧ ∃y ∈ \rhs, ∃x ∈ \self : y = x \\\\
330 /// &∧ ∃y ∈ \rhs, ∀x ∈ \self : y < x.
331 /// \end{align*}
332 /// $$
333 ///
334 /// ```text
335 /// a b
336 /// self: •——————•
337 /// rhs: •——————•
338 /// c d
339 /// ```
340 ///
341 /// Inverse: [`Overlap::Meets`].
342 MetBy,
343
344 /// Both $\self = \[a, b\]$ and $rhs = \[c, d\]$ are nonempty and $d < a$.
345 ///
346 /// Equivalently,
347 ///
348 /// $$
349 /// \self ≠ ∅ ∧ \rhs ≠ ∅ ∧ ∀y ∈ \rhs, ∀x ∈ \self : y < x.
350 /// $$
351 ///
352 /// ```text
353 /// a b
354 /// self: •——————•
355 /// rhs: •——————•
356 /// c d
357 /// ```
358 ///
359 /// Inverse: [`Overlap::Before`].
360 After,
361}
362
363impl Interval {
364 /// Returns the overlapping state of `self` and `rhs`.
365 /// See [`Overlap`] for the possible states to be returned.
366 pub fn overlap(self, rhs: Self) -> Overlap {
367 use Overlap::*;
368
369 if self.is_empty() {
370 if rhs.is_empty() {
371 return BothEmpty;
372 } else {
373 return FirstEmpty;
374 }
375 }
376 if rhs.is_empty() {
377 return SecondEmpty;
378 }
379
380 let a = self.inf_raw();
381 let b = self.sup_raw();
382 let c = rhs.inf_raw();
383 let d = rhs.sup_raw();
384
385 // | aRc | aRd | bRc | bRd
386 // | < = > | < = > | < = > | < = >
387 // ----+-------+-------+-------+-------
388 // B | x | x | x | x
389 // M | x | x | x | x
390 // O | x | x | x | x
391 // S | x | x | ? ? | x
392 // Cb | x | x | x | x
393 // F | x | ? ? | x | x
394 // E | x | ? ? | ? ? | x
395 // Fb | x | x | ? ? | x
396 // C | x | x | x | x
397 // Sb | x | ? ? | x | x
398 // Ob | x | x | x | x
399 // Mb | x | x | x | x
400 // A | x | x | x | x
401
402 #[allow(clippy::collapsible_else_if, clippy::collapsible_if)]
403 if b < d {
404 if a < c {
405 if b < c {
406 Before
407 } else if b == c {
408 Meets
409 } else {
410 Overlaps
411 }
412 } else {
413 if a == c {
414 Starts
415 } else {
416 ContainedBy
417 }
418 }
419 } else if b == d {
420 if a > c {
421 Finishes
422 } else if a == c {
423 Equals
424 } else {
425 FinishedBy
426 }
427 } else {
428 if a <= c {
429 if a < c {
430 Contains
431 } else {
432 StartedBy
433 }
434 } else {
435 if a < d {
436 OverlappedBy
437 } else if a == d {
438 MetBy
439 } else {
440 After
441 }
442 }
443 }
444 }
445}
446
447impl DecInterval {
448 /// Applies [`Interval::overlap`] to the interval parts of `self` and `rhs` and returns the result.
449 ///
450 /// [`None`] is returned if `self` or `rhs` is NaI.
451 pub fn overlap(self, rhs: Self) -> Option<Overlap> {
452 if self.is_nai() || rhs.is_nai() {
453 return None;
454 }
455
456 Some(self.x.overlap(rhs.x))
457 }
458}
459
460#[cfg(test)]
461mod tests {
462 use crate::*;
463 use DecInterval as DI;
464
465 #[test]
466 fn nai() {
467 assert_eq!(DI::NAI.overlap(DI::PI), None);
468 assert_eq!(DI::PI.overlap(DI::NAI), None);
469 }
470
471 #[test]
472 fn pattern() {
473 use Overlap::*;
474 // Pattern matching results in a more efficient code than using bitmasks as the compiler
475 // can eliminate unnecessary comparisons.
476 assert!(matches!(
477 const_interval!(1.0, 2.0).overlap(const_interval!(3.0, 4.0)),
478 BothEmpty | FirstEmpty | SecondEmpty | Before | After
479 ))
480 }
481}