celox_analysis/
interval.rs

1//! Unit-independent exact interval indexing.
2//!
3//! The index is deliberately separate from the byte-oriented memory adapter.
4//! Clients may use bytes, bits, words, or another ordered unit without lying
5//! about the alias domain.  Construction costs `O(N log N)` time and `O(N)`
6//! space.  One overlap query costs `O(log N + K)`, where `K` is the number of
7//! definitions returned; neither bound depends on the numerical interval
8//! width.
9
10use std::collections::BTreeMap;
11
12#[derive(Debug, Clone, Copy, PartialEq, Eq)]
13pub struct ExactInterval<O, V> {
14    pub object: O,
15    pub start: usize,
16    pub length: usize,
17    pub value: V,
18}
19
20impl<O, V> ExactInterval<O, V> {
21    #[must_use]
22    pub fn end(&self) -> Option<usize> {
23        self.start.checked_add(self.length)
24    }
25}
26
27#[derive(Debug, Clone, Copy, PartialEq, Eq)]
28pub enum DisjointIntervalError<V> {
29    Empty { value: V },
30    Overflow { value: V },
31    Overlap { first: V, second: V },
32}
33
34#[derive(Debug, Clone, Copy)]
35struct Entry<V> {
36    start: usize,
37    end: usize,
38    value: V,
39}
40
41#[derive(Debug)]
42pub struct DisjointIntervalMap<O, V> {
43    objects: BTreeMap<O, Vec<Entry<V>>>,
44}
45
46impl<O: Ord, V: Copy> DisjointIntervalMap<O, V> {
47    pub fn try_new(
48        intervals: impl IntoIterator<Item = ExactInterval<O, V>>,
49    ) -> Result<Self, DisjointIntervalError<V>> {
50        let mut objects = BTreeMap::<O, Vec<Entry<V>>>::new();
51        for interval in intervals {
52            if interval.length == 0 {
53                return Err(DisjointIntervalError::Empty {
54                    value: interval.value,
55                });
56            }
57            let Some(end) = interval.end() else {
58                return Err(DisjointIntervalError::Overflow {
59                    value: interval.value,
60                });
61            };
62            objects.entry(interval.object).or_default().push(Entry {
63                start: interval.start,
64                end,
65                value: interval.value,
66            });
67        }
68
69        for entries in objects.values_mut() {
70            entries.sort_unstable_by_key(|entry| entry.start);
71            for pair in entries.windows(2) {
72                if pair[0].end > pair[1].start {
73                    return Err(DisjointIntervalError::Overlap {
74                        first: pair[0].value,
75                        second: pair[1].value,
76                    });
77                }
78            }
79        }
80        Ok(Self { objects })
81    }
82
83    pub fn overlapping(
84        &self,
85        object: &O,
86        start: usize,
87        length: usize,
88    ) -> Result<Overlapping<'_, V>, InvalidInterval> {
89        if length == 0 {
90            return Err(InvalidInterval::Empty);
91        }
92        let end = start.checked_add(length).ok_or(InvalidInterval::Overflow)?;
93        let entries = self.objects.get(object).map_or(&[][..], Vec::as_slice);
94        let cursor = entries.partition_point(|entry| entry.end <= start);
95        Ok(Overlapping {
96            entries,
97            cursor,
98            end,
99        })
100    }
101}
102
103#[derive(Debug, Clone, Copy, PartialEq, Eq)]
104pub enum InvalidInterval {
105    Empty,
106    Overflow,
107}
108
109pub struct Overlapping<'a, V> {
110    entries: &'a [Entry<V>],
111    cursor: usize,
112    end: usize,
113}
114
115impl<V: Copy> Iterator for Overlapping<'_, V> {
116    type Item = V;
117
118    fn next(&mut self) -> Option<Self::Item> {
119        let entry = self.entries.get(self.cursor)?;
120        if entry.start >= self.end {
121            return None;
122        }
123        self.cursor += 1;
124        Some(entry.value)
125    }
126}
127
128#[cfg(test)]
129mod tests {
130    use super::*;
131
132    #[test]
133    fn exact_queries_return_only_overlapping_disjoint_definitions() {
134        let index = DisjointIntervalMap::try_new([
135            ExactInterval {
136                object: 1u8,
137                start: 0,
138                length: 8,
139                value: 10,
140            },
141            ExactInterval {
142                object: 1,
143                start: 16,
144                length: 8,
145                value: 11,
146            },
147            ExactInterval {
148                object: 2,
149                start: 4,
150                length: 8,
151                value: 12,
152            },
153        ])
154        .unwrap();
155
156        assert_eq!(
157            index.overlapping(&1, 4, 16).unwrap().collect::<Vec<_>>(),
158            vec![10, 11]
159        );
160        assert_eq!(
161            index.overlapping(&1, 8, 8).unwrap().collect::<Vec<_>>(),
162            Vec::<i32>::new()
163        );
164        assert_eq!(
165            index.overlapping(&2, 0, 4).unwrap().collect::<Vec<_>>(),
166            Vec::<i32>::new()
167        );
168    }
169
170    #[test]
171    fn construction_rejects_overlapping_definitions() {
172        let error = DisjointIntervalMap::try_new([
173            ExactInterval {
174                object: 1u8,
175                start: 8,
176                length: 8,
177                value: 3,
178            },
179            ExactInterval {
180                object: 1,
181                start: 0,
182                length: 9,
183                value: 2,
184            },
185        ])
186        .unwrap_err();
187
188        assert_eq!(
189            error,
190            DisjointIntervalError::Overlap {
191                first: 2,
192                second: 3
193            }
194        );
195    }
196
197    #[test]
198    fn numerical_width_does_not_expand_the_index() {
199        let index = DisjointIntervalMap::try_new([ExactInterval {
200            object: 1u8,
201            start: 0,
202            length: 16 * 1024 * 1024,
203            value: 7,
204        }])
205        .unwrap();
206
207        assert_eq!(
208            index
209                .overlapping(&1, 8 * 1024 * 1024, 1)
210                .unwrap()
211                .collect::<Vec<_>>(),
212            vec![7]
213        );
214    }
215}
celox_analysis/interval.rs

celox_analysis/
interval.rs
