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: &RangeInclusive| {
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}
153