int_interval_set/int_co_set/
impls_for_searching.rs

1use super::*;
2
3impl<I: IntCO> IntCOSet<I> {
4    /// Iterates over all canonical intervals intersecting `query`.
5    ///
6    /// The iterator yields original intervals stored in the set,
7    /// not clipped intersection segments.
8    ///
9    /// Complexity: `O(log n + k)`, where `k` is the number of
10    /// returned intervals.
11    #[inline]
12    pub fn intervals_intersecting(&self, query: I) -> impl Iterator<Item = I> + '_ {
13        let i = self
14            .intervals
15            .partition_point(|iv| iv.end_excl() <= query.start());
16
17        self.intervals[i..]
18            .iter()
19            .copied()
20            .take_while(move |iv| iv.start() < query.end_excl())
21    }
22}
23
24impl<I: IntCO> IntCOSet<I> {
25    /// Returns the unique interval containing `x`, if any.
26    ///
27    /// Because the set is canonical, at most one interval can
28    /// contain a single point.
29    ///
30    /// Complexity: `O(log n)`.
31    #[inline]
32    pub fn interval_containing_point(&self, x: I::CoordType) -> Option<I> {
33        let i = self.intervals.partition_point(|iv| iv.start() <= x);
34
35        if i == 0 {
36            return None;
37        }
38
39        let iv = self.intervals[i - 1];
40        iv.contains(x).then_some(iv)
41    }
42}
43
44#[cfg(test)]
45mod tests_for_interval_containing_point;
46#[cfg(test)]
47mod tests_for_intervals_intersecting;
int_interval_set/int_co_set/impls_for_searching.rs

int_interval_set/int_co_set/
impls_for_searching.rs
