rustybuzz/hb/
glyph_set.rs

1use alloc::vec::Vec;
2use core::cmp::{self, Ordering};
3use core::ops::RangeInclusive;
4
5use ttf_parser::GlyphId;
6
7/// A set of glyphs.
8///
9/// Performs best when the glyphs are in consecutive ranges.
10#[derive(Clone, Debug)]
11pub struct GlyphSet {
12    ranges: Vec<RangeInclusive<GlyphId>>,
13}
14
15impl GlyphSet {
16    /// Create a new glyph set builder.
17    pub fn builder() -> GlyphSetBuilder {
18        GlyphSetBuilder { ranges: Vec::new() }
19    }
20
21    /// Check whether the glyph is contained in the set.
22    pub fn contains(&self, glyph: GlyphId) -> bool {
23        self.ranges
24            .binary_search_by(|range| {
25                if glyph < *range.start() {
26                    Ordering::Greater
27                } else if glyph <= *range.end() {
28                    Ordering::Equal
29                } else {
30                    Ordering::Less
31                }
32            })
33            .is_ok()
34    }
35}
36
37/// A builder for a [`GlyphSet`].
38#[derive(Clone, Debug)]
39pub struct GlyphSetBuilder {
40    ranges: Vec<RangeInclusive<GlyphId>>,
41}
42
43impl GlyphSetBuilder {
44    /// Insert a single glyph.
45    pub fn insert(&mut self, glyph: GlyphId) {
46        self.ranges.push(glyph..=glyph);
47    }
48
49    /// Insert a range of glyphs.
50    pub fn insert_range(&mut self, range: RangeInclusive<GlyphId>) {
51        self.ranges.push(range);
52    }
53
54    /// Finish the set building.
55    pub fn finish(self) -> GlyphSet {
56        let mut ranges = self.ranges;
57
58        // Sort because we want to use binary search in `GlyphSet::contains`.
59        ranges.sort_by_key(|range| *range.start());
60
61        // The visited and merged ranges are in `ranges[..=left]` and the
62        // unvisited ranges in `ranges[right..]`.
63        let mut left = 0;
64        let mut right = 1;
65
66        // Merge touching and overlapping adjacent ranges.
67        //
68        // The cloning is cheap, it's just needed because `RangeInclusive<T>`
69        // does not implement `Copy`.
70        while let Some(next) = ranges.get(right).cloned() {
71            right += 1;
72
73            if let Some(prev) = ranges.get_mut(left) {
74                // Detect whether the ranges can be merged.
75                //
76                // We add one to `prev.end` because we want to merge touching ranges
77                // like `1..=3` and `4..=5`. We have to be careful with overflow,
78                // hence `saturating_add`.
79                if next.start().0 <= prev.end().0.saturating_add(1) {
80                    *prev = *prev.start()..=cmp::max(*prev.end(), *next.end());
81                    continue;
82                }
83            }
84
85            left += 1;
86            ranges[left] = next.clone();
87        }
88
89        // Can't overflow because `left < ranges.len() <= isize::MAX`.
90        ranges.truncate(left + 1);
91
92        GlyphSet { ranges }
93    }
94}
95
96#[cfg(test)]
97mod tests {
98    use super::*;
99    use alloc::vec;
100
101    #[test]
102    fn test_empty() {
103        assert!(GlyphSet::builder().finish().ranges.is_empty());
104    }
105
106    #[test]
107    fn test_contains() {
108        let mut builder = GlyphSet::builder();
109        builder.insert(GlyphId(1));
110        builder.insert_range(GlyphId(3)..=GlyphId(5));
111        let set = builder.finish();
112        assert!(set.contains(GlyphId(1)));
113        assert!(!set.contains(GlyphId(2)));
114        assert!(set.contains(GlyphId(3)));
115        assert!(set.contains(GlyphId(4)));
116        assert!(set.contains(GlyphId(5)));
117        assert!(!set.contains(GlyphId(6)));
118    }
119
120    #[test]
121    fn test_merge_ranges() {
122        let mut builder = GlyphSet::builder();
123        builder.insert(GlyphId(0));
124        builder.insert_range(GlyphId(2)..=GlyphId(6));
125        builder.insert_range(GlyphId(3)..=GlyphId(7));
126        builder.insert_range(GlyphId(9)..=GlyphId(10));
127        builder.insert(GlyphId(9));
128        builder.insert_range(GlyphId(18)..=GlyphId(21));
129        builder.insert_range(GlyphId(11)..=GlyphId(14));
130        assert_eq!(
131            builder.finish().ranges,
132            vec![
133                GlyphId(0)..=GlyphId(0),
134                GlyphId(2)..=GlyphId(7),
135                GlyphId(9)..=GlyphId(14),
136                GlyphId(18)..=GlyphId(21),
137            ]
138        )
139    }
140
141    #[test]
142    fn test_merge_ranges_at_numeric_boundaries() {
143        let mut builder = GlyphSet::builder();
144        builder.insert_range(GlyphId(3)..=GlyphId(u16::MAX));
145        builder.insert(GlyphId(u16::MAX - 1));
146        builder.insert(GlyphId(2));
147        assert_eq!(
148            builder.finish().ranges,
149            vec![GlyphId(2)..=GlyphId(u16::MAX)]
150        );
151    }
152}
rustybuzz/hb/glyph_set.rs

rustybuzz/hb/
glyph_set.rs
