allen_intervals/
relation.rs

1use std::cmp::Ordering;
2
3use crate::{
4    Bb, Be, Bounds, Eb, Ee, FromIntervals, Interval, IntervalBounds, IntervalError, IntervalFrom,
5    IntervalFull, IntervalTo, NonEmpty, TryFromIntervals,
6};
7
8mod contains;
9mod equals;
10mod finishes;
11mod meets;
12mod overlaps;
13mod precedes;
14mod starts;
15
16pub use self::{
17    contains::*, equals::*, finishes::*, meets::*, overlaps::*, precedes::*, starts::*,
18};
19
20#[derive(Clone, Copy, Debug, Hash, Eq, PartialEq, Ord, PartialOrd)]
21enum RelationOrder {
22    Precedes,
23    Meets,
24    Overlaps,
25    IsFinishedBy,
26    Contains,
27    Starts,
28    Equals,
29    IsStartedBy,
30    IsContainedBy,
31    Finishes,
32    IsOverlappedBy,
33    IsMetBy,
34    IsPrecededBy,
35}
36
37/// A type describing the possible relations between two intervals (e.g. `s` and `t`).
38///
39/// The relations are comparable (via `Ord`) by the degree to which `s` begins before `t` and then within that by the degree to which `s` ends before `t`.
40///
41/// Six pairs of the relations are converses. For example, the converse of "s precedes t" is "t is preceded by s";
42/// whenever the first relation is true, its converse is true also. The thirteenth, "s equals t", is its own converse
43#[derive(Clone, Copy, Debug, Hash, PartialEq, Eq)]
44pub enum Relation {
45    /// `Precedes { is_inverted: false }`:
46    ///
47    /// ```plain
48    /// s: ┌────────┐
49    /// t:            └────────┘
50    /// ```
51    ///
52    /// `Precedes { is_inverted: true }`:
53    ///
54    /// ```plain
55    /// s:            ┌────────┐
56    /// t: └────────┘
57    /// ```
58    Precedes {
59        /// `true` iff the relation is inverted, otherwise `false.
60        ///
61        /// - `false` => "s precedes t"
62        /// - `true` => "s is preceded by t"
63        is_inverted: bool,
64    },
65    /// `Meets { is_inverted: false }`:
66    ///
67    /// ```plain
68    /// s: ┌────────┐
69    /// t:          └────────┘
70    /// ```
71    ///
72    /// `Meets { is_inverted: true }`:
73    ///
74    /// ```plain
75    /// s:          ┌────────┐
76    /// t: └────────┘
77    /// ```
78    Meets {
79        /// `true` iff the relation is inverted, otherwise `false.
80        ///
81        /// - `false` => "s meets t"
82        /// - `true` => "s is met by t"
83        is_inverted: bool,
84    },
85    /// `Overlaps { is_inverted: false }`:
86    ///
87    /// ```plain
88    /// s: ┌────────┐
89    /// t:      └────────┘
90    /// ```
91    ///
92    /// `Overlaps { is_inverted: true }`:
93    ///
94    /// ```plain
95    /// s:      ┌────────┐
96    /// t: └────────┘
97    /// ```
98    Overlaps {
99        /// `true` iff the relation is inverted, otherwise `false.
100        ///
101        /// - `false` => "s overlaps t"
102        /// - `true` => "s is overlapped by t"
103        is_inverted: bool,
104    },
105    /// `Finishes { is_inverted: false }`:
106    ///
107    /// ```plain
108    /// s:         ┌────────┐
109    /// t: └────────────────┘
110    ///
111    /// `Finishes { is_inverted: true }`:
112    ///
113    /// ```plain
114    /// s: ┌────────────────┐
115    /// t:         └────────┘
116    /// ```
117    Finishes {
118        /// `true` iff the relation is inverted, otherwise `false.
119        ///
120        /// - `false` => "s finishes t"
121        /// - `true` => "s is finished by t"
122        is_inverted: bool,
123    },
124    /// `Contains { is_inverted: false }`:
125    ///
126    /// ```plain
127    /// s: ┌────────────────┐
128    /// t:     └────────┘
129    /// ```
130    ///
131    /// `Contains { is_inverted: true }`:
132    ///
133    /// ```plain
134    /// s:     ┌────────┐
135    /// t: └────────────────┘
136    /// ```
137    Contains {
138        /// `true` iff the relation is inverted, otherwise `false.
139        ///
140        /// - `false` => "s contains t"
141        /// - `true` => "s is contained by t"
142        is_inverted: bool,
143    },
144    /// `Starts { is_inverted: false }`:
145    ///
146    /// ```plain
147    /// s: ┌────────┐
148    /// t: └────────────────┘
149    /// ```
150    ///
151    /// `Starts { is_inverted: true }`:
152    ///
153    /// ```plain
154    /// s: ┌────────────────┐
155    /// t: └────────┘
156    /// ```
157    Starts {
158        /// `true` iff the relation is inverted, otherwise `false.
159        ///
160        /// - `false` => "s starts t"
161        /// - `true` => "s is started by t"
162        is_inverted: bool,
163    },
164    /// `Equals`:
165    ///
166    /// ```plain
167    /// s: ┌────────┐
168    /// t: └────────┘
169    /// ```
170    Equals,
171}
172
173impl Relation {
174    #[inline]
175    fn from_bounds<T>(s: &Bounds<T>, t: &Bounds<T>) -> Self
176    where
177        T: Ord,
178    {
179        let bb = Bb::from_bounds(&s.start, &t.start);
180        let be = Be::from_bounds(&s.start, &t.end);
181        let eb = Eb::from_bounds(&s.end, &t.start);
182        let ee = Ee::from_bounds(&s.end, &t.end);
183
184        Self::from_atomic_relations(bb, be, eb, ee)
185    }
186
187    #[inline]
188    fn try_from_bounds<T>(s: &Bounds<T>, t: &Bounds<T>) -> Result<Self, IntervalError>
189    where
190        T: PartialOrd,
191    {
192        let bb = Bb::try_from_bounds(&s.start, &t.start)?;
193        let be = Be::try_from_bounds(&s.start, &t.end)?;
194        let eb = Eb::try_from_bounds(&s.end, &t.start)?;
195        let ee = Ee::try_from_bounds(&s.end, &t.end)?;
196
197        Ok(Self::from_atomic_relations(bb, be, eb, ee))
198    }
199
200    /// Each of Allen’s relations can be reduced to a boolean combination of
201    /// a combination of atomic relations.
202    /// By computing each of the atomic relations only once and only if needed,
203    /// we can decrease the overall runtime of the computation of Allen relations.
204    ///
205    /// See the following paper for more info:
206    ///
207    /// > Georgala, K., Sherif, M. A., & Ngonga Ngomo, A. C. (2016).
208    /// > An efficient approach for the generation of Allen relations.
209    /// > In ECAI 2016 (pp. 948-956). IOS Press.
210    #[inline]
211    fn from_atomic_relations(bb: Bb, be: Be, eb: Eb, ee: Ee) -> Self {
212        use Ordering::*;
213
214        match (bb.0, be.0, eb.0, ee.0) {
215            // bf(s,t):
216            // = { EB1(s,t) }
217            (_, _, Less, _) => Self::Precedes { is_inverted: false },
218            // bfi(s,t):
219            // = { BE−1 }
220            // = ¬(BE1(s,t) ∨ BE0(s,t))
221            (_, Greater, _, _) => Self::Precedes { is_inverted: true },
222            // m(s,t):
223            // = { EB0(s,t) }
224            (_, _, Equal, _) => Self::Meets { is_inverted: false },
225            // mi(s,t):
226            // = { BE0(s,t) }
227            (_, Equal, _, _) => Self::Meets { is_inverted: true },
228            // f(s,t):
229            // = { EE0(s,t) ∧ BB−1(s,t) }
230            // = { EE0(s,t) ∧ ¬(BB0(s,t) ∨ BB1(s,t)) }
231            (Greater, _, _, Equal) => Self::Finishes { is_inverted: false },
232            // fi(s,t):
233            // = { BB1(s,t) ∧ EE0(s,t) }
234            (Less, _, _, Equal) => Self::Finishes { is_inverted: true },
235            // st(s,t):
236            // = { BB0(s,t) ∧ EE1(s,t) }
237            (Equal, _, _, Less) => Self::Starts { is_inverted: false },
238            // sti(s,t):
239            // = { BB0(s,t) ∧ EE−1(s,t) }
240            // = { BB0(s,t) ∧ ¬(EE0(s,t) ∨ EE1(s,t)) }
241            (Equal, _, _, Greater) => Self::Starts { is_inverted: true },
242            // di(s,t):
243            // = { BB1(s,t) ∧ EE−1(s,t) }
244            // = { BB1(s,t) ∧ ¬(EE0(s,t) ∨ EE1(s,t)) }
245            (Less, _, _, Greater) => Self::Contains { is_inverted: false },
246            // d(s,t):
247            // = { EE1(s,t) ∧ BB−1(s,t) }
248            // = { EE1(s,t) ∧ ¬(BB0(s,t) ∨ BB1(s,t)) }
249            (Greater, _, _, Less) => Self::Contains { is_inverted: true },
250            // eq(s,t):
251            // = { BB0(s,t) ∧ EE0(s,t) }
252            (Equal, _, _, Equal) => Self::Equals,
253            // ov(s,t):
254            // = { BB1(s,t) ∧ EB−1(s,t) ∧ EE1(s,t) }
255            // = { (BB1(s,t) ∧ EE1(s,t)) ∧ ¬(EB0(s,t) ∨ EB1(s,t)) }
256            (Less, _, Greater, Less) => Self::Overlaps { is_inverted: false },
257            // ovi(s,t):
258            // = { BB−1(s,t) ∧ BE1(s,t) ∧ EE−1(s,t) }
259            // = { (BE1(s,t) ∧ ¬(BB0(s,t) ∨ BB1(s,t))) ∧ ¬(EE0(s,t) ∨ EE1(s,t)) }
260            (Greater, Less, _, Greater) => Self::Overlaps { is_inverted: true },
261        }
262    }
263
264    fn order(&self) -> RelationOrder {
265        match self {
266            Relation::Precedes { is_inverted: false } => RelationOrder::Precedes,
267            Relation::Precedes { is_inverted: true } => RelationOrder::IsPrecededBy,
268            Relation::Meets { is_inverted: false } => RelationOrder::Meets,
269            Relation::Meets { is_inverted: true } => RelationOrder::IsMetBy,
270            Relation::Overlaps { is_inverted: false } => RelationOrder::Overlaps,
271            Relation::Overlaps { is_inverted: true } => RelationOrder::IsOverlappedBy,
272            Relation::Finishes { is_inverted: false } => RelationOrder::Finishes,
273            Relation::Finishes { is_inverted: true } => RelationOrder::IsFinishedBy,
274            Relation::Contains { is_inverted: false } => RelationOrder::Contains,
275            Relation::Contains { is_inverted: true } => RelationOrder::IsContainedBy,
276            Relation::Starts { is_inverted: false } => RelationOrder::IsStartedBy,
277            Relation::Starts { is_inverted: true } => RelationOrder::Starts,
278            Relation::Equals => RelationOrder::Equals,
279        }
280    }
281
282    /// Returns the relation's converse.
283    pub fn as_converse(&self) -> Self {
284        match self {
285            Self::Precedes { is_inverted } => Self::Precedes {
286                is_inverted: !is_inverted,
287            },
288            Self::Meets { is_inverted } => Self::Meets {
289                is_inverted: !is_inverted,
290            },
291            Self::Overlaps { is_inverted } => Self::Overlaps {
292                is_inverted: !is_inverted,
293            },
294            Self::Finishes { is_inverted } => Self::Finishes {
295                is_inverted: !is_inverted,
296            },
297            Self::Contains { is_inverted } => Self::Contains {
298                is_inverted: !is_inverted,
299            },
300            Self::Starts { is_inverted } => Self::Starts {
301                is_inverted: !is_inverted,
302            },
303            Self::Equals => Self::Equals,
304        }
305    }
306}
307
308impl Ord for Relation {
309    #[inline]
310    fn cmp(&self, other: &Self) -> Ordering {
311        self.order().cmp(&other.order())
312    }
313}
314
315impl PartialOrd for Relation {
316    #[inline]
317    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
318        Some(self.cmp(other))
319    }
320}
321
322impl FromIntervals<IntervalFull, IntervalFull> for Relation {
323    #[inline]
324    fn from_intervals(s: &NonEmpty<IntervalFull>, t: &NonEmpty<IntervalFull>) -> Self {
325        assert_eq!(s, t);
326
327        let bb = Bb(Ordering::Equal);
328        let be = Be(Ordering::Less);
329        let eb = Eb(Ordering::Greater);
330        let ee = Ee(Ordering::Equal);
331
332        Self::from_atomic_relations(bb, be, eb, ee)
333    }
334}
335
336impl TryFromIntervals<IntervalFull, IntervalFull> for Relation {
337    #[inline]
338    fn try_from_intervals(
339        s: &NonEmpty<IntervalFull>,
340        t: &NonEmpty<IntervalFull>,
341    ) -> Result<Self, IntervalError> {
342        assert_eq!(s, t);
343
344        let bb = Bb(Ordering::Equal);
345        let be = Be(Ordering::Less);
346        let eb = Eb(Ordering::Greater);
347        let ee = Ee(Ordering::Equal);
348
349        Ok(Self::from_atomic_relations(bb, be, eb, ee))
350    }
351}
352
353macro_rules! from_intervals_impl {
354    ($s:ty, $t:ty) => {
355        impl<T> FromIntervals<$s, $t> for Relation
356        where
357            T: Ord + Copy,
358        {
359            fn from_intervals(s: &NonEmpty<$s>, t: &NonEmpty<$t>) -> Self {
360                Self::from_bounds(&s.0.bounds(), &t.0.bounds())
361            }
362        }
363
364        impl<T> TryFromIntervals<$s, $t> for Relation
365        where
366            T: PartialOrd + Copy,
367        {
368            fn try_from_intervals(
369                s: &NonEmpty<$s>,
370                t: &NonEmpty<$t>,
371            ) -> Result<Self, IntervalError> {
372                Self::try_from_bounds(&s.0.bounds(), &t.0.bounds())
373            }
374        }
375    };
376}
377
378from_intervals_impl!(IntervalFull, IntervalTo<T>);
379from_intervals_impl!(IntervalFull, IntervalFrom<T>);
380from_intervals_impl!(IntervalFull, Interval<T>);
381
382from_intervals_impl!(IntervalTo<T>, IntervalFull);
383from_intervals_impl!(IntervalTo<T>, IntervalTo<T>);
384from_intervals_impl!(IntervalTo<T>, IntervalFrom<T>);
385from_intervals_impl!(IntervalTo<T>, Interval<T>);
386
387from_intervals_impl!(IntervalFrom<T>, IntervalFull);
388from_intervals_impl!(IntervalFrom<T>, IntervalTo<T>);
389from_intervals_impl!(IntervalFrom<T>, IntervalFrom<T>);
390from_intervals_impl!(IntervalFrom<T>, Interval<T>);
391
392from_intervals_impl!(Interval<T>, IntervalFull);
393from_intervals_impl!(Interval<T>, IntervalTo<T>);
394from_intervals_impl!(Interval<T>, IntervalFrom<T>);
395from_intervals_impl!(Interval<T>, Interval<T>);
396
397#[cfg(test)]
398mod tests;
allen_intervals/relation.rs

allen_intervals/
relation.rs
