unicode_intervals/
intervalset.rs

1use crate::Interval;
2
3/// A collection of non-overlapping Unicode codepoint intervals that enables interval-based
4/// operations, such as iteration over all Unicode codepoints or finding the codepoint at a
5/// specific position within the intervals.
6#[derive(Debug, Clone)]
7pub struct IntervalSet {
8    intervals: Vec<Interval>,
9    offsets: Vec<u32>,
10    size: u32,
11}
12
13impl IntervalSet {
14    #[must_use]
15    pub(crate) fn new(intervals: Vec<Interval>) -> IntervalSet {
16        let mut offsets = vec![0];
17        offsets.reserve_exact(intervals.len());
18        let mut size = 0;
19        // INVARIANT: `right` is always `>= left`, hence no overflow
20        #[allow(clippy::arithmetic_side_effects)]
21        for (left, right) in &intervals {
22            size += *right - *left + 1;
23            offsets.push(size);
24        }
25        IntervalSet {
26            intervals,
27            offsets,
28            size,
29        }
30    }
31
32    /// Returns the number of Unicode codepoints in the interval set.
33    ///
34    /// # Examples
35    ///
36    /// ```rust
37    /// # use unicode_intervals::UnicodeCategory;
38    /// let interval_set = unicode_intervals::query()
39    ///     .include_categories(UnicodeCategory::UPPERCASE_LETTER)
40    ///     .interval_set()
41    ///     .expect("Invalid query input");
42    /// assert_eq!(interval_set.len(), 1886);
43    /// ```
44    #[inline]
45    #[must_use]
46    pub fn len(&self) -> usize {
47        self.size as usize
48    }
49
50    /// Returns `true` if the interval set contains no elements.
51    ///
52    /// # Examples
53    ///
54    /// ```rust
55    /// # use unicode_intervals::UnicodeCategory;
56    /// let interval_set = unicode_intervals::query()
57    ///     .include_categories(UnicodeCategory::UPPERCASE_LETTER)
58    ///     // The first upper case letter has 65
59    ///     .max_codepoint(50)
60    ///     .interval_set()
61    ///     .expect("Invalid query input");
62    /// assert!(interval_set.is_empty());
63    /// ```
64    #[inline]
65    #[must_use]
66    pub const fn is_empty(&self) -> bool {
67        self.size == 0
68    }
69
70    /// Returns `true` if the interval set contains a codepoint with the given value.
71    ///
72    /// # Examples
73    ///
74    /// ```rust
75    /// # use unicode_intervals::UnicodeCategory;
76    /// let interval_set = unicode_intervals::query()
77    ///     .include_categories(UnicodeCategory::UPPERCASE_LETTER)
78    ///     .interval_set()
79    ///     .expect("Invalid query input");
80    /// assert!(interval_set.contains('C'));
81    /// assert!(!interval_set.contains('a'));
82    /// ```
83    #[inline]
84    #[must_use]
85    pub fn contains(&self, codepoint: impl Into<u32>) -> bool {
86        self.index_of(codepoint.into()).is_some()
87    }
88
89    /// Returns the codepoint at `index` in the `IntervalSet`.
90    ///
91    /// # Examples
92    ///
93    /// ```rust
94    /// # use unicode_intervals::UnicodeCategory;
95    /// let interval_set = unicode_intervals::query()
96    ///     .include_categories(UnicodeCategory::UPPERCASE_LETTER)
97    ///     .interval_set()
98    ///     .expect("Invalid query input");
99    /// // Get 10th codepoint in this interval set
100    ///assert_eq!(interval_set.codepoint_at(10), Some('K' as u32));
101    /// ```
102    #[inline]
103    #[must_use]
104    pub fn codepoint_at(&self, index: u32) -> Option<u32> {
105        if index >= self.size {
106            return None;
107        }
108        // Last interval whose start offset is `<= index`. `offsets[0]` is always 0 and `index`
109        // is in range, so the partition point is at least 1 and the subtraction can't underflow.
110        #[allow(clippy::arithmetic_side_effects)]
111        let current = self.offsets.partition_point(|&offset| offset <= index) - 1;
112        // INVARIANT: `index >= offsets[current]` and values are small enough to not overflow.
113        #[allow(clippy::arithmetic_side_effects)]
114        Some(self.intervals[current].0 + index - self.offsets[current])
115    }
116
117    /// Returns the index of a specific codepoint in the `IntervalSet`.
118    ///
119    /// # Examples
120    ///
121    /// ```rust
122    /// # use unicode_intervals::UnicodeCategory;
123    /// let interval_set = unicode_intervals::query()
124    ///     .include_categories(UnicodeCategory::UPPERCASE_LETTER)
125    ///     .interval_set()
126    ///     .expect("Invalid query input");
127    /// assert_eq!(interval_set.index_of('A'), Some(0));
128    /// assert_eq!(interval_set.index_of('c'), None);
129    /// ```
130    #[inline]
131    #[must_use]
132    pub fn index_of(&self, codepoint: impl Into<u32>) -> Option<u32> {
133        let codepoint = codepoint.into();
134        // Last interval whose left bound is `<= codepoint`.
135        let idx = self
136            .intervals
137            .partition_point(|&(left, _)| left <= codepoint);
138        if idx == 0 {
139            return None;
140        }
141        // INVARIANT: `idx >= 1` per the check above.
142        #[allow(clippy::arithmetic_side_effects)]
143        let (left, right) = self.intervals[idx - 1];
144        if codepoint <= right {
145            // INVARIANT: `left <= codepoint` and offsets are small enough to not overflow.
146            #[allow(clippy::arithmetic_side_effects)]
147            Some(self.offsets[idx - 1] + (codepoint - left))
148        } else {
149            None
150        }
151    }
152
153    /// Returns the index of a specific codepoint in the `IntervalSet` if it is present in the set,
154    /// or the index of the closest codepoint that is greater than the given one.
155    ///
156    /// If the given codepoint is greater than the largest codepoint in the set, then the set's
157    /// size is returned.
158    ///
159    /// # Examples
160    ///
161    /// ```rust
162    /// # use unicode_intervals::UnicodeCategory;
163    /// let interval_set = unicode_intervals::query()
164    ///     .include_categories(UnicodeCategory::UPPERCASE_LETTER)
165    ///     .interval_set()
166    ///     .expect("Invalid query input");
167    /// assert_eq!(interval_set.index_above('Z'), 25);
168    /// ```
169    #[inline]
170    #[must_use]
171    pub fn index_above(&self, codepoint: impl Into<u32>) -> u32 {
172        let codepoint = codepoint.into();
173        // Last interval whose left bound is `<= codepoint`.
174        let idx = self
175            .intervals
176            .partition_point(|&(left, _)| left <= codepoint);
177        if idx > 0 {
178            // INVARIANT: `idx >= 1` per the check above.
179            #[allow(clippy::arithmetic_side_effects)]
180            let (left, right) = self.intervals[idx - 1];
181            if codepoint <= right {
182                // INVARIANT: `left <= codepoint` and offsets are small enough to not overflow.
183                #[allow(clippy::arithmetic_side_effects)]
184                return self.offsets[idx - 1] + (codepoint - left);
185            }
186        }
187        // `codepoint` falls in a gap (or after the last interval): the next codepoint is the
188        // start of interval `idx`, whose index is `offsets[idx]` (== `size` when `idx == len`).
189        self.offsets[idx]
190    }
191
192    /// Returns an iterator over all codepoints in all contained intervals.
193    ///
194    /// # Examples
195    ///
196    /// ```rust
197    /// # use unicode_intervals::UnicodeCategory;
198    /// let interval_set = unicode_intervals::query()
199    ///     .include_categories(UnicodeCategory::UPPERCASE_LETTER)
200    ///     .max_codepoint(67)
201    ///     .interval_set()
202    ///     .expect("Invalid query input");
203    /// let mut iterator = interval_set.iter();
204    /// assert_eq!(iterator.next(), Some('A' as u32));
205    /// assert_eq!(iterator.next(), Some('B' as u32));
206    /// assert_eq!(iterator.next(), Some('C' as u32));
207    /// assert_eq!(iterator.next(), None);
208    /// ```
209    pub fn iter(&self) -> Codepoints<'_> {
210        fn expand((left, right): Interval) -> core::ops::RangeInclusive<u32> {
211            left..=right
212        }
213        let expand: Expand = expand;
214        Codepoints(self.intervals.iter().copied().flat_map(expand))
215    }
216}
217
218type Expand = fn(Interval) -> core::ops::RangeInclusive<u32>;
219
220/// Iterator over the codepoints of an [`IntervalSet`].
221#[derive(Debug, Clone)]
222pub struct Codepoints<'a>(
223    core::iter::FlatMap<
224        core::iter::Copied<core::slice::Iter<'a, Interval>>,
225        core::ops::RangeInclusive<u32>,
226        Expand,
227    >,
228);
229
230impl Iterator for Codepoints<'_> {
231    type Item = u32;
232
233    #[inline]
234    fn next(&mut self) -> Option<u32> {
235        self.0.next()
236    }
237}
238
239impl DoubleEndedIterator for Codepoints<'_> {
240    #[inline]
241    fn next_back(&mut self) -> Option<u32> {
242        self.0.next_back()
243    }
244}
245
246impl<'a> IntoIterator for &'a IntervalSet {
247    type Item = u32;
248    type IntoIter = Codepoints<'a>;
249
250    #[inline]
251    fn into_iter(self) -> Codepoints<'a> {
252        self.iter()
253    }
254}
255
256#[cfg(test)]
257mod tests {
258    use super::*;
259    use crate::{UnicodeCategory, UnicodeVersion};
260    use test_case::test_case;
261
262    // Pinned to a fixed Unicode version so the expected indices/counts below stay
263    // deterministic across Unicode upgrades; these tests exercise `IntervalSet`
264    // mechanics, not the latest Unicode data.
265    fn uppercase_letters() -> IntervalSet {
266        UnicodeVersion::V15_0_0
267            .query()
268            .include_categories(UnicodeCategory::UPPERCASE_LETTER)
269            .interval_set()
270            .expect("Invalid query input")
271    }
272
273    #[test_case(vec![(1, 1)])]
274    #[test_case(vec![])]
275    fn test_index_not_present(intervals: Vec<Interval>) {
276        assert!(IntervalSet::new(intervals).index_of(0_u32).is_none());
277    }
278
279    #[test_case(vec![], 1, None)]
280    #[test_case(vec![(1, 10)], 11, None)]
281    fn test_get(intervals: Vec<Interval>, index: u32, expected: Option<u32>) {
282        assert_eq!(IntervalSet::new(intervals).codepoint_at(index), expected);
283    }
284
285    #[test_case(vec![(1, 10)], 1, 0)]
286    #[test_case(vec![(1, 10)], 2, 1)]
287    #[test_case(vec![(1, 10)], 100, 10)]
288    fn test_index_above(intervals: Vec<Interval>, index: u32, expected: u32) {
289        assert_eq!(IntervalSet::new(intervals).index_above(index), expected);
290    }
291
292    #[test_case('Z' as u32, 25; "In the set")]
293    #[test_case('b' as u32, 26; "Not in the set")]
294    #[test_case(125218, 1831; "Greater than all")]
295    fn test_index_above_with_uppercase_letters(codepoint: u32, expected: u32) {
296        let interval_set = uppercase_letters();
297        assert_eq!(interval_set.index_above(codepoint), expected);
298    }
299
300    #[test_case('C', true)]
301    #[test_case('a', false)]
302    fn test_contains(codepoint: char, expected: bool) {
303        let interval_set = uppercase_letters();
304        assert_eq!(interval_set.contains(codepoint), expected);
305    }
306
307    #[test_case(10, Some('K' as u32); "Look from left")]
308    #[test_case(27, Some('Á' as u32); "Look from right")]
309    #[test_case(1830, Some(125217); "Max codepoint in the set")]
310    #[test_case(10000, None)]
311    #[test_case(u32::MAX, None)]
312    fn test_codepoint_at(index: u32, expected: Option<u32>) {
313        let interval_set = uppercase_letters();
314        assert_eq!(interval_set.codepoint_at(index), expected);
315    }
316
317    #[test]
318    fn test_codepoint_at_empty_set() {
319        let interval_set = IntervalSet::new(vec![]);
320        assert!(interval_set.codepoint_at(0).is_none());
321    }
322
323    // Oracle: compare every lookup method against a flattened reference over a set
324    // with single-element intervals, multi-element intervals, and gaps between them.
325    #[test]
326    fn test_lookups_against_oracle() {
327        let intervals = vec![(1, 3), (10, 12), (20, 20), (100, 200)];
328        let set = IntervalSet::new(intervals.clone());
329        // Reference: every codepoint paired with its index, in order.
330        let flat: Vec<u32> = intervals
331            .iter()
332            .flat_map(|(left, right)| *left..=*right)
333            .collect();
334        let total = u32::try_from(flat.len()).expect("fits in u32");
335
336        // codepoint_at over every valid index, plus past the end.
337        for (index, expected) in (0u32..).zip(flat.iter()) {
338            assert_eq!(
339                set.codepoint_at(index),
340                Some(*expected),
341                "codepoint_at({index})"
342            );
343        }
344        assert_eq!(set.codepoint_at(total), None);
345
346        // index_of / contains / index_above over the full codepoint span and beyond.
347        for codepoint in 0..=210_u32 {
348            let expected_index = (0u32..)
349                .zip(flat.iter())
350                .find(|(_, &c)| c == codepoint)
351                .map(|(index, _)| index);
352            assert_eq!(
353                set.index_of(codepoint),
354                expected_index,
355                "index_of({codepoint})"
356            );
357            assert_eq!(
358                set.contains(codepoint),
359                expected_index.is_some(),
360                "contains({codepoint})"
361            );
362            // Index of the first codepoint `>= codepoint`, or `total` if none.
363            let expected_above = (0u32..)
364                .zip(flat.iter())
365                .find(|(_, &c)| c >= codepoint)
366                .map_or(total, |(index, _)| index);
367            assert_eq!(
368                set.index_above(codepoint),
369                expected_above,
370                "index_above({codepoint})"
371            );
372        }
373    }
374
375    #[test_case('K' as u32, Some(10); "Look from left")]
376    #[test_case('Á' as u32, Some(27); "Look from right")]
377    #[test_case(125184, Some(1797))]
378    #[test_case(5, None)]
379    fn test_index_of(codepoint: u32, expected: Option<u32>) {
380        let interval_set = uppercase_letters();
381        assert_eq!(interval_set.index_of(codepoint), expected);
382    }
383
384    #[test]
385    fn test_iter() {
386        let intervals = crate::query()
387            .include_categories(UnicodeCategory::LOWERCASE_LETTER)
388            .intervals()
389            .expect("Invalid query input");
390        let interval_set = IntervalSet::new(intervals);
391        let codepoints: Vec<_> = interval_set.iter().collect();
392        let mut expected = Vec::with_capacity(interval_set.len());
393        for (left, right) in
394            UnicodeVersion::latest().intervals_for(UnicodeCategory::LOWERCASE_LETTER)
395        {
396            for codepoint in *left..=*right {
397                expected.push(codepoint);
398            }
399        }
400        assert_eq!(codepoints, expected);
401        assert_eq!(interval_set.len(), codepoints.len());
402        assert!(!interval_set.is_empty());
403    }
404
405    #[test]
406    fn test_iter_rev() {
407        let interval_set = uppercase_letters();
408        let mut iter = interval_set.iter().rev();
409        assert_eq!(iter.next(), Some(125217));
410    }
411
412    #[test]
413    fn test_into_iterator_for_ref() {
414        let interval_set = IntervalSet::new(vec![(65, 67), (70, 70)]);
415        let collected: Vec<u32> = (&interval_set).into_iter().collect();
416        assert_eq!(collected, vec![65, 66, 67, 70]);
417        let mut via_for_loop = Vec::new();
418        for codepoint in &interval_set {
419            via_for_loop.push(codepoint);
420        }
421        assert_eq!(via_for_loop, vec![65, 66, 67, 70]);
422    }
423
424    #[test]
425    #[allow(clippy::redundant_clone)]
426    fn test_interval_set_traits() {
427        let interval_set = IntervalSet::new(vec![(0, 1)]);
428        let _ = interval_set.clone();
429        assert_eq!(
430            format!("{interval_set:?}"),
431            "IntervalSet { intervals: [(0, 1)], offsets: [0, 2], size: 2 }"
432        );
433    }
434}
unicode_intervals/intervalset.rs

unicode_intervals/
intervalset.rs
